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