Hazard Pointers with well defined allocators in C++

Question

I read the following note in Chapter 7 of the book C++ Concurrency in Action (Page 194). My question is, is there any allocator in the standard library, for which what we do in Hazard Pointers is well defined?

Using hazard pointers like this relies on the fact that it's safe to use the value of a pointer after the object it references has been deleted. This is technically undefined behavior if you are using the default implementation of new and delete, so either you need to ensure that your implementation permits it, or you need to use a custom allocator that permits such usage.

Here is a relevant post to the undefined/unspecified behavior I am talking about here. The piece of code the above note is referring to is the following:

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
  node* old_head=head.load();
  node* temp;
  do {
    temp=old_head;         // Here we are reading (not dereferencing) a pointer that might have been deleted already
    hp.store(old_head);    // And here
    old_head=head.load();
  } while(old_head!=temp); // And here
  // ...
}

In fact, I would say the same problem exists when Reference Counting is used instead of Hazard Pointers (the book does not make such a claim). The following is how one pushes an element into a stack using reference counting (Page 208). The whole purpose of the while-loop in this code is to make sure value of new_node.ptr->next is valid, and that involves reading a pointer that might have been already deleted.

void push(T const& data) {
  counted_node_ptr new_node;
  new_node.ptr=new node(data);
  new_node.external_count=1;
  new_node.ptr->next=head.load(std::memory_order_relaxed)
  while(!head.compare_exchange_weak(
                new_node.ptr->next,
                new_node,
                std::memory_order_release,
                std::memory_order_relaxed)); }

Answer 1

This is the so called "memory reclamation problem" - an object must not be deleted as long as some thread may still hold a reference to it and thus might still access it. If a thread wants to "release" some object, it usually does not call delete directly but some retire function that stores the pointer and defers reclamation until later when it is safe (i.e., in case of hazard pointers until no thread holds a HP to this object). Since scanning the hazard pointers of all threads is rather expensive this is only done once the number of retired objects reaches some threshold. This way it is absolutely possible to implement hazard pointers with well defined behavior.

The code of your pop operation is missing some important details - you are about to replace head, but what do you do with the old value? How do you reclaim it? Do you simply call delete?

Arch D. Robison proposed N3712 : Policy-Based Design for Safe Destructionin Concurrent Containers as a generic interface for memory reclamation schemes for the C++ standard. The general idea is that you have the concept of a guard_ptr that holds a safe reference to the object (similar to a share_ptr). As long as any thread holds such a guard_ptr to an object, this object cannot be deleted, and you may only access the object after acquiring such a guard_ptr. If you want to reclaim an object you simply call guard_ptr::retire. Then the object will eventually be deleted by the underlying implementation once it is safe.

Reference counting is a whole different story, because it is not possible to load the pointer and increase the ref counter in a single atomic operation. That's why with lock-free reference counting it is never possible to return a retired object to the memory manager, because the ref counter has to be available indefinitely. Instead, the nodes are usually kept in a free-list and reused.

Regarding your push operation that uses reference counting - this is perfectly safe. The while loop keeps trying to update head with new_node, where new_node.ptr->next is the expected value. If the CAS fails, the current value is stored in new_node.ptr->next, but this is fine because since the CAS has failed new_node is not visible, so no other thread can access it. Where do you think we are reading a pointer that might have been already deleted.

If you are interested in this topic I can refer you to my thesis Effective memory reclamation for lock-free data structures in C++. It not only provides a general discussion about a large number of reclamation schemes, but also covers in great detail my own implementation of various reclamation schemes based on an adapted version of the previously mentioned interface proposed by Arch D. Robison.

Based on my work for this thesis I started an open source library that provides implementations of various reclamation schemes (including hazard pointers and lock-free reference counting) and concurrent data structures: xenium

Update
Regarding your statement that "reading the value of (and not dereferencing) an already deallocated pointer is in general undefined" - I don't have that book, so I am not sure what the author refers to. And I don't know why the authro in the referenced SO answer states that '"Using" includes "copying the value of"'. The C++17 standard says the following about invalid pointer values:

Indirection through an invalid pointer value and passing an invalid pointer value to a deallocation function have undefined behavior. Any other use of an invalid pointer value has implementation-defined behavior.

And as a footnote:

Some implementations might define that copying an invalid pointer value causes a system-generated runtime fault.

The reason for the possibility of a potential runtime fault is that some architectures in the past used dedicated address registers for pointer loads and stores and they could fault if, for example, a segment number in a pointer was not currently mapped. However, I am not aware of any current architecture or compiler on which reading an invalid pointer value would cause such a fault.

The pointer_safety concept was added in C++11 as part of the garbage collector interface (see the N2670: Minimal Support for Garbage Collection and Reachability-Based Leak Detection proposal). The book "The C++ Programming Language" (4th edition) by Bjarne Stroustrup says the following about the pointer_safety values:

• relaxed: Safely-derived and not safely-derived pointers are treated equivalent. Collect every object that does not have a safely derived or traceable pointer to it.
• preferred: Like relaxed, but a garbage collector may be running as a leak detector and/or a detector of dereferences of "bad pointers".
• strict: Safely-derived and not safely-derived pointers may be treated differently; that is, a garbage collector may be running and will ignore pointers that are not safely derived.

So the whole pointer_safety is only relevant when you use a garbage collector.