Are Hazard Pointers Lock-Free or Wait-Free ?

I've seen some people refer to Hazard Pointers (HP) as lock-free and others as wait-free, so which one is it?

The simple answer is: they're lock-free

The complex answer is: it depends


If you go and take a look at the original HP paper by Maged Michael, you'll see there is an implicit mention of "lock-free":
https://researchweb.watson.ibm.com/people/m/michael/ieeetpds-2004.pdf
I mean, the title itself has the term "lock-free" in it: "Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects"

So it's lock-free, right?

But then you start reading the text and in page 492 you have this:
(...) It is wait-free [8], i.e., progress is guaranteed for active threads individually, not just collectively; thus, it is also applicable to wait-free algorithms without weakening their progress guarantee. It allows reclaimed memory to be returned to the operating system. It does not require any special support from the kernel or the scheduler. (...)

The first sentence is clearly mentioning that although this was designed for usage in lock-free algorithms, it can be used in wait-free algorithms, and the HP itself will be wait-free.
The last sentence is just to say that you don't need kernel/scheduler support like you do on the Linux Kernel's RCU. Of course, nowadays there are good userspace RCU implementations that don't need that either and can be implemented with just atomics, i.e. they're as generic as HPs.

Huhhh, so it's wait-free then?

Not so fast. The question you want to pose is:
Is it true that we can we apply HPs to a wait-free algorithm and keep it wait-free? For every wait-free algorithm?

Andreia and I know for a fact that answer to this question is "No".
Not every wait-free algorithm can be adapted to use Hazard Pointers and still maintain its wait-free progress. The best example is the list by Tim Harris (later modified by Maged Michael himself) which can be made wait-free for lookups, i.e. the contains() method, but when using HP it will revert back to being lock-free (more details on this below).
http://researchweb.watson.ibm.com/people/m/michael/spaa-2002.pdf


The Hazard Pointers technique has three procedures in its API:
- Publish a pointer: publish(ptr)
- Clear a pointer: clear(ptr)
- Retire an object: retire(ptr)    (named retireNode() in the original paper)

The retire() method is called when reclaiming memory, for example, from within a remove() method in the Harris-Maged list after a node has been successfully marked and unlinked from the list. The publish()/clear() are used by all methods contains()/add()/remove() because any of them can dereference pointers that another thread may be attempting to delete through a call to retire().

One of the rarely mentioned advantages of HP is that they provide a memory bound. In other words, they give the guarantee that out of all the objects/pointers for which retire(object) was called, there is a maximum number of objects that have not yet been deleted. For an 'R' factor of zero (page 492 of the HP paper) this bound is MAX_THREADS x MAX_HPS, which is actually very low, and this is in the extremely unlikely worst-case scenario.
This low bound on the memory usage can be vital on embedded systems where memory is scarce.
This bound on the number of object/nodes to retire has one other implication, it means that a call to Scan() (figure 3 of the HP paper) which is typically called from inside retire(), will have a bounded number of nodes to scan, and therefore, retire() is a wait-free bounded method.

As it so happens, publishing a pointer is just a matter of doing a seq-cst store of the pointer, and
clearing a pointer consists of doing a seq-cst store of nullptr on the same shared memory location (the hazard pointers array), and both of these operations are wait-free population oblivious.
In summary, the progress conditions of the HP API are:
- publish(ptr): wait-free population oblivious
- clear(ptr): wait-free population oblivious
- retire(ptr): wait-free bounded

Hummmm, so HPs are wait-free bounded for doing memory reclamation?
Yes, this they can be made wait-free bounded for calls to retire(), subject to implementation details.

And HPs are wait-free population oblivious for calls to publish() and clear(), so they must be wait-free?
No, not always. The answer is related to the way you call publish() and clear().


How do you adapt a wait-free algorithm to (wait-free) hazard pointers?

Here is what a lock-free method looks like when using hazard pointers:
std::atomic<Node*> ptr; // Global shared pointer

void lockFreeMethod() {
  Node* lptr = ptr.load();
  do {
    publish(lptr);
  } while (lptr != ptr.load());
  doSomethingWithHead(lptr);
  clear(lptr);
}      // May need infinite steps to complete

and here is what a wait-free usage looks like:

void waitFreeBoundedMethod() {
  for (int istep=0; istep < maxSteps; istep++) {
    Node* lptr = ptr.load();
    publish(lptr);
    if (lptr != ptr.load()) continue;
    doSomethingWithHead(lptr);
    clear(lptr);
    break;
  }
}    // Completes in maxSteps

The difference between the lock-free and the wait-free version is in how you call the publish() method.
If you have a wait-free algorithm where you want to incorporate HPs and you are able to re-write it such that is looks like the second form, then it will be wait-free.
However, if you can only write it in the first form, then there is the possibility (no matter how unlikely) that the loop will go on indefinitely, meaning that it's lock-free.
In which situations can you write an algorithm in the second form? That's a subject for another post.

Unfortunately, when using HPs, the contains() method in the Harris-Maged list can only be written in a lock-free way.
The reasons for this are related to the invariants on the Harris-Maged list itself, and they would require a separate post to explain in detail, but the rough idea is that re-checking the pointer may cause an invalidation the publishing due to some other thread calling add()/remove() changing the pointer. This can happen an infinite number of times, so it's lock-free. And we can't just give up on it and skip to the next node because the next node may have already been free()/deleted.
Yes, it can happen that the next node wasn't just retired, it was really deleted, and then... crash!

Confused?
If yes, then I just proved the point on my previous post: Hazard Pointers are hard to use, not because they are complex themselves, but because they require deep knowledge of the algorithm where they are being deployed.


In summary, doing memory reclamation with hazard pointers is always wait-free, but using hazard pointers for reading is typically lock-free and although it can be made wait-free it is never easy and sometimes not possible.