From 90eca36a23cf5ec59a46626771f8074e2b68df60 Mon Sep 17 00:00:00 2001
From: Dmitriy Vyukov <dvyukov@google.com>
Date: Tue, 21 Jan 2014 10:24:42 +0400
Subject: [PATCH] runtime: ensure fair scheduling during frequent GCs What was
 happenning is as follows: Each writer goroutine always triggers GC during its
 scheduling quntum. After GC goroutines are shuffled so that the timer
 goroutine is always second in the queue. This repeats infinitely, causing
 timer goroutine starvation. Fixes #7126.

R=golang-codereviews, shanemhansen, khr, khr
CC=golang-codereviews
https://golang.org/cl/53080043
---
 src/pkg/runtime/proc.c       | 27 +++++++++++++++++-----
 src/pkg/runtime/proc_test.go | 43 ++++++++++++++++++++++++++++++++++++
 2 files changed, 65 insertions(+), 5 deletions(-)

diff --git a/src/pkg/runtime/proc.c b/src/pkg/runtime/proc.c
index 29b6a7c763..693cacaa58 100644
--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -2207,6 +2207,7 @@ static void
 procresize(int32 new)
 {
 	int32 i, old;
+	bool empty;
 	G *gp;
 	P *p;
 
@@ -2231,11 +2232,27 @@ procresize(int32 new)
 	}
 
 	// redistribute runnable G's evenly
-	// collect all runnable goroutines in global queue
-	for(i = 0; i < old; i++) {
-		p = runtime·allp[i];
-		while(gp = runqget(p))
-			globrunqput(gp);
+	// collect all runnable goroutines in global queue preserving FIFO order
+	// FIFO order is required to ensure fairness even during frequent GCs
+	// see http://golang.org/issue/7126
+	empty = false;
+	while(!empty) {
+		empty = true;
+		for(i = 0; i < old; i++) {
+			p = runtime·allp[i];
+			if(p->runqhead == p->runqtail)
+				continue;
+			empty = false;
+			// pop from tail of local queue
+			p->runqtail--;
+			gp = p->runq[p->runqtail%nelem(p->runq)];
+			// push onto head of global queue
+			gp->schedlink = runtime·sched.runqhead;
+			runtime·sched.runqhead = gp;
+			if(runtime·sched.runqtail == nil)
+				runtime·sched.runqtail = gp;
+			runtime·sched.runqsize++;
+		}
 	}
 	// fill local queues with at most nelem(p->runq)/2 goroutines
 	// start at 1 because current M already executes some G and will acquire allp[0] below,
diff --git a/src/pkg/runtime/proc_test.go b/src/pkg/runtime/proc_test.go
index dd70ed97d7..d3f1f8bb1c 100644
--- a/src/pkg/runtime/proc_test.go
+++ b/src/pkg/runtime/proc_test.go
@@ -244,6 +244,49 @@ func TestPreemptionGC(t *testing.T) {
 	atomic.StoreUint32(&stop, 1)
 }
 
+func TestGCFairness(t *testing.T) {
+	output := executeTest(t, testGCFairnessSource, nil)
+	want := "OK\n"
+	if output != want {
+		t.Fatalf("want %s, got %s\n", want, output)
+	}
+}
+
+const testGCFairnessSource = `
+package main
+
+import (
+	"fmt"
+	"os"
+	"runtime"
+	"time"
+)
+
+func main() {
+	runtime.GOMAXPROCS(1)
+	f, err := os.Open("/dev/null")
+	if os.IsNotExist(err) {
+		// This test tests what it is intended to test only if writes are fast.
+		// If there is no /dev/null, we just don't execute the test.
+		fmt.Println("OK\n")
+		return
+	}
+	if err != nil {
+		fmt.Println(err)
+		os.Exit(1)
+	}
+	for i := 0; i < 2; i++ {
+		go func() {
+			for {
+				f.Write([]byte("."))
+			}
+		}()
+	}
+	time.Sleep(10 * time.Millisecond)
+	fmt.Println("OK")
+}
+`
+
 func stackGrowthRecursive(i int) {
 	var pad [128]uint64
 	if i != 0 && pad[0] == 0 {
-- 
2.48.1