cmd/link: establish dependable package initialization order

(This is a retry of CL 462035 which was reverted at 474976.
The only change from that CL is the aix fix SRODATA->SNOPTRDATA
at inittask.go:141)

As described here:

https://github.com/golang/go/issues/31636#issuecomment-493271830

"Find the lexically earliest package that is not initialized yet,
but has had all its dependencies initialized, initialize that package,
 and repeat."

Simplify the runtime a bit, by just computing the ordering required
in the linker and giving a list to the runtime.

Update #31636
Fixes #57411

RELNOTE=yes

Change-Id: I28c09451d6aa677d7394c179d23c2c02c503fc56
Reviewed-on: https://go-review.googlesource.com/c/go/+/478916
Reviewed-by: Than McIntosh <thanm@google.com>
Reviewed-by: Cherry Mui <cherryyz@google.com>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>

6 files changed, 253 insertions, 0 deletions

diff --git a/src/cmd/link/internal/ld/deadcode.go b/src/cmd/link/internal/ld/deadcode.go
index 307a6dd42f..c80bacd92c 100644
--- a/src/cmd/link/internal/ld/deadcode.go
+++ b/src/cmd/link/internal/ld/deadcode.go
@@ -113,6 +113,9 @@ func (d *deadcodePass) init() {
 	if d.mapinitnoop == 0 {
 		panic("could not look up runtime.mapinitnoop")
 	}
+	if d.ctxt.mainInittasks != 0 {
+		d.mark(d.ctxt.mainInittasks, 0)
+	}
 }
 
 func (d *deadcodePass) flood() {
@@ -208,6 +211,11 @@ func (d *deadcodePass) flood() {
 				}
 				d.genericIfaceMethod[name] = true
 				continue // don't mark referenced symbol - it is not needed in the final binary.
+			case objabi.R_INITORDER:
+				// inittasks has already run, so any R_INITORDER links are now
+				// superfluous - the only live inittask records are those which are
+				// in a scheduled list somewhere (e.g. runtime.moduledata.inittasks).
+				continue
 			}
 			rs := r.Sym()
 			if isgotype && usedInIface && d.ldr.IsGoType(rs) && !d.ldr.AttrUsedInIface(rs) {
diff --git a/src/cmd/link/internal/ld/heap.go b/src/cmd/link/internal/ld/heap.go
index ea2d772bee..286a61b78f 100644
--- a/src/cmd/link/internal/ld/heap.go
+++ b/src/cmd/link/internal/ld/heap.go
@@ -52,3 +52,50 @@ func (h *heap) pop() loader.Sym {
 }
 
 func (h *heap) empty() bool { return len(*h) == 0 }
+
+// Same as heap, but sorts alphabetically instead of by index.
+// (Note that performance is not so critical here, as it is
+// in the case above. Some simplification might be in order.)
+type lexHeap []loader.Sym
+
+func (h *lexHeap) push(ldr *loader.Loader, s loader.Sym) {
+	*h = append(*h, s)
+	// sift up
+	n := len(*h) - 1
+	for n > 0 {
+		p := (n - 1) / 2 // parent
+		if ldr.SymName((*h)[p]) <= ldr.SymName((*h)[n]) {
+			break
+		}
+		(*h)[n], (*h)[p] = (*h)[p], (*h)[n]
+		n = p
+	}
+}
+
+func (h *lexHeap) pop(ldr *loader.Loader) loader.Sym {
+	r := (*h)[0]
+	n := len(*h) - 1
+	(*h)[0] = (*h)[n]
+	*h = (*h)[:n]
+
+	// sift down
+	i := 0
+	for {
+		c := 2*i + 1 // left child
+		if c >= n {
+			break
+		}
+		if c1 := c + 1; c1 < n && ldr.SymName((*h)[c1]) < ldr.SymName((*h)[c]) {
+			c = c1 // right child
+		}
+		if ldr.SymName((*h)[i]) <= ldr.SymName((*h)[c]) {
+			break
+		}
+		(*h)[i], (*h)[c] = (*h)[c], (*h)[i]
+		i = c
+	}
+
+	return r
+}
+
+func (h *lexHeap) empty() bool { return len(*h) == 0 }
diff --git a/src/cmd/link/internal/ld/inittask.go b/src/cmd/link/internal/ld/inittask.go
new file mode 100644
index 0000000000..0699107cd0
--- /dev/null
+++ b/src/cmd/link/internal/ld/inittask.go
@@ -0,0 +1,175 @@
+// Copyright 2022 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 ld
+
+import (
+	"cmd/internal/objabi"
+	"cmd/link/internal/loader"
+	"cmd/link/internal/sym"
+	"fmt"
+	"sort"
+)
+
+// Inittasks finds inittask records, figures out a good
+// order to execute them in, and emits that order for the
+// runtime to use.
+//
+// An inittask represents the initialization code that needs
+// to be run for a package. For package p, the p..inittask
+// symbol contains a list of init functions to run, both
+// explicit user init functions and implicit compiler-generated
+// init functions for initializing global variables like maps.
+//
+// In addition, inittask records have dependencies between each
+// other, mirroring the import dependencies. So if package p
+// imports package q, then there will be a dependency p -> q.
+// We can't initialize package p until after package q has
+// already been initialized.
+//
+// Package dependencies are encoded with relocations. If package
+// p imports package q, then package p's inittask record will
+// have a R_INITORDER relocation pointing to package q's inittask
+// record. See cmd/compile/internal/pkginit/init.go.
+//
+// This function computes an ordering of all of the inittask
+// records so that the order respects all the dependencies,
+// and given that restriction, orders the inittasks in
+// lexicographic order.
+func (ctxt *Link) inittasks() {
+	switch ctxt.BuildMode {
+	case BuildModeExe, BuildModePIE, BuildModeCArchive, BuildModeCShared:
+		// Normally the inittask list will be run on program startup.
+		ctxt.mainInittasks = ctxt.inittaskSym("main..inittask", "go:main.inittasks")
+	case BuildModePlugin:
+		// For plugins, the list will be run on plugin load.
+		ctxt.mainInittasks = ctxt.inittaskSym(fmt.Sprintf("%s..inittask", objabi.PathToPrefix(*flagPluginPath)), "go:plugin.inittasks")
+		// Make symbol local so multiple plugins don't clobber each other's inittask list.
+		ctxt.loader.SetAttrLocal(ctxt.mainInittasks, true)
+	case BuildModeShared:
+		// Nothing to do. The inittask list will be built by
+		// the final build (with the -linkshared option).
+	default:
+		Exitf("unhandled build mode %d", ctxt.BuildMode)
+	}
+
+	// If the runtime is one of the packages we are building,
+	// initialize the runtime_inittasks variable.
+	ldr := ctxt.loader
+	if ldr.Lookup("runtime.runtime_inittasks", 0) != 0 {
+		t := ctxt.inittaskSym("runtime..inittask", "go:runtime.inittasks")
+
+		// This slice header is already defined in runtime/proc.go, so we update it here with new contents.
+		sh := ldr.Lookup("runtime.runtime_inittasks", 0)
+		sb := ldr.MakeSymbolUpdater(sh)
+		sb.SetSize(0)
+		sb.SetType(sym.SNOPTRDATA) // Could be SRODATA, but see issue 58857.
+		sb.AddAddr(ctxt.Arch, t)
+		sb.AddUint(ctxt.Arch, uint64(ldr.SymSize(t)/int64(ctxt.Arch.PtrSize)))
+		sb.AddUint(ctxt.Arch, uint64(ldr.SymSize(t)/int64(ctxt.Arch.PtrSize)))
+	}
+}
+
+// inittaskSym builds a symbol containing pointers to all the inittasks
+// that need to be run, given the root inittask symbol.
+func (ctxt *Link) inittaskSym(rootName, symName string) loader.Sym {
+	ldr := ctxt.loader
+	root := ldr.Lookup(rootName, 0)
+	if root == 0 {
+		// Nothing to do
+		return 0
+	}
+
+	// Edges record dependencies between packages.
+	// {from,to} is in edges if from's package imports to's package.
+	// This list is used to implement reverse edge lookups.
+	type edge struct {
+		from, to loader.Sym
+	}
+	var edges []edge
+
+	// List of packages that are ready to schedule. We use a lexicographic
+	// ordered heap to pick the lexically earliest uninitialized but
+	// inititalizeable package at each step.
+	var h lexHeap
+
+	// m maps from an inittask symbol for package p to the number of
+	// p's direct imports that have not yet been scheduled.
+	m := map[loader.Sym]int{}
+
+	// Find all reachable inittask records from the root.
+	// Keep track of the dependency edges between them in edges.
+	// Keep track of how many imports each package has in m.
+	// q is the list of found but not yet explored packages.
+	var q []loader.Sym
+	m[root] = 0
+	q = append(q, root)
+	for len(q) > 0 {
+		x := q[len(q)-1]
+		q = q[:len(q)-1]
+		relocs := ldr.Relocs(x)
+		n := relocs.Count()
+		ndeps := 0
+		for i := 0; i < n; i++ {
+			r := relocs.At(i)
+			if r.Type() != objabi.R_INITORDER {
+				continue
+			}
+			ndeps++
+			s := r.Sym()
+			edges = append(edges, edge{from: x, to: s})
+			if _, ok := m[s]; ok {
+				continue // already found
+			}
+			q = append(q, s)
+			m[s] = 0 // mark as found
+		}
+		m[x] = ndeps
+		if ndeps == 0 {
+			h.push(ldr, x)
+		}
+	}
+
+	// Sort edges so we can look them up by edge destination.
+	sort.Slice(edges, func(i, j int) bool {
+		return edges[i].to < edges[j].to
+	})
+
+	// Figure out the schedule.
+	sched := ldr.MakeSymbolBuilder(symName)
+	sched.SetType(sym.SNOPTRDATA) // Could be SRODATA, but see isue 58857.
+	for !h.empty() {
+		// Pick the lexicographically first initializable package.
+		s := h.pop(ldr)
+
+		// Add s to the schedule.
+		if ldr.SymSize(s) > 8 {
+			// Note: don't add s if it has no functions to run. We need
+			// s during linking to compute an ordering, but the runtime
+			// doesn't need to know about it. About 1/2 of stdlib packages
+			// fit in this bucket.
+			sched.AddAddr(ctxt.Arch, s)
+		}
+
+		// Find all incoming edges into s.
+		a := sort.Search(len(edges), func(i int) bool { return edges[i].to >= s })
+		b := sort.Search(len(edges), func(i int) bool { return edges[i].to > s })
+
+		// Decrement the import count for all packages that import s.
+		// If the count reaches 0, that package is now ready to schedule.
+		for _, e := range edges[a:b] {
+			m[e.from]--
+			if m[e.from] == 0 {
+				h.push(ldr, e.from)
+			}
+		}
+	}
+
+	for s, n := range m {
+		if n != 0 {
+			Exitf("inittask for %s is not schedulable %d", ldr.SymName(s), n)
+		}
+	}
+	return sched.Sym()
+}
diff --git a/src/cmd/link/internal/ld/lib.go b/src/cmd/link/internal/ld/lib.go
index 02c6908407..b2a7daba23 100644
--- a/src/cmd/link/internal/ld/lib.go
+++ b/src/cmd/link/internal/ld/lib.go
@@ -119,6 +119,10 @@ type ArchSyms struct {
 	DynStr  loader.Sym
 
 	unreachableMethod loader.Sym
+
+	// Symbol containing a list of all the inittasks that need
+	// to be run at startup.
+	mainInittasks loader.Sym
 }
 
 // mkArchSym is a helper for setArchSyms, to set up a special symbol.
diff --git a/src/cmd/link/internal/ld/main.go b/src/cmd/link/internal/ld/main.go
index 9042a4db32..093bb4365b 100644
--- a/src/cmd/link/internal/ld/main.go
+++ b/src/cmd/link/internal/ld/main.go
@@ -276,6 +276,9 @@ func Main(arch *sys.Arch, theArch Arch) {
 	bench.Start("loadlib")
 	ctxt.loadlib()
 
+	bench.Start("inittasks")
+	ctxt.inittasks()
+
 	bench.Start("deadcode")
 	deadcode(ctxt)
 
diff --git a/src/cmd/link/internal/ld/symtab.go b/src/cmd/link/internal/ld/symtab.go
index 21a1466c49..5f5f2e1d0b 100644
--- a/src/cmd/link/internal/ld/symtab.go
+++ b/src/cmd/link/internal/ld/symtab.go
@@ -765,6 +765,22 @@ func (ctxt *Link) symtab(pcln *pclntab) []sym.SymKind {
 		moduledata.AddUint(ctxt.Arch, 0)
 		moduledata.AddUint(ctxt.Arch, 0)
 	}
+	// Add inittasks slice
+	t := ctxt.mainInittasks
+	if t != 0 {
+		moduledata.AddAddr(ctxt.Arch, t)
+		moduledata.AddUint(ctxt.Arch, uint64(ldr.SymSize(t)/int64(ctxt.Arch.PtrSize)))
+		moduledata.AddUint(ctxt.Arch, uint64(ldr.SymSize(t)/int64(ctxt.Arch.PtrSize)))
+	} else {
+		// Some build modes have no inittasks, like a shared library.
+		// Its inittask list will be constructed by a higher-level
+		// linking step.
+		// This branch can also happen if there are no init tasks at all.
+		moduledata.AddUint(ctxt.Arch, 0)
+		moduledata.AddUint(ctxt.Arch, 0)
+		moduledata.AddUint(ctxt.Arch, 0)
+	}
+
 	if len(ctxt.Shlibs) > 0 {
 		thismodulename := filepath.Base(*flagOutfile)
 		switch ctxt.BuildMode {