Re: [RFC PATCH v2 3/4] hp: Implement Hazard Pointers

[Mathieu Desnoyers]

On 2024-10-05 13:19, Frederic Weisbecker wrote:
> Le Fri, Oct 04, 2024 at 02:27:33PM -0400, Mathieu Desnoyers a écrit :
> > +void hp_scan(struct hp_slot __percpu *percpu_slots, void *addr,
> > +	     void (*retire_cb)(int cpu, struct hp_slot *slot, void *addr))
> > +{
> > +	int cpu;
> > +
> > +	/*
> > +	 * Store A precedes hp_scan(): it unpublishes addr (sets it to
> > +	 * NULL or to a different value), and thus hides it from hazard
> > +	 * pointer readers.
> > +	 */
> > +
> > +	if (!addr)
> > +		return;
> > +	/* Memory ordering: Store A before Load B. */
> > +	smp_mb();
> > +	/* Scan all CPUs slots. */
> > +	for_each_possible_cpu(cpu) {
> > +		struct hp_slot *slot = per_cpu_ptr(percpu_slots, cpu);
> > +
> > +		if (retire_cb && smp_load_acquire(&slot->addr) == addr)	/* Load B */
> > +			retire_cb(cpu, slot, addr);
> > +		/* Busy-wait if node is found. */
> > +		while ((smp_load_acquire(&slot->addr)) == addr)	/* Load B */
> > +			cpu_relax();
>
> You agree that having a single possible per-cpu pointer per context and a busy
> waiting update side pointer release can't be a general purpose hazard pointer
> implementation, right? :-)

Of course. This is a minimalist implementation, which can be extended in
various ways, some of which I've implemented as POC in userspace already:

- Increase the number of per-cpu slots available,
- Distinguish between current scan depth target and available
  per-cpu slots,
- Fall-back to reference counter when slots are full,
- Allow scanning for a range of addresses (useful for type-safe
  memory),
- Allow scanning for a set of hazard pointers (scan batching)
  using Bloom filters to probabilistically speed up the comparison
  (not implemented yet).
- Implement a queued blocking wait/wakeup when HP scan must wait
  (not implemented yet).
- Implement a HP-to-refcount promotion triggered by the HP scan
  callback to promote hazard pointers which would be blocked on
  to a reference count increment. (not implemented yet)
- Use hazard pointers + refcount to implement smart pointers, which
  could be useful for Rust. (not implemented yet)

But my general approach is to wait until the use-cases justify adding
features.

Although if you are curious about any of the points listed above,
just ask and I'll be happy to discuss them in more depth.

Thanks,

Mathieu

> Thanks.
>
> > +	}
> > +}
> > --
> > 2.39.2

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