you know what a spinlock is, right?
here's a spinlock:
Lock = AtomicBoolean()
UNLOCKED = false
LOCKED = true
func lock () {
while no timeout {
if Lock.AtomicLoad() == UNLOCKED {
if Lock.CompareAndSwap(UNLOCKED, LOCKED) {
return true
}
spin()
}
return false
}
func unlock() {
compare_and_swap(LOCKED, UNLOCKED)
}
the essence of a spinlock is a little loop with a compare and set, and we don't have to constrain ourselves to an AtomicBoolean.
there's quite a lot you can do with 64 atomic bits, or even 32 atomic bits;
- we can use a
<exclusive bit> <shared count>encoding and get a read-write lock - we store an epoch instead of a flag, and when the epoch is an odd number, the lock is in use.
- this lets us do optimistic reads of the lock, and we can also combne both techniques to get an optimistic rw-lock
the only real problem with a lock like this is starvation, or contention more broadly. it's easy for one thread to get left out when there's a lot of rivals for the lock.
the usual solution to this is to use a waiting list
instead of storing a single lock, we store a linked list of lock entries, and we keep a pointer to the tail of the list.
- when a thread wants the lock, it adds a new entry to the tail of the list
- the first entry in the list is the one holding the lock
- when a thread unlocks, it marks the next entry in the list as owning the lock
- if a thread is the last entry in the list, it marks the list as empty
struct LockEntry {
locked atomic[bool]
next atomicPointer[LockEntry]
}
EndOfList := new LockEntry{}
ListFrozen := new LockEntry{}
Lock := atomicPointer[LockEntry](EndOfList)
func lock() -> LockEntry {
entry = new LockEntry{next: EndOfList}
restartSearch: while True {
head = Lock.AtomicLoad()
if head == EndOfList && head.CompareAndSwap(EndOfList, entry) {
entry.locked.AtomicStore(true) // we are the first entry
return entry
}
while True {
next = head.next.AtomicLoad()
// find the end of the list, if someone has added themselves in
restartTail: while True {
head = next
next = head.next.AtomicLoad()
if next == ListFrozen {
// try again, we found the end of list as it is being deleted
// restart search from Head
continue restartSearch
} else if next == EndOfList {
if !next.CompareAndSwap(EndOfList, entry) {
// someone inserted before us, try searching again
continue restartTail
}
// we are now at the end of the list, so update the tail pointer
while !Lock.CompareAndSwap(head, entry) {
fast-spin()
}
while !entry.locked() {
spin()
}
return entry
}
}
}
}
method (entry LockEntry) unlock() {
// if there's no next pointer, swap in the Sentinel
// as we will be deleting this entry from the list
entry.next.CompareAndSwap(nil, Sentinel)
next = entry.next.Load()
if next == Sentinel {
// we are the last entry in the list
LOCK.CompareAndSwap(entry, nil)
} else {
next.lock.Store(true)
}
}
nb: we swap in an empty sentinel entry when we're done, to avoid a race condition. if we left it as nil, other threads could append themselves to the list, while we are trying to remove ourselves from the Lock pointer.
the other reason for using a lock like this is that each thread ends up waiting on a different spinlock, so there's less cache thrashing, but it is not the only feature a linked list can bring to the table.
a waiting list of rwlocks offers an intriguing possibility: if we're taking a read lock, we don't have to insert at the tail of the list. we can start at the head of the list and find the first rwlock with capacity, and join in:
- we keep a head and a tail pointer inside the lock, the lock is held if tail is non empty
- each lock entry keeps a (has_lock, exclusive_lock, shared_acquire, shared_release) atomic field, and a next pointer
- the order is always "update next pointer, then update tail" for inserts
- and the order is always "update locked then head pointer" for the lock flag
- when a writer comes along, it adds itself to the tail of the list
- when a reader arrives, it scans from the head to find any other read locks, and adds itself to the count
- when a writer unlocks, it works as before
- when a reader unlocks, it increments shared_release, and releases has_lock if complete
- by bounding shared_acquire, we ensure that writes eventually get the lock
readers jump the queue isn't the only policy, we can also insert new lockentries into the queue, using tagged pointers to freeze the next value, to allow writers to jump ahead of others.
we now have a mostly fair rw-lock, but contention isn't the only issue with a spinlock: another issue is deadlocks.
if we have two spinlocks, a and b, and we have threads that try to acquire the locks in different orders, say (a,b) and (b,a), they can end up in a cycle, and deadlocking.
the usual remedy is "don't do that", but not every lock is lucky enough to have a deterministic ordering for acquisition and release. for those cases, we want to be able to find the cycle and break it, forcing one lock holder to release things.
one method for deadlock detection uses a bloom filter: dreadlocks
the rough idea is this, using a bloom filter instead of a real set:
- every thread contains a 'digest set', a set of threads it is waiting on, and some identifier
- the digest set for each thread initially contains the thread identifier
- when i lock an item, i replace it with a pointer to my digest set
- when i try to lock an item, and it is busy, i look at it's digest set
- if my thread identifier is there, waiting will create a deadlock, so the thread unwinds
- if my thread identifier is not there, i set my digest to union(lock.digest, my_id), and wait
- if the lock digest changes, i set my digest to union(lock.digest, my_id)
- when we release all of our locks, we regenerate the thread identifier
- if we use the same id again, and acquire the same locks, the other locks might not have updated their digest set yet
it's not perfect, it will generate false positives, but it is very, very lightweight, and apparently very effective.
let's stop with the deadlocks for a moment, and take a look at the bloom filter again: it gives us a cheap set with very easy unions
a reader writer lock is quite coarse: any writer excludes all readers.
we could use a bloom filter to make a more finer grained lock.
i.e. we could store a spinlock with <count><read set><write set> inside an atomic word:
- when a new thread arrives, it compares it's read and write set with the lock to see if there is a conflict
- if there is none, it atomically updates the lock and increments the count
- if there is a conflict, the lock spins as usual
we can also use the waiting list from before:
- i go through the list of lock entries, i find the first one that does not conflict with my operation
- i update the spinlock atomically to add 1 to the acq count and update the read and write bloom sets to include my own sets
- i spin on the lock entry as usual, and the last thread passes the lock over to the next entry
once a lock is acquired, it cannot be released piecemeal: locks only get released when all involved threads finish their operations. this means that if a lock cannot be obtained, the thread must exit, and retry later.
unless, of course, the next entry in the waiting list doesn't have any conflict. in which case the thread can acquire the lock it needs in the next entry, decrement the count in the current entry, and wait until the next entry is active. a thread could also insert a new entry in the list, but it does involve trickery with epochs to prevent this happening twice.
this means that although a thread can wait for a lock to be free, it can never deadlock. if another thread needs a lock, and sees a conflict in the next entry, it is forced to exit.
et voila: here's a spinlock that's fair, deadlock free, and fine grained.