Re: Help needed for glibc software transaction memory algorithm

[Szabolcs Nagy <szabolcs.nagy@arm.com>]

The 01/04/2022 15:12, Florian Weimer via Libc-alpha wrote:
> I've tried to implement a software transactional memory algorithm
> 
> The characteristics are:
> 
> * Single writer, multiple readers.
> 
> * Two copies of the data.
> 
> * A 64-bit version counter tracks modifications.  The lowest bit of the
>   counter tells the reader which copy of the data to read.
> 
> * The writer increments the counter by 2, modifies the STM-protected
>   data, and increments the counter by 1.
> 
> * The reader loads the counter, reads the STM-protected data, loads the
>   counter for a second time, and retries if the counter does not match.
> 
> I've attached a model implementation.  The glibc implementation has a
> wrapper around the counter updates to support 32-bit implementations as
> well.  In both implementations, the writer uses release MO stores for
> the version update, and the reader uses acquire MO loads.  The stores
> and loads of the STM data itself are unordered (not even volatile).
> 
> It turns out that this does not work: In the reader, loads of the
> STM-protected data can be reordered past the final acquire MO load of
> the STM version.  As a result, the reader can observe incoherent data.
> In practice, I only saw this on powerpc64le, where the *compiler*
> performed the reordering:
> 
>   _dl_find_object miscompilation on powerpc64le
>   <https://sourceware.org/bugzilla/show_bug.cgi?id=28745>
> 
> Emprically, my stm.c model does not exhibit this behavior.
> 
> To fix this, I think it is sufficient to add a release fence just before
> the second version load in the reader.  However, from a C memory model
> perspective, I don't quite see what this fence would synchronize
> with. 8-/  And of course once there is one concurrency bug, there might
> be others as well.  Do I need to change the writer to use
> acquire-release MO for the version updates?
> 
> I think there should be a canned recipe for this scenario (single
> writer, two data copies), but I couldn't find one.

this reminds me the discussion in section 4 and 5 of

https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf

there are no 2 data copies here but i think the reasoning
about the synchronization may apply.