0

This is for the "hazard pointer" algorithm, a lock-free algorithm in multi-threaded environments.

The hazard pointer algorithm works like this:

  1. save the global pointer to a local pointer.
  2. put the local pointer to hazard pointer list to show others can't reclaim it.

I run into an issue that how can we make sure the global pointer is not reclaimed before step 2?

void *local_p = global_p;
put_local_p_to_hazard_list(local_p);

Before the call to put_local_p_to_hazard_list(), the local_p may be reclaimed; how can I avoid that?

S.S. Anne
  • 15,171
  • 8
  • 38
  • 76
zhihuifan
  • 1,093
  • 2
  • 16
  • 30
  • 1
    Suggestion: add a new pointer to the hazard list, atomic swap the hazard pointer with the global pointer, then copy the original pointer from the hazard list to the local. It cannot be reassigned during the atomic swap, nor can it be reassigned after because it is then a hazard. – Davislor Jul 05 '19 at 00:23
  • I think your question would greatly benefit from more context ... you're running in a multithreaded environment here I guess. – Daniel Jour Jul 05 '19 at 00:25
  • yes, @DanielJour, I will highlight this. – zhihuifan Jul 05 '19 at 00:26
  • 2
    Which language are you using? Asking questions with both the C and C++ tags tends to be frowned upon — not least because many questions require very different answers for an idiomatic C solution and an idiomatic C++ solution (even if there is also a solution that does work in both C and C++, it is seldom idiomatic for both). – Jonathan Leffler Jul 05 '19 at 01:10
  • How can the local pointer be reclaimed before you add it to the list? It is a pointer that is local to the current thread; no other thread should be accessing it, should they? Especially not releasing it. Or are you saying the `global_p` could be reclaimed before you manage to put the `local_p` copy onto the list? – Jonathan Leffler Jul 05 '19 at 01:13
  • @JonathanLeffler: yes, the local_p pointer to the same address as global_p, and global_p can be reclaimed by other thread. – zhihuifan Jul 05 '19 at 01:21
  • Is it true that this is how "the" hazard pointer algorithm works, or is this merely your implementation of the hazard pointer approach? That is, is it an acceptable answer to tell you the algorithm is wrong (because the global pointer could be reclaimed between the steps)? – JaMiT Jul 05 '19 at 01:23
  • @JaMiT . it is true how the algorithm works. actually the expectation is the answer should be know this algorithm at least, that's why I didn't explain the whole algorithm here. but any suggestion to improve the question is very welcome. – zhihuifan Jul 05 '19 at 01:31
  • @zhihuifan Why would you want to make such a restriction on the people who might have a good answer? Compare your original no-explanation question to [this one](https://stackoverflow.com/questions/25204494/lock-free-memory-reclamation-with-hazard-pointers). Teach others about what you are working with and you might learn something along the way. – JaMiT Jul 05 '19 at 01:56
  • @zhihuifan Doing a search of other questions regarding hazard pointers, I came across [Is this hazard pointer example flawed because of ABA issue](https://stackoverflow.com/questions/48783613/is-this-hazard-pointer-example-flawed-because-of-aba-issue), which contradicts your claim that your version of the algorithm is the correct one. (More precisely, it contradicts the completeness of your version of the algorithm.) – JaMiT Jul 05 '19 at 01:57
  • @JaMiT： Thank you for the example! I can do the similar next time. – zhihuifan Jul 05 '19 at 02:01
  • @JonathanLeffler Actually C/C++ is a thing, even though many ppl here claim it isn't and these language only accidentally have some constructs in common. Notably **C and C++ have the same threading model.** Intentionally. None of the similarity or compatibility is an accident. C and C++ committee work seriously to preserve that. – curiousguy Jul 05 '19 at 05:38

2 Answers2

0

the answer should be double-check after we put it to my owner hazard point list. here is a simple example. if you find bugs, please let me know. (looks it have bugs, please do see the comments)

hazard_pointer * hp = acquire_hazard_pointer();
void* local_p;
do {
  local_p = global_p;
  hp->ptr = local_p;
  __asm__ volatile("mfence" ::: "memory");  // prevent the `while` executed before the `hp = local_p`;
} while ( local_p != global_p );

read_local_p(local_p);
...
zhihuifan
  • 1,093
  • 2
  • 16
  • 30
  • Is this the read side? You don't need `mfence` here, only a compiler barrier. e.g. `local_p = atomic_load_explicit(&global_p, memory_order_acquire);` or if you don't want to fix the UB of reading a non-atomic global, maybe `asm("" :::"memory");` for x86. [When should I use \_mm\_sfence \_mm\_lfence and \_mm\_mfence](//stackoverflow.com/a/50780314) – Peter Cordes Jul 05 '19 at 04:29
  • More importantly, a retry loop makes no sense. If `global_p` can change after you read it, it can also change between leaving the `do{}while()` and dereferencing `local_p`. You can't fix that race condition purely on the read side. – Peter Cordes Jul 05 '19 at 04:30
  • 1
    I wonder if you meant to write `*hp = local_p;` or something, because this code overwrites the `hp = acquire_hazard_pointer();` return value without ever using it. (I forget how hazard pointers work so maybe that doesn't make sense, but `hp = local_p;` appears to be a totally pointless statement in this snippet.) – Peter Cordes Jul 05 '19 at 04:32
  • @PeterCordes : you are right on the `*hp = local_p' part, I will change the snippet code. for the other 2 part, especially the `do {} while ()` comment, how can we make it after we considering the write part? I am learning more about the `mfence`. – zhihuifan Jul 05 '19 at 04:51
  • Ok yes, then `mfence` might make after all, to make this thread stall until the `hp->ptr = local_p` is globally visible. Your `global_p` probably should be `volatile` or preferably `_Atomic`, but the memory-clobber should force a re-read. And you *want* the `local_p = global_p` in the next iteration to CSE with the check. You could express that with a tmp var so you can use `_Atomic foobar *global_p` and still have the compiler optimize it nicely. – Peter Cordes Jul 05 '19 at 05:05
  • @PeterCordes: I'm confused now, so do we have race issue on the `do {} while ()` part? – zhihuifan Jul 05 '19 at 06:01
  • If other threads can still modify `global_p` then maybe. But if you only need to check for races that happen before your own store becomes globally visible, then this code is fine. Like I said, I forget how hazard pointers are supposed to work, but I think making your store visible in the location `acquire_hazard_pointer` gave you is sufficient to make it safe to read from that value of `global_p`. So the only window for having the rug pulled out from under you is between the load and the store becoming visible. A check *after* that `mfence` completes should be sufficient. – Peter Cordes Jul 05 '19 at 06:08
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/196033/discussion-between-zhihuifan-and-peter-cordes). – zhihuifan Jul 05 '19 at 08:49
0

After storing the HP you have to re-check that the pointer has not been updated (i.e., you do need a retry-loop as you already figured out yourself). And yes, you do need a seq-cst fence to ensure that either the HP, or the updated pointer is visible. In case you are interested you can check out my HP implementation (it is C++ though): https://github.com/mpoeter/xenium/blob/master/xenium/reclamation/impl/hazard_pointer.hpp
For those interested in the gory details - I provide correctness arguments about the implementation based on the semantics of the C++ memory model in my thesis.

mpoeter
  • 2,574
  • 1
  • 5
  • 12