Selects are always selecting the first case if multiple can proceed

[gopherbot]

by bjorn.tipling:

What steps will reproduce the problem?
1. Compile and run this code:
package main

import "fmt"

func main() {
        a := make(chan int)
        go func() {
                for {
                        fmt.Print(<-a)
                }
        } ()
        for {
                select {
                case a <- 0:
                case a <- 1:
                }
        }
}

2. See it just spit out 0's.

What is the expected output?

There should be a distribution of 0's and 1's, not just 0's.

What do you see instead?

Just 0's.

Which compiler are you using (5g, 6g, 8g, gccgo)?

6g

Which operating system are you using?

Mac OS X Lion 10.7

Which revision are you using?  (hg identify)

c17ce5ec06b4 weekly/weekly.2011-08-10 (Latest don't build on OS X Lion)

Please provide any additional information below.


IRC log from #go-nuts:

18:48 < s|k> just gives me 0's
18:49 < s|k> the random program
18:49 < s|k> http://pastie.org/2371134
19:51 < f2f> s|k, post to the list to see what's changed.
19:51 < f2f> it is certaonly contrary to the spec: "If multiple cases can
proceed, a pseudo-random fair choice is made to decide which single communication 
             will execute.
19:52 < f2f> "
19:52 < f2f> certainly even
19:52 < f2f> if you don't want to post to the list i will :)
19:59 < chilts> ok, so I downloaded and compiled that program and get lots of 0's
and 1's in random order
19:59 < chilts> (pseudo random order)
19:59 < f2f> i get lots of 0s. on osx 6g and linux 8g
20:00 < chilts> I'm on Linux : 6g version release.r59 9022
20:00 < chilts> seems fine to me
20:00 < f2f> hmm. still 0
20:01 < f2f> 9354 is my release
20:01 < f2f> 9414 for 8g
20:03 < f2f> let's see if i revert to 9022
20:05 < f2f> yes, i get random 0s and 1s at release 9022.
20:05 < f2f> s|k please report this violation of the spec.

[mirtchovski]

Comment 1:

this also occurs at 9433 (latest tip), osx, 6g:
$ hg identify
db3b3cfd9d28 tip

[mirtchovski]

Comment 2:

the bug was introduced with release 9237:
$ hg log -r 9237
changeset:   9237:2ccdb29d715c
user:        Dmitriy Vyukov <dvyukov@google.com>
date:        Thu Jul 21 13:57:13 2011 -0400
summary:     runtime: faster select
9236 behaves as per the spec.

[mirtchovski]

Comment 3:

sorry, 9236 and 9237 are local numbers relevant to my repository.
this is the revision that introduced the bug:
http://code.google.com/p/go/source/detail?r=2ccdb29d715c

[niemeyer]

Comment 4:

Owner changed to @niemeyer.

Status changed to Started.

[dvyukov]

Comment 5:

Here is test/fixedbugs/bug2152.go
// $G $D/$F.go && $L $F.$A && ./$A.out
// Copyright 2011 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package main
import (
    "runtime"
)
func main() {
    const N = 100
    const K = 10
    c := make(chan int)
    go func() {
        zeros := 0
        for i := 0; i < N; i++ {
            runtime.Gosched()
            if <-c == 0 {
                zeros++
            }
        }
        if zeros <= N/K || zeros >= N-N/K {
            println("zeros=", zeros, "ones=", N-zeros)
            panic("select cases are not that random")
        }
        c <- 0
    }()
    for i := 0; i < N; i++ {
        select {
        case c <- 0:
        case c <- 1:
        }
    }
    <-c
}

[dvyukov]

Comment 6:

Here is the fix
diff -r 4dfd650363a2 src/pkg/runtime/chan.c
--- a/src/pkg/runtime/chan.c    Mon Aug 15 15:16:57 2011 +1000
+++ b/src/pkg/runtime/chan.c    Mon Aug 15 10:21:57 2011 +0400
@@ -904,7 +904,8 @@
 
    // pass 2 - enqueue on all chans
    for(i=0; i<sel->ncase; i++) {
-       cas = &sel->scase[i];
+       o = sel->pollorder[i];
+       cas = &sel->scase[o];
        c = cas->chan;
        sg = &cas->sg;
        sg->g = g;

[dvyukov]

Comment 7:

How far have you moved forward? I may submit it.

[niemeyer]

Comment 8:

It's in review with test and all:
http://golang.org/cl/4888044/

[niemeyer]

Comment 9:

This issue was closed by revision 1758492.

Status changed to Fixed.