Atomic pointers to arrays and sequenced-before guarantees for array elements

[Konstantin Khomoutov]

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.)

[jake...@gmail.com]

I would like to give you a definitive answer, but the same question comes up in https://groups.google.com/g/golang-nuts/c/Gze1TRtdLdc/ and there is much disagreement and no clear resolution. (The initial question is not exactly yours, but if I understand correctly, the discussion quickly gets simplified to exactly yours.) So unless someone from the go team is willing to clarify, all you are getting are varying options. Of course, read the thread yourself and maybe you will believe one side was correct.

Reading your description, I am also concerned that you could have a logical race. Its possible you already account for this, but if you are setting the 'array pointer' atomically and separately setting the 'count' atomically, the there could be cases where readers read a count not matching the current array. There are many simple fixes, and you hopefully have already taken this into account, but I just wanted to mention it.

[burak serdar]

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.

--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/20221030132816.zrmrqxucsc2rf7ou%40carbon.

[Konstantin Khomoutov]

On Sun, Oct 30, 2022 at 08:47:41AM -0700, jake...@gmail.com wrote:

> I would like to give you a definitive answer, but the same question comes
> up in https://groups.google.com/g/golang-nuts/c/Gze1TRtdLdc/ and there is
> much disagreement and no clear resolution. (The initial question is not
> exactly yours, but if I understand correctly, the discussion quickly gets

> simplified to exactly yours.) So unless *someone from the go team is
> willing to clarify,* all you are getting are varying options. Of course,

> read the thread yourself and maybe you will believe one side was correct.

Thank you!
Somehow I missed that thread, and it is indeed very close to my situation.
An very interesting read - though not quite satisfying, alas ;-)

> Reading your description, I am also concerned that you could have a logical
> race. Its possible you already account for this, but if you are setting the
> 'array pointer' atomically and separately setting the 'count' atomically,
> the there could be cases where readers read a count not matching the
> current array. There are many simple fixes, and you hopefully have already
> taken this into account, but I just wanted to mention it.

Again, thanks!
Yes, there is a logical race, but in the real code the variable holding the
address of an array is written only once: the writer goroutine actually grows
a linked list, and the "active" array is the list's tail - in the same
compound variable with its length. So I _thought_ that any reader who managed
to get to the list's tail had no way reading the length from a different
array. (Trying to explain the whole construction I'm dealing with would
supposedly made it impenetrable for the readers so I've tried to simplify the
things as much as possible.)

[Keith Randall]

> 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?

Yes. The writes of X, Y, and Z are sequenced before the atomic write to M, the atomic write to M is synchronized before the atomic read of M (assuming the read returns the result of that write), and the atomic read of M is sequenced before the reads of X,Y, and Z. Thus the writes of X, Y, and Z happen before the reads of X, Y, and Z in your example.