What this project is

This project is a collection of various lock-free synchronization primitives and fast pathed synchronization functions. See here for a definition and explanation of lock-free.

• Lock-free futex based Posix condition variable for Linux --
  This a faster version than NPTL's. Much faster as you can see by the timings here.
• Lock-free futex based eventcount for Linux --
  Eventcounts, your basic non lossy lock-free signaling mechanism. The waiting can't be considered lock-free because it blocks but having the signaling part lock-free has major performance implications.
• atomic_ptr proxy GC
  A proxy GC scheme with an api much like RCU which is also a proxy based GC. Amortizes the atomic_ptr overhead for read access. This has a C++ OO api.
• RCU+SMR - hazard pointers w/o memory barriers
  This is an implementation of Maged Michael's hazard pointers without the need for expensive memory barriers. It also handles non cyclic traversal of linked data structures without the need for some other mechanism like reference counting.
• rcpc (reference counted proxy collector)
  like appc except it's in C, not C++, and only requires single word compare and swap if double word compare and swap or load reserved/store conditional is not available.

Released packages

• eventcount 0.0.0 -- pre-alpha futex based eventcount
• fastcv 0.0.0 -- pre-alpha futex based fast pathed condition variable
• atomic-ptr-plus 0.0.4 -- pre-alpha release of atomic_ptr and appc (atomic pointer proxy collector)
• fastsmr 0.0.3 -- pre-alpha RCU+SMR hazard pointer implementation
• rcpc 0.0.2 -- pre-alpha (yet another) reference counted proxy collector

Status

This kind of project takes a lot of resources, particularly in the area of hardware since it has to be ported to different platforms and tested on multi-core machines. Also, I don't want to freeze the api until I get to use it in a serious application. Since lock-free is about scalability among other things this means applications on the large side which also means a lot of resources. For example, try writing a full blown OLAP database from scratch as a proof of lock-free scalability and to firm out the api. Future development will depend on if and when any resources become available.

Design

These pages are somewhat out of date. Future enhancements to fastsmr will probably entail support for reference counting and/or tracing GC instead of the fifo ordering requirement on scheduling object deallocation. Or maybe not.

Current design issues and direction
Synchronization techniques for possible future implementation.

Lock-free patents

Various lock-free patents and patent applications, some by me, some by others, in the area of lock-free programming.

Patent Applications
• 20060037026 Lightweight reference counting using single-target synchronization
  Lock-free reference counting very similar to atomic_ptr or so it would seem.
• 20040107227 Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation
  Hazard pointers, the SMR (safe memory reclamation) in RCU+SMR
• 20030174572 Non-blocking memory management mechanism for supporting dynamic-sized data structures
  Repeat Offender Problem (ROP)
• 20030140085 Single-word lock-free reference counting
  Lock-free reference counting using ROP. If you have GC, lock-free reference counting is easy, see RCU based refcounting, rcuref, in the Linux kernel.
• 20060130061 Use of rollback RCU with read-side modifications to RCU-protected data structures
  An RCU for preemptive user threads that never panned out. Somewhat moot since RCU+SMR is probably a better way to go. See "RCU for preemptive user threads" usenet references below for earlier discussions on this.

To look at any of the above patent applications go to uspto publication number search and paste in the patent application number.

Patents
• 6,993,770 Lock free reference counting
  using DCAS
• 4,809,168 Passive serialization in a multitasking environment
  An early version of RCU.
• 5,295,262 Read-only access without blocking via access vectors
  Basis for rcpc and part basis for atomic_ptr.
• more RCU patents. See RCU papers below for now.

Stuff previously disclosed on usenet

• 2005/04/22 RCU+SMR, Hazard pointers w/o memory barrier
• 2003/08/12 restartable intervals for RCU
• 2004/04/07 RCU for preemtive user threads
• 2004/06/02 RCU for preemptive user threads
• 2002-11-07 atomic_ptr
  One of the earlier postings on atomic_ptr.
• 1998/06/24 atomic refcounts on powerpc
• 2003-06-19 proxy collector explanation
• 2004-08024 Fastpathed win32 Semaphores
  You can speed up Linux NPTL semaphores with this logic as well.
• 2005-03-28 Using lock-free PCOW
  A brief explanation of how to do lock-free programming with PDR (PCOW (Partial Copy On Write) Deferred Reclaimation).

References

1. RCU papers Paul McKenney's Read, Copy, Update papers. Also contains discussions the general technique and some dicussions and reference to other lock-free algorithms. See annotated bibiography document for more references.
2. Maged Michael's publications page Includes paper on SMR hazard pointers.
3. Maurice Herlihy's publications page. The definitions for lock-free, wait-free, and obstruction-free are out there somewhere.
4. Lock-Free Reference Counting. You can't implement this algorithm unless you have cpu's with DCAS but it does sort of cover the issues of lock-free reference counting.
5. R. K. Treiber. Systems Programming: Coping with Parallelism. RJ 5118, IBM Almaden Research Center, April 1986.