benchmark/ms-queue/note.txt

   1 #1: The new bug we found in this data structure is as the following:
   2
   3 In dequeue(), the load of Tail has to be acquire. If not, the load of the next
   4 field won't get synchronize with the enqueuer that inserted the element right
   5 after this dequeue() operation. We can catch this bug using the two independent
   6 dequeuers and 1 (or 2) enqueuer.
   7
   8 #2: When writing the speicification for this data structure, we have been
   9 considering the following invariance of the enqueue() and dequeue() operations.
  10 For enqueue() to succeed, it finally loads the Tail, inserts the new element by
  11 updating the next field right after the Tail load. The load of Tail actually
  12 orders the enqueuers, and the CAS of the next field will order the enqueuer and
  13 its dequeuer. For dequeue() to succeed, it either loads the Head and Tail, and
  14 then bails; or it loads the Head and then loads the next field. Similarly, the
  15 load of Head orders dequeuers.
  16
  17 We have one key "additional_ordering_point" in enqueue() method for ordering the
  18 dequeuer and its immediately next enqueuer. For example, when we have two
  19 threads, 1 dequeuer and 1 enqueuer, when dequeue() returns NULL, we can order
  20 dequeue() before enqueue() by using the additional ordering point of enqueue()
  21 where the swing of Tail (or just the load of Tail when someone else swings it).
  22 Since dequeue() will load the Tail, and enqueue() will CAS or load the Tail
  23 later, deuqeue() can be ordered() before enqueue(). Notably here, additional
  24 ordering points are only used when methods has 'same-location' commit points and
  25 they can't order each other.