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(InputSectionBase<ELFT> *Sec, 65 RelT &Rel) { 66 SymbolBody &B = Sec->getFile()->getRelocTargetSym(Rel); 67 auto *D = dyn_cast<DefinedRegular<ELFT>>(&B); 68 if (!D || !D->Section) 69 return {nullptr, 0}; 70 typename ELFT::uint Offset = D->Value; 71 if (D->isSection()) 72 Offset += getAddend(Sec, Rel); 73 return {D->Section->Repl, Offset}; 74 } 75 76 template <class ELFT, class Elf_Shdr> 77 static void run(ELFFile<ELFT> &Obj, InputSectionBase<ELFT> *Sec, 78 Elf_Shdr *RelSec, std::function<void(ResolvedReloc<ELFT>)> Fn) { 79 if (RelSec->sh_type == SHT_RELA) { 80 for (const typename ELFT::Rela &RI : Obj.relas(RelSec)) 81 Fn(resolveReloc(Sec, RI)); 82 } else { 83 for (const typename ELFT::Rel &RI : Obj.rels(RelSec)) 84 Fn(resolveReloc(Sec, RI)); 85 } 86 } 87 88 // Calls Fn for each section that Sec refers to via relocations. 89 template <class ELFT> 90 static void forEachSuccessor(InputSection<ELFT> *Sec, 91 std::function<void(ResolvedReloc<ELFT>)> Fn) { 92 ELFFile<ELFT> &Obj = Sec->getFile()->getObj(); 93 for (const typename ELFT::Shdr *RelSec : Sec->RelocSections) 94 run(Obj, Sec, RelSec, Fn); 95 } 96 97 template <class ELFT> 98 static void scanEhFrameSection(EhInputSection<ELFT> &EH, 99 std::function<void(ResolvedReloc<ELFT>)> Fn) { 100 if (!EH.RelocSection) 101 return; 102 ELFFile<ELFT> &EObj = EH.getFile()->getObj(); 103 run<ELFT>(EObj, &EH, EH.RelocSection, [&](ResolvedReloc<ELFT> R) { 104 if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded) 105 return; 106 if (R.Sec->getSectionHdr()->sh_flags & SHF_EXECINSTR) 107 return; 108 Fn({R.Sec, 0}); 109 }); 110 } 111 112 // Sections listed below are special because they are used by the loader 113 // just by being in an ELF file. They should not be garbage-collected. 114 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) { 115 switch (Sec->getSectionHdr()->sh_type) { 116 case SHT_FINI_ARRAY: 117 case SHT_INIT_ARRAY: 118 case SHT_NOTE: 119 case SHT_PREINIT_ARRAY: 120 return true; 121 default: 122 StringRef S = Sec->getSectionName(); 123 124 // We do not want to reclaim sections if they can be referred 125 // by __start_* and __stop_* symbols. 126 if (isValidCIdentifier(S)) 127 return true; 128 129 return S.startswith(".ctors") || S.startswith(".dtors") || 130 S.startswith(".init") || S.startswith(".fini") || 131 S.startswith(".jcr"); 132 } 133 } 134 135 // This is the main function of the garbage collector. 136 // Starting from GC-root sections, this function visits all reachable 137 // sections to set their "Live" bits. 138 template <class ELFT> void elf::markLive() { 139 SmallVector<InputSection<ELFT> *, 256> Q; 140 141 auto Enqueue = [&](ResolvedReloc<ELFT> R) { 142 if (!R.Sec) 143 return; 144 145 // Usually, a whole section is marked as live or dead, but in mergeable 146 // (splittable) sections, each piece of data has independent liveness bit. 147 // So we explicitly tell it which offset is in use. 148 if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec)) 149 MS->markLiveAt(R.Offset); 150 151 if (R.Sec->Live) 152 return; 153 R.Sec->Live = true; 154 if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec)) 155 Q.push_back(S); 156 }; 157 158 auto MarkSymbol = [&](const SymbolBody *Sym) { 159 if (auto *D = dyn_cast_or_null<DefinedRegular<ELFT>>(Sym)) 160 Enqueue({D->Section, D->Value}); 161 }; 162 163 // Add GC root symbols. 164 if (Config->EntrySym) 165 MarkSymbol(Config->EntrySym->body()); 166 MarkSymbol(Symtab<ELFT>::X->find(Config->Init)); 167 MarkSymbol(Symtab<ELFT>::X->find(Config->Fini)); 168 for (StringRef S : Config->Undefined) 169 MarkSymbol(Symtab<ELFT>::X->find(S)); 170 171 // Preserve externally-visible symbols if the symbols defined by this 172 // file can interrupt other ELF file's symbols at runtime. 173 for (const Symbol *S : Symtab<ELFT>::X->getSymbols()) 174 if (S->includeInDynsym()) 175 MarkSymbol(S->body()); 176 177 // Preserve special sections and those which are specified in linker 178 // script KEEP command. 179 for (const std::unique_ptr<ObjectFile<ELFT>> &F : 180 Symtab<ELFT>::X->getObjectFiles()) 181 for (InputSectionBase<ELFT> *Sec : F->getSections()) 182 if (Sec && Sec != &InputSection<ELFT>::Discarded) { 183 // .eh_frame is always marked as live now, but also it can reference to 184 // sections that contain personality. We preserve all non-text sections 185 // referred by .eh_frame here. 186 if (auto *EH = dyn_cast_or_null<EhInputSection<ELFT>>(Sec)) 187 scanEhFrameSection<ELFT>(*EH, Enqueue); 188 if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec)) 189 Enqueue({Sec, 0}); 190 } 191 192 // Mark all reachable sections. 193 while (!Q.empty()) 194 forEachSuccessor<ELFT>(Q.pop_back_val(), Enqueue); 195 } 196 197 template void elf::markLive<ELF32LE>(); 198 template void elf::markLive<ELF32BE>(); 199 template void elf::markLive<ELF64LE>(); 200 template void elf::markLive<ELF64BE>(); 201