Page History

...

This example is considered to be the "simple case" because we only prepend to the list (no deletes) and we only use:

• • one load-acquire
  • one release-store-release and
  • one cmpxchg

to achieve the safe update of the 'g_block_list' value; the atomic increment of the 'g_om_population' counter is considered to be just accounting (pun intended).

...

Note: The above code snippet comes from prepend_to_common(); see that function for more context and a few more comments.

mark_next(), mark_om_ptr(), and set_next()

...

Helper Functions

Managing marks on ObjectMonitors has been abstracted into a few helper functions. mark_next() is the first interesting one:

...

• • This function is simply a wrapper around a release-store of an ObjectMonitor* into the next field in an ObjectMonitor.
  • The typical "set_next(cur, next)" call sequence is easier to read than "OrderAccess::release_store(&cur→_next_om, next)".

Taking From The Start Of A List

The next case to consider for lock-free list management with the Java Monitor subsystem is taking an ObjectMonitor from the start of a list. Taking an ObjectMonitor from the start of a list is a specialized form of delete that is guaranteed to interact with a thread that is prepending to the same list at the same time. Again, the core of the solution is to "mark" the next field in the ObjectMonitor at the head of the list we're trying to take the ObjectMonitor from, but we use slightly different code because we have less linkages to make than a prepend.

    L01:  static ObjectMonitor* take_from_start_of_common(ObjectMonitor* volatile * list_p,
    L02:                                                  int volatile * count_p) {
    L03:    ObjectMonitor* next = NULL;
    L04:    ObjectMonitor* take = NULL;
    L05:    // Mark the list head to guard against A-B-A race:
    L06:    if (!mark_list_head(list_p, &take, &next)) {
    L07:      return NULL;  // None are available.
    L08:    }
    L09:    // Switch marked list head to next (which unmarks the list head, but
    L10:    // leaves take marked):
    L11:    OrderAccess::release_store(list_p, next);
    L12:    Atomic::dec(count_p);
    L13:    // Unmark take, but leave the next value for any lagging list
    L14:    // walkers. It will get cleaned up when take is prepended to
    L15:    // the in-use list:
    L16:    set_next(take, next);
    L17:    return take;
    L18:  }

What the above function does is:

• • Tries to mark the ObjectMonitor at the head of the list:
    • Marking will only fail if the list is empty so that NULL can be returned.
    • Otherwise mark_list_head() will loop until the ObjectMonitor at the list head has been marked.
  • Updates the list head to refer to the next ObjectMonitor.
  • Decrements the counter referred to by 'count_p'.
  • Unmarks the next field in the taken ObjectMonitor.

The function can be called by more than one thread at a time and each thread will take a unique ObjectMonitor from the start of the list (if one is available) without losing any other ObjectMonitors on the list. Of course, the "take a unique ObjectMonitor" and "without losing any other ObjectMonitors" parts are where all the details come in:

• • L03 tries to mark the list head:
    • mark_list_head() returns false if the list is empty so we return NULL on L07.
    • Otherwise, 'take' is a pointer to the marked list head and 'next' is the unmarked next field in the list head.
  • L11 release-stores 'next' into 'list_p'.
    You might be asking yourself: Why release-store instead of cmpxchg?
    • mark_list_head() only returns to the caller when it has marked the next field in the ObjectMonitor at the head of the list.
    • Because of that guarantee, any prepender or deleter thread that is running in parallel must loop until we have release-stored 'next' into 'list_p' which unmarks the list head.
  • L12 decrements the counter referred to by 'count_p'.
  • L16 unmarks 'take' using the unmarked 'next' value we got from mark_list_head():
    • Keeping the 'next' value in take's next field allows any lagging list walker to get to the next ObjectMonitor on that list.
    • take's next field will get cleaned up when take is prepended to its target in-use list.
  • L17 returns 'take' to the caller.

The take_from_start_of_common() function calls another helper function, mark_list_head(), that is explained in the next subsection.

mark_list_head() Helper Function

mark_list_head() is the next interesting helper function:

    L01:  static bool mark_list_head(ObjectMonitor* volatile * list_p,
    L02:                             ObjectMonitor** mid_p, ObjectMonitor** next_p) {
    L03:    while (true) {
    L04:      ObjectMonitor* mid = OrderAccess::load_acquire(list_p);
    L05:      if (mid == NULL) {
    L06:        return false;  // The list is empty so nothing to mark.
    L07:      }
    L08:      if (mark_next(mid, next_p)) {
    L09:        if (OrderAccess::load_acquire(list_p) != mid) {
    L10:          // The list head changed so we have to retry.
    L11:          set_next(mid, *next_p);  // unmark mid
    L12:          continue;
    L13:        }
    L14:        // We marked next field to guard against races.
    L15:        *mid_p = mid;
    L16:        return true;
    L17:      }
    L18:    }
    L19 }

The above function tries to mark the next field in the list head's ObjectMonitor:

• • If the list is empty, false is returned.
  • Otherwise, the list head's ObjectMonitor* is returned via parameter (mid_p), the unmarked next field is returned via parameter (next_p) and true is returned.

The function can be called by more than one thread on the same 'list_p' at a time. False is only returned when 'list_p' refers to an empty list. Otherwise only one thread will return true at a time with the 'mid_p' and 'next_p' return parameters set. Since the next field in 'mid_p' is marked, any parallel callers to mark_list_head() will loop until the next field in the list head's ObjectMonitor is no longer marked. That typically happens when the list head's ObjectMonitor is taken off the list and 'list_p' is advanced to the next ObjectMonitor on the list. Of course, making sure that "only one thread will return true at a time" is where all the details come in:

• • L04 load-acquires the current 'list_p' value into 'mid'; the use of load-acquire is necessary to get the latest value release-stored or cmpxchg'ed by another thread.
  • L0[56] is the empty list check and the only time that false is returned by this function.
  • L08 tries to mark the next field in 'mid':
    • If marking is not successful, we loop around to try it all again.
    • If marking is successful, then 'next_p' contains mid's unmarked next field value.
    • L09 load-acquires the current 'list_p' value to see if it still matches 'mid':
      • If the list head has changed, then we unmark mid on L11 and try it all again.
      • Otherwise, 'mid' is returned via 'mid_p' and we return true.

When this function returns true, the next field in 'mid_p' is marked and any parallel callers of mark_list_head() on the same list will be looping until the next field in the list head's ObjectMonitor is no longer marked. The caller that just got the 'true' return needs to finish up its work with 'mid_p' quickly.

Housekeeping Parts of the Algorithm

...