Multithreading – lockless memory reclamation with dangerous pointers

Hazard pointers is a technique for safely reclaiming memory without garbage collection and lock - free code

The idea is that before accessing an object that can be deleted at the same time, the thread sets its dangerous pointer to point to the object The thread to delete an object will first check whether any dangerous pointers are set to point to the object If so, the deletion will be delayed so that the access thread will not eventually read the deleted data

Now, suppose our delete thread starts iterating over the dangerous pointer list and is preempted in the ith element Now another thread sets my dangerous pointer to delete the object that the thread is currently trying to delete After that, the delete thread resumes, checks the rest of the list, and deletes the object, even if there is now a dangerous pointer at position I pointing to the object

Therefore, it is clear that setting the dangerous pointer is not enough, because the deleting thread may have checked our dangerous pointer and decided that our thread does not want to access the object After setting the danger pointer, how can I ensure that the object I am trying to access is not deleted from my hands?

Solution

Authoritative answer

Original paper by maged M. Michael places this important limitation on algorithms that use dangerous pointers:

What does it mean to delete a thread

As Anton's answer pointed out in, deleting is a two-stage operation: first, you must "unpublish" the node and delete it from the data structure so that it can no longer be accessed from the public interface

At this point, Michael's term may delete nodes Concurrent threads are no longer safe to access it (unless they already hold a dangerous pointer)

Therefore, once a node may be deleted, the deletion thread can safely iterate over the dangerous pointer list Even if the delete thread is preempted, the concurrent thread may no longer access the node After verifying that the dangerous pointer is not set to the node, the deletion thread can safely proceed to the second stage of deletion: actual release

In short, the sequence of operations for deleting threads is

D-1. Remove the node from the data structure.
D-2. Iterate the list of hazard pointers.
D-3. If no hazards were found,delete the node.

The real algorithm involves a little, because we need to maintain a list of nodes that cannot be recycled and ensure that they are eventually deleted This has been skipped here because it has nothing to do with the question posed by the explanation question

What does it mean to access threads

Setting a hazard indicator is not sufficient to ensure safe access to it After all, when we set the dangerous pointer, the node may be deleted

The only way to ensure secure access is if we can ensure that our dangerous pointer is constantly pointing to the node from the time of arrival from the root directory of the object

Since the code should be lockless, there is only one way to achieve this: We optimistically set our dangerous pointer to the node, and then check whether the node is marked as likely to be deleted (that is, it is no longer reachable from the common root)

Therefore, the operation order of the access thread is

A-1. Obtain a pointer to the node by traversing the data structure.
A-2. Set the hazard pointer to point to the node.
A-3. Check that the node is still part of the data structure.
     That is,it has not been possibly removed in the meantime.
A-4. If the node is still valid,access it.

Potential race impact delete thread

After the node (D - 1) may be deleted, the deletion thread may be preempted Therefore, concurrent threads can still optimistically set their dangerous pointer to it (even if access to it is not allowed) (A-2)

Therefore, deleting a thread may detect a false danger and prevent it from deleting a node immediately, even if none of the other threads will access the node again This will simply delay the deletion of nodes in the same way as the legal danger

The important point is that the node will eventually be deleted

Potential race affecting access threads

Before verifying that the node is not potentially deleted, the access thread may be preempted by the deleted thread (A-3) In this case, access to the object is no longer allowed

Please note that if preemption occurs after A-2, it is even safe for the access thread to access the node (because there is a dangerous pointer to the node), but since it is impossible for the access thread to distinguish, it must fail falsely in this case

The important point is that if a node is not deleted, it will only be accessed