runtime: apparent false-positive race report for a buffered channel after CL 220419

[bcmills]

I got the following race report on CL 258758.

(https://storage.googleapis.com/go-build-log/04d98a9c/linux-amd64-race_596e00e8.log)

--- FAIL: TestScript (0.11s)
    --- FAIL: TestScript/mod_retract (0.34s)
        script_test.go:211: 
            # Populate go.sum. (0.087s)
            # 'go list pkg' does not report an error when a retracted version is used. (0.069s)
            # Nor does 'go build'. (0.000s)
            # Neither 'go list' nor 'go build' should download go.mod from the version
            # that would list retractions. (0.000s)
            # Importing a package from a module with a retracted latest version will
            # select the latest non-retracted version. (0.175s)
            > go get -d ./use_self_prev
            [stderr]
            go: downloading example.com v1.0.0
            go: downloading example.com/retract/self/prev v1.1.0
            go: downloading example.com/retract v1.1.0
            ==================
            WARNING: DATA RACE
            Read at 0x00c0002c0ce8 by main goroutine:
              cmd/go/internal/modget.reportRetractions()
                  /workdir/go/src/cmd/go/internal/modget/get.go:550 +0x224
              cmd/go/internal/modget.runGet()
                  /workdir/go/src/cmd/go/internal/modget/get.go:490 +0x931
              main.main()
                  /workdir/go/src/cmd/go/main.go:195 +0xb94
            
            Previous write at 0x00c0002c0ce8 by goroutine 76:
              cmd/go/internal/modload.addRetraction()
                  /workdir/go/src/cmd/go/internal/modload/build.go:132 +0x424
              cmd/go/internal/modload.ListModules.func1.1()
                  /workdir/go/src/cmd/go/internal/modload/list.go:40 +0x84
            
            Goroutine 76 (finished) created at:
              cmd/go/internal/modload.ListModules.func1()
                  /workdir/go/src/cmd/go/internal/modload/list.go:32 +0xe4
              cmd/go/internal/modload.ListModules()
                  /workdir/go/src/cmd/go/internal/modload/list.go:46 +0x1fa
              cmd/go/internal/modget.reportRetractions()
                  /workdir/go/src/cmd/go/internal/modget/get.go:547 +0x184
              cmd/go/internal/modget.runGet()
                  /workdir/go/src/cmd/go/internal/modget/get.go:490 +0x931
              main.main()
                  /workdir/go/src/cmd/go/main.go:195 +0xb94
            ==================
            ==================
            WARNING: DATA RACE
            Read at 0x00c000058ac0 by main goroutine:
              cmd/go/internal/modget.reportRetractions()
                  /workdir/go/src/cmd/go/internal/modget/get.go:556 +0x2b9
              cmd/go/internal/modget.runGet()
                  /workdir/go/src/cmd/go/internal/modget/get.go:490 +0x931
              main.main()
                  /workdir/go/src/cmd/go/main.go:195 +0xb94
            
            Previous write at 0x00c000058ac0 by goroutine 76:
              cmd/go/internal/modload.checkRetractions()
                  /workdir/go/src/cmd/go/internal/modload/modfile.go:163 +0x4a4
              cmd/go/internal/modload.addRetraction()
                  /workdir/go/src/cmd/go/internal/modload/build.go:126 +0x104
              cmd/go/internal/modload.ListModules.func1.1()
                  /workdir/go/src/cmd/go/internal/modload/list.go:40 +0x84
            
            Goroutine 76 (finished) created at:
              cmd/go/internal/modload.ListModules.func1()
                  /workdir/go/src/cmd/go/internal/modload/list.go:32 +0xe4
              cmd/go/internal/modload.ListModules()
                  /workdir/go/src/cmd/go/internal/modload/list.go:46 +0x1fa
              cmd/go/internal/modget.reportRetractions()
                  /workdir/go/src/cmd/go/internal/modget/get.go:547 +0x184
              cmd/go/internal/modget.runGet()
                  /workdir/go/src/cmd/go/internal/modget/get.go:490 +0x931
              main.main()
                  /workdir/go/src/cmd/go/main.go:195 +0xb94
            ==================
            go: warning: example.com/retract@v1.0.0-bad is retracted: bad
            go: run 'go get example.com/retract@latest' to switch to the latest unretracted version
            Found 2 data race(s)
            [exit status 66]
            FAIL: testdata/script/mod_retract.txt:23: unexpected command failure
            
FAIL
FAIL	cmd/go	151.822s

The reported race is for a function that uses an N-buffered channel as a semaphore. The function sends to the channel (from the main goroutine) to acquire a semaphore token, and receives from the channel (in a background goroutine) to release the token. Before the function returns, it sends N additional tokens to the channel to ensure that all of the background goroutines have finished.

I believe that this pattern is explicitly covered by the memory model:

The kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.

This is the first race we've seen reported for this code, and the timing w.r.t. CL 220419, which changes the semantics of channels under the race detector, seems suspicious to me.

[bcmills]

CC @dfava @ianlancetaylor @dvyukov @aclements @randall77

[bcmills]

@cherrymui, your example is spawning N goroutines that all mutate the same global variable, whereas the goroutines in the actual code in question mutate disjoint variables.

The race reported for your example should be a write–write race, whereas the newly-observed false positive is reported as a read-write race.

[dvyukov]

I've spent some time analyzing the effect of CL 220419 at the time and I concluded it's perfectly in line with MM.

I believe that this pattern explicitly covered by the memory model:
The kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.

This is true, but this relation does not seem to be transitive. Namely, if there are more than C operations, kth receive HB k+Cth send, but it does not HB 2*k+Cth send. So when the code does:

	for n := cap(sem); n > 0; n-- {
		sem <- token{}
	}

It only synchronizes with the completion of the last cap(sem) operations, but not with all the previous ones.

[cherrymui]

@bcmills you're right. Sorry about the noise.

[ianlancetaylor]

@dvyukov If I understand you correctly, that sounds like a bug in the memory model. Perhaps the memory model ought to say that the kth receive on a channel with capacity C happens before the k+Cth+N send from the channel completes, where N is any non-negative integer. There is no necessary relationship between sends, of course. But with capacity C, a receive may happen concurrently with up to (but not including) C sends, but it happens before C sends complete, or C+1 sends complete, or C+2 sends complete, etc.

[bcmills]

@dvyukov, in this case we should be able to prove that all previous receives happen before the final send by induction, because all sends on the channel occur in the same goroutine.

• The kth receive happens before the k+Cth send because “[t]he kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.”

• In this program all sends are within a single goroutine, so the k+Cth send happens before the i+Cth send for all i ≥ k because “[w]ithin a single goroutine, the happens-before order is the order expressed by the program.”

• “Happens before” is transitive, so in this program the kth receive happens before the i+Cth send for all i ≥ k.

• In this program there are exactly N+C sends and exactly N receives, so each receive happens before the last send.

[bcmills]

@ianlancetaylor, I think the terms “kth receive” and “k+Cth send” are confusing and perhaps misleading here. Identifying the “kth receive” requires a total order among the receives, but the point of HB is that we may only have a partial order.

A more precise definition might be more like: “If a send on a channel with capacity C happens before k ≥ C other sends on the channel, then the receive corresponding to the first send happens before the last of those k+1 sends completes.”

[dvyukov]

@dvyukov If I understand you correctly, that sounds like a bug in the memory model. Perhaps the memory model ought to say that the kth receive on a channel with capacity C happens before the k+Cth+N send from the channel completes, where N is any non-negative integer. There is no necessary relationship between sends, of course. But with capacity C, a receive may happen concurrently with up to (but not including) C sends, but it happens before C sends complete, or C+1 sends complete, or C+2 sends complete, etc.

Good question.
The examples we had in CL 258758, did not look like something we need to support and race detector indeed produced false negatives on these examples. This "wait for all" example did not come up at the time.

happens before the k+Cth+N

This feels a bit fishy to me. It seems we are trying to compensate for broken transitivity, where fixing transitivity would cleaner.
I am thinking of:

-The kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.
-This rule generalizes the previous rule to buffered channels.

+The kth receive completion on a buffered channel with capacity C happens before the k+Cth send.

It does not generalize the rule for unbuffered channels anymore: the use of send/recv and send completion/recv completion is swapped. But breaking generalization by introducing new custom rules also feels fishy to me :)
However, my understanding always was that weird splitting to operation and operation completion was introduced specifically for unbuffered channels to break HB cycle. Without that splitting the current rules would work perfectly for buffered channels (support the code in question).

[dvyukov]

@dvyukov, in this case we should be able to prove that all previous receives happen before the final send by induction, because all sends on the channel occur in the same goroutine.

• The kth receive happens before the k+Cth send because “[t]he kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.”
• In this program all sends are within a single goroutine, so the k+Cth send happens before the i+Cth send for all i ≥ k because “[w]ithin a single goroutine, the happens-before order is the order expressed by the program.”
• “Happens before” is transitive, so in this program the kth receive happens before the i+Cth send for all i ≥ k.
• In this program there are exactly N+C sends and exactly N receives, so each receive happens before the last send.

Good point.
With the changes Ian or me proposed above it would work without relying on the fact that all sends happen in the same goroutine, the channel itself would provide the necessary synchronization. But if we take into account that all sends happen in the same goroutine, then it seems that it should work with the current rules as well:

Here channel capacity is 2 and all accesses d0-3 happen before use.

@dfava where is the flaw now?

Also now I wonder if we are dealing with one issue or two :) There seems to be a bug in race detector implementation, but also do we still want to fix the memory model so that similar synchronization is provided even when sends do not happen in the same goroutine? For ListModules is seems inherent that all sends happen in the same goroutine (?).

[bcmills]

In this case it actually is important that the initial sends happen before the final loop, so I would be wary about strengthening the model too much.

If the initial sends were moved into the background goroutines, it would be possible for that final channel-fill loop to execute before the background goroutines, causing them to leak (blocked on the sends) instead of execute. That wouldn't be a data race, but only because the mutations would no longer happen at all!

[bcmills]

@dvyukov, also note that the phrasing I suggested in #42598 (comment) does continue to generalize to the unbuffered case.