1 //===- InputSection.h -------------------------------------------*- C++ -*-===//
2 //
3 //                             The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef LLD_ELF_INPUT_SECTION_H
11 #define LLD_ELF_INPUT_SECTION_H
12 
13 #include "Config.h"
14 #include "Relocations.h"
15 #include "Thunks.h"
16 #include "lld/Core/LLVM.h"
17 #include "llvm/ADT/CachedHashString.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/TinyPtrVector.h"
20 #include "llvm/Object/ELF.h"
21 #include <mutex>
22 
23 namespace lld {
24 namespace elf {
25 
26 class DefinedCommon;
27 class SymbolBody;
28 struct SectionPiece;
29 
30 template <class ELFT> class DefinedRegular;
31 template <class ELFT> class ObjectFile;
32 template <class ELFT> class OutputSection;
33 class OutputSectionBase;
34 
35 // We need non-template input section class to store symbol layout
36 // in linker script parser structures, where we do not have ELFT
37 // template parameter. For each scripted output section symbol we
38 // store pointer to preceding InputSectionData object or nullptr,
39 // if symbol should be placed at the very beginning of the output
40 // section
41 class InputSectionData {
42 public:
43   enum Kind { Regular, EHFrame, Merge, Synthetic, };
44 
45   // The garbage collector sets sections' Live bits.
46   // If GC is disabled, all sections are considered live by default.
47   InputSectionData(Kind SectionKind, StringRef Name, ArrayRef<uint8_t> Data,
48                    bool Live)
49       : SectionKind(SectionKind), Live(Live), Assigned(false), Name(Name),
50         Data(Data) {}
51 
52 private:
53   unsigned SectionKind : 3;
54 
55 public:
56   Kind kind() const { return (Kind)SectionKind; }
57 
58   unsigned Live : 1;       // for garbage collection
59   unsigned Assigned : 1;   // for linker script
60   uint32_t Alignment;
61   StringRef Name;
62   ArrayRef<uint8_t> Data;
63 
64   template <typename T> llvm::ArrayRef<T> getDataAs() const {
65     size_t S = Data.size();
66     assert(S % sizeof(T) == 0);
67     return llvm::makeArrayRef<T>((const T *)Data.data(), S / sizeof(T));
68   }
69 
70   std::vector<Relocation> Relocations;
71 };
72 
73 // This corresponds to a section of an input file.
74 template <class ELFT> class InputSectionBase : public InputSectionData {
75 protected:
76   typedef typename ELFT::Chdr Elf_Chdr;
77   typedef typename ELFT::Rel Elf_Rel;
78   typedef typename ELFT::Rela Elf_Rela;
79   typedef typename ELFT::Shdr Elf_Shdr;
80   typedef typename ELFT::Sym Elf_Sym;
81   typedef typename ELFT::uint uintX_t;
82 
83   // The file this section is from.
84   ObjectFile<ELFT> *File;
85 
86 public:
87   // These corresponds to the fields in Elf_Shdr.
88   uintX_t Flags;
89   uintX_t Offset = 0;
90   uintX_t Entsize;
91   uint32_t Type;
92   uint32_t Link;
93   uint32_t Info;
94 
95   InputSectionBase()
96       : InputSectionData(Regular, "", ArrayRef<uint8_t>(), false), Repl(this) {
97     NumRelocations = 0;
98     AreRelocsRela = false;
99   }
100 
101   InputSectionBase(ObjectFile<ELFT> *File, const Elf_Shdr *Header,
102                    StringRef Name, Kind SectionKind);
103   InputSectionBase(ObjectFile<ELFT> *File, uintX_t Flags, uint32_t Type,
104                    uintX_t Entsize, uint32_t Link, uint32_t Info,
105                    uintX_t Addralign, ArrayRef<uint8_t> Data, StringRef Name,
106                    Kind SectionKind);
107   OutputSectionBase *OutSec = nullptr;
108 
109   // Relocations that refer to this section.
110   const Elf_Rel *FirstRelocation = nullptr;
111   unsigned NumRelocations : 31;
112   unsigned AreRelocsRela : 1;
113   ArrayRef<Elf_Rel> rels() const {
114     assert(!AreRelocsRela);
115     return llvm::makeArrayRef(FirstRelocation, NumRelocations);
116   }
117   ArrayRef<Elf_Rela> relas() const {
118     assert(AreRelocsRela);
119     return llvm::makeArrayRef(static_cast<const Elf_Rela *>(FirstRelocation),
120                               NumRelocations);
121   }
122 
123   // This pointer points to the "real" instance of this instance.
124   // Usually Repl == this. However, if ICF merges two sections,
125   // Repl pointer of one section points to another section. So,
126   // if you need to get a pointer to this instance, do not use
127   // this but instead this->Repl.
128   InputSectionBase<ELFT> *Repl;
129 
130   // Returns the size of this section (even if this is a common or BSS.)
131   size_t getSize() const;
132 
133   ObjectFile<ELFT> *getFile() const { return File; }
134   llvm::object::ELFFile<ELFT> getObj() const { return File->getObj(); }
135   uintX_t getOffset(const DefinedRegular<ELFT> &Sym) const;
136   InputSectionBase *getLinkOrderDep() const;
137   // Translate an offset in the input section to an offset in the output
138   // section.
139   uintX_t getOffset(uintX_t Offset) const;
140 
141   void uncompress();
142 
143   // Returns a source location string. Used to construct an error message.
144   std::string getLocation(uintX_t Offset);
145 
146   void relocate(uint8_t *Buf, uint8_t *BufEnd);
147 };
148 
149 // SectionPiece represents a piece of splittable section contents.
150 // We allocate a lot of these and binary search on them. This means that they
151 // have to be as compact as possible, which is why we don't store the size (can
152 // be found by looking at the next one) and put the hash in a side table.
153 struct SectionPiece {
154   SectionPiece(size_t Off, bool Live = false)
155       : InputOff(Off), OutputOff(-1), Live(Live || !Config->GcSections) {}
156 
157   size_t InputOff;
158   ssize_t OutputOff : 8 * sizeof(ssize_t) - 1;
159   size_t Live : 1;
160 };
161 static_assert(sizeof(SectionPiece) == 2 * sizeof(size_t),
162               "SectionPiece is too big");
163 
164 // This corresponds to a SHF_MERGE section of an input file.
165 template <class ELFT> class MergeInputSection : public InputSectionBase<ELFT> {
166   typedef typename ELFT::uint uintX_t;
167   typedef typename ELFT::Sym Elf_Sym;
168   typedef typename ELFT::Shdr Elf_Shdr;
169 
170 public:
171   MergeInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header,
172                     StringRef Name);
173   static bool classof(const InputSectionData *S);
174   void splitIntoPieces();
175 
176   // Mark the piece at a given offset live. Used by GC.
177   void markLiveAt(uintX_t Offset) {
178     assert(this->Flags & llvm::ELF::SHF_ALLOC);
179     LiveOffsets.insert(Offset);
180   }
181 
182   // Translate an offset in the input section to an offset
183   // in the output section.
184   uintX_t getOffset(uintX_t Offset) const;
185 
186   // Splittable sections are handled as a sequence of data
187   // rather than a single large blob of data.
188   std::vector<SectionPiece> Pieces;
189 
190   // Returns I'th piece's data. This function is very hot when
191   // string merging is enabled, so we want to inline.
192   LLVM_ATTRIBUTE_ALWAYS_INLINE
193   llvm::CachedHashStringRef getData(size_t I) const {
194     size_t Begin = Pieces[I].InputOff;
195     size_t End;
196     if (Pieces.size() - 1 == I)
197       End = this->Data.size();
198     else
199       End = Pieces[I + 1].InputOff;
200 
201     StringRef S = {(const char *)(this->Data.data() + Begin), End - Begin};
202     return {S, Hashes[I]};
203   }
204 
205   // Returns the SectionPiece at a given input section offset.
206   SectionPiece *getSectionPiece(uintX_t Offset);
207   const SectionPiece *getSectionPiece(uintX_t Offset) const;
208 
209 private:
210   void splitStrings(ArrayRef<uint8_t> A, size_t Size);
211   void splitNonStrings(ArrayRef<uint8_t> A, size_t Size);
212 
213   std::vector<uint32_t> Hashes;
214 
215   mutable llvm::DenseMap<uintX_t, uintX_t> OffsetMap;
216   mutable std::once_flag InitOffsetMap;
217 
218   llvm::DenseSet<uintX_t> LiveOffsets;
219 };
220 
221 struct EhSectionPiece : public SectionPiece {
222   EhSectionPiece(size_t Off, InputSectionData *ID, uint32_t Size,
223                  unsigned FirstRelocation)
224       : SectionPiece(Off, false), ID(ID), Size(Size),
225         FirstRelocation(FirstRelocation) {}
226   InputSectionData *ID;
227   uint32_t Size;
228   uint32_t size() const { return Size; }
229 
230   ArrayRef<uint8_t> data() { return {ID->Data.data() + this->InputOff, Size}; }
231   unsigned FirstRelocation;
232 };
233 
234 // This corresponds to a .eh_frame section of an input file.
235 template <class ELFT> class EhInputSection : public InputSectionBase<ELFT> {
236 public:
237   typedef typename ELFT::Shdr Elf_Shdr;
238   typedef typename ELFT::uint uintX_t;
239   EhInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header, StringRef Name);
240   static bool classof(const InputSectionData *S);
241   void split();
242   template <class RelTy> void split(ArrayRef<RelTy> Rels);
243 
244   // Splittable sections are handled as a sequence of data
245   // rather than a single large blob of data.
246   std::vector<EhSectionPiece> Pieces;
247 };
248 
249 // This corresponds to a non SHF_MERGE section of an input file.
250 template <class ELFT> class InputSection : public InputSectionBase<ELFT> {
251   typedef InputSectionBase<ELFT> Base;
252   typedef typename ELFT::Shdr Elf_Shdr;
253   typedef typename ELFT::Rela Elf_Rela;
254   typedef typename ELFT::Rel Elf_Rel;
255   typedef typename ELFT::Sym Elf_Sym;
256   typedef typename ELFT::uint uintX_t;
257   typedef InputSectionData::Kind Kind;
258 
259 public:
260   InputSection();
261   InputSection(uintX_t Flags, uint32_t Type, uintX_t Addralign,
262                ArrayRef<uint8_t> Data, StringRef Name,
263                Kind K = InputSectionData::Regular);
264   InputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header, StringRef Name);
265 
266   static InputSection<ELFT> Discarded;
267 
268   // Write this section to a mmap'ed file, assuming Buf is pointing to
269   // beginning of the output section.
270   void writeTo(uint8_t *Buf);
271 
272   // The offset from beginning of the output sections this section was assigned
273   // to. The writer sets a value.
274   uint64_t OutSecOff = 0;
275 
276   // InputSection that is dependent on us (reverse dependency for GC)
277   InputSectionBase<ELFT> *DependentSection = nullptr;
278 
279   static bool classof(const InputSectionData *S);
280 
281   InputSectionBase<ELFT> *getRelocatedSection();
282 
283   // Register thunk related to the symbol. When the section is written
284   // to a mmap'ed file, target is requested to write an actual thunk code.
285   // Now thunks is supported for MIPS and ARM target only.
286   void addThunk(const Thunk<ELFT> *T);
287 
288   // The offset of synthetic thunk code from beginning of this section.
289   uint64_t getThunkOff() const;
290 
291   // Size of chunk with thunks code.
292   uint64_t getThunksSize() const;
293 
294   template <class RelTy>
295   void relocateNonAlloc(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
296 
297   // Used by ICF.
298   uint32_t Class[2] = {0, 0};
299 
300   // Called by ICF to merge two input sections.
301   void replace(InputSection<ELFT> *Other);
302 
303 private:
304   template <class RelTy>
305   void copyRelocations(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
306 
307   llvm::TinyPtrVector<const Thunk<ELFT> *> Thunks;
308 };
309 
310 template <class ELFT> InputSection<ELFT> InputSection<ELFT>::Discarded;
311 } // namespace elf
312 
313 template <class ELFT> std::string toString(const elf::InputSectionBase<ELFT> *);
314 } // namespace lld
315 
316 #endif
317