I recently implemented a concurrent skip list based upon William Pugh's tech report. Since the implementation is in C, I needed a way to safely reclaim memory in the presence of lock-free readers, and opted to use hazard pointers.
It turns out that there are a few errors / missing features in the pseudocode presented in the tech report, and I was unable to find a corrected version. Also, modifying the algorithm to make use of hazard pointers was trickier than I'd anticipated.
Hazard pointers allow readers to efficiently broadcast their intent to access a memory location to each other, and provide a deferred memory reclamation algorithm that waits until no threads (and no pointers) to the freed memory remain. The main difficulty arises due to the fact that, when traversing the skiplist for update, threads maintain pointers at each level of the tree. Worse, skiplist deletions install backpointers from the deleted nodes to earlier nodes in the list, effectively creating new garbage collection roots.
I address the problem by introducing reference counts; deleted nodes bump the reference count on each node they point into. When the deleted node is reclaimed, the refcount is decremented. Reclamation is delayed until both the refcount is zero, and no threads are pointing to the freed data.
Note that the refcount is only manipulated at deletion. Hazard pointers go to great lengths to prevent CPU memory write conflicts, and avoid writing to the same memory address with multiple threads. In contrast, reference counts create write hotspots if used carelessly. Restricting the use of reference counts to deletions should prevent them from having a significant performance impact.
Another problem arose due to the need to return old existing values after atomically replacing them in insert. The problem is that other threads could be deleting or inserting the value in race, which lead to double free bugs, and broke the atomicity of test-and-set. I fix this problem by releasing all mutexes and locking the level field (which is held by insert and delete). The other mutexes have to be deleted in order to preserve lock orderings, but releasing them creates the possibility that the replaced value is deleted in race with the insert:
This doesn't correspond to a linearizable schedule, since the old value gets deleted and replaced, and the new value is lost. The anomaly was hidden in the original pseudocode, which simply returns status variables, and not the existing values. I address this by detecting the anomaly, and using a GOTO to restart the insert process.
Here is an updated version of the pseudocode for insert and delete. Changes due to refcounting are in blue; test and set is in red. There were a few obvious bugs in the original pseudocode; these changes are in green.
Before digging into the code, I highly recommend taking a look at the papers linked above if you're not already familiar with concurrent skiplists and hazard pointers.
Insert(list, searchKey, newValue) IN: local update[1..levelCap] x := list➜header L := list➜levelHint for i := L downto 1 do y := x➜forward[i] while y➜key < searchKey do x := y y := x➜forward[i] update[i] := x x := getLock(x, searchKey, 1) if x➜forward[1]➜key = searchKey then unlock(x, forward[1]) lock(y, level) x = y➜forward[1] isGarbage = x➜key < searchKey) if !isGarbage oldValue = y➜value y➜value := newValue unlock(y, level) return updated else goto IN y := makeNode(randomLevel(), searchKey, value) lock(y, level) -- if L < y➜level, add levels L+1..y➜level to update, -- so that we can insert y into levels 1..y➜level. -- This will allow the header of the list to be updated correctly. for i := L+1 to y➜level do update[i] = header(list) -- insert y into levels 1..level(y) for i := 1 to y➜level do -- y is effectively a level i–1 element if i ≠ 1 then x := getLock(update[i], searchKey, i) -- searchKey is not present at level i, ∴ x➜key < searchKey < x➜forward[i]➜key y➜forward[i] := x➜forward[i] x➜forward[i] := y unlock(x, forward[i]) unlock(y, level) -- increase levelHint to correspond to maximum non–NIL level if needed L := list➜levelHint if L < levelCap and list➜header➜forward[L+1] ≠ NIL and not locked(list, levelHint) then lock(list, levelHint) while list➜levelHint < levelCap and list➜header➜forward[list➜levelHint+1] ≠ NIL do list➜levelHint := list➜levelHint+1 unlock(list, levelHint) return inserted Delete(list, searchKey) local update[1..levelCap] x := list➜header L := list➜levelHint for i := L downto 1 do y := x➜forward[i] while y➜key < searchKey do x := y y := x➜forward[i] update[i] := x y := x first := true repeat y := y➜forward[i] if(first) first := false else unlock(y, level) if y➜key > searchKey then return not-found lock(y, level) isGarbage := y➜key > y➜forward[i]➜key //if isGarbage then unlock(y, level) until y➜key = searchKey and not isGarbage -- y is in the list and we have exclusive insert/delete rights for i := L+1 to y➜level do update[i] := list➜header for i := y➜level downto 1 do -- loop invariant: y is effectively a level i element x := getLock(update[i], searchKey, i) -- x➜forward[i] = y lock(y, forward[i]) -- decrement happens in finalizer of x. atomic_increment(x, refcount) x➜forward[i] := y➜forward[i] y➜forward[i] := x unlock(x, forward[i]) unlock(y, forward[i]) putOnGarbageQueue(y) unlock(y, level) -- decrease levelHint to correspond to maximum non–NIL level if needed L := list➜levelHint if L > 1 and list➜header➜forward[L] = NIL and not locked(list, levelHint) then lock(list, levelHint) while list➜levelHint > 1 and list➜header➜forward[list➜levelHint] = NIL do list➜levelHint := list➜levelHint - 1 unlock(list, levelHint) return deleted