Page History

...

Prepending To A List That Also Allows Deletes

It is now time to switch from algorithms to real snippets from the code.

The next case to consider for lock-free list management with the Java Monitor subsystem is prepending to a list that also allows deletes. As you might imagine, the possibility of a prepend racing with a delete makes things more complicated. The solution is to "mark" the next field in the ObjectMonitor at the head of the list we're trying to prepend to. A successful mark tells other prependers or deleters that the marked ObjectMonitor is busy and they will need to retry their own mark operation.

...

• • L02 load-acquires the current 'list_p' value into 'cur'; the use of load-acquire is necessary to get the latest value cmpxchg'ed by another thread release-stored by another thread; the current 'list_p' is updated by either a release-store or a cmpxchg depending on the algorithm that made the update; only the release-store needs to match up with a load-acquire, but this code doesn't know whether release-store or cmpxchg was used.
  • L04 tries to mark 'm's next field; if marking fails, then another thread (T2) has 'm' marked and we try again until it is unmarked.
    You might be asking yourself: why does T2 have 'm' marked?
    • Our thread (T1) wants Before T1 was trying to prepend 'm' to an the in-use list, T1 and T2 were racing to take an ObjectMonitor off the free list.
    • T2 just finished prepending T1 won the race, marked 'm', removed 'm' to a free list where T1 found 'm', but T2 has not yet from the free list and unmarked 'm'; T2 stalled before trying to mark 'm'.
    • T2 resumed and marked 'm', realized that 'm' was no longer the head of the free list, unmarked 'm' and tried it all again.
    • If our thread (T1) does not mark 'm' before it tries to prepend it to the in-use list, then T2's umarking of 'm' could erase the next value that T1 wants to put in 'm'.
  • L07 sets 'm's next field to the current list head 'cur' (which also unmarks 'm').
  • L08 → L13 recognizes that the current list is empty and tries to cmpxchg 'list_p' to 'm':
    • if cmpxchg works, then the counter referred to by 'count_p' is incremented by one and we're done.
    • Otherwise, another prepender won the race to update the list head so we have to try again.
  • L16 → L29 is where we handle a non empty current list:
    • L18 tries to mark the current list head 'cur'; if marking fails, then another thread (a prepender or a deleter) has 'cur' marked and we try again until it is unmarked.
    • Once our thread has 'cur' marked, another prepender or deleter will have to retry until we have unmarked 'cur'.
    • L22 tries to cmpxchg 'list_p' to 'm':
      • if cmpxchg does not work, then we unmark 'cur' and try again; the cmpxchg can fail if another thread has managed to change the list head 'list_p' and unmarked 'cur' after we load-acquired list_p on L02 and before we tried to cmpxchg it on L22.
      • Otherwise, the counter referred to by 'count_p' is incremented by one, we unmark 'cur' and we're done.

...