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