Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

doc: define how sync/atomic interacts with memory model #5045

Closed
rsc opened this issue Mar 13, 2013 · 79 comments
Closed

doc: define how sync/atomic interacts with memory model #5045

rsc opened this issue Mar 13, 2013 · 79 comments
Assignees
Labels
FrozenDueToAge NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Milestone

Comments

@rsc
Copy link
Contributor

rsc commented Mar 13, 2013

Neither golang.org/ref/mem nor golang.org/pkg/sync/atomic say anything about what
guarantees are made by the atomic operations wrt the memory model. They should be as
weak as possible, of course, but right now they are non-existence, which is a little too
weak.

We might say, for example, that an atomic.Store writing a value to a memory location
happens before an atomic.Load that reads that value from the memory location. Is that
something we want to say? If not, what do we want to say?

What about Add?

What about CompareAndSwap?
@dvyukov
Copy link
Member

dvyukov commented Mar 14, 2013

Comment 1:

Why do you want them to be as weak as possible? Weak atomics are difficult to program.

@dvyukov
Copy link
Member

dvyukov commented Mar 14, 2013

Comment 2:

>We might say, for example, that an atomic.Store writing a value to a memory location
happens before an atomic.Load that reads that value from the memory location. Is that
something we want to say? If not, what do we want to say?
Yes, we want to say that.
Regarding Add/CAS, it should be formulated in in more general terms, along the lines of:
at atomic operation that stores a value (incl ADD/CAS) happens before atomic operation
that reads that value from the memory location (incl ADD/CAS).
However, this does not cover the Dekker synchronization pattern:
X = Y = 0
// goroutine 1
X = 1  // atomic
r1 = Y  // atomic
// goroutine 2
Y = 1  // atomic
r2 = X  // atomic
The rule above allows r1 == r2 == 0, however such outcome is impossible under sequential
consistency (total order).
Dekker pattern is used in tricky mutual exclusion algorithms and in safe object
reclamation schemes. On one hand it's used very infrequently, but on the other hand
there will be no way to implement it at all. That's why I am asking about "as weak as
possible".

@rsc
Copy link
Contributor Author

rsc commented Mar 14, 2013

Comment 3:

Let me amend my earlier statement: I want them to be as weak as possible
but still useful, like the current memory model is very weak compared to
what other languages have to say about the topic, but it's still useful.

@dvyukov
Copy link
Member

dvyukov commented Mar 15, 2013

Comment 4:

Current chan semantics are complete wrt the problem the solve.
Atomics won't be complete if they provide weak synchronization guarantees, i.e. some
problems will be unsolvable.
Moreover, sequential consistency is the simplest to specify (C/C++ complexity comes from
exactly weak atomics -- possible reorderings, data dependencies, etc).
Moreover, sequential consistency is easy to understand and explain (remember the recent
discussion and confusion about chan-based semaphores, and the Effective Go example was
incorrect for several years).

@rsc
Copy link
Contributor Author

rsc commented Mar 15, 2013

Comment 5:

I think we are using different meanings for the word weak. You have a very
precise meaning in mind. I do not. I just mean "let's not guarantee more
than we need to guarantee to make things useful for people." That's a
general goal, not a concrete proposal.
Dmitriy, if you have time, could you please make a proposal about what you
think the atomics should guarantee? A few sentences here in the issue is
fine.
Thanks.
Russ

@robpike
Copy link
Contributor

robpike commented May 18, 2013

Comment 6:

Labels changed: added go1.2maybe, removed go1.1maybe.

@dvyukov
Copy link
Member

dvyukov commented Jul 30, 2013

Comment 7:

Please clarify more on your meaning of "weak".
The problem with atomic operations is that they are lower level that chans. There are
lots of practically useful things that are possible to build using atomics.
So what do you want to specify:
1. Semantics for majority of simpler use cases (say 95%), and leave the remaining cases
unspecified for now.
or 2. Semantics for all practically useful cases.
I would vote for 2, because sooner or later somebody will ask about the remaining 5% and
answer "you can rely on X guarantee, but we do not want to officially guarantee it" does
not look good. (btw we use that remaining 5% in e.g. WaitGroup).
And 2 is extremely strong, it's not weak in any possible sense of this word.

@rsc
Copy link
Contributor Author

rsc commented Jul 31, 2013

Comment 8:

I mean 1, especially if the semantics can be kept to a minumum.
No, that is not the answer. The answer is "if it is not in the memory model
you must not depend on it." If that's still true once we have defined the
semantics, we should rewrite WaitGroup.
I asked you to write a few sentences sketching the semantics you want, but
you haven't done that.

@dvyukov
Copy link
Member

dvyukov commented Aug 8, 2013

Comment 9:

The minimal semantics must be along the lines of:
"If an atomic operation A observes a side effect of an atomic operation B, then A
happens before B".
That's basically it.
Note that not only Load can observe the side effect. Return value from Add and
CompareAndSwap also allows in infer which side effect we observe. Read-modify-write
operations (Add, CAS) first observe side effect of a previous operation on the same var,
and then produce a new side effect. I imply that there is a total order Mv over all
atomic operations that mutate atomic variable V.
Such definition supports use cases like producer-consumer, object publication, etc.
However, such definition does not support trickier synchronization patterns. And frankly
I would not want to rewrite any existing synchronization primitives due to this. In
runtime we a dozen of such "unsupported" cases, I understand that that's different
atomics, but I just want to show that such use cases exist.
Semantics that cover all synchronization patterns would be along the lines of:
"There is a total order S over all atomic operations (that is consistent with
modification orders M of individual atomic variables, happen-before relations,
bla-bla-bla). An atomic operation A happens after all atomic operations that precede A
in S".
The trick here is that you usually can not infer S (w/o any pre-existing happens-before
relations). The only (?) cases where you can infer a useful information from S are:
1. When atomic operations A and B operate on the same var, and this makes this
definition a superset of the first definition (S is consistent with all Mv).
2. When it's enough to know that either A happens-before B or vise versa (this is true
for any pair of atomic operations due to total order S).

@dvyukov
Copy link
Member

dvyukov commented Aug 8, 2013

Comment 10:

>"If an atomic operation A observes a side effect of an atomic operation B, then A
happens before B"
s/A happens before B/B happens before A/

@rsc
Copy link
Contributor Author

rsc commented Aug 13, 2013

Comment 11:

How about this:
"Package sync/atomic provides access to individual atomic operations. These atomic
operations never happen simultaneously. That is, for any two atomic operations e1 and
e2, either e1 happens before e2 or e2 happens before e1, even if e1 and e2 operate on
different memory locations."
Is that a good idea? Is it too strong? Is it more than we need, less than we need? Is it
going to be too hard to guarantee on systems like Alpha? I don't know. But at least it
is simple and I understand what it is saying. That's different than understanding all
the implications.

@dvyukov
Copy link
Member

dvyukov commented Aug 14, 2013

Comment 12:

As per offline discussion, your "either e1 happens before e2 or e2 happens before e1"
definition looks good if data races are prohibited. Otherwise, racy accesses allow to
infer weird relations, e.g. that a Load happens-before a Store:
// thread 1
x = 1
atomic.Load(&whatever)
y = 1
// thread 2
if y == 1 {
  atomic.Store(&whatever2)
  println(x) // must print 1
}
This means that Load must execute release memory barrier and store -- acquire memory
barrier. Most likely this will make implementations of atomic operations costlier.

@rsc
Copy link
Contributor Author

rsc commented Aug 14, 2013

Comment 13:

Okay, maybe that's a bad definition then (I was just rephrasing yours, I
believe). It sounds like it is too strong. Are loads and stores the only
problem. Is this any better?
"""
Package sync/atomic provides access to individual atomic operations. For
any two atomic operations e1 and e2 operating on the same address:
  - if e1 is not a Load, e2 is a Load, and e2 observes the effect of e1, e1
happens before e2.
  - if e1 is a Store, e2 is not a Store, and e2 observes the effect of e1,
e1 happens before e2.
  - if neither operation is a Load or Store, either e1 happens before e2 or
e2 happens before e1.
"""

@dvyukov
Copy link
Member

dvyukov commented Aug 15, 2013

Comment 14:

Why don't you want to give up on data races?
We probably can ensure atomicity of word accesses in gc w/o sacrificing important
optimizations. But:
1. We can not ensure visibility guarantess, e.g. if a var is registrized in a loop, and
at this point racy accesses become almost useless.
2. Races are definitely not safe for maps and slices.
3. Most likely we can not ensure any guarantees for races in gccgo (not sure what gcc
java does here).
4. I do not see any benefits of allowing data races. Currently there is runtime cost for
calling atomic.Load instead of doing plain load. But this must be addresses by providing
better atomic operations with compiler support (if that becomes the bottleneck).
Allowing data races instead to solve this looks completely wrong.
If we prohibit data races, it would make reasoning about atomic operations much much
simpler.

@dvyukov
Copy link
Member

dvyukov commented Aug 15, 2013

Comment 15:

There are 2 litmus tests for atomic operations:
1.
// goroutine 1
data = 42
atomic.Store(&ready, 1)
// goroutine 2
if atomic.Load(&ready) {
  if data != 42 {
    panic("broken")
  }
}
2.
// goroutine 1
atomic.Store(&X, 1)
r1 = atomic.Load(&Y)
// goroutine 2
atomic.Store(&Y, 1)
r2 = atomic.Load(&X)
// afterwards
if r1 == 0 && r2 == 0 {
  panic("broken")
}
As far as I see you definition does not work for 2.

@dvyukov
Copy link
Member

dvyukov commented Aug 15, 2013

Comment 16:

For 2 to work, atomic operations (including loads and stores) must form total order.
Probably the following 2 clause definition can do:
(1) If an atomic operation A observes an effect of an atomic operation B, then B happens
before A.
(2) All atomic operations form a total order that is consistent with happens-before
relations, modification orders of individual atomic variables and intra-goroutine order
of operations.
(2) implies that values returned by atomic operations and their side effects are
dictated by the total order. I am not sure whether it's obvious or not.
Note that (2) does not introduce new happens-before relations. Even if you somehow infer
that A precedes B in total order (e.g. by using racy memory accesses), this gives you
nothing.

@rsc
Copy link
Contributor Author

rsc commented Aug 15, 2013

Comment 17:

You wrote "why don't you want to give up on data races?". That's not what I
am trying to do. I am trying to avoid making atomic.Load and atomic.Store
unnecessarily expensive.

@dvyukov
Copy link
Member

dvyukov commented Aug 15, 2013

Comment 18:

It is more difficult to do in presence of data races.
W/o data races the following looks OK:
"Package sync/atomic provides access to individual atomic operations. These atomic
operations never happen simultaneously. That is, for any two atomic operations e1 and
e2, either e1 happens before e2 or e2 happens before e1, even if e1 and e2 operate on
different memory locations."

@rsc
Copy link
Contributor Author

rsc commented Aug 15, 2013

Comment 19:

Okay, then define how to prohibit data races.

@dvyukov
Copy link
Member

dvyukov commented Aug 15, 2013

Comment 20:

It's simple. We need to replace:
--------------------------
To guarantee that a read r of a variable v observes a particular write w to v, ensure
that w is the only write r is allowed to observe. That is, r is guaranteed to observe w
if both of the following hold:
w happens before r.
Any other write to the shared variable v either happens before w or after r.
This pair of conditions is stronger than the first pair; it requires that there are no
other writes happening concurrently with w or r.
Within a single goroutine, there is no concurrency, so the two definitions are
equivalent: a read r observes the value written by the most recent write w to v. When
multiple goroutines access a shared variable v, they must use synchronization events to
establish happens-before conditions that ensure reads observe the desired writes.
The initialization of variable v with the zero value for v's type behaves as a write in
the memory model.
Reads and writes of values larger than a single machine word behave as multiple
machine-word-sized operations in an unspecified order.
--------------------------
with:
--------------------------
If there is more than one such w, the behavior is undefined.
The initialization of variable v with the zero value for v's type behaves as a write in
the memory model.
--------------------------

@robpike
Copy link
Contributor

robpike commented Aug 20, 2013

Comment 21:

Is this converging?

@dvyukov
Copy link
Member

dvyukov commented Aug 20, 2013

Comment 22:

Difficult to say. I would not hurry with this. Moving to 1.3.

Labels changed: added go1.3, removed go1.2maybe.

@robpike
Copy link
Contributor

robpike commented Aug 20, 2013

Comment 23:

Labels changed: removed go1.3.

@rsc
Copy link
Contributor Author

rsc commented Nov 27, 2013

Comment 24:

Labels changed: added go1.3maybe.

@rsc
Copy link
Contributor Author

rsc commented Dec 4, 2013

Comment 25:

Labels changed: added release-none, removed go1.3maybe.

@rsc
Copy link
Contributor Author

rsc commented Dec 4, 2013

Comment 26:

Labels changed: added repo-main.

@robaho
Copy link

robaho commented Nov 16, 2019 via email

@zhiqiangxu
Copy link
Contributor

zhiqiangxu commented Dec 14, 2019

I agree with @eloff , we should let all users know that all exposed functions in sync/atomic guarantee sequential consistency, not only known in the go team(eg, #32428 (comment) and https://stackoverflow.com/a/58892365/3382012), unless one day we decide to expose atomic.LoadAcq/atomic.StoreRel or alike , by that time we can add additional document for these functions though. It has been pending for 6 years, time to make a change:)

@eloff
Copy link

eloff commented Dec 22, 2019

@robaho I'm referring to the C++ atomics happens-before ordering when talking about consistency. The docs can either point one to the C++ docs for the happens-before wording, or copy it.

Since there's no movement on this, I'm going to sign the contrib agreement and submit a pull-request.

@bcmills
Copy link
Contributor

bcmills commented May 5, 2020

Here's a neat question that needs to be resolved: are programs allowed to use 32-bit atomic ops concurrently with 64-bit atomic ops on the same memory?

For example, is this program racy?

	var x uint64
	xa := (*[2]uint32)(unsafe.Pointer(&x))
	xl := &xa[0]
	xh := &xa[1]

	done := make(chan struct{})
	go func() {
		atomic.StoreUint64(&x, 0xbadc0ffee)
		close(done)
	}()

	x0 := atomic.LoadUint32(xl)
	x1 := atomic.LoadUint32(xh)

	<-done

My instinct is that this sort of size-mixing must not be allowed, because the implementations for 32-bit and 64-bit atomic ops may differ on some 32-bit hardware. However, the race detector does not currently flag it.

@yangwenmai
Copy link
Contributor

yangwenmai commented Jul 10, 2020

specific lock free algorithm used by prometheus

Would be interesting in watching this talk, do you know if there is a video anywhere?

@nhooyr
GopherCon UK 2019: Björn Rabenstein - Lock-free Observations for Prometheus Histograms

https://youtu.be/VmrEG-3bWyM

@leventov
Copy link

Currently, the usage examples of atomic.Value are unsound without defining the happens-before relationships between Store() and Load().

@chrisprobst
Copy link

chrisprobst commented Dec 3, 2020

My team just learned about this issue and we are using atomics for years. Are there at least any guarantees or is using atomics always undefined behavior in Go?

@ianlancetaylor
Copy link
Contributor

Pedantically, when talking about things like memory models "undefined behavior" means that any random bug can happen (https://en.wikipedia.org/wiki/Undefined_behavior). That isn't the case here. Go is always going to do some approximation of the right thing.

There has been a lot of discussion on this issue. The general goal here remains #5045 (comment) . But the precise details and wording remain open.

@ghost
Copy link

ghost commented Jan 4, 2022

Can we just add "Go's atomics guarantee sequential consistency among the atomic variables (behave like C/C++'s seqconst atomics). You shouldn't mix atomic and non-atomic accesses for a given memory word, unless some other full memory barrier, like a Mutex, guarantees exclusive access. You shouldn't mix atomics of different memory sizes for the same address."

This is merely anecdote, but in my experience (full-time go developer >5y), the users of atomics assume sequential consistent ordering. I sure know I did!

@btiernay
Copy link

Any movement on this issue in the last year, or is this now being covered by #47141?

@ianlancetaylor
Copy link
Contributor

I think this is now covered by #50859.

@ianlancetaylor
Copy link
Contributor

This was done by https://go.dev/cl/381315.

@robaho
Copy link

robaho commented Jul 18, 2022

Woo Hoo ! Just sneaked in under the 10 year mark!

@golang golang locked and limited conversation to collaborators Jul 18, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Projects
No open projects
Development

No branches or pull requests