Thread: Trying to understand hazard pointer implementation

Hi.

I am implementing hazard pointers.

The original paper is here;

Index of /downloads/white papers/[SMR]%20-%20[Michael]%20-%20Hazard%20Pointers;%20Safe%20Memory%20Reclaimati on%20for%20Lock-Free%20Objects.pdf

McKenney in this white paper;

Structured Deferral: Synchronization via Procrastination - ACM Queue

gives some example code and looks like this (copied nearly verbatim, I moved one opening curley brace);

Code:

1  int hp_record(void **p, void **hp)
2  {
3    void *tmp;
4    tmp = ACCESS_ONCE(*p);
5    ACCESS_ONCE(*hp) = tmp;
6    smp_mb();
7    if (tmp != ACCESS_ONCE(*p))
8    {
9      ACCESS_ONCE(*hp) = NULL;
10     return 0;
11   }
12   return 1;
13 }

We see here in this code there are no atomic operations. The hazard pointer is set on line 5 (and confirmed on line 7) and there is a full barrier on line 6 - this means that in principle, the write we made to "*hp" may never be seen by any other core, ever.

Imagine I want to set a hazard pointer.

The first thing I must do is get a copy of the pointer I wish to protect. I can actually do this using the code above, i.e. I get a copy by putting it into the hazard pointer, but the problem is that code does not use an atomic operation at all. It sets the hazard pointer on line 5, issues a load barrier (as part of a full barrier) on line 6 and then checks the hazard pointer is still correct on line 7; but there is in none of this a forced write to memory (an atomic operation) so in principle the hazard pointer which has been set may *never* been seen by any physical core - i.e. *it has not been made visible*, which means it cannot work.

I may well be mistaken, but reading the original white paper, the intent of line 7 appears to be to ensure that the hazard pointer is visible to other threads.

I do not see how this can be so because store buffers mean that the write to the hazard pointer on line 5 is not necessarily visible to other threads, and the check on line 7 does not address this problem - it only checks that the invalidation requests serviced by the load part of the full barrier on line 6 have caused "*p" to change, which is to say, ensures that the value written to the hazard pointer is correct. I believe it is correct, but I also - as above - believe it is not yet visible to other physical cores, which is a fatal problem.

I am wondering if I properly and fully understand how memory barriers and atomic operations work.