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/BitVector.h"
20 #include "llvm/ADT/CachedHashString.h"
21 #include "llvm/ADT/TinyPtrVector.h"
22 #include "llvm/BinaryFormat/MachO.h"
23 
24 namespace lld {
25 namespace macho {
26 
27 class InputFile;
28 class OutputSection;
29 
30 class InputSection {
31 public:
32   enum Kind : uint8_t {
33     ConcatKind,
34     CStringLiteralKind,
35     WordLiteralKind,
36   };
37 
38   Kind kind() const { return sectionKind; }
39   virtual ~InputSection() = default;
40   virtual uint64_t getSize() const { return data.size(); }
41   virtual bool empty() const { return data.empty(); }
42   InputFile *getFile() const { return section.file; }
43   StringRef getName() const { return section.name; }
44   StringRef getSegName() const { return section.segname; }
45   uint32_t getFlags() const { return section.flags; }
46   uint64_t getFileSize() const;
47   // Translates \p off -- an offset relative to this InputSection -- into an
48   // offset from the beginning of its parent OutputSection.
49   virtual uint64_t getOffset(uint64_t off) const = 0;
50   // The offset from the beginning of the file.
51   uint64_t getVA(uint64_t off) const;
52   // Return a user-friendly string for use in diagnostics.
53   // Format: /path/to/object.o:(symbol _func+0x123)
54   std::string getLocation(uint64_t off) const;
55   // Return the source line corresponding to an address, or the empty string.
56   // Format: Source.cpp:123 (/path/to/Source.cpp:123)
57   std::string getSourceLocation(uint64_t off) const;
58   // Whether the data at \p off in this InputSection is live.
59   virtual bool isLive(uint64_t off) const = 0;
60   virtual void markLive(uint64_t off) = 0;
61   virtual InputSection *canonical() { return this; }
62   virtual const InputSection *canonical() const { return this; }
63 
64 protected:
65   InputSection(Kind kind, const Section &section, ArrayRef<uint8_t> data,
66                uint32_t align)
67       : sectionKind(kind), align(align), data(data), section(section) {}
68 
69   InputSection(const InputSection &rhs)
70       : sectionKind(rhs.sectionKind), align(rhs.align), data(rhs.data),
71         section(rhs.section) {}
72 
73   Kind sectionKind;
74 
75 public:
76   // is address assigned?
77   bool isFinal = false;
78   // keep the address of the symbol(s) in this section unique in the final
79   // binary ?
80   bool keepUnique = false;
81   uint32_t align = 1;
82 
83   OutputSection *parent = nullptr;
84   ArrayRef<uint8_t> data;
85   std::vector<Reloc> relocs;
86   ArrayRef<OptimizationHint> optimizationHints;
87   // The symbols that belong to this InputSection, sorted by value. With
88   // .subsections_via_symbols, there is typically only one element here.
89   llvm::TinyPtrVector<Defined *> symbols;
90 
91 protected:
92   const Section &section;
93 
94   const Defined *getContainingSymbol(uint64_t off) const;
95 };
96 
97 // ConcatInputSections are combined into (Concat)OutputSections through simple
98 // concatenation, in contrast with literal sections which may have their
99 // contents merged before output.
100 class ConcatInputSection final : public InputSection {
101 public:
102   ConcatInputSection(const Section &section, ArrayRef<uint8_t> data,
103                      uint32_t align = 1)
104       : InputSection(ConcatKind, section, data, align) {}
105 
106   uint64_t getOffset(uint64_t off) const override { return outSecOff + off; }
107   uint64_t getVA() const { return InputSection::getVA(0); }
108   // ConcatInputSections are entirely live or dead, so the offset is irrelevant.
109   bool isLive(uint64_t off) const override { return live; }
110   void markLive(uint64_t off) override { live = true; }
111   bool isCoalescedWeak() const { return wasCoalesced && symbols.empty(); }
112   bool shouldOmitFromOutput() const { return !live || isCoalescedWeak(); }
113   void writeTo(uint8_t *buf);
114 
115   void foldIdentical(ConcatInputSection *redundant);
116   ConcatInputSection *canonical() override {
117     return replacement ? replacement : this;
118   }
119   const InputSection *canonical() const override {
120     return replacement ? replacement : this;
121   }
122 
123   static bool classof(const InputSection *isec) {
124     return isec->kind() == ConcatKind;
125   }
126 
127   // Points to the surviving section after this one is folded by ICF
128   ConcatInputSection *replacement = nullptr;
129   // Equivalence-class ID for ICF
130   uint32_t icfEqClass[2] = {0, 0};
131 
132   // With subsections_via_symbols, most symbols have their own InputSection,
133   // and for weak symbols (e.g. from inline functions), only the
134   // InputSection from one translation unit will make it to the output,
135   // while all copies in other translation units are coalesced into the
136   // first and not copied to the output.
137   bool wasCoalesced = false;
138   bool live = !config->deadStrip;
139   bool hasCallSites = false;
140   // This variable has two usages. Initially, it represents the input order.
141   // After assignAddresses is called, it represents the offset from the
142   // beginning of the output section this section was assigned to.
143   uint64_t outSecOff = 0;
144 };
145 
146 // Initialize a fake InputSection that does not belong to any InputFile.
147 ConcatInputSection *makeSyntheticInputSection(StringRef segName,
148                                               StringRef sectName,
149                                               uint32_t flags = 0,
150                                               ArrayRef<uint8_t> data = {},
151                                               uint32_t align = 1);
152 
153 // Helper functions to make it easy to sprinkle asserts.
154 
155 inline bool shouldOmitFromOutput(InputSection *isec) {
156   return isa<ConcatInputSection>(isec) &&
157          cast<ConcatInputSection>(isec)->shouldOmitFromOutput();
158 }
159 
160 inline bool isCoalescedWeak(InputSection *isec) {
161   return isa<ConcatInputSection>(isec) &&
162          cast<ConcatInputSection>(isec)->isCoalescedWeak();
163 }
164 
165 // We allocate a lot of these and binary search on them, so they should be as
166 // compact as possible. Hence the use of 31 rather than 64 bits for the hash.
167 struct StringPiece {
168   // Offset from the start of the containing input section.
169   uint32_t inSecOff;
170   uint32_t live : 1;
171   // Only set if deduplicating literals
172   uint32_t hash : 31;
173   // Offset from the start of the containing output section.
174   uint64_t outSecOff = 0;
175 
176   StringPiece(uint64_t off, uint32_t hash)
177       : inSecOff(off), live(!config->deadStrip), hash(hash) {}
178 };
179 
180 static_assert(sizeof(StringPiece) == 16, "StringPiece is too big!");
181 
182 // CStringInputSections are composed of multiple null-terminated string
183 // literals, which we represent using StringPieces. These literals can be
184 // deduplicated and tail-merged, so translating offsets between the input and
185 // outputs sections is more complicated.
186 //
187 // NOTE: One significant difference between LLD and ld64 is that we merge all
188 // cstring literals, even those referenced directly by non-private symbols.
189 // ld64 is more conservative and does not do that. This was mostly done for
190 // implementation simplicity; if we find programs that need the more
191 // conservative behavior we can certainly implement that.
192 class CStringInputSection final : public InputSection {
193 public:
194   CStringInputSection(const Section &section, ArrayRef<uint8_t> data,
195                       uint32_t align)
196       : InputSection(CStringLiteralKind, section, data, align) {}
197   uint64_t getOffset(uint64_t off) const override;
198   bool isLive(uint64_t off) const override { return getStringPiece(off).live; }
199   void markLive(uint64_t off) override { getStringPiece(off).live = true; }
200   // Find the StringPiece that contains this offset.
201   StringPiece &getStringPiece(uint64_t off);
202   const StringPiece &getStringPiece(uint64_t off) const;
203   // Split at each null byte.
204   void splitIntoPieces();
205 
206   LLVM_ATTRIBUTE_ALWAYS_INLINE
207   StringRef getStringRef(size_t i) const {
208     size_t begin = pieces[i].inSecOff;
209     size_t end =
210         (pieces.size() - 1 == i) ? data.size() : pieces[i + 1].inSecOff;
211     return toStringRef(data.slice(begin, end - begin));
212   }
213 
214   // Returns i'th piece as a CachedHashStringRef. This function is very hot when
215   // string merging is enabled, so we want to inline.
216   LLVM_ATTRIBUTE_ALWAYS_INLINE
217   llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
218     assert(config->dedupLiterals);
219     return {getStringRef(i), pieces[i].hash};
220   }
221 
222   static bool classof(const InputSection *isec) {
223     return isec->kind() == CStringLiteralKind;
224   }
225 
226   std::vector<StringPiece> pieces;
227 };
228 
229 class WordLiteralInputSection final : public InputSection {
230 public:
231   WordLiteralInputSection(const Section &section, ArrayRef<uint8_t> data,
232                           uint32_t align);
233   uint64_t getOffset(uint64_t off) const override;
234   bool isLive(uint64_t off) const override {
235     return live[off >> power2LiteralSize];
236   }
237   void markLive(uint64_t off) override {
238     live[off >> power2LiteralSize] = true;
239   }
240 
241   static bool classof(const InputSection *isec) {
242     return isec->kind() == WordLiteralKind;
243   }
244 
245 private:
246   unsigned power2LiteralSize;
247   // The liveness of data[off] is tracked by live[off >> power2LiteralSize].
248   llvm::BitVector live;
249 };
250 
251 inline uint8_t sectionType(uint32_t flags) {
252   return flags & llvm::MachO::SECTION_TYPE;
253 }
254 
255 inline bool isZeroFill(uint32_t flags) {
256   return llvm::MachO::isVirtualSection(sectionType(flags));
257 }
258 
259 inline bool isThreadLocalVariables(uint32_t flags) {
260   return sectionType(flags) == llvm::MachO::S_THREAD_LOCAL_VARIABLES;
261 }
262 
263 // These sections contain the data for initializing thread-local variables.
264 inline bool isThreadLocalData(uint32_t flags) {
265   return sectionType(flags) == llvm::MachO::S_THREAD_LOCAL_REGULAR ||
266          sectionType(flags) == llvm::MachO::S_THREAD_LOCAL_ZEROFILL;
267 }
268 
269 inline bool isDebugSection(uint32_t flags) {
270   return (flags & llvm::MachO::SECTION_ATTRIBUTES_USR) ==
271          llvm::MachO::S_ATTR_DEBUG;
272 }
273 
274 inline bool isWordLiteralSection(uint32_t flags) {
275   return sectionType(flags) == llvm::MachO::S_4BYTE_LITERALS ||
276          sectionType(flags) == llvm::MachO::S_8BYTE_LITERALS ||
277          sectionType(flags) == llvm::MachO::S_16BYTE_LITERALS;
278 }
279 
280 bool isCodeSection(const InputSection *);
281 bool isCfStringSection(const InputSection *);
282 bool isClassRefsSection(const InputSection *);
283 bool isEhFrameSection(const InputSection *);
284 bool isGccExceptTabSection(const InputSection *);
285 
286 extern std::vector<ConcatInputSection *> inputSections;
287 
288 namespace section_names {
289 
290 constexpr const char authGot[] = "__auth_got";
291 constexpr const char authPtr[] = "__auth_ptr";
292 constexpr const char binding[] = "__binding";
293 constexpr const char bitcodeBundle[] = "__bundle";
294 constexpr const char cString[] = "__cstring";
295 constexpr const char cfString[] = "__cfstring";
296 constexpr const char cgProfile[] = "__cg_profile";
297 constexpr const char codeSignature[] = "__code_signature";
298 constexpr const char common[] = "__common";
299 constexpr const char compactUnwind[] = "__compact_unwind";
300 constexpr const char data[] = "__data";
301 constexpr const char debugAbbrev[] = "__debug_abbrev";
302 constexpr const char debugInfo[] = "__debug_info";
303 constexpr const char debugLine[] = "__debug_line";
304 constexpr const char debugStr[] = "__debug_str";
305 constexpr const char ehFrame[] = "__eh_frame";
306 constexpr const char gccExceptTab[] = "__gcc_except_tab";
307 constexpr const char export_[] = "__export";
308 constexpr const char dataInCode[] = "__data_in_code";
309 constexpr const char functionStarts[] = "__func_starts";
310 constexpr const char got[] = "__got";
311 constexpr const char header[] = "__mach_header";
312 constexpr const char indirectSymbolTable[] = "__ind_sym_tab";
313 constexpr const char const_[] = "__const";
314 constexpr const char lazySymbolPtr[] = "__la_symbol_ptr";
315 constexpr const char lazyBinding[] = "__lazy_binding";
316 constexpr const char literals[] = "__literals";
317 constexpr const char moduleInitFunc[] = "__mod_init_func";
318 constexpr const char moduleTermFunc[] = "__mod_term_func";
319 constexpr const char nonLazySymbolPtr[] = "__nl_symbol_ptr";
320 constexpr const char objcCatList[] = "__objc_catlist";
321 constexpr const char objcClassList[] = "__objc_classlist";
322 constexpr const char objcClassRefs[] = "__objc_classrefs";
323 constexpr const char objcConst[] = "__objc_const";
324 constexpr const char objCImageInfo[] = "__objc_imageinfo";
325 constexpr const char objcNonLazyCatList[] = "__objc_nlcatlist";
326 constexpr const char objcNonLazyClassList[] = "__objc_nlclslist";
327 constexpr const char objcProtoList[] = "__objc_protolist";
328 constexpr const char pageZero[] = "__pagezero";
329 constexpr const char pointers[] = "__pointers";
330 constexpr const char rebase[] = "__rebase";
331 constexpr const char staticInit[] = "__StaticInit";
332 constexpr const char stringTable[] = "__string_table";
333 constexpr const char stubHelper[] = "__stub_helper";
334 constexpr const char stubs[] = "__stubs";
335 constexpr const char swift[] = "__swift";
336 constexpr const char symbolTable[] = "__symbol_table";
337 constexpr const char textCoalNt[] = "__textcoal_nt";
338 constexpr const char text[] = "__text";
339 constexpr const char threadPtrs[] = "__thread_ptrs";
340 constexpr const char threadVars[] = "__thread_vars";
341 constexpr const char unwindInfo[] = "__unwind_info";
342 constexpr const char weakBinding[] = "__weak_binding";
343 constexpr const char zeroFill[] = "__zerofill";
344 constexpr const char addrSig[] = "__llvm_addrsig";
345 
346 } // namespace section_names
347 
348 } // namespace macho
349 
350 std::string toString(const macho::InputSection *);
351 
352 } // namespace lld
353 
354 #endif
355