cmd/link: use a two-pass approach for trampoline insertion

Currently in the linker, for trampoline insertion it does a one-pass
approach, where it assigns addresses for each function and inserts
trampolines on the go. For this to work and not to emit too many
unnecessary trampolines, the functions need to be laid out in
dependency order, so a direct call's target is always as a known
address (or known to be not too far).

This mostly works, but there are a few exceptions:
- linkname can break dependency tree and cause cycles.
- in internal linking mode, on some platforms, some calls are turned
  into calls via PLT, but the PLT stubs are inserted rather late.

Also, this is expensive in that it has to investigate all CALL
relocations.

This CL changes it to use a two-pass approach. The first pass is
just to assign addresses without inserting any trampolines, assuming
the program is not too big. If this succeeds, no extra work needs to
be done. If this fails, start over and insert trampolines for too-
far targets as well as targets with unknown addresses. This should
make it faster for small programs (most cases) and generate fewer
conservative trampolines.

Change-Id: Ib13e01f38ec6dfbef1cd446b06da33ee17bded5d
Reviewed-on: https://go-review.googlesource.com/c/go/+/314450
Trust: Cherry Zhang <cherryyz@google.com>
Reviewed-by: Than McIntosh <thanm@google.com>

4 files changed, 103 insertions, 44 deletions

diff --git a/src/cmd/link/internal/arm/obj.go b/src/cmd/link/internal/arm/obj.go
index fed8dce4de..b7d149851c 100644
--- a/src/cmd/link/internal/arm/obj.go
+++ b/src/cmd/link/internal/arm/obj.go
@@ -45,6 +45,7 @@ func Init() (*sys.Arch, ld.Arch) {
 		Minalign:   minAlign,
 		Dwarfregsp: dwarfRegSP,
 		Dwarfreglr: dwarfRegLR,
+		TrampLimit: 0x1c00000, // 24-bit signed offset * 4, leave room for PLT etc.
 
 		Plan9Magic: 0x647,
 
diff --git a/src/cmd/link/internal/ld/data.go b/src/cmd/link/internal/ld/data.go
index a135fe8fd2..a5e6d37f29 100644
--- a/src/cmd/link/internal/ld/data.go
+++ b/src/cmd/link/internal/ld/data.go
@@ -117,7 +117,6 @@ func trampoline(ctxt *Link, s loader.Sym) {
 
 		thearch.Trampoline(ctxt, ldr, ri, rs, s)
 	}
-
 }
 
 // FoldSubSymbolOffset computes the offset of symbol s to its top-level outer
@@ -2203,23 +2202,87 @@ func (ctxt *Link) textaddress() {
 		ctxt.Textp[0] = text
 	}
 
-	va := uint64(Rnd(*FlagTextAddr, int64(Funcalign)))
+	start := uint64(Rnd(*FlagTextAddr, int64(Funcalign)))
+	va := start
 	n := 1
 	sect.Vaddr = va
-	ntramps := 0
-	for _, s := range ctxt.Textp {
-		sect, n, va = assignAddress(ctxt, sect, n, s, va, false)
 
-		trampoline(ctxt, s) // resolve jumps, may add trampolines if jump too far
+	limit := thearch.TrampLimit
+	if limit == 0 {
+		limit = 1 << 63 // unlimited
+	}
+	if *FlagDebugTextSize != 0 {
+		limit = uint64(*FlagDebugTextSize)
+	}
+	if *FlagDebugTramp > 1 {
+		limit = 1 // debug mode, force generating trampolines for everything
+	}
+
+	if ctxt.IsAIX() && ctxt.IsExternal() {
+		// On AIX, normally we won't generate direct calls to external symbols,
+		// except in one test, cmd/go/testdata/script/link_syso_issue33139.txt.
+		// That test doesn't make much sense, and I'm not sure it ever works.
+		// Just generate trampoline for now (which will turn a direct call to
+		// an indirect call, which at least builds).
+		limit = 1
+	}
+
+	// First pass: assign addresses assuming the program is small and
+	// don't generate trampolines.
+	big := false
+	for _, s := range ctxt.Textp {
+		sect, n, va = assignAddress(ctxt, sect, n, s, va, false, big)
+		if va-start >= limit {
+			big = true
+			break
+		}
+	}
 
-		// lay down trampolines after each function
-		for ; ntramps < len(ctxt.tramps); ntramps++ {
-			tramp := ctxt.tramps[ntramps]
-			if ctxt.IsAIX() && strings.HasPrefix(ldr.SymName(tramp), "runtime.text.") {
-				// Already set in assignAddress
+	// Second pass: only if it is too big, insert trampolines for too-far
+	// jumps and targets with unknown addresses.
+	if big {
+		// reset addresses
+		for _, s := range ctxt.Textp {
+			if ldr.OuterSym(s) != 0 || s == text {
 				continue
 			}
-			sect, n, va = assignAddress(ctxt, sect, n, tramp, va, true)
+			oldv := ldr.SymValue(s)
+			for sub := s; sub != 0; sub = ldr.SubSym(sub) {
+				ldr.SetSymValue(sub, ldr.SymValue(sub)-oldv)
+			}
+		}
+		va = start
+
+		ntramps := 0
+		for _, s := range ctxt.Textp {
+			sect, n, va = assignAddress(ctxt, sect, n, s, va, false, big)
+
+			trampoline(ctxt, s) // resolve jumps, may add trampolines if jump too far
+
+			// lay down trampolines after each function
+			for ; ntramps < len(ctxt.tramps); ntramps++ {
+				tramp := ctxt.tramps[ntramps]
+				if ctxt.IsAIX() && strings.HasPrefix(ldr.SymName(tramp), "runtime.text.") {
+					// Already set in assignAddress
+					continue
+				}
+				sect, n, va = assignAddress(ctxt, sect, n, tramp, va, true, big)
+			}
+		}
+
+		// merge tramps into Textp, keeping Textp in address order
+		if ntramps != 0 {
+			newtextp := make([]loader.Sym, 0, len(ctxt.Textp)+ntramps)
+			i := 0
+			for _, s := range ctxt.Textp {
+				for ; i < ntramps && ldr.SymValue(ctxt.tramps[i]) < ldr.SymValue(s); i++ {
+					newtextp = append(newtextp, ctxt.tramps[i])
+				}
+				newtextp = append(newtextp, s)
+			}
+			newtextp = append(newtextp, ctxt.tramps[i:ntramps]...)
+
+			ctxt.Textp = newtextp
 		}
 	}
 
@@ -2231,25 +2294,10 @@ func (ctxt *Link) textaddress() {
 		ldr.SetSymValue(etext, int64(va))
 		ldr.SetSymValue(text, int64(Segtext.Sections[0].Vaddr))
 	}
-
-	// merge tramps into Textp, keeping Textp in address order
-	if ntramps != 0 {
-		newtextp := make([]loader.Sym, 0, len(ctxt.Textp)+ntramps)
-		i := 0
-		for _, s := range ctxt.Textp {
-			for ; i < ntramps && ldr.SymValue(ctxt.tramps[i]) < ldr.SymValue(s); i++ {
-				newtextp = append(newtextp, ctxt.tramps[i])
-			}
-			newtextp = append(newtextp, s)
-		}
-		newtextp = append(newtextp, ctxt.tramps[i:ntramps]...)
-
-		ctxt.Textp = newtextp
-	}
 }
 
 // assigns address for a text symbol, returns (possibly new) section, its number, and the address
-func assignAddress(ctxt *Link, sect *sym.Section, n int, s loader.Sym, va uint64, isTramp bool) (*sym.Section, int, uint64) {
+func assignAddress(ctxt *Link, sect *sym.Section, n int, s loader.Sym, va uint64, isTramp, big bool) (*sym.Section, int, uint64) {
 	ldr := ctxt.loader
 	if thearch.AssignAddress != nil {
 		return thearch.AssignAddress(ldr, sect, n, s, va, isTramp)
@@ -2277,20 +2325,19 @@ func assignAddress(ctxt *Link, sect *sym.Section, n int, s loader.Sym, va uint64
 	// On ppc64x a text section should not be larger than 2^26 bytes due to the size of
 	// call target offset field in the bl instruction.  Splitting into smaller text
 	// sections smaller than this limit allows the GNU linker to modify the long calls
-	// appropriately.  The limit allows for the space needed for tables inserted by the linker.
-
+	// appropriately. The limit allows for the space needed for tables inserted by the linker.
+	//
 	// If this function doesn't fit in the current text section, then create a new one.
-
+	//
 	// Only break at outermost syms.
+	if ctxt.Arch.InFamily(sys.PPC64) && ldr.OuterSym(s) == 0 && ctxt.IsExternal() && big {
+		// For debugging purposes, allow text size limit to be cranked down,
+		// so as to stress test the code that handles multiple text sections.
+		var textSizelimit uint64 = thearch.TrampLimit
+		if *FlagDebugTextSize != 0 {
+			textSizelimit = uint64(*FlagDebugTextSize)
+		}
 
-	// For debugging purposes, allow text size limit to be cranked down,
-	// so as to stress test the code that handles multiple text sections.
-	var textSizelimit uint64 = 0x1c00000
-	if *FlagDebugTextSize != 0 {
-		textSizelimit = uint64(*FlagDebugTextSize)
-	}
-
-	if ctxt.Arch.InFamily(sys.PPC64) && ldr.OuterSym(s) == 0 && ctxt.IsExternal() {
 		// Sanity check: make sure the limit is larger than any
 		// individual text symbol.
 		if funcsize > textSizelimit {
@@ -2346,6 +2393,9 @@ func assignAddress(ctxt *Link, sect *sym.Section, n int, s loader.Sym, va uint64
 	ldr.SetSymValue(s, 0)
 	for sub := s; sub != 0; sub = ldr.SubSym(sub) {
 		ldr.SetSymValue(sub, ldr.SymValue(sub)+int64(va))
+		if ctxt.Debugvlog > 2 {
+			fmt.Println("assign text address:", ldr.SymName(sub), ldr.SymValue(sub))
+		}
 	}
 
 	va += funcsize
diff --git a/src/cmd/link/internal/ld/lib.go b/src/cmd/link/internal/ld/lib.go
index 7408526076..e9349a4b3e 100644
--- a/src/cmd/link/internal/ld/lib.go
+++ b/src/cmd/link/internal/ld/lib.go
@@ -177,11 +177,18 @@ func (ctxt *Link) setArchSyms() {
 }
 
 type Arch struct {
-	Funcalign      int
-	Maxalign       int
-	Minalign       int
-	Dwarfregsp     int
-	Dwarfreglr     int
+	Funcalign  int
+	Maxalign   int
+	Minalign   int
+	Dwarfregsp int
+	Dwarfreglr int
+
+	// Threshold of total text size, used for trampoline insertion. If the total
+	// text size is smaller than TrampLimit, we won't need to insert trampolines.
+	// It is pretty close to the offset range of a direct CALL machine instruction.
+	// We leave some room for extra stuff like PLT stubs.
+	TrampLimit uint64
+
 	Androiddynld   string
 	Linuxdynld     string
 	Freebsddynld   string
diff --git a/src/cmd/link/internal/ppc64/obj.go b/src/cmd/link/internal/ppc64/obj.go
index 54d4606487..f56fa76b5b 100644
--- a/src/cmd/link/internal/ppc64/obj.go
+++ b/src/cmd/link/internal/ppc64/obj.go
@@ -49,6 +49,7 @@ func Init() (*sys.Arch, ld.Arch) {
 		Minalign:        minAlign,
 		Dwarfregsp:      dwarfRegSP,
 		Dwarfreglr:      dwarfRegLR,
+		TrampLimit:      0x1c00000,
 		WriteTextBlocks: true,
 
 		Adddynrel:        adddynrel,