1//===- lib/MC/ELFObjectWriter.cpp - ELF File Writer -----------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements ELF object file writer information.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/MC/MCELFObjectWriter.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/ADT/SmallString.h"
18#include "llvm/ADT/StringMap.h"
19#include "llvm/MC/MCAsmBackend.h"
20#include "llvm/MC/MCAsmInfo.h"
21#include "llvm/MC/MCAsmLayout.h"
22#include "llvm/MC/MCAssembler.h"
23#include "llvm/MC/MCContext.h"
24#include "llvm/MC/MCELF.h"
25#include "llvm/MC/MCELFSymbolFlags.h"
26#include "llvm/MC/MCExpr.h"
27#include "llvm/MC/MCFixupKindInfo.h"
28#include "llvm/MC/MCObjectWriter.h"
29#include "llvm/MC/MCSectionELF.h"
30#include "llvm/MC/MCValue.h"
31#include "llvm/MC/StringTableBuilder.h"
32#include "llvm/Support/Compression.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/ELF.h"
35#include "llvm/Support/Endian.h"
36#include "llvm/Support/ErrorHandling.h"
37#include <vector>
38using namespace llvm;
39
40#undef  DEBUG_TYPE
41#define DEBUG_TYPE "reloc-info"
42
43namespace {
44class FragmentWriter {
45  bool IsLittleEndian;
46
47public:
48  FragmentWriter(bool IsLittleEndian);
49  template <typename T> void write(MCDataFragment &F, T Val);
50};
51
52typedef DenseMap<const MCSectionELF *, uint32_t> SectionIndexMapTy;
53
54class SymbolTableWriter {
55  MCAssembler &Asm;
56  FragmentWriter &FWriter;
57  bool Is64Bit;
58  SectionIndexMapTy &SectionIndexMap;
59
60  // The symbol .symtab fragment we are writting to.
61  MCDataFragment *SymtabF;
62
63  // .symtab_shndx fragment we are writting to.
64  MCDataFragment *ShndxF;
65
66  // The numbel of symbols written so far.
67  unsigned NumWritten;
68
69  void createSymtabShndx();
70
71  template <typename T> void write(MCDataFragment &F, T Value);
72
73public:
74  SymbolTableWriter(MCAssembler &Asm, FragmentWriter &FWriter, bool Is64Bit,
75                    SectionIndexMapTy &SectionIndexMap,
76                    MCDataFragment *SymtabF);
77
78  void writeSymbol(uint32_t name, uint8_t info, uint64_t value, uint64_t size,
79                   uint8_t other, uint32_t shndx, bool Reserved);
80};
81
82class ELFObjectWriter : public MCObjectWriter {
83  FragmentWriter FWriter;
84
85  protected:
86
87    static bool isFixupKindPCRel(const MCAssembler &Asm, unsigned Kind);
88    static bool RelocNeedsGOT(MCSymbolRefExpr::VariantKind Variant);
89    static uint64_t SymbolValue(MCSymbolData &Data, const MCAsmLayout &Layout);
90    static bool isInSymtab(const MCAsmLayout &Layout, const MCSymbolData &Data,
91                           bool Used, bool Renamed);
92    static bool isLocal(const MCSymbolData &Data, bool isUsedInReloc);
93    static bool IsELFMetaDataSection(const MCSectionData &SD);
94    static uint64_t DataSectionSize(const MCSectionData &SD);
95    static uint64_t GetSectionAddressSize(const MCAsmLayout &Layout,
96                                          const MCSectionData &SD);
97
98    void writeDataSectionData(MCAssembler &Asm, const MCAsmLayout &Layout,
99                              const MCSectionData &SD);
100
101    /// Helper struct for containing some precomputed information on symbols.
102    struct ELFSymbolData {
103      MCSymbolData *SymbolData;
104      uint64_t StringIndex;
105      uint32_t SectionIndex;
106      StringRef Name;
107
108      // Support lexicographic sorting.
109      bool operator<(const ELFSymbolData &RHS) const {
110        unsigned LHSType = MCELF::GetType(*SymbolData);
111        unsigned RHSType = MCELF::GetType(*RHS.SymbolData);
112        if (LHSType == ELF::STT_SECTION && RHSType != ELF::STT_SECTION)
113          return false;
114        if (LHSType != ELF::STT_SECTION && RHSType == ELF::STT_SECTION)
115          return true;
116        if (LHSType == ELF::STT_SECTION && RHSType == ELF::STT_SECTION)
117          return SectionIndex < RHS.SectionIndex;
118        return Name < RHS.Name;
119      }
120    };
121
122    /// The target specific ELF writer instance.
123    std::unique_ptr<MCELFObjectTargetWriter> TargetObjectWriter;
124
125    SmallPtrSet<const MCSymbol *, 16> UsedInReloc;
126    SmallPtrSet<const MCSymbol *, 16> WeakrefUsedInReloc;
127    DenseMap<const MCSymbol *, const MCSymbol *> Renames;
128
129    llvm::DenseMap<const MCSectionData *, std::vector<ELFRelocationEntry>>
130    Relocations;
131    StringTableBuilder ShStrTabBuilder;
132
133    /// @}
134    /// @name Symbol Table Data
135    /// @{
136
137    StringTableBuilder StrTabBuilder;
138    std::vector<uint64_t> FileSymbolData;
139    std::vector<ELFSymbolData> LocalSymbolData;
140    std::vector<ELFSymbolData> ExternalSymbolData;
141    std::vector<ELFSymbolData> UndefinedSymbolData;
142
143    /// @}
144
145    bool NeedsGOT;
146
147    // This holds the symbol table index of the last local symbol.
148    unsigned LastLocalSymbolIndex;
149    // This holds the .strtab section index.
150    unsigned StringTableIndex;
151    // This holds the .symtab section index.
152    unsigned SymbolTableIndex;
153
154    unsigned ShstrtabIndex;
155
156
157    // TargetObjectWriter wrappers.
158    bool is64Bit() const { return TargetObjectWriter->is64Bit(); }
159    bool hasRelocationAddend() const {
160      return TargetObjectWriter->hasRelocationAddend();
161    }
162    unsigned GetRelocType(const MCValue &Target, const MCFixup &Fixup,
163                          bool IsPCRel) const {
164      return TargetObjectWriter->GetRelocType(Target, Fixup, IsPCRel);
165    }
166
167  public:
168    ELFObjectWriter(MCELFObjectTargetWriter *MOTW, raw_pwrite_stream &OS,
169                    bool IsLittleEndian)
170        : MCObjectWriter(OS, IsLittleEndian), FWriter(IsLittleEndian),
171          TargetObjectWriter(MOTW), NeedsGOT(false) {}
172
173    void reset() override {
174      UsedInReloc.clear();
175      WeakrefUsedInReloc.clear();
176      Renames.clear();
177      Relocations.clear();
178      ShStrTabBuilder.clear();
179      StrTabBuilder.clear();
180      FileSymbolData.clear();
181      LocalSymbolData.clear();
182      ExternalSymbolData.clear();
183      UndefinedSymbolData.clear();
184      MCObjectWriter::reset();
185    }
186
187    ~ELFObjectWriter() override;
188
189    void WriteWord(uint64_t W) {
190      if (is64Bit())
191        Write64(W);
192      else
193        Write32(W);
194    }
195
196    template <typename T> void write(MCDataFragment &F, T Value) {
197      FWriter.write(F, Value);
198    }
199
200    void WriteHeader(const MCAssembler &Asm,
201                     unsigned NumberOfSections);
202
203    void WriteSymbol(SymbolTableWriter &Writer, ELFSymbolData &MSD,
204                     const MCAsmLayout &Layout);
205
206    void WriteSymbolTable(MCDataFragment *SymtabF, MCAssembler &Asm,
207                          const MCAsmLayout &Layout,
208                          SectionIndexMapTy &SectionIndexMap);
209
210    bool shouldRelocateWithSymbol(const MCAssembler &Asm,
211                                  const MCSymbolRefExpr *RefA,
212                                  const MCSymbolData *SD, uint64_t C,
213                                  unsigned Type) const;
214
215    void RecordRelocation(MCAssembler &Asm, const MCAsmLayout &Layout,
216                          const MCFragment *Fragment, const MCFixup &Fixup,
217                          MCValue Target, bool &IsPCRel,
218                          uint64_t &FixedValue) override;
219
220    uint64_t getSymbolIndexInSymbolTable(const MCAssembler &Asm,
221                                         const MCSymbol *S);
222
223    // Map from a group section to the signature symbol
224    typedef DenseMap<const MCSectionELF*, const MCSymbol*> GroupMapTy;
225    // Map from a signature symbol to the group section
226    typedef DenseMap<const MCSymbol*, const MCSectionELF*> RevGroupMapTy;
227    // Map from a section to its offset
228    typedef DenseMap<const MCSectionELF*, uint64_t> SectionOffsetMapTy;
229
230    /// Compute the symbol table data
231    ///
232    /// \param Asm - The assembler.
233    /// \param SectionIndexMap - Maps a section to its index.
234    /// \param RevGroupMap - Maps a signature symbol to the group section.
235    void computeSymbolTable(MCAssembler &Asm, const MCAsmLayout &Layout,
236                            const SectionIndexMapTy &SectionIndexMap,
237                            const RevGroupMapTy &RevGroupMap);
238
239    void computeIndexMap(MCAssembler &Asm, SectionIndexMapTy &SectionIndexMap);
240
241    MCSectionData *createRelocationSection(MCAssembler &Asm,
242                                           const MCSectionData &SD);
243
244    void CompressDebugSections(MCAssembler &Asm, MCAsmLayout &Layout);
245
246    void WriteRelocations(MCAssembler &Asm, MCAsmLayout &Layout);
247
248    void CreateMetadataSections(MCAssembler &Asm, MCAsmLayout &Layout,
249                                SectionIndexMapTy &SectionIndexMap);
250
251    // Create the sections that show up in the symbol table. Currently
252    // those are the .note.GNU-stack section and the group sections.
253    void createIndexedSections(MCAssembler &Asm, MCAsmLayout &Layout,
254                               GroupMapTy &GroupMap, RevGroupMapTy &RevGroupMap,
255                               SectionIndexMapTy &SectionIndexMap);
256
257    void ExecutePostLayoutBinding(MCAssembler &Asm,
258                                  const MCAsmLayout &Layout) override;
259
260    void writeSectionHeader(ArrayRef<const MCSectionELF *> Sections,
261                            MCAssembler &Asm, const GroupMapTy &GroupMap,
262                            const MCAsmLayout &Layout,
263                            const SectionIndexMapTy &SectionIndexMap,
264                            const SectionOffsetMapTy &SectionOffsetMap);
265
266    void WriteSecHdrEntry(uint32_t Name, uint32_t Type, uint64_t Flags,
267                          uint64_t Address, uint64_t Offset,
268                          uint64_t Size, uint32_t Link, uint32_t Info,
269                          uint64_t Alignment, uint64_t EntrySize);
270
271    void WriteRelocationsFragment(const MCAssembler &Asm,
272                                  MCDataFragment *F,
273                                  const MCSectionData *SD);
274
275    bool
276    IsSymbolRefDifferenceFullyResolvedImpl(const MCAssembler &Asm,
277                                           const MCSymbolData &DataA,
278                                           const MCSymbolData *DataB,
279                                           const MCFragment &FB,
280                                           bool InSet,
281                                           bool IsPCRel) const override;
282
283    bool isWeak(const MCSymbolData &SD) const override;
284
285    void WriteObject(MCAssembler &Asm, const MCAsmLayout &Layout) override;
286    void writeSection(MCAssembler &Asm,
287                      const SectionIndexMapTy &SectionIndexMap,
288                      uint32_t GroupSymbolIndex,
289                      uint64_t Offset, uint64_t Size, uint64_t Alignment,
290                      const MCSectionELF &Section);
291  };
292}
293
294FragmentWriter::FragmentWriter(bool IsLittleEndian)
295    : IsLittleEndian(IsLittleEndian) {}
296
297template <typename T> void FragmentWriter::write(MCDataFragment &F, T Val) {
298  if (IsLittleEndian)
299    Val = support::endian::byte_swap<T, support::little>(Val);
300  else
301    Val = support::endian::byte_swap<T, support::big>(Val);
302  const char *Start = (const char *)&Val;
303  F.getContents().append(Start, Start + sizeof(T));
304}
305
306void SymbolTableWriter::createSymtabShndx() {
307  if (ShndxF)
308    return;
309
310  MCContext &Ctx = Asm.getContext();
311  const MCSectionELF *SymtabShndxSection =
312      Ctx.getELFSection(".symtab_shndxr", ELF::SHT_SYMTAB_SHNDX, 0, 4, "");
313  MCSectionData *SymtabShndxSD =
314      &Asm.getOrCreateSectionData(*SymtabShndxSection);
315  SymtabShndxSD->setAlignment(4);
316  ShndxF = new MCDataFragment(SymtabShndxSD);
317  unsigned Index = SectionIndexMap.size() + 1;
318  SectionIndexMap[SymtabShndxSection] = Index;
319
320  for (unsigned I = 0; I < NumWritten; ++I)
321    write(*ShndxF, uint32_t(0));
322}
323
324template <typename T>
325void SymbolTableWriter::write(MCDataFragment &F, T Value) {
326  FWriter.write(F, Value);
327}
328
329SymbolTableWriter::SymbolTableWriter(MCAssembler &Asm, FragmentWriter &FWriter,
330                                     bool Is64Bit,
331                                     SectionIndexMapTy &SectionIndexMap,
332                                     MCDataFragment *SymtabF)
333    : Asm(Asm), FWriter(FWriter), Is64Bit(Is64Bit),
334      SectionIndexMap(SectionIndexMap), SymtabF(SymtabF), ShndxF(nullptr),
335      NumWritten(0) {}
336
337void SymbolTableWriter::writeSymbol(uint32_t name, uint8_t info, uint64_t value,
338                                    uint64_t size, uint8_t other,
339                                    uint32_t shndx, bool Reserved) {
340  bool LargeIndex = shndx >= ELF::SHN_LORESERVE && !Reserved;
341
342  if (LargeIndex)
343    createSymtabShndx();
344
345  if (ShndxF) {
346    if (LargeIndex)
347      write(*ShndxF, shndx);
348    else
349      write(*ShndxF, uint32_t(0));
350  }
351
352  uint16_t Index = LargeIndex ? uint16_t(ELF::SHN_XINDEX) : shndx;
353
354  if (Is64Bit) {
355    write(*SymtabF, name);  // st_name
356    write(*SymtabF, info);  // st_info
357    write(*SymtabF, other); // st_other
358    write(*SymtabF, Index); // st_shndx
359    write(*SymtabF, value); // st_value
360    write(*SymtabF, size);  // st_size
361  } else {
362    write(*SymtabF, name);            // st_name
363    write(*SymtabF, uint32_t(value)); // st_value
364    write(*SymtabF, uint32_t(size));  // st_size
365    write(*SymtabF, info);            // st_info
366    write(*SymtabF, other);           // st_other
367    write(*SymtabF, Index);           // st_shndx
368  }
369
370  ++NumWritten;
371}
372
373bool ELFObjectWriter::isFixupKindPCRel(const MCAssembler &Asm, unsigned Kind) {
374  const MCFixupKindInfo &FKI =
375    Asm.getBackend().getFixupKindInfo((MCFixupKind) Kind);
376
377  return FKI.Flags & MCFixupKindInfo::FKF_IsPCRel;
378}
379
380bool ELFObjectWriter::RelocNeedsGOT(MCSymbolRefExpr::VariantKind Variant) {
381  switch (Variant) {
382  default:
383    return false;
384  case MCSymbolRefExpr::VK_GOT:
385  case MCSymbolRefExpr::VK_PLT:
386  case MCSymbolRefExpr::VK_GOTPCREL:
387  case MCSymbolRefExpr::VK_GOTOFF:
388  case MCSymbolRefExpr::VK_TPOFF:
389  case MCSymbolRefExpr::VK_TLSGD:
390  case MCSymbolRefExpr::VK_GOTTPOFF:
391  case MCSymbolRefExpr::VK_INDNTPOFF:
392  case MCSymbolRefExpr::VK_NTPOFF:
393  case MCSymbolRefExpr::VK_GOTNTPOFF:
394  case MCSymbolRefExpr::VK_TLSLDM:
395  case MCSymbolRefExpr::VK_DTPOFF:
396  case MCSymbolRefExpr::VK_TLSLD:
397    return true;
398  }
399}
400
401ELFObjectWriter::~ELFObjectWriter()
402{}
403
404// Emit the ELF header.
405void ELFObjectWriter::WriteHeader(const MCAssembler &Asm,
406                                  unsigned NumberOfSections) {
407  // ELF Header
408  // ----------
409  //
410  // Note
411  // ----
412  // emitWord method behaves differently for ELF32 and ELF64, writing
413  // 4 bytes in the former and 8 in the latter.
414
415  Write8(0x7f); // e_ident[EI_MAG0]
416  Write8('E');  // e_ident[EI_MAG1]
417  Write8('L');  // e_ident[EI_MAG2]
418  Write8('F');  // e_ident[EI_MAG3]
419
420  Write8(is64Bit() ? ELF::ELFCLASS64 : ELF::ELFCLASS32); // e_ident[EI_CLASS]
421
422  // e_ident[EI_DATA]
423  Write8(isLittleEndian() ? ELF::ELFDATA2LSB : ELF::ELFDATA2MSB);
424
425  Write8(ELF::EV_CURRENT);        // e_ident[EI_VERSION]
426  // e_ident[EI_OSABI]
427  Write8(TargetObjectWriter->getOSABI());
428  Write8(0);                  // e_ident[EI_ABIVERSION]
429
430  WriteZeros(ELF::EI_NIDENT - ELF::EI_PAD);
431
432  Write16(ELF::ET_REL);             // e_type
433
434  Write16(TargetObjectWriter->getEMachine()); // e_machine = target
435
436  Write32(ELF::EV_CURRENT);         // e_version
437  WriteWord(0);                    // e_entry, no entry point in .o file
438  WriteWord(0);                    // e_phoff, no program header for .o
439  WriteWord(0);                     // e_shoff = sec hdr table off in bytes
440
441  // e_flags = whatever the target wants
442  Write32(Asm.getELFHeaderEFlags());
443
444  // e_ehsize = ELF header size
445  Write16(is64Bit() ? sizeof(ELF::Elf64_Ehdr) : sizeof(ELF::Elf32_Ehdr));
446
447  Write16(0);                  // e_phentsize = prog header entry size
448  Write16(0);                  // e_phnum = # prog header entries = 0
449
450  // e_shentsize = Section header entry size
451  Write16(is64Bit() ? sizeof(ELF::Elf64_Shdr) : sizeof(ELF::Elf32_Shdr));
452
453  // e_shnum     = # of section header ents
454  if (NumberOfSections >= ELF::SHN_LORESERVE)
455    Write16(ELF::SHN_UNDEF);
456  else
457    Write16(NumberOfSections);
458
459  // e_shstrndx  = Section # of '.shstrtab'
460  if (ShstrtabIndex >= ELF::SHN_LORESERVE)
461    Write16(ELF::SHN_XINDEX);
462  else
463    Write16(ShstrtabIndex);
464}
465
466uint64_t ELFObjectWriter::SymbolValue(MCSymbolData &Data,
467                                      const MCAsmLayout &Layout) {
468  if (Data.isCommon() && Data.isExternal())
469    return Data.getCommonAlignment();
470
471  uint64_t Res;
472  if (!Layout.getSymbolOffset(&Data, Res))
473    return 0;
474
475  if (Layout.getAssembler().isThumbFunc(&Data.getSymbol()))
476    Res |= 1;
477
478  return Res;
479}
480
481void ELFObjectWriter::ExecutePostLayoutBinding(MCAssembler &Asm,
482                                               const MCAsmLayout &Layout) {
483  // The presence of symbol versions causes undefined symbols and
484  // versions declared with @@@ to be renamed.
485
486  for (MCSymbolData &OriginalData : Asm.symbols()) {
487    const MCSymbol &Alias = OriginalData.getSymbol();
488
489    // Not an alias.
490    if (!Alias.isVariable())
491      continue;
492    auto *Ref = dyn_cast<MCSymbolRefExpr>(Alias.getVariableValue());
493    if (!Ref)
494      continue;
495    const MCSymbol &Symbol = Ref->getSymbol();
496    MCSymbolData &SD = Asm.getSymbolData(Symbol);
497
498    StringRef AliasName = Alias.getName();
499    size_t Pos = AliasName.find('@');
500    if (Pos == StringRef::npos)
501      continue;
502
503    // Aliases defined with .symvar copy the binding from the symbol they alias.
504    // This is the first place we are able to copy this information.
505    OriginalData.setExternal(SD.isExternal());
506    MCELF::SetBinding(OriginalData, MCELF::GetBinding(SD));
507
508    StringRef Rest = AliasName.substr(Pos);
509    if (!Symbol.isUndefined() && !Rest.startswith("@@@"))
510      continue;
511
512    // FIXME: produce a better error message.
513    if (Symbol.isUndefined() && Rest.startswith("@@") &&
514        !Rest.startswith("@@@"))
515      report_fatal_error("A @@ version cannot be undefined");
516
517    Renames.insert(std::make_pair(&Symbol, &Alias));
518  }
519}
520
521static uint8_t mergeTypeForSet(uint8_t origType, uint8_t newType) {
522  uint8_t Type = newType;
523
524  // Propagation rules:
525  // IFUNC > FUNC > OBJECT > NOTYPE
526  // TLS_OBJECT > OBJECT > NOTYPE
527  //
528  // dont let the new type degrade the old type
529  switch (origType) {
530  default:
531    break;
532  case ELF::STT_GNU_IFUNC:
533    if (Type == ELF::STT_FUNC || Type == ELF::STT_OBJECT ||
534        Type == ELF::STT_NOTYPE || Type == ELF::STT_TLS)
535      Type = ELF::STT_GNU_IFUNC;
536    break;
537  case ELF::STT_FUNC:
538    if (Type == ELF::STT_OBJECT || Type == ELF::STT_NOTYPE ||
539        Type == ELF::STT_TLS)
540      Type = ELF::STT_FUNC;
541    break;
542  case ELF::STT_OBJECT:
543    if (Type == ELF::STT_NOTYPE)
544      Type = ELF::STT_OBJECT;
545    break;
546  case ELF::STT_TLS:
547    if (Type == ELF::STT_OBJECT || Type == ELF::STT_NOTYPE ||
548        Type == ELF::STT_GNU_IFUNC || Type == ELF::STT_FUNC)
549      Type = ELF::STT_TLS;
550    break;
551  }
552
553  return Type;
554}
555
556void ELFObjectWriter::WriteSymbol(SymbolTableWriter &Writer, ELFSymbolData &MSD,
557                                  const MCAsmLayout &Layout) {
558  MCSymbolData &OrigData = *MSD.SymbolData;
559  assert((!OrigData.getFragment() ||
560          (&OrigData.getFragment()->getParent()->getSection() ==
561           &OrigData.getSymbol().getSection())) &&
562         "The symbol's section doesn't match the fragment's symbol");
563  const MCSymbol *Base = Layout.getBaseSymbol(OrigData.getSymbol());
564
565  // This has to be in sync with when computeSymbolTable uses SHN_ABS or
566  // SHN_COMMON.
567  bool IsReserved = !Base || OrigData.isCommon();
568
569  // Binding and Type share the same byte as upper and lower nibbles
570  uint8_t Binding = MCELF::GetBinding(OrigData);
571  uint8_t Type = MCELF::GetType(OrigData);
572  MCSymbolData *BaseSD = nullptr;
573  if (Base) {
574    BaseSD = &Layout.getAssembler().getSymbolData(*Base);
575    Type = mergeTypeForSet(Type, MCELF::GetType(*BaseSD));
576  }
577  uint8_t Info = (Binding << ELF_STB_Shift) | (Type << ELF_STT_Shift);
578
579  // Other and Visibility share the same byte with Visibility using the lower
580  // 2 bits
581  uint8_t Visibility = MCELF::GetVisibility(OrigData);
582  uint8_t Other = MCELF::getOther(OrigData) << (ELF_STO_Shift - ELF_STV_Shift);
583  Other |= Visibility;
584
585  uint64_t Value = SymbolValue(OrigData, Layout);
586  uint64_t Size = 0;
587
588  const MCExpr *ESize = OrigData.getSize();
589  if (!ESize && Base)
590    ESize = BaseSD->getSize();
591
592  if (ESize) {
593    int64_t Res;
594    if (!ESize->evaluateKnownAbsolute(Res, Layout))
595      report_fatal_error("Size expression must be absolute.");
596    Size = Res;
597  }
598
599  // Write out the symbol table entry
600  Writer.writeSymbol(MSD.StringIndex, Info, Value, Size, Other,
601                     MSD.SectionIndex, IsReserved);
602}
603
604void ELFObjectWriter::WriteSymbolTable(MCDataFragment *SymtabF,
605                                       MCAssembler &Asm,
606                                       const MCAsmLayout &Layout,
607                                       SectionIndexMapTy &SectionIndexMap) {
608  // The string table must be emitted first because we need the index
609  // into the string table for all the symbol names.
610
611  // FIXME: Make sure the start of the symbol table is aligned.
612
613  SymbolTableWriter Writer(Asm, FWriter, is64Bit(), SectionIndexMap, SymtabF);
614
615  // The first entry is the undefined symbol entry.
616  Writer.writeSymbol(0, 0, 0, 0, 0, 0, false);
617
618  for (unsigned i = 0, e = FileSymbolData.size(); i != e; ++i) {
619    Writer.writeSymbol(FileSymbolData[i], ELF::STT_FILE | ELF::STB_LOCAL, 0, 0,
620                       ELF::STV_DEFAULT, ELF::SHN_ABS, true);
621  }
622
623  // Write the symbol table entries.
624  LastLocalSymbolIndex = FileSymbolData.size() + LocalSymbolData.size() + 1;
625
626  for (unsigned i = 0, e = LocalSymbolData.size(); i != e; ++i) {
627    ELFSymbolData &MSD = LocalSymbolData[i];
628    WriteSymbol(Writer, MSD, Layout);
629  }
630
631  for (unsigned i = 0, e = ExternalSymbolData.size(); i != e; ++i) {
632    ELFSymbolData &MSD = ExternalSymbolData[i];
633    MCSymbolData &Data = *MSD.SymbolData;
634    assert(((Data.getFlags() & ELF_STB_Global) ||
635            (Data.getFlags() & ELF_STB_Weak)) &&
636           "External symbol requires STB_GLOBAL or STB_WEAK flag");
637    WriteSymbol(Writer, MSD, Layout);
638    if (MCELF::GetBinding(Data) == ELF::STB_LOCAL)
639      LastLocalSymbolIndex++;
640  }
641
642  for (unsigned i = 0, e = UndefinedSymbolData.size(); i != e; ++i) {
643    ELFSymbolData &MSD = UndefinedSymbolData[i];
644    MCSymbolData &Data = *MSD.SymbolData;
645    WriteSymbol(Writer, MSD, Layout);
646    if (MCELF::GetBinding(Data) == ELF::STB_LOCAL)
647      LastLocalSymbolIndex++;
648  }
649}
650
651// It is always valid to create a relocation with a symbol. It is preferable
652// to use a relocation with a section if that is possible. Using the section
653// allows us to omit some local symbols from the symbol table.
654bool ELFObjectWriter::shouldRelocateWithSymbol(const MCAssembler &Asm,
655                                               const MCSymbolRefExpr *RefA,
656                                               const MCSymbolData *SD,
657                                               uint64_t C,
658                                               unsigned Type) const {
659  // A PCRel relocation to an absolute value has no symbol (or section). We
660  // represent that with a relocation to a null section.
661  if (!RefA)
662    return false;
663
664  MCSymbolRefExpr::VariantKind Kind = RefA->getKind();
665  switch (Kind) {
666  default:
667    break;
668  // The .odp creation emits a relocation against the symbol ".TOC." which
669  // create a R_PPC64_TOC relocation. However the relocation symbol name
670  // in final object creation should be NULL, since the symbol does not
671  // really exist, it is just the reference to TOC base for the current
672  // object file. Since the symbol is undefined, returning false results
673  // in a relocation with a null section which is the desired result.
674  case MCSymbolRefExpr::VK_PPC_TOCBASE:
675    return false;
676
677  // These VariantKind cause the relocation to refer to something other than
678  // the symbol itself, like a linker generated table. Since the address of
679  // symbol is not relevant, we cannot replace the symbol with the
680  // section and patch the difference in the addend.
681  case MCSymbolRefExpr::VK_GOT:
682  case MCSymbolRefExpr::VK_PLT:
683  case MCSymbolRefExpr::VK_GOTPCREL:
684  case MCSymbolRefExpr::VK_Mips_GOT:
685  case MCSymbolRefExpr::VK_PPC_GOT_LO:
686  case MCSymbolRefExpr::VK_PPC_GOT_HI:
687  case MCSymbolRefExpr::VK_PPC_GOT_HA:
688    return true;
689  }
690
691  // An undefined symbol is not in any section, so the relocation has to point
692  // to the symbol itself.
693  const MCSymbol &Sym = SD->getSymbol();
694  if (Sym.isUndefined())
695    return true;
696
697  unsigned Binding = MCELF::GetBinding(*SD);
698  switch(Binding) {
699  default:
700    llvm_unreachable("Invalid Binding");
701  case ELF::STB_LOCAL:
702    break;
703  case ELF::STB_WEAK:
704    // If the symbol is weak, it might be overridden by a symbol in another
705    // file. The relocation has to point to the symbol so that the linker
706    // can update it.
707    return true;
708  case ELF::STB_GLOBAL:
709    // Global ELF symbols can be preempted by the dynamic linker. The relocation
710    // has to point to the symbol for a reason analogous to the STB_WEAK case.
711    return true;
712  }
713
714  // If a relocation points to a mergeable section, we have to be careful.
715  // If the offset is zero, a relocation with the section will encode the
716  // same information. With a non-zero offset, the situation is different.
717  // For example, a relocation can point 42 bytes past the end of a string.
718  // If we change such a relocation to use the section, the linker would think
719  // that it pointed to another string and subtracting 42 at runtime will
720  // produce the wrong value.
721  auto &Sec = cast<MCSectionELF>(Sym.getSection());
722  unsigned Flags = Sec.getFlags();
723  if (Flags & ELF::SHF_MERGE) {
724    if (C != 0)
725      return true;
726
727    // It looks like gold has a bug (http://sourceware.org/PR16794) and can
728    // only handle section relocations to mergeable sections if using RELA.
729    if (!hasRelocationAddend())
730      return true;
731  }
732
733  // Most TLS relocations use a got, so they need the symbol. Even those that
734  // are just an offset (@tpoff), require a symbol in gold versions before
735  // 5efeedf61e4fe720fd3e9a08e6c91c10abb66d42 (2014-09-26) which fixed
736  // http://sourceware.org/PR16773.
737  if (Flags & ELF::SHF_TLS)
738    return true;
739
740  // If the symbol is a thumb function the final relocation must set the lowest
741  // bit. With a symbol that is done by just having the symbol have that bit
742  // set, so we would lose the bit if we relocated with the section.
743  // FIXME: We could use the section but add the bit to the relocation value.
744  if (Asm.isThumbFunc(&Sym))
745    return true;
746
747  if (TargetObjectWriter->needsRelocateWithSymbol(*SD, Type))
748    return true;
749  return false;
750}
751
752static const MCSymbol *getWeakRef(const MCSymbolRefExpr &Ref) {
753  const MCSymbol &Sym = Ref.getSymbol();
754
755  if (Ref.getKind() == MCSymbolRefExpr::VK_WEAKREF)
756    return &Sym;
757
758  if (!Sym.isVariable())
759    return nullptr;
760
761  const MCExpr *Expr = Sym.getVariableValue();
762  const auto *Inner = dyn_cast<MCSymbolRefExpr>(Expr);
763  if (!Inner)
764    return nullptr;
765
766  if (Inner->getKind() == MCSymbolRefExpr::VK_WEAKREF)
767    return &Inner->getSymbol();
768  return nullptr;
769}
770
771static bool isWeak(const MCSymbolData &D) {
772  return D.getFlags() & ELF_STB_Weak || MCELF::GetType(D) == ELF::STT_GNU_IFUNC;
773}
774
775void ELFObjectWriter::RecordRelocation(MCAssembler &Asm,
776                                       const MCAsmLayout &Layout,
777                                       const MCFragment *Fragment,
778                                       const MCFixup &Fixup, MCValue Target,
779                                       bool &IsPCRel, uint64_t &FixedValue) {
780  const MCSectionData *FixupSection = Fragment->getParent();
781  uint64_t C = Target.getConstant();
782  uint64_t FixupOffset = Layout.getFragmentOffset(Fragment) + Fixup.getOffset();
783
784  if (const MCSymbolRefExpr *RefB = Target.getSymB()) {
785    assert(RefB->getKind() == MCSymbolRefExpr::VK_None &&
786           "Should not have constructed this");
787
788    // Let A, B and C being the components of Target and R be the location of
789    // the fixup. If the fixup is not pcrel, we want to compute (A - B + C).
790    // If it is pcrel, we want to compute (A - B + C - R).
791
792    // In general, ELF has no relocations for -B. It can only represent (A + C)
793    // or (A + C - R). If B = R + K and the relocation is not pcrel, we can
794    // replace B to implement it: (A - R - K + C)
795    if (IsPCRel)
796      Asm.getContext().FatalError(
797          Fixup.getLoc(),
798          "No relocation available to represent this relative expression");
799
800    const MCSymbol &SymB = RefB->getSymbol();
801
802    if (SymB.isUndefined())
803      Asm.getContext().FatalError(
804          Fixup.getLoc(),
805          Twine("symbol '") + SymB.getName() +
806              "' can not be undefined in a subtraction expression");
807
808    assert(!SymB.isAbsolute() && "Should have been folded");
809    const MCSection &SecB = SymB.getSection();
810    if (&SecB != &FixupSection->getSection())
811      Asm.getContext().FatalError(
812          Fixup.getLoc(), "Cannot represent a difference across sections");
813
814    const MCSymbolData &SymBD = Asm.getSymbolData(SymB);
815    if (::isWeak(SymBD))
816      Asm.getContext().FatalError(
817          Fixup.getLoc(), "Cannot represent a subtraction with a weak symbol");
818
819    uint64_t SymBOffset = Layout.getSymbolOffset(&SymBD);
820    uint64_t K = SymBOffset - FixupOffset;
821    IsPCRel = true;
822    C -= K;
823  }
824
825  // We either rejected the fixup or folded B into C at this point.
826  const MCSymbolRefExpr *RefA = Target.getSymA();
827  const MCSymbol *SymA = RefA ? &RefA->getSymbol() : nullptr;
828  const MCSymbolData *SymAD = SymA ? &Asm.getSymbolData(*SymA) : nullptr;
829
830  unsigned Type = GetRelocType(Target, Fixup, IsPCRel);
831  bool RelocateWithSymbol = shouldRelocateWithSymbol(Asm, RefA, SymAD, C, Type);
832  if (!RelocateWithSymbol && SymA && !SymA->isUndefined())
833    C += Layout.getSymbolOffset(SymAD);
834
835  uint64_t Addend = 0;
836  if (hasRelocationAddend()) {
837    Addend = C;
838    C = 0;
839  }
840
841  FixedValue = C;
842
843  // FIXME: What is this!?!?
844  MCSymbolRefExpr::VariantKind Modifier =
845      RefA ? RefA->getKind() : MCSymbolRefExpr::VK_None;
846  if (RelocNeedsGOT(Modifier))
847    NeedsGOT = true;
848
849  if (!RelocateWithSymbol) {
850    const MCSection *SecA =
851        (SymA && !SymA->isUndefined()) ? &SymA->getSection() : nullptr;
852    auto *ELFSec = cast_or_null<MCSectionELF>(SecA);
853    MCSymbol *SectionSymbol =
854        ELFSec ? Asm.getContext().getOrCreateSectionSymbol(*ELFSec)
855               : nullptr;
856    ELFRelocationEntry Rec(FixupOffset, SectionSymbol, Type, Addend);
857    Relocations[FixupSection].push_back(Rec);
858    return;
859  }
860
861  if (SymA) {
862    if (const MCSymbol *R = Renames.lookup(SymA))
863      SymA = R;
864
865    if (const MCSymbol *WeakRef = getWeakRef(*RefA))
866      WeakrefUsedInReloc.insert(WeakRef);
867    else
868      UsedInReloc.insert(SymA);
869  }
870  ELFRelocationEntry Rec(FixupOffset, SymA, Type, Addend);
871  Relocations[FixupSection].push_back(Rec);
872  return;
873}
874
875
876uint64_t
877ELFObjectWriter::getSymbolIndexInSymbolTable(const MCAssembler &Asm,
878                                             const MCSymbol *S) {
879  const MCSymbolData &SD = Asm.getSymbolData(*S);
880  return SD.getIndex();
881}
882
883bool ELFObjectWriter::isInSymtab(const MCAsmLayout &Layout,
884                                 const MCSymbolData &Data, bool Used,
885                                 bool Renamed) {
886  const MCSymbol &Symbol = Data.getSymbol();
887  if (Symbol.isVariable()) {
888    const MCExpr *Expr = Symbol.getVariableValue();
889    if (const MCSymbolRefExpr *Ref = dyn_cast<MCSymbolRefExpr>(Expr)) {
890      if (Ref->getKind() == MCSymbolRefExpr::VK_WEAKREF)
891        return false;
892    }
893  }
894
895  if (Used)
896    return true;
897
898  if (Renamed)
899    return false;
900
901  if (Symbol.getName() == "_GLOBAL_OFFSET_TABLE_")
902    return true;
903
904  if (Symbol.isVariable()) {
905    const MCSymbol *Base = Layout.getBaseSymbol(Symbol);
906    if (Base && Base->isUndefined())
907      return false;
908  }
909
910  bool IsGlobal = MCELF::GetBinding(Data) == ELF::STB_GLOBAL;
911  if (!Symbol.isVariable() && Symbol.isUndefined() && !IsGlobal)
912    return false;
913
914  if (Symbol.isTemporary())
915    return false;
916
917  return true;
918}
919
920bool ELFObjectWriter::isLocal(const MCSymbolData &Data, bool isUsedInReloc) {
921  if (Data.isExternal())
922    return false;
923
924  const MCSymbol &Symbol = Data.getSymbol();
925  if (Symbol.isDefined())
926    return true;
927
928  if (isUsedInReloc)
929    return false;
930
931  return true;
932}
933
934void ELFObjectWriter::computeIndexMap(MCAssembler &Asm,
935                                      SectionIndexMapTy &SectionIndexMap) {
936  unsigned Index = 1;
937  for (MCAssembler::iterator it = Asm.begin(),
938         ie = Asm.end(); it != ie; ++it) {
939    const MCSectionELF &Section =
940      static_cast<const MCSectionELF &>(it->getSection());
941    if (Section.getType() != ELF::SHT_GROUP)
942      continue;
943    SectionIndexMap[&Section] = Index++;
944  }
945
946  for (MCAssembler::iterator it = Asm.begin(),
947         ie = Asm.end(); it != ie; ++it) {
948    const MCSectionData &SD = *it;
949    const MCSectionELF &Section =
950      static_cast<const MCSectionELF &>(SD.getSection());
951    if (Section.getType() == ELF::SHT_GROUP ||
952        Section.getType() == ELF::SHT_REL ||
953        Section.getType() == ELF::SHT_RELA)
954      continue;
955    SectionIndexMap[&Section] = Index++;
956    if (MCSectionData *RelSD = createRelocationSection(Asm, SD)) {
957      const MCSectionELF *RelSection =
958          static_cast<const MCSectionELF *>(&RelSD->getSection());
959      SectionIndexMap[RelSection] = Index++;
960    }
961  }
962}
963
964void ELFObjectWriter::computeSymbolTable(
965    MCAssembler &Asm, const MCAsmLayout &Layout,
966    const SectionIndexMapTy &SectionIndexMap,
967    const RevGroupMapTy &RevGroupMap) {
968  // FIXME: Is this the correct place to do this?
969  // FIXME: Why is an undefined reference to _GLOBAL_OFFSET_TABLE_ needed?
970  if (NeedsGOT) {
971    StringRef Name = "_GLOBAL_OFFSET_TABLE_";
972    MCSymbol *Sym = Asm.getContext().GetOrCreateSymbol(Name);
973    MCSymbolData &Data = Asm.getOrCreateSymbolData(*Sym);
974    Data.setExternal(true);
975    MCELF::SetBinding(Data, ELF::STB_GLOBAL);
976  }
977
978  // Add the data for the symbols.
979  for (MCSymbolData &SD : Asm.symbols()) {
980    const MCSymbol &Symbol = SD.getSymbol();
981
982    bool Used = UsedInReloc.count(&Symbol);
983    bool WeakrefUsed = WeakrefUsedInReloc.count(&Symbol);
984    bool isSignature = RevGroupMap.count(&Symbol);
985
986    if (!isInSymtab(Layout, SD,
987                    Used || WeakrefUsed || isSignature,
988                    Renames.count(&Symbol)))
989      continue;
990
991    ELFSymbolData MSD;
992    MSD.SymbolData = &SD;
993    const MCSymbol *BaseSymbol = Layout.getBaseSymbol(Symbol);
994
995    // Undefined symbols are global, but this is the first place we
996    // are able to set it.
997    bool Local = isLocal(SD, Used);
998    if (!Local && MCELF::GetBinding(SD) == ELF::STB_LOCAL) {
999      assert(BaseSymbol);
1000      MCSymbolData &BaseData = Asm.getSymbolData(*BaseSymbol);
1001      MCELF::SetBinding(SD, ELF::STB_GLOBAL);
1002      MCELF::SetBinding(BaseData, ELF::STB_GLOBAL);
1003    }
1004
1005    if (!BaseSymbol) {
1006      MSD.SectionIndex = ELF::SHN_ABS;
1007    } else if (SD.isCommon()) {
1008      assert(!Local);
1009      MSD.SectionIndex = ELF::SHN_COMMON;
1010    } else if (BaseSymbol->isUndefined()) {
1011      if (isSignature && !Used)
1012        MSD.SectionIndex = SectionIndexMap.lookup(RevGroupMap.lookup(&Symbol));
1013      else
1014        MSD.SectionIndex = ELF::SHN_UNDEF;
1015      if (!Used && WeakrefUsed)
1016        MCELF::SetBinding(SD, ELF::STB_WEAK);
1017    } else {
1018      const MCSectionELF &Section =
1019        static_cast<const MCSectionELF&>(BaseSymbol->getSection());
1020      MSD.SectionIndex = SectionIndexMap.lookup(&Section);
1021      assert(MSD.SectionIndex && "Invalid section index!");
1022    }
1023
1024    // The @@@ in symbol version is replaced with @ in undefined symbols and @@
1025    // in defined ones.
1026    //
1027    // FIXME: All name handling should be done before we get to the writer,
1028    // including dealing with GNU-style version suffixes.  Fixing this isn't
1029    // trivial.
1030    //
1031    // We thus have to be careful to not perform the symbol version replacement
1032    // blindly:
1033    //
1034    // The ELF format is used on Windows by the MCJIT engine.  Thus, on
1035    // Windows, the ELFObjectWriter can encounter symbols mangled using the MS
1036    // Visual Studio C++ name mangling scheme. Symbols mangled using the MSVC
1037    // C++ name mangling can legally have "@@@" as a sub-string. In that case,
1038    // the EFLObjectWriter should not interpret the "@@@" sub-string as
1039    // specifying GNU-style symbol versioning. The ELFObjectWriter therefore
1040    // checks for the MSVC C++ name mangling prefix which is either "?", "@?",
1041    // "__imp_?" or "__imp_@?".
1042    //
1043    // It would have been interesting to perform the MS mangling prefix check
1044    // only when the target triple is of the form *-pc-windows-elf. But, it
1045    // seems that this information is not easily accessible from the
1046    // ELFObjectWriter.
1047    StringRef Name = Symbol.getName();
1048    if (!Name.startswith("?") && !Name.startswith("@?") &&
1049        !Name.startswith("__imp_?") && !Name.startswith("__imp_@?")) {
1050      // This symbol isn't following the MSVC C++ name mangling convention. We
1051      // can thus safely interpret the @@@ in symbol names as specifying symbol
1052      // versioning.
1053      SmallString<32> Buf;
1054      size_t Pos = Name.find("@@@");
1055      if (Pos != StringRef::npos) {
1056        Buf += Name.substr(0, Pos);
1057        unsigned Skip = MSD.SectionIndex == ELF::SHN_UNDEF ? 2 : 1;
1058        Buf += Name.substr(Pos + Skip);
1059        Name = Buf;
1060      }
1061    }
1062
1063    // Sections have their own string table
1064    if (MCELF::GetType(SD) != ELF::STT_SECTION)
1065      MSD.Name = StrTabBuilder.add(Name);
1066
1067    if (MSD.SectionIndex == ELF::SHN_UNDEF)
1068      UndefinedSymbolData.push_back(MSD);
1069    else if (Local)
1070      LocalSymbolData.push_back(MSD);
1071    else
1072      ExternalSymbolData.push_back(MSD);
1073  }
1074
1075  for (auto i = Asm.file_names_begin(), e = Asm.file_names_end(); i != e; ++i)
1076    StrTabBuilder.add(*i);
1077
1078  StrTabBuilder.finalize(StringTableBuilder::ELF);
1079
1080  for (auto i = Asm.file_names_begin(), e = Asm.file_names_end(); i != e; ++i)
1081    FileSymbolData.push_back(StrTabBuilder.getOffset(*i));
1082
1083  for (ELFSymbolData &MSD : LocalSymbolData)
1084    MSD.StringIndex = MCELF::GetType(*MSD.SymbolData) == ELF::STT_SECTION
1085                          ? 0
1086                          : StrTabBuilder.getOffset(MSD.Name);
1087  for (ELFSymbolData &MSD : ExternalSymbolData)
1088    MSD.StringIndex = StrTabBuilder.getOffset(MSD.Name);
1089  for (ELFSymbolData& MSD : UndefinedSymbolData)
1090    MSD.StringIndex = StrTabBuilder.getOffset(MSD.Name);
1091
1092  // Symbols are required to be in lexicographic order.
1093  array_pod_sort(LocalSymbolData.begin(), LocalSymbolData.end());
1094  array_pod_sort(ExternalSymbolData.begin(), ExternalSymbolData.end());
1095  array_pod_sort(UndefinedSymbolData.begin(), UndefinedSymbolData.end());
1096
1097  // Set the symbol indices. Local symbols must come before all other
1098  // symbols with non-local bindings.
1099  unsigned Index = FileSymbolData.size() + 1;
1100  for (unsigned i = 0, e = LocalSymbolData.size(); i != e; ++i)
1101    LocalSymbolData[i].SymbolData->setIndex(Index++);
1102
1103  for (unsigned i = 0, e = ExternalSymbolData.size(); i != e; ++i)
1104    ExternalSymbolData[i].SymbolData->setIndex(Index++);
1105  for (unsigned i = 0, e = UndefinedSymbolData.size(); i != e; ++i)
1106    UndefinedSymbolData[i].SymbolData->setIndex(Index++);
1107}
1108
1109MCSectionData *
1110ELFObjectWriter::createRelocationSection(MCAssembler &Asm,
1111                                         const MCSectionData &SD) {
1112  if (Relocations[&SD].empty())
1113    return nullptr;
1114
1115  MCContext &Ctx = Asm.getContext();
1116  const MCSectionELF &Section =
1117      static_cast<const MCSectionELF &>(SD.getSection());
1118
1119  const StringRef SectionName = Section.getSectionName();
1120  std::string RelaSectionName = hasRelocationAddend() ? ".rela" : ".rel";
1121  RelaSectionName += SectionName;
1122
1123  unsigned EntrySize;
1124  if (hasRelocationAddend())
1125    EntrySize = is64Bit() ? sizeof(ELF::Elf64_Rela) : sizeof(ELF::Elf32_Rela);
1126  else
1127    EntrySize = is64Bit() ? sizeof(ELF::Elf64_Rel) : sizeof(ELF::Elf32_Rel);
1128
1129  unsigned Flags = 0;
1130  if (Section.getFlags() & ELF::SHF_GROUP)
1131    Flags = ELF::SHF_GROUP;
1132
1133  const MCSectionELF *RelaSection = Ctx.createELFRelSection(
1134      RelaSectionName, hasRelocationAddend() ? ELF::SHT_RELA : ELF::SHT_REL,
1135      Flags, EntrySize, Section.getGroup(), &Section);
1136  return &Asm.getOrCreateSectionData(*RelaSection);
1137}
1138
1139static SmallVector<char, 128>
1140getUncompressedData(MCAsmLayout &Layout,
1141                    MCSectionData::FragmentListType &Fragments) {
1142  SmallVector<char, 128> UncompressedData;
1143  for (const MCFragment &F : Fragments) {
1144    const SmallVectorImpl<char> *Contents;
1145    switch (F.getKind()) {
1146    case MCFragment::FT_Data:
1147      Contents = &cast<MCDataFragment>(F).getContents();
1148      break;
1149    case MCFragment::FT_Dwarf:
1150      Contents = &cast<MCDwarfLineAddrFragment>(F).getContents();
1151      break;
1152    case MCFragment::FT_DwarfFrame:
1153      Contents = &cast<MCDwarfCallFrameFragment>(F).getContents();
1154      break;
1155    default:
1156      llvm_unreachable(
1157          "Not expecting any other fragment types in a debug_* section");
1158    }
1159    UncompressedData.append(Contents->begin(), Contents->end());
1160  }
1161  return UncompressedData;
1162}
1163
1164// Include the debug info compression header:
1165// "ZLIB" followed by 8 bytes representing the uncompressed size of the section,
1166// useful for consumers to preallocate a buffer to decompress into.
1167static bool
1168prependCompressionHeader(uint64_t Size,
1169                         SmallVectorImpl<char> &CompressedContents) {
1170  const StringRef Magic = "ZLIB";
1171  if (Size <= Magic.size() + sizeof(Size) + CompressedContents.size())
1172    return false;
1173  if (sys::IsLittleEndianHost)
1174    sys::swapByteOrder(Size);
1175  CompressedContents.insert(CompressedContents.begin(),
1176                            Magic.size() + sizeof(Size), 0);
1177  std::copy(Magic.begin(), Magic.end(), CompressedContents.begin());
1178  std::copy(reinterpret_cast<char *>(&Size),
1179            reinterpret_cast<char *>(&Size + 1),
1180            CompressedContents.begin() + Magic.size());
1181  return true;
1182}
1183
1184// Return a single fragment containing the compressed contents of the whole
1185// section. Null if the section was not compressed for any reason.
1186static std::unique_ptr<MCDataFragment>
1187getCompressedFragment(MCAsmLayout &Layout,
1188                      MCSectionData::FragmentListType &Fragments) {
1189  std::unique_ptr<MCDataFragment> CompressedFragment(new MCDataFragment());
1190
1191  // Gather the uncompressed data from all the fragments, recording the
1192  // alignment fragment, if seen, and any fixups.
1193  SmallVector<char, 128> UncompressedData =
1194      getUncompressedData(Layout, Fragments);
1195
1196  SmallVectorImpl<char> &CompressedContents = CompressedFragment->getContents();
1197
1198  zlib::Status Success = zlib::compress(
1199      StringRef(UncompressedData.data(), UncompressedData.size()),
1200      CompressedContents);
1201  if (Success != zlib::StatusOK)
1202    return nullptr;
1203
1204  if (!prependCompressionHeader(UncompressedData.size(), CompressedContents))
1205    return nullptr;
1206
1207  return CompressedFragment;
1208}
1209
1210typedef DenseMap<const MCSectionData *, std::vector<MCSymbolData *>>
1211DefiningSymbolMap;
1212
1213static void UpdateSymbols(const MCAsmLayout &Layout,
1214                          const std::vector<MCSymbolData *> &Symbols,
1215                          MCFragment &NewFragment) {
1216  for (MCSymbolData *Sym : Symbols) {
1217    Sym->setOffset(Sym->getOffset() +
1218                   Layout.getFragmentOffset(Sym->getFragment()));
1219    Sym->setFragment(&NewFragment);
1220  }
1221}
1222
1223static void CompressDebugSection(MCAssembler &Asm, MCAsmLayout &Layout,
1224                                 const DefiningSymbolMap &DefiningSymbols,
1225                                 const MCSectionELF &Section,
1226                                 MCSectionData &SD) {
1227  StringRef SectionName = Section.getSectionName();
1228  MCSectionData::FragmentListType &Fragments = SD.getFragmentList();
1229
1230  std::unique_ptr<MCDataFragment> CompressedFragment =
1231      getCompressedFragment(Layout, Fragments);
1232
1233  // Leave the section as-is if the fragments could not be compressed.
1234  if (!CompressedFragment)
1235    return;
1236
1237  // Update the fragment+offsets of any symbols referring to fragments in this
1238  // section to refer to the new fragment.
1239  auto I = DefiningSymbols.find(&SD);
1240  if (I != DefiningSymbols.end())
1241    UpdateSymbols(Layout, I->second, *CompressedFragment);
1242
1243  // Invalidate the layout for the whole section since it will have new and
1244  // different fragments now.
1245  Layout.invalidateFragmentsFrom(&Fragments.front());
1246  Fragments.clear();
1247
1248  // Complete the initialization of the new fragment
1249  CompressedFragment->setParent(&SD);
1250  CompressedFragment->setLayoutOrder(0);
1251  Fragments.push_back(CompressedFragment.release());
1252
1253  // Rename from .debug_* to .zdebug_*
1254  Asm.getContext().renameELFSection(&Section,
1255                                    (".z" + SectionName.drop_front(1)).str());
1256}
1257
1258void ELFObjectWriter::CompressDebugSections(MCAssembler &Asm,
1259                                            MCAsmLayout &Layout) {
1260  if (!Asm.getContext().getAsmInfo()->compressDebugSections())
1261    return;
1262
1263  DefiningSymbolMap DefiningSymbols;
1264
1265  for (MCSymbolData &SD : Asm.symbols())
1266    if (MCFragment *F = SD.getFragment())
1267      DefiningSymbols[F->getParent()].push_back(&SD);
1268
1269  for (MCSectionData &SD : Asm) {
1270    const MCSectionELF &Section =
1271        static_cast<const MCSectionELF &>(SD.getSection());
1272    StringRef SectionName = Section.getSectionName();
1273
1274    // Compressing debug_frame requires handling alignment fragments which is
1275    // more work (possibly generalizing MCAssembler.cpp:writeFragment to allow
1276    // for writing to arbitrary buffers) for little benefit.
1277    if (!SectionName.startswith(".debug_") || SectionName == ".debug_frame")
1278      continue;
1279
1280    CompressDebugSection(Asm, Layout, DefiningSymbols, Section, SD);
1281  }
1282}
1283
1284void ELFObjectWriter::WriteRelocations(MCAssembler &Asm, MCAsmLayout &Layout) {
1285  for (MCAssembler::iterator it = Asm.begin(), ie = Asm.end(); it != ie; ++it) {
1286    MCSectionData &RelSD = *it;
1287    const MCSectionELF &RelSection =
1288        static_cast<const MCSectionELF &>(RelSD.getSection());
1289
1290    unsigned Type = RelSection.getType();
1291    if (Type != ELF::SHT_REL && Type != ELF::SHT_RELA)
1292      continue;
1293
1294    const MCSectionELF *Section = RelSection.getAssociatedSection();
1295    MCSectionData &SD = Asm.getOrCreateSectionData(*Section);
1296    RelSD.setAlignment(is64Bit() ? 8 : 4);
1297
1298    MCDataFragment *F = new MCDataFragment(&RelSD);
1299    WriteRelocationsFragment(Asm, F, &SD);
1300  }
1301}
1302
1303void ELFObjectWriter::WriteSecHdrEntry(uint32_t Name, uint32_t Type,
1304                                       uint64_t Flags, uint64_t Address,
1305                                       uint64_t Offset, uint64_t Size,
1306                                       uint32_t Link, uint32_t Info,
1307                                       uint64_t Alignment,
1308                                       uint64_t EntrySize) {
1309  Write32(Name);        // sh_name: index into string table
1310  Write32(Type);        // sh_type
1311  WriteWord(Flags);     // sh_flags
1312  WriteWord(Address);   // sh_addr
1313  WriteWord(Offset);    // sh_offset
1314  WriteWord(Size);      // sh_size
1315  Write32(Link);        // sh_link
1316  Write32(Info);        // sh_info
1317  WriteWord(Alignment); // sh_addralign
1318  WriteWord(EntrySize); // sh_entsize
1319}
1320
1321void ELFObjectWriter::WriteRelocationsFragment(const MCAssembler &Asm,
1322                                               MCDataFragment *F,
1323                                               const MCSectionData *SD) {
1324  std::vector<ELFRelocationEntry> &Relocs = Relocations[SD];
1325
1326  // Sort the relocation entries. Most targets just sort by Offset, but some
1327  // (e.g., MIPS) have additional constraints.
1328  TargetObjectWriter->sortRelocs(Asm, Relocs);
1329
1330  for (unsigned i = 0, e = Relocs.size(); i != e; ++i) {
1331    const ELFRelocationEntry &Entry = Relocs[e - i - 1];
1332    unsigned Index =
1333        Entry.Symbol ? getSymbolIndexInSymbolTable(Asm, Entry.Symbol) : 0;
1334
1335    if (is64Bit()) {
1336      write(*F, Entry.Offset);
1337      if (TargetObjectWriter->isN64()) {
1338        write(*F, uint32_t(Index));
1339
1340        write(*F, TargetObjectWriter->getRSsym(Entry.Type));
1341        write(*F, TargetObjectWriter->getRType3(Entry.Type));
1342        write(*F, TargetObjectWriter->getRType2(Entry.Type));
1343        write(*F, TargetObjectWriter->getRType(Entry.Type));
1344      } else {
1345        struct ELF::Elf64_Rela ERE64;
1346        ERE64.setSymbolAndType(Index, Entry.Type);
1347        write(*F, ERE64.r_info);
1348      }
1349      if (hasRelocationAddend())
1350        write(*F, Entry.Addend);
1351    } else {
1352      write(*F, uint32_t(Entry.Offset));
1353
1354      struct ELF::Elf32_Rela ERE32;
1355      ERE32.setSymbolAndType(Index, Entry.Type);
1356      write(*F, ERE32.r_info);
1357
1358      if (hasRelocationAddend())
1359        write(*F, uint32_t(Entry.Addend));
1360    }
1361  }
1362}
1363
1364void ELFObjectWriter::CreateMetadataSections(
1365    MCAssembler &Asm, MCAsmLayout &Layout, SectionIndexMapTy &SectionIndexMap) {
1366  MCContext &Ctx = Asm.getContext();
1367  MCDataFragment *F;
1368
1369  unsigned EntrySize = is64Bit() ? ELF::SYMENTRY_SIZE64 : ELF::SYMENTRY_SIZE32;
1370
1371  // We construct .shstrtab, .symtab and .strtab in this order to match gnu as.
1372  const MCSectionELF *ShstrtabSection =
1373      Ctx.getELFSection(".shstrtab", ELF::SHT_STRTAB, 0);
1374  MCSectionData &ShstrtabSD = Asm.getOrCreateSectionData(*ShstrtabSection);
1375  ShstrtabSD.setAlignment(1);
1376  ShstrtabIndex = SectionIndexMap.size() + 1;
1377  SectionIndexMap[ShstrtabSection] = ShstrtabIndex;
1378
1379  const MCSectionELF *SymtabSection =
1380    Ctx.getELFSection(".symtab", ELF::SHT_SYMTAB, 0,
1381                      EntrySize, "");
1382  MCSectionData &SymtabSD = Asm.getOrCreateSectionData(*SymtabSection);
1383  SymtabSD.setAlignment(is64Bit() ? 8 : 4);
1384  SymbolTableIndex = SectionIndexMap.size() + 1;
1385  SectionIndexMap[SymtabSection] = SymbolTableIndex;
1386
1387  const MCSectionELF *StrtabSection;
1388  StrtabSection = Ctx.getELFSection(".strtab", ELF::SHT_STRTAB, 0);
1389  MCSectionData &StrtabSD = Asm.getOrCreateSectionData(*StrtabSection);
1390  StrtabSD.setAlignment(1);
1391  StringTableIndex = SectionIndexMap.size() + 1;
1392  SectionIndexMap[StrtabSection] = StringTableIndex;
1393
1394  // Symbol table
1395  F = new MCDataFragment(&SymtabSD);
1396  WriteSymbolTable(F, Asm, Layout, SectionIndexMap);
1397
1398  F = new MCDataFragment(&StrtabSD);
1399  F->getContents().append(StrTabBuilder.data().begin(),
1400                          StrTabBuilder.data().end());
1401
1402  F = new MCDataFragment(&ShstrtabSD);
1403
1404  // Section header string table.
1405  for (auto it = Asm.begin(), ie = Asm.end(); it != ie; ++it) {
1406    const MCSectionELF &Section =
1407      static_cast<const MCSectionELF&>(it->getSection());
1408    ShStrTabBuilder.add(Section.getSectionName());
1409  }
1410  ShStrTabBuilder.finalize(StringTableBuilder::ELF);
1411  F->getContents().append(ShStrTabBuilder.data().begin(),
1412                          ShStrTabBuilder.data().end());
1413}
1414
1415void ELFObjectWriter::createIndexedSections(
1416    MCAssembler &Asm, MCAsmLayout &Layout, GroupMapTy &GroupMap,
1417    RevGroupMapTy &RevGroupMap, SectionIndexMapTy &SectionIndexMap) {
1418  MCContext &Ctx = Asm.getContext();
1419
1420  // Build the groups
1421  for (MCAssembler::const_iterator it = Asm.begin(), ie = Asm.end();
1422       it != ie; ++it) {
1423    const MCSectionELF &Section =
1424      static_cast<const MCSectionELF&>(it->getSection());
1425    if (!(Section.getFlags() & ELF::SHF_GROUP))
1426      continue;
1427
1428    const MCSymbol *SignatureSymbol = Section.getGroup();
1429    Asm.getOrCreateSymbolData(*SignatureSymbol);
1430    const MCSectionELF *&Group = RevGroupMap[SignatureSymbol];
1431    if (!Group) {
1432      Group = Ctx.CreateELFGroupSection();
1433      MCSectionData &Data = Asm.getOrCreateSectionData(*Group);
1434      Data.setAlignment(4);
1435      MCDataFragment *F = new MCDataFragment(&Data);
1436      write(*F, uint32_t(ELF::GRP_COMDAT));
1437    }
1438    GroupMap[Group] = SignatureSymbol;
1439  }
1440
1441  computeIndexMap(Asm, SectionIndexMap);
1442
1443  // Add sections to the groups
1444  for (MCAssembler::const_iterator it = Asm.begin(), ie = Asm.end();
1445       it != ie; ++it) {
1446    const MCSectionELF &Section =
1447      static_cast<const MCSectionELF&>(it->getSection());
1448    if (!(Section.getFlags() & ELF::SHF_GROUP))
1449      continue;
1450    const MCSectionELF *Group = RevGroupMap[Section.getGroup()];
1451    MCSectionData &Data = Asm.getOrCreateSectionData(*Group);
1452    // FIXME: we could use the previous fragment
1453    MCDataFragment *F = new MCDataFragment(&Data);
1454    uint32_t Index = SectionIndexMap.lookup(&Section);
1455    write(*F, Index);
1456  }
1457}
1458
1459void ELFObjectWriter::writeSection(MCAssembler &Asm,
1460                                   const SectionIndexMapTy &SectionIndexMap,
1461                                   uint32_t GroupSymbolIndex,
1462                                   uint64_t Offset, uint64_t Size,
1463                                   uint64_t Alignment,
1464                                   const MCSectionELF &Section) {
1465  uint64_t sh_link = 0;
1466  uint64_t sh_info = 0;
1467
1468  switch(Section.getType()) {
1469  default:
1470    // Nothing to do.
1471    break;
1472
1473  case ELF::SHT_DYNAMIC:
1474    sh_link = ShStrTabBuilder.getOffset(Section.getSectionName());
1475    break;
1476
1477  case ELF::SHT_REL:
1478  case ELF::SHT_RELA: {
1479    sh_link = SymbolTableIndex;
1480    assert(sh_link && ".symtab not found");
1481    const MCSectionELF *InfoSection = Section.getAssociatedSection();
1482    sh_info = SectionIndexMap.lookup(InfoSection);
1483    break;
1484  }
1485
1486  case ELF::SHT_SYMTAB:
1487  case ELF::SHT_DYNSYM:
1488    sh_link = StringTableIndex;
1489    sh_info = LastLocalSymbolIndex;
1490    break;
1491
1492  case ELF::SHT_SYMTAB_SHNDX:
1493    sh_link = SymbolTableIndex;
1494    break;
1495
1496  case ELF::SHT_GROUP:
1497    sh_link = SymbolTableIndex;
1498    sh_info = GroupSymbolIndex;
1499    break;
1500  }
1501
1502  if (TargetObjectWriter->getEMachine() == ELF::EM_ARM &&
1503      Section.getType() == ELF::SHT_ARM_EXIDX)
1504    sh_link = SectionIndexMap.lookup(Section.getAssociatedSection());
1505
1506  WriteSecHdrEntry(ShStrTabBuilder.getOffset(Section.getSectionName()),
1507                   Section.getType(),
1508                   Section.getFlags(), 0, Offset, Size, sh_link, sh_info,
1509                   Alignment, Section.getEntrySize());
1510}
1511
1512bool ELFObjectWriter::IsELFMetaDataSection(const MCSectionData &SD) {
1513  return SD.getOrdinal() == ~UINT32_C(0) &&
1514    !SD.getSection().isVirtualSection();
1515}
1516
1517uint64_t ELFObjectWriter::DataSectionSize(const MCSectionData &SD) {
1518  uint64_t Ret = 0;
1519  for (MCSectionData::const_iterator i = SD.begin(), e = SD.end(); i != e;
1520       ++i) {
1521    const MCFragment &F = *i;
1522    assert(F.getKind() == MCFragment::FT_Data);
1523    Ret += cast<MCDataFragment>(F).getContents().size();
1524  }
1525  return Ret;
1526}
1527
1528uint64_t ELFObjectWriter::GetSectionAddressSize(const MCAsmLayout &Layout,
1529                                                const MCSectionData &SD) {
1530  if (IsELFMetaDataSection(SD))
1531    return DataSectionSize(SD);
1532  return Layout.getSectionAddressSize(&SD);
1533}
1534
1535void ELFObjectWriter::writeDataSectionData(MCAssembler &Asm,
1536                                           const MCAsmLayout &Layout,
1537                                           const MCSectionData &SD) {
1538  if (IsELFMetaDataSection(SD)) {
1539    for (MCSectionData::const_iterator i = SD.begin(), e = SD.end(); i != e;
1540         ++i) {
1541      const MCFragment &F = *i;
1542      assert(F.getKind() == MCFragment::FT_Data);
1543      WriteBytes(cast<MCDataFragment>(F).getContents());
1544    }
1545  } else {
1546    Asm.writeSectionData(&SD, Layout);
1547  }
1548}
1549
1550void ELFObjectWriter::writeSectionHeader(
1551    ArrayRef<const MCSectionELF *> Sections, MCAssembler &Asm,
1552    const GroupMapTy &GroupMap, const MCAsmLayout &Layout,
1553    const SectionIndexMapTy &SectionIndexMap,
1554    const SectionOffsetMapTy &SectionOffsetMap) {
1555  const unsigned NumSections = Asm.size();
1556
1557  // Null section first.
1558  uint64_t FirstSectionSize =
1559      (NumSections + 1) >= ELF::SHN_LORESERVE ? NumSections + 1 : 0;
1560  uint32_t FirstSectionLink =
1561    ShstrtabIndex >= ELF::SHN_LORESERVE ? ShstrtabIndex : 0;
1562  WriteSecHdrEntry(0, 0, 0, 0, 0, FirstSectionSize, FirstSectionLink, 0, 0, 0);
1563
1564  for (unsigned i = 0; i < NumSections; ++i) {
1565    const MCSectionELF &Section = *Sections[i];
1566    const MCSectionData &SD = Asm.getOrCreateSectionData(Section);
1567    uint32_t GroupSymbolIndex;
1568    if (Section.getType() != ELF::SHT_GROUP)
1569      GroupSymbolIndex = 0;
1570    else
1571      GroupSymbolIndex = getSymbolIndexInSymbolTable(Asm,
1572                                                     GroupMap.lookup(&Section));
1573
1574    uint64_t Size = GetSectionAddressSize(Layout, SD);
1575
1576    writeSection(Asm, SectionIndexMap, GroupSymbolIndex,
1577                 SectionOffsetMap.lookup(&Section), Size, SD.getAlignment(),
1578                 Section);
1579  }
1580}
1581
1582void ELFObjectWriter::WriteObject(MCAssembler &Asm,
1583                                  const MCAsmLayout &Layout) {
1584  GroupMapTy GroupMap;
1585  RevGroupMapTy RevGroupMap;
1586  SectionIndexMapTy SectionIndexMap;
1587
1588  CompressDebugSections(Asm, const_cast<MCAsmLayout &>(Layout));
1589  createIndexedSections(Asm, const_cast<MCAsmLayout &>(Layout), GroupMap,
1590                        RevGroupMap, SectionIndexMap);
1591
1592  // Compute symbol table information.
1593  computeSymbolTable(Asm, Layout, SectionIndexMap, RevGroupMap);
1594
1595  WriteRelocations(Asm, const_cast<MCAsmLayout &>(Layout));
1596
1597  CreateMetadataSections(const_cast<MCAssembler&>(Asm),
1598                         const_cast<MCAsmLayout&>(Layout),
1599                         SectionIndexMap);
1600
1601  unsigned NumSections = Asm.size();
1602  std::vector<const MCSectionELF*> Sections;
1603  Sections.resize(NumSections);
1604
1605  for (auto &Pair : SectionIndexMap)
1606    Sections[Pair.second - 1] = Pair.first;
1607
1608  SectionOffsetMapTy SectionOffsetMap;
1609
1610  // Write out the ELF header ...
1611  WriteHeader(Asm, NumSections + 1);
1612
1613  // ... then the sections ...
1614  for (unsigned i = 0; i < NumSections; ++i) {
1615    const MCSectionELF &Section = *Sections[i];
1616    const MCSectionData &SD = Asm.getOrCreateSectionData(Section);
1617    uint64_t Padding = OffsetToAlignment(OS.tell(), SD.getAlignment());
1618    WriteZeros(Padding);
1619
1620    // Remember the offset into the file for this section.
1621    SectionOffsetMap[&Section] = OS.tell();
1622
1623    writeDataSectionData(Asm, Layout, SD);
1624  }
1625
1626  uint64_t NaturalAlignment = is64Bit() ? 8 : 4;
1627  uint64_t Padding = OffsetToAlignment(OS.tell(), NaturalAlignment);
1628  WriteZeros(Padding);
1629
1630  const unsigned SectionHeaderOffset = OS.tell();
1631
1632  // ... then the section header table ...
1633  writeSectionHeader(Sections, Asm, GroupMap, Layout, SectionIndexMap,
1634                     SectionOffsetMap);
1635
1636  if (is64Bit()) {
1637    uint64_t Val = SectionHeaderOffset;
1638    if (sys::IsLittleEndianHost != IsLittleEndian)
1639      sys::swapByteOrder(Val);
1640    OS.pwrite(reinterpret_cast<char *>(&Val), sizeof(Val),
1641              offsetof(ELF::Elf64_Ehdr, e_shoff));
1642  } else {
1643    uint32_t Val = SectionHeaderOffset;
1644    if (sys::IsLittleEndianHost != IsLittleEndian)
1645      sys::swapByteOrder(Val);
1646    OS.pwrite(reinterpret_cast<char *>(&Val), sizeof(Val),
1647              offsetof(ELF::Elf32_Ehdr, e_shoff));
1648  }
1649}
1650
1651bool ELFObjectWriter::IsSymbolRefDifferenceFullyResolvedImpl(
1652    const MCAssembler &Asm, const MCSymbolData &DataA,
1653    const MCSymbolData *DataB, const MCFragment &FB, bool InSet,
1654    bool IsPCRel) const {
1655  if (!InSet && (::isWeak(DataA) || (DataB && ::isWeak(*DataB))))
1656    return false;
1657  return MCObjectWriter::IsSymbolRefDifferenceFullyResolvedImpl(
1658      Asm, DataA, DataB, FB, InSet, IsPCRel);
1659}
1660
1661bool ELFObjectWriter::isWeak(const MCSymbolData &SD) const {
1662  return ::isWeak(SD);
1663}
1664
1665MCObjectWriter *llvm::createELFObjectWriter(MCELFObjectTargetWriter *MOTW,
1666                                            raw_pwrite_stream &OS,
1667                                            bool IsLittleEndian) {
1668  return new ELFObjectWriter(MOTW, OS, IsLittleEndian);
1669}
1670