inittask.go

     1  // Copyright 2022 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ld
     6  
     7  import (
     8  	"cmd/internal/objabi"
     9  	"cmd/link/internal/loader"
    10  	"cmd/link/internal/sym"
    11  	"fmt"
    12  	"sort"
    13  )
    14  
    15  // Inittasks finds inittask records, figures out a good
    16  // order to execute them in, and emits that order for the
    17  // runtime to use.
    18  //
    19  // An inittask represents the initialization code that needs
    20  // to be run for a package. For package p, the p..inittask
    21  // symbol contains a list of init functions to run, both
    22  // explicit user init functions and implicit compiler-generated
    23  // init functions for initializing global variables like maps.
    24  //
    25  // In addition, inittask records have dependencies between each
    26  // other, mirroring the import dependencies. So if package p
    27  // imports package q, then there will be a dependency p -> q.
    28  // We can't initialize package p until after package q has
    29  // already been initialized.
    30  //
    31  // Package dependencies are encoded with relocations. If package
    32  // p imports package q, then package p's inittask record will
    33  // have a R_INITORDER relocation pointing to package q's inittask
    34  // record. See cmd/compile/internal/pkginit/init.go.
    35  //
    36  // This function computes an ordering of all of the inittask
    37  // records so that the order respects all the dependencies,
    38  // and given that restriction, orders the inittasks in
    39  // lexicographic order.
    40  func (ctxt *Link) inittasks() {
    41  	switch ctxt.BuildMode {
    42  	case BuildModeExe, BuildModePIE, BuildModeCArchive, BuildModeCShared:
    43  		// Normally the inittask list will be run on program startup.
    44  		ctxt.mainInittasks = ctxt.inittaskSym([]string{"main..inittask"}, "go:main.inittasks")
    45  	case BuildModePlugin:
    46  		// For plugins, the list will be run on plugin load.
    47  		ctxt.mainInittasks = ctxt.inittaskSym([]string{fmt.Sprintf("%s..inittask", objabi.PathToPrefix(*flagPluginPath))}, "go:plugin.inittasks")
    48  		// Make symbol local so multiple plugins don't clobber each other's inittask list.
    49  		ctxt.loader.SetAttrLocal(ctxt.mainInittasks, true)
    50  	case BuildModeShared:
    51  		// For a shared library, all packages are roots.
    52  		var roots []string
    53  		for _, lib := range ctxt.Library {
    54  			roots = append(roots, fmt.Sprintf("%s..inittask", objabi.PathToPrefix(lib.Pkg)))
    55  		}
    56  		ctxt.mainInittasks = ctxt.inittaskSym(roots, "go:shlib.inittasks")
    57  		// Make symbol local so multiple plugins don't clobber each other's inittask list.
    58  		ctxt.loader.SetAttrLocal(ctxt.mainInittasks, true)
    59  	default:
    60  		Exitf("unhandled build mode %d", ctxt.BuildMode)
    61  	}
    62  
    63  	// If the runtime is one of the packages we are building,
    64  	// initialize the runtime_inittasks variable.
    65  	ldr := ctxt.loader
    66  	if ldr.Lookup("runtime.runtime_inittasks", 0) != 0 {
    67  		t := ctxt.inittaskSym([]string{"runtime..inittask"}, "go:runtime.inittasks")
    68  
    69  		// This slice header is already defined in runtime/proc.go, so we update it here with new contents.
    70  		sh := ldr.Lookup("runtime.runtime_inittasks", 0)
    71  		sb := ldr.MakeSymbolUpdater(sh)
    72  		sb.SetSize(0)
    73  		sb.SetType(sym.SNOPTRDATA) // Could be SRODATA, but see issue 58857.
    74  		sb.AddAddr(ctxt.Arch, t)
    75  		sb.AddUint(ctxt.Arch, uint64(ldr.SymSize(t)/int64(ctxt.Arch.PtrSize)))
    76  		sb.AddUint(ctxt.Arch, uint64(ldr.SymSize(t)/int64(ctxt.Arch.PtrSize)))
    77  	}
    78  }
    79  
    80  // inittaskSym builds a symbol containing pointers to all the inittasks
    81  // that need to be run, given a list of root inittask symbols.
    82  func (ctxt *Link) inittaskSym(rootNames []string, symName string) loader.Sym {
    83  	ldr := ctxt.loader
    84  	var roots []loader.Sym
    85  	for _, n := range rootNames {
    86  		p := ldr.Lookup(n, 0)
    87  		if p != 0 {
    88  			roots = append(roots, p)
    89  		}
    90  	}
    91  	if len(roots) == 0 {
    92  		// Nothing to do
    93  		return 0
    94  	}
    95  
    96  	// Edges record dependencies between packages.
    97  	// {from,to} is in edges if from's package imports to's package.
    98  	// This list is used to implement reverse edge lookups.
    99  	type edge struct {
   100  		from, to loader.Sym
   101  	}
   102  	var edges []edge
   103  
   104  	// List of packages that are ready to schedule. We use a lexicographic
   105  	// ordered heap to pick the lexically earliest uninitialized but
   106  	// inititalizeable package at each step.
   107  	var h lexHeap
   108  
   109  	// m maps from an inittask symbol for package p to the number of
   110  	// p's direct imports that have not yet been scheduled.
   111  	m := map[loader.Sym]int{}
   112  
   113  	// Find all reachable inittask records from the roots.
   114  	// Keep track of the dependency edges between them in edges.
   115  	// Keep track of how many imports each package has in m.
   116  	// q is the list of found but not yet explored packages.
   117  	var q []loader.Sym
   118  	for _, p := range roots {
   119  		m[p] = 0
   120  		q = append(q, p)
   121  	}
   122  	for len(q) > 0 {
   123  		x := q[len(q)-1]
   124  		q = q[:len(q)-1]
   125  		relocs := ldr.Relocs(x)
   126  		n := relocs.Count()
   127  		ndeps := 0
   128  		for i := 0; i < n; i++ {
   129  			r := relocs.At(i)
   130  			if r.Type() != objabi.R_INITORDER {
   131  				continue
   132  			}
   133  			ndeps++
   134  			s := r.Sym()
   135  			edges = append(edges, edge{from: x, to: s})
   136  			if _, ok := m[s]; ok {
   137  				continue // already found
   138  			}
   139  			q = append(q, s)
   140  			m[s] = 0 // mark as found
   141  		}
   142  		m[x] = ndeps
   143  		if ndeps == 0 {
   144  			h.push(ldr, x)
   145  		}
   146  	}
   147  
   148  	// Sort edges so we can look them up by edge destination.
   149  	sort.Slice(edges, func(i, j int) bool {
   150  		return edges[i].to < edges[j].to
   151  	})
   152  
   153  	// Figure out the schedule.
   154  	sched := ldr.MakeSymbolBuilder(symName)
   155  	sched.SetType(sym.SNOPTRDATA) // Could be SRODATA, but see issue 58857.
   156  	for !h.empty() {
   157  		// Pick the lexicographically first initializable package.
   158  		s := h.pop(ldr)
   159  
   160  		// Add s to the schedule.
   161  		if ldr.SymSize(s) > 8 {
   162  			// Note: don't add s if it has no functions to run. We need
   163  			// s during linking to compute an ordering, but the runtime
   164  			// doesn't need to know about it. About 1/2 of stdlib packages
   165  			// fit in this bucket.
   166  			sched.AddAddr(ctxt.Arch, s)
   167  		}
   168  
   169  		// Find all incoming edges into s.
   170  		a := sort.Search(len(edges), func(i int) bool { return edges[i].to >= s })
   171  		b := sort.Search(len(edges), func(i int) bool { return edges[i].to > s })
   172  
   173  		// Decrement the import count for all packages that import s.
   174  		// If the count reaches 0, that package is now ready to schedule.
   175  		for _, e := range edges[a:b] {
   176  			m[e.from]--
   177  			if m[e.from] == 0 {
   178  				h.push(ldr, e.from)
   179  			}
   180  		}
   181  	}
   182  
   183  	for s, n := range m {
   184  		if n != 0 {
   185  			Exitf("inittask for %s is not schedulable %d", ldr.SymName(s), n)
   186  		}
   187  	}
   188  	return sched.Sym()
   189  }
   190
View as plain text