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 "Thunks.h"
15#include "lld/Common/LLVM.h"
16#include "llvm/ADT/CachedHashString.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/TinyPtrVector.h"
19#include "llvm/Object/ELF.h"
20
21namespace lld {
22namespace elf {
23
24class Symbol;
25struct SectionPiece;
26
27class Defined;
28struct Partition;
29class SyntheticSection;
30class MergeSyntheticSection;
31template <class ELFT> class ObjFile;
32class OutputSection;
33
34extern std::vector<Partition> partitions;
35
36// This is the base class of all sections that lld handles. Some are sections in
37// input files, some are sections in the produced output file and some exist
38// just as a convenience for implementing special ways of combining some
39// sections.
40class SectionBase {
41public:
42  enum Kind { Regular, EHFrame, Merge, Synthetic, Output };
43
44  Kind kind() const { return (Kind)sectionKind; }
45
46  StringRef name;
47
48  // This pointer points to the "real" instance of this instance.
49  // Usually Repl == this. However, if ICF merges two sections,
50  // Repl pointer of one section points to another section. So,
51  // if you need to get a pointer to this instance, do not use
52  // this but instead this->Repl.
53  SectionBase *repl;
54
55  unsigned sectionKind : 3;
56
57  // The next two bit fields are only used by InputSectionBase, but we
58  // put them here so the struct packs better.
59
60  unsigned bss : 1;
61
62  // Set for sections that should not be folded by ICF.
63  unsigned keepUnique : 1;
64
65  // The 1-indexed partition that this section is assigned to by the garbage
66  // collector, or 0 if this section is dead. Normally there is only one
67  // partition, so this will either be 0 or 1.
68  uint8_t partition;
69  elf::Partition &getPartition() const;
70
71  // These corresponds to the fields in Elf_Shdr.
72  uint32_t alignment;
73  uint64_t flags;
74  uint64_t entsize;
75  uint32_t type;
76  uint32_t link;
77  uint32_t info;
78
79  OutputSection *getOutputSection();
80  const OutputSection *getOutputSection() const {
81    return const_cast<SectionBase *>(this)->getOutputSection();
82  }
83
84  // Translate an offset in the input section to an offset in the output
85  // section.
86  uint64_t getOffset(uint64_t offset) const;
87
88  uint64_t getVA(uint64_t offset = 0) const;
89
90  bool isLive() const { return partition != 0; }
91  void markLive() { partition = 1; }
92  void markDead() { partition = 0; }
93
94protected:
95  SectionBase(Kind sectionKind, StringRef name, uint64_t flags,
96              uint64_t entsize, uint64_t alignment, uint32_t type,
97              uint32_t info, uint32_t link)
98      : name(name), repl(this), sectionKind(sectionKind), bss(false),
99        keepUnique(false), partition(0), alignment(alignment), flags(flags),
100        entsize(entsize), type(type), link(link), info(info) {}
101};
102
103// This corresponds to a section of an input file.
104class InputSectionBase : public SectionBase {
105public:
106  template <class ELFT>
107  InputSectionBase(ObjFile<ELFT> &file, const typename ELFT::Shdr &header,
108                   StringRef name, Kind sectionKind);
109
110  InputSectionBase(InputFile *file, uint64_t flags, uint32_t type,
111                   uint64_t entsize, uint32_t link, uint32_t info,
112                   uint32_t alignment, ArrayRef<uint8_t> data, StringRef name,
113                   Kind sectionKind);
114
115  static bool classof(const SectionBase *s) { return s->kind() != Output; }
116
117  // Relocations that refer to this section.
118  unsigned numRelocations : 31;
119  unsigned areRelocsRela : 1;
120  const void *firstRelocation = nullptr;
121
122  // The file which contains this section. Its dynamic type is always
123  // ObjFile<ELFT>, but in order to avoid ELFT, we use InputFile as
124  // its static type.
125  InputFile *file;
126
127  template <class ELFT> ObjFile<ELFT> *getFile() const {
128    return cast_or_null<ObjFile<ELFT>>(file);
129  }
130
131  // If basic block sections are enabled, many code sections could end up with
132  // one or two jump instructions at the end that could be relaxed to a smaller
133  // instruction. The members below help trimming the trailing jump instruction
134  // and shrinking a section.
135  unsigned bytesDropped = 0;
136
137  void drop_back(uint64_t num) { bytesDropped += num; }
138
139  void push_back(uint64_t num) {
140    assert(bytesDropped >= num);
141    bytesDropped -= num;
142  }
143
144  void trim() {
145    if (bytesDropped) {
146      rawData = rawData.drop_back(bytesDropped);
147      bytesDropped = 0;
148    }
149  }
150
151  ArrayRef<uint8_t> data() const {
152    if (uncompressedSize >= 0)
153      uncompress();
154    return rawData;
155  }
156
157  uint64_t getOffsetInFile() const;
158
159  // Input sections are part of an output section. Special sections
160  // like .eh_frame and merge sections are first combined into a
161  // synthetic section that is then added to an output section. In all
162  // cases this points one level up.
163  SectionBase *parent = nullptr;
164
165  // The next member in the section group if this section is in a group. This is
166  // used by --gc-sections.
167  InputSectionBase *nextInSectionGroup = nullptr;
168
169  template <class ELFT> ArrayRef<typename ELFT::Rel> rels() const {
170    assert(!areRelocsRela);
171    return llvm::makeArrayRef(
172        static_cast<const typename ELFT::Rel *>(firstRelocation),
173        numRelocations);
174  }
175
176  template <class ELFT> ArrayRef<typename ELFT::Rela> relas() const {
177    assert(areRelocsRela);
178    return llvm::makeArrayRef(
179        static_cast<const typename ELFT::Rela *>(firstRelocation),
180        numRelocations);
181  }
182
183  // InputSections that are dependent on us (reverse dependency for GC)
184  llvm::TinyPtrVector<InputSection *> dependentSections;
185
186  // Returns the size of this section (even if this is a common or BSS.)
187  size_t getSize() const;
188
189  InputSection *getLinkOrderDep() const;
190
191  // Get the function symbol that encloses this offset from within the
192  // section.
193  template <class ELFT>
194  Defined *getEnclosingFunction(uint64_t offset);
195
196  // Returns a source location string. Used to construct an error message.
197  template <class ELFT> std::string getLocation(uint64_t offset);
198  std::string getSrcMsg(const Symbol &sym, uint64_t offset);
199  std::string getObjMsg(uint64_t offset);
200
201  // Each section knows how to relocate itself. These functions apply
202  // relocations, assuming that Buf points to this section's copy in
203  // the mmap'ed output buffer.
204  template <class ELFT> void relocate(uint8_t *buf, uint8_t *bufEnd);
205  void relocateAlloc(uint8_t *buf, uint8_t *bufEnd);
206  static uint64_t getRelocTargetVA(const InputFile *File, RelType Type,
207                                   int64_t A, uint64_t P, const Symbol &Sym,
208                                   RelExpr Expr);
209
210  // The native ELF reloc data type is not very convenient to handle.
211  // So we convert ELF reloc records to our own records in Relocations.cpp.
212  // This vector contains such "cooked" relocations.
213  std::vector<Relocation> relocations;
214
215  // Indicates that this section needs to be padded with a NOP filler if set to
216  // true.
217  bool nopFiller = false;
218
219  // These are modifiers to jump instructions that are necessary when basic
220  // block sections are enabled.  Basic block sections creates opportunities to
221  // relax jump instructions at basic block boundaries after reordering the
222  // basic blocks.
223  std::vector<JumpInstrMod> jumpInstrMods;
224
225  // A function compiled with -fsplit-stack calling a function
226  // compiled without -fsplit-stack needs its prologue adjusted. Find
227  // such functions and adjust their prologues.  This is very similar
228  // to relocation. See https://gcc.gnu.org/wiki/SplitStacks for more
229  // information.
230  template <typename ELFT>
231  void adjustSplitStackFunctionPrologues(uint8_t *buf, uint8_t *end);
232
233
234  template <typename T> llvm::ArrayRef<T> getDataAs() const {
235    size_t s = data().size();
236    assert(s % sizeof(T) == 0);
237    return llvm::makeArrayRef<T>((const T *)data().data(), s / sizeof(T));
238  }
239
240protected:
241  void parseCompressedHeader();
242  void uncompress() const;
243
244  mutable ArrayRef<uint8_t> rawData;
245
246  // This field stores the uncompressed size of the compressed data in rawData,
247  // or -1 if rawData is not compressed (either because the section wasn't
248  // compressed in the first place, or because we ended up uncompressing it).
249  // Since the feature is not used often, this is usually -1.
250  mutable int64_t uncompressedSize = -1;
251};
252
253// SectionPiece represents a piece of splittable section contents.
254// We allocate a lot of these and binary search on them. This means that they
255// have to be as compact as possible, which is why we don't store the size (can
256// be found by looking at the next one).
257struct SectionPiece {
258  SectionPiece(size_t off, uint32_t hash, bool live)
259      : inputOff(off), live(live || !config->gcSections), hash(hash >> 1) {}
260
261  uint32_t inputOff;
262  uint32_t live : 1;
263  uint32_t hash : 31;
264  uint64_t outputOff = 0;
265};
266
267static_assert(sizeof(SectionPiece) == 16, "SectionPiece is too big");
268
269// This corresponds to a SHF_MERGE section of an input file.
270class MergeInputSection : public InputSectionBase {
271public:
272  template <class ELFT>
273  MergeInputSection(ObjFile<ELFT> &f, const typename ELFT::Shdr &header,
274                    StringRef name);
275  MergeInputSection(uint64_t flags, uint32_t type, uint64_t entsize,
276                    ArrayRef<uint8_t> data, StringRef name);
277
278  static bool classof(const SectionBase *s) { return s->kind() == Merge; }
279  void splitIntoPieces();
280
281  // Translate an offset in the input section to an offset in the parent
282  // MergeSyntheticSection.
283  uint64_t getParentOffset(uint64_t offset) const;
284
285  // Splittable sections are handled as a sequence of data
286  // rather than a single large blob of data.
287  std::vector<SectionPiece> pieces;
288
289  // Returns I'th piece's data. This function is very hot when
290  // string merging is enabled, so we want to inline.
291  LLVM_ATTRIBUTE_ALWAYS_INLINE
292  llvm::CachedHashStringRef getData(size_t i) const {
293    size_t begin = pieces[i].inputOff;
294    size_t end =
295        (pieces.size() - 1 == i) ? data().size() : pieces[i + 1].inputOff;
296    return {toStringRef(data().slice(begin, end - begin)), pieces[i].hash};
297  }
298
299  // Returns the SectionPiece at a given input section offset.
300  SectionPiece *getSectionPiece(uint64_t offset);
301  const SectionPiece *getSectionPiece(uint64_t offset) const {
302    return const_cast<MergeInputSection *>(this)->getSectionPiece(offset);
303  }
304
305  SyntheticSection *getParent() const;
306
307private:
308  void splitStrings(ArrayRef<uint8_t> a, size_t size);
309  void splitNonStrings(ArrayRef<uint8_t> a, size_t size);
310};
311
312struct EhSectionPiece {
313  EhSectionPiece(size_t off, InputSectionBase *sec, uint32_t size,
314                 unsigned firstRelocation)
315      : inputOff(off), sec(sec), size(size), firstRelocation(firstRelocation) {}
316
317  ArrayRef<uint8_t> data() {
318    return {sec->data().data() + this->inputOff, size};
319  }
320
321  size_t inputOff;
322  ssize_t outputOff = -1;
323  InputSectionBase *sec;
324  uint32_t size;
325  unsigned firstRelocation;
326};
327
328// This corresponds to a .eh_frame section of an input file.
329class EhInputSection : public InputSectionBase {
330public:
331  template <class ELFT>
332  EhInputSection(ObjFile<ELFT> &f, const typename ELFT::Shdr &header,
333                 StringRef name);
334  static bool classof(const SectionBase *s) { return s->kind() == EHFrame; }
335  template <class ELFT> void split();
336  template <class ELFT, class RelTy> void split(ArrayRef<RelTy> rels);
337
338  // Splittable sections are handled as a sequence of data
339  // rather than a single large blob of data.
340  std::vector<EhSectionPiece> pieces;
341
342  SyntheticSection *getParent() const;
343};
344
345// This is a section that is added directly to an output section
346// instead of needing special combination via a synthetic section. This
347// includes all input sections with the exceptions of SHF_MERGE and
348// .eh_frame. It also includes the synthetic sections themselves.
349class InputSection : public InputSectionBase {
350public:
351  InputSection(InputFile *f, uint64_t flags, uint32_t type, uint32_t alignment,
352               ArrayRef<uint8_t> data, StringRef name, Kind k = Regular);
353  template <class ELFT>
354  InputSection(ObjFile<ELFT> &f, const typename ELFT::Shdr &header,
355               StringRef name);
356
357  // Write this section to a mmap'ed file, assuming Buf is pointing to
358  // beginning of the output section.
359  template <class ELFT> void writeTo(uint8_t *buf);
360
361  uint64_t getOffset(uint64_t offset) const { return outSecOff + offset; }
362
363  OutputSection *getParent() const;
364
365  // This variable has two usages. Initially, it represents an index in the
366  // OutputSection's InputSection list, and is used when ordering SHF_LINK_ORDER
367  // sections. After assignAddresses is called, it represents the offset from
368  // the beginning of the output section this section was assigned to.
369  uint64_t outSecOff = 0;
370
371  static bool classof(const SectionBase *s);
372
373  InputSectionBase *getRelocatedSection() const;
374
375  template <class ELFT, class RelTy>
376  void relocateNonAlloc(uint8_t *buf, llvm::ArrayRef<RelTy> rels);
377
378  // Used by ICF.
379  uint32_t eqClass[2] = {0, 0};
380
381  // Called by ICF to merge two input sections.
382  void replace(InputSection *other);
383
384  static InputSection discarded;
385
386private:
387  template <class ELFT, class RelTy>
388  void copyRelocations(uint8_t *buf, llvm::ArrayRef<RelTy> rels);
389
390  template <class ELFT> void copyShtGroup(uint8_t *buf);
391};
392
393inline bool isDebugSection(const InputSectionBase &sec) {
394  return (sec.flags & llvm::ELF::SHF_ALLOC) == 0 &&
395         (sec.name.startswith(".debug") || sec.name.startswith(".zdebug"));
396}
397
398// The list of all input sections.
399extern std::vector<InputSectionBase *> inputSections;
400
401// The set of TOC entries (.toc + addend) for which we should not apply
402// toc-indirect to toc-relative relaxation. const Symbol * refers to the
403// STT_SECTION symbol associated to the .toc input section.
404extern llvm::DenseSet<std::pair<const Symbol *, uint64_t>> ppc64noTocRelax;
405
406} // namespace elf
407
408std::string toString(const elf::InputSectionBase *);
409} // namespace lld
410
411#endif
412