Previous | Next --- Slide 31 of 37
Back to Lecture Thumbnails
rootB

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.

@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.