loader.go

// Copyright 2019 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 loader

import (
	"bytes"
	"cmd/internal/bio"
	"cmd/internal/dwarf"
	"cmd/internal/goobj2"
	"cmd/internal/obj"
	"cmd/internal/objabi"
	"cmd/internal/sys"
	"cmd/link/internal/sym"
	"fmt"
	"log"
	"math/bits"
	"os"
	"sort"
	"strconv"
	"strings"
)

var _ = fmt.Print

// Sym encapsulates a global symbol index, used to identify a specific
// Go symbol. The 0-valued Sym is corresponds to an invalid symbol.
type Sym int

// Relocs encapsulates the set of relocations on a given symbol; an
// instance of this type is returned by the Loader Relocs() method.
type Relocs struct {
	Count int // number of relocs

	li int      // local index of symbol whose relocs we're examining
	r  *oReader // object reader for containing package
	l  *Loader  // loader

	extIdx Sym // index of external symbol we're examining or 0
}

// Reloc contains the payload for a specific relocation.
// TODO: replace this with sym.Reloc, once we change the
// relocation target from "*sym.Symbol" to "loader.Sym" in sym.Reloc.
type Reloc struct {
	Off  int32            // offset to rewrite
	Size uint8            // number of bytes to rewrite: 0, 1, 2, or 4
	Type objabi.RelocType // the relocation type
	Add  int64            // addend
	Sym  Sym              // global index of symbol the reloc addresses
}

// oReader is a wrapper type of obj.Reader, along with some
// extra information.
// TODO: rename to objReader once the old one is gone?
type oReader struct {
	*goobj2.Reader
	unit      *sym.CompilationUnit
	version   int    // version of static symbol
	flags     uint32 // read from object file
	pkgprefix string
	rcache    []Sym // cache mapping local PkgNone symbol to resolved Sym
}

type objIdx struct {
	r *oReader
	i Sym // start index
	e Sym // end index
}

type nameVer struct {
	name string
	v    int
}

type bitmap []uint32

// set the i-th bit.
func (bm bitmap) set(i Sym) {
	n, r := uint(i)/32, uint(i)%32
	bm[n] |= 1 << r
}

// unset the i-th bit.
func (bm bitmap) unset(i Sym) {
	n, r := uint(i)/32, uint(i)%32
	bm[n] &^= (1 << r)
}

// whether the i-th bit is set.
func (bm bitmap) has(i Sym) bool {
	n, r := uint(i)/32, uint(i)%32
	return bm[n]&(1<<r) != 0
}

// return current length of bitmap in bits.
func (bm bitmap) len() int {
	return len(bm) * 32
}
func makeBitmap(n int) bitmap {
	return make(bitmap, (n+31)/32)
}

// growBitmap insures that the specified bitmap has enough capacity,
// reallocating (doubling the size) if needed.
func growBitmap(reqLen int, b bitmap) bitmap {
	curLen := b.len()
	if reqLen > curLen {
		b = append(b, makeBitmap(reqLen+1-curLen)...)
	}
	return b
}

// A Loader loads new object files and resolves indexed symbol references.
//
// Notes on the layout of global symbol index space:
//
// - Go object files are read before host object files; each Go object
//   read allocates a new chunk of global index space of size P + NP,
//   where P is the number of package defined symbols in the object and
//   NP is the number of non-package defined symbols.
//
// - In loader.LoadRefs(), the loader makes a sweep through all of the
//   non-package references in each object file and allocates sym indices
//   for any symbols that have not yet been defined (start of this space
//   is marked by loader.extStart).
//
// - Host object file loading happens; the host object loader does a
//   name/version lookup for each symbol it finds; this can wind up
//   extending the external symbol index space range. The host object
//   loader currently stores symbol payloads in sym.Symbol objects,
//   which get handed off to the loader.
//
// - A given external symbol (Sym) either has a sym.Symbol acting as
//   its backing store (this will continue to be the case until we
//   finish rewriting the host object loader to work entirely with
//   loader.Sym) or it has a "payload" backing store (represented by
//   extSymPayload). Newly created external symbols (created by
//   a call to AddExtSym or equivalent) start out in the "has payload"
//   state, and continue until installSym is called for the sym
//   index in question.
//
// - At some point (when the wayfront is pushed through all of the
//   linker), all external symbols will be payload-based, and we can
//   get rid of the loader.Syms array.
//
type Loader struct {
	start       map[*oReader]Sym // map from object file to its start index
	objs        []objIdx         // sorted by start index (i.e. objIdx.i)
	max         Sym              // current max index
	extStart    Sym              // from this index on, the symbols are externally defined
	builtinSyms []Sym            // global index of builtin symbols
	ocache      int              // index (into 'objs') of most recent lookup

	symsByName    [2]map[string]Sym // map symbol name to index, two maps are for ABI0 and ABIInternal
	extStaticSyms map[nameVer]Sym   // externally defined static symbols, keyed by name
	overwrite     map[Sym]Sym       // overwrite[i]=j if symbol j overwrites symbol i

	payloads []extSymPayload // contents of linker-materialized external syms
	values   []int64         // symbol values, indexed by global sym index

	itablink map[Sym]struct{} // itablink[j] defined if j is go.itablink.*

	objByPkg map[string]*oReader // map package path to its Go object reader

	Syms     []*sym.Symbol // indexed symbols. XXX we still make sym.Symbol for now.
	symBatch []sym.Symbol  // batch of symbols.

	anonVersion int // most recently assigned ext static sym pseudo-version

	// Bitmaps and other side structures used to store data used to store
	// symbol flags/attributes; these are to be accessed via the
	// corresponding loader "AttrXXX" and "SetAttrXXX" methods. Please
	// visit the comments on these methods for more details on the
	// semantics / interpretation of the specific flags or attribute.
	attrReachable        bitmap // reachable symbols, indexed by global index
	attrOnList           bitmap // "on list" symbols, indexed by global index
	attrVisibilityHidden bitmap // hidden symbols, indexed by ext sym index
	attrDuplicateOK      bitmap // dupOK symbols, indexed by ext sym index
	attrShared           bitmap // shared symbols, indexed by ext sym index
	attrExternal         bitmap // external symbols, indexed by ext sym index

	attrTopFrame         map[Sym]struct{} // top frame symbols
	attrSpecial          map[Sym]struct{} // "special" frame symbols
	attrCgoExportDynamic map[Sym]struct{} // "cgo_export_dynamic" symbols
	attrCgoExportStatic  map[Sym]struct{} // "cgo_export_static" symbols

	// Outer and Sub relations for symbols.
	// TODO: figure out whether it's more efficient to just have these
	// as fields on extSymPayload (note that this won't be a viable
	// strategy if somewhere in the linker we set sub/outer for a
	// non-external sym).
	outer map[Sym]Sym
	sub   map[Sym]Sym

	align map[Sym]int32 // stores alignment for symbols

	// Used to implement field tracking; created during deadcode if
	// field tracking is enabled. Reachparent[K] contains the index of