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 removed from output. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "InputSection.h" 24 #include "OutputSections.h" 25 #include "SymbolTable.h" 26 #include "Symbols.h" 27 #include "Writer.h" 28 #include "llvm/ADT/STLExtras.h" 29 #include "llvm/Object/ELF.h" 30 #include <functional> 31 #include <vector> 32 33 using namespace llvm; 34 using namespace llvm::ELF; 35 using namespace llvm::object; 36 37 using namespace lld; 38 using namespace lld::elf2; 39 40 // Calls Fn for each section that Sec refers to. 41 template <class ELFT> 42 static void forEachSuccessor(InputSection<ELFT> *Sec, 43 std::function<void(InputSectionBase<ELFT> *)> Fn) { 44 typedef typename ELFFile<ELFT>::Elf_Rel Elf_Rel; 45 typedef typename ELFFile<ELFT>::Elf_Rela Elf_Rela; 46 typedef typename ELFFile<ELFT>::Elf_Shdr Elf_Shdr; 47 48 ELFFile<ELFT> &Obj = Sec->getFile()->getObj(); 49 for (const Elf_Shdr *RelSec : Sec->RelocSections) { 50 if (RelSec->sh_type == SHT_RELA) { 51 for (const Elf_Rela &RI : Obj.relas(RelSec)) 52 if (InputSectionBase<ELFT> *Succ = Sec->getRelocTarget(RI)) 53 Fn(Succ); 54 } else { 55 for (const Elf_Rel &RI : Obj.rels(RelSec)) 56 if (InputSectionBase<ELFT> *Succ = Sec->getRelocTarget(RI)) 57 Fn(Succ); 58 } 59 } 60 } 61 62 // Sections listed below are special because they are used by the loader 63 // just by being in an ELF file. They should not be garbage-collected. 64 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) { 65 switch (Sec->getSectionHdr()->sh_type) { 66 case SHT_FINI_ARRAY: 67 case SHT_INIT_ARRAY: 68 case SHT_NOTE: 69 case SHT_PREINIT_ARRAY: 70 return true; 71 default: 72 StringRef S = Sec->getSectionName(); 73 return S.startswith(".init") || S.startswith(".fini") || 74 S.startswith(".jcr"); 75 } 76 } 77 78 template <class ELFT> void lld::elf2::markLive(SymbolTable<ELFT> *Symtab) { 79 SmallVector<InputSection<ELFT> *, 256> Q; 80 81 auto Enqueue = [&](InputSectionBase<ELFT> *Sec) { 82 if (!Sec || Sec->Live) 83 return; 84 Sec->Live = true; 85 if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(Sec)) 86 Q.push_back(S); 87 }; 88 89 auto MarkSymbol = [&](SymbolBody *Sym) { 90 if (Sym) 91 if (auto *D = dyn_cast<DefinedRegular<ELFT>>(Sym->repl())) 92 Enqueue(&D->Section); 93 }; 94 95 // Add GC root symbols. 96 MarkSymbol(Config->EntrySym); 97 MarkSymbol(Symtab->find(Config->Init)); 98 MarkSymbol(Symtab->find(Config->Fini)); 99 for (StringRef S : Config->Undefined) 100 MarkSymbol(Symtab->find(S)); 101 102 // Preserve externally-visible symbols if the symbols defined by this 103 // file could override other ELF file's symbols at runtime. 104 if (Config->Shared || Config->ExportDynamic) { 105 for (const std::pair<StringRef, Symbol *> &P : Symtab->getSymbols()) { 106 SymbolBody *B = P.second->Body; 107 if (B->getVisibility() == STV_DEFAULT) 108 MarkSymbol(B); 109 } 110 } 111 112 // Preserve special sections. 113 for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles()) { 114 for (InputSectionBase<ELFT> *Sec : F->getSections()) { 115 if (!Sec || Sec == &InputSection<ELFT>::Discarded) 116 continue; 117 if (isReserved(Sec)) 118 Enqueue(Sec); 119 else if (Sec->getSectionName() == ".eh_frame") 120 // .eh_frame is special. It should be marked live so that we don't 121 // drop it, but it should not keep any section alive. 122 Sec->Live = true; 123 } 124 } 125 126 // Mark all reachable sections. 127 while (!Q.empty()) 128 forEachSuccessor<ELFT>(Q.pop_back_val(), Enqueue); 129 } 130 131 template void lld::elf2::markLive<ELF32LE>(SymbolTable<ELF32LE> *); 132 template void lld::elf2::markLive<ELF32BE>(SymbolTable<ELF32BE> *); 133 template void lld::elf2::markLive<ELF64LE>(SymbolTable<ELF64LE> *); 134 template void lld::elf2::markLive<ELF64BE>(SymbolTable<ELF64BE> *); 135