CC @dvyukov

Looks like we started promising sequential consistent behavior in https://go-review.googlesource.com/c/go/+/381316 (~ 1 year ago, released first in 1.19), but we didn't verify that we actually provided that, as far as I can tell. @rsc

Probably the right fix is to fix the tsan library to use mo_acq_rel for the __tsan_go_atomic64_store versions.

But an easier, quicker fix is just to use the _exchange tsan operations to implement the Go Store operations. Especially for backport to 1.19 and the soon-to-be-released 1.20, that's an easier, safer fix.

Change https://go.dev/cl/463227 mentions this issue: runtime: fix sequential consistency of sync/atomic.Store* when in race mode

I have a CL out to fix this immediate problem. I'm not sure we're really covered completely, though. For instance atomic loads are marked acquire, not acquire+release. Will that lead to problems? The compare-and-swap ops are also dual-marked and one of the marks is acquire-only. Maybe that's for when the comparison fails?

What about other architectures? They may in fact be worse, as they tend to have looser default semantics.

How do we test this?

The good news is that this only matters to race mode, where performance doesn't matter much. We can drop big memory barrier hammers if we need to.

There are tests for sequential consistency, they run under race detector and don't fail, right?
https://github.com/golang/go/blob/master/src/sync/atomic/atomic_test.go#L2221-L2303
Besides mo_release there are at least 2 other Mutex lock/unlock operations. They also participate in synchronization. Have you accounted for these?

Yes, those tests pass.

That said, they also pass if I change the non-race code to use MOVQ instead of XCHGQ. So either we're currently using XCHGQ unnecessarily or our tests aren't very thorough. (Or maybe my processor provides more than minimal guarantees, hard to tell.)

I think we're going to need a test case from the OP. Without that, it is hard to be sure there is something wrong, and certainly hard to tell whether we've actually fixed it.

It should fail pretty reliably on a typical x86 CPU.
Here is what I did:

atomic$ go test -run=TestStoreLoadSeqCst64 -count=1000 
PASS
ok  	sync/atomic	0.273s

atomic$ go test -run=TestStoreLoadSeqCst64 -count=1000 -race
PASS
ok  	sync/atomic	1.507s

Then (which should practically lead to MOVQ):

--- a/src/sync/atomic/atomic_test.go
+++ b/src/sync/atomic/atomic_test.go
@@ -2276,7 +2276,8 @@ func TestStoreLoadSeqCst64(t *testing.T) {
                        for i := int64(1); i < N; i++ {
-                               StoreInt64(&X[me], i)
+                               X[me] = i
                                my := LoadInt64(&X[he])

atomic$ go test -run=TestStoreLoadSeqCst64 -count=10
--- FAIL: TestStoreLoadSeqCst64 (0.00s)
    atomic_test.go:2294: store/load are not sequentially consistent: 27/27 (28)
    atomic_test.go:2294: store/load are not sequentially consistent: 27/27 (28)
--- FAIL: TestStoreLoadSeqCst64 (0.00s)
    atomic_test.go:2294: store/load are not sequentially consistent: 20/20 (21)
    atomic_test.go:2294: store/load are not sequentially consistent: 20/20 (21)
--- FAIL: TestStoreLoadSeqCst64 (0.00s)
    atomic_test.go:2294: store/load are not sequentially consistent: 11/11 (12)
    atomic_test.go:2294: store/load are not sequentially consistent: 11/11 (12)
--- FAIL: TestStoreLoadSeqCst64 (0.00s)
    atomic_test.go:2294: store/load are not sequentially consistent: 3/3 (4)
    atomic_test.go:2294: store/load are not sequentially consistent: 3/3 (4)
--- FAIL: TestStoreLoadSeqCst64 (0.00s)
    atomic_test.go:2294: store/load are not sequentially consistent: 45/45 (46)
    atomic_test.go:2294: store/load are not sequentially consistent: 45/45 (46)
--- FAIL: TestStoreLoadSeqCst64 (0.00s)
    atomic_test.go:2294: store/load are not sequentially consistent: 491/491 (492)
    atomic_test.go:2294: store/load are not sequentially consistent: 491/491 (492)
--- FAIL: TestStoreLoadSeqCst64 (0.00s)
    atomic_test.go:2294: store/load are not sequentially consistent: 2/2 (3)
    atomic_test.go:2294: store/load are not sequentially consistent: 2/2 (3)
FAIL

Hmm, I did this:

--- a/src/runtime/internal/atomic/atomic_amd64.s
+++ b/src/runtime/internal/atomic/atomic_amd64.s
@@ -171,7 +171,8 @@ TEXT ·Store8(SB), NOSPLIT, $0-9
 TEXT ·Store64(SB), NOSPLIT, $0-16
        MOVQ    ptr+0(FP), BX
        MOVQ    val+8(FP), AX
-       XCHGQ   AX, 0(BX)
+       MOVQ    AX, 0(BX)
+       //XCHGQ AX, 0(BX)
        RET

Maybe that code doesn't get used somehow? Semantic inlining somewhere, I suspect.

Yes, that'll be the reason. Need this patch:

--- a/src/cmd/compile/internal/ssagen/ssa.go
+++ b/src/cmd/compile/internal/ssagen/ssa.go
@@ -4085,7 +4085,7 @@ func InitTables() {
                sys.AMD64, sys.ARM64, sys.Loong64, sys.MIPS, sys.MIPS64, sys.PPC64, sys.RISCV64, sys.S390X)
        addF("runtime/internal/atomic", "Store64",
                func(s *state, n *ir.CallExpr, args []*ssa.Value) *ssa.Value {
-                       s.vars[memVar] = s.newValue3(ssa.OpAtomicStore64, types.TypeMem, args[0], args[1], s.mem())
+                       s.vars[memVar] = s.newValue3A(ssa.OpStore, types.TypeMem, types.Types[types.TINT64], args[0], args[1], s.mem())
                        return nil
                },

Then the sequential consistency tests in sync/atomic fail.

CC @golang/compiler @golang/runtime

Timed out in state WaitingForInfo. Closing.

(I am just a bot, though. Please speak up if this is a mistake or you have the requested information.)

This is still not fixed in Go 1.20.3 or gotip, and it appears that @randall77 and @dvyukov managed to verify the issue. Is there any further info you need me to provide?

We're going to need a test case. I do think the code looks not quite right, but @dvyukov disagrees. We have tests for sequential consistency under -race which are currently passing. So if there is something wrong here, it is subtle.

I'll reopen for now.

Yes, we need a test. What's failing?
That store in tsan runtime is not the only one instruction that implements the operation.

@dvyukov: Here's a reproduction recipe. It's based on "Left-Right - A Concurrency Control Technique with Wait-Free Population Oblivious Reads", an algorithm that requires sequential consistency.

When run under -race, TestLeftRightRace consistently fails because either the left or right maps are being accessed concurrently by the writer and one of the readers. When run without -race, the algorithm never fails. Note that if the implementation was incorrect, it would fail without -race too, because concurrent writes and reads to builtin Go maps are always checked.

Furthermore, to demonstrate what we believe to be the reported issue, you can change the Store calls in readerArrive and readerDepart with Swap calls, and the algorithm now always works even when run under -race. If the semantics described by the language were being applied, the behavior of Store and Swap whilst ignoring the returned value should be identical.

package view

import (
	"runtime"
	"sync"
	"sync/atomic"
	"testing"
	_ "unsafe"
)

//go:linkname sync_runtime_procPin sync.runtime_procPin
//go:nosplit
func sync_runtime_procPin() int

//go:linkname sync_runtime_procUnpin sync.runtime_procUnpin
//go:nosplit
func sync_runtime_procUnpin()

const Reading = 1
const NotReading = 0
const Left = -1

type atomicInt64 struct {
	atomic.Int64
	pad [120]byte
}

type leftright struct {
	active        atomic.Int64
	writerVersion atomic.Uint64
	readerVersion [2][]atomicInt64

	left, right map[uintptr]uintptr
}

func (lr *leftright) init(maxprocs int) {
	lr.left = make(map[uintptr]uintptr)
	lr.right = make(map[uintptr]uintptr)
	lr.readerVersion = [2][]atomicInt64{
		make([]atomicInt64, maxprocs),
		make([]atomicInt64, maxprocs),
	}
	lr.active.Store(Left)
}

func (lr *leftright) readerArrive(version uint64, tid int) {
	v := lr.readerVersion[version&0x1]
	// BUG: this breaks sequential consistency when run under -race
	// Because Swap uses a LOCK XCHG in x64, you can fix the sequential consistency issue with:
	// v[tid].Swap(Reading)
	v[tid].Store(Reading)
}

func (lr *leftright) readerDepart(version uint64, tid int) {
	v := lr.readerVersion[version&0x1]
	// BUG: this breaks sequential consistency when run under -race
	// Because Swap uses a LOCK XCHG in x64, you can fix the sequential consistency issue with:
	// v[tid].Swap(NotReading)
	v[tid].Store(NotReading)
}

func (lr *leftright) readerIsEmpty(version uint64) bool {
	v := lr.readerVersion[version&0x1]
	for t := range v {
		if v[t].Load() == Reading {
			return false
		}
	}
	return true
}

func (lr *leftright) Read(callback func(tbl map[uintptr]uintptr, version uint64)) {
	tid := sync_runtime_procPin()
	vi := lr.writerVersion.Load()

	lr.readerArrive(vi, tid)

	if lr.active.Load() == Left {
		callback(lr.left, vi)
	} else {
		callback(lr.right, vi)
	}

	lr.readerDepart(vi, tid)
	sync_runtime_procUnpin()
}

func (lr *leftright) publish(active int64, callback func(tbl map[uintptr]uintptr)) {
	lr.active.Store(-active)

	prevVersion := lr.writerVersion.Load()
	nextVersion := prevVersion + 1

	for !lr.readerIsEmpty(nextVersion) {
		runtime.Gosched()
	}
	lr.writerVersion.Store(nextVersion)

	for !lr.readerIsEmpty(prevVersion) {
		runtime.Gosched()
	}

	if -active == Left {
		callback(lr.right)
	} else {
		callback(lr.left)
	}
}

func (lr *leftright) Write(callback func(tbl map[uintptr]uintptr)) {
	active := lr.active.Load()
	if active == Left {
		callback(lr.right)
	} else {
		callback(lr.left)
	}
	lr.publish(active, callback)
}

func TestLeftRightRace(t *testing.T) {
	runtime.GOMAXPROCS(8)

	const Procs = 8
	const Iter = 1000000

	var lr leftright
	lr.init(Procs)

	var wg sync.WaitGroup
	wg.Add(Procs + 1)

	for proc := 0; proc < Procs; proc++ {
		go func() {
			defer wg.Done()
			for i := 0; i < Iter; i++ {
				lr.Read(func(tbl map[uintptr]uintptr, _ uint64) {
					_ = tbl[0]
				})
			}
		}()
	}

	go func() {
		defer wg.Done()
		for i := 0; i < Iter; i++ {
			lr.Write(func(tbl map[uintptr]uintptr) {
				tbl[0] = uintptr(i)
			})
		}
	}()

	wg.Wait()
}

It's quite hard to understand what it's doing and ensure the code itself is correct. A simpler example that just captures the pattern where race detector fails would help.

The race detector also reports a race on this code. Is it a false race report?

It's quite hard to understand what it's doing and ensure the code itself is correct. A simpler example that just captures the pattern where race detector fails would help.

I know, but reducing the test case further is proving to be very complicated and I currently don't have more cycles to spend on this this week. Can we agree that the reproduction recipe is valid, for now?

The race detector also reports a race on this code. Is it a false race report?

Do you mean the data race on runtime.mapassign_fast64()? No, the report is legitimate. The map is being written and read to concurrently, even though the purpose of the algorithm is providing exclusionary access to it.

Have you attempted running the same code but replacing the two calls to Store in readerDepart and readerArrive with Swap? In my experience, this fixes the race and makes the code run successfully, both in -race and without.

Can we agree that replacing an atomic Store with a Swap should not change the behavior of a Go program? Can you reproduce that the provided example shows a data race when using Store but shows no data race when using Swap?

If you agree with the underlying issue and can reproduce the bug with the provided example, I'll gladly spend some more time (probably next week) trying to minimize this test case so it can be incorporated in the standard library's test suite.

Thanks for taking the time to look into this. I know the issue is hairy!

A simpler example that just captures the pattern where race detector fails would help.

Just to clarify, this bug report is not about the race detector failing. It's about the race detector weakening the sequential consistency of Go programs, so that algorithms like Left/Right, which require sequential consistency, stop behaving properly when they're being run under the race detector.

Can we agree that the reproduction recipe is valid, for now?

I don't know. It took humanity a decade to shake out bugs of a simple lock-free stack. And you are providing a much more involved algorithm.

It's about the race detector weakening the sequential consistency of Go programs, so that algorithms like Left/Right, which require sequential consistency, stop behaving properly when they're being run under the race detector.

I am confused.
What exactly do you mean by this program is failing? Do you mean that it produces race reports when it should not? Or it fails in other way?
If it's races, the line you pointed to in the tsan runtime has nothing to do with race detection.

But I think I see what may be the issue. It has nothing to do with tsan providing sequential consistency for executions or not, but rather with race detection algorithm.

C++ does have a difference between sequentially consistent store and an RMW operations:

1.10/7
A release sequence headed by a release operation A on an atomic object M is a maximal contiguous subsequence of side effects in the modification order of M, where the first operation is A, and every subsequent
operation
— is performed by the same thread that performed A, or
— is an atomic read-modify-write operation.

In the absence of a formal Go memory model, I assumed that Go follows C++ in these aspects (e.g. because it's compiled by the same backends that generally respect C++ rules only).

And the release sequence is the foundation for building happens-before relation.

Changing the code to the following also prevents the race report by establishing transitive HB relation between goroutines mapped to the same proc:

func (lr *leftright) readerArrive(version uint64, tid int) {
        v := lr.readerVersion[version&0x1]
        // BUG: this breaks sequential consistency when run under -race
        // Because Swap uses a LOCK XCHG in x64, you can fix the sequential consistency issue with:
        // v[tid].Swap(Reading)
        _ = v[tid].Load()
        v[tid].Store(Reading)
}

And the root cause is import "unsafe" and related hacky imports. You wanted unsafe hacks, you got them :)

If you go this route, you need to somehow teach race detector about the transitive synchronization provided by the runtime scheduler.

Thanks for the review! Let me see if I understand the situation: you're saying that by pinning the reader goroutines to specific Ps, the happens-before relation between the readers is hidden from TSAN. This is because the two stores must necessarily happen sequentially, as the G where they run is pinned, but TSAN is not aware of this fact. Explicitly performing a read (with a Load or Swap) forces TSAN to see the HB relation. If so, this is a bug that could never reproduce in safe Go code, but would apply to internal runtime code. Does this seem accurate?

Yes. Looks accurate.
And this is where difference between Store and Swap kicks in -- Swap's done by reads synchronize with each other, while Store's don't.
In you actual code Readers effectively synchronize as well by means of pin/unpin, but the race detector is not aware of that.
If this is your real production code, I would suggest adding some "annotations" in race build. The Load as I added in the previous comment is probably the simplest and cheapest way.

Thanks again for the review, @dvyukov. I don't know if making TSAN aware of Go scheduler pinning is in scope, since this would only apply when race testing internal runtime code. I'll leave that up to you!

The race detector intentionally ignores all synchronization in the runtime and does not test it. It's intended for end users for testing of their code.
If we want to test the runtime itself, we need a different tool, or at least a radically different operation mode.

So let me just summarize where I think we are.

The issue here is that the race detector is reporting on a race that you think it shouldn't be.

The issue is not race mode breaking sequential consistency semantics. That is, if we modified the race detector to do its normal thing but not report any races, the program would still run correctly.

We think the race detector is reporting races because it cannot see happens-before edges introduced by procPin/procUnpin that are required to infer a race-free execution.

If all that sounds right, then I don't think there is anything to do here on the Go side. procPin/procUnpin is not a supported API and we don't make any promises about its use via linkname.