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 "OutputSections.h"
21 #include "ScriptParser.h"
22 #include "SymbolTable.h"
23 #include "llvm/ADT/StringSwitch.h"
24 #include "llvm/Support/ELF.h"
25 #include "llvm/Support/FileSystem.h"
26 #include "llvm/Support/MemoryBuffer.h"
27 #include "llvm/Support/Path.h"
28 #include "llvm/Support/StringSaver.h"
29 
30 using namespace llvm;
31 using namespace llvm::ELF;
32 using namespace llvm::object;
33 using namespace lld;
34 using namespace lld::elf;
35 
36 ScriptConfiguration *elf::ScriptConfig;
37 
38 static bool matchStr(StringRef S, StringRef T);
39 
40 // This is an operator-precedence parser to parse and evaluate
41 // a linker script expression. For each linker script arithmetic
42 // expression (e.g. ". = . + 0x1000"), a new instance of ExprParser
43 // is created and ran.
44 namespace {
45 class ExprParser : public ScriptParserBase {
46 public:
47   ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
48       : ScriptParserBase(Tokens), Dot(Dot) {}
49 
50   uint64_t run();
51 
52 private:
53   uint64_t parsePrimary();
54   uint64_t parseTernary(uint64_t Cond);
55   uint64_t apply(StringRef Op, uint64_t L, uint64_t R);
56   uint64_t parseExpr1(uint64_t Lhs, int MinPrec);
57   uint64_t parseExpr();
58 
59   uint64_t Dot;
60 };
61 }
62 
63 static int precedence(StringRef Op) {
64   return StringSwitch<int>(Op)
65       .Case("*", 4)
66       .Case("/", 4)
67       .Case("+", 3)
68       .Case("-", 3)
69       .Case("<", 2)
70       .Case(">", 2)
71       .Case(">=", 2)
72       .Case("<=", 2)
73       .Case("==", 2)
74       .Case("!=", 2)
75       .Case("&", 1)
76       .Default(-1);
77 }
78 
79 static uint64_t evalExpr(std::vector<StringRef> &Tokens, uint64_t Dot) {
80   return ExprParser(Tokens, Dot).run();
81 }
82 
83 uint64_t ExprParser::run() {
84   uint64_t V = parseExpr();
85   if (!atEOF() && !Error)
86     setError("stray token: " + peek());
87   return V;
88 }
89 
90 // This is a part of the operator-precedence parser to evaluate
91 // arithmetic expressions in SECTIONS command. This function evaluates an
92 // integer literal, a parenthesized expression, the ALIGN function,
93 // or the special variable ".".
94 uint64_t ExprParser::parsePrimary() {
95   StringRef Tok = next();
96   if (Tok == ".")
97     return Dot;
98   if (Tok == "(") {
99     uint64_t V = parseExpr();
100     expect(")");
101     return V;
102   }
103   if (Tok == "ALIGN") {
104     expect("(");
105     uint64_t V = parseExpr();
106     expect(")");
107     return alignTo(Dot, V);
108   }
109   uint64_t V = 0;
110   if (Tok.getAsInteger(0, V))
111     setError("malformed number: " + Tok);
112   return V;
113 }
114 
115 uint64_t ExprParser::parseTernary(uint64_t Cond) {
116   next();
117   uint64_t V = parseExpr();
118   expect(":");
119   uint64_t W = parseExpr();
120   return Cond ? V : W;
121 }
122 
123 uint64_t ExprParser::apply(StringRef Op, uint64_t L, uint64_t R) {
124   if (Op == "*")
125     return L * R;
126   if (Op == "/") {
127     if (R == 0) {
128       error("division by zero");
129       return 0;
130     }
131     return L / R;
132   }
133   if (Op == "+")
134     return L + R;
135   if (Op == "-")
136     return L - R;
137   if (Op == "<")
138     return L < R;
139   if (Op == ">")
140     return L > R;
141   if (Op == ">=")
142     return L >= R;
143   if (Op == "<=")
144     return L <= R;
145   if (Op == "==")
146     return L == R;
147   if (Op == "!=")
148     return L != R;
149   if (Op == "&")
150     return L & R;
151   llvm_unreachable("invalid operator");
152   return 0;
153 }
154 
155 // This is a part of the operator-precedence parser.
156 // This function assumes that the remaining token stream starts
157 // with an operator.
158 uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) {
159   while (!atEOF()) {
160     // Read an operator and an expression.
161     StringRef Op1 = peek();
162     if (Op1 == "?")
163       return parseTernary(Lhs);
164     if (precedence(Op1) < MinPrec)
165       return Lhs;
166     next();
167     uint64_t Rhs = parsePrimary();
168 
169     // Evaluate the remaining part of the expression first if the
170     // next operator has greater precedence than the previous one.
171     // For example, if we have read "+" and "3", and if the next
172     // operator is "*", then we'll evaluate 3 * ... part first.
173     while (!atEOF()) {
174       StringRef Op2 = peek();
175       if (precedence(Op2) <= precedence(Op1))
176         break;
177       Rhs = parseExpr1(Rhs, precedence(Op2));
178     }
179 
180     Lhs = apply(Op1, Lhs, Rhs);
181   }
182   return Lhs;
183 }
184 
185 // Reads and evaluates an arithmetic expression.
186 uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
187 
188 template <class ELFT>
189 StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
190   for (SectionRule &R : Opt.Sections)
191     if (matchStr(R.SectionPattern, S->getSectionName()))
192       return R.Dest;
193   return "";
194 }
195 
196 template <class ELFT>
197 bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
198   return getOutputSection(S) == "/DISCARD/";
199 }
200 
201 template <class ELFT>
202 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
203   for (StringRef Pat : Opt.KeptSections)
204     if (matchStr(Pat, S->getSectionName()))
205       return true;
206   return false;
207 }
208 
209 template <class ELFT>
210 static OutputSectionBase<ELFT> *
211 findSection(ArrayRef<OutputSectionBase<ELFT> *> V, StringRef Name) {
212   for (OutputSectionBase<ELFT> *Sec : V)
213     if (Sec->getName() == Name)
214       return Sec;
215   return nullptr;
216 }
217 
218 template <class ELFT>
219 void LinkerScript<ELFT>::assignAddresses(
220     ArrayRef<OutputSectionBase<ELFT> *> Sections) {
221   // Orphan sections are sections present in the input files which
222   // are not explicitly placed into the output file by the linker script.
223   // We place orphan sections at end of file.
224   // Other linkers places them using some heuristics as described in
225   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
226   for (OutputSectionBase<ELFT> *Sec : Sections) {
227     StringRef Name = Sec->getName();
228     if (getSectionIndex(Name) == INT_MAX)
229       Opt.Commands.push_back({SectionKind, {}, Name});
230   }
231 
232   // Assign addresses as instructed by linker script SECTIONS sub-commands.
233   Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
234   uintX_t ThreadBssOffset = 0;
235 
236   for (SectionsCommand &Cmd : Opt.Commands) {
237     if (Cmd.Kind == ExprKind) {
238       Dot = evalExpr(Cmd.Expr, Dot);
239       continue;
240     }
241 
242     OutputSectionBase<ELFT> *Sec = findSection<ELFT>(Sections, Cmd.SectionName);
243     if (!Sec)
244       continue;
245 
246     if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
247       uintX_t TVA = Dot + ThreadBssOffset;
248       TVA = alignTo(TVA, Sec->getAlign());
249       Sec->setVA(TVA);
250       ThreadBssOffset = TVA - Dot + Sec->getSize();
251       continue;
252     }
253 
254     if (Sec->getFlags() & SHF_ALLOC) {
255       Dot = alignTo(Dot, Sec->getAlign());
256       Sec->setVA(Dot);
257       Dot += Sec->getSize();
258       continue;
259     }
260   }
261 }
262 
263 template <class ELFT>
264 ArrayRef<uint8_t> LinkerScript<ELFT>::getFiller(StringRef Name) {
265   auto I = Opt.Filler.find(Name);
266   if (I == Opt.Filler.end())
267     return {};
268   return I->second;
269 }
270 
271 // Returns the index of the given section name in linker script
272 // SECTIONS commands. Sections are laid out as the same order as they
273 // were in the script. If a given name did not appear in the script,
274 // it returns INT_MAX, so that it will be laid out at end of file.
275 template <class ELFT>
276 int LinkerScript<ELFT>::getSectionIndex(StringRef Name) {
277   auto Begin = Opt.Commands.begin();
278   auto End = Opt.Commands.end();
279   auto I = std::find_if(Begin, End, [&](SectionsCommand &N) {
280     return N.Kind == SectionKind && N.SectionName == Name;
281   });
282   return I == End ? INT_MAX : (I - Begin);
283 }
284 
285 // A compartor to sort output sections. Returns -1 or 1 if
286 // A or B are mentioned in linker script. Otherwise, returns 0.
287 template <class ELFT>
288 int LinkerScript<ELFT>::compareSections(StringRef A, StringRef B) {
289   int I = getSectionIndex(A);
290   int J = getSectionIndex(B);
291   if (I == INT_MAX && J == INT_MAX)
292     return 0;
293   return I < J ? -1 : 1;
294 }
295 
296 // Returns true if S matches T. S can contain glob meta-characters.
297 // The asterisk ('*') matches zero or more characacters, and the question
298 // mark ('?') matches one character.
299 static bool matchStr(StringRef S, StringRef T) {
300   for (;;) {
301     if (S.empty())
302       return T.empty();
303     if (S[0] == '*') {
304       S = S.substr(1);
305       if (S.empty())
306         // Fast path. If a pattern is '*', it matches anything.
307         return true;
308       for (size_t I = 0, E = T.size(); I < E; ++I)
309         if (matchStr(S, T.substr(I)))
310           return true;
311       return false;
312     }
313     if (T.empty() || (S[0] != T[0] && S[0] != '?'))
314       return false;
315     S = S.substr(1);
316     T = T.substr(1);
317   }
318 }
319 
320 class elf::ScriptParser : public ScriptParserBase {
321   typedef void (ScriptParser::*Handler)();
322 
323 public:
324   ScriptParser(StringRef S, bool B) : ScriptParserBase(S), IsUnderSysroot(B) {}
325 
326   void run();
327 
328 private:
329   void addFile(StringRef Path);
330 
331   void readAsNeeded();
332   void readEntry();
333   void readExtern();
334   void readGroup();
335   void readInclude();
336   void readNothing() {}
337   void readOutput();
338   void readOutputArch();
339   void readOutputFormat();
340   void readSearchDir();
341   void readSections();
342 
343   void readLocationCounterValue();
344   void readOutputSectionDescription();
345   void readSectionPatterns(StringRef OutSec);
346 
347   const static StringMap<Handler> Cmd;
348   ScriptConfiguration &Opt = *ScriptConfig;
349   StringSaver Saver = {ScriptConfig->Alloc};
350   bool IsUnderSysroot;
351 };
352 
353 const StringMap<elf::ScriptParser::Handler> elf::ScriptParser::Cmd = {
354     {"ENTRY", &ScriptParser::readEntry},
355     {"EXTERN", &ScriptParser::readExtern},
356     {"GROUP", &ScriptParser::readGroup},
357     {"INCLUDE", &ScriptParser::readInclude},
358     {"INPUT", &ScriptParser::readGroup},
359     {"OUTPUT", &ScriptParser::readOutput},
360     {"OUTPUT_ARCH", &ScriptParser::readOutputArch},
361     {"OUTPUT_FORMAT", &ScriptParser::readOutputFormat},
362     {"SEARCH_DIR", &ScriptParser::readSearchDir},
363     {"SECTIONS", &ScriptParser::readSections},
364     {";", &ScriptParser::readNothing}};
365 
366 void ScriptParser::run() {
367   while (!atEOF()) {
368     StringRef Tok = next();
369     if (Handler Fn = Cmd.lookup(Tok))
370       (this->*Fn)();
371     else
372       setError("unknown directive: " + Tok);
373   }
374 }
375 
376 void ScriptParser::addFile(StringRef S) {
377   if (IsUnderSysroot && S.startswith("/")) {
378     SmallString<128> Path;
379     (Config->Sysroot + S).toStringRef(Path);
380     if (sys::fs::exists(Path)) {
381       Driver->addFile(Saver.save(Path.str()));
382       return;
383     }
384   }
385 
386   if (sys::path::is_absolute(S)) {
387     Driver->addFile(S);
388   } else if (S.startswith("=")) {
389     if (Config->Sysroot.empty())
390       Driver->addFile(S.substr(1));
391     else
392       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
393   } else if (S.startswith("-l")) {
394     Driver->addLibrary(S.substr(2));
395   } else if (sys::fs::exists(S)) {
396     Driver->addFile(S);
397   } else {
398     std::string Path = findFromSearchPaths(S);
399     if (Path.empty())
400       setError("unable to find " + S);
401     else
402       Driver->addFile(Saver.save(Path));
403   }
404 }
405 
406 void ScriptParser::readAsNeeded() {
407   expect("(");
408   bool Orig = Config->AsNeeded;
409   Config->AsNeeded = true;
410   while (!Error) {
411     StringRef Tok = next();
412     if (Tok == ")")
413       break;
414     addFile(Tok);
415   }
416   Config->AsNeeded = Orig;
417 }
418 
419 void ScriptParser::readEntry() {
420   // -e <symbol> takes predecence over ENTRY(<symbol>).
421   expect("(");
422   StringRef Tok = next();
423   if (Config->Entry.empty())
424     Config->Entry = Tok;
425   expect(")");
426 }
427 
428 void ScriptParser::readExtern() {
429   expect("(");
430   while (!Error) {
431     StringRef Tok = next();
432     if (Tok == ")")
433       return;
434     Config->Undefined.push_back(Tok);
435   }
436 }
437 
438 void ScriptParser::readGroup() {
439   expect("(");
440   while (!Error) {
441     StringRef Tok = next();
442     if (Tok == ")")
443       return;
444     if (Tok == "AS_NEEDED") {
445       readAsNeeded();
446       continue;
447     }
448     addFile(Tok);
449   }
450 }
451 
452 void ScriptParser::readInclude() {
453   StringRef Tok = next();
454   auto MBOrErr = MemoryBuffer::getFile(Tok);
455   if (!MBOrErr) {
456     setError("cannot open " + Tok);
457     return;
458   }
459   std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
460   StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
461   std::vector<StringRef> V = tokenize(S);
462   Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
463 }
464 
465 void ScriptParser::readOutput() {
466   // -o <file> takes predecence over OUTPUT(<file>).
467   expect("(");
468   StringRef Tok = next();
469   if (Config->OutputFile.empty())
470     Config->OutputFile = Tok;
471   expect(")");
472 }
473 
474 void ScriptParser::readOutputArch() {
475   // Error checking only for now.
476   expect("(");
477   next();
478   expect(")");
479 }
480 
481 void ScriptParser::readOutputFormat() {
482   // Error checking only for now.
483   expect("(");
484   next();
485   StringRef Tok = next();
486   if (Tok == ")")
487    return;
488   if (Tok != ",") {
489     setError("unexpected token: " + Tok);
490     return;
491   }
492   next();
493   expect(",");
494   next();
495   expect(")");
496 }
497 
498 void ScriptParser::readSearchDir() {
499   expect("(");
500   Config->SearchPaths.push_back(next());
501   expect(")");
502 }
503 
504 void ScriptParser::readSections() {
505   Opt.DoLayout = true;
506   expect("{");
507   while (!Error && !skip("}")) {
508     StringRef Tok = peek();
509     if (Tok == ".")
510       readLocationCounterValue();
511     else
512       readOutputSectionDescription();
513   }
514 }
515 
516 void ScriptParser::readSectionPatterns(StringRef OutSec) {
517   expect("(");
518   while (!Error && !skip(")"))
519     Opt.Sections.emplace_back(OutSec, next());
520 }
521 
522 void ScriptParser::readLocationCounterValue() {
523   expect(".");
524   expect("=");
525   Opt.Commands.push_back({ExprKind, {}, ""});
526   SectionsCommand &Cmd = Opt.Commands.back();
527   while (!Error) {
528     StringRef Tok = next();
529     if (Tok == ";")
530       break;
531     Cmd.Expr.push_back(Tok);
532   }
533   if (Cmd.Expr.empty())
534     error("error in location counter expression");
535 }
536 
537 void ScriptParser::readOutputSectionDescription() {
538   StringRef OutSec = next();
539   Opt.Commands.push_back({SectionKind, {}, OutSec});
540   expect(":");
541   expect("{");
542 
543   while (!Error && !skip("}")) {
544     StringRef Tok = next();
545     if (Tok == "*") {
546       expect("(");
547       while (!Error && !skip(")"))
548         Opt.Sections.emplace_back(OutSec, next());
549     } else if (Tok == "KEEP") {
550       expect("(");
551       expect("*");
552       expect("(");
553       while (!Error && !skip(")")) {
554         StringRef Sec = next();
555         Opt.Sections.emplace_back(OutSec, Sec);
556         Opt.KeptSections.push_back(Sec);
557       }
558       expect(")");
559     } else {
560       setError("unknown command " + Tok);
561     }
562   }
563 
564   StringRef Tok = peek();
565   if (Tok.startswith("=")) {
566     if (!Tok.startswith("=0x")) {
567       setError("filler should be a hexadecimal value");
568       return;
569     }
570     Tok = Tok.substr(3);
571     Opt.Filler[OutSec] = parseHex(Tok);
572     next();
573   }
574 }
575 
576 static bool isUnderSysroot(StringRef Path) {
577   if (Config->Sysroot == "")
578     return false;
579   for (; !Path.empty(); Path = sys::path::parent_path(Path))
580     if (sys::fs::equivalent(Config->Sysroot, Path))
581       return true;
582   return false;
583 }
584 
585 // Entry point.
586 void elf::readLinkerScript(MemoryBufferRef MB) {
587   StringRef Path = MB.getBufferIdentifier();
588   ScriptParser(MB.getBuffer(), isUnderSysroot(Path)).run();
589 }
590 
591 template class elf::LinkerScript<ELF32LE>;
592 template class elf::LinkerScript<ELF32BE>;
593 template class elf::LinkerScript<ELF64LE>;
594 template class elf::LinkerScript<ELF64BE>;
595