cmd/link, runtime: remove typelinks

Instead of adding a typelinks section to a Go binary,
mark the start and end of the typelinked type descriptors.
The runtime can then step through the descriptors to find them all,
rather than relying on the extra linker-generated offset list.

The runtime steps through the type descriptors lazily,
as many Go programs don't need the typelinks list at all.

This reduces the size of cmd/go by 15K bytes, which isn't much
but it's not nothing.

A future CL will change the reflect package to use the type pointers
directly rather than converting to offsets and then back to type pointers.

For #6853

Change-Id: Id0af4ce81c5b1cea899fc92b6ff9d2db8ce4c267
Reviewed-on: https://go-review.googlesource.com/c/go/+/724261
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Ian Lance Taylor <iant@golang.org>

6 files changed, 112 insertions, 77 deletions

diff --git a/src/cmd/compile/internal/reflectdata/reflect.go b/src/cmd/compile/internal/reflectdata/reflect.go
index 324007ea79..8a2b15ab24 100644
--- a/src/cmd/compile/internal/reflectdata/reflect.go
+++ b/src/cmd/compile/internal/reflectdata/reflect.go
@@ -756,6 +756,9 @@ func writeType(t *types.Type) *obj.LSym {
 	// | method list, if any            |   dextratype
 	// +--------------------------------+                            - E
 
+	// runtime.moduleTypelinks is aware of this type layout,
+	// and must be changed if the layout change.
+
 	// UncommonType section is included if we have a name or a method.
 	extra := t.Sym() != nil || len(methods(t)) != 0
 
diff --git a/src/cmd/link/internal/ld/data.go b/src/cmd/link/internal/ld/data.go
index baf7dafce5..51163c2c8b 100644
--- a/src/cmd/link/internal/ld/data.go
+++ b/src/cmd/link/internal/ld/data.go
@@ -1535,6 +1535,10 @@ func fixZeroSizedSymbols(ctxt *Link) {
 	types.SetSize(8)
 	ldr.SetAttrSpecial(types.Sym(), false)
 
+	etypedesc := ldr.CreateSymForUpdate("runtime.etypedesc", 0)
+	etypedesc.SetType(sym.STYPE)
+	ldr.SetAttrSpecial(etypedesc.Sym(), false)
+
 	etypes := ldr.CreateSymForUpdate("runtime.etypes", 0)
 	etypes.SetType(sym.STYPE)
 	ldr.SetAttrSpecial(etypes.Sym(), false)
@@ -2124,16 +2128,6 @@ func (state *dodataState) allocateDataSections(ctxt *Link) {
 		xcoffUpdateOuterSize(ctxt, int64(sect.Length), sym.SPCLNTAB)
 	}
 
-	/* typelink */
-	sect = state.allocateNamedDataSection(segro, ".typelink", []sym.SymKind{sym.STYPELINK}, 04)
-
-	typelink := ldr.CreateSymForUpdate("runtime.typelink", 0)
-	ldr.SetSymSect(typelink.Sym(), sect)
-	typelink.SetType(sym.SRODATA)
-	state.datsize += typelink.Size()
-	state.checkdatsize(sym.STYPELINK)
-	sect.Length = uint64(state.datsize) - sect.Vaddr
-
 	/* read-only ELF, Mach-O sections */
 	state.allocateSingleSymSections(segro, sym.SELFROSECT, sym.SRODATA, 04)
 
@@ -2224,6 +2218,7 @@ func (state *dodataState) allocateDataSections(ctxt *Link) {
 
 	sect = createRelroSect(".go.type", sym.STYPE)
 	ldr.SetSymSect(ldr.LookupOrCreateSym("runtime.types", 0), sect)
+	ldr.SetSymSect(ldr.LookupOrCreateSym("runtime.etypedesc", 0), sect)
 	ldr.SetSymSect(ldr.LookupOrCreateSym("runtime.etypes", 0), sect)
 
 	sect = createRelroSect(".go.func", sym.SGOFUNC)
@@ -2358,39 +2353,107 @@ func (state *dodataState) dodataSect(ctxt *Link, symn sym.SymKind, syms []loader
 	}
 	zerobase = ldr.Lookup("runtime.zerobase", 0)
 
+	sortHeadTail := func(si, sj loader.Sym) (less bool, matched bool) {
+		switch {
+		case si == head, sj == tail:
+			return true, true
+		case sj == head, si == tail:
+			return false, true
+		}
+		return false, false
+	}
+
+	sortFn := func(i, j int) bool {
+		si, sj := sl[i].sym, sl[j].sym
+		isz, jsz := sl[i].sz, sl[j].sz
+		if ret, matched := sortHeadTail(si, sj); matched {
+			return ret
+		}
+		if sortBySize {
+			switch {
+			// put zerobase right after all the zero-sized symbols,
+			// so zero-sized symbols have the same address as zerobase.
+			case si == zerobase:
+				return jsz != 0 // zerobase < nonzero-sized, zerobase > zero-sized
+			case sj == zerobase:
+				return isz == 0 // 0-sized < zerobase, nonzero-sized > zerobase
+			case isz != jsz:
+				return isz < jsz
+			}
+		} else {
+			iname := sl[i].name
+			jname := sl[j].name
+			if iname != jname {
+				return iname < jname
+			}
+		}
+		return si < sj // break ties by symbol number
+	}
+
 	// Perform the sort.
-	if symn != sym.SPCLNTAB {
+	switch symn {
+	case sym.SPCLNTAB:
+		// PCLNTAB was built internally, and already has the proper order.
+
+	case sym.STYPE:
+		// Sort type descriptors with the typelink flag first,
+		// sorted by type string. The reflect package will use
+		// this to ensure that type descriptor pointers are unique.
+
+		// Compute all the type strings we need once.
+		typelinkStrings := make(map[loader.Sym]string)
+		for _, s := range syms {
+			if ldr.IsTypelink(s) {
+				typelinkStrings[s] = decodetypeStr(ldr, ctxt.Arch, s)
+			}
+		}
+
 		sort.Slice(sl, func(i, j int) bool {
 			si, sj := sl[i].sym, sl[j].sym
-			isz, jsz := sl[i].sz, sl[j].sz
-			switch {
-			case si == head, sj == tail:
-				return true
-			case sj == head, si == tail:
-				return false
+
+			// Sort head and tail regardless of typelink.
+			if ret, matched := sortHeadTail(si, sj); matched {
+				return ret
 			}
-			if sortBySize {
-				switch {
-				// put zerobase right after all the zero-sized symbols,
-				// so zero-sized symbols have the same address as zerobase.
-				case si == zerobase:
-					return jsz != 0 // zerobase < nonzero-sized, zerobase > zero-sized
-				case sj == zerobase:
-					return isz == 0 // 0-sized < zerobase, nonzero-sized > zerobase
-				case isz != jsz:
-					return isz < jsz
-				}
-			} else {
-				iname := sl[i].name
-				jname := sl[j].name
-				if iname != jname {
-					return iname < jname
+
+			iTypestr, iIsTypelink := typelinkStrings[si]
+			jTypestr, jIsTypelink := typelinkStrings[sj]
+
+			if iIsTypelink {
+				if jIsTypelink {
+					// typelink symbols sort by type string
+					return iTypestr < jTypestr
 				}
+
+				// typelink < non-typelink
+				return true
+			} else if jIsTypelink {
+				// non-typelink greater than typelink
+				return false
 			}
-			return si < sj // break ties by symbol number
+
+			// non-typelink symbols sort by size as usual
+			return sortFn(i, j)
 		})
-	} else {
-		// PCLNTAB was built internally, and already has the proper order.
+
+		// Find the end of the typelink descriptors.
+		// The offset starts at 1 to match the increment in
+		// createRelroSect in allocateDataSections.
+		// TODO: This wastes some space.
+		offset := int64(1)
+		for i := range sl {
+			si := sl[i].sym
+			if _, isTypelink := typelinkStrings[si]; !isTypelink {
+				break
+			}
+			offset = Rnd(offset, int64(symalign(ldr, si)))
+			offset += sl[i].sz
+		}
+
+		ldr.SetSymValue(ldr.LookupOrCreateSym("runtime.etypedesc", 0), offset)
+
+	default:
+		sort.Slice(sl, sortFn)
 	}
 
 	// Set alignment, construct result
@@ -3035,9 +3098,12 @@ func (ctxt *Link) address() []*sym.Segment {
 	ctxt.xdefine("runtime.rodata", sym.SRODATA, int64(rodata.Vaddr))
 	ctxt.xdefine("runtime.erodata", sym.SRODATA, int64(rodata.Vaddr+rodata.Length))
 	ctxt.xdefine("runtime.types", sym.SRODATA, int64(types.Vaddr))
+	// etypedesc was set to the offset from the symbol start in dodataSect.
+	s := ldr.Lookup("runtime.etypedesc", 0)
+	ctxt.xdefine("runtime.etypedesc", sym.SRODATA, int64(types.Vaddr+uint64(ldr.SymValue(s))))
 	ctxt.xdefine("runtime.etypes", sym.SRODATA, int64(types.Vaddr+types.Length))
 
-	s := ldr.Lookup("runtime.gcdata", 0)
+	s = ldr.Lookup("runtime.gcdata", 0)
 	ldr.SetAttrLocal(s, true)
 	ctxt.xdefine("runtime.egcdata", sym.SRODATA, ldr.SymAddr(s)+ldr.SymSize(s))
 	ldr.SetSymSect(ldr.LookupOrCreateSym("runtime.egcdata", 0), ldr.SymSect(s))
diff --git a/src/cmd/link/internal/ld/elf_test.go b/src/cmd/link/internal/ld/elf_test.go
index c56d27f29e..0b3229e29c 100644
--- a/src/cmd/link/internal/ld/elf_test.go
+++ b/src/cmd/link/internal/ld/elf_test.go
@@ -408,8 +408,7 @@ func TestElfBindNow(t *testing.T) {
 }
 
 // This program is intended to be just big/complicated enough that
-// we wind up with decent-sized .data.rel.ro.{typelink,itablink}
-// sections.
+// we wind up with a decent-sized .data.rel.ro.itablink section.
 const ifacecallsProg = `
 package main
 
diff --git a/src/cmd/link/internal/ld/symtab.go b/src/cmd/link/internal/ld/symtab.go
index d2bd5d660c..d63a96d12b 100644
--- a/src/cmd/link/internal/ld/symtab.go
+++ b/src/cmd/link/internal/ld/symtab.go
@@ -433,6 +433,7 @@ func (ctxt *Link) symtab(pcln *pclntab) []sym.SymKind {
 	ctxt.xdefine("runtime.rodata", sym.SRODATA, 0)
 	ctxt.xdefine("runtime.erodata", sym.SRODATAEND, 0)
 	ctxt.xdefine("runtime.types", sym.SRODATA, 0)
+	ctxt.xdefine("runtime.etypedesc", sym.SRODATA, 0)
 	ctxt.xdefine("runtime.etypes", sym.SRODATA, 0)
 	ctxt.xdefine("runtime.noptrdata", sym.SNOPTRDATA, 0)
 	ctxt.xdefine("runtime.enoptrdata", sym.SNOPTRDATAEND, 0)
@@ -618,6 +619,7 @@ func (ctxt *Link) symtab(pcln *pclntab) []sym.SymKind {
 	moduledata.AddAddr(ctxt.Arch, ldr.Lookup("runtime.gcdata", 0))
 	moduledata.AddAddr(ctxt.Arch, ldr.Lookup("runtime.gcbss", 0))
 	moduledata.AddAddr(ctxt.Arch, ldr.Lookup("runtime.types", 0))
+	moduledata.AddAddr(ctxt.Arch, ldr.Lookup("runtime.etypedesc", 0))
 	moduledata.AddAddr(ctxt.Arch, ldr.Lookup("runtime.etypes", 0))
 	moduledata.AddAddr(ctxt.Arch, ldr.Lookup("runtime.rodata", 0))
 	moduledata.AddAddr(ctxt.Arch, ldr.Lookup("go:func.*", 0))
@@ -661,11 +663,6 @@ func (ctxt *Link) symtab(pcln *pclntab) []sym.SymKind {
 	// text section information
 	slice(textsectionmapSym, uint64(nsections))
 
-	// The typelinks slice
-	typelinkSym := ldr.Lookup("runtime.typelink", 0)
-	ntypelinks := uint64(ldr.SymSize(typelinkSym)) / 4
-	slice(typelinkSym, ntypelinks)
-
 	// The itablinks slice
 	itablinkSym := ldr.Lookup("runtime.itablink", 0)
 	nitablinks := uint64(ldr.SymSize(itablinkSym)) / uint64(ctxt.Arch.PtrSize)
diff --git a/src/cmd/link/internal/ld/typelink.go b/src/cmd/link/internal/ld/typelink.go
index 966de5571c..d9217182dd 100644
--- a/src/cmd/link/internal/ld/typelink.go
+++ b/src/cmd/link/internal/ld/typelink.go
@@ -8,49 +8,20 @@ import (
 	"cmd/internal/objabi"
 	"cmd/link/internal/loader"
 	"cmd/link/internal/sym"
-	"slices"
-	"strings"
 )
 
-type typelinkSortKey struct {
-	TypeStr string
-	Type    loader.Sym
-}
-
-// typelink generates the typelink table which is used by reflect.typelinks().
-// Types that should be added to the typelinks table are marked with the
-// MakeTypelink attribute by the compiler.
+// typelink generates the itablink table which is used by runtime.itabInit.
 func (ctxt *Link) typelink() {
 	ldr := ctxt.loader
-	var typelinks []typelinkSortKey
 	var itabs []loader.Sym
 	for s := loader.Sym(1); s < loader.Sym(ldr.NSym()); s++ {
 		if !ldr.AttrReachable(s) {
 			continue
 		}
-		if ldr.IsTypelink(s) {
-			typelinks = append(typelinks, typelinkSortKey{decodetypeStr(ldr, ctxt.Arch, s), s})
-		} else if ldr.IsItab(s) {
+		if ldr.IsItab(s) {
 			itabs = append(itabs, s)
 		}
 	}
-	slices.SortFunc(typelinks, func(a, b typelinkSortKey) int {
-		return strings.Compare(a.TypeStr, b.TypeStr)
-	})
-
-	tl := ldr.CreateSymForUpdate("runtime.typelink", 0)
-	tl.SetType(sym.STYPELINK)
-	ldr.SetAttrLocal(tl.Sym(), true)
-	tl.SetSize(int64(4 * len(typelinks)))
-	tl.Grow(tl.Size())
-	relocs := tl.AddRelocs(len(typelinks))
-	for i, s := range typelinks {
-		r := relocs.At(i)
-		r.SetSym(s.Type)
-		r.SetOff(int32(i * 4))
-		r.SetSiz(4)
-		r.SetType(objabi.R_ADDROFF)
-	}
 
 	ptrsize := ctxt.Arch.PtrSize
 	il := ldr.CreateSymForUpdate("runtime.itablink", 0)
@@ -58,7 +29,7 @@ func (ctxt *Link) typelink() {
 	ldr.SetAttrLocal(il.Sym(), true)
 	il.SetSize(int64(ptrsize * len(itabs)))
 	il.Grow(il.Size())
-	relocs = il.AddRelocs(len(itabs))
+	relocs := il.AddRelocs(len(itabs))
 	for i, s := range itabs {
 		r := relocs.At(i)
 		r.SetSym(s)
diff --git a/src/cmd/link/internal/wasm/asm.go b/src/cmd/link/internal/wasm/asm.go
index 5c25cc603b..7608d292e4 100644
--- a/src/cmd/link/internal/wasm/asm.go
+++ b/src/cmd/link/internal/wasm/asm.go
@@ -125,7 +125,6 @@ var dataSects []wasmDataSect
 func asmb(ctxt *ld.Link, ldr *loader.Loader) {
 	sections := []*sym.Section{
 		ldr.SymSect(ldr.Lookup("runtime.rodata", 0)),
-		ldr.SymSect(ldr.Lookup("runtime.typelink", 0)),
 		ldr.SymSect(ldr.Lookup("runtime.itablink", 0)),
 		ldr.SymSect(ldr.Lookup("runtime.types", 0)),
 		ldr.SymSect(ldr.Lookup("go:funcdesc", 0)),