  This paper presents a new and practical approach to lock-free locks based on
helping, which allows the user to write code using fine-grained locks, but run
it in a lock-free manner.
  Although lock-free locks have been suggested in the past, they are widely
viewed as impractical, have some key limitations, and, as far as we know, have
never been implemented. The paper presents some key techniques that make
lock-free locks practical and more general. The most important technique is an
approach to idempotence -- i.e. making code that runs multiple times appear as
if it ran once. The idea is based on using a shared log among processes running
the same protected code. Importantly, the approach can be library based,
requiring very little if any change to standard code -- code just needs to use
the idempotent versions of memory operations (load, store, LL/SC, allocation,
free).
  We have implemented a C++ library called Flock based on the ideas. Flock
allows lock-based data structures to run in either lock-free or blocking
(traditional locks) mode. We implemented a variety of tree and list-based data
structures with Flock and compare the performance of the lock-free and blocking
modes under a variety of workloads. The lock-free mode is almost as fast as
blocking mode under almost all workloads, and significantly faster when threads
are oversubscribed (more threads than processors). We also compare with several
existing lock-based and lock-free alternatives.
