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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <16c2aba7-212d-4612-8cea-50c64626d8f3@huaweicloud.com>
Date: Fri, 20 Sep 2024 09:43:52 +0200
From: Jonas Oberhauser <jonas.oberhauser@...weicloud.com>
To: Jann Horn <jannh@...gle.com>, Boqun Feng <boqun.feng@...il.com>,
 "Paul E. McKenney" <paulmck@...nel.org>
Cc: linux-kernel@...r.kernel.org, rcu@...r.kernel.org, linux-mm@...ck.org,
 lkmm@...r.kernel.org, Frederic Weisbecker <frederic@...nel.org>,
 Neeraj Upadhyay <neeraj.upadhyay@...nel.org>,
 Joel Fernandes <joel@...lfernandes.org>,
 Josh Triplett <josh@...htriplett.org>, Uladzislau Rezki <urezki@...il.com>,
 Steven Rostedt <rostedt@...dmis.org>,
 Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
 Lai Jiangshan <jiangshanlai@...il.com>, Zqiang <qiang.zhang1211@...il.com>,
 Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>,
 Will Deacon <will@...nel.org>, Waiman Long <longman@...hat.com>,
 Mark Rutland <mark.rutland@....com>, Thomas Gleixner <tglx@...utronix.de>,
 Kent Overstreet <kent.overstreet@...il.com>,
 Linus Torvalds <torvalds@...ux-foundation.org>,
 Vlastimil Babka <vbabka@...e.cz>, maged.michael@...il.com,
 Neeraj Upadhyay <neeraj.upadhyay@....com>, lkmm@...ts.linux.dev
Subject: Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard
 pointers

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@...il.com> 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