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_ELF_INPUT_SECTION_H
10#define LLD_ELF_INPUT_SECTION_H
11
12#include "Config.h"
13#include "Relocations.h"
14#include "lld/Common/CommonLinkerContext.h"
15#include "lld/Common/LLVM.h"
16#include "lld/Common/Memory.h"
17#include "llvm/ADT/CachedHashString.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/StringExtras.h"
20#include "llvm/ADT/TinyPtrVector.h"
21#include "llvm/Object/ELF.h"
22#include "llvm/Support/Compiler.h"
23
24namespace lld {
25namespace elf {
26
27class InputFile;
28class Symbol;
29
30class Defined;
31class SyntheticSection;
32template <class ELFT> class ObjFile;
33class OutputSection;
34
35// Returned by InputSectionBase::relsOrRelas. At least two members are empty.
36template <class ELFT> struct RelsOrRelas {
37 Relocs<typename ELFT::Rel> rels;
38 Relocs<typename ELFT::Rela> relas;
39 Relocs<typename ELFT::Crel> crels;
40 bool areRelocsRel() const { return rels.size(); }
41 bool areRelocsCrel() const { return crels.size(); }
42};
43
44#define invokeOnRelocs(sec, f, ...) \
45 { \
46 const RelsOrRelas<ELFT> rs = (sec).template relsOrRelas<ELFT>(); \
47 if (rs.areRelocsCrel()) \
48 f(__VA_ARGS__, rs.crels); \
49 else if (rs.areRelocsRel()) \
50 f(__VA_ARGS__, rs.rels); \
51 else \
52 f(__VA_ARGS__, rs.relas); \
53 }
54
55// This is the base class of all sections that lld handles. Some are sections in
56// input files, some are sections in the produced output file and some exist
57// just as a convenience for implementing special ways of combining some
58// sections.
59class SectionBase {
60public:
61 enum Kind : uint8_t {
62 Regular,
63 Synthetic,
64 Spill,
65 EHFrame,
66 Merge,
67 Output,
68 Class,
69 };
70
71 Kind kind() const { return sectionKind; }
72
73 // The file which contains this section. For InputSectionBase, its dynamic
74 // type is usually ObjFile<ELFT>, but may be an InputFile of InternalKind
75 // (for a synthetic section).
76 InputFile *file;
77
78 StringRef name;
79
80 // These corresponds to the fields in Elf_Shdr.
81 uint64_t flags;
82 uint32_t type;
83 uint32_t link;
84 uint32_t info;
85 uint32_t addralign;
86 uint32_t entsize;
87
88 Kind sectionKind;
89 // 0 (dead) or 1 (live).
90 uint8_t partition = 1;
91
92 // The next two bit fields are only used by InputSectionBase, but we
93 // put them here so the struct packs better.
94
95 Ctx &getCtx() const;
96 OutputSection *getOutputSection();
97 const OutputSection *getOutputSection() const {
98 return const_cast<SectionBase *>(this)->getOutputSection();
99 }
100
101 // Translate an offset in the input section to an offset in the output
102 // section.
103 uint64_t getOffset(uint64_t offset) const;
104
105 uint64_t getVA(uint64_t offset = 0) const;
106
107 bool isLive() const { return partition != 0; }
108 void markLive() { partition = 1; }
109 void markDead() { partition = 0; }
110
111protected:
112 constexpr SectionBase(Kind sectionKind, InputFile *file, StringRef name,
113 uint32_t type, uint64_t flags, uint32_t link,
114 uint32_t info, uint32_t addralign, uint32_t entsize)
115 : file(file), name(name), flags(flags), type(type), link(link),
116 info(info), addralign(addralign), entsize(entsize),
117 sectionKind(sectionKind) {}
118};
119
120struct SymbolAnchor {
121 uint64_t offset;
122 Defined *d;
123 bool end; // true for the anchor of st_value+st_size
124};
125
126struct RelaxAux {
127 // This records symbol start and end offsets which will be adjusted according
128 // to the nearest relocDeltas element.
129 SmallVector<SymbolAnchor, 0> anchors;
130 // For relocations[i], the actual offset is
131 // r_offset - (i ? relocDeltas[i-1] : 0).
132 std::unique_ptr<uint32_t[]> relocDeltas;
133 // For relocations[i], the actual type is relocTypes[i].
134 std::unique_ptr<RelType[]> relocTypes;
135 SmallVector<uint32_t, 0> writes;
136};
137
138// This corresponds to a section of an input file.
139class InputSectionBase : public SectionBase {
140public:
141 struct ObjMsg {
142 const InputSectionBase *sec;
143 uint64_t offset;
144 };
145 struct SrcMsg {
146 const InputSectionBase &sec;
147 const Symbol &sym;
148 uint64_t offset;
149 };
150
151 template <class ELFT>
152 InputSectionBase(ObjFile<ELFT> &file, const typename ELFT::Shdr &header,
153 StringRef name, Kind sectionKind);
154
155 InputSectionBase(InputFile *file, StringRef name, uint32_t type,
156 uint64_t flags, uint32_t link, uint32_t info,
157 uint32_t addralign, uint32_t entsize, ArrayRef<uint8_t> data,
158 Kind sectionKind);
159
160 static bool classof(const SectionBase *s) {
161 return s->kind() != Output && s->kind() != Class;
162 }
163
164 LLVM_PREFERRED_TYPE(bool)
165 uint8_t bss : 1;
166
167 // Whether this section is SHT_CREL and has been decoded to RELA by
168 // relsOrRelas.
169 LLVM_PREFERRED_TYPE(bool)
170 uint8_t decodedCrel : 1;
171
172 // Set for sections that should not be folded by ICF.
173 LLVM_PREFERRED_TYPE(bool)
174 uint8_t keepUnique : 1;
175
176 // Whether the section needs to be padded with a NOP filler due to
177 // deleteFallThruJmpInsn.
178 LLVM_PREFERRED_TYPE(bool)
179 uint8_t nopFiller : 1;
180
181 mutable bool compressed = false;
182
183 // Input sections are part of an output section. Special sections
184 // like .eh_frame and merge sections are first combined into a
185 // synthetic section that is then added to an output section. In all
186 // cases this points one level up.
187 SectionBase *parent = nullptr;
188
189 // Section index of the relocation section if exists.
190 uint32_t relSecIdx = 0;
191
192 // Getter when the dynamic type is ObjFile<ELFT>.
193 template <class ELFT> ObjFile<ELFT> *getFile() const {
194 return cast<ObjFile<ELFT>>(file);
195 }
196
197 // Used by --optimize-bb-jumps and RISC-V linker relaxation temporarily to
198 // indicate the number of bytes which is not counted in the size. This should
199 // be reset to zero after uses.
200 uint32_t bytesDropped = 0;
201
202 void drop_back(unsigned num) {
203 assert(bytesDropped + num < 256);
204 bytesDropped += num;
205 }
206
207 mutable const uint8_t *content_;
208 uint64_t size;
209
210 void trim() {
211 if (bytesDropped) {
212 size -= bytesDropped;
213 bytesDropped = 0;
214 }
215 }
216
217 ArrayRef<uint8_t> content() const {
218 return ArrayRef<uint8_t>(content_, size);
219 }
220 ArrayRef<uint8_t> contentMaybeDecompress() const {
221 if (compressed)
222 decompress();
223 return content();
224 }
225
226 // The next member in the section group if this section is in a group. This is
227 // used by --gc-sections.
228 InputSectionBase *nextInSectionGroup = nullptr;
229
230 template <class ELFT>
231 RelsOrRelas<ELFT> relsOrRelas(bool supportsCrel = true) const;
232
233 // InputSections that are dependent on us (reverse dependency for GC)
234 llvm::TinyPtrVector<InputSection *> dependentSections;
235
236 // Returns the size of this section (even if this is a common or BSS.)
237 size_t getSize() const;
238
239 InputSection *getLinkOrderDep() const;
240
241 // Get a symbol that encloses this offset from within the section. If type is
242 // not zero, return a symbol with the specified type.
243 Defined *getEnclosingSymbol(uint64_t offset, uint8_t type = 0) const;
244 Defined *getEnclosingFunction(uint64_t offset) const {
245 return getEnclosingSymbol(offset, type: llvm::ELF::STT_FUNC);
246 }
247
248 // Returns a source location string. Used to construct an error message.
249 std::string getLocation(uint64_t offset) const;
250 ObjMsg getObjMsg(uint64_t offset) const { return {.sec: this, .offset: offset}; }
251 SrcMsg getSrcMsg(const Symbol &sym, uint64_t offset) const {
252 return {.sec: *this, .sym: sym, .offset: offset};
253 }
254
255 uint64_t getRelocTargetVA(Ctx &, const Relocation &r, uint64_t p) const;
256
257 // The native ELF reloc data type is not very convenient to handle.
258 // So we convert ELF reloc records to our own records in Relocations.cpp.
259 // This vector contains such "cooked" relocations.
260 SmallVector<Relocation, 0> relocations;
261
262 void addReloc(const Relocation &r) { relocations.push_back(Elt: r); }
263 MutableArrayRef<Relocation> relocs() { return relocations; }
264 ArrayRef<Relocation> relocs() const { return relocations; }
265
266 union {
267 // These are modifiers to jump instructions that are necessary when basic
268 // block sections are enabled. Basic block sections creates opportunities
269 // to relax jump instructions at basic block boundaries after reordering the
270 // basic blocks.
271 JumpInstrMod *jumpInstrMod = nullptr;
272
273 // Auxiliary information for RISC-V and LoongArch linker relaxation.
274 // They do not use jumpInstrMod.
275 RelaxAux *relaxAux;
276
277 // The compressed content size when `compressed` is true.
278 size_t compressedSize;
279 };
280
281 // A function compiled with -fsplit-stack calling a function
282 // compiled without -fsplit-stack needs its prologue adjusted. Find
283 // such functions and adjust their prologues. This is very similar
284 // to relocation. See https://gcc.gnu.org/wiki/SplitStacks for more
285 // information.
286 template <typename ELFT>
287 void adjustSplitStackFunctionPrologues(Ctx &, uint8_t *buf, uint8_t *end);
288
289 template <typename T> llvm::ArrayRef<T> getDataAs() const {
290 size_t s = content().size();
291 assert(s % sizeof(T) == 0);
292 assert(reinterpret_cast<uintptr_t>(content().data()) % alignof(T) == 0);
293 return llvm::ArrayRef<T>((const T *)content().data(), s / sizeof(T));
294 }
295
296protected:
297 template <typename ELFT> void parseCompressedHeader(Ctx &);
298 void decompress() const;
299};
300
301// SectionPiece represents a piece of splittable section contents.
302// We allocate a lot of these and binary search on them. This means that they
303// have to be as compact as possible, which is why we don't store the size (can
304// be found by looking at the next one).
305struct SectionPiece {
306 SectionPiece() = default;
307 SectionPiece(size_t off, uint32_t hash, bool live)
308 : inputOff(off), live(live), hash(hash >> 1) {}
309
310 uint32_t inputOff;
311 LLVM_PREFERRED_TYPE(bool)
312 uint32_t live : 1;
313 uint32_t hash : 31;
314 uint64_t outputOff = 0;
315};
316
317static_assert(sizeof(SectionPiece) == 16, "SectionPiece is too big");
318
319// Used by splitSections to pre-resolve section piece indexes. 32 bits of offset
320// supports section piece up to 4GB.
321constexpr unsigned mergeValueShift = 32;
322
323// This corresponds to a SHF_MERGE section of an input file.
324class MergeInputSection : public InputSectionBase {
325public:
326 template <class ELFT>
327 MergeInputSection(ObjFile<ELFT> &f, const typename ELFT::Shdr &header,
328 StringRef name);
329 MergeInputSection(Ctx &, StringRef name, uint32_t type, uint64_t flags,
330 uint64_t entsize, ArrayRef<uint8_t> data);
331
332 static bool classof(const SectionBase *s) { return s->kind() == Merge; }
333 void splitIntoPieces();
334
335 // Translate an offset in the input section to an offset in the parent
336 // MergeSyntheticSection. If the offset was pre-resolved by
337 // resolveSymbolPieces (upper bits non-zero), this is O(1).
338 uint64_t getParentOffset(uint64_t offset) const;
339
340 // Splittable sections are handled as a sequence of data
341 // rather than a single large blob of data.
342 SmallVector<SectionPiece, 0> pieces;
343
344 // Returns I'th piece's data. This function is very hot when
345 // string merging is enabled, so we want to inline.
346 LLVM_ATTRIBUTE_ALWAYS_INLINE
347 llvm::CachedHashStringRef getData(size_t i) const {
348 size_t begin = pieces[i].inputOff;
349 size_t end =
350 (pieces.size() - 1 == i) ? content().size() : pieces[i + 1].inputOff;
351 return {toStringRef(Input: content().slice(N: begin, M: end - begin)), pieces[i].hash};
352 }
353
354 // Returns the SectionPiece at a given input section offset.
355 SectionPiece &getSectionPiece(uint64_t offset);
356 const SectionPiece &getSectionPiece(uint64_t offset) const {
357 return const_cast<MergeInputSection *>(this)->getSectionPiece(offset);
358 }
359
360 SyntheticSection *getParent() const {
361 return cast_or_null<SyntheticSection>(Val: parent);
362 }
363
364private:
365 void splitStrings(StringRef s, size_t size);
366 void splitNonStrings(ArrayRef<uint8_t> a, size_t size);
367};
368
369struct EhSectionPiece {
370 EhSectionPiece(size_t off, InputSectionBase *sec, uint32_t size,
371 unsigned firstRelocation)
372 : inputOff(off), sec(sec), size(size), firstRelocation(firstRelocation) {}
373
374 ArrayRef<uint8_t> data() const {
375 return {sec->content().data() + this->inputOff, size};
376 }
377
378 size_t inputOff;
379 ssize_t outputOff = -1;
380 InputSectionBase *sec;
381 uint32_t size;
382 unsigned firstRelocation;
383};
384
385// This corresponds to a .eh_frame section of an input file.
386class EhInputSection : public InputSectionBase {
387public:
388 template <class ELFT>
389 EhInputSection(ObjFile<ELFT> &f, const typename ELFT::Shdr &header,
390 StringRef name);
391 static bool classof(const SectionBase *s) { return s->kind() == EHFrame; }
392 template <class ELFT> void split();
393 template <class ELFT, class RelTy> void preprocessRelocs(Relocs<RelTy> rels);
394
395 // Splittable sections are handled as a sequence of data
396 // rather than a single large blob of data.
397 SmallVector<EhSectionPiece, 0> cies, fdes;
398
399 SyntheticSection *getParent() const;
400 uint64_t getParentOffset(uint64_t offset) const;
401
402 // Preprocessed relocations in uniform format to avoid REL/RELA/CREL
403 // relocation format handling throughout the codebase.
404 SmallVector<Relocation, 0> rels;
405};
406
407// This is a section that is added directly to an output section
408// instead of needing special combination via a synthetic section. This
409// includes all input sections with the exceptions of SHF_MERGE and
410// .eh_frame. It also includes the synthetic sections themselves.
411class InputSection : public InputSectionBase {
412public:
413 InputSection(InputFile *f, StringRef name, uint32_t type, uint64_t flags,
414 uint32_t addralign, uint32_t entsize, ArrayRef<uint8_t> data,
415 Kind k = Regular);
416 template <class ELFT>
417 InputSection(ObjFile<ELFT> &f, const typename ELFT::Shdr &header,
418 StringRef name);
419
420 static bool classof(const SectionBase *s) {
421 return s->kind() == SectionBase::Regular ||
422 s->kind() == SectionBase::Synthetic ||
423 s->kind() == SectionBase::Spill;
424 }
425
426 // Write this section to a mmap'ed file, assuming Buf is pointing to
427 // beginning of the output section.
428 template <class ELFT> void writeTo(Ctx &, uint8_t *buf);
429
430 OutputSection *getParent() const {
431 return reinterpret_cast<OutputSection *>(parent);
432 }
433
434 // This variable has two usages. Initially, it represents an index in the
435 // OutputSection's InputSection list, and is used when ordering SHF_LINK_ORDER
436 // sections. After assignAddresses is called, it represents the offset from
437 // the beginning of the output section this section was assigned to.
438 uint64_t outSecOff = 0;
439
440 InputSectionBase *getRelocatedSection() const;
441
442 // Each section knows how to relocate itself. These functions apply
443 // relocations, assuming that `buf` points to this section's copy in
444 // the mmap'ed output buffer.
445 template <class ELFT, class RelTy>
446 void relocateNonAlloc(Ctx &, uint8_t *buf, Relocs<RelTy> rels);
447 template <class ELFT> void relocate(Ctx &, uint8_t *buf, uint8_t *bufEnd);
448
449 // Points to the canonical section. If ICF folds two sections, repl pointer of
450 // one section points to the other.
451 InputSection *repl = this;
452
453 // Used by ICF.
454 uint32_t eqClass[2] = {0, 0};
455
456 // Called by ICF to merge two input sections.
457 void replace(InputSection *other);
458
459 static InputSection discarded;
460
461private:
462 template <class ELFT, class RelTy> void copyRelocations(Ctx &, uint8_t *buf);
463
464 template <class ELFT, class RelTy, class RelIt>
465 void copyRelocations(Ctx &, uint8_t *buf, llvm::iterator_range<RelIt> rels);
466
467 template <class ELFT> void copyShtGroup(uint8_t *buf);
468};
469
470// A marker for a potential spill location for another input section. This
471// broadly acts as if it were the original section until address assignment.
472// Then it is either replaced with the real input section or removed.
473class PotentialSpillSection : public InputSection {
474public:
475 // The containing input section description; used to quickly replace this stub
476 // with the actual section.
477 InputSectionDescription *isd;
478
479 // Next potential spill location for the same source input section.
480 PotentialSpillSection *next = nullptr;
481
482 PotentialSpillSection(const InputSectionBase &source,
483 InputSectionDescription &isd);
484
485 static bool classof(const SectionBase *sec) {
486 return sec->kind() == InputSectionBase::Spill;
487 }
488};
489
490#ifndef _WIN32
491static_assert(sizeof(InputSection) <= 152, "InputSection is too big");
492#endif
493
494class SyntheticSection : public InputSection {
495public:
496 Ctx &ctx;
497 SyntheticSection(Ctx &ctx, StringRef name, uint32_t type, uint64_t flags,
498 uint32_t addralign)
499 : InputSection(ctx.internalFile, name, type, flags, addralign,
500 /*entsize=*/0, {}, InputSectionBase::Synthetic),
501 ctx(ctx) {}
502
503 virtual ~SyntheticSection() = default;
504 virtual size_t getSize() const = 0;
505 virtual bool updateAllocSize(Ctx &) { return false; }
506 // If the section has the SHF_ALLOC flag and the size may be changed if
507 // thunks are added, update the section size.
508 virtual bool isNeeded() const { return true; }
509 virtual void finalizeContents() {}
510 virtual void writeTo(uint8_t *buf) = 0;
511
512 static bool classof(const SectionBase *sec) {
513 return sec->kind() == InputSectionBase::Synthetic;
514 }
515};
516
517inline bool isStaticRelSecType(uint32_t type) {
518 return type == llvm::ELF::SHT_RELA || type == llvm::ELF::SHT_CREL ||
519 type == llvm::ELF::SHT_REL;
520}
521
522inline bool isDebugSection(const InputSectionBase &sec) {
523 return (sec.flags & llvm::ELF::SHF_ALLOC) == 0 &&
524 sec.name.starts_with(Prefix: ".debug");
525}
526
527std::string toStr(elf::Ctx &, const elf::InputSectionBase *);
528const ELFSyncStream &operator<<(const ELFSyncStream &,
529 const InputSectionBase *);
530const ELFSyncStream &operator<<(const ELFSyncStream &,
531 InputSectionBase::ObjMsg &&);
532const ELFSyncStream &operator<<(const ELFSyncStream &,
533 InputSectionBase::SrcMsg &&);
534} // namespace elf
535} // namespace lld
536
537#endif
538