1 //===- MarkLive.cpp -------------------------------------------------------===// 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 // This file implements --gc-sections, which is a feature to remove unused 11 // sections from output. Unused sections are sections that are not reachable 12 // from known GC-root symbols or sections. Naturally the feature is 13 // implemented as a mark-sweep garbage collector. 14 // 15 // Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off 16 // by default. Starting with GC-root symbols or sections, markLive function 17 // defined in this file visits all reachable sections to set their Live 18 // bits. Writer will then ignore sections whose Live bits are off, so that 19 // such sections are not included into output. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "InputSection.h" 24 #include "LinkerScript.h" 25 #include "OutputSections.h" 26 #include "SymbolTable.h" 27 #include "Symbols.h" 28 #include "Target.h" 29 #include "Writer.h" 30 #include "llvm/ADT/STLExtras.h" 31 #include "llvm/Object/ELF.h" 32 #include <functional> 33 #include <vector> 34 35 using namespace llvm; 36 using namespace llvm::ELF; 37 using namespace llvm::object; 38 39 using namespace lld; 40 using namespace lld::elf; 41 42 // A resolved relocation. The Sec and Offset fields are set if the relocation 43 // was resolved to an offset within a section. 44 template <class ELFT> 45 struct ResolvedReloc { 46 InputSectionBase<ELFT> *Sec; 47 typename ELFT::uint Offset; 48 }; 49 50 template <class ELFT> 51 static typename ELFT::uint getAddend(InputSectionBase<ELFT> *Sec, 52 const typename ELFT::Rel &Rel) { 53 return Target->getImplicitAddend(Sec->getSectionData().begin(), 54 Rel.getType(Config->Mips64EL)); 55 } 56 57 template <class ELFT> 58 static typename ELFT::uint getAddend(InputSectionBase<ELFT> *Sec, 59 const typename ELFT::Rela &Rel) { 60 return Rel.r_addend; 61 } 62 63 template <class ELFT, class RelT> 64 static ResolvedReloc<ELFT> resolveReloc(InputSection<ELFT> *Sec, RelT &Rel) { 65 SymbolBody &B = Sec->getFile()->getRelocTargetSym(Rel); 66 auto *D = dyn_cast<DefinedRegular<ELFT>>(&B); 67 if (!D || !D->Section) 68 return {nullptr, 0}; 69 typename ELFT::uint Offset = D->Value; 70 if (D->isSection()) 71 Offset += getAddend(Sec, Rel); 72 return {D->Section->Repl, Offset}; 73 } 74 75 // Calls Fn for each section that Sec refers to via relocations. 76 template <class ELFT> 77 static void forEachSuccessor(InputSection<ELFT> *Sec, 78 std::function<void(ResolvedReloc<ELFT>)> Fn) { 79 typedef typename ELFT::Rel Elf_Rel; 80 typedef typename ELFT::Rela Elf_Rela; 81 typedef typename ELFT::Shdr Elf_Shdr; 82 83 ELFFile<ELFT> &Obj = Sec->getFile()->getObj(); 84 for (const Elf_Shdr *RelSec : Sec->RelocSections) { 85 if (RelSec->sh_type == SHT_RELA) { 86 for (const Elf_Rela &RI : Obj.relas(RelSec)) 87 Fn(resolveReloc(Sec, RI)); 88 } else { 89 for (const Elf_Rel &RI : Obj.rels(RelSec)) 90 Fn(resolveReloc(Sec, RI)); 91 } 92 } 93 } 94 95 // Sections listed below are special because they are used by the loader 96 // just by being in an ELF file. They should not be garbage-collected. 97 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) { 98 switch (Sec->getSectionHdr()->sh_type) { 99 case SHT_FINI_ARRAY: 100 case SHT_INIT_ARRAY: 101 case SHT_NOTE: 102 case SHT_PREINIT_ARRAY: 103 return true; 104 default: 105 StringRef S = Sec->getSectionName(); 106 107 // We do not want to reclaim sections if they can be referred 108 // by __start_* and __stop_* symbols. 109 if (isValidCIdentifier(S)) 110 return true; 111 112 return S.startswith(".ctors") || S.startswith(".dtors") || 113 S.startswith(".init") || S.startswith(".fini") || 114 S.startswith(".jcr"); 115 } 116 } 117 118 // This is the main function of the garbage collector. 119 // Starting from GC-root sections, this function visits all reachable 120 // sections to set their "Live" bits. 121 template <class ELFT> void elf::markLive(SymbolTable<ELFT> *Symtab) { 122 typedef typename ELFT::uint uintX_t; 123 SmallVector<InputSection<ELFT> *, 256> Q; 124 125 auto Enqueue = [&](ResolvedReloc<ELFT> R) { 126 if (!R.Sec) 127 return; 128 if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec)) { 129 std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T = 130 MS->getRangeAndSize(R.Offset); 131 T.first->second = 0; 132 } 133 if (R.Sec->Live) 134 return; 135 R.Sec->Live = true; 136 if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec)) 137 Q.push_back(S); 138 }; 139 140 auto MarkSymbol = [&](SymbolBody *Sym) { 141 if (Sym) 142 if (auto *D = dyn_cast<DefinedRegular<ELFT>>(Sym)) 143 Enqueue({D->Section, D->Value}); 144 }; 145 146 // Add GC root symbols. 147 if (Config->EntrySym) 148 MarkSymbol(Config->EntrySym->Body); 149 MarkSymbol(Symtab->find(Config->Init)); 150 MarkSymbol(Symtab->find(Config->Fini)); 151 for (StringRef S : Config->Undefined) 152 MarkSymbol(Symtab->find(S)); 153 154 // Preserve externally-visible symbols if the symbols defined by this 155 // file can interrupt other ELF file's symbols at runtime. 156 for (const Symbol *S : Symtab->getSymbols()) 157 if (S->includeInDynsym()) 158 MarkSymbol(S->Body); 159 160 // Preserve special sections and those which are specified in linker 161 // script KEEP command. 162 for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles()) 163 for (InputSectionBase<ELFT> *Sec : F->getSections()) 164 if (Sec && Sec != &InputSection<ELFT>::Discarded) 165 if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec)) 166 Enqueue({Sec, 0}); 167 168 // Mark all reachable sections. 169 while (!Q.empty()) 170 forEachSuccessor<ELFT>(Q.pop_back_val(), Enqueue); 171 } 172 173 template void elf::markLive<ELF32LE>(SymbolTable<ELF32LE> *); 174 template void elf::markLive<ELF32BE>(SymbolTable<ELF32BE> *); 175 template void elf::markLive<ELF64LE>(SymbolTable<ELF64LE> *); 176 template void elf::markLive<ELF64BE>(SymbolTable<ELF64BE> *); 177