Memory barrier for linux in hazard pointer implementation
- Dominant language
- C++
- Stars
- 30.5k
- Forks
- 5.9k
- PR merge metrics
- No merged PRs in 30d
Description
While try to understand and use hazard pointer here, i have a question regarding the memory barrier used and wonder if it's a real issue.
When using on linux with membarrier() available, the light barrier becomes compiler barrier and the heavy barrier becomes 'membarrier()'. In current implementation, there's a light barrier before 'retire' operation, a light barrier before 'try protect' operation and a heavy barrier when doing reclaim btw reading the retirement list and reading the hazard ptr list. I think the following could happen with current hazard pointer implementation(a simplified version):
source ptr: the memory pointer that can be protected by hazard pointer
thread 1: thread that tries to delete the source ptr
thread 2: consumer thread that tries to read source ptr
thread 3: the thread that does the memory reclaim (free memory from retirement list)
At start:
source ptr value = PTR_A
At time 0:
thread 1 (deleter): change source ptr to PTR_B and put PTR_A in the retirement list (retire operation); but let's say these results are not visible to the consumer thread (thread 2) but visible to thread 3 (reclaim thread), because there's only the light barrier.
At time 1:
thread 3 (reclaim thread): read the retirement list and found PTR_A in the list. issue the heavy barrier which is 'membarrier()' call. Say it first sends IPI to thread 2 and the CPU for thread 2 finishes.
At time 2:
thread 2 (consumer thread): read the old value (PTR_A) from source ptr (new value not visible yet). and calls 'try_protect' to protect the pointer. But this is not visible to other CPU yet, again since there's only compiler barrier now. thread 2 starts to use PTR_A.
At time 3:
the heavy barrier issued by thread 3 at time 1 now reaches thread 1 and finishes. Now thread 3 starts to collect the hazard pointer list. But the hazard pointer set by thread 2 at time 2 is not visible to thread 3 yet. So it doesn't see it. Then thread 3 now could see PTR_A in the retirement list but not in hazard pointer list, which means it would start to delete it.
Could this happen? do I miss anything? Thanks.
Contributor guide
Research direction
Start by reading the hazard pointer implementation, focusing on the light barriers around the retire and try_protect operations and the heavy barrier during reclaim. Trace the ordering described between the retirement list and hazard pointer list, including membarrier() when available. Done means determining whether the proposed interleaving can reclaim PTR_A while thread 2 still uses it, and documenting the conclusion or required follow-up.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, linux
- Domain
- operating-systems
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100