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