cmd/dist: build packages in parallel, make code more Go-like

(Changed modified by bradfitz from original rsc version)

Change-Id: I8ea40044c325f333a13d48b59b4795b02c579533
Reviewed-on: https://go-review.googlesource.com/14026
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

4 files changed, 162 insertions, 105 deletions

diff --git a/src/cmd/dist/build.go b/src/cmd/dist/build.go
index 184f9738b4..dba59c66f5 100644
--- a/src/cmd/dist/build.go
+++ b/src/cmd/dist/build.go
@@ -11,7 +11,9 @@ import (
 	"os"
 	"os/exec"
 	"path/filepath"
+	"sort"
 	"strings"
+	"sync"
 )
 
 // Initialization for any invocation.
@@ -487,9 +489,20 @@ var gentab = []struct {
 	{"anames9.c", nil},
 }
 
+// installed maps from a dir name (as given to install) to a chan
+// closed when the dir's package is installed.
+var installed = make(map[string]chan struct{})
+
 // install installs the library, package, or binary associated with dir,
 // which is relative to $GOROOT/src.
 func install(dir string) {
+	if ch, ok := installed[dir]; ok {
+		defer close(ch)
+	}
+	for _, dep := range builddeps[dir] {
+		<-installed[dep]
+	}
+
 	if vflag > 0 {
 		if goos != gohostos || goarch != gohostarch {
 			errprintf("%s (%s/%s)\n", dir, goos, goarch)
@@ -498,6 +511,9 @@ func install(dir string) {
 		}
 	}
 
+	workdir := pathf("%s/%s", workdir, dir)
+	xmkdirall(workdir)
+
 	var clean []string
 	defer func() {
 		for _, name := range clean {
@@ -673,6 +689,7 @@ func install(dir string) {
 	run(path, CheckExit|ShowOutput, compile...)
 
 	// Compile the files.
+	var wg sync.WaitGroup
 	for _, p := range files {
 		if !strings.HasSuffix(p, ".s") {
 			continue
@@ -695,14 +712,14 @@ func install(dir string) {
 		// Change the last character of the output file (which was c or s).
 		b = b[:len(b)-1] + "o"
 		compile = append(compile, "-o", b, p)
-		bgrun(path, compile...)
+		bgrun(&wg, path, compile...)
 
 		link = append(link, b)
 		if doclean {
 			clean = append(clean, b)
 		}
 	}
-	bgwait()
+	bgwait(&wg)
 
 	if ispackcmd {
 		xremove(link[targ])
@@ -839,62 +856,19 @@ func dopack(dst, src string, extra []string) {
 	writefile(bdst.String(), dst, 0)
 }
 
-// buildorder records the order of builds for the 'go bootstrap' command.
-// The Go packages and commands must be in dependency order,
-// maintained by hand, but the order doesn't change often.
-var buildorder = []string{
-	// Go libraries and programs for bootstrap.
-	"runtime",
-	"errors",
-	"sync/atomic",
-	"sync",
-	"internal/singleflight",
-	"io",
-	"unicode",
-	"unicode/utf8",
-	"unicode/utf16",
-	"bytes",
-	"math",
-	"strings",
-	"strconv",
-	"bufio",
-	"sort",
-	"container/heap",
-	"encoding/base64",
-	"syscall",
-	"internal/syscall/windows/registry",
-	"time",
-	"internal/syscall/windows",
-	"os",
-	"reflect",
-	"fmt",
-	"encoding",
-	"encoding/binary",
-	"encoding/json",
-	"flag",
-	"path/filepath",
-	"path",
-	"io/ioutil",
-	"log",
-	"regexp/syntax",
-	"regexp",
-	"go/token",
-	"go/scanner",
-	"go/ast",
-	"go/parser",
-	"os/exec",
-	"os/signal",
-	"net/url",
-	"text/template/parse",
-	"text/template",
-	"go/doc",
-	"go/build",
-	"hash",
-	"crypto",
-	"crypto/sha1",
-	"debug/dwarf",
-	"debug/elf",
-	"cmd/go",
+// builddeps records the build dependencies for the 'go bootstrap' command.
+// It is a map[string][]string and generated by mkdeps.bash into deps.go.
+
+// buildlist is the list of directories being built, sorted by name.
+var buildlist = makeBuildlist()
+
+func makeBuildlist() []string {
+	var all []string
+	for dir := range builddeps {
+		all = append(all, dir)
+	}
+	sort.Strings(all)
+	return all
 }
 
 var runtimegen = []string{
@@ -903,7 +877,7 @@ var runtimegen = []string{
 }
 
 func clean() {
-	for _, name := range buildorder {
+	for _, name := range buildlist {
 		path := pathf("%s/src/%s", goroot, name)
 		// Remove generated files.
 		for _, elem := range xreaddir(path) {
@@ -1044,19 +1018,30 @@ func cmdbootstrap() {
 	// than in a standard release like Go 1.4, so don't do this rebuild by default.
 	if false {
 		xprintf("##### Building Go toolchain using itself.\n")
-		for _, dir := range buildorder {
-			if dir == "cmd/go" {
-				break
-			}
-			install(dir)
+		for _, dir := range buildlist {
+			installed[dir] = make(chan struct{})
 		}
+		var wg sync.WaitGroup
+		for _, dir := range builddeps["cmd/go"] {
+			wg.Add(1)
+			dir := dir
+			go func() {
+				defer wg.Done()
+				install(dir)
+			}()
+		}
+		wg.Wait()
 		xprintf("\n")
 	}
 
 	xprintf("##### Building go_bootstrap for host, %s/%s.\n", gohostos, gohostarch)
-	for _, dir := range buildorder {
-		install(dir)
+	for _, dir := range buildlist {
+		installed[dir] = make(chan struct{})
+	}
+	for _, dir := range buildlist {
+		go install(dir)
 	}
+	<-installed["cmd/go"]
 
 	goos = oldgoos
 	goarch = oldgoarch
@@ -1065,6 +1050,7 @@ func cmdbootstrap() {
 
 	// Build runtime for actual goos/goarch too.
 	if goos != gohostos || goarch != gohostarch {
+		installed["runtime"] = make(chan struct{})
 		install("runtime")
 	}
 }
diff --git a/src/cmd/dist/deps.go b/src/cmd/dist/deps.go
new file mode 100644
index 0000000000..01d134e958
--- /dev/null
+++ b/src/cmd/dist/deps.go
@@ -0,0 +1,57 @@
+// generated by mkdeps.bash
+
+package main
+
+var builddeps = map[string][]string{
+	"bufio":                             {"bytes", "errors", "io", "runtime", "sync", "sync/atomic", "unicode", "unicode/utf8"},
+	"bytes":                             {"errors", "io", "runtime", "sync", "sync/atomic", "unicode", "unicode/utf8"},
+	"container/heap":                    {"runtime", "sort"},
+	"crypto":                            {"errors", "hash", "io", "math", "runtime", "strconv", "sync", "sync/atomic", "unicode/utf8"},
+	"crypto/sha1":                       {"crypto", "errors", "hash", "io", "math", "runtime", "strconv", "sync", "sync/atomic", "unicode/utf8"},
+	"debug/dwarf":                       {"encoding/binary", "errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "path", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"debug/elf":                         {"bytes", "debug/dwarf", "encoding/binary", "errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "path", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"encoding":                          {"runtime"},
+	"encoding/base64":                   {"errors", "io", "math", "runtime", "strconv", "sync", "sync/atomic", "unicode/utf8"},
+	"encoding/binary":                   {"errors", "io", "math", "reflect", "runtime", "strconv", "sync", "sync/atomic", "unicode/utf8"},
+	"encoding/json":                     {"bytes", "encoding", "encoding/base64", "errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"errors":                            {"runtime"},
+	"flag":                              {"errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "reflect", "runtime", "sort", "strconv", "sync", "sync/atomic", "syscall", "time", "unicode/utf16", "unicode/utf8"},
+	"fmt":                               {"errors", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "reflect", "runtime", "strconv", "sync", "sync/atomic", "syscall", "time", "unicode/utf16", "unicode/utf8"},
+	"go/ast":                            {"bytes", "errors", "fmt", "go/scanner", "go/token", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "path/filepath", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"go/build":                          {"bufio", "bytes", "errors", "fmt", "go/ast", "go/doc", "go/parser", "go/scanner", "go/token", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "io/ioutil", "log", "math", "net/url", "os", "path", "path/filepath", "reflect", "regexp", "regexp/syntax", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "text/template", "text/template/parse", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"go/doc":                            {"bytes", "errors", "fmt", "go/ast", "go/scanner", "go/token", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "io/ioutil", "math", "net/url", "os", "path", "path/filepath", "reflect", "regexp", "regexp/syntax", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "text/template", "text/template/parse", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"go/parser":                         {"bytes", "errors", "fmt", "go/ast", "go/scanner", "go/token", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "io/ioutil", "math", "os", "path/filepath", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"go/scanner":                        {"bytes", "errors", "fmt", "go/token", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "path/filepath", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"go/token":                          {"errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "reflect", "runtime", "sort", "strconv", "sync", "sync/atomic", "syscall", "time", "unicode/utf16", "unicode/utf8"},
+	"hash":                              {"errors", "io", "runtime", "sync", "sync/atomic"},
+	"internal/singleflight":             {"runtime", "sync", "sync/atomic"},
+	"internal/syscall/windows":          {"errors", "runtime", "sync", "sync/atomic", "syscall", "unicode/utf16"},
+	"internal/syscall/windows/registry": {"errors", "io", "runtime", "sync", "sync/atomic", "syscall", "unicode/utf16"},
+	"io":                  {"errors", "runtime", "sync", "sync/atomic"},
+	"io/ioutil":           {"bytes", "errors", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "path/filepath", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"log":                 {"errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "reflect", "runtime", "strconv", "sync", "sync/atomic", "syscall", "time", "unicode/utf16", "unicode/utf8"},
+	"math":                {"runtime"},
+	"net/url":             {"bytes", "errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"os":                  {"errors", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "runtime", "sync", "sync/atomic", "syscall", "time", "unicode/utf16", "unicode/utf8"},
+	"os/exec":             {"bytes", "errors", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "path/filepath", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"os/signal":           {"errors", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "os", "runtime", "sync", "sync/atomic", "syscall", "time", "unicode/utf16", "unicode/utf8"},
+	"path":                {"errors", "io", "runtime", "strings", "sync", "sync/atomic", "unicode", "unicode/utf8"},
+	"path/filepath":       {"bytes", "errors", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "os", "runtime", "sort", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"reflect":             {"errors", "math", "runtime", "strconv", "sync", "sync/atomic", "unicode/utf8"},
+	"regexp":              {"bytes", "errors", "io", "math", "regexp/syntax", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "unicode", "unicode/utf8"},
+	"regexp/syntax":       {"bytes", "errors", "io", "math", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "unicode", "unicode/utf8"},
+	"runtime":             {},
+	"sort":                {"runtime"},
+	"strconv":             {"errors", "math", "runtime", "unicode/utf8"},
+	"strings":             {"errors", "io", "runtime", "sync", "sync/atomic", "unicode", "unicode/utf8"},
+	"sync":                {"runtime", "sync/atomic"},
+	"sync/atomic":         {"runtime"},
+	"syscall":             {"errors", "runtime", "sync", "sync/atomic", "unicode/utf16"},
+	"text/template":       {"bytes", "errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "io/ioutil", "math", "net/url", "os", "path/filepath", "reflect", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "text/template/parse", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"text/template/parse": {"bytes", "errors", "fmt", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "math", "os", "reflect", "runtime", "strconv", "strings", "sync", "sync/atomic", "syscall", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+	"time":                {"errors", "internal/syscall/windows/registry", "io", "runtime", "sync", "sync/atomic", "syscall", "unicode/utf16"},
+	"unicode":             {"runtime"},
+	"unicode/utf16":       {"runtime"},
+	"unicode/utf8":        {"runtime"},
+	"cmd/go":              {"bufio", "bytes", "container/heap", "crypto", "crypto/sha1", "debug/dwarf", "debug/elf", "encoding", "encoding/base64", "encoding/binary", "encoding/json", "errors", "flag", "fmt", "go/ast", "go/build", "go/doc", "go/parser", "go/scanner", "go/token", "hash", "internal/singleflight", "internal/syscall/windows", "internal/syscall/windows/registry", "io", "io/ioutil", "log", "math", "net/url", "os", "os/exec", "os/signal", "path", "path/filepath", "reflect", "regexp", "regexp/syntax", "runtime", "sort", "strconv", "strings", "sync", "sync/atomic", "syscall", "text/template", "text/template/parse", "time", "unicode", "unicode/utf16", "unicode/utf8"},
+}
diff --git a/src/cmd/dist/mkdeps.bash b/src/cmd/dist/mkdeps.bash
new file mode 100755
index 0000000000..283d6bff81
--- /dev/null
+++ b/src/cmd/dist/mkdeps.bash
@@ -0,0 +1,19 @@
+#!/bin/bash
+
+set -e
+
+# Windows has the most dependencies.
+export GOOS=windows
+
+(
+	echo '// generated by mkdeps.bash'
+	echo
+	echo 'package main'
+	echo
+	echo 'var builddeps = map[string][]string{'
+
+	deps=$(GOOS=windows go list -tags cmd_go_bootstrap -f '{{join .Deps "\n"}}' cmd/go | grep -v '^unsafe$')
+	GOOS=windows go list -tags cmd_go_bootstrap -f '{{printf "%q" .ImportPath}}: { {{range .Deps}}{{if not (eq . "unsafe")}}{{printf "%q" .}}, {{end}}{{end}} },' $deps cmd/go
+
+	echo '}'
+) |gofmt >deps.go
diff --git a/src/cmd/dist/util.go b/src/cmd/dist/util.go
index 34cbf50282..2fcd9ca995 100644
--- a/src/cmd/dist/util.go
+++ b/src/cmd/dist/util.go
@@ -16,7 +16,6 @@ import (
 	"strconv"
 	"strings"
 	"sync"
-	"sync/atomic"
 	"time"
 )
 
@@ -109,7 +108,9 @@ func run(dir string, mode int, cmd ...string) string {
 		}
 		outputLock.Unlock()
 		if mode&Background != 0 {
-			bgdied.Done()
+			// Prevent fatal from waiting on our own goroutine's
+			// bghelper to exit:
+			bghelpers.Done()
 		}
 		fatal("FAILED: %v: %v", strings.Join(cmd, " "), err)
 	}
@@ -130,62 +131,60 @@ var (
 	bgwork = make(chan func(), 1e5)
 	bgdone = make(chan struct{}, 1e5)
 
-	bgdied sync.WaitGroup
-	nwork  int32
-	ndone  int32
+	bghelpers sync.WaitGroup
 
-	dying  = make(chan bool)
-	nfatal int32
+	dieOnce sync.Once // guards close of dying
+	dying   = make(chan struct{})
 )
 
 func bginit() {
-	bgdied.Add(maxbg)
+	bghelpers.Add(maxbg)
 	for i := 0; i < maxbg; i++ {
 		go bghelper()
 	}
 }
 
 func bghelper() {
+	defer bghelpers.Done()
 	for {
-		w := <-bgwork
-		w()
-
-		// Stop if we're dying.
-		if atomic.LoadInt32(&nfatal) > 0 {
-			bgdied.Done()
+		select {
+		case <-dying:
 			return
+		case w := <-bgwork:
+			// Dying takes precedence over doing more work.
+			select {
+			case <-dying:
+				return
+			default:
+				w()
+			}
 		}
 	}
 }
 
 // bgrun is like run but runs the command in the background.
 // CheckExit|ShowOutput mode is implied (since output cannot be returned).
-func bgrun(dir string, cmd ...string) {
+// bgrun adds 1 to wg immediately, and calls Done when the work completes.
+func bgrun(wg *sync.WaitGroup, dir string, cmd ...string) {
+	wg.Add(1)
 	bgwork <- func() {
+		defer wg.Done()
 		run(dir, CheckExit|ShowOutput|Background, cmd...)
 	}
 }
 
 // bgwait waits for pending bgruns to finish.
 // bgwait must be called from only a single goroutine at a time.
-func bgwait() {
-	var wg sync.WaitGroup
-	wg.Add(maxbg)
-	done := make(chan bool)
-	for i := 0; i < maxbg; i++ {
-		bgwork <- func() {
-			wg.Done()
-
-			// Hold up bg goroutine until either the wait finishes
-			// or the program starts dying due to a call to fatal.
-			select {
-			case <-dying:
-			case <-done:
-			}
-		}
+func bgwait(wg *sync.WaitGroup) {
+	done := make(chan struct{})
+	go func() {
+		wg.Wait()
+		close(done)
+	}()
+	select {
+	case <-done:
+	case <-dying:
 	}
-	wg.Wait()
-	close(done)
 }
 
 // xgetwd returns the current directory.
@@ -355,16 +354,12 @@ func xworkdir() string {
 func fatal(format string, args ...interface{}) {
 	fmt.Fprintf(os.Stderr, "go tool dist: %s\n", fmt.Sprintf(format, args...))
 
+	dieOnce.Do(func() { close(dying) })
+
 	// Wait for background goroutines to finish,
 	// so that exit handler that removes the work directory
 	// is not fighting with active writes or open files.
-	if atomic.AddInt32(&nfatal, 1) == 1 {
-		close(dying)
-	}
-	for i := 0; i < maxbg; i++ {
-		bgwork <- func() {} // wake up workers so they notice nfatal > 0
-	}
-	bgdied.Wait()
+	bghelpers.Wait()
 
 	xexit(2)
 }