Hazard pointer enabled refcount prototype

Hazard pointer enabled refcount prototype

[Mathieu Desnoyers]

Hi Greg,

After our discussion at KR2024, I've created a prototype adding hazard pointer
dereference support to refcount.h:

https://github.com/compudj/linux-dev/commit/234523dc9be90f1bc9221bf2d430c9187ac61528

Branch: https://github.com/compudj/linux-dev/tree/hp-6.11-refcount

It allows dereferencing a pointer to a refcount and incrementing the refcount,
without relying on RCU.

A good candidate for this would be the "usblp" driver which is using a static mutex
for existence guarantees. Introducing a refcount as first field of struct usblp
should do the trick.

I am not entirely sure if this kind of use-case justifies introducing hazard pointers
though, as this can be done just as well with RCU. I'll let you be the judge on this.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: Hazard pointer enabled refcount prototype

[Greg Kroah-Hartman]

On Fri, Oct 04, 2024 at 03:52:01PM -0400, Mathieu Desnoyers wrote:
> Hi Greg,
> 
> After our discussion at KR2024, I've created a prototype adding hazard pointer
> dereference support to refcount.h:
> 
> https://github.com/compudj/linux-dev/commit/234523dc9be90f1bc9221bf2d430c9187ac61528
> 
> Branch: https://github.com/compudj/linux-dev/tree/hp-6.11-refcount
> 
> It allows dereferencing a pointer to a refcount and incrementing the refcount,
> without relying on RCU.
> 
> A good candidate for this would be the "usblp" driver which is using a static mutex
> for existence guarantees. Introducing a refcount as first field of struct usblp
> should do the trick.
> 
> I am not entirely sure if this kind of use-case justifies introducing hazard pointers
> though, as this can be done just as well with RCU. I'll let you be the judge on this.

How could it be used with RCU?  I'll have to look into that, but thanks
for the links and I'll dig into this on Monday to see if I could use
these to get rid of the "static mutex" pattern that almost all drivers
need to have these days (which in turn will mean we will not need to use
that in new rust drivers either, which will make them simpler as well
because the static mutex pattern in rust is rough to make work.)

thanks,

greg k-h

Re: Hazard pointer enabled refcount prototype

[Mathieu Desnoyers]

On 2024-10-05 10:43, Greg Kroah-Hartman wrote:
> On Fri, Oct 04, 2024 at 03:52:01PM -0400, Mathieu Desnoyers wrote:
>> Hi Greg,
>>
>> After our discussion at KR2024, I've created a prototype adding hazard pointer
>> dereference support to refcount.h:
>>
>> https://github.com/compudj/linux-dev/commit/234523dc9be90f1bc9221bf2d430c9187ac61528
>>
>> Branch: https://github.com/compudj/linux-dev/tree/hp-6.11-refcount
>>
>> It allows dereferencing a pointer to a refcount and incrementing the refcount,
>> without relying on RCU.
>>
>> A good candidate for this would be the "usblp" driver which is using a static mutex
>> for existence guarantees. Introducing a refcount as first field of struct usblp
>> should do the trick.
>>
>> I am not entirely sure if this kind of use-case justifies introducing hazard pointers
>> though, as this can be done just as well with RCU. I'll let you be the judge on this.
> 
> How could it be used with RCU?

This is a trick I've used a lot with liburcu: Using RCU guarantees for
object lookup (pointer dereference) chained with reference counting
(obtained with refcount_inc_not_zero() to keep using the object for
longer than a RCU read-side critical section.

Object reclaim then goes as follow:

- unpublish pointer to object (e.g. list_del or set pointer to NULL).
- refcount_dec_and_test
   -> in release callback, use call_rcu to reclaim object, thus
      chaining reference count decrement to 0 with an RCU grace period.

Object lookup/refcount inc goes as follow:

- rcu read lock
- rcu_deference() to get pointer to object
- try to grab reference with refcount_inc_not_zero
   - if it fails, rcu read unlock and return NULL.
   - on success, we have a reference to the object.
- rcu read unlock

return pointer to an object guaranteed to exist due to refcount,
or NULL if it was not found.

The same kind of trick can be done with hazard pointers rather than
RCU, e.g.:

Object reclaim then goes as follow:

- unpublish pointer to object (e.g. set pointer to NULL).
- refcount_dec_and_test
   -> in release callback, use hp_scan before reclaiming object, thus
      chaining reference count decrement to 0 with a HP scan.

Object lookup/refcount inc goes as follow:

- hp_dereference_acquire to get pointer to the object
- if NULL, return NULL
- try to grab reference with refcount_inc_not_zero
   - if it fails, hp_retire and return NULL
   - on success, we have a reference to the object.
- hp_retire

return pointer to an object guaranteed to exist due to refcount,
or NULL if it was not found.

> I'll have to look into that, but thanks
> for the links and I'll dig into this on Monday to see if I could use
> these to get rid of the "static mutex" pattern that almost all drivers
> need to have these days (which in turn will mean we will not need to use
> that in new rust drivers either, which will make them simpler as well
> because the static mutex pattern in rust is rough to make work.)

If your target is Rust, I have ideas on how we could turn this kind
of Hazard Pointer + Reference Counter combined scheme into smart pointers.
Let me know if this is indeed your goal, and we can discuss this further.

Thanks,

Mathieu

> 
> thanks,
> 
> greg k-h

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com