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 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;
   *old

(W)riter:

   p =_??? ... // assuming we don't set it to null this needs a rel
   --- mb ---
   haz ||= 0
   while (read_acq haz == old) retry;
   delete old


In order to get a use-after-free, both of the R:read p need to read before W:p = ... , so because of the W:mb, they execute before W:haz||=0 .

Also, for the use-after-free, W:read_acq haz needs to read before (the write part of) R:haz||=_acq old .


Then the W:haz ||= 0 also needs to read before (the write part of) R:haz||=_acq old because of coherence on the same location.

Since both of them are atomic RMW, the W:haz||= 0 also needs to write before (the write part of) R:haz||=_acq old , and in the absence of non-RMW writes (so assuming no thread will just store to the hazard pointer), this implies that the latter reads-from an rmw-sequence-later store than W:haz||=0 , which therefore executes before R:haz||=_acq old .

But because of the acquire barrier, R:haz||=_acq old executes before the second R:read p .


This gives a cycle
   (2nd)R:read p  ->xb  W:haz||=0  ->xb  R:haz||=_acq  ->xb  (2nd)R:read p

and therefore is forbidden.

Note that in this argument, the two R:read p are not necessarily reading from the same store. Because of ABA, it can happen that they read from distinct stores and see the same value.

It does require clearing hazard pointers with an RMW like atomic_and(0) (**). The combination of the two RMW (for setting & clearing the hazard pointer) might in total be slower again than an mb.


(I took the liberty to add an acquire barrier in the writer's while loop for the case where we read from the (not shown) release store of the reader that clears the hazard pointer. It's arguable whether that acq is needed since one could argue that a delete is a kind of store, in which case control dependency would handle it.)

have fun,
  jonas


(*
you talk about sandwiching, and the data dependency does guarantee some weaker form of sandwiching than the acq, but I don't think sandwiching is required at all. If you happened to be able to set the hazard pointer before reading the pointer, that would just extend the protected area, wouldn't it?
)

(**
I think if you clear the pointer with a store, the hazard bit does not help. You could be overwriting the hazard bit, and the RMWs that set the hazard bit might never propagate to your CPU.

Also in your code you probably meant to clear the whole hazard pointer in the retry code of the reader, not just the hazard bit.)





[Index of Archives]     [Linux ARM Kernel]     [Linux ARM]     [Linux Omap]     [Fedora ARM]     [IETF Annouce]     [Bugtraq]     [Linux OMAP]     [Linux MIPS]     [eCos]     [Asterisk Internet PBX]     [Linux API]

  Powered by Linux