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 
40 using namespace lld;
41 using namespace lld::elf;
42 
43 // A resolved relocation. The Sec and Offset fields are set if the relocation
44 // was resolved to an offset within a section.
45 template <class ELFT>
46 struct ResolvedReloc {
47   InputSectionBase<ELFT> *Sec;
48   typename ELFT::uint Offset;
49 };
50 
51 template <class ELFT>
52 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec,
53                                      const typename ELFT::Rel &Rel) {
54   return Target->getImplicitAddend(Sec.getSectionData().begin(),
55                                    Rel.getType(Config->Mips64EL));
56 }
57 
58 template <class ELFT>
59 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec,
60                                      const typename ELFT::Rela &Rel) {
61   return Rel.r_addend;
62 }
63 
64 template <class ELFT, class RelT>
65 static ResolvedReloc<ELFT> resolveReloc(InputSectionBase<ELFT> &Sec,
66                                         RelT &Rel) {
67   SymbolBody &B = Sec.getFile()->getRelocTargetSym(Rel);
68   auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
69   if (!D || !D->Section)
70     return {nullptr, 0};
71   typename ELFT::uint Offset = D->Value;
72   if (D->isSection())
73     Offset += getAddend(Sec, Rel);
74   return {D->Section->Repl, Offset};
75 }
76 
77 template <class ELFT, class Elf_Shdr>
78 static void run(ELFFile<ELFT> &Obj, InputSectionBase<ELFT> &Sec,
79                 Elf_Shdr *RelSec, std::function<void(ResolvedReloc<ELFT>)> Fn) {
80   if (RelSec->sh_type == SHT_RELA) {
81     for (const typename ELFT::Rela &RI : Obj.relas(RelSec))
82       Fn(resolveReloc(Sec, RI));
83   } else {
84     for (const typename ELFT::Rel &RI : Obj.rels(RelSec))
85       Fn(resolveReloc(Sec, RI));
86   }
87 }
88 
89 // Calls Fn for each section that Sec refers to via relocations.
90 template <class ELFT>
91 static void forEachSuccessor(InputSection<ELFT> &Sec,
92                              std::function<void(ResolvedReloc<ELFT>)> Fn) {
93   ELFFile<ELFT> &Obj = Sec.getFile()->getObj();
94   for (const typename ELFT::Shdr *RelSec : Sec.RelocSections)
95     run(Obj, Sec, RelSec, Fn);
96 }
97 
98 template <class ELFT>
99 static void scanEhFrameSection(EhInputSection<ELFT> &EH,
100                                std::function<void(ResolvedReloc<ELFT>)> Fn) {
101   if (!EH.RelocSection)
102     return;
103   ELFFile<ELFT> &EObj = EH.getFile()->getObj();
104   run<ELFT>(EObj, EH, EH.RelocSection, [&](ResolvedReloc<ELFT> R) {
105     if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded)
106       return;
107     if (R.Sec->getSectionHdr()->sh_flags & SHF_EXECINSTR)
108       return;
109     Fn({R.Sec, 0});
110   });
111 }
112 
113 // Sections listed below are special because they are used by the loader
114 // just by being in an ELF file. They should not be garbage-collected.
115 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) {
116   switch (Sec->getSectionHdr()->sh_type) {
117   case SHT_FINI_ARRAY:
118   case SHT_INIT_ARRAY:
119   case SHT_NOTE:
120   case SHT_PREINIT_ARRAY:
121     return true;
122   default:
123     StringRef S = Sec->getSectionName();
124 
125     // We do not want to reclaim sections if they can be referred
126     // by __start_* and __stop_* symbols.
127     if (isValidCIdentifier(S))
128       return true;
129 
130     return S.startswith(".ctors") || S.startswith(".dtors") ||
131            S.startswith(".init") || S.startswith(".fini") ||
132            S.startswith(".jcr");
133   }
134 }
135 
136 // This is the main function of the garbage collector.
137 // Starting from GC-root sections, this function visits all reachable
138 // sections to set their "Live" bits.
139 template <class ELFT> void elf::markLive() {
140   SmallVector<InputSection<ELFT> *, 256> Q;
141 
142   auto Enqueue = [&](ResolvedReloc<ELFT> R) {
143     if (!R.Sec)
144       return;
145 
146     // Usually, a whole section is marked as live or dead, but in mergeable
147     // (splittable) sections, each piece of data has independent liveness bit.
148     // So we explicitly tell it which offset is in use.
149     if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec))
150       MS->markLiveAt(R.Offset);
151 
152     if (R.Sec->Live)
153       return;
154     R.Sec->Live = true;
155     if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
156       Q.push_back(S);
157   };
158 
159   auto MarkSymbol = [&](const SymbolBody *Sym) {
160     if (auto *D = dyn_cast_or_null<DefinedRegular<ELFT>>(Sym))
161       Enqueue({D->Section, D->Value});
162   };
163 
164   // Add GC root symbols.
165   if (Config->EntrySym)
166     MarkSymbol(Config->EntrySym->body());
167   MarkSymbol(Symtab<ELFT>::X->find(Config->Init));
168   MarkSymbol(Symtab<ELFT>::X->find(Config->Fini));
169   for (StringRef S : Config->Undefined)
170     MarkSymbol(Symtab<ELFT>::X->find(S));
171 
172   // Preserve externally-visible symbols if the symbols defined by this
173   // file can interrupt other ELF file's symbols at runtime.
174   for (const Symbol *S : Symtab<ELFT>::X->getSymbols())
175     if (S->includeInDynsym())
176       MarkSymbol(S->body());
177 
178   // Preserve special sections and those which are specified in linker
179   // script KEEP command.
180   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
181        Symtab<ELFT>::X->getObjectFiles())
182     for (InputSectionBase<ELFT> *Sec : F->getSections())
183       if (Sec && Sec != &InputSection<ELFT>::Discarded) {
184         // .eh_frame is always marked as live now, but also it can reference to
185         // sections that contain personality. We preserve all non-text sections
186         // referred by .eh_frame here.
187         if (auto *EH = dyn_cast_or_null<EhInputSection<ELFT>>(Sec))
188           scanEhFrameSection<ELFT>(*EH, Enqueue);
189         if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
190           Enqueue({Sec, 0});
191       }
192 
193   // Mark all reachable sections.
194   while (!Q.empty())
195     forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
196 }
197 
198 template void elf::markLive<ELF32LE>();
199 template void elf::markLive<ELF32BE>();
200 template void elf::markLive<ELF64LE>();
201 template void elf::markLive<ELF64BE>();
202