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