runtime: eliminate scase.kind field

Currently, we include a "kind" field on scase to distinguish the three
kinds of cases in a select statement: sends, receives, and defaults.

This commit removes by kind field by instead arranging for the
compiler to always place sends before receives, and to provide their
counts separately. It also passes an explicit "block bool" parameter
to avoid needing to include a default case in the array.

It's safe to shuffle cases like this because the runtime will
randomize the order they're polled in anyway.

Fixes #40410.

Change-Id: Iaeaed4cf7bddd576d78f2c863bd91a03a5c82df2
Reviewed-on: https://go-review.googlesource.com/c/go/+/245125
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 58 insertions, 46 deletions

diff --git a/src/runtime/select.go b/src/runtime/select.go
index d7c7d9f26f..80768b285b 100644
--- a/src/runtime/select.go
+++ b/src/runtime/select.go
@@ -12,23 +12,12 @@ import (
 
 const debugSelect = false
 
-// scase.kind values.
-// Known to compiler.
-// Changes here must also be made in src/cmd/compile/internal/gc/select.go's walkselectcases.
-const (
-	caseNil = iota
-	caseRecv
-	caseSend
-	caseDefault
-)
-
 // Select case descriptor.
 // Known to compiler.
 // Changes here must also be made in src/cmd/internal/gc/select.go's scasetype.
 type scase struct {
 	c    *hchan         // chan
 	elem unsafe.Pointer // data element
-	kind uint16
 }
 
 var (
@@ -115,7 +104,7 @@ func block() {
 // ordinal position of its respective select{recv,send,default} call.
 // Also, if the chosen scase was a receive operation, it reports whether
 // a value was received.
-func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool) {
+func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, nsends, nrecvs int, block bool) (int, bool) {
 	if debugSelect {
 		print("select: cas0=", cas0, "\n")
 	}
@@ -125,6 +114,7 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 	cas1 := (*[1 << 16]scase)(unsafe.Pointer(cas0))
 	order1 := (*[1 << 17]uint16)(unsafe.Pointer(order0))
 
+	ncases := nsends + nrecvs
 	scases := cas1[:ncases:ncases]
 	pollorder := order1[:ncases:ncases]
 	lockorder := order1[ncases:][:ncases:ncases]
@@ -158,16 +148,12 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 	// optimizing (and needing to test).
 
 	// generate permuted order
-	dfli := -1
 	norder := 0
 	for i := range scases {
 		cas := &scases[i]
 
 		// Omit cases without channels from the poll and lock orders.
 		if cas.c == nil {
-			if cas.kind == caseDefault {
-				dfli = i
-			}
 			cas.elem = nil // allow GC
 			continue
 		}
@@ -250,8 +236,7 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 		cas = &scases[casi]
 		c = cas.c
 
-		switch cas.kind {
-		case caseRecv:
+		if casi >= nsends {
 			sg = c.sendq.dequeue()
 			if sg != nil {
 				goto recv
@@ -262,8 +247,7 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 			if c.closed != 0 {
 				goto rclose
 			}
-
-		case caseSend:
+		} else {
 			if raceenabled {
 				racereadpc(c.raceaddr(), casePC(casi), chansendpc)
 			}
@@ -280,9 +264,9 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 		}
 	}
 
-	if dfli >= 0 {
+	if !block {
 		selunlock(scases, lockorder)
-		casi = dfli
+		casi = -1
 		goto retc
 	}
 
@@ -311,12 +295,10 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 		*nextp = sg
 		nextp = &sg.waitlink
 
-		switch cas.kind {
-		case caseRecv:
-			c.recvq.enqueue(sg)
-
-		case caseSend:
+		if casi < nsends {
 			c.sendq.enqueue(sg)
+		} else {
+			c.recvq.enqueue(sg)
 		}
 	}
 
@@ -359,7 +341,7 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 			}
 		} else {
 			c = k.c
-			if k.kind == caseSend {
+			if int(casei) < nsends {
 				c.sendq.dequeueSudoG(sglist)
 			} else {
 				c.recvq.dequeueSudoG(sglist)
@@ -378,27 +360,29 @@ func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, ncases int) (int, bool)
 	c = cas.c
 
 	if debugSelect {
-		print("wait-return: cas0=", cas0, " c=", c, " cas=", cas, " kind=", cas.kind, "\n")
+		print("wait-return: cas0=", cas0, " c=", c, " cas=", cas, " send=", casi < nsends, "\n")
 	}
 
-	if cas.kind == caseRecv {
+	if casi < nsends {
+		if !caseSuccess {
+			goto sclose
+		}
+	} else {
 		recvOK = caseSuccess
-	} else if cas.kind == caseSend && !caseSuccess {
-		goto sclose
 	}
 
 	if raceenabled {
-		if cas.kind == caseRecv && cas.elem != nil {
-			raceWriteObjectPC(c.elemtype, cas.elem, casePC(casi), chanrecvpc)
-		} else if cas.kind == caseSend {
+		if casi < nsends {
 			raceReadObjectPC(c.elemtype, cas.elem, casePC(casi), chansendpc)
+		} else if cas.elem != nil {
+			raceWriteObjectPC(c.elemtype, cas.elem, casePC(casi), chanrecvpc)
 		}
 	}
 	if msanenabled {
-		if cas.kind == caseRecv && cas.elem != nil {
-			msanwrite(cas.elem, c.elemtype.size)
-		} else if cas.kind == caseSend {
+		if casi < nsends {
 			msanread(cas.elem, c.elemtype.size)
+		} else if cas.elem != nil {
+			msanwrite(cas.elem, c.elemtype.size)
 		}
 	}
 
@@ -526,29 +510,57 @@ func reflect_rselect(cases []runtimeSelect) (int, bool) {
 		block()
 	}
 	sel := make([]scase, len(cases))
-	order := make([]uint16, 2*len(cases))
-	for i := range cases {
-		rc := &cases[i]
+	orig := make([]int, len(cases))
+	nsends, nrecvs := 0, 0
+	dflt := -1
+	for i, rc := range cases {
+		var j int
 		switch rc.dir {
 		case selectDefault:
-			sel[i] = scase{kind: caseDefault}
+			dflt = i
+			continue
 		case selectSend:
-			sel[i] = scase{kind: caseSend, c: rc.ch, elem: rc.val}
+			j = nsends
+			nsends++
 		case selectRecv:
-			sel[i] = scase{kind: caseRecv, c: rc.ch, elem: rc.val}
+			nrecvs++
+			j = len(cases) - nrecvs
 		}
+
+		sel[j] = scase{c: rc.ch, elem: rc.val}
+		orig[j] = i
 	}
 
+	// Only a default case.
+	if nsends+nrecvs == 0 {
+		return dflt, false
+	}
+
+	// Compact sel and orig if necessary.
+	if nsends+nrecvs < len(cases) {
+		copy(sel[nsends:], sel[len(cases)-nrecvs:])
+		copy(orig[nsends:], orig[len(cases)-nrecvs:])
+	}
+
+	order := make([]uint16, 2*(nsends+nrecvs))
 	var pc0 *uintptr
 	if raceenabled {
-		pcs := make([]uintptr, len(cases))
+		pcs := make([]uintptr, nsends+nrecvs)
 		for i := range pcs {
 			selectsetpc(&pcs[i])
 		}
 		pc0 = &pcs[0]
 	}
 
-	return selectgo(&sel[0], &order[0], pc0, len(cases))
+	chosen, recvOK := selectgo(&sel[0], &order[0], pc0, nsends, nrecvs, dflt == -1)
+
+	// Translate chosen back to caller's ordering.
+	if chosen < 0 {
+		chosen = dflt
+	} else {
+		chosen = orig[chosen]
+	}
+	return chosen, recvOK
 }
 
 func (q *waitq) dequeueSudoG(sgp *sudog) {