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 "Strings.h" 27 #include "SymbolTable.h" 28 #include "Symbols.h" 29 #include "Target.h" 30 #include "Writer.h" 31 #include "llvm/ADT/STLExtras.h" 32 #include "llvm/Object/ELF.h" 33 #include <functional> 34 #include <vector> 35 36 using namespace llvm; 37 using namespace llvm::ELF; 38 using namespace llvm::object; 39 using namespace llvm::support::endian; 40 41 using namespace lld; 42 using namespace lld::elf; 43 44 namespace { 45 // A resolved relocation. The Sec and Offset fields are set if the relocation 46 // was resolved to an offset within a section. 47 template <class ELFT> struct ResolvedReloc { 48 InputSectionBase<ELFT> *Sec; 49 typename ELFT::uint Offset; 50 }; 51 } // end anonymous namespace 52 53 template <class ELFT> 54 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec, 55 const typename ELFT::Rel &Rel) { 56 return Target->getImplicitAddend(Sec.Data.begin() + Rel.r_offset, 57 Rel.getType(Config->Mips64EL)); 58 } 59 60 template <class ELFT> 61 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec, 62 const typename ELFT::Rela &Rel) { 63 return Rel.r_addend; 64 } 65 66 template <class ELFT, class RelT> 67 static ResolvedReloc<ELFT> resolveReloc(InputSectionBase<ELFT> &Sec, 68 RelT &Rel) { 69 SymbolBody &B = Sec.getFile()->getRelocTargetSym(Rel); 70 auto *D = dyn_cast<DefinedRegular<ELFT>>(&B); 71 if (!D || !D->Section) 72 return {nullptr, 0}; 73 typename ELFT::uint Offset = D->Value; 74 if (D->isSection()) 75 Offset += getAddend(Sec, Rel); 76 return {D->Section->Repl, Offset}; 77 } 78 79 // Calls Fn for each section that Sec refers to via relocations. 80 template <class ELFT> 81 static void forEachSuccessor(InputSection<ELFT> &Sec, 82 std::function<void(ResolvedReloc<ELFT>)> Fn) { 83 if (Sec.AreRelocsRela) { 84 for (const typename ELFT::Rela &Rel : Sec.relas()) 85 Fn(resolveReloc(Sec, Rel)); 86 } else { 87 for (const typename ELFT::Rel &Rel : Sec.rels()) 88 Fn(resolveReloc(Sec, Rel)); 89 } 90 if (Sec.DependentSection) 91 Fn({Sec.DependentSection, 0}); 92 } 93 94 // The .eh_frame section is an unfortunate special case. 95 // The section is divided in CIEs and FDEs and the relocations it can have are 96 // * CIEs can refer to a personality function. 97 // * FDEs can refer to a LSDA 98 // * FDEs refer to the function they contain information about 99 // The last kind of relocation cannot keep the referred section alive, or they 100 // would keep everything alive in a common object file. In fact, each FDE is 101 // alive if the section it refers to is alive. 102 // To keep things simple, in here we just ignore the last relocation kind. The 103 // other two keep the referred section alive. 104 // 105 // A possible improvement would be to fully process .eh_frame in the middle of 106 // the gc pass. With that we would be able to also gc some sections holding 107 // LSDAs and personality functions if we found that they were unused. 108 template <class ELFT, class RelTy> 109 static void 110 scanEhFrameSection(EhInputSection<ELFT> &EH, ArrayRef<RelTy> Rels, 111 std::function<void(ResolvedReloc<ELFT>)> Enqueue) { 112 const endianness E = ELFT::TargetEndianness; 113 for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) { 114 EhSectionPiece &Piece = EH.Pieces[I]; 115 unsigned FirstRelI = Piece.FirstRelocation; 116 if (FirstRelI == (unsigned)-1) 117 continue; 118 if (read32<E>(Piece.data().data() + 4) == 0) { 119 // This is a CIE, we only need to worry about the first relocation. It is 120 // known to point to the personality function. 121 Enqueue(resolveReloc(EH, Rels[FirstRelI])); 122 continue; 123 } 124 // This is a FDE. The relocations point to the described function or to 125 // a LSDA. We only need to keep the LSDA alive, so ignore anything that 126 // points to executable sections. 127 typename ELFT::uint PieceEnd = Piece.InputOff + Piece.size(); 128 for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) { 129 const RelTy &Rel = Rels[I2]; 130 if (Rel.r_offset >= PieceEnd) 131 break; 132 ResolvedReloc<ELFT> R = resolveReloc(EH, Rels[I2]); 133 if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded) 134 continue; 135 if (R.Sec->Flags & SHF_EXECINSTR) 136 continue; 137 Enqueue({R.Sec, 0}); 138 } 139 } 140 } 141 142 template <class ELFT> 143 static void 144 scanEhFrameSection(EhInputSection<ELFT> &EH, 145 std::function<void(ResolvedReloc<ELFT>)> Enqueue) { 146 if (!EH.NumRelocations) 147 return; 148 149 // Unfortunately we need to split .eh_frame early since some relocations in 150 // .eh_frame keep other section alive and some don't. 151 EH.split(); 152 153 if (EH.AreRelocsRela) 154 scanEhFrameSection(EH, EH.relas(), Enqueue); 155 else 156 scanEhFrameSection(EH, EH.rels(), Enqueue); 157 } 158 159 // We do not garbage-collect two types of sections: 160 // 1) Sections used by the loader (.init, .fini, .ctors, .dtors or .jcr) 161 // 2) Non-allocatable sections which typically contain debugging information 162 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) { 163 switch (Sec->Type) { 164 case SHT_FINI_ARRAY: 165 case SHT_INIT_ARRAY: 166 case SHT_NOTE: 167 case SHT_PREINIT_ARRAY: 168 return true; 169 default: 170 if (!(Sec->Flags & SHF_ALLOC)) 171 return true; 172 173 // We do not want to reclaim sections if they can be referred 174 // by __start_* and __stop_* symbols. 175 StringRef S = Sec->Name; 176 if (isValidCIdentifier(S)) 177 return true; 178 179 return S.startswith(".ctors") || S.startswith(".dtors") || 180 S.startswith(".init") || S.startswith(".fini") || 181 S.startswith(".jcr"); 182 } 183 } 184 185 // This is the main function of the garbage collector. 186 // Starting from GC-root sections, this function visits all reachable 187 // sections to set their "Live" bits. 188 template <class ELFT> void elf::markLive() { 189 SmallVector<InputSection<ELFT> *, 256> Q; 190 191 auto Enqueue = [&](ResolvedReloc<ELFT> R) { 192 // Skip over discarded sections. This in theory shouldn't happen, because 193 // the ELF spec doesn't allow a relocation to point to a deduplicated 194 // COMDAT section directly. Unfortunately this happens in practice (e.g. 195 // .eh_frame) so we need to add a check. 196 if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded) 197 return; 198 199 // We don't gc non alloc sections. 200 if (!(R.Sec->Flags & SHF_ALLOC)) 201 return; 202 203 // Usually, a whole section is marked as live or dead, but in mergeable 204 // (splittable) sections, each piece of data has independent liveness bit. 205 // So we explicitly tell it which offset is in use. 206 if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec)) 207 MS->markLiveAt(R.Offset); 208 209 if (R.Sec->Live) 210 return; 211 R.Sec->Live = true; 212 // Add input section to the queue. 213 if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec)) 214 Q.push_back(S); 215 }; 216 217 auto MarkSymbol = [&](const SymbolBody *Sym) { 218 if (auto *D = dyn_cast_or_null<DefinedRegular<ELFT>>(Sym)) 219 Enqueue({D->Section, D->Value}); 220 }; 221 222 // Add GC root symbols. 223 MarkSymbol(Symtab<ELFT>::X->find(Config->Entry)); 224 MarkSymbol(Symtab<ELFT>::X->find(Config->Init)); 225 MarkSymbol(Symtab<ELFT>::X->find(Config->Fini)); 226 for (StringRef S : Config->Undefined) 227 MarkSymbol(Symtab<ELFT>::X->find(S)); 228 229 // Preserve externally-visible symbols if the symbols defined by this 230 // file can interrupt other ELF file's symbols at runtime. 231 for (const Symbol *S : Symtab<ELFT>::X->getSymbols()) 232 if (S->includeInDynsym()) 233 MarkSymbol(S->body()); 234 235 // Preserve special sections and those which are specified in linker 236 // script KEEP command. 237 for (InputSectionBase<ELFT> *Sec : Symtab<ELFT>::X->Sections) { 238 // .eh_frame is always marked as live now, but also it can reference to 239 // sections that contain personality. We preserve all non-text sections 240 // referred by .eh_frame here. 241 if (auto *EH = dyn_cast_or_null<EhInputSection<ELFT>>(Sec)) 242 scanEhFrameSection<ELFT>(*EH, Enqueue); 243 if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec)) 244 Enqueue({Sec, 0}); 245 } 246 247 // Mark all reachable sections. 248 while (!Q.empty()) 249 forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue); 250 } 251 252 template void elf::markLive<ELF32LE>(); 253 template void elf::markLive<ELF32BE>(); 254 template void elf::markLive<ELF64LE>(); 255 template void elf::markLive<ELF64BE>(); 256