Am 9/19/2024 um 10:30 PM schrieb Jonas Oberhauser:
Am 9/19/2024 um 2:12 AM schrieb Jann Horn:
On Tue, Sep 17, 2024 at 4:33 PM Boqun Feng <boqun.feng@xxxxxxxxx> wrote:
Hazard pointers [1] provide a way to dynamically distribute refcounting
and can be used to improve the scalability of refcounting without
significant space cost.
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+ void *const *p,
+ unsigned long head_offset)
+{
+ void *ptr;
+ struct callback_head *head;
+
+ ptr = READ_ONCE(*p);
+
+ if (ptr == NULL)
+ return NULL;
+
+ head = (struct callback_head *)(ptr + head_offset);
+
+ WRITE_ONCE(*hzp, head);
+ smp_mb();
+
+ ptr = READ_ONCE(*p); // read again
+
+ if (ptr + head_offset != head) { // pointer changed
+ WRITE_ONCE(*hzp, NULL); // reset hazard pointer
+ return NULL;
+ } else
+ return ptr;
+}
I got nerdsniped by the Plumbers talk. So, about that smp_mb()...
I think you should be able to avoid the smp_mb() using relaxed atomics
(on architectures that have those), at the cost of something like a
cmpxchg-acquire sandwiched between a load-acquire and a relaxed load?
I'm not sure how their cost compares to an smp_mb() though.
We have done a similar scheme before, and on some architectures (not
x86) the RMW is slightly cheaper than the mb.
Your reasoning is a bit simplified because it seems to assume a stronger
concept of ordering than LKMM has, but even with LKMM's ordering your
code seems fine.
I feel it can even be simplified a little, the hazard bit does not seem
necessary.
Assuming atomic operations for everything racy, relaxed unless stated
otherwise:
(R)eader:
old = read p // I don't think this needs acq, because of address
dependencies (*)
haz ||=_acq old
if (read p != old) retry;
I realized before going to bed that I copied a subtle mistake here from
Jann's code, we need an address dependency from this read, or it is not
ABA safe.
This can be done with the small detour that Boqun used:
head = read p // I don't think this needs acq, because of address
dependencies (*)
haz ||=_acq head
old = read p // again
if (head != old) retry;
barrier(); // ensure compiler does not use its knowledge that head
== old to do *head instead!
*old // definitely use the second read pointer so hardware can't
speculatively dereference this before the second read!
Have a good time,
jonas
