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