Lock-Free Locks Revisited

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 is purely 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 variety of data structures based on trees and lists using the approach and we compare their performance with several lock-based and lock-free alternatives under a wide variety of workloads. Our approach competes well with all these data structures. We also compare the same code run with and without helping turned on