1 //===- MarkLive.cpp -------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements --gc-sections, which is a feature to remove unused 10 // sections from output. Unused sections are sections that are not reachable 11 // from known GC-root symbols or sections. Naturally the feature is 12 // implemented as a mark-sweep garbage collector. 13 // 14 // Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off 15 // by default. Starting with GC-root symbols or sections, markLive function 16 // defined in this file visits all reachable sections to set their Live 17 // bits. Writer will then ignore sections whose Live bits are off, so that 18 // such sections are not included into output. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #include "MarkLive.h" 23 #include "InputSection.h" 24 #include "LinkerScript.h" 25 #include "OutputSections.h" 26 #include "SymbolTable.h" 27 #include "Symbols.h" 28 #include "SyntheticSections.h" 29 #include "Target.h" 30 #include "lld/Common/Memory.h" 31 #include "lld/Common/Strings.h" 32 #include "llvm/ADT/STLExtras.h" 33 #include "llvm/Object/ELF.h" 34 #include <functional> 35 #include <vector> 36 37 using namespace llvm; 38 using namespace llvm::ELF; 39 using namespace llvm::object; 40 41 namespace endian = llvm::support::endian; 42 43 namespace lld { 44 namespace elf { 45 namespace { 46 template <class ELFT> class MarkLive { 47 public: 48 MarkLive(unsigned partition) : partition(partition) {} 49 50 void run(); 51 void moveToMain(); 52 53 private: 54 void enqueue(InputSectionBase *sec, uint64_t offset); 55 void markSymbol(Symbol *sym); 56 void mark(); 57 58 template <class RelTy> 59 void resolveReloc(InputSectionBase &sec, RelTy &rel, bool isLSDA); 60 61 template <class RelTy> 62 void scanEhFrameSection(EhInputSection &eh, ArrayRef<RelTy> rels); 63 64 // The index of the partition that we are currently processing. 65 unsigned partition; 66 67 // A list of sections to visit. 68 SmallVector<InputSection *, 256> queue; 69 70 // There are normally few input sections whose names are valid C 71 // identifiers, so we just store a std::vector instead of a multimap. 72 DenseMap<StringRef, std::vector<InputSectionBase *>> cNamedSections; 73 }; 74 } // namespace 75 76 template <class ELFT> 77 static uint64_t getAddend(InputSectionBase &sec, 78 const typename ELFT::Rel &rel) { 79 return target->getImplicitAddend(sec.data().begin() + rel.r_offset, 80 rel.getType(config->isMips64EL)); 81 } 82 83 template <class ELFT> 84 static uint64_t getAddend(InputSectionBase &sec, 85 const typename ELFT::Rela &rel) { 86 return rel.r_addend; 87 } 88 89 template <class ELFT> 90 template <class RelTy> 91 void MarkLive<ELFT>::resolveReloc(InputSectionBase &sec, RelTy &rel, 92 bool isLSDA) { 93 Symbol &sym = sec.getFile<ELFT>()->getRelocTargetSym(rel); 94 95 // If a symbol is referenced in a live section, it is used. 96 sym.used = true; 97 98 if (auto *d = dyn_cast<Defined>(&sym)) { 99 auto *relSec = dyn_cast_or_null<InputSectionBase>(d->section); 100 if (!relSec) 101 return; 102 103 uint64_t offset = d->value; 104 if (d->isSection()) 105 offset += getAddend<ELFT>(sec, rel); 106 107 if (!isLSDA || !(relSec->flags & SHF_EXECINSTR)) 108 enqueue(relSec, offset); 109 return; 110 } 111 112 if (auto *ss = dyn_cast<SharedSymbol>(&sym)) 113 if (!ss->isWeak()) 114 ss->getFile().isNeeded = true; 115 116 for (InputSectionBase *sec : cNamedSections.lookup(sym.getName())) 117 enqueue(sec, 0); 118 } 119 120 // The .eh_frame section is an unfortunate special case. 121 // The section is divided in CIEs and FDEs and the relocations it can have are 122 // * CIEs can refer to a personality function. 123 // * FDEs can refer to a LSDA 124 // * FDEs refer to the function they contain information about 125 // The last kind of relocation cannot keep the referred section alive, or they 126 // would keep everything alive in a common object file. In fact, each FDE is 127 // alive if the section it refers to is alive. 128 // To keep things simple, in here we just ignore the last relocation kind. The 129 // other two keep the referred section alive. 130 // 131 // A possible improvement would be to fully process .eh_frame in the middle of 132 // the gc pass. With that we would be able to also gc some sections holding 133 // LSDAs and personality functions if we found that they were unused. 134 template <class ELFT> 135 template <class RelTy> 136 void MarkLive<ELFT>::scanEhFrameSection(EhInputSection &eh, 137 ArrayRef<RelTy> rels) { 138 for (size_t i = 0, end = eh.pieces.size(); i < end; ++i) { 139 EhSectionPiece &piece = eh.pieces[i]; 140 size_t firstRelI = piece.firstRelocation; 141 if (firstRelI == (unsigned)-1) 142 continue; 143 144 if (endian::read32<ELFT::TargetEndianness>(piece.data().data() + 4) == 0) { 145 // This is a CIE, we only need to worry about the first relocation. It is 146 // known to point to the personality function. 147 resolveReloc(eh, rels[firstRelI], false); 148 continue; 149 } 150 151 // This is a FDE. The relocations point to the described function or to 152 // a LSDA. We only need to keep the LSDA alive, so ignore anything that 153 // points to executable sections. 154 uint64_t pieceEnd = piece.inputOff + piece.size; 155 for (size_t j = firstRelI, end2 = rels.size(); j < end2; ++j) 156 if (rels[j].r_offset < pieceEnd) 157 resolveReloc(eh, rels[j], true); 158 } 159 } 160 161 // Some sections are used directly by the loader, so they should never be 162 // garbage-collected. This function returns true if a given section is such 163 // section. 164 static bool isReserved(InputSectionBase *sec) { 165 switch (sec->type) { 166 case SHT_FINI_ARRAY: 167 case SHT_INIT_ARRAY: 168 case SHT_NOTE: 169 case SHT_PREINIT_ARRAY: 170 return true; 171 default: 172 StringRef s = sec->name; 173 return s.startswith(".ctors") || s.startswith(".dtors") || 174 s.startswith(".init") || s.startswith(".fini") || 175 s.startswith(".jcr"); 176 } 177 } 178 179 template <class ELFT> 180 void MarkLive<ELFT>::enqueue(InputSectionBase *sec, uint64_t offset) { 181 // Skip over discarded sections. This in theory shouldn't happen, because 182 // the ELF spec doesn't allow a relocation to point to a deduplicated 183 // COMDAT section directly. Unfortunately this happens in practice (e.g. 184 // .eh_frame) so we need to add a check. 185 if (sec == &InputSection::discarded) 186 return; 187 188 // Usually, a whole section is marked as live or dead, but in mergeable 189 // (splittable) sections, each piece of data has independent liveness bit. 190 // So we explicitly tell it which offset is in use. 191 if (auto *ms = dyn_cast<MergeInputSection>(sec)) 192 ms->getSectionPiece(offset)->live = true; 193 194 // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and 195 // Sec->Partition in the following lattice: 1 < other < 0. If Sec->Partition 196 // doesn't change, we don't need to do anything. 197 if (sec->partition == 1 || sec->partition == partition) 198 return; 199 sec->partition = sec->partition ? 1 : partition; 200 201 // Add input section to the queue. 202 if (InputSection *s = dyn_cast<InputSection>(sec)) 203 queue.push_back(s); 204 } 205 206 template <class ELFT> void MarkLive<ELFT>::markSymbol(Symbol *sym) { 207 if (auto *d = dyn_cast_or_null<Defined>(sym)) 208 if (auto *isec = dyn_cast_or_null<InputSectionBase>(d->section)) 209 enqueue(isec, d->value); 210 } 211 212 // This is the main function of the garbage collector. 213 // Starting from GC-root sections, this function visits all reachable 214 // sections to set their "Live" bits. 215 template <class ELFT> void MarkLive<ELFT>::run() { 216 // Add GC root symbols. 217 218 // Preserve externally-visible symbols if the symbols defined by this 219 // file can interrupt other ELF file's symbols at runtime. 220 symtab->forEachSymbol([&](Symbol *sym) { 221 if (sym->includeInDynsym() && sym->partition == partition) 222 markSymbol(sym); 223 }); 224 225 // If this isn't the main partition, that's all that we need to preserve. 226 if (partition != 1) { 227 mark(); 228 return; 229 } 230 231 markSymbol(symtab->find(config->entry)); 232 markSymbol(symtab->find(config->init)); 233 markSymbol(symtab->find(config->fini)); 234 for (StringRef s : config->undefined) 235 markSymbol(symtab->find(s)); 236 for (StringRef s : script->referencedSymbols) 237 markSymbol(symtab->find(s)); 238 239 // Preserve special sections and those which are specified in linker 240 // script KEEP command. 241 for (InputSectionBase *sec : inputSections) { 242 // Mark .eh_frame sections as live because there are usually no relocations 243 // that point to .eh_frames. Otherwise, the garbage collector would drop 244 // all of them. We also want to preserve personality routines and LSDA 245 // referenced by .eh_frame sections, so we scan them for that here. 246 if (auto *eh = dyn_cast<EhInputSection>(sec)) { 247 eh->markLive(); 248 if (!eh->numRelocations) 249 continue; 250 251 if (eh->areRelocsRela) 252 scanEhFrameSection(*eh, eh->template relas<ELFT>()); 253 else 254 scanEhFrameSection(*eh, eh->template rels<ELFT>()); 255 } 256 257 if (sec->flags & SHF_LINK_ORDER) 258 continue; 259 260 if (isReserved(sec) || script->shouldKeep(sec)) { 261 enqueue(sec, 0); 262 } else if (isValidCIdentifier(sec->name)) { 263 cNamedSections[saver.save("__start_" + sec->name)].push_back(sec); 264 cNamedSections[saver.save("__stop_" + sec->name)].push_back(sec); 265 } 266 } 267 268 mark(); 269 } 270 271 template <class ELFT> void MarkLive<ELFT>::mark() { 272 // Mark all reachable sections. 273 while (!queue.empty()) { 274 InputSectionBase &sec = *queue.pop_back_val(); 275 276 if (sec.areRelocsRela) { 277 for (const typename ELFT::Rela &rel : sec.template relas<ELFT>()) 278 resolveReloc(sec, rel, false); 279 } else { 280 for (const typename ELFT::Rel &rel : sec.template rels<ELFT>()) 281 resolveReloc(sec, rel, false); 282 } 283 284 for (InputSectionBase *isec : sec.dependentSections) 285 enqueue(isec, 0); 286 } 287 } 288 289 // Move the sections for some symbols to the main partition, specifically ifuncs 290 // (because they can result in an IRELATIVE being added to the main partition's 291 // GOT, which means that the ifunc must be available when the main partition is 292 // loaded) and TLS symbols (because we only know how to correctly process TLS 293 // relocations for the main partition). 294 // 295 // We also need to move sections whose names are C identifiers that are referred 296 // to from __start_/__stop_ symbols because there will only be one set of 297 // symbols for the whole program. 298 template <class ELFT> void MarkLive<ELFT>::moveToMain() { 299 for (InputFile *file : objectFiles) 300 for (Symbol *s : file->getSymbols()) 301 if (auto *d = dyn_cast<Defined>(s)) 302 if ((d->type == STT_GNU_IFUNC || d->type == STT_TLS) && d->section && 303 d->section->isLive()) 304 markSymbol(s); 305 306 for (InputSectionBase *sec : inputSections) { 307 if (!sec->isLive() || !isValidCIdentifier(sec->name)) 308 continue; 309 if (symtab->find(("__start_" + sec->name).str()) || 310 symtab->find(("__stop_" + sec->name).str())) 311 enqueue(sec, 0); 312 } 313 314 mark(); 315 } 316 317 // Before calling this function, Live bits are off for all 318 // input sections. This function make some or all of them on 319 // so that they are emitted to the output file. 320 template <class ELFT> void markLive() { 321 // If -gc-sections is not given, no sections are removed. 322 if (!config->gcSections) { 323 for (InputSectionBase *sec : inputSections) 324 sec->markLive(); 325 326 // If a DSO defines a symbol referenced in a regular object, it is needed. 327 symtab->forEachSymbol([](Symbol *sym) { 328 if (auto *s = dyn_cast<SharedSymbol>(sym)) 329 if (s->isUsedInRegularObj && !s->isWeak()) 330 s->getFile().isNeeded = true; 331 }); 332 return; 333 } 334 335 // Otheriwse, do mark-sweep GC. 336 // 337 // The -gc-sections option works only for SHF_ALLOC sections 338 // (sections that are memory-mapped at runtime). So we can 339 // unconditionally make non-SHF_ALLOC sections alive except 340 // SHF_LINK_ORDER and SHT_REL/SHT_RELA sections. 341 // 342 // Usually, non-SHF_ALLOC sections are not removed even if they are 343 // unreachable through relocations because reachability is not 344 // a good signal whether they are garbage or not (e.g. there is 345 // usually no section referring to a .comment section, but we 346 // want to keep it.). 347 // 348 // Note on SHF_LINK_ORDER: Such sections contain metadata and they 349 // have a reverse dependency on the InputSection they are linked with. 350 // We are able to garbage collect them. 351 // 352 // Note on SHF_REL{,A}: Such sections reach here only when -r 353 // or -emit-reloc were given. And they are subject of garbage 354 // collection because, if we remove a text section, we also 355 // remove its relocation section. 356 for (InputSectionBase *sec : inputSections) { 357 bool isAlloc = (sec->flags & SHF_ALLOC); 358 bool isLinkOrder = (sec->flags & SHF_LINK_ORDER); 359 bool isRel = (sec->type == SHT_REL || sec->type == SHT_RELA); 360 361 if (!isAlloc && !isLinkOrder && !isRel) 362 sec->markLive(); 363 } 364 365 // Follow the graph to mark all live sections. 366 for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart) 367 MarkLive<ELFT>(curPart).run(); 368 369 // If we have multiple partitions, some sections need to live in the main 370 // partition even if they were allocated to a loadable partition. Move them 371 // there now. 372 if (partitions.size() != 1) 373 MarkLive<ELFT>(1).moveToMain(); 374 375 // Report garbage-collected sections. 376 if (config->printGcSections) 377 for (InputSectionBase *sec : inputSections) 378 if (!sec->isLive()) 379 message("removing unused section " + toString(sec)); 380 } 381 382 template void markLive<ELF32LE>(); 383 template void markLive<ELF32BE>(); 384 template void markLive<ELF64LE>(); 385 template void markLive<ELF64BE>(); 386 387 } // namespace elf 388 } // namespace lld 389