Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

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

Hi Jonas,

On Fri, Sep 20, 2024 at 09:41:15AM +0200, Jonas Oberhauser wrote:
> 
> 
> Am 9/17/2024 um 4:33 PM schrieb Boqun Feng:
> > +static inline void *__hazptr_tryprotect(hazptr_t *hzp,
> > +					void *const *p,
> > +					unsigned long head_offset)
> > +{
> > +	void *ptr;
> > +	struct callback_head *head;
> > +
> > +	ptr = READ_ONCE(*p);
> > +
> > +	if (ptr == NULL)
> > +		return NULL;
> > +
> > +	head = (struct callback_head *)(ptr + head_offset);
> > +
> > +	WRITE_ONCE(*hzp, head);
> > +	smp_mb();
> > +
> > +	ptr = READ_ONCE(*p); // read again
> > +
> > +	if (ptr + head_offset != head) { // pointer changed
> > +		WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
> > +		return NULL;
> > +	} else
> > +		return ptr;
> > +}
> 
> There is a subtle potential for ABA issues here.
> 
> If the compiler replaces 'return ptr;' with 'return head - head_offset;',
> then you do not have an address dependency from the second read.
> 
> In this case, in ABA, the first read can read from a stale store, then the
> second read reads the same value from a newer store but only establishes
> control-dependency based synchronization with that store; any reads from
> *ptr could be speculatively executed before doing the second ptr =
> READ_ONCE(*p).
> 
> Therefore you could read the object state before it is properly
> reinitialized by the second store.
> 

Thanks for taking a look, and nice find!

> I'm not sure what the most efficient fix is or if you just want to gamble
> that "the compiler will never do that".
> I guess either READ_ONCE(ptr) or a compiler barrier before return ptr might
> do it?
> 

I think the root cause of this is that compiler can replace 'ptr' with
'head - head_offset' based on pointer value comparison. A fix would be
converting pointer to unsigned long and doing the comparison:

	if ((unsigned long)ptr + head_offset != (unsigned long)head) {
		WRITE_ONCE(*hzp, NULL);
		return NULL;
	} else
		return ptr;

because of the conversion, compilers lose the information of pointer
equality, therefore cannot replace 'ptr' with 'head - head_offset'. Of
course, if we are really worried about compilers being too "smart", we
can always do the comparison in asm code, then compilers don't know
anything of the equality between 'ptr' and 'head - head_offset'.

Regards,
boqun

> Have fun,
>    jonas
>