blob: a64d3f77af5f7b6d57a21581a5b3a10aa97943af [file] [log] [blame]
Rui Ueyamac4aaed92015-10-22 18:49:53 +00001//===- 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
Rui Ueyamaf53b1b72016-01-05 16:35:46 +000019// such sections are not included into output.
Rui Ueyamac4aaed92015-10-22 18:49:53 +000020//
21//===----------------------------------------------------------------------===//
22
23#include "InputSection.h"
George Rimar481c2ce2016-02-23 07:47:54 +000024#include "LinkerScript.h"
Rui Ueyamac4aaed92015-10-22 18:49:53 +000025#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
34using namespace llvm;
35using namespace llvm::ELF;
36using namespace llvm::object;
37
38using namespace lld;
Rafael Espindolae0df00b2016-02-28 00:25:54 +000039using namespace lld::elf;
Rui Ueyamac4aaed92015-10-22 18:49:53 +000040
Rui Ueyamaf53b1b72016-01-05 16:35:46 +000041// Calls Fn for each section that Sec refers to via relocations.
Rui Ueyamac4aaed92015-10-22 18:49:53 +000042template <class ELFT>
Rafael Espindolacaa831d2016-04-22 16:46:08 +000043static void forEachSuccessor(
44 InputSection<ELFT> *Sec,
45 std::function<void(InputSectionBase<ELFT> *, typename ELFT::uint Offset)>
46 Fn) {
Rui Ueyama9328b2c2016-03-14 23:16:09 +000047 typedef typename ELFT::Rel Elf_Rel;
48 typedef typename ELFT::Rela Elf_Rela;
49 typedef typename ELFT::Shdr Elf_Shdr;
Rafael Espindolacaa831d2016-04-22 16:46:08 +000050 typedef typename ELFT::uint uintX_t;
Rui Ueyama12504642015-10-27 21:51:13 +000051
Rafael Espindola197d6a82016-04-22 16:39:59 +000052 ELFFile<ELFT> &Obj = Sec->getFile()->getObj();
Rui Ueyamac4aaed92015-10-22 18:49:53 +000053 for (const Elf_Shdr *RelSec : Sec->RelocSections) {
Rui Ueyama12504642015-10-27 21:51:13 +000054 if (RelSec->sh_type == SHT_RELA) {
Rafael Espindolacaa831d2016-04-22 16:46:08 +000055 for (const Elf_Rela &RI : Obj.relas(RelSec)) {
56 std::pair<InputSectionBase<ELFT> *, uintX_t> P =
57 Sec->getRelocTarget(RI);
58 Fn(P.first, P.second);
59 }
Rui Ueyama12504642015-10-27 21:51:13 +000060 } else {
Rafael Espindolacaa831d2016-04-22 16:46:08 +000061 for (const Elf_Rel &RI : Obj.rels(RelSec)) {
62 std::pair<InputSectionBase<ELFT> *, uintX_t> P =
63 Sec->getRelocTarget(RI);
64 Fn(P.first, P.second);
65 }
Rui Ueyama12504642015-10-27 21:51:13 +000066 }
Rui Ueyamac4aaed92015-10-22 18:49:53 +000067 }
68}
69
70// Sections listed below are special because they are used by the loader
71// just by being in an ELF file. They should not be garbage-collected.
72template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) {
73 switch (Sec->getSectionHdr()->sh_type) {
74 case SHT_FINI_ARRAY:
75 case SHT_INIT_ARRAY:
76 case SHT_NOTE:
77 case SHT_PREINIT_ARRAY:
78 return true;
79 default:
80 StringRef S = Sec->getSectionName();
George Rimar12737b72016-02-25 08:40:26 +000081
82 // We do not want to reclaim sections if they can be referred
83 // by __start_* and __stop_* symbols.
84 if (isValidCIdentifier(S))
85 return true;
86
Davide Italianobcbfedc2015-12-24 09:52:11 +000087 return S.startswith(".ctors") || S.startswith(".dtors") ||
88 S.startswith(".init") || S.startswith(".fini") ||
Rafael Espindola8ea46e02015-11-09 17:44:10 +000089 S.startswith(".jcr");
Rui Ueyamac4aaed92015-10-22 18:49:53 +000090 }
91}
92
Rui Ueyama7924fb82015-12-24 09:50:22 +000093// This is the main function of the garbage collector.
94// Starting from GC-root sections, this function visits all reachable
95// sections to set their "Live" bits.
Rafael Espindolae0df00b2016-02-28 00:25:54 +000096template <class ELFT> void elf::markLive(SymbolTable<ELFT> *Symtab) {
Rafael Espindolacaa831d2016-04-22 16:46:08 +000097 typedef typename ELFT::uint uintX_t;
Rui Ueyama92ce0e92015-11-12 19:42:43 +000098 SmallVector<InputSection<ELFT> *, 256> Q;
Rui Ueyamac4aaed92015-10-22 18:49:53 +000099
Rafael Espindolacaa831d2016-04-22 16:46:08 +0000100 auto Enqueue = [&](InputSectionBase<ELFT> *Sec, uintX_t Offset) {
101 if (!Sec)
102 return;
103 if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(Sec)) {
104 std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
105 MS->getRangeAndSize(Offset);
106 T.first->second = 0;
107 }
108 if (Sec->Live)
Rui Ueyamac4aaed92015-10-22 18:49:53 +0000109 return;
110 Sec->Live = true;
Rui Ueyama92ce0e92015-11-12 19:42:43 +0000111 if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(Sec))
112 Q.push_back(S);
Rui Ueyamac4aaed92015-10-22 18:49:53 +0000113 };
114
115 auto MarkSymbol = [&](SymbolBody *Sym) {
116 if (Sym)
Rafael Espindola38c67a22016-04-15 14:41:56 +0000117 if (auto *D = dyn_cast<DefinedRegular<ELFT>>(Sym))
Rafael Espindolacaa831d2016-04-22 16:46:08 +0000118 Enqueue(D->Section, D->Value);
Rui Ueyamac4aaed92015-10-22 18:49:53 +0000119 };
120
121 // Add GC root symbols.
Rafael Espindola38c67a22016-04-15 14:41:56 +0000122 if (Config->EntrySym)
123 MarkSymbol(Config->EntrySym->Body);
Rui Ueyamac4aaed92015-10-22 18:49:53 +0000124 MarkSymbol(Symtab->find(Config->Init));
125 MarkSymbol(Symtab->find(Config->Fini));
126 for (StringRef S : Config->Undefined)
127 MarkSymbol(Symtab->find(S));
128
129 // Preserve externally-visible symbols if the symbols defined by this
Rui Ueyamaf53b1b72016-01-05 16:35:46 +0000130 // file can interrupt other ELF file's symbols at runtime.
Peter Collingbournedadcc172016-04-22 18:42:48 +0000131 if (Config->Shared || Config->ExportDynamic)
132 for (const Symbol *S : Symtab->getSymbols())
133 if (S->includeInDynsym())
134 MarkSymbol(S->Body);
Rui Ueyamac4aaed92015-10-22 18:49:53 +0000135
George Rimar481c2ce2016-02-23 07:47:54 +0000136 // Preserve special sections and those which are specified in linker
137 // script KEEP command.
Rui Ueyama74f598b2015-12-24 10:14:05 +0000138 for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles())
139 for (InputSectionBase<ELFT> *Sec : F->getSections())
Rafael Espindolaccfe3cb2016-04-04 14:04:16 +0000140 if (Sec && Sec != &InputSection<ELFT>::Discarded)
Rui Ueyama07320e42016-04-20 20:13:41 +0000141 if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
Rafael Espindolacaa831d2016-04-22 16:46:08 +0000142 Enqueue(Sec, 0);
Rui Ueyamac4aaed92015-10-22 18:49:53 +0000143
144 // Mark all reachable sections.
145 while (!Q.empty())
Rui Ueyama92ce0e92015-11-12 19:42:43 +0000146 forEachSuccessor<ELFT>(Q.pop_back_val(), Enqueue);
Rui Ueyamac4aaed92015-10-22 18:49:53 +0000147}
148
Rafael Espindolae0df00b2016-02-28 00:25:54 +0000149template void elf::markLive<ELF32LE>(SymbolTable<ELF32LE> *);
150template void elf::markLive<ELF32BE>(SymbolTable<ELF32BE> *);
151template void elf::markLive<ELF64LE>(SymbolTable<ELF64LE> *);
152template void elf::markLive<ELF64BE>(SymbolTable<ELF64BE> *);