Based on my reading of the Go memory model, this algorithm sketch is
memory-race free. However, there is a race condition. Here's the reason:
The writer issues a synchronized-write to array pointer, and another
synchronized-write to the array len. A reader issues a synchronized read.
the corresponding synchronized-write is synchronized-before this read, so
you get the address of an array. Then the reader issues a synchronized-read
of the array len. The synchronized-write for the array len is synchronized
before this read. However, there is no guarantee that the array length you
read is the length corresponding to the array read at the first step. So
this is the race condition, and you can fix it by atomically writing a
struct that has both array pointer and len in it. You have to
synchronized-read the struct, and synchronized-read the array len after
that. There is no need for a synchronized-read of array pointer, provided
you set it in the writer before synchronized-write of the struct pointer.
That is:
var arr atomic.Value
arrPtr:=&someStruct{array:a, len:0}
arr.Store(arrPtr)
For the second part of your question: the go memory model guarantees that
non-synchronized stores before a synchronized write happen before
non-synchronized reads after the synchronized read corresponding to that
synchronized write. This is because:
"The happens before relation is defined as the transitive closure of the
union of the sequenced before and synchronized before relations."
So: if A is synchronized before B, A happens before B. If A is
sequenced-before B, a happens-before B. Thus, if A is sequenced-before B,
and B is synchronized-before C, and C is synchronized-before D, then A
happens before D.
Of course, I'd appreciate it if someone from the Go team could verify this.
On Sun, Oct 30, 2022 at 7:28 AM Konstantin Khomoutov <kos...@bswap.ru>
wrote:
> Hi!
>
> I would like to receive clarifications, if possible, on Go memory model
> guarantees about non-atomic load and stores when intermixed with atomic
> load
> and stores.
>
> I'm reviewing a piece of code which, simplified, works as follows:
>
> - There is a single "writer" goroutine which
>
> - Allocates a new array, then uses sync/atomic.StorePointer to save the
> address of this array someplace.
>
> - Writes the array elements one by one.
> After writing each element it - again atomically - updates some
> memory
> location which contains the number of elements currently written in
> the
> array.
>
> - When the array fills up, it repeats the routine.
>
> A point to note is that the writer writes each element only once,
> and after it's done with the array, it never touches this array again.
>
> - There are multiple "reader" goroutines each of which consumes the data
> being updated by the "writer" in the following way:
>
> - Use sync/atomic.LoadPointer to obtain the address of the array
> currently
> in use by the "writer" goroutine.
>
> - Atomically read the current number of elements written in the array
> by the "writer" goroutine and then read that many elements
> from the array.
>
> My problem is that I fail to properly apply the text of the Go memory model
> to this case to figure out if there is still a data race on the elements
> of these arrays between the writer and the readers.
>
> The chief problem I have with my reasoning is that I fail to understand
> whether the sequenced-before guarantees provided by atomics apply only to
> the
> atomic operations theirselves - and the memory locations they operate on -
> or
> to the whole sequences of statements executed by goroutines which perform
> the atomic operations.
>
> To simplify, and given the description of the algorithm above, I apply the
> following reasoning.
> A goroutine A performs multiple non-synchronized stores to memory
> locations X,
> Y and Z, and then performs atomic store into memory location M. Naturally,
> all
> store operations done on A up to and including the atomic store to M, are
> naturally sequenced - all the non-synchronized stores has happened before
> the
> atomic store.
> Now a goroutine B uses atomic load of memory location M and then
> performs multiple non-synchronized memory loads from memory locations X, Y
> and Z. These non-synchronized loads are naturally sequenced after the
> atomic
> load from M.
> ("Naturally sequenced" means it's just a regular program flow within a
> goroutine.)
> Given the above, is it guaranteed that A's stores to X, Y and Z are
> synchronized-before B's loads from X, Y and Z?
>
> My gut feeling is that no, Go does not provide this guarantee because of
> two
> reasons:
>
> - The store performed by A to M does not depend on stores to X, Y and Z,
> and the compiler and/or the hardware are free to reorder them.
>
> - An atomic store operation is not required to perform a full memory
> fence,
> so even if no reordering has happened on any layer, the goroutine B
> can still obtain stale data from the CPU cache.
>
> Hence I came to the conclusion that theoretically the code described above
> is
> still prone to data races on the elements of the arrays.
>
> On the other hand, a sample program implementing the algorithm described
> above
> compiled with -race does not fail (8-core i7-8550U, linux/amd64, Go
> 1.17.13;
> also tried other versions). I know that the race detector does only have no
> false positives, but the possibility to detect a particular data race
> heavily
> depends on the hardware and relative timings of the operations in a running
> program, so the fact it does not see the data race here does not prove it
> is
> not possible.
>
> So, can anyone please help me analyze this case?
>
> (Well, I also should admit the real code is more complicated than that but
> the
> basic idea still holds: the implementor has tries to use atomics in the way
> presented in the algorithm described.)
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/20221030132816.zrmrqxucsc2rf7ou%40carbon
> .
>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/CAMV2RqqrUysYR6E%3DMrVEup-Dbn%3Drkn%2B4Ux050AV6xerTinx1%2BA%40mail.gmail.com.
