[RFC] Synchronized Shared Pointers for the Linux kernel

[RFC] Synchronized Shared Pointers for the Linux kernel

[Mathieu Desnoyers]

Hi,

I've created a new API (sharedptr.h) for the use-case of
providing existence object guarantees (e.g. for Rust)
when dereferencing pointers which can be concurrently updated.
I call this "Synchronized Shared Pointers".

This should be an elegant solution to Greg's refcount
existence use-case as well.

The current implementation can be found here:

https://github.com/compudj/linux-dev/commit/64c3756b88776fe534629c70f6a1d27fad27e9ba

Patch added inline below for feedback.

Thanks!

Mathieu


diff --git a/include/linux/sharedptr.h b/include/linux/sharedptr.h
new file mode 100644
index 000000000000..ff925c509734
--- /dev/null
+++ b/include/linux/sharedptr.h
@@ -0,0 +1,163 @@
+// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+//
+// SPDX-License-Identifier: LGPL-2.1-or-later
+
+#ifndef _LINUX_SHAREDPTR_H
+#define _LINUX_SHAREDPTR_H
+
+/*
+ * sharedptr: Synchronized Shared Pointers
+ *
+ * Synchronized shared pointers guarantee existence of objects when the
+ * synchronized pointer is dereferenced. It is meant to help solving the
+ * problem of object existence guarantees faced by Rust when interfacing
+ * with C.
+ *
+ * Those shared pointers are based on a reference counter embedded into
+ * the object, using hazard pointers to provide object existence
+ * guarantee based on pointer dereference for synchronized shared
+ * pointers.
+ *
+ * References:
+ *
+ * [1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
+ *      lock-free objects," in IEEE Transactions on Parallel and
+ *      Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004
+ */
+
+#include <linux/hazptr.h>
+#include <linux/refcount.h>
+#include <linux/types.h>
+#include <linux/rcupdate.h>
+
+DECLARE_HAZPTR_DOMAIN(hazptr_domain_sharedptr);
+
+struct sharedptr_node {
+	refcount_t refcount;
+};
+
+/*
+ * Local copy of a shared pointer, holding a reference to a
+ * shared pointer node.
+ */
+struct sharedptr {
+	struct sharedptr_node *spn;
+};
+
+/*
+ * A syncsharedptr has a single updater, but many threads can
+ * concurrently copy a shared pointer from it using
+ * sharedptr_copy_from_sync(). Just like a sharedptr, a syncsharedptr
+ * holds a reference to a shared pointer node.
+ */
+struct syncsharedptr {
+	struct sharedptr_node *spn;
+};
+
+/*
+ * Initialize shared pointer node with refcount=1. Returns a shared pointer.
+ */
+static inline
+struct sharedptr sharedptr_create(struct sharedptr_node *spn)
+{
+	struct sharedptr sp = {
+		.spn = spn,
+	};
+	if (spn)
+		refcount_set(&spn->refcount, 1);
+	return sp;
+}
+
+static inline
+struct sharedptr sharedptr_copy(struct sharedptr sp)
+{
+	struct sharedptr_node *spn = sp.spn;
+
+	if (spn)
+		refcount_inc(&spn->refcount);
+	return sp;
+}
+
+static inline
+bool sharedptr_is_null(struct sharedptr sp)
+{
+	return sp.spn == NULL;
+}
+
+/* Move sharedptr to a syncsharedptr. */
+static inline
+void sharedptr_move_to_sync(struct syncsharedptr *dst, struct sharedptr *src)
+{
+	WARN_ON_ONCE(dst->spn);	/* Single updater, expect dst==NULL. */
+	rcu_assign_pointer(dst->spn, src->spn);
+	src->spn = NULL;	/* Transfer ownership. */
+}
+
+/*
+ * Copy sharedptr to a syncsharedptr, incrementing the reference.
+ */
+static inline
+void sharedptr_copy_to_sync(struct syncsharedptr *dst, const struct sharedptr *src)
+{
+	struct sharedptr_node *spn = src->spn;
+
+	WARN_ON_ONCE(dst->spn);	/* Single updater, expect dst==NULL. */
+	if (spn)
+		refcount_inc(&spn->refcount);
+	rcu_assign_pointer(dst->spn, spn);
+}
+
+/*
+ * Obtain a shared pointer copy from a syncsharedptr.
+ */
+static inline
+struct sharedptr sharedptr_copy_from_sync(const struct syncsharedptr *ssp)
+{
+	struct sharedptr_node *spn, *hp;
+	struct hazptr_slot *slot;
+	struct sharedptr sp;
+
+	preempt_disable();
+	hp = spn = hazptr_load_try_protect(&hazptr_domain_sharedptr, &ssp->spn, &slot);
+	if (!spn)
+		goto end;
+	if (!refcount_inc_not_zero(&spn->refcount))
+		spn = NULL;
+	hazptr_release(slot, hp);
+end:
+	sp.spn = spn;
+	preempt_enable();
+	return sp;
+}
+
+static inline
+void syncsharedptr_delete(struct syncsharedptr *ssp,
+			  void (*sharedptr_node_release)(struct sharedptr_node *spn))
+{
+	struct sharedptr_node *spn = ssp->spn;
+
+	if (!spn)
+		return;
+	WRITE_ONCE(ssp->spn, NULL);
+	if (refcount_dec_and_test(&spn->refcount)) {
+		hazptr_scan(&hazptr_domain_sharedptr, spn, NULL);
+		sharedptr_node_release(spn);
+	}
+}
+
+static inline
+void sharedptr_delete(struct sharedptr *sp,
+		      void (*sharedptr_node_release)(struct sharedptr_node *spn))
+{
+	struct sharedptr_node *spn = sp->spn;
+
+	if (!spn)
+		return;
+	WRITE_ONCE(sp->spn, NULL);
+	if (refcount_dec_and_test(&spn->refcount)) {
+		hazptr_scan(&hazptr_domain_sharedptr, spn, NULL);
+		sharedptr_node_release(spn);
+	}
+}
+
+#endif /* _LINUX_SHAREDPTR_H */
diff --git a/kernel/hazptr.c b/kernel/hazptr.c
index 3f9f14afbf1d..ba772f020325 100644
--- a/kernel/hazptr.c
+++ b/kernel/hazptr.c
@@ -8,6 +8,9 @@
  
  #include <linux/hazptr.h>
  #include <linux/percpu.h>
+#include <linux/sharedptr.h>
+
+DEFINE_HAZPTR_DOMAIN(hazptr_domain_sharedptr);
  
  /*
   * hazptr_scan: Scan hazard pointer domain for @addr.

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

Re: [RFC] Synchronized Shared Pointers for the Linux kernel

[Boqun Feng]

On Thu, Oct 10, 2024 at 03:16:25PM -0400, Mathieu Desnoyers wrote:
> Hi,
> 
> I've created a new API (sharedptr.h) for the use-case of
> providing existence object guarantees (e.g. for Rust)
> when dereferencing pointers which can be concurrently updated.
> I call this "Synchronized Shared Pointers".
> 
> This should be an elegant solution to Greg's refcount
> existence use-case as well.
> 
> The current implementation can be found here:
> 
> https://github.com/compudj/linux-dev/commit/64c3756b88776fe534629c70f6a1d27fad27e9ba
> 
> Patch added inline below for feedback.
> 
> Thanks!
> 
> Mathieu
> 
> 
> diff --git a/include/linux/sharedptr.h b/include/linux/sharedptr.h
> new file mode 100644
> index 000000000000..ff925c509734
> --- /dev/null
> +++ b/include/linux/sharedptr.h
> @@ -0,0 +1,163 @@
> +// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> +//
> +// SPDX-License-Identifier: LGPL-2.1-or-later
> +
> +#ifndef _LINUX_SHAREDPTR_H
> +#define _LINUX_SHAREDPTR_H
> +
> +/*
> + * sharedptr: Synchronized Shared Pointers
> + *
> + * Synchronized shared pointers guarantee existence of objects when the
> + * synchronized pointer is dereferenced. It is meant to help solving the
> + * problem of object existence guarantees faced by Rust when interfacing
> + * with C.
> + *
> + * Those shared pointers are based on a reference counter embedded into
> + * the object, using hazard pointers to provide object existence
> + * guarantee based on pointer dereference for synchronized shared
> + * pointers.
> + *
> + * References:
> + *
> + * [1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
> + *      lock-free objects," in IEEE Transactions on Parallel and
> + *      Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004
> + */
> +
> +#include <linux/hazptr.h>
> +#include <linux/refcount.h>
> +#include <linux/types.h>
> +#include <linux/rcupdate.h>
> +
> +DECLARE_HAZPTR_DOMAIN(hazptr_domain_sharedptr);
> +
> +struct sharedptr_node {
> +	refcount_t refcount;
> +};
> +
> +/*
> + * Local copy of a shared pointer, holding a reference to a
> + * shared pointer node.
> + */
> +struct sharedptr {
> +	struct sharedptr_node *spn;
> +};
> +
> +/*
> + * A syncsharedptr has a single updater, but many threads can
> + * concurrently copy a shared pointer from it using
> + * sharedptr_copy_from_sync(). Just like a sharedptr, a syncsharedptr
> + * holds a reference to a shared pointer node.
> + */
> +struct syncsharedptr {
> +	struct sharedptr_node *spn;
> +};
> +
> +/*
> + * Initialize shared pointer node with refcount=1. Returns a shared pointer.
> + */
> +static inline
> +struct sharedptr sharedptr_create(struct sharedptr_node *spn)
> +{
> +	struct sharedptr sp = {
> +		.spn = spn,
> +	};
> +	if (spn)
> +		refcount_set(&spn->refcount, 1);
> +	return sp;
> +}
> +
> +static inline
> +struct sharedptr sharedptr_copy(struct sharedptr sp)
> +{
> +	struct sharedptr_node *spn = sp.spn;
> +
> +	if (spn)
> +		refcount_inc(&spn->refcount);
> +	return sp;
> +}
> +
> +static inline
> +bool sharedptr_is_null(struct sharedptr sp)
> +{
> +	return sp.spn == NULL;
> +}
> +
> +/* Move sharedptr to a syncsharedptr. */
> +static inline
> +void sharedptr_move_to_sync(struct syncsharedptr *dst, struct sharedptr *src)
> +{
> +	WARN_ON_ONCE(dst->spn);	/* Single updater, expect dst==NULL. */
> +	rcu_assign_pointer(dst->spn, src->spn);
> +	src->spn = NULL;	/* Transfer ownership. */
> +}
> +
> +/*
> + * Copy sharedptr to a syncsharedptr, incrementing the reference.
> + */
> +static inline
> +void sharedptr_copy_to_sync(struct syncsharedptr *dst, const struct sharedptr *src)
> +{
> +	struct sharedptr_node *spn = src->spn;
> +
> +	WARN_ON_ONCE(dst->spn);	/* Single updater, expect dst==NULL. */
> +	if (spn)
> +		refcount_inc(&spn->refcount);
> +	rcu_assign_pointer(dst->spn, spn);
> +}
> +
> +/*
> + * Obtain a shared pointer copy from a syncsharedptr.
> + */
> +static inline
> +struct sharedptr sharedptr_copy_from_sync(const struct syncsharedptr *ssp)
> +{
> +	struct sharedptr_node *spn, *hp;
> +	struct hazptr_slot *slot;
> +	struct sharedptr sp;
> +
> +	preempt_disable();

Disabling preemption acts as an RCU read-side critical section, so I
guess the immediate question is why (or when) not use RCU ;-)

Regards,
Boqun

> +	hp = spn = hazptr_load_try_protect(&hazptr_domain_sharedptr, &ssp->spn, &slot);
> +	if (!spn)
> +		goto end;
> +	if (!refcount_inc_not_zero(&spn->refcount))
> +		spn = NULL;
> +	hazptr_release(slot, hp);
> +end:
> +	sp.spn = spn;
> +	preempt_enable();
> +	return sp;
> +}
> +
> +static inline
> +void syncsharedptr_delete(struct syncsharedptr *ssp,
> +			  void (*sharedptr_node_release)(struct sharedptr_node *spn))
> +{
> +	struct sharedptr_node *spn = ssp->spn;
> +
> +	if (!spn)
> +		return;
> +	WRITE_ONCE(ssp->spn, NULL);
> +	if (refcount_dec_and_test(&spn->refcount)) {
> +		hazptr_scan(&hazptr_domain_sharedptr, spn, NULL);
> +		sharedptr_node_release(spn);
> +	}
> +}
> +
> +static inline
> +void sharedptr_delete(struct sharedptr *sp,
> +		      void (*sharedptr_node_release)(struct sharedptr_node *spn))
> +{
> +	struct sharedptr_node *spn = sp->spn;
> +
> +	if (!spn)
> +		return;
> +	WRITE_ONCE(sp->spn, NULL);
> +	if (refcount_dec_and_test(&spn->refcount)) {
> +		hazptr_scan(&hazptr_domain_sharedptr, spn, NULL);
> +		sharedptr_node_release(spn);
> +	}
> +}
> +
> +#endif /* _LINUX_SHAREDPTR_H */
> diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> index 3f9f14afbf1d..ba772f020325 100644
> --- a/kernel/hazptr.c
> +++ b/kernel/hazptr.c
> @@ -8,6 +8,9 @@
>  #include <linux/hazptr.h>
>  #include <linux/percpu.h>
> +#include <linux/sharedptr.h>
> +
> +DEFINE_HAZPTR_DOMAIN(hazptr_domain_sharedptr);
>  /*
>   * hazptr_scan: Scan hazard pointer domain for @addr.
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com

Re: [RFC] Synchronized Shared Pointers for the Linux kernel

[Mathieu Desnoyers]

On 2024-10-11 01:11, Boqun Feng wrote:
> On Thu, Oct 10, 2024 at 03:16:25PM -0400, Mathieu Desnoyers wrote:
>> Hi,
>>
>> I've created a new API (sharedptr.h) for the use-case of
>> providing existence object guarantees (e.g. for Rust)
>> when dereferencing pointers which can be concurrently updated.
>> I call this "Synchronized Shared Pointers".
>>
>> This should be an elegant solution to Greg's refcount
>> existence use-case as well.
>>
>> The current implementation can be found here:
>>
>> https://github.com/compudj/linux-dev/commit/64c3756b88776fe534629c70f6a1d27fad27e9ba
>>
>> Patch added inline below for feedback.
>>
>> Thanks!
>>
>> Mathieu
>>

[...]

>> + */
>> +static inline
>> +struct sharedptr sharedptr_copy_from_sync(const struct syncsharedptr *ssp)
>> +{
>> +	struct sharedptr_node *spn, *hp;
>> +	struct hazptr_slot *slot;
>> +	struct sharedptr sp;
>> +
>> +	preempt_disable();
> 
> Disabling preemption acts as an RCU read-side critical section, so I
> guess the immediate question is why (or when) not use RCU ;-)

That's a very relevant question indeed! Why use hazard pointers rather
than RCU in this particular use-case ?

You are right that I could add a rcu_read_lock()/rcu_read_unlock()
around sharedptr_copy_from_sync(), and pair this with a call_rcu()
in node_release, which would effectively replace hazard pointers
by RCU.

Please keep in mind that the current implementation of this API
is minimalist. I mean to extend this, and this is where the benefits
of hazard pointers over RCU should become clearer:

1) With hazard pointers, AFAIU we can modify the sharedptr_delete
    and syncsharedptr_delete to issue hazptr_scan() _before_
    decrementing to 0, e.g.

       unsigned int old, new;

       WRITE_ONCE(sp->spn, NULL);
       old = spn->refcount;
       do {
               new = old - 1;
               if (!new)
                       hazptr_scan(&hazptr_domain_sharedptr, spn, NULL);
       } while (!atomic_try_cmpxchg(&spn->refcount->refs, &old, new);
       if (!new)
               sharedptr_node_release(spn);

    And therefore modify sharedptr_copy_from_sync to use a refcount_inc
    rather than a refcount_inc_not_zero, because the reference count
    can never be 0 while a hazard pointer to the object exists.

    This modification would make hazard pointers act as if they
    *are* holding a reference count on the object.

This improvement brings us to a more important benefit:

2) If we increase the number of available hazptr slots per cpu
    (e.g. to 8 or more), then we can start using hazard pointers as
    reference counter replacement (fast-path).

    This will allow introducing a new type of sharedptr object, which
    could be named "thread sharedptr", meant to hold a reference for a
    relatively short period of time, on a single thread, where the thread
    is still allowed to be preempted or block while holding the thread
    sharedptr.

    The per-cpu hazard pointer slots would point to per-thread sharedptr
    structures, which would hold the protected hazard pointer slot.

    When the application means to keep the reference for longer,
    to store it into a data structure or pass it around to another
    thread, then it should copy the thread-sharedptr to a normal
    sharedptr, which will make sure a reference is taken on the
    object.

    The thread sharedptr is tied to the thread using it. Because the
    hazard pointer context would be in a well-defined per-thread area
    (rather than just on the stack), we can do the following when
    scanning for hazard pointers: force the thread sharedptr to promote
    to a reference counter increment on the object, thus allowing the
    hazard pointer scan to progress. This allows freeing up the per-cpu
    slot immediately.

    If all per-cpu hazard pointer slots are used, the thread sharedptr
    would automatically fall-back to reference counter.

    We could even add a per-cpu timer which would track how old are each
    per-CPU hazard pointer slots, and promote them to a reference counter
    increment based on their age if needed.

This would effectively allow implementing a "per-thread shared pointer"
fast-path, which would scale better than just reference counters on large
multi-core systems.

Thanks,

Mathieu

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