Moving a list with hazard pointers

Question

I am working with a Hazard pointer to implement a lock-related list in C. I could not find any sample code other than different bases and stacks. The problem is that I need to go through the list, so my question is whether I can change the value of the hazard indicator when it is assigned. For example:

t←Top while(true) { if t=null then return null *hp←t if Top!=t then continue ... t←(t→next) //after this instruction pointer t will be still protected? } 

Answer 1

Finally, I finished implementing my own version of the Hazard Pointers (HP) according to the original paper . The answer to my question: "No", "t" is safer to use. The reason is that how HP works, * hp protects the node pointed to by t when you declared it a dangerous pointer, so when t moves to the next node, the HP engine retains the protection of the previous node. I must reassign the new * hp value before I can use it safely.

Also, in the sample article, it is not explicit, but when you finish using the hazard pointer, you must free it. This means returning * hp to its original state (NULL). Thus, if another thread wants to delete (delete) this node, it will not be considered as used.

In my example above, I have to free * hp before leaving this method. Inside the loop, this is not necessary because I am rewriting the same * hp (* hp ← t) position, so the previous node is no longer protected.

Answer 2

You do not need hazard indicators when you are viewing only the list. A danger arises when different streams read and write from the same resource (in particular, hazard pointers must overcome the ABA problem when the resource value is changed to something, and then returns to its original value, which makes it difficult to replace the change). You are only reading the passage, so there is no need for hazard indicators.

By the way, it seems to me that you need to change if Top=t to if Top!=t so that you can continue your code if there is no danger. Note that continue returns to the beginning of the loop. In addition, all of your code should be in a (true) loop.

You can read more about hazard indicators here http://www.drdobbs.com/lock-free-data-structures-with-hazard-po/184401890 or simply by a search query!

EDIT . You need to provide code to insert and remove functions. In short, the part of the code you mentioned ends in an endless loop after executing t←(t→next) , since Top! = T will be true after that. What you need to do instead of checking t against Top is to check it against a previously fixed value. Again, it depends on your implementation of the other methods, but you probably want to implement something similar to the Tim Harris algorithm , which uses two-phase deletion (1-labeling and 2-release node). Then, when you cross the list, you also need to check the marked nodes. There is also an implementation of a doubly linked list with a search method, which you can use as the basis of your implementation, in fig. 9 from http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf . Hope this helps.