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 template <class ELFT, bool isRela> 41 static void 42 doForEachSuccessor(InputSectionBase<ELFT> *Sec, 43 std::function<void(InputSectionBase<ELFT> *)> Fn, 44 iterator_range<const Elf_Rel_Impl<ELFT, isRela> *> Rels) { 45 typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym; 46 typedef Elf_Rel_Impl<ELFT, isRela> RelType; 47 48 ObjectFile<ELFT> *File = Sec->getFile(); 49 for (const RelType &RI : Rels) { 50 // Global symbol 51 uint32_t SymIndex = RI.getSymbol(Config->Mips64EL); 52 if (SymbolBody *B = File->getSymbolBody(SymIndex)) { 53 if (auto *D = dyn_cast<DefinedRegular<ELFT>>(B->repl())) 54 Fn(&D->Section); 55 continue; 56 } 57 // Local symbol 58 if (const Elf_Sym *Sym = File->getLocalSymbol(SymIndex)) 59 if (InputSectionBase<ELFT> *Sec = File->getSection(*Sym)) 60 Fn(Sec); 61 } 62 } 63 64 // Calls Fn for each section that Sec refers to. 65 template <class ELFT> 66 static void forEachSuccessor(InputSection<ELFT> *Sec, 67 std::function<void(InputSectionBase<ELFT> *)> Fn) { 68 typedef typename ELFFile<ELFT>::Elf_Shdr Elf_Shdr; 69 for (const Elf_Shdr *RelSec : Sec->RelocSections) { 70 if (RelSec->sh_type == SHT_RELA) 71 doForEachSuccessor(Sec, Fn, Sec->getFile()->getObj().relas(RelSec)); 72 else 73 doForEachSuccessor(Sec, Fn, Sec->getFile()->getObj().rels(RelSec)); 74 } 75 } 76 77 // Sections listed below are special because they are used by the loader 78 // just by being in an ELF file. They should not be garbage-collected. 79 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) { 80 switch (Sec->getSectionHdr()->sh_type) { 81 case SHT_FINI_ARRAY: 82 case SHT_INIT_ARRAY: 83 case SHT_NOTE: 84 case SHT_PREINIT_ARRAY: 85 return true; 86 default: 87 StringRef S = Sec->getSectionName(); 88 return S.startswith(".init") || S.startswith(".fini"); 89 } 90 } 91 92 template <class ELFT> void lld::elf2::markLive(SymbolTable<ELFT> *Symtab) { 93 SmallVector<InputSectionBase<ELFT> *, 256> Q; 94 95 auto Enqueue = [&](InputSectionBase<ELFT> *Sec) { 96 if (!Sec || Sec->Live) 97 return; 98 Sec->Live = true; 99 Q.push_back(Sec); 100 }; 101 102 auto MarkSymbol = [&](SymbolBody *Sym) { 103 if (Sym) 104 if (auto *D = dyn_cast_or_null<DefinedRegular<ELFT>>(Sym->repl())) 105 Enqueue(&D->Section); 106 }; 107 108 // Add GC root symbols. 109 MarkSymbol(Config->EntrySym); 110 MarkSymbol(Symtab->find(Config->Init)); 111 MarkSymbol(Symtab->find(Config->Fini)); 112 for (StringRef S : Config->Undefined) 113 MarkSymbol(Symtab->find(S)); 114 115 // Preserve externally-visible symbols if the symbols defined by this 116 // file could override other ELF file's symbols at runtime. 117 if (Config->Shared || Config->ExportDynamic) { 118 for (const std::pair<StringRef, Symbol *> &P : Symtab->getSymbols()) { 119 SymbolBody *B = P.second->Body; 120 if (B->getVisibility() == STV_DEFAULT) 121 MarkSymbol(B); 122 } 123 } 124 125 // Preserve special sections. 126 for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles()) 127 for (InputSectionBase<ELFT> *Sec : F->getSections()) 128 if (Sec && Sec != &InputSection<ELFT>::Discarded) 129 if (isReserved(Sec)) 130 Enqueue(Sec); 131 132 // Mark all reachable sections. 133 while (!Q.empty()) 134 if (auto *Sec = dyn_cast<InputSection<ELFT>>(Q.pop_back_val())) 135 forEachSuccessor<ELFT>(Sec, Enqueue); 136 } 137 138 template void lld::elf2::markLive<ELF32LE>(SymbolTable<ELF32LE> *); 139 template void lld::elf2::markLive<ELF32BE>(SymbolTable<ELF32BE> *); 140 template void lld::elf2::markLive<ELF64LE>(SymbolTable<ELF64LE> *); 141 template void lld::elf2::markLive<ELF64BE>(SymbolTable<ELF64BE> *); 142