reloc.go

     1  // Copyright 2021 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 pkgbits
     6  
     7  // A SectionKind indicates a section, as well as the ordering of sections within
     8  // unified export data. Any object given a dedicated section can be referred to
     9  // via a section / index pair (and thus dereferenced) in other sections.
    10  type SectionKind int32 // TODO(markfreeman): Replace with uint8.
    11  
    12  const (
    13  	SectionString SectionKind = iota
    14  	SectionMeta
    15  	SectionPosBase
    16  	SectionPkg
    17  	SectionName
    18  	SectionType
    19  	SectionObj
    20  	SectionObjExt
    21  	SectionObjDict
    22  	SectionBody
    23  
    24  	numRelocs = iota
    25  )
    26  
    27  // An Index represents a bitstream element index *within* (i.e., relative to) a
    28  // particular section.
    29  type Index int32
    30  
    31  // An AbsElemIdx, or absolute element index, is an index into the elements
    32  // that is not relative to some other index.
    33  type AbsElemIdx = uint32
    34  
    35  // TODO(markfreeman): Make this its own type.
    36  // A RelElemIdx, or relative element index, is an index into the elements
    37  // relative to some other index, such as the start of a section.
    38  type RelElemIdx = Index
    39  
    40  /*
    41  All elements are preceded by a reference table. Reference tables provide an
    42  additional indirection layer for element references. That is, for element A to
    43  reference element B, A encodes the reference table index pointing to B, rather
    44  than the table entry itself.
    45  
    46  # Functional Considerations
    47  Reference table layout is important primarily to the UIR linker. After noding,
    48  the UIR linker sees a UIR file for each package with imported objects
    49  represented as stubs. In a simple sense, the job of the UIR linker is to merge
    50  these "stubbed" UIR files into a single "linked" UIR file for the target package
    51  with stubs replaced by object definitions.
    52  
    53  To do this, the UIR linker walks each stubbed UIR file and pulls in elements in
    54  dependency order; that is, if A references B, then B must be placed into the
    55  linked UIR file first. This depth-first traversal is done by recursing through
    56  each element's reference table.
    57  
    58  When placing A in the linked UIR file, the reference table entry for B must be
    59  updated, since B is unlikely to be at the same relative element index as it was
    60  in the stubbed UIR file.
    61  
    62  Without reference tables, the UIR linker would need to read in the element to
    63  discover its references. Note that the UIR linker cannot jump directly to the
    64  reference locations after discovering merely the type of the element;
    65  variable-width primitives prevent this.
    66  
    67  After updating the reference table, the rest of the element may be copied
    68  directly into the linked UIR file. Note that the UIR linker may decide to read
    69  in the element anyway (for unrelated reasons).
    70  
    71  In short, reference tables provide an efficient mechanism for traversing,
    72  discovering, and updating element references during UIR linking.
    73  
    74  # Storage Considerations
    75  Reference tables also have compactness benefits:
    76    - If A refers to B multiple times, the entry is deduplicated and referred to
    77      more compactly by the index.
    78    - Relative (to a section) element indices are typically smaller than absolute
    79      element indices, and thus fit into smaller varints.
    80    - Most elements do not reference many elements; thus table size indicators and
    81      table indices are typically a byte each.
    82  
    83  Thus, the storage performance is as follows:
    84  +-----------------------------+-----------+--------------+
    85  |          Scenario           | Best Case | Typical Case |
    86  +-----------------------------+-----------+--------------+
    87  | First reference from A to B | 3 Bytes   | 4 Bytes      |
    88  | Other reference from A to B | 1 Byte    | 1 Byte       |
    89  +-----------------------------+-----------+--------------+
    90  
    91  The typical case for the first scenario changes because many sections have more
    92  than 127 (range of a 1-byte uvarint) elements and thus the relative index is
    93  typically 2 bytes, though this depends on the distribution of referenced indices
    94  within the section.
    95  
    96  The second does not because most elements do not reference more than 127
    97  elements and the table index can thus keep to 1 byte.
    98  
    99  Typically, A will only reference B once, so most references are 4 bytes.
   100  */
   101  
   102  // A RefTableEntry is an entry in an element's reference table. All
   103  // elements are preceded by a reference table which provides locations
   104  // for referenced elements.
   105  type RefTableEntry struct {
   106  	Kind SectionKind
   107  	Idx  RelElemIdx
   108  }
   109  
   110  // Reserved indices within the [SectionMeta] section.
   111  const (
   112  	PublicRootIdx  RelElemIdx = 0
   113  	PrivateRootIdx RelElemIdx = 1
   114  )
   115
View as plain text