Page History

...

When we allow simultaneous take and prepend operations on the same list, the simple algorithms are exposed to A-B-A races. An A-B-A race is a situation where the head of the list can change from node "A" to node "B" and back to node "A" again without the simple algorithm being aware that critical state has changed. In the middle column of the above diagram, we show what happens when Thread3 causes the head of the list to change from node "A" to node "B" (a take operation) and back to node "A" (a prepend operation). That A-B-A race causes Thread1 to lose node "B" when it updates the list head to node "X" instead of node "B" because Thread1 was unaware that the its local 'next' value in its code was stale.

Here's the diagram again with the code in Thread1 and Thread2 lined up with the effects of the A-B-A race executed by Thread3:

    T1: Simple Take:                           |                                            | T2: Simple Prepend:
    ----------------                           |  T1 and T3 see this initial list:          | -------------------
    while (true) {                             |          +---+    +---+    +---+           |  :
      cur = head;                              |  head -> | A | -> | X | -> | Y |           |  :
      next = cur->next;                        |          +---+    +---+    +---+           |  :
      :                                        |  T3 takes "A", T2 sees this list:          |  :
      :                                        |          +---+    +---+                    |  :
      :                                        |  head -> | X | -> | Y |                    |  :
      :                                        |          +---+    +---+                    |  while (true) {
      :                                        |  T2 prepends "B":                          |    cur = head; 
      :                                        |          +---+    +---+    +---+           |    new->next = cur;
      :                                        |  head -> | B | -> | X | -> | Y |           |    if (cmpxchg(new, &head, cur) == cur) {
      :                                        |          +---+    +---+    +---+           |      break;
      :                                        |  T3 prepends "A":                          |    }
      :                                        |          +---+    +---+    +---+    +---+  |  }
      :                                        |  head -> | A | -> | B | -> | X | -> | Y |  |
      :                                        |          +---+    +---+    +---+    +---+  |
      :                                        |  T1 takes "A", loses "B":                  |
      :                                        |  +---+                                     |
      :                                        |  | B | ----+                               |
      :                                        |  +---+     |                               |
      :                                        |            V                               |
      :                                        |          +---+    +---+                    |
      if (cmpxchg(next, &head, cur) == cur) {  |  head -> | X | -> | Y |                    |
      }                                        |          +---+    +---+                    |
    }                                          |         +---+                              |
    return cur;                                |  cur -> | A |                              |
                                               |         +---+                              |

So the simple algortihms algorithms are not sufficient when we allow simultaneous take and prepend operations.

...

    // "take" a node with marking:
    while (true) {
      cur = head;
      if (!mark_next(cur, &next)) {
        // could not mark cur so try again
        continue;
      }
      if (head != cur) {
        // head changed while marking cur so try again
        unmark_next(cur);
        continue;
      }
      // list head is now marked so switch it to next which also makes list head unmarked
      Atomic::release_store(&head, next);
      unmark_next(cur);  // unmark cur and return it
      return cur;
    }

The modified take algorithm does not change the list head pointer until it has successfully marked the list head node. Notice that after we mark the list head node we have to verify that the list head pointer hasn't changed in the mean time. Only after we have verified that the node we marked is still the list head is it safe to modify the list head pointer. The marking of the list head prevents the take algorithm from executing in parallel with a prepend algorithm and losing a node.

Also notice that we update the list head pointer with release-store instead of with cmpxchg. Since we have the list head marked, we are not racing with other threads to change the list head pointer so we can use the smaller release-store hammer instead of the heavier cmpxchg hammer.

Here's the prepend algorithm modified with marking (ignores the empty list for clarity):

    // "prepend" a node with marking:
    while (true) {
      cur = head;
      if (!mark_next(cur, &next)) {
        // could not mark cur so try again
        continue;
      }
      if (head != cur) {
        // head changed while marking cur so try again
        unmark_next(cur);
        continue;
      }
      // list head is now marked so switch it to 'new' which also makes list head unmarked
      Atomic::release_store(&head, new);
      unmark_next(cur);  // unmark the previous list head
    }

The modified prepend algorithm does not change the list head pointer until it has successfully marked the list head node. Notice that after we mark the list head node we have to verify that the list head pointer hasn't changed in the mean time. Only after we have verified that the node we marked is still the list head is it safe to modify the list head pointer. The marking of the list head prevents the prepend algorithm from executing in parallel with the take algorithm and losing a node.

Also notice that we update the list head pointer with release-store instead of with cmpxchg for the same reasons as the previous algorithm.

Prepending To A List That Also Allows Deletes

...