RAW-style Lock Manager More...

Classes
struct	RawLock
	An RAW-style lock entry in the queue. More...

struct	RawLockQueue
	An RAW-style lock queue to hold granted and waiting lock requests (RawLock). More...

class	RawXctLockHashMap
	A hashmap for lock entries in transaction's private memory. More...

struct	RawXct
	A shadow transaction object for RAW-style lock manager. More...

class	RawLockBackgroundThread
	The background thread for pre-allocation and garbage collection of object pools used in RAW-style lock manager. More...

Functions
void	atomic_synchronize ()
	Invokes "mfence", which is sfence + lfence. More...

Variables
const int	RAW_XCT_LOCK_HASHMAP_SIZE = 1023

Detailed Description

RAW-style Lock Manager

Classes implementing Read-After-Write (RAW) style lock manager proposed by Jung et al [JUNG13]. This lock manager reduces mutex enter/release and the length of critical sections by employing RAW-style algorithm as much as possible.

Read-After-Write

In short, RAW is a general protocol to Write (Declare) something in a shared variable followed by a memory-barrier, then followed by Read. Assuming all other threads are also running the same protocol, this can be an efficient lightweight synchronization without too many atomic operations or mutex. Membar is also expensive, but not as much as atomic operations and mutex.

Terminology

In this code, we avoid abusing the often misused term "lock-free" because it's confusing especially in our context (lock manager). Instead, we use "RAW-style" to mean that we reduce blocking as much as possible. We say "lock-free" only when it's really lock-free.

Remember, the canonical meaning of "lock-free" is "some call always finishes in a finite number of steps" [HERLIHY]. Lock manager is inherently not such an existence.

Hierarchy

Shore-MT's lock manager had a three-level hierarchy; bucket with hash modulo, queue with precise hash, and each lock. In [JUNG13], a bucket is a queue. This might cause more hash collisions, but adding another level in RAW-style algorithm is quite tricky (eg, how and when we can safely delete the queue?). So, here we do something in-between.

Bucket is a queue. However, each lock also contains the precise hash in the member. When lock-compatibility methods traverse the list, we ignore locks that have different hashes. This gives the same concurrency and yet does not cause 3-level complexity.

Algorithm Overview

In short, [JUNG13] proposes an RAW-style singly-linked list (based on well known lock-free singly-linked list) as lock queue and a garbage collector for it based on generation versioning. Sounds easy?

There are a few complications and simplifications, though.

When we have to really wait (conflicting locks), there is no option other than waiting with mutex or spinning. So, this is not really a lock-free list.
We never insert into lock queue, rather we always append. This makes many operations easier than the original lock-free linked list.
There are several cases we can tolerate false positives (which only results in conservative executions) and even some false negatives (see check_only param of RawLockQueue::acquire()).
Garbage collection has to be based on LSN.

Garbage Collection

RawXct and RawLock are maintained by LSN-based Garbage Collector. See GcPoolForest for more details.

Differences from [JUNG13]

We made a few changes from the original algorithm. The first one is, as described above, we put precise hash in each lock and ignore locks that have different hashes during checks.

Second difference is that we steal a bit from 64 bit pointer to atomically delete an obsolete lock entry. We use MarkablePointer class and the same protocol as the standard LockFreeList with mark-for-death bit. See Chap 9.8 in [HERLIHY].

Third difference is that we physically delete the lock from the queue as soon as we end the transaction. This is required to avoid dangling pointer even with garbage collector.

Fource, we found that spinning while waiting is more efficient than mutex assuming the system does a right throttling to bound the number of active workers. PURE_SPIN_RAWLOCK ifdef controls it.

Finally, we don't have "tail" as a member in RawLockQueue. Again, it's equivalent to the standard Harris-Michael LockFreeList [MICH02].

References

[JUNG13] "A scalable lock manager for multicores" Hyungsoo Jung, Hyuck Han, Alan D. Fekete, Gernot Heiser, Heon Y. Yeom. SIGMOD'13.
Also see MarkablePointer, [MICH02], and [HERLIHY].

Function Documentation

§ atomic_synchronize()

void atomic_synchronize ( )

inline

Invokes "mfence", which is sfence + lfence.

[JUNG13] uses only one type of membar named "atomic_synchronize", not clarifying which place needs full mfence, which place needs only sfence or lfence. This code might result in too conservative barriers. Should revisit later.

Variable Documentation

§ RAW_XCT_LOCK_HASHMAP_SIZE

const int RAW_XCT_LOCK_HASHMAP_SIZE = 1023

Bucket count in RawXctLockHashMap (private lock entry hashmap).

See also: RawXctLockHashMap

Classes

Functions

Variables