Lightweight spinlocks built from GCC atomic operations?

c++, gcc, multithreading, pthreads, thread-safety

Solution

You need a `volatile` qualifier on `lock`, and I would also make it a `sig_atomic_t`. Without the `volatile` qualifier, this code:

    u16 savedlock = lock;
    while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false)
        savedlock = lock;

may not re-read `lock` when updating `savedlock` in the body of the while-loop. Consider the case that `lock` is 0xffff. Then, `savedlock` will be 0xffff prior to checking the loop condition, so the `while` condition will short-circuit prior to calling `__sync_bool_compare_and_swap`. Since `__sync_bool_compare_and_swap` wasn't called, the compiler doesn't encounter a memory barrier, so it might reasonably assume that the value of `lock` hasn't changed underneath you, and avoid re-loading it in `savedlock`.

Re: `sig_atomic_t`, there's a decent discussion here. The same considerations that apply to signal handlers would also apply to threads.

With these changes, I'd guess that your code would be thread-safe. I would still recommend using mutexes, though, since you really don't know how long your RB-tree insert will take in the general case (per my previous comments under the question).

Problem

I'd like to minimize synchronization and write lock-free code when possible in a project of mine. When absolutely necessary I'd love to substitute light-weight spinlocks built from atomic operations for pthread and win32 mutex locks. My understanding is that these are system calls underneath and could cause a context switch (which may be unnecessary for very quick critical sections where simply spinning a few times would be preferable). The atomic operations I'm referring to are well documented here: http://gcc.gnu.org/onlinedocs/gcc-4.4.1/gcc/Atomic-Builtins.html Here is an example to illustrate what I'm talking about. Imagine a RB-tree with multiple readers and writers possible. RBTree::exists() is read-only and thread safe, RBTree::insert() would require exclusive access by a single writer (and no readers) to be safe. Some code: ``` class IntSetTest { private: unsigned short lock; RBTree<int>* myset; public: // ... void add_number(int n) { // Aquire once locked==false (atomic) while (__sync_bool_compare_and_swap(&lock, 0, 0xffff) == false); // Perform a thread-unsafe operation on the set myset->insert(n); // Unlock (atomic) __sync_bool_compare_and_swap(&lock, 0xffff, 0); } bool check_number(int n) { // Increment once the lock is below 0xffff u16 savedlock = lock; while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false) savedlock = lock; // Perform read-only operation bool exists = tree->exists(n); // Decrement savedlock = lock; while (__sync_bool_compare_and_swap(&lock, savedlock, savedlock-1) == false) savedlock = lock; return exists; } }; ``` (lets assume it need not be exception-safe) Is this code indeed thread-safe? Are there any pros/cons to this idea? Any advice? Is the use of spinlocks like this a bad idea if the threads are not truly concurrent? Thanks in advance. ;)

Original source