julian m bucknall >> Hazard Pointers (part 2)

Hazard Pointers (part 2)

published: Wed, 10-Jan-2007 | updated: Wed, 10-Jan-2007

Last time in this series on hazard pointers I looked at how the concept could help provide a node reuse manager for a lock-free stack using C#, admittedly without fleshing out the details of how hazard pointers would work under the hood. This time I just want to look at the lock-free queue in the same way, to see how hazard pointers would help provide lock-free memory management. Next time, we'll delve into the C# code for the hazard pointers themselves.

With the stack we were lucky in that only the Pop() method required any real changes for lock-free management. For the queue, things are a lot different: the Enqueue() method also requires protection from the ABA problem.

Let's look at the (simplified) lock-free Enqueue() method (shown here with line numbers):

01    public void Enqueue(T item) {
02      Node<T> oldTail = null;
03      Node<T> oldNext = null;
04
05      // create and initialize the new node
06      Node<T> node = new Node<T>();
07      node.Item = item;
08
09      // loop until we have managed to update the tail's Next link 
10      // to point to our new node
11      bool UpdatedNewLink = false;
12      while (!UpdatedNewLink) {
13
14        // make local copies of the tail and its Next link, but in 
15        // getting the latter use the local copy of the tail since
16        // another thread may have changed the value of tail
17        oldTail = tail;         
18        oldNext = oldTail.Next; 
19
20        // providing that the tail field has not changed...
21        if (tail == oldTail) {
22
23          // ...and its Next field is null
24          if (oldNext == null) {
25
26            // ...try to update the tail's Next field
27            UpdatedNewLink = CAS(ref tail.Next, null, node);
28          }
29
30          // if the tail's Next field was non-null, another thread
31          // is in the middle of enqueuing a new node, so try and 
32          // advance the tail to point to its Next node
33          else {
34            CAS(ref tail, oldTail, oldNext);
35          }
36        }
37      }
38
39      // try and update the tail field to point to our node; don't
40      // worry if we can't, another thread will update it for us on
41      // the next call to Enqueue()
42      CAS(ref tail, oldTail, node);
43    }

The first line of interest is line 17. The lines prior to that are merely operating on local variables and consequently have no issues in a multithreaded lock-free environment. But line 17 makes a local copy of the queue's tail reference, which by now should alert you to a possible hazard coming up.

And, lo and behold, in the very next line, line 18, we dereference our copy of the tail reference to get its Next reference. As discussed last time, this is a problem since the reference we have may have been reused in between our copying it and our using it. Hence our oldTail variable is a hazard pointer, and so we must mark it as such.

If you look at the remainder of the method you'll see that neither oldTail or OldNext (the next shared reference we make a copy of) is dereferenced and so we have no other hazard pointers to worry about.

The code changes then are as we've seen before: mark it as a hazard pointer, check to see if it has changed, and if so, go round the loop again:

17        oldTail = tail;         
17a       MagicMemoryManager.MarkAsHazardPointer(oldTail);
17b       if (oldTail != tail)
17c         continue; 
18        oldNext = oldTail.Next;

Now the Dequeue() method. Here it is in its simplified form:

01    public T Dequeue() {
02      T result = default(T);
03
04      // loop until we manage to advance the head, removing 
05      // a node (if there are no nodes to dequeue, we'll exit
06      // the method instead)
07      bool HaveAdvancedHead = false;
08      while (!HaveAdvancedHead) {
09
10        // make local copies of the head, the tail, and the head's Next 
11        // reference
12        Node<T> oldHead = head;
13        Node<T> oldTail = tail;
14        Node<T> oldHeadNext = oldHead.Next;
15
16        // providing that the head field has not changed...
17        if (oldHead == head) {
18
19          // ...and it is equal to the tail field
20          if (oldHead == oldTail) {
21
22            // ...and the head's Next field is null
23            if (oldHeadNext == null) {
24
25              // ...then there is nothing to dequeue
26              return default(T);
27            }
28
29            // if the head's Next field is non-null and head was equal to the tail
30            // then we have a lagging tail: try and update it
31            CAS(ref tail, oldTail, oldHeadNext);
32          }
33
34          // otherwise the head and tail fields are different
35          else {
36
37            // grab the item to dequeue, and then try to advance the head reference
38            result = oldHeadNext.Item;
39            HaveAdvancedHead = CAS(ref head, oldHead, oldHeadNext);
40          }
41        }
42      }
43      return result;
44    }

The first line of any interest is line 12 where we copy the head reference into a local variable. Line 13 could also be interesting: we're copying the tail reference. Line 14 is a dereference of our local copy of a shared reference, so we can immediately identify oldHead as being a hazard pointer and slot in the (by now) usual code.

12        Node<T> oldHead = head;
12a       MagicMemoryManager.MarkAsHazardPointer(oldHead);
12b       if (oldHead != head)
12c         continue; 
13        Node<T> oldTail = tail;

The next line where there's anything of real importance is line 38 where we deference oldHeadNext to get at the item. Alarm bells should be ringing by now: this is a hazard, and so we should mark oldHeadNext as a hazard pointer and insert the usual code.

14        Node<T> oldHeadNext = oldHead.Next;
14a       MagicMemoryManager.MarkAsHazardPointer(oldHeadNext);
15

Notice though we can make a small optimization: we don't need to check to see if the value of oldHead.Next has changed. Why not? Well, oldHead has already been marked and verified as a hazard pointer. oldHead.Next is therefore guaranteed not to change from its assumed value. Furthermore the very next line checks to see whether head has changed from when we made the copy. If it has, it doesn't matter what value of head.Next we have, we're just going to ignore it as we go round the loop again.

The next thing to notice is that, although we make a copy of the tail reference, we never dereference it. It therefore does not pose a hazard and does not have to be marked as a hazard pointer.

Also, if you think about it, the Dequeue() method needs to maintain two hazard pointers at the same time: there's oldHead and there's oldHeadNext. That means our eventual hazard pointer implementation will have to store at least two hazard pointers per thread, not one.

And with that we'll finish this installment. Next time we'll be looking at the actual implementation in C# of the hazard pointer system.