Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 





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





[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux