1//===- GNULDBackend.h -----------------------------------------------------===//
2//
3//                     The MCLinker Project
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9#ifndef MCLD_TARGET_GNU_LDBACKEND_H
10#define MCLD_TARGET_GNU_LDBACKEND_H
11#ifdef ENABLE_UNITTEST
12#include <gtest.h>
13#endif
14#include <mcld/Target/TargetLDBackend.h>
15
16#include <llvm/Support/ELF.h>
17#include <mcld/ADT/HashTable.h>
18#include <mcld/ADT/HashEntry.h>
19#include <mcld/LD/ELFDynObjFileFormat.h>
20#include <mcld/LD/ELFExecFileFormat.h>
21#include <mcld/LD/ELFObjectFileFormat.h>
22#include <mcld/LD/GNUArchiveReader.h>
23#include <mcld/LD/ELFObjectReader.h>
24#include <mcld/LD/ELFDynObjReader.h>
25#include <mcld/LD/ELFBinaryReader.h>
26#include <mcld/LD/ELFObjectWriter.h>
27#include <mcld/LD/ELFSegment.h>
28#include <mcld/LD/ELFSegmentFactory.h>
29#include <mcld/Target/ELFDynamic.h>
30#include <mcld/Target/GNUInfo.h>
31
32#include <mcld/Support/GCFactory.h>
33#include <mcld/Module.h>
34
35namespace mcld {
36
37class Module;
38class LinkerConfig;
39class IRBuilder;
40class Layout;
41class EhFrameHdr;
42class BranchIslandFactory;
43class StubFactory;
44class GNUInfo;
45
46/** \class GNULDBackend
47 *  \brief GNULDBackend provides a common interface for all GNU Unix-OS
48 *  LDBackend.
49 */
50class GNULDBackend : public TargetLDBackend
51{
52protected:
53  GNULDBackend(const LinkerConfig& pConfig, GNUInfo* pInfo);
54
55public:
56  virtual ~GNULDBackend();
57
58  // -----  readers/writers  ----- //
59  GNUArchiveReader* createArchiveReader(Module& pModule);
60  ELFObjectReader* createObjectReader(IRBuilder& pBuilder);
61  ELFDynObjReader* createDynObjReader(IRBuilder& pBuilder);
62  ELFBinaryReader* createBinaryReader(IRBuilder& pBuilder);
63  ELFObjectWriter* createWriter();
64
65  // -----  output sections  ----- //
66  /// initStdSections - initialize standard sections of the output file.
67  bool initStdSections(ObjectBuilder& pBuilder);
68
69  /// getOutputFormat - get the sections of the output file.
70  const ELFFileFormat* getOutputFormat() const;
71  ELFFileFormat*       getOutputFormat();
72
73  // -----  target symbols ----- //
74  /// initStandardSymbols - initialize standard symbols.
75  /// Some section symbols is undefined in input object, and linkers must set
76  /// up its value. Take __init_array_begin for example. This symbol is an
77  /// undefined symbol in input objects. ObjectLinker must finalize its value
78  /// to the begin of the .init_array section, then relocation enties to
79  /// __init_array_begin can be applied without emission of "undefined
80  /// reference to `__init_array_begin'".
81  bool initStandardSymbols(IRBuilder& pBuilder, Module& pModule);
82
83  /// finalizeSymbol - Linker checks pSymbol.reserved() if it's not zero,
84  /// then it will ask backend to finalize the symbol value.
85  /// @return ture - if backend set the symbol value sucessfully
86  /// @return false - if backend do not recognize the symbol
87  bool finalizeSymbols() {
88    return (finalizeStandardSymbols() &&
89            finalizeTargetSymbols());
90  }
91
92  /// finalizeStandardSymbols - set the value of standard symbols
93  virtual bool finalizeStandardSymbols();
94
95  /// finalizeTargetSymbols - set the value of target symbols
96  virtual bool finalizeTargetSymbols() = 0;
97
98  /// finalizeTLSSymbol - set the value of a TLS symbol
99  virtual bool finalizeTLSSymbol(LDSymbol& pSymbol);
100
101  size_t sectionStartOffset() const;
102
103  const GNUInfo& getInfo() const { return *m_pInfo; }
104  GNUInfo&       getInfo()       { return *m_pInfo; }
105
106  bool hasTextRel() const { return m_bHasTextRel; }
107
108  bool hasStaticTLS() const { return m_bHasStaticTLS; }
109
110  /// getSegmentStartAddr - this function returns the start address of the segment
111  uint64_t getSegmentStartAddr(const LinkerScript& pScript) const;
112
113  /// sizeNamePools - compute the size of regular name pools
114  /// In ELF executable files, regular name pools are .symtab, .strtab.,
115  /// .dynsym, .dynstr, and .hash
116  virtual void sizeNamePools(Module& pModule);
117
118  /// emitSectionData - emit target-dependent section data
119  virtual uint64_t emitSectionData(const LDSection& pSection,
120                                   MemoryRegion& pRegion) const = 0;
121
122  /// emitRegNamePools - emit regular name pools - .symtab, .strtab
123  virtual void emitRegNamePools(const Module& pModule, MemoryArea& pOutput);
124
125  /// emitNamePools - emit dynamic name pools - .dyntab, .dynstr, .hash
126  virtual void emitDynNamePools(Module& pModule, MemoryArea& pOutput);
127
128  /// emitELFHashTab - emit .hash
129  virtual void emitELFHashTab(const Module::SymbolTable& pSymtab,
130                              MemoryArea& pOutput);
131
132  /// emitGNUHashTab - emit .gnu.hash
133  virtual void emitGNUHashTab(Module::SymbolTable& pSymtab,
134                              MemoryArea& pOutput);
135
136  /// sizeInterp - compute the size of program interpreter's name
137  /// In ELF executables, this is the length of dynamic linker's path name
138  virtual void sizeInterp();
139
140  /// emitInterp - emit the .interp
141  virtual void emitInterp(MemoryArea& pOutput);
142
143  /// hasEntryInStrTab - symbol has an entry in a .strtab
144  virtual bool hasEntryInStrTab(const LDSymbol& pSym) const;
145
146  /// orderSymbolTable - order symbol table before emitting
147  virtual void orderSymbolTable(Module& pModule);
148
149  void setHasStaticTLS(bool pVal = true)
150  { m_bHasStaticTLS = pVal; }
151
152  /// getSectionOrder - compute the layout order of the section
153  /// Layout calls this function to get the default order of the pSectHdr.
154  /// If the pSectHdr.type() is LDFileFormat::Target, then getSectionOrder()
155  /// will call getTargetSectionOrder().
156  ///
157  /// If targets favors certain order for general sections, please override
158  /// this function.
159  ///
160  /// @see getTargetSectionOrder
161  virtual unsigned int getSectionOrder(const LDSection& pSectHdr) const;
162
163  /// getTargetSectionOrder - compute the layout order of target section
164  /// If the target favors certain order for the given gSectHdr, please
165  /// override this function.
166  ///
167  /// By default, this function returns the maximun order, and pSectHdr
168  /// will be the last section to be laid out.
169  virtual unsigned int getTargetSectionOrder(const LDSection& pSectHdr) const
170  { return (unsigned int)-1; }
171
172  /// numOfSegments - return the number of segments
173  /// if the target favors other ways to emit program header, please override
174  /// this function
175  size_t numOfSegments() const { return m_ELFSegmentTable.size(); }
176
177  /// elfSegmentTable - return the reference of the elf segment table
178  ELFSegmentFactory&       elfSegmentTable()       { return m_ELFSegmentTable; }
179
180  /// elfSegmentTable - return the reference of the elf segment table
181  const ELFSegmentFactory& elfSegmentTable() const { return m_ELFSegmentTable; }
182
183  /// commonPageSize - the common page size of the target machine
184  uint64_t commonPageSize() const;
185
186  /// abiPageSize - the abi page size of the target machine
187  uint64_t abiPageSize() const;
188
189  /// getSymbolIdx - get the symbol index of ouput symbol table
190  size_t getSymbolIdx(const LDSymbol* pSymbol) const;
191
192  /// allocateCommonSymbols - allocate common symbols in the corresponding
193  /// sections.
194  /// Different concrete target backend may overlap this function.
195  virtual bool allocateCommonSymbols(Module& pModule);
196
197  /// updateSectionFlags - update pTo's flags when merging pFrom
198  /// update the output section flags based on input section flags.
199  virtual bool updateSectionFlags(LDSection& pTo, const LDSection& pFrom);
200
201  /// symbolNeedsPLT - return whether the symbol needs a PLT entry
202  /// @ref Google gold linker, symtab.h:596
203  bool symbolNeedsPLT(const ResolveInfo& pSym) const;
204
205  /// symbolNeedsCopyReloc - return whether the symbol needs a copy relocation
206  bool symbolNeedsCopyReloc(const Relocation& pReloc,
207                            const ResolveInfo& pSym) const;
208
209  /// symbolNeedsDynRel - return whether the symbol needs a dynamic relocation
210  /// @ref Google gold linker, symtab.h:645
211  bool symbolNeedsDynRel(const ResolveInfo& pSym,
212                         bool pSymHasPLT,
213                         bool isAbsReloc) const;
214
215  /// isSymbolPreemtible - whether the symbol can be preemted by other
216  /// link unit
217  /// @ref Google gold linker, symtab.h:551
218  bool isSymbolPreemptible(const ResolveInfo& pSym) const;
219
220  /// symbolHasFinalValue - return true if the symbol's value can be decided at
221  /// link time
222  bool symbolFinalValueIsKnown(const ResolveInfo& pSym) const;
223
224  /// isDynamicSymbol
225  /// @ref Google gold linker: symtab.cc:311
226  bool isDynamicSymbol(const LDSymbol& pSymbol);
227
228  /// isDynamicSymbol
229  /// @ref Google gold linker: symtab.cc:311
230  bool isDynamicSymbol(const ResolveInfo& pResolveInfo);
231
232  virtual ResolveInfo::Desc getSymDesc(uint16_t pShndx) const {
233    return ResolveInfo::Define;
234  }
235
236  bool hasTDATASymbol() const { return (NULL != f_pTDATA); }
237  bool hasTBSSSymbol()  const { return (NULL != f_pTBSS);  }
238
239  void setTDATASymbol(LDSymbol& pTDATA) { f_pTDATA = &pTDATA; }
240  void setTBSSSymbol(LDSymbol& pTBSS)   { f_pTBSS  = &pTBSS;  }
241
242  // getTDATASymbol - get section symbol of .tdata
243  LDSymbol& getTDATASymbol();
244  const LDSymbol& getTDATASymbol() const;
245
246  /// getTBSSSymbol - get section symbol of .tbss
247  LDSymbol& getTBSSSymbol();
248  const LDSymbol& getTBSSSymbol() const;
249
250  //  -----  relaxation  -----  //
251  /// initBRIslandFactory - initialize the branch island factory for relaxation
252  bool initBRIslandFactory();
253
254  /// initStubFactory - initialize the stub factory for relaxation
255  bool initStubFactory();
256
257  /// getBRIslandFactory
258  BranchIslandFactory* getBRIslandFactory() { return m_pBRIslandFactory; }
259
260  /// getStubFactory
261  StubFactory*         getStubFactory()     { return m_pStubFactory; }
262
263  /// maxBranchOffset - return the max (forward) branch offset of the backend.
264  /// Target can override this function if needed.
265  virtual uint64_t maxBranchOffset() { return (uint64_t)-1; }
266
267  /// checkAndSetHasTextRel - check pSection flag to set HasTextRel
268  void checkAndSetHasTextRel(const LDSection& pSection);
269
270protected:
271  uint64_t getSymbolSize(const LDSymbol& pSymbol) const;
272
273  uint64_t getSymbolInfo(const LDSymbol& pSymbol) const;
274
275  uint64_t getSymbolValue(const LDSymbol& pSymbol) const;
276
277  uint64_t getSymbolShndx(const LDSymbol& pSymbol) const;
278
279  /// isTemporary - Whether pSymbol is a local label.
280  virtual bool isTemporary(const LDSymbol& pSymbol) const;
281
282  /// getHashBucketCount - calculate hash bucket count.
283  /// @ref Google gold linker, dynobj.cc:791
284  static unsigned getHashBucketCount(unsigned pNumOfSymbols, bool pIsGNUStyle);
285
286  /// getGNUHashMaskbitslog2 - calculate the number of mask bits in log2
287  /// @ref binutils gold, dynobj.cc:1165
288  unsigned getGNUHashMaskbitslog2(unsigned pNumOfSymbols) const;
289
290  /// emitSymbol32 - emit an ELF32 symbol
291  void emitSymbol32(llvm::ELF::Elf32_Sym& pSym32,
292                    LDSymbol& pSymbol,
293                    char* pStrtab,
294                    size_t pStrtabsize,
295                    size_t pSymtabIdx);
296
297  /// emitSymbol64 - emit an ELF64 symbol
298  void emitSymbol64(llvm::ELF::Elf64_Sym& pSym64,
299                    LDSymbol& pSymbol,
300                    char* pStrtab,
301                    size_t pStrtabsize,
302                    size_t pSymtabIdx);
303
304private:
305  /// createProgramHdrs - base on output sections to create the program headers
306  void createProgramHdrs(Module& pModule);
307
308  /// doCreateProgramHdrs - backend can implement this function to create the
309  /// target-dependent segments
310  virtual void doCreateProgramHdrs(Module& pModule) = 0;
311
312  /// setupProgramHdrs - set up the attributes of segments
313  ///  (i.e., offset, addresses, file/mem size, flag,  and alignment)
314  void setupProgramHdrs(const LinkerScript& pScript);
315
316  /// getSegmentFlag - give a section flag and return the corresponding segment
317  /// flag
318  inline uint32_t getSegmentFlag(const uint32_t pSectionFlag)
319  {
320    uint32_t flag = llvm::ELF::PF_R;
321    if (0 != (pSectionFlag & llvm::ELF::SHF_WRITE))
322      flag |= llvm::ELF::PF_W;
323    if (0 != (pSectionFlag & llvm::ELF::SHF_EXECINSTR))
324      flag |= llvm::ELF::PF_X;
325    return flag;
326  }
327
328  /// setupGNUStackInfo - setup the section flag of .note.GNU-stack in output
329  void setupGNUStackInfo(Module& pModule);
330
331  /// setupRelro - setup the offset constraint of PT_RELRO
332  void setupRelro(Module& pModule);
333
334  /// setOutputSectionOffset - helper function to set a group of output sections'
335  /// offset, and set pSectBegin to pStartOffset if pStartOffset is not -1U.
336  void setOutputSectionOffset(Module& pModule,
337                              Module::iterator pSectBegin,
338                              Module::iterator pSectEnd,
339                              uint64_t pStartOffset = -1U);
340
341  /// setOutputSectionOffset - helper function to set output sections' address.
342  void setOutputSectionAddress(Module& pModule,
343                               Module::iterator pSectBegin,
344                               Module::iterator pSectEnd);
345
346  /// layout - layout method
347  void layout(Module& pModule);
348
349  /// preLayout - Backend can do any needed modification before layout
350  void preLayout(Module& pModule, IRBuilder& pBuilder);
351
352  /// postLayout -Backend can do any needed modification after layout
353  void postLayout(Module& pModule, IRBuilder& pBuilder);
354
355  /// preLayout - Backend can do any needed modification before layout
356  virtual void doPreLayout(IRBuilder& pBuilder) = 0;
357
358  /// postLayout -Backend can do any needed modification after layout
359  virtual void doPostLayout(Module& pModule, IRBuilder& pLinker) = 0;
360
361  /// postProcessing - Backend can do any needed modification in the final stage
362  void postProcessing(MemoryArea& pOutput);
363
364  /// dynamic - the dynamic section of the target machine.
365  virtual ELFDynamic& dynamic() = 0;
366
367  /// dynamic - the dynamic section of the target machine.
368  virtual const ELFDynamic& dynamic() const = 0;
369
370  /// relax - the relaxation pass
371  bool relax(Module& pModule, IRBuilder& pBuilder);
372
373  /// mayRelax - Backends should override this function if they need relaxation
374  virtual bool mayRelax() { return false; }
375
376  /// doRelax - Backend can orevride this function to add its relaxation
377  /// implementation. Return true if the output (e.g., .text) is "relaxed"
378  /// (i.e. layout is changed), and set pFinished to true if everything is fit,
379  /// otherwise set it to false.
380  virtual bool doRelax(Module& pModule, IRBuilder& pBuilder, bool& pFinished)
381  { return false; }
382
383  /// getRelEntrySize - the size in BYTE of rel type relocation
384  virtual size_t getRelEntrySize() = 0;
385
386  /// getRelEntrySize - the size in BYTE of rela type relocation
387  virtual size_t getRelaEntrySize() = 0;
388
389protected:
390  // Based on Kind in LDFileFormat to define basic section orders for ELF, and
391  // refer gold linker to add more enumerations to handle Regular and BSS kind
392  enum SectionOrder {
393    SHO_INTERP = 1,          // .interp
394    SHO_RO_NOTE,             // .note.ABI-tag, .note.gnu.build-id
395    SHO_NAMEPOOL,            // *.hash, .dynsym, .dynstr
396    SHO_RELOCATION,          // .rel.*, .rela.*
397    SHO_REL_PLT,             // .rel.plt should come after other .rel.*
398    SHO_INIT,                // .init
399    SHO_PLT,                 // .plt
400    SHO_TEXT,                // .text
401    SHO_FINI,                // .fini
402    SHO_RO,                  // .rodata
403    SHO_EXCEPTION,           // .eh_frame_hdr, .eh_frame, .gcc_except_table
404    SHO_TLS_DATA,            // .tdata
405    SHO_TLS_BSS,             // .tbss
406    SHO_RELRO_LOCAL,         // .data.rel.ro.local
407    SHO_RELRO,               // .data.rel.ro,
408    SHO_RELRO_LAST,          // for x86 to adjust .got if needed
409    SHO_NON_RELRO_FIRST,     // for x86 to adjust .got.plt if needed
410    SHO_DATA,                // .data
411    SHO_LARGE_DATA,          // .ldata
412    SHO_RW_NOTE,             //
413    SHO_SMALL_DATA,          // .sdata
414    SHO_SMALL_BSS,           // .sbss
415    SHO_BSS,                 // .bss
416    SHO_LARGE_BSS,           // .lbss
417    SHO_UNDEFINED,           // default order
418    SHO_STRTAB               // .strtab
419  };
420
421  typedef std::pair<LDSection*, unsigned int> SHOEntry;
422
423  struct SHOCompare
424  {
425    bool operator()(const SHOEntry& X, const SHOEntry& Y) const
426    { return X.second < Y.second; }
427  };
428
429  struct SymCompare
430  {
431    bool operator()(const LDSymbol* X, const LDSymbol* Y) const
432    { return (X==Y); }
433  };
434
435  // for gnu style hash table
436  struct DynsymCompare
437  {
438    bool needGNUHash(const LDSymbol& X) const;
439
440    bool operator()(const LDSymbol* X, const LDSymbol* Y) const;
441  };
442
443  struct SymPtrHash
444  {
445    size_t operator()(const LDSymbol* pKey) const
446    {
447      return (unsigned((uintptr_t)pKey) >> 4) ^
448             (unsigned((uintptr_t)pKey) >> 9);
449    }
450  };
451
452  typedef HashEntry<LDSymbol*, size_t, SymCompare> SymHashEntryType;
453  typedef HashTable<SymHashEntryType,
454                    SymPtrHash,
455                    EntryFactory<SymHashEntryType> > HashTableType;
456
457
458protected:
459  ELFObjectReader* m_pObjectReader;
460
461  // -----  file formats  ----- //
462  ELFDynObjFileFormat* m_pDynObjFileFormat;
463  ELFExecFileFormat*   m_pExecFileFormat;
464  ELFObjectFileFormat* m_pObjectFileFormat;
465
466  // GNUInfo
467  GNUInfo* m_pInfo;
468
469  // ELF segment factory
470  ELFSegmentFactory m_ELFSegmentTable;
471
472  // branch island factory
473  BranchIslandFactory* m_pBRIslandFactory;
474
475  // stub factory
476  StubFactory* m_pStubFactory;
477
478  // map the LDSymbol to its index in the output symbol table
479  HashTableType* m_pSymIndexMap;
480
481  // section .eh_frame_hdr
482  EhFrameHdr* m_pEhFrameHdr;
483
484  // ----- dynamic flags ----- //
485  // DF_TEXTREL of DT_FLAGS
486  bool m_bHasTextRel;
487
488  // DF_STATIC_TLS of DT_FLAGS
489  bool m_bHasStaticTLS;
490
491  // -----  standard symbols  ----- //
492  // section symbols
493  LDSymbol* f_pPreInitArrayStart;
494  LDSymbol* f_pPreInitArrayEnd;
495  LDSymbol* f_pInitArrayStart;
496  LDSymbol* f_pInitArrayEnd;
497  LDSymbol* f_pFiniArrayStart;
498  LDSymbol* f_pFiniArrayEnd;
499  LDSymbol* f_pStack;
500  LDSymbol* f_pDynamic;
501
502  // section symbols for .tdata and .tbss
503  LDSymbol* f_pTDATA;
504  LDSymbol* f_pTBSS;
505
506  // segment symbols
507  LDSymbol* f_pExecutableStart;
508  LDSymbol* f_pEText;
509  LDSymbol* f_p_EText;
510  LDSymbol* f_p__EText;
511  LDSymbol* f_pEData;
512  LDSymbol* f_p_EData;
513  LDSymbol* f_pBSSStart;
514  LDSymbol* f_pEnd;
515  LDSymbol* f_p_End;
516};
517
518} // namespace of mcld
519
520#endif
521
522