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