1//===- InputSection.h -------------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLD_MACHO_INPUT_SECTION_H
10#define LLD_MACHO_INPUT_SECTION_H
11
12#include "Config.h"
13#include "Relocations.h"
14#include "Symbols.h"
15
16#include "lld/Common/LLVM.h"
17#include "lld/Common/Memory.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/CachedHashString.h"
20#include "llvm/ADT/TinyPtrVector.h"
21#include "llvm/BinaryFormat/MachO.h"
22#include "llvm/Support/SwapByteOrder.h"
23
24#include <atomic>
25#include <memory>
26
27namespace lld {
28namespace macho {
29
30class InputFile;
31class OutputSection;
32
33class InputSection {
34public:
35 enum Kind : uint8_t {
36 ConcatKind,
37 CStringLiteralKind,
38 WordLiteralKind,
39 };
40
41 Kind kind() const { return sectionKind; }
42 virtual ~InputSection() = default;
43 virtual uint64_t getSize() const { return data.size(); }
44 virtual bool empty() const { return data.empty(); }
45 InputFile *getFile() const { return section.file; }
46 StringRef getName() const { return section.name; }
47 StringRef getSegName() const { return section.segname; }
48 uint32_t getFlags() const { return section.flags; }
49 uint64_t getFileSize() const;
50 // Translates \p off -- an offset relative to this InputSection -- into an
51 // offset from the beginning of its parent OutputSection.
52 virtual uint64_t getOffset(uint64_t off) const = 0;
53 // The offset from the beginning of the file.
54 uint64_t getVA(uint64_t off) const;
55 // Return a user-friendly string for use in diagnostics.
56 // Format: /path/to/object.o:(symbol _func+0x123)
57 std::string getLocation(uint64_t off) const;
58 // Return the source line corresponding to an address, or the empty string.
59 // Format: Source.cpp:123 (/path/to/Source.cpp:123)
60 std::string getSourceLocation(uint64_t off) const;
61 // Return the relocation at \p off, if it exists. This does a linear search.
62 const Relocation *getRelocAt(uint32_t off) const;
63 // Whether the data at \p off in this InputSection is live. isLive() and
64 // markLive() are safe to call from several threads at once.
65 virtual bool isLive(uint64_t off) const = 0;
66 virtual void markLive(uint64_t off) = 0;
67 virtual InputSection *canonical() { return this; }
68 virtual const InputSection *canonical() const { return this; }
69
70protected:
71 InputSection(Kind kind, const Section &section, ArrayRef<uint8_t> data,
72 uint32_t align)
73 : sectionKind(kind), keepUnique(false), hasAltEntry(false), isCold(false),
74 align(align), data(data), section(section) {}
75
76 InputSection(const InputSection &rhs)
77 : sectionKind(rhs.sectionKind), keepUnique(false), hasAltEntry(false),
78 isCold(rhs.isCold), align(rhs.align), data(rhs.data),
79 section(rhs.section) {}
80
81 Kind sectionKind;
82
83public:
84 // is address assigned?
85 bool isFinal = false;
86 // keep the address of the symbol(s) in this section unique in the final
87 // binary ?
88 bool keepUnique : 1;
89 // Does this section have symbols at offsets other than zero? (NOTE: only
90 // applies to ConcatInputSections.)
91 bool hasAltEntry : 1;
92 // Is this considered cold? Computed before ICF. Currently reflects whether
93 // any symbol in the section has the N_COLD_FUNC nlist flag set. Cold
94 // sections are placed at the end of their containing output section to
95 // improve locality of non-cold input sections. When a section is given an
96 // explicit priority (via order file, --bp-startup-sort, or
97 // --bp-compression-sort), this flag is unset so that the priority-based
98 // ordering takes precedence over cold partitioning.
99 bool isCold : 1;
100 uint32_t align = 1;
101
102 OutputSection *parent = nullptr;
103 ArrayRef<uint8_t> data;
104 std::vector<Relocation> relocs;
105 // The symbols that belong to this InputSection, sorted by value. With
106 // .subsections_via_symbols, there is typically only one element here.
107 llvm::TinyPtrVector<Defined *> symbols;
108
109 const Section &section;
110
111protected:
112 const Defined *getContainingSymbol(uint64_t off) const;
113};
114
115// ConcatInputSections are combined into (Concat)OutputSections through simple
116// concatenation, in contrast with literal sections which may have their
117// contents merged before output.
118class ConcatInputSection final : public InputSection {
119public:
120 ConcatInputSection(const Section &section, ArrayRef<uint8_t> data,
121 uint32_t align = 1)
122 : InputSection(ConcatKind, section, data, align) {}
123
124 uint64_t getOffset(uint64_t off) const override { return outSecOff + off; }
125 uint64_t getVA() const { return InputSection::getVA(off: 0); }
126 // ConcatInputSections are entirely live or dead, so the offset is irrelevant.
127 bool isLive(uint64_t off) const override {
128 return utils::atomicRef(x: live).load(m: std::memory_order_relaxed);
129 }
130 void markLive(uint64_t off) override {
131 utils::atomicRef(x&: live).store(i: true, m: std::memory_order_relaxed);
132 }
133 bool isCoalescedWeak() const { return wasCoalesced && symbols.empty(); }
134 bool shouldOmitFromOutput() const { return !live || isCoalescedWeak(); }
135 void writeTo(uint8_t *buf);
136
137 void foldIdentical(ConcatInputSection *redundant,
138 Symbol::ICFFoldKind foldKind = Symbol::ICFFoldKind::Body);
139 ConcatInputSection *canonical() override {
140 return replacement ? replacement : this;
141 }
142 const InputSection *canonical() const override {
143 return replacement ? replacement : this;
144 }
145
146 static bool classof(const InputSection *isec) {
147 return isec->kind() == ConcatKind;
148 }
149
150 // Points to the surviving section after this one is folded by ICF
151 ConcatInputSection *replacement = nullptr;
152 // Equivalence-class ID for ICF
153 uint32_t icfEqClass[2] = {0, 0};
154
155 // With subsections_via_symbols, most symbols have their own InputSection,
156 // and for weak symbols (e.g. from inline functions), only the
157 // InputSection from one translation unit will make it to the output,
158 // while all copies in other translation units are coalesced into the
159 // first and not copied to the output.
160 bool wasCoalesced = false;
161 bool live = !config->deadStrip;
162 // This variable has two usages. Initially, it represents the input order.
163 // After assignAddresses is called, it represents the offset from the
164 // beginning of the output section this section was assigned to.
165 uint64_t outSecOff = 0;
166};
167
168// Initialize a fake InputSection that does not belong to any InputFile.
169// The created ConcatInputSection will always have 'live=true'
170ConcatInputSection *makeSyntheticInputSection(StringRef segName,
171 StringRef sectName,
172 uint32_t flags = 0,
173 ArrayRef<uint8_t> data = {},
174 uint32_t align = 1);
175
176// Helper functions to make it easy to sprinkle asserts.
177
178inline bool shouldOmitFromOutput(InputSection *isec) {
179 return isa<ConcatInputSection>(Val: isec) &&
180 cast<ConcatInputSection>(Val: isec)->shouldOmitFromOutput();
181}
182
183inline bool isCoalescedWeak(InputSection *isec) {
184 return isa<ConcatInputSection>(Val: isec) &&
185 cast<ConcatInputSection>(Val: isec)->isCoalescedWeak();
186}
187
188// We allocate a lot of these and binary search on them, so they should be as
189// compact as possible. Hence the use of 31 rather than 64 bits for the hash.
190struct StringPiece {
191 // Offset from the start of the containing input section.
192 uint32_t inSecOff;
193 uint32_t live : 1;
194 // Only set if deduplicating literals
195 uint32_t hash : 31;
196 // Offset from the start of the containing output section.
197 uint64_t outSecOff = 0;
198
199 StringPiece(uint64_t off, uint32_t hash)
200 : inSecOff(off), live(!config->deadStrip), hash(hash) {}
201
202 // Thread-safe iff `hash` is not modified concurrently.
203 bool isLive() const {
204 // &inSecOff + 1 points to the `live` bitfield.
205 auto &word = utils::atomicRef(x: *(&inSecOff + 1));
206 return word.load(m: std::memory_order_relaxed) & liveBit;
207 }
208
209 void markLive() {
210 auto &word = utils::atomicRef(x&: *(&inSecOff + 1));
211 uint32_t w = word.load(m: std::memory_order_relaxed);
212 // No atomic OR is needed: while markLive runs, `hash` does not change and
213 // `live` only goes from false to true, so threads racing here all store the
214 // same value.
215 if (!(w & liveBit))
216 word.store(i: w | liveBit, m: std::memory_order_relaxed);
217 }
218
219 // The bit of the word after inSecOff that holds `live`.
220 static constexpr uint32_t liveBit =
221 llvm::sys::IsBigEndianHost ? (1U << 31) : 1U;
222};
223
224static_assert(sizeof(StringPiece) == 16, "StringPiece is too big!");
225
226// CStringInputSections are composed of multiple null-terminated string
227// literals, which we represent using StringPieces. These literals can be
228// deduplicated and tail-merged, so translating offsets between the input and
229// outputs sections is more complicated.
230//
231// NOTE: One significant difference between LLD and ld64 is that we merge all
232// cstring literals, even those referenced directly by non-private symbols.
233// ld64 is more conservative and does not do that. This was mostly done for
234// implementation simplicity; if we find programs that need the more
235// conservative behavior we can certainly implement that.
236class CStringInputSection final : public InputSection {
237public:
238 CStringInputSection(const Section &section, ArrayRef<uint8_t> data,
239 uint32_t align, bool dedupLiterals)
240 : InputSection(CStringLiteralKind, section, data, align),
241 deduplicateLiterals(dedupLiterals) {}
242
243 uint64_t getOffset(uint64_t off) const override;
244 bool isLive(uint64_t off) const override {
245 return getStringPiece(off).isLive();
246 }
247 void markLive(uint64_t off) override { getStringPiece(off).markLive(); }
248 // Find the StringPiece that contains this offset.
249 StringPiece &getStringPiece(uint64_t off);
250 const StringPiece &getStringPiece(uint64_t off) const;
251 // Split at each null byte.
252 void splitIntoPieces();
253
254 LLVM_ATTRIBUTE_ALWAYS_INLINE
255 StringRef getStringRef(size_t i) const {
256 size_t begin = pieces[i].inSecOff;
257 // The endpoint should be *at* the null terminator, not after. This matches
258 // the behavior of StringRef(const char *Str).
259 size_t end =
260 ((pieces.size() - 1 == i) ? data.size() : pieces[i + 1].inSecOff) - 1;
261 return toStringRef(Input: data.slice(N: begin, M: end - begin));
262 }
263
264 StringRef getStringRefAtOffset(uint64_t off) const {
265 return getStringRef(i: getStringPieceIndex(off));
266 }
267
268 // Returns i'th piece as a CachedHashStringRef. This function is very hot when
269 // string merging is enabled, so we want to inline.
270 LLVM_ATTRIBUTE_ALWAYS_INLINE
271 llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
272 assert(deduplicateLiterals);
273 return {getStringRef(i), pieces[i].hash};
274 }
275
276 static bool classof(const InputSection *isec) {
277 return isec->kind() == CStringLiteralKind;
278 }
279
280 bool deduplicateLiterals = false;
281 std::vector<StringPiece> pieces;
282
283private:
284 size_t getStringPieceIndex(uint64_t off) const;
285};
286
287class WordLiteralInputSection final : public InputSection {
288public:
289 WordLiteralInputSection(const Section &section, ArrayRef<uint8_t> data,
290 uint32_t align);
291 uint64_t getOffset(uint64_t off) const override;
292 bool isLive(uint64_t off) const override {
293 return live[off >> power2LiteralSize].load(m: std::memory_order_relaxed);
294 }
295 void markLive(uint64_t off) override {
296 live[off >> power2LiteralSize].store(i: true, m: std::memory_order_relaxed);
297 }
298
299 static bool classof(const InputSection *isec) {
300 return isec->kind() == WordLiteralKind;
301 }
302
303private:
304 unsigned power2LiteralSize;
305 // The liveness of data[off] is tracked by live[off >> power2LiteralSize].
306 std::unique_ptr<std::atomic<bool>[]> live;
307};
308
309inline uint8_t sectionType(uint32_t flags) {
310 return flags & llvm::MachO::SECTION_TYPE;
311}
312
313inline bool isZeroFill(uint32_t flags) {
314 return llvm::MachO::isVirtualSection(type: sectionType(flags));
315}
316
317inline bool isThreadLocalVariables(uint32_t flags) {
318 return sectionType(flags) == llvm::MachO::S_THREAD_LOCAL_VARIABLES;
319}
320
321// These sections contain the data for initializing thread-local variables.
322inline bool isThreadLocalData(uint32_t flags) {
323 return sectionType(flags) == llvm::MachO::S_THREAD_LOCAL_REGULAR ||
324 sectionType(flags) == llvm::MachO::S_THREAD_LOCAL_ZEROFILL;
325}
326
327inline bool isDebugSection(uint32_t flags) {
328 return (flags & llvm::MachO::SECTION_ATTRIBUTES_USR) ==
329 llvm::MachO::S_ATTR_DEBUG;
330}
331
332inline bool isWordLiteralSection(uint32_t flags) {
333 return sectionType(flags) == llvm::MachO::S_4BYTE_LITERALS ||
334 sectionType(flags) == llvm::MachO::S_8BYTE_LITERALS ||
335 sectionType(flags) == llvm::MachO::S_16BYTE_LITERALS;
336}
337
338bool isCodeSection(const InputSection *);
339bool isCfStringSection(const InputSection *);
340bool isClassRefsSection(const InputSection *);
341bool isSelRefsSection(const InputSection *);
342bool isEhFrameSection(const InputSection *);
343bool isGccExceptTabSection(const InputSection *);
344bool usesAuthGot(const InputSection *);
345const AuthInfo *getImplicitAuthInfo(const InputSection *isec,
346 const Symbol *sym);
347
348extern std::vector<ConcatInputSection *> inputSections;
349// This is used as a counter for specifying input order for input sections.
350extern int inputSectionsOrder;
351
352namespace section_names {
353
354constexpr const char authGot[] = "__auth_got";
355constexpr const char authPtr[] = "__auth_ptr";
356constexpr const char binding[] = "__binding";
357constexpr const char bitcodeBundle[] = "__bundle";
358constexpr const char cString[] = "__cstring";
359constexpr const char cfString[] = "__cfstring";
360constexpr const char cgProfile[] = "__cg_profile";
361constexpr const char chainFixups[] = "__chainfixups";
362constexpr const char codeSignature[] = "__code_signature";
363constexpr const char common[] = "__common";
364constexpr const char compactUnwind[] = "__compact_unwind";
365constexpr const char data[] = "__data";
366constexpr const char debugAbbrev[] = "__debug_abbrev";
367constexpr const char debugInfo[] = "__debug_info";
368constexpr const char debugLine[] = "__debug_line";
369constexpr const char debugLineStr[] = "__debug_line_str";
370constexpr const char debugStr[] = "__debug_str";
371constexpr const char debugStrOffs[] = "__debug_str_offs";
372constexpr const char ehFrame[] = "__eh_frame";
373constexpr const char gccExceptTab[] = "__gcc_except_tab";
374constexpr const char export_[] = "__export";
375constexpr const char dataInCode[] = "__data_in_code";
376constexpr const char functionStarts[] = "__func_starts";
377constexpr const char got[] = "__got";
378constexpr const char header[] = "__mach_header";
379constexpr const char indirectSymbolTable[] = "__ind_sym_tab";
380constexpr const char initOffsets[] = "__init_offsets";
381constexpr const char const_[] = "__const";
382constexpr const char constCfObj2[] = "__const_cfobj2";
383constexpr const char lazySymbolPtr[] = "__la_symbol_ptr";
384constexpr const char lazyBinding[] = "__lazy_binding";
385constexpr const char literals[] = "__literals";
386constexpr const char functionMap[] = "__llvm_merge";
387constexpr const char moduleInitFunc[] = "__mod_init_func";
388constexpr const char moduleTermFunc[] = "__mod_term_func";
389constexpr const char nonLazySymbolPtr[] = "__nl_symbol_ptr";
390constexpr const char objcArrayData[] = "__objc_arraydata";
391constexpr const char objcArrayObj[] = "__objc_arrayobj";
392constexpr const char objcCatList[] = "__objc_catlist";
393constexpr const char objcCatList2[] = "__objc_catlist2";
394constexpr const char objcClassList[] = "__objc_classlist";
395constexpr const char objcMethList[] = "__objc_methlist";
396constexpr const char objcClassRefs[] = "__objc_classrefs";
397constexpr const char objcConst[] = "__objc_const";
398constexpr const char objcDateObj[] = "__objc_dateobj";
399constexpr const char objcDictObj[] = "__objc_dictobj";
400constexpr const char objcDoubleObj[] = "__objc_doubleobj";
401constexpr const char objcFloatObj[] = "__objc_floatobj";
402constexpr const char objCImageInfo[] = "__objc_imageinfo";
403constexpr const char objcIntObj[] = "__objc_intobj";
404constexpr const char objcStubs[] = "__objc_stubs";
405constexpr const char objcSelrefs[] = "__objc_selrefs";
406constexpr const char objcMethname[] = "__objc_methname";
407constexpr const char objcNonLazyCatList[] = "__objc_nlcatlist";
408constexpr const char objcNonLazyClassList[] = "__objc_nlclslist";
409constexpr const char objcProtoList[] = "__objc_protolist";
410constexpr const char outlinedHashTree[] = "__llvm_outline";
411constexpr const char pageZero[] = "__pagezero";
412constexpr const char pointers[] = "__pointers";
413constexpr const char rebase[] = "__rebase";
414constexpr const char staticInit[] = "__StaticInit";
415constexpr const char stringTable[] = "__string_table";
416constexpr const char stubHelper[] = "__stub_helper";
417constexpr const char stubs[] = "__stubs";
418constexpr const char authStubs[] = "__auth_stubs";
419constexpr const char swift[] = "__swift";
420constexpr const char symbolTable[] = "__symbol_table";
421constexpr const char textCoalNt[] = "__textcoal_nt";
422constexpr const char text[] = "__text";
423constexpr const char threadVars[] = "__thread_vars";
424constexpr const char unwindInfo[] = "__unwind_info";
425constexpr const char weakBinding[] = "__weak_binding";
426constexpr const char zeroFill[] = "__zerofill";
427constexpr const char addrSig[] = "__llvm_addrsig";
428
429} // namespace section_names
430
431void addInputSection(InputSection *inputSection);
432
433uint64_t resolveSymbolOffsetVA(const Symbol *sym, uint8_t type, int64_t offset);
434} // namespace macho
435
436std::string toString(const macho::InputSection *);
437
438} // namespace lld
439
440#endif
441