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

[Boqun Feng <boqun.feng@gmail.com>]

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