From 4f269d3060b89567ed413b17bb488668bdbb6972 Mon Sep 17 00:00:00 2001
From: Russ Cox <rsc@golang.org>
Date: Thu, 20 Jan 2011 09:20:47 -0500
Subject: [PATCH] runtime: make select fairer

The o+i*p approach to visiting select cases in random
order stops being fair when there is some case that
is never ready.  If that happens, then the case that follows
it in the order gets more chances than the others.

In general the only way to ensure fairness is to make
all permutations equally likely.  I've done that by computing
one explicitly.

Makes the permutations correct for n >= 4 where
previously they were broken.  For n > 12, there's not
enough randomness to do a perfect job but this should
still be much better than before.

Fixes #1425.

R=r, ken2, ejsherry
CC=golang-dev
https://golang.org/cl/4037043
---
 src/pkg/runtime/chan.c | 85 +++++++++++++++---------------------------
 1 file changed, 30 insertions(+), 55 deletions(-)

diff --git a/src/pkg/runtime/chan.c b/src/pkg/runtime/chan.c
index fad437d379..4ef0b6f6f5 100644
--- a/src/pkg/runtime/chan.c
+++ b/src/pkg/runtime/chan.c
@@ -76,6 +76,7 @@ struct	Select
 	uint16	tcase;			// total count of scase[]
 	uint16	ncase;			// currently filled scase[]
 	Select*	link;			// for freelist
+	uint16*	order;
 	Scase*	scase[1];		// one per case
 };
 
@@ -84,9 +85,7 @@ static	SudoG*	dequeue(WaitQ*, Hchan*);
 static	void	enqueue(WaitQ*, SudoG*);
 static	SudoG*	allocsg(Hchan*);
 static	void	freesg(Hchan*, SudoG*);
-static	uint32	gcd(uint32, uint32);
-static	uint32	fastrand1(void);
-static	uint32	fastrand2(void);
+static	uint32	fastrandn(uint32);
 static	void	destroychan(Hchan*);
 
 Hchan*
@@ -496,10 +495,11 @@ runtime·newselect(int32 size, ...)
 	if(size > 1)
 		n = size-1;
 
-	sel = runtime·mal(sizeof(*sel) + n*sizeof(sel->scase[0]));
+	sel = runtime·mal(sizeof(*sel) + n*sizeof(sel->scase[0]) + size*sizeof(sel->order[0]));
 
 	sel->tcase = size;
 	sel->ncase = 0;
+	sel->order = (void*)(sel->scase + size);
 	*selp = sel;
 	if(debug)
 		runtime·printf("newselect s=%p size=%d\n", sel, size);
@@ -650,7 +650,7 @@ selunlock(Select *sel)
 void
 runtime·selectgo(Select *sel)
 {
-	uint32 p, o, i, j;
+	uint32 o, i, j;
 	Scase *cas, *dfl;
 	Hchan *c;
 	SudoG *sg;
@@ -671,21 +671,16 @@ runtime·selectgo(Select *sel)
 		// TODO: make special case of one.
 	}
 
-	// select a (relative) prime
-	for(i=0;; i++) {
-		p = fastrand1();
-		if(gcd(p, sel->ncase) == 1)
-			break;
-		if(i > 1000)
-			runtime·throw("select: failed to select prime");
+	// generate permuted order
+	for(i=0; i<sel->ncase; i++)
+		sel->order[i] = i;
+	for(i=1; i<sel->ncase; i++) {
+		o = sel->order[i];
+		j = fastrandn(i+1);
+		sel->order[i] = sel->order[j];
+		sel->order[j] = o;
 	}
 
-	// select an initial offset
-	o = fastrand2();
-
-	p %= sel->ncase;
-	o %= sel->ncase;
-
 	// sort the cases by Hchan address to get the locking order.
 	for(i=1; i<sel->ncase; i++) {
 		cas = sel->scase[i];
@@ -693,13 +688,13 @@ runtime·selectgo(Select *sel)
 			sel->scase[j] = sel->scase[j-1];
 		sel->scase[j] = cas;
 	}
-
 	sellock(sel);
 
 loop:
 	// pass 1 - look for something already waiting
 	dfl = nil;
 	for(i=0; i<sel->ncase; i++) {
+		o = sel->order[i];
 		cas = sel->scase[o];
 		c = cas->chan;
 
@@ -734,10 +729,6 @@ loop:
 			dfl = cas;
 			break;
 		}
-
-		o += p;
-		if(o >= sel->ncase)
-			o -= sel->ncase;
 	}
 
 	if(dfl != nil) {
@@ -748,6 +739,7 @@ loop:
 
 	// pass 2 - enqueue on all chans
 	for(i=0; i<sel->ncase; i++) {
+		o = sel->order[i];
 		cas = sel->scase[o];
 		c = cas->chan;
 		sg = allocsg(c);
@@ -777,10 +769,6 @@ loop:
 			enqueue(&c->sendq, sg);
 			break;
 		}
-
-		o += p;
-		if(o >= sel->ncase)
-			o -= sel->ncase;
 	}
 
 	g->param = nil;
@@ -794,18 +782,14 @@ loop:
 	// pass 3 - dequeue from unsuccessful chans
 	// otherwise they stack up on quiet channels
 	for(i=0; i<sel->ncase; i++) {
-		if(sg == nil || o != sg->offset) {
-			cas = sel->scase[o];
+		if(sg == nil || i != sg->offset) {
+			cas = sel->scase[i];
 			c = cas->chan;
 			if(cas->send)
 				dequeueg(&c->sendq, c);
 			else
 				dequeueg(&c->recvq, c);
 		}
-		
-		o += p;
-		if(o >= sel->ncase)
-			o -= sel->ncase;
 	}
 
 	if(sg == nil)
@@ -1059,22 +1043,6 @@ freesg(Hchan *c, SudoG *sg)
 	}
 }
 
-static uint32
-gcd(uint32 u, uint32 v)
-{
-	for(;;) {
-		if(u > v) {
-			if(v == 0)
-				return u;
-			u = u%v;
-			continue;
-		}
-		if(u == 0)
-			return v;
-		v = v%u;
-	}
-}
-
 static uint32
 fastrand1(void)
 {
@@ -1087,12 +1055,19 @@ fastrand1(void)
 }
 
 static uint32
-fastrand2(void)
+fastrandn(uint32 n)
 {
-	static uint32 x = 0x49f6428aUL;
+	uint32 max, r;
 
-	x += x;
-	if(x & 0x80000000L)
-		x ^= 0xfafd871bUL;
-	return x;
+	if(n <= 1)
+		return 0;
+
+	r = fastrand1();
+	if(r < (1ULL<<31)-n)  // avoid computing max in common case
+		return r%n;
+
+	max = (1ULL<<31)/n * n;
+	while(r >= max)
+		r = fastrand1();
+	return r%n;
 }
-- 
2.50.0