MarkLive.cpp revision 360784
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 37using namespace llvm; 38using namespace llvm::ELF; 39using namespace llvm::object; 40 41namespace endian = llvm::support::endian; 42 43namespace lld { 44namespace elf { 45namespace { 46template <class ELFT> class MarkLive { 47public: 48 MarkLive(unsigned partition) : partition(partition) {} 49 50 void run(); 51 void moveToMain(); 52 53private: 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 76template <class ELFT> 77static 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 83template <class ELFT> 84static uint64_t getAddend(InputSectionBase &sec, 85 const typename ELFT::Rela &rel) { 86 return rel.r_addend; 87} 88 89template <class ELFT> 90template <class RelTy> 91void 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. 134template <class ELFT> 135template <class RelTy> 136void 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. 164static bool isReserved(InputSectionBase *sec) { 165 switch (sec->type) { 166 case SHT_FINI_ARRAY: 167 case SHT_INIT_ARRAY: 168 case SHT_PREINIT_ARRAY: 169 return true; 170 case SHT_NOTE: 171 // SHT_NOTE sections in a group are subject to garbage collection. 172 return !sec->nextInSectionGroup; 173 default: 174 StringRef s = sec->name; 175 return s.startswith(".ctors") || s.startswith(".dtors") || 176 s.startswith(".init") || s.startswith(".fini") || 177 s.startswith(".jcr"); 178 } 179} 180 181template <class ELFT> 182void MarkLive<ELFT>::enqueue(InputSectionBase *sec, uint64_t offset) { 183 // Skip over discarded sections. This in theory shouldn't happen, because 184 // the ELF spec doesn't allow a relocation to point to a deduplicated 185 // COMDAT section directly. Unfortunately this happens in practice (e.g. 186 // .eh_frame) so we need to add a check. 187 if (sec == &InputSection::discarded) 188 return; 189 190 // Usually, a whole section is marked as live or dead, but in mergeable 191 // (splittable) sections, each piece of data has independent liveness bit. 192 // So we explicitly tell it which offset is in use. 193 if (auto *ms = dyn_cast<MergeInputSection>(sec)) 194 ms->getSectionPiece(offset)->live = true; 195 196 // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and 197 // Sec->Partition in the following lattice: 1 < other < 0. If Sec->Partition 198 // doesn't change, we don't need to do anything. 199 if (sec->partition == 1 || sec->partition == partition) 200 return; 201 sec->partition = sec->partition ? 1 : partition; 202 203 // Add input section to the queue. 204 if (InputSection *s = dyn_cast<InputSection>(sec)) 205 queue.push_back(s); 206} 207 208template <class ELFT> void MarkLive<ELFT>::markSymbol(Symbol *sym) { 209 if (auto *d = dyn_cast_or_null<Defined>(sym)) 210 if (auto *isec = dyn_cast_or_null<InputSectionBase>(d->section)) 211 enqueue(isec, d->value); 212} 213 214// This is the main function of the garbage collector. 215// Starting from GC-root sections, this function visits all reachable 216// sections to set their "Live" bits. 217template <class ELFT> void MarkLive<ELFT>::run() { 218 // Add GC root symbols. 219 220 // Preserve externally-visible symbols if the symbols defined by this 221 // file can interrupt other ELF file's symbols at runtime. 222 for (Symbol *sym : symtab->symbols()) 223 if (sym->includeInDynsym() && sym->partition == partition) 224 markSymbol(sym); 225 226 // If this isn't the main partition, that's all that we need to preserve. 227 if (partition != 1) { 228 mark(); 229 return; 230 } 231 232 markSymbol(symtab->find(config->entry)); 233 markSymbol(symtab->find(config->init)); 234 markSymbol(symtab->find(config->fini)); 235 for (StringRef s : config->undefined) 236 markSymbol(symtab->find(s)); 237 for (StringRef s : script->referencedSymbols) 238 markSymbol(symtab->find(s)); 239 240 // Preserve special sections and those which are specified in linker 241 // script KEEP command. 242 for (InputSectionBase *sec : inputSections) { 243 // Mark .eh_frame sections as live because there are usually no relocations 244 // that point to .eh_frames. Otherwise, the garbage collector would drop 245 // all of them. We also want to preserve personality routines and LSDA 246 // referenced by .eh_frame sections, so we scan them for that here. 247 if (auto *eh = dyn_cast<EhInputSection>(sec)) { 248 eh->markLive(); 249 if (!eh->numRelocations) 250 continue; 251 252 if (eh->areRelocsRela) 253 scanEhFrameSection(*eh, eh->template relas<ELFT>()); 254 else 255 scanEhFrameSection(*eh, eh->template rels<ELFT>()); 256 } 257 258 if (sec->flags & SHF_LINK_ORDER) 259 continue; 260 261 if (isReserved(sec) || script->shouldKeep(sec)) { 262 enqueue(sec, 0); 263 } else if (isValidCIdentifier(sec->name)) { 264 cNamedSections[saver.save("__start_" + sec->name)].push_back(sec); 265 cNamedSections[saver.save("__stop_" + sec->name)].push_back(sec); 266 } 267 } 268 269 mark(); 270} 271 272template <class ELFT> void MarkLive<ELFT>::mark() { 273 // Mark all reachable sections. 274 while (!queue.empty()) { 275 InputSectionBase &sec = *queue.pop_back_val(); 276 277 if (sec.areRelocsRela) { 278 for (const typename ELFT::Rela &rel : sec.template relas<ELFT>()) 279 resolveReloc(sec, rel, false); 280 } else { 281 for (const typename ELFT::Rel &rel : sec.template rels<ELFT>()) 282 resolveReloc(sec, rel, false); 283 } 284 285 for (InputSectionBase *isec : sec.dependentSections) 286 enqueue(isec, 0); 287 288 // Mark the next group member. 289 if (sec.nextInSectionGroup) 290 enqueue(sec.nextInSectionGroup, 0); 291 } 292} 293 294// Move the sections for some symbols to the main partition, specifically ifuncs 295// (because they can result in an IRELATIVE being added to the main partition's 296// GOT, which means that the ifunc must be available when the main partition is 297// loaded) and TLS symbols (because we only know how to correctly process TLS 298// relocations for the main partition). 299// 300// We also need to move sections whose names are C identifiers that are referred 301// to from __start_/__stop_ symbols because there will only be one set of 302// symbols for the whole program. 303template <class ELFT> void MarkLive<ELFT>::moveToMain() { 304 for (InputFile *file : objectFiles) 305 for (Symbol *s : file->getSymbols()) 306 if (auto *d = dyn_cast<Defined>(s)) 307 if ((d->type == STT_GNU_IFUNC || d->type == STT_TLS) && d->section && 308 d->section->isLive()) 309 markSymbol(s); 310 311 for (InputSectionBase *sec : inputSections) { 312 if (!sec->isLive() || !isValidCIdentifier(sec->name)) 313 continue; 314 if (symtab->find(("__start_" + sec->name).str()) || 315 symtab->find(("__stop_" + sec->name).str())) 316 enqueue(sec, 0); 317 } 318 319 mark(); 320} 321 322// Before calling this function, Live bits are off for all 323// input sections. This function make some or all of them on 324// so that they are emitted to the output file. 325template <class ELFT> void markLive() { 326 // If -gc-sections is not given, no sections are removed. 327 if (!config->gcSections) { 328 for (InputSectionBase *sec : inputSections) 329 sec->markLive(); 330 331 // If a DSO defines a symbol referenced in a regular object, it is needed. 332 for (Symbol *sym : symtab->symbols()) 333 if (auto *s = dyn_cast<SharedSymbol>(sym)) 334 if (s->isUsedInRegularObj && !s->isWeak()) 335 s->getFile().isNeeded = true; 336 return; 337 } 338 339 // Otherwise, do mark-sweep GC. 340 // 341 // The -gc-sections option works only for SHF_ALLOC sections 342 // (sections that are memory-mapped at runtime). So we can 343 // unconditionally make non-SHF_ALLOC sections alive except 344 // SHF_LINK_ORDER and SHT_REL/SHT_RELA sections. 345 // 346 // Usually, non-SHF_ALLOC sections are not removed even if they are 347 // unreachable through relocations because reachability is not 348 // a good signal whether they are garbage or not (e.g. there is 349 // usually no section referring to a .comment section, but we 350 // want to keep it.). 351 // 352 // Note on SHF_LINK_ORDER: Such sections contain metadata and they 353 // have a reverse dependency on the InputSection they are linked with. 354 // We are able to garbage collect them. 355 // 356 // Note on SHF_REL{,A}: Such sections reach here only when -r 357 // or -emit-reloc were given. And they are subject of garbage 358 // collection because, if we remove a text section, we also 359 // remove its relocation section. 360 // 361 // Note on nextInSectionGroup: The ELF spec says that group sections are 362 // included or omitted as a unit. We take the interpretation that: 363 // 364 // - Group members (nextInSectionGroup != nullptr) are subject to garbage 365 // collection. 366 // - Groups members are retained or discarded as a unit. 367 for (InputSectionBase *sec : inputSections) { 368 bool isAlloc = (sec->flags & SHF_ALLOC); 369 bool isLinkOrder = (sec->flags & SHF_LINK_ORDER); 370 bool isRel = (sec->type == SHT_REL || sec->type == SHT_RELA); 371 372 if (!isAlloc && !isLinkOrder && !isRel && !sec->nextInSectionGroup) 373 sec->markLive(); 374 } 375 376 // Follow the graph to mark all live sections. 377 for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart) 378 MarkLive<ELFT>(curPart).run(); 379 380 // If we have multiple partitions, some sections need to live in the main 381 // partition even if they were allocated to a loadable partition. Move them 382 // there now. 383 if (partitions.size() != 1) 384 MarkLive<ELFT>(1).moveToMain(); 385 386 // Report garbage-collected sections. 387 if (config->printGcSections) 388 for (InputSectionBase *sec : inputSections) 389 if (!sec->isLive()) 390 message("removing unused section " + toString(sec)); 391} 392 393template void markLive<ELF32LE>(); 394template void markLive<ELF32BE>(); 395template void markLive<ELF64LE>(); 396template void markLive<ELF64BE>(); 397 398} // namespace elf 399} // namespace lld 400