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

[Jonas Oberhauser]

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