Page History

...

Note: The above code snippet comes from ObjectSynchronizer::prepend_block_to_lists(); see that function for more complete context (and comments).

Prepending To A List That Also Allows Deletes

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.

    L01:  while (true) {
    L02:    ObjectMonitor* cur = OrderAccess::load_acquire(list_p);
    L03:    ObjectMonitor* next = NULL;
    L04:    if (!mark_next(m, &next)) {
    L05:      continue;  // failed to mark next field so try it all again
    L06:    }
    L07:    set_next(m, cur);  // m now points to cur (and unmarks m)
    L08:    if (cur == NULL) {
    L09:      // No potential race with other prependers since *list_p is empty.
    L10:      if (Atomic::cmpxchg(m, list_p, cur) == cur) {
    L11:        // Successfully switched *list_p to 'm'.
    L12:        Atomic::inc(count_p);
    L13:        break;
    L14:      }
    L15:      // Implied else: try it all again
    L16:    } else {
    L17:      // Try to mark next field to guard against races:
    L18:      if (!mark_next(cur, &next)) {
    L19:        continue;  // failed to mark next field so try it all again
    L20:      }
    L21:      // We marked the next field so try to switch *list_p to 'm'.
    L22:      if (Atomic::cmpxchg(m, list_p, cur) != cur) {
    L23:        // The list head has changed so unmark the next field and try again:
    L24:        set_next(cur, next);
    L25:        continue;
    L26:      }
    L27:      Atomic::inc(count_p);
    L28:      set_next(cur, next);  // unmark next field
    L29:      break;
    L30:    }
    L31:  }

What the above block of code does is:

• • prepends an ObjectMonitor 'm' to the front of the list referred to by list_p
    • mark 'm's next field and update 'm' to refer to the list head
    • mark the list head's next field
    • update 'list_p' to refer to 'm'
    • unmark the next field in the previous list head
  • increments the counter referred to by 'count_p' by one

The above block of code can be called by multiple prependers in parallel or with deleters running in parallel and does not lose track of any ObjectMonitor. Of course, the "does not lose track of any ObjectMonitor" part is where all the details come in:

• • 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.
  • 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 to prepend 'm' to an in-use list.
    • T2 just finished prepending 'm' to a free list where T1 found 'm', but T2 has not yet unmarked 'm'.
    • If our thread (T1) does not mark 'm', 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.

ObjectMonitor 'm' is safely on the list at the point that we have updated 'list_p' to refer to 'm'. In this subsection's block of code, we also called two new functions, mark_next() and set_next(), that are explained in the next subsection.

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:

    L01:  static bool mark_next(ObjectMonitor* om, ObjectMonitor** next_p) {
    L02:    // Get current next field without any marking value.
    L03:    ObjectMonitor* next = (ObjectMonitor*)
    L04:        ((intptr_t)OrderAccess::load_acquire(&om->_next_om) & ~0x1);
    L05:    if (Atomic::cmpxchg(mark_om_ptr(next), &om->_next_om, next) != next) {
    L06:      return false;  // Could not mark the next field or it was already marked.
    L07:    }  
    L08:    *next_p = next;
    L09:    return true;
    L10:  }

The above function tries to mark the next field in an ObjectMonitor:

• • If marking is successful, then the unmarked next field is returned via parameter and true is returned.
  • Otherwise, false is returned.

The function can be called by multiple threads at the same time and only one thread will succeed in the marking operation (return == true) and all other threads will get return == false. Of course, the "only one thread will succeed" part is where all the details come in:

• • L0[34] load-acquires the ObjectMonitor's next field and strips the marking bit:
    • The unmarked value is saved in 'next'.
    • We need the unmarked next value in order to properly detect if the next field was already marked.
  • L05 tries to cmpxchg a marked 'next' value into the ObjectMonitor's next field:
    • if cmpxchg does not work, then we return false:
      • The cmpxchg will not work if the next field changes after we load-acquired the value on L04.
      • The cmpxchg will not work if the next field is already marked.
    • Otherwise, we return the unmarked 'next' value via 'next_p' and return true.

The mark_next() function calls another helper function, mark_om_ptr(), that needs a quick explanation:

    L1:  static ObjectMonitor* mark_om_ptr(ObjectMonitor* om) {
    L2:    return (ObjectMonitor*)((intptr_t)om | 0x1);
    L3:  }

This function encapsulates the setting of the marking bit in an ObjectMonitor* for the purpose of hiding the details and making the calling code easier to read:

• • L2 casts the ObjectMonitor* into a type that will allow the '|' operator to be used.
  • We use the 0x1 bit as our marking value because ObjectMonitors are aligned on a cache line so the low order bit is not used by the normal addressing of an ObjectMonitor*.

set_next() is the next interesting function and it also only needs a quick explanation:

    L1:  static void set_next(ObjectMonitor* om, ObjectMonitor* value) {
    L2:    OrderAccess::release_store(&om->_next_om, value);
    L3:  }

This function encapsulates the setting of the next field in an ObjectMonitor for the purpose of hiding the details and making the calling code easier to read:

• • 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)".

Housekeeping Parts of the Algorithm

...