Lock-Free Locks Revisited
arxiv.org
arxiv.org
flock(2) being the name of the existing file-locking primitive on Linux, this is a terrible name for a new locking library.
That point matters nothing as the problem is not getting symbols mixed up, but name recognition.
DragonlyBSD kernel has locks.
Linux and most free BSDs these days use various lock-free synchronization techniques in the performance sensitive areas.
1. First, make all memory ABA-free, which the paper does in two ways. The first, for CPUs with 128-bit compare-and-swap, is to simply use a 64-bit counter and 64-bit value; the second appears to use a 16-bit epoch and 48-bit pointer value and seems to work by delaying freeing until nobody is in the middle of an operation using that epoch
2. Then, to execute an operation on a data structure using this scheme, a compare-and-swap is used to register a "descriptor" consisting of a pointer to the function performing the operation, its arguments, and then a "log" of values that are initially empty
3. To perform a read, the value is read for memory, and then a compare-and-swap from empty of a log entry is done (incrementing the current log position for the current thread), returning the value from the log entry if someone had already recorded it
4. To perform a write, first a read is performed as described above, and then the write to memory is done with a compare-and-swap from the value read as above
5. If when performing an operation a descriptor already exists, then the operation in that descriptor is executed, and then a compare-and-swap with the empty descriptor is done, and the operation is retried.
So basically at the cost of turning all memory into tagged values and significantly higher overhead, any algorithm with locks can be made lock-free (as long as there are no external interactions such as system calls or MMIO access, or they are idempotent).
The way it works is that the compare-and-swap on the descriptor and the log positions effectively create a global order on all memory writes, and the tagging of all memory locations and stores with compare-and-swap result in a write having no effect if that write has already been performed. The system is lockless because if another thread is in the middle of operation, then it's safe to have the current thread run it as well from the begining.
However, it appears there is no guarantee of a single thread making progress, i.e. a thread could indefinitely find another operation in progress and execute it and never find a window to register and execute its own. This might fixable by allowing threads to queue operations even if some other operation is in progress.
As expected, their experiments show that this scheme is slower than simply taking locks unless there are significantly more threads than cores, in which case this scheme avoids the problem of having to wait on another thread that has been preempted while holding the lock, and thus potentially have very frequent context switches.