How does hazard pointer check whether or not it's pointed by other threads?
BestBunny
Also interested in answer to above question. Furthermore, wouldn't the entirety of that "if statement" that checks if n is not pointer to by any thread's hazard pointer followed by removing n have to be atomic? Because if it isn't, another thread could change its hazard pointer to point to n right after the check succeeds, thereby causing problems.
pdp
Why is there no if (doubleword_CAS(s, old, new_stack) "==old") in this or the previous slide? Why is the return of doubleword_CAS not compared to old? And shouldn't it be doubleword_CAS(*s, old, new_stack)?
kayvonf
@pdp. I was being a little loose with my syntax. You can interpret the slide as using an op that returns true if the CAS succeeds. (if the value in memory at the location matches the value in old).
In the code s is a pointer, so it can directly passed to the CAS.
kayvonf
@BestBunny, @rootB. retire() can look to see if the node n it is trying to delete is the hazard pointer in any of the other threads. (Note that hazard is a locally visibile per-thread pointer.) A node pointed at by the hazard pointer cannot be deleted since a thread may be deference that address.
ykt
In retire, after the check to remove a node succeeds, no thread can set that node as a hazard pointer because everyone will see the new stack top at that point.
emt
Is it possible for the same node to appear in multiple retire lists? If so, is there something in place to remove it from the rest of the retire lists once it is deleted?
kayvonf
@emt. No it is not. This is because a node is marked as "retired" when it is successfully removed from the stack, and this can happen exactly once. A simple implementation would delete the memory for the node at this point, but it's possible that another thread is still holding a pointer to this node. (and if so, that thread's hazard pointer will be set to the node.) Therefore, the implementation deletes retired nodes at some later time, and before deleting checks to make sure the node is not on some threads hazard list.
atadkase
@kayvonf If per thread hazard pointer has to be checked, will there be a need for inter-thread communication when the retire function determines the necessity of a cleanup?
kayvonf
@atadkase. Yes. But this is a shared address space system. So by "per-thread communication" you really mean that P0 will inspect addresses last written to by P1.
life
when DCAS in thread A is done successfully and delete old.top as the previous slide suggests, thread B's PC may be right after if (old.top == NULL) {...}. In this situation, referencing old.top->next raises segment fault. So the solution proposed here is that, instead of for thread A to delete old.top as soon as DCAS succeeds, thread A marks old.top as TOBEDELETED. thread B will still be able to reference old.top->next but its DCAS will doom to fail. When thread B starts its next iteration, its hazard pointer will point to the new top of the stack. When no hazard pointers are pointing to the TOBEDELETED old.top and when the number of these TOBEDELETED old.top is big enough, some thread will do the cleaning. The THRESHOLD is just a complication that reduces overhead of memory deallocation.
vasua
I wonder if this is the mechanism behind the implementation of shared_ptr in c++, which provides some semblance of garbage-collection semantics in C++, which is obviously not a garbage collected language. From what I understand there is some sort of internal reference counting. Would that be considered similar to a hazard pointer?
khans
"Each reader thread owns a single-writer/multi-reader shared pointer called "hazard pointer." When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), "I am reading this map. You can replace it if you want, but don't change its contents and certainly keep your deleteing hands off it."
-Andrei Alexandrescu and Maged Michael, Lock-Free Data Structures with Hazard Pointers
https://en.wikipedia.org/wiki/Hazard_pointer
It's like all of the threads have a shared list of pointers and a counter for each, so that everyone knows which references are still live. Manual garbage collection.
How does hazard pointer check whether or not it's pointed by other threads?
Also interested in answer to above question. Furthermore, wouldn't the entirety of that "if statement" that checks if n is not pointer to by any thread's hazard pointer followed by removing n have to be atomic? Because if it isn't, another thread could change its hazard pointer to point to n right after the check succeeds, thereby causing problems.
Why is there no if (doubleword_CAS(s, old, new_stack) "==old") in this or the previous slide? Why is the return of doubleword_CAS not compared to old? And shouldn't it be doubleword_CAS(*s, old, new_stack)?
@pdp. I was being a little loose with my syntax. You can interpret the slide as using an op that returns true if the CAS succeeds. (if the value in memory at the location matches the value in
old
).In the code
s
is a pointer, so it can directly passed to the CAS.@BestBunny, @rootB.
retire()
can look to see if the noden
it is trying to delete is the hazard pointer in any of the other threads. (Note thathazard
is a locally visibile per-thread pointer.) A node pointed at by the hazard pointer cannot be deleted since a thread may be deference that address.In retire, after the check to remove a node succeeds, no thread can set that node as a hazard pointer because everyone will see the new stack top at that point.
Is it possible for the same node to appear in multiple retire lists? If so, is there something in place to remove it from the rest of the retire lists once it is deleted?
@emt. No it is not. This is because a node is marked as "retired" when it is successfully removed from the stack, and this can happen exactly once. A simple implementation would delete the memory for the node at this point, but it's possible that another thread is still holding a pointer to this node. (and if so, that thread's hazard pointer will be set to the node.) Therefore, the implementation deletes retired nodes at some later time, and before deleting checks to make sure the node is not on some threads hazard list.
@kayvonf If per thread hazard pointer has to be checked, will there be a need for inter-thread communication when the retire function determines the necessity of a cleanup?
@atadkase. Yes. But this is a shared address space system. So by "per-thread communication" you really mean that P0 will inspect addresses last written to by P1.
when DCAS in thread A is done successfully and delete old.top as the previous slide suggests, thread B's PC may be right after if (old.top == NULL) {...}. In this situation, referencing old.top->next raises segment fault. So the solution proposed here is that, instead of for thread A to delete old.top as soon as DCAS succeeds, thread A marks old.top as TOBEDELETED. thread B will still be able to reference old.top->next but its DCAS will doom to fail. When thread B starts its next iteration, its hazard pointer will point to the new top of the stack. When no hazard pointers are pointing to the TOBEDELETED old.top and when the number of these TOBEDELETED old.top is big enough, some thread will do the cleaning. The THRESHOLD is just a complication that reduces overhead of memory deallocation.
I wonder if this is the mechanism behind the implementation of shared_ptr in c++, which provides some semblance of garbage-collection semantics in C++, which is obviously not a garbage collected language. From what I understand there is some sort of internal reference counting. Would that be considered similar to a hazard pointer?
"Each reader thread owns a single-writer/multi-reader shared pointer called "hazard pointer." When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), "I am reading this map. You can replace it if you want, but don't change its contents and certainly keep your deleteing hands off it."
-Andrei Alexandrescu and Maged Michael, Lock-Free Data Structures with Hazard Pointers
https://en.wikipedia.org/wiki/Hazard_pointer
It's like all of the threads have a shared list of pointers and a counter for each, so that everyone knows which references are still live. Manual garbage collection.