Page History

...

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.

Using The New Lock-Free Monitor List Functions

ObjectSynchronizer::om_alloc(Thread* self, ...)

ObjectSynchronizer::om_alloc() is responsible for allocating an ObjectMonitor and returning it to the caller. It has a three step algorithm:

1) Try to allocate from self's local free-list:

• • take_from_start_of_om_free_list(self) takes an ObjectMonitor from self's free list (if possible).
  • prepend_to_om_in_use_list(self, m) prepends the newly taken ObjectMonitor to self's in-use list.

2) Try to allocate from the global free list (up to self→om_free_provision times):

• • take_from_start_of_g_free_list() takes an ObjectMonitor from the global free list (if possible).
  • om_release(self, take, false) prepends the newly taken ObjectMonitor to self's free list.
  • Retry the allocation from step 1.

3) Allocate a block of new ObjectMonitors:

• • prepend_block_to_lists() prepends the newly allocated block to 'g_block_list' and to the global free list.
  • Retry the allocation from step 1.

ObjectSynchronizer::om_release(Thread* self, ObjectMonitor* m, bool from_per_thread_alloc)

ObjectSynchronizer::om_release() is responsible for putting an ObjectMonitor on self's free list. If 'from_per_thread_alloc' is true, then om_release() is also responsible for extracting the ObjectMonitor from self's in-use list. The extraction from self's in-use list must happen first:

    L01:  mark_list_head(&self->om_in_use_list, &mid, &next);
    L02:  while (true) {
    L03:    if (m == mid) {
    L04:      if (Atomic::cmpxchg(next, &self->om_in_use_list, mid) != mid) {
    L05:        ObjectMonitor* marked_mid = mark_om_ptr(mid);
    L06:        Atomic::cmpxchg(next, &cur_mid_in_use->_next_om, marked_mid);
    L07:      }
    L08:      extracted = true;
    L09:      Atomic::dec(&self->om_in_use_count);
    L10:      set_next(mid, next);
    L11:      break;
    L12:    }
    L13:    if (cur_mid_in_use != NULL) {
    L14:      set_next(cur_mid_in_use, mid);  // umark cur_mid_in_use
    L15:    }
    L16:    cur_mid_in_use = mid;
    L17:    mid = next;
    L18:    next = mark_next_loop(mid);
    L19:  }

The above code block extracts 'm' from self's in-use list; it is not an exact quote from om_release(), but it is the highlights:

• • L01 is used mark self's in-use list head:
    • 'mid' is self's in-use list head and its next field is marked.
    • 'next' is the unmarked next field from 'mid'.
  • L02 → L19: self's in-use list is traversed looking for the target ObjectMonitor 'm':
    • L03: if the current 'mid' matches 'm':
      • L04: if we can't cmpxchg self's in-use list head to the 'next' ObjectMonitor*:
        Note: This cmpxchg only works if 'm' is self's in-use list head and no-harm-no-foul if 'm' is not self's in-use list head. This is faster than doing a load-acquire of self's in-use list head, checking the value and then calling cmpxchg.
        
        • L05: make a marked copy of 'mid'
        • L06: we cmpxchg cur_mid_in_use's next field to 'marked_mid'.
          Note: We use cmpxchg here instead of release-store so that we can sanity check the result; see the real code.
      • L08 → L11: we've successfully extracted 'm' from self's in-use list so we decrement self's in-use counter, unmark the next field in 'mid' and we're done.
    • L1[34]: if cur_mid_in_use != NULL, then unmark its next field.
    • L16: set 'cur_mid_in_use' to 'mid'
      Note: cur_mid_in_use keeps the marked next field so that it remains stable for a possible next field change. It cannot be deflated while it is marked.
    • L17: set 'mid' to 'next'.
    • L18: mark next field in the new 'mid' and update 'next'

mark_next_loop() Helper Function

mark_next_loop() is next interesting helper function:

    L1:  static ObjectMonitor* mark_next_loop(ObjectMonitor* om) {
    L2:    ObjectMonitor* next;
    L3:    while (true) {
    L4:      if (mark_next(om, &next)) {
    L5:        // Marked om's next field so return the unmarked value.
    L6:        return next;
    L7:      }
    L8:    }
    L9:  }

The above function loops until it marks the next field of the target ObjectMonitor. The unmarked value of the next field is returned by the function. There is nothing particularly special about this function so we don't need any line specific annotations.

Housekeeping Parts of the Algorithm

...