1 //===- LinkerScript.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 contains the parser/evaluator of the linker script.
11 // It does not construct an AST but consume linker script directives directly.
12 // Results are written to Driver or Config object.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "LinkerScript.h"
17 #include "Config.h"
18 #include "Driver.h"
19 #include "InputSection.h"
20 #include "ScriptParser.h"
21 #include "SymbolTable.h"
22 #include "llvm/Support/FileSystem.h"
23 #include "llvm/Support/MemoryBuffer.h"
24 #include "llvm/Support/Path.h"
25 #include "llvm/Support/StringSaver.h"
26 
27 using namespace llvm;
28 using namespace llvm::object;
29 using namespace lld;
30 using namespace lld::elf;
31 
32 LinkerScript *elf::Script;
33 
34 template <class ELFT>
35 SectionRule *LinkerScript::find(InputSectionBase<ELFT> *S) {
36   for (SectionRule &R : Sections)
37     if (R.match(S))
38       return &R;
39   return nullptr;
40 }
41 
42 template <class ELFT>
43 StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
44   SectionRule *R = find(S);
45   return R ? R->Dest : "";
46 }
47 
48 template <class ELFT>
49 bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
50   return getOutputSection(S) == "/DISCARD/";
51 }
52 
53 template <class ELFT> bool LinkerScript::shouldKeep(InputSectionBase<ELFT> *S) {
54   SectionRule *R = find(S);
55   return R && R->Keep;
56 }
57 
58 ArrayRef<uint8_t> LinkerScript::getFiller(StringRef Name) {
59   auto I = Filler.find(Name);
60   if (I == Filler.end())
61     return {};
62   return I->second;
63 }
64 
65 // A compartor to sort output sections. Returns -1 or 1 if both
66 // A and B are mentioned in linker scripts. Otherwise, returns 0
67 // to use the default rule which is implemented in Writer.cpp.
68 int LinkerScript::compareSections(StringRef A, StringRef B) {
69   auto E = SectionOrder.end();
70   auto I = std::find(SectionOrder.begin(), E, A);
71   auto J = std::find(SectionOrder.begin(), E, B);
72   if (I == E || J == E)
73     return 0;
74   return I < J ? -1 : 1;
75 }
76 
77 // Returns true if S matches T. S can contain glob meta-characters.
78 // The asterisk ('*') matches zero or more characacters, and the question
79 // mark ('?') matches one character.
80 static bool matchStr(StringRef S, StringRef T) {
81   for (;;) {
82     if (S.empty())
83       return T.empty();
84     if (S[0] == '*') {
85       S = S.substr(1);
86       if (S.empty())
87         // Fast path. If a pattern is '*', it matches anything.
88         return true;
89       for (size_t I = 0, E = T.size(); I < E; ++I)
90         if (matchStr(S, T.substr(I)))
91           return true;
92       return false;
93     }
94     if (T.empty() || (S[0] != T[0] && S[0] != '?'))
95       return false;
96     S = S.substr(1);
97     T = T.substr(1);
98   }
99 }
100 
101 template <class ELFT> bool SectionRule::match(InputSectionBase<ELFT> *S) {
102   return matchStr(SectionPattern, S->getSectionName());
103 }
104 
105 class elf::ScriptParser final : public elf::ScriptParserBase {
106   typedef void (ScriptParser::*Handler)();
107 
108 public:
109   ScriptParser(BumpPtrAllocator *A, StringRef S, bool B)
110       : ScriptParserBase(S), Saver(*A), IsUnderSysroot(B) {}
111 
112   void run() override;
113 
114 private:
115   void addFile(StringRef Path);
116 
117   void readAsNeeded();
118   void readEntry();
119   void readExtern();
120   void readGroup();
121   void readInclude();
122   void readNothing() {}
123   void readOutput();
124   void readOutputArch();
125   void readOutputFormat();
126   void readSearchDir();
127   void readSections();
128 
129   void readOutputSectionDescription();
130   void readSectionPatterns(StringRef OutSec, bool Keep);
131 
132   StringSaver Saver;
133   const static StringMap<Handler> Cmd;
134   bool IsUnderSysroot;
135 };
136 
137 const StringMap<elf::ScriptParser::Handler> elf::ScriptParser::Cmd = {
138     {"ENTRY", &ScriptParser::readEntry},
139     {"EXTERN", &ScriptParser::readExtern},
140     {"GROUP", &ScriptParser::readGroup},
141     {"INCLUDE", &ScriptParser::readInclude},
142     {"INPUT", &ScriptParser::readGroup},
143     {"OUTPUT", &ScriptParser::readOutput},
144     {"OUTPUT_ARCH", &ScriptParser::readOutputArch},
145     {"OUTPUT_FORMAT", &ScriptParser::readOutputFormat},
146     {"SEARCH_DIR", &ScriptParser::readSearchDir},
147     {"SECTIONS", &ScriptParser::readSections},
148     {";", &ScriptParser::readNothing}};
149 
150 void ScriptParser::run() {
151   while (!atEOF()) {
152     StringRef Tok = next();
153     if (Handler Fn = Cmd.lookup(Tok))
154       (this->*Fn)();
155     else
156       setError("unknown directive: " + Tok);
157   }
158 }
159 
160 void ScriptParser::addFile(StringRef S) {
161   if (IsUnderSysroot && S.startswith("/")) {
162     SmallString<128> Path;
163     (Config->Sysroot + S).toStringRef(Path);
164     if (sys::fs::exists(Path)) {
165       Driver->addFile(Saver.save(Path.str()));
166       return;
167     }
168   }
169 
170   if (sys::path::is_absolute(S)) {
171     Driver->addFile(S);
172   } else if (S.startswith("=")) {
173     if (Config->Sysroot.empty())
174       Driver->addFile(S.substr(1));
175     else
176       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
177   } else if (S.startswith("-l")) {
178     Driver->addLibrary(S.substr(2));
179   } else if (sys::fs::exists(S)) {
180     Driver->addFile(S);
181   } else {
182     std::string Path = findFromSearchPaths(S);
183     if (Path.empty())
184       setError("unable to find " + S);
185     else
186       Driver->addFile(Saver.save(Path));
187   }
188 }
189 
190 void ScriptParser::readAsNeeded() {
191   expect("(");
192   bool Orig = Config->AsNeeded;
193   Config->AsNeeded = true;
194   while (!Error) {
195     StringRef Tok = next();
196     if (Tok == ")")
197       break;
198     addFile(Tok);
199   }
200   Config->AsNeeded = Orig;
201 }
202 
203 void ScriptParser::readEntry() {
204   // -e <symbol> takes predecence over ENTRY(<symbol>).
205   expect("(");
206   StringRef Tok = next();
207   if (Config->Entry.empty())
208     Config->Entry = Tok;
209   expect(")");
210 }
211 
212 void ScriptParser::readExtern() {
213   expect("(");
214   while (!Error) {
215     StringRef Tok = next();
216     if (Tok == ")")
217       return;
218     Config->Undefined.push_back(Tok);
219   }
220 }
221 
222 void ScriptParser::readGroup() {
223   expect("(");
224   while (!Error) {
225     StringRef Tok = next();
226     if (Tok == ")")
227       return;
228     if (Tok == "AS_NEEDED") {
229       readAsNeeded();
230       continue;
231     }
232     addFile(Tok);
233   }
234 }
235 
236 void ScriptParser::readInclude() {
237   StringRef Tok = next();
238   auto MBOrErr = MemoryBuffer::getFile(Tok);
239   if (!MBOrErr) {
240     setError("cannot open " + Tok);
241     return;
242   }
243   std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
244   StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
245   std::vector<StringRef> V = tokenize(S);
246   Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
247 }
248 
249 void ScriptParser::readOutput() {
250   // -o <file> takes predecence over OUTPUT(<file>).
251   expect("(");
252   StringRef Tok = next();
253   if (Config->OutputFile.empty())
254     Config->OutputFile = Tok;
255   expect(")");
256 }
257 
258 void ScriptParser::readOutputArch() {
259   // Error checking only for now.
260   expect("(");
261   next();
262   expect(")");
263 }
264 
265 void ScriptParser::readOutputFormat() {
266   // Error checking only for now.
267   expect("(");
268   next();
269   StringRef Tok = next();
270   if (Tok == ")")
271    return;
272   if (Tok != ",") {
273     setError("unexpected token: " + Tok);
274     return;
275   }
276   next();
277   expect(",");
278   next();
279   expect(")");
280 }
281 
282 void ScriptParser::readSearchDir() {
283   expect("(");
284   Config->SearchPaths.push_back(next());
285   expect(")");
286 }
287 
288 void ScriptParser::readSections() {
289   expect("{");
290   while (!Error && !skip("}"))
291     readOutputSectionDescription();
292 }
293 
294 void ScriptParser::readSectionPatterns(StringRef OutSec, bool Keep) {
295   expect("(");
296   while (!Error && !skip(")"))
297     Script->Sections.emplace_back(OutSec, next(), Keep);
298 }
299 
300 void ScriptParser::readOutputSectionDescription() {
301   StringRef OutSec = next();
302   Script->SectionOrder.push_back(OutSec);
303   expect(":");
304   expect("{");
305   while (!Error && !skip("}")) {
306     StringRef Tok = next();
307     if (Tok == "*") {
308       readSectionPatterns(OutSec, false);
309     } else if (Tok == "KEEP") {
310       expect("(");
311       next(); // Skip *
312       readSectionPatterns(OutSec, true);
313       expect(")");
314     } else {
315       setError("unknown command " + Tok);
316     }
317   }
318   StringRef Tok = peek();
319   if (Tok.startswith("=")) {
320     if (!Tok.startswith("=0x")) {
321       setError("filler should be a hexadecimal value");
322       return;
323     }
324     Tok = Tok.substr(3);
325     Script->Filler[OutSec] = parseHex(Tok);
326     next();
327   }
328 }
329 
330 static bool isUnderSysroot(StringRef Path) {
331   if (Config->Sysroot == "")
332     return false;
333   for (; !Path.empty(); Path = sys::path::parent_path(Path))
334     if (sys::fs::equivalent(Config->Sysroot, Path))
335       return true;
336   return false;
337 }
338 
339 // Entry point. The other functions or classes are private to this file.
340 void LinkerScript::read(MemoryBufferRef MB) {
341   StringRef Path = MB.getBufferIdentifier();
342   ScriptParser(&Alloc, MB.getBuffer(), isUnderSysroot(Path)).run();
343 }
344 
345 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32LE> *);
346 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32BE> *);
347 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64LE> *);
348 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64BE> *);
349 
350 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32LE> *);
351 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32BE> *);
352 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64LE> *);
353 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64BE> *);
354 
355 template bool LinkerScript::shouldKeep(InputSectionBase<ELF32LE> *);
356 template bool LinkerScript::shouldKeep(InputSectionBase<ELF32BE> *);
357 template bool LinkerScript::shouldKeep(InputSectionBase<ELF64LE> *);
358 template bool LinkerScript::shouldKeep(InputSectionBase<ELF64BE> *);
359