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