CC @dfava @ianlancetaylor @dvyukov @aclements @randall77

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.

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

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

@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 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, 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 (?).

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!

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

Given that we're coming up against the beta, should we revert CL 220419?

Yes, I think we need to rollback for now and add this pattern as a new race test. False positives are much worse than false negatives.

Change https://golang.org/cl/271946 mentions this issue: Revert "runtime: swap the order of raceacquire() and racerelease()"

I sent a revert CL: https://golang.org/cl/271946.

Sorry I wasn't receiving emails about this thread until the change was reverted just now. I haven't had a chance to read it, but I will soon and can comment.

For what it's worth, the revert CL is not yet committed. A simple roll forward fix is still possible, but it would have to happen very very soon.

Is the failure intermittent (or "somewhat deterministic")? I'm not able to reproduce it on commit 5e58ae4.

Seems like there has been some refactoring around modules. I can't find "reportRetractions" in the source tree. Seems like the function has recently been removed and it used to live in src/cmd/go/internal/modget/get.go. Is that correct?

@bcmills , is the race still reported after this recent refactoring?

(I haven't had a chance to fully digest the discussion above, just going piece by piece from the beginning. I agree on reverting the CL so we can drill down into this carefully. I doubt there is a "bug" in memory model specification; more likely the bug is on my code, or on the code where the race is being reported)

Also, I vaguely recall an earlier discussion on how the race detector treats differently channels whose elements are size zero... Perhaps that special treatment maters now.

Also, I vaguely recall an earlier discussion on how the race detector treats differently channels whose elements are size zero... Perhaps that special treatment maters now.

Good point!
Here is the address we use for synchronization:

// chanbuf(c, i) is pointer to the i'th slot in the buffer.
func chanbuf(c *hchan, i uint) unsafe.Pointer {
	return add(c.buf, uintptr(i)*uintptr(c.elemsize))
}

I assume for struct{} it's always the same location for all elements.
I guess racereleaseacquire fix does not work for such case.

I think we could do:

if c.elemsize != 0 {
  racereleaseacquire(qp)
} else {
  raceacquire(qp)
  racerelease(qp)
}

I agree, we could put a check for elemsize. It's nice and simple, and it doesn't force us to revisit the assumptions made about channels of elemsize==0 right now.

I'm happy that the memory model specification is fine as it is, and I also see that the code in ListModules is correct.

I also think that my patch is not wrong :) though it did expose the issue with elemsize==0, and, in hindsight, I should have accounted for that when testing.

I'll spend a bit of time thinking about what exactly happens when elemsize==0 interacts with racereleaseacquire().

@dfava

Is the failure intermittent (or "somewhat deterministic")? I'm not able to reproduce it on commit 5e58ae4.

The failure is intermittent.

There have so far been at least three failures in TryBots and one on the build dashboard (2020-11-14T17:24:37-92c732e/linux-amd64-race).

I'll spend a bit of time thinking about what exactly happens when elemsize==0 interacts with racereleaseacquire().

My understanding is that previously HB was completely cumulative, so the fact that the same address was shared between unrelated elements did not matter (we only get more false negatives). But racereleaseacquire is not cumulative, it always drops everything that was there before, so sharing breaks.

I'll spend a bit of time thinking about what exactly happens when elemsize==0 interacts with racereleaseacquire().

My understanding is that previously HB was completely cumulative, so the fact that the same address was shared between unrelated elements did not matter (we only get more false negatives). But racereleaseacquire is not cumulative, it always drops everything that was there before, so sharing breaks.

You are absolutely right. Here is in a bit more detail, perhaps it's nice to document.
The code essentially does the following, where c is a channel of size 2:

T0                T1        T2
c <-         |           |
go T1        |  wr X     |
c <-         |  <- c     |
go T2        |           |  wr Y
             |           |  <- c
c <-         |           |
c <-         |           |

I'll represent each entry in the channel's buffer as B0 and B1.
Here is a picture of the state of the race detector after T1 and T2 write to variable X and Y:

B0      B1      T0             T1      T2
{}      {}      {}             {wr X}  {wr Y}  => then T1 receives from c
{wr X}  {}      {}             {wr X}  {wr Y}  => then T2 receives from c
{wr X}  {wr Y}  {}             {wr X}  {wr Y}  => then T0 sends onto c
{}      {wr Y}  {wr X}         {wr X}  {wr Y}  => then T0 sends onto c
{}      {wr X}  {wr X, wr Y}   {wr X}  {wr Y}

The end state is, T0 is properly synchronized with T1 and T2: T0 "knows" of both T1's and T2's writes to X and Y.

However, we currently model channels whose elmsize==0 with one buffer entry, so only B0 and no B1. The picture then looks like:

B0        T0             T1      T2
{}        {}             {wr X}  {wr Y}        => then T1 receives from c
{wr X}    {}             {wr X}  {wr Y}        => then T2 receives from c
{wr Y}    {}             {wr X}  {wr X, wr Y}  => then T0 sends onto c
{}        {wr Y}         {wr X}  {wr Y, wr Y}  => then T0 sends onto c
{wr Y}    {wr Y}         {wr X}  {wr Y, wr Y}

In the end state now, T0 is unaware of one of the writes, so a race is flagged.

It seems like we are able to keep CL 220419 and add the check that Dmitry suggested.

Let me know if you would like me to do it, or if you prefer to do it yourselves (since you are probably faster at it than me, given your familiarity with the flow and my lack of access to buildbot and etc). I'm happy either way!

Whoever is doing it, just please add some comments/references and tests ;)

Whoever is doing it, just please add some comments/references and tests ;)

:) Is it possible to force a specific scheduling of goroutines so we hit the scenario exactly? Maybe using internals/unsafe/something?

(I'm working on a patch)

Change https://golang.org/cl/271987 mentions this issue: runtime: check channel's elemsize before calling race detector

I submitted a patch which included the check for elemsize, documentation, and a test.
The test fails on top-of-tree (as expected), and passes on the branch with the patch (as expected).