src/runtime/chan_test.go | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/runtime/stubs.go | 8 +++++--- diff --git a/src/runtime/chan_test.go b/src/runtime/chan_test.go index a75fa1b992987fd623533d89b3bc323406f7d942..0c94cf1a633041a4d9486f71a547fd59709be369 100644 --- a/src/runtime/chan_test.go +++ b/src/runtime/chan_test.go @@ -5,6 +5,7 @@ package runtime_test import ( + "math" "runtime" "sync" "sync/atomic" @@ -427,6 +428,62 @@ } } wg.Done() }() + wg.Wait() +} + +func TestSelectFairness(t *testing.T) { + const trials = 10000 + c1 := make(chan byte, trials+1) + c2 := make(chan byte, trials+1) + for i := 0; i < trials+1; i++ { + c1 <- 1 + c2 <- 2 + } + c3 := make(chan byte) + c4 := make(chan byte) + out := make(chan byte) + done := make(chan byte) + var wg sync.WaitGroup + wg.Add(1) + go func() { + defer wg.Done() + for { + var b byte + select { + case b = <-c3: + case b = <-c4: + case b = <-c1: + case b = <-c2: + } + select { + case out <- b: + case <-done: + return + } + } + }() + cnt1, cnt2 := 0, 0 + for i := 0; i < trials; i++ { + switch b := <-out; b { + case 1: + cnt1++ + case 2: + cnt2++ + default: + t.Fatalf("unexpected value %d on channel", b) + } + } + // If the select in the goroutine is fair, + // cnt1 and cnt2 should be about the same value. + // With 10,000 trials, the expected margin of error at + // a confidence level of five nines is 4.4172 / (2 * Sqrt(10000)). + r := float64(cnt1) / trials + e := math.Abs(r - 0.5) + t.Log(cnt1, cnt2, r, e) + if e > 4.4172/(2*math.Sqrt(trials)) { + t.Errorf("unfair select: in %d trials, results were %d, %d", trials, cnt1, cnt2) + } + close(done) wg.Wait() } diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go index c4f32a84825c9cdbb81136909f21ac17c9bf557f..72d21187ec1da1dc70e8fdfe76893c2401747a45 100644 --- a/src/runtime/stubs.go +++ b/src/runtime/stubs.go @@ -105,9 +105,11 @@ } //go:nosplit func fastrandn(n uint32) uint32 { - // This is similar to fastrand() % n, but faster. - // See http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ - return uint32(uint64(fastrand()) * uint64(n) >> 32) + // Don't be clever. + // fastrand is not good enough for cleverness. + // Just use mod. + // See golang.org/issue/21806. + return fastrand() % n } //go:linkname sync_fastrand sync.fastrand