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 "SymbolTable.h"
21 #include "llvm/Support/FileSystem.h"
22 #include "llvm/Support/MemoryBuffer.h"
23 #include "llvm/Support/Path.h"
24 #include "llvm/Support/StringSaver.h"
25 
26 using namespace llvm;
27 using namespace llvm::object;
28 using namespace lld;
29 using namespace lld::elf2;
30 
31 LinkerScript *elf2::Script;
32 
33 template <class ELFT>
34 SectionRule *LinkerScript::find(InputSectionBase<ELFT> *S) {
35   for (SectionRule &R : Sections)
36     if (R.match(S))
37       return &R;
38   return nullptr;
39 }
40 
41 template <class ELFT>
42 StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
43   SectionRule *R = find(S);
44   return R ? R->Dest : "";
45 }
46 
47 template <class ELFT>
48 bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
49   return getOutputSection(S) == "/DISCARD/";
50 }
51 
52 template <class ELFT> bool LinkerScript::shouldKeep(InputSectionBase<ELFT> *S) {
53   SectionRule *R = find(S);
54   return R && R->Keep;
55 }
56 
57 // A compartor to sort output sections. Returns -1 or 1 if both
58 // A and B are mentioned in linker scripts. Otherwise, returns 0
59 // to use the default rule which is implemented in Writer.cpp.
60 int LinkerScript::compareSections(StringRef A, StringRef B) {
61   auto E = SectionOrder.end();
62   auto I = std::find(SectionOrder.begin(), E, A);
63   auto J = std::find(SectionOrder.begin(), E, B);
64   if (I == E || J == E)
65     return 0;
66   return I < J ? -1 : 1;
67 }
68 
69 // Returns true if S matches T. S may contain a meta character '*'
70 // which matches zero or more occurrences of any character.
71 static bool matchStr(StringRef S, StringRef T) {
72   for (;;) {
73     if (S.empty())
74       return T.empty();
75     if (S[0] == '*') {
76       S = S.substr(1);
77       if (S.empty())
78         // Fast path. If a pattern is '*', it matches anything.
79         return true;
80       for (size_t I = 0, E = T.size(); I < E; ++I)
81         if (matchStr(S, T.substr(I)))
82           return true;
83       return false;
84     }
85     if (T.empty() || S[0] != T[0])
86       return false;
87     S = S.substr(1);
88     T = T.substr(1);
89   }
90 }
91 
92 template <class ELFT> bool SectionRule::match(InputSectionBase<ELFT> *S) {
93   return matchStr(SectionPattern, S->getSectionName());
94 }
95 
96 class elf2::ScriptParser {
97 public:
98   ScriptParser(BumpPtrAllocator *A, StringRef S, bool B)
99       : Saver(*A), Tokens(tokenize(S)), IsUnderSysroot(B) {
100     Cmd["ENTRY"] = std::mem_fn(&ScriptParser::readEntry);
101     Cmd["EXTERN"] = std::mem_fn(&ScriptParser::readExtern);
102     Cmd["GROUP"] = std::mem_fn(&ScriptParser::readGroup);
103     Cmd["INCLUDE"] = std::mem_fn(&ScriptParser::readInclude);
104     Cmd["INPUT"] = std::mem_fn(&ScriptParser::readGroup);
105     Cmd["OUTPUT"] = std::mem_fn(&ScriptParser::readOutput);
106     Cmd["OUTPUT_ARCH"] = std::mem_fn(&ScriptParser::readOutputArch);
107     Cmd["OUTPUT_FORMAT"] = std::mem_fn(&ScriptParser::readOutputFormat);
108     Cmd["SEARCH_DIR"] = std::mem_fn(&ScriptParser::readSearchDir);
109     Cmd["SECTIONS"] = std::mem_fn(&ScriptParser::readSections);
110     Cmd[";"] = [](ScriptParser &) {};
111   }
112 
113   void run();
114 
115 private:
116   void setError(const Twine &Msg);
117   static std::vector<StringRef> tokenize(StringRef S);
118   static StringRef skipSpace(StringRef S);
119   bool atEOF();
120   StringRef next();
121   bool skip(StringRef Tok);
122   void expect(StringRef Expect);
123 
124   void addFile(StringRef Path);
125 
126   void readAsNeeded();
127   void readEntry();
128   void readExtern();
129   void readGroup();
130   void readInclude();
131   void readOutput();
132   void readOutputArch();
133   void readOutputFormat();
134   void readSearchDir();
135   void readSections();
136 
137   void readOutputSectionDescription();
138   void readSectionPatterns(StringRef OutSec, bool Keep);
139 
140   StringSaver Saver;
141   std::vector<StringRef> Tokens;
142   llvm::StringMap<std::function<void(ScriptParser &)>> Cmd;
143   size_t Pos = 0;
144   bool IsUnderSysroot;
145   bool Error = false;
146 };
147 
148 void ScriptParser::run() {
149   while (!atEOF()) {
150     StringRef Tok = next();
151     auto It = Cmd.find(Tok);
152     if (It != Cmd.end()) {
153       std::function<void(ScriptParser &)> &Handler = It->second;
154       Handler(*this);
155     } else {
156       setError("unknown directive: " + Tok);
157     }
158   }
159 }
160 
161 // We don't want to record cascading errors. Keep only the first one.
162 void ScriptParser::setError(const Twine &Msg) {
163   if (Error)
164     return;
165   error(Msg);
166   Error = true;
167 }
168 
169 // Split S into linker script tokens.
170 std::vector<StringRef> ScriptParser::tokenize(StringRef S) {
171   std::vector<StringRef> Ret;
172   for (;;) {
173     S = skipSpace(S);
174     if (S.empty())
175       return Ret;
176 
177     // Quoted token
178     if (S.startswith("\"")) {
179       size_t E = S.find("\"", 1);
180       if (E == StringRef::npos) {
181         error("unclosed quote");
182         return {};
183       }
184       Ret.push_back(S.substr(1, E - 1));
185       S = S.substr(E + 1);
186       continue;
187     }
188 
189     // Unquoted token
190     size_t Pos = S.find_first_not_of(
191         "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
192         "0123456789_.$/\\~=+[]*?-:");
193     // A character that cannot start a word (which is usually a
194     // punctuation) forms a single character token.
195     if (Pos == 0)
196       Pos = 1;
197     Ret.push_back(S.substr(0, Pos));
198     S = S.substr(Pos);
199   }
200 }
201 
202 // Skip leading whitespace characters or /**/-style comments.
203 StringRef ScriptParser::skipSpace(StringRef S) {
204   for (;;) {
205     if (S.startswith("/*")) {
206       size_t E = S.find("*/", 2);
207       if (E == StringRef::npos) {
208         error("unclosed comment in a linker script");
209         return "";
210       }
211       S = S.substr(E + 2);
212       continue;
213     }
214     size_t Size = S.size();
215     S = S.ltrim();
216     if (S.size() == Size)
217       return S;
218   }
219 }
220 
221 // An errneous token is handled as if it were the last token before EOF.
222 bool ScriptParser::atEOF() { return Error || Tokens.size() == Pos; }
223 
224 StringRef ScriptParser::next() {
225   if (Error)
226     return "";
227   if (atEOF()) {
228     setError("unexpected EOF");
229     return "";
230   }
231   return Tokens[Pos++];
232 }
233 
234 bool ScriptParser::skip(StringRef Tok) {
235   if (Error)
236     return false;
237   if (atEOF()) {
238     setError("unexpected EOF");
239     return false;
240   }
241   if (Tok != Tokens[Pos])
242     return false;
243   ++Pos;
244   return true;
245 }
246 
247 void ScriptParser::expect(StringRef Expect) {
248   if (Error)
249     return;
250   StringRef Tok = next();
251   if (Tok != Expect)
252     setError(Expect + " expected, but got " + Tok);
253 }
254 
255 void ScriptParser::addFile(StringRef S) {
256   if (IsUnderSysroot && S.startswith("/")) {
257     SmallString<128> Path;
258     (Config->Sysroot + S).toStringRef(Path);
259     if (sys::fs::exists(Path)) {
260       Driver->addFile(Saver.save(Path.str()));
261       return;
262     }
263   }
264 
265   if (sys::path::is_absolute(S)) {
266     Driver->addFile(S);
267   } else if (S.startswith("=")) {
268     if (Config->Sysroot.empty())
269       Driver->addFile(S.substr(1));
270     else
271       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
272   } else if (S.startswith("-l")) {
273     Driver->addLibrary(S.substr(2));
274   } else if (sys::fs::exists(S)) {
275     Driver->addFile(S);
276   } else {
277     std::string Path = findFromSearchPaths(S);
278     if (Path.empty())
279       setError("Unable to find " + S);
280     else
281       Driver->addFile(Saver.save(Path));
282   }
283 }
284 
285 void ScriptParser::readAsNeeded() {
286   expect("(");
287   bool Orig = Config->AsNeeded;
288   Config->AsNeeded = true;
289   while (!Error) {
290     StringRef Tok = next();
291     if (Tok == ")")
292       break;
293     addFile(Tok);
294   }
295   Config->AsNeeded = Orig;
296 }
297 
298 void ScriptParser::readEntry() {
299   // -e <symbol> takes predecence over ENTRY(<symbol>).
300   expect("(");
301   StringRef Tok = next();
302   if (Config->Entry.empty())
303     Config->Entry = Tok;
304   expect(")");
305 }
306 
307 void ScriptParser::readExtern() {
308   expect("(");
309   while (!Error) {
310     StringRef Tok = next();
311     if (Tok == ")")
312       return;
313     Config->Undefined.push_back(Tok);
314   }
315 }
316 
317 void ScriptParser::readGroup() {
318   expect("(");
319   while (!Error) {
320     StringRef Tok = next();
321     if (Tok == ")")
322       return;
323     if (Tok == "AS_NEEDED") {
324       readAsNeeded();
325       continue;
326     }
327     addFile(Tok);
328   }
329 }
330 
331 void ScriptParser::readInclude() {
332   StringRef Tok = next();
333   auto MBOrErr = MemoryBuffer::getFile(Tok);
334   if (!MBOrErr) {
335     setError("cannot open " + Tok);
336     return;
337   }
338   std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
339   StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
340   std::vector<StringRef> V = tokenize(S);
341   Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
342 }
343 
344 void ScriptParser::readOutput() {
345   // -o <file> takes predecence over OUTPUT(<file>).
346   expect("(");
347   StringRef Tok = next();
348   if (Config->OutputFile.empty())
349     Config->OutputFile = Tok;
350   expect(")");
351 }
352 
353 void ScriptParser::readOutputArch() {
354   // Error checking only for now.
355   expect("(");
356   next();
357   expect(")");
358 }
359 
360 void ScriptParser::readOutputFormat() {
361   // Error checking only for now.
362   expect("(");
363   next();
364   StringRef Tok = next();
365   if (Tok == ")")
366    return;
367   if (Tok != ",") {
368     setError("unexpected token: " + Tok);
369     return;
370   }
371   next();
372   expect(",");
373   next();
374   expect(")");
375 }
376 
377 void ScriptParser::readSearchDir() {
378   expect("(");
379   Config->SearchPaths.push_back(next());
380   expect(")");
381 }
382 
383 void ScriptParser::readSections() {
384   expect("{");
385   while (!Error && !skip("}"))
386     readOutputSectionDescription();
387 }
388 
389 void ScriptParser::readSectionPatterns(StringRef OutSec, bool Keep) {
390   expect("(");
391   while (!Error && !skip(")"))
392     Script->Sections.emplace_back(OutSec, next(), Keep);
393 }
394 
395 void ScriptParser::readOutputSectionDescription() {
396   StringRef OutSec = next();
397   Script->SectionOrder.push_back(OutSec);
398   expect(":");
399   expect("{");
400   while (!Error && !skip("}")) {
401     StringRef Tok = next();
402     if (Tok == "*") {
403       readSectionPatterns(OutSec, false);
404     } else if (Tok == "KEEP") {
405       expect("(");
406       next(); // Skip *
407       readSectionPatterns(OutSec, true);
408       expect(")");
409     } else {
410       setError("Unknown command " + Tok);
411     }
412   }
413 }
414 
415 static bool isUnderSysroot(StringRef Path) {
416   if (Config->Sysroot == "")
417     return false;
418   for (; !Path.empty(); Path = sys::path::parent_path(Path))
419     if (sys::fs::equivalent(Config->Sysroot, Path))
420       return true;
421   return false;
422 }
423 
424 // Entry point. The other functions or classes are private to this file.
425 void LinkerScript::read(MemoryBufferRef MB) {
426   StringRef Path = MB.getBufferIdentifier();
427   ScriptParser(&Alloc, MB.getBuffer(), isUnderSysroot(Path)).run();
428 }
429 
430 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32LE> *);
431 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32BE> *);
432 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64LE> *);
433 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64BE> *);
434 
435 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32LE> *);
436 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32BE> *);
437 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64LE> *);
438 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64BE> *);
439 
440 template bool LinkerScript::shouldKeep(InputSectionBase<ELF32LE> *);
441 template bool LinkerScript::shouldKeep(InputSectionBase<ELF32BE> *);
442 template bool LinkerScript::shouldKeep(InputSectionBase<ELF64LE> *);
443 template bool LinkerScript::shouldKeep(InputSectionBase<ELF64BE> *);
444 
445 template bool SectionRule::match(InputSectionBase<ELF32LE> *);
446 template bool SectionRule::match(InputSectionBase<ELF32BE> *);
447 template bool SectionRule::match(InputSectionBase<ELF64LE> *);
448 template bool SectionRule::match(InputSectionBase<ELF64BE> *);
449