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 "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 via relocations. 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(".ctors") || S.startswith(".dtors") || 74 S.startswith(".init") || S.startswith(".fini") || 75 S.startswith(".jcr"); 76 } 77 } 78 79 // This is the main function of the garbage collector. 80 // Starting from GC-root sections, this function visits all reachable 81 // sections to set their "Live" bits. 82 template <class ELFT> void elf2::markLive(SymbolTable<ELFT> *Symtab) { 83 SmallVector<InputSection<ELFT> *, 256> Q; 84 85 auto Enqueue = [&](InputSectionBase<ELFT> *Sec) { 86 if (!Sec || Sec->Live) 87 return; 88 Sec->Live = true; 89 if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(Sec)) 90 Q.push_back(S); 91 }; 92 93 auto MarkSymbol = [&](SymbolBody *Sym) { 94 if (Sym) 95 if (auto *D = dyn_cast<DefinedRegular<ELFT>>(Sym->repl())) 96 Enqueue(D->Section); 97 }; 98 99 // Add GC root symbols. 100 MarkSymbol(Config->EntrySym); 101 MarkSymbol(Symtab->find(Config->Init)); 102 MarkSymbol(Symtab->find(Config->Fini)); 103 for (StringRef S : Config->Undefined) 104 MarkSymbol(Symtab->find(S)); 105 106 // Preserve externally-visible symbols if the symbols defined by this 107 // file can interrupt other ELF file's symbols at runtime. 108 if (Config->Shared || Config->ExportDynamic) { 109 for (const std::pair<StringRef, Symbol *> &P : Symtab->getSymbols()) { 110 SymbolBody *B = P.second->Body; 111 if (B->getVisibility() == STV_DEFAULT) 112 MarkSymbol(B); 113 } 114 } 115 116 // Preserve special sections. 117 for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles()) 118 for (InputSectionBase<ELFT> *Sec : F->getSections()) 119 if (Sec && Sec != &InputSection<ELFT>::Discarded) 120 if (isReserved(Sec)) 121 Enqueue(Sec); 122 123 // Mark all reachable sections. 124 while (!Q.empty()) 125 forEachSuccessor<ELFT>(Q.pop_back_val(), Enqueue); 126 } 127 128 template void elf2::markLive<ELF32LE>(SymbolTable<ELF32LE> *); 129 template void elf2::markLive<ELF32BE>(SymbolTable<ELF32BE> *); 130 template void elf2::markLive<ELF64LE>(SymbolTable<ELF64LE> *); 131 template void elf2::markLive<ELF64BE>(SymbolTable<ELF64BE> *); 132