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

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

On 2024-10-03 02:24, Boqun Feng wrote:
> On Tue, Oct 01, 2024 at 09:02:04PM -0400, Mathieu Desnoyers wrote:
[...]
>> +/*
>> + * hp_allocate: Allocate a hazard pointer.
>> + *
>> + * Allocate a hazard pointer slot for @addr. The object existence should
>> + * be guaranteed by the caller.
>> + *
>> + * Returns a hazard pointer context.
>> + */
>> +static inline
>> +struct hp_ctx hp_allocate(struct hp_slot __percpu *percpu_slots, void *addr)
>> +{
>> +	struct hp_slot *slot;
>> +	struct hp_ctx ctx;
>> +
>> +	if (!addr)
>> +		goto fail;
>> +	slot = this_cpu_ptr(percpu_slots);
> 
> Are you assuming this is called with preemption disabled? Otherwise,
> there could two threads picking up the same hazard pointer slot on one
> CPU,

Indeed, this minimalist implementation only covers the preempt-off
use-case, where there is a single use of HP per CPU at any given
time (e.g. for the lazy mm use-case). It expects to be called
from preempt-off context. I will update the comment accordingly.

> 
>> +	/*
>> +	 * A single hazard pointer slot per CPU is available currently.
>> +	 * Other hazard pointer domains can eventually have a different
>> +	 * configuration.
>> +	 */
>> +	if (READ_ONCE(slot->addr))
>> +		goto fail;
> 
> .. and they could both read an empty slot, and both think they
> successfully protect the objects, which could be different objects.
> 
> Or am I missing something subtle here?

You are correct, I should document this.

> 
>> +	WRITE_ONCE(slot->addr, addr);	/* Store B */
>> +	ctx.slot = slot;
>> +	ctx.addr = addr;
>> +	return ctx;
>> +
>> +fail:
>> +	ctx.slot = NULL;
>> +	ctx.addr = NULL;
>> +	return ctx;
>> +}
>> +
>> +/*
>> + * hp_dereference_allocate: Dereference and allocate a hazard pointer.
>> + *
>> + * Returns a hazard pointer context.
>> + */
>> +static inline
>> +struct hp_ctx hp_dereference_allocate(struct hp_slot __percpu *percpu_slots, void * const * addr_p)
>> +{
>> +	struct hp_slot *slot;
>> +	void *addr, *addr2;
>> +	struct hp_ctx ctx;
>> +
>> +	addr = READ_ONCE(*addr_p);
>> +retry:
>> +	ctx = hp_allocate(percpu_slots, addr);
>> +	if (!hp_ctx_addr(ctx))
>> +		goto fail;
>> +	/* Memory ordering: Store B before Load A. */
>> +	smp_mb();
>> +	/*
>> +	 * Use RCU dereference without lockdep checks, because
>> +	 * lockdep is not aware of HP guarantees.
>> +	 */
>> +	addr2 = rcu_access_pointer(*addr_p);	/* Load A */
> 
> Why rcu_access_pointer() instead of READ_ONCE()? Because you want to
> mark the head of address dependency?

Yes, the intent here is to mark the address dependency and provide
a publication guarantee similar to RCU pairing rcu_assign_pointer
and rcu_dereference. Do you see any reason why READ_ONCE() would
suffice here ?

Thanks,

Mathieu


> 
> Regards,
> Boqun
> 
>> +	/*
>> +	 * If @addr_p content has changed since the first load,
>> +	 * clear the hazard pointer and try again.
>> +	 */
>> +	if (!ptr_eq(addr2, addr)) {
>> +		WRITE_ONCE(slot->addr, NULL);
>> +		if (!addr2)
>> +			goto fail;
>> +		addr = addr2;
>> +		goto retry;
>> +	}
>> +	ctx.slot = slot;
>> +	ctx.addr = addr2;
>> +	return ctx;
>> +
>> +fail:
>> +	ctx.slot = NULL;
>> +	ctx.addr = NULL;
>> +	return ctx;
>> +}
>> +
> [...]

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