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 void LinkerScript<ELFT>::assignAddresses(
211     ArrayRef<OutputSectionBase<ELFT> *> Sections) {
212   // Orphan sections are sections present in the input files which
213   // are not explicitly placed into the output file by the linker script.
214   // We place orphan sections at end of file.
215   // Other linkers places them using some heuristics as described in
216   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
217   for (OutputSectionBase<ELFT> *Sec : Sections) {
218     StringRef Name = Sec->getName();
219     if (getSectionIndex(Name) == INT_MAX)
220       Opt.Commands.push_back({SectionKind, {}, Name});
221   }
222 
223   // Assign addresses as instructed by linker script SECTIONS sub-commands.
224   Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
225   uintX_t ThreadBssOffset = 0;
226 
227   for (SectionsCommand &Cmd : Opt.Commands) {
228     if (Cmd.Kind == ExprKind) {
229       Dot = evalExpr(Cmd.Expr, Dot);
230       continue;
231     }
232 
233     // Find all the sections with required name. There can be more than
234     // ont section with such name, if the alignment, flags or type
235     // attribute differs.
236     for (OutputSectionBase<ELFT> *Sec : Sections) {
237       if (Sec->getName() != Cmd.SectionName)
238         continue;
239 
240       if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
241         uintX_t TVA = Dot + ThreadBssOffset;
242         TVA = alignTo(TVA, Sec->getAlign());
243         Sec->setVA(TVA);
244         ThreadBssOffset = TVA - Dot + Sec->getSize();
245         continue;
246       }
247 
248       if (Sec->getFlags() & SHF_ALLOC) {
249         Dot = alignTo(Dot, Sec->getAlign());
250         Sec->setVA(Dot);
251         Dot += Sec->getSize();
252         continue;
253       }
254     }
255   }
256 }
257 
258 template <class ELFT>
259 ArrayRef<uint8_t> LinkerScript<ELFT>::getFiller(StringRef Name) {
260   auto I = Opt.Filler.find(Name);
261   if (I == Opt.Filler.end())
262     return {};
263   return I->second;
264 }
265 
266 // Returns the index of the given section name in linker script
267 // SECTIONS commands. Sections are laid out as the same order as they
268 // were in the script. If a given name did not appear in the script,
269 // it returns INT_MAX, so that it will be laid out at end of file.
270 template <class ELFT>
271 int LinkerScript<ELFT>::getSectionIndex(StringRef Name) {
272   auto Begin = Opt.Commands.begin();
273   auto End = Opt.Commands.end();
274   auto I = std::find_if(Begin, End, [&](SectionsCommand &N) {
275     return N.Kind == SectionKind && N.SectionName == Name;
276   });
277   return I == End ? INT_MAX : (I - Begin);
278 }
279 
280 // A compartor to sort output sections. Returns -1 or 1 if
281 // A or B are mentioned in linker script. Otherwise, returns 0.
282 template <class ELFT>
283 int LinkerScript<ELFT>::compareSections(StringRef A, StringRef B) {
284   int I = getSectionIndex(A);
285   int J = getSectionIndex(B);
286   if (I == INT_MAX && J == INT_MAX)
287     return 0;
288   return I < J ? -1 : 1;
289 }
290 
291 // Returns true if S matches T. S can contain glob meta-characters.
292 // The asterisk ('*') matches zero or more characacters, and the question
293 // mark ('?') matches one character.
294 static bool matchStr(StringRef S, StringRef T) {
295   for (;;) {
296     if (S.empty())
297       return T.empty();
298     if (S[0] == '*') {
299       S = S.substr(1);
300       if (S.empty())
301         // Fast path. If a pattern is '*', it matches anything.
302         return true;
303       for (size_t I = 0, E = T.size(); I < E; ++I)
304         if (matchStr(S, T.substr(I)))
305           return true;
306       return false;
307     }
308     if (T.empty() || (S[0] != T[0] && S[0] != '?'))
309       return false;
310     S = S.substr(1);
311     T = T.substr(1);
312   }
313 }
314 
315 class elf::ScriptParser : public ScriptParserBase {
316   typedef void (ScriptParser::*Handler)();
317 
318 public:
319   ScriptParser(StringRef S, bool B) : ScriptParserBase(S), IsUnderSysroot(B) {}
320 
321   void run();
322 
323 private:
324   void addFile(StringRef Path);
325 
326   void readAsNeeded();
327   void readEntry();
328   void readExtern();
329   void readGroup();
330   void readInclude();
331   void readNothing() {}
332   void readOutput();
333   void readOutputArch();
334   void readOutputFormat();
335   void readSearchDir();
336   void readSections();
337 
338   void readLocationCounterValue();
339   void readOutputSectionDescription();
340 
341   const static StringMap<Handler> Cmd;
342   ScriptConfiguration &Opt = *ScriptConfig;
343   StringSaver Saver = {ScriptConfig->Alloc};
344   bool IsUnderSysroot;
345 };
346 
347 const StringMap<elf::ScriptParser::Handler> elf::ScriptParser::Cmd = {
348     {"ENTRY", &ScriptParser::readEntry},
349     {"EXTERN", &ScriptParser::readExtern},
350     {"GROUP", &ScriptParser::readGroup},
351     {"INCLUDE", &ScriptParser::readInclude},
352     {"INPUT", &ScriptParser::readGroup},
353     {"OUTPUT", &ScriptParser::readOutput},
354     {"OUTPUT_ARCH", &ScriptParser::readOutputArch},
355     {"OUTPUT_FORMAT", &ScriptParser::readOutputFormat},
356     {"SEARCH_DIR", &ScriptParser::readSearchDir},
357     {"SECTIONS", &ScriptParser::readSections},
358     {";", &ScriptParser::readNothing}};
359 
360 void ScriptParser::run() {
361   while (!atEOF()) {
362     StringRef Tok = next();
363     if (Handler Fn = Cmd.lookup(Tok))
364       (this->*Fn)();
365     else
366       setError("unknown directive: " + Tok);
367   }
368 }
369 
370 void ScriptParser::addFile(StringRef S) {
371   if (IsUnderSysroot && S.startswith("/")) {
372     SmallString<128> Path;
373     (Config->Sysroot + S).toStringRef(Path);
374     if (sys::fs::exists(Path)) {
375       Driver->addFile(Saver.save(Path.str()));
376       return;
377     }
378   }
379 
380   if (sys::path::is_absolute(S)) {
381     Driver->addFile(S);
382   } else if (S.startswith("=")) {
383     if (Config->Sysroot.empty())
384       Driver->addFile(S.substr(1));
385     else
386       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
387   } else if (S.startswith("-l")) {
388     Driver->addLibrary(S.substr(2));
389   } else if (sys::fs::exists(S)) {
390     Driver->addFile(S);
391   } else {
392     std::string Path = findFromSearchPaths(S);
393     if (Path.empty())
394       setError("unable to find " + S);
395     else
396       Driver->addFile(Saver.save(Path));
397   }
398 }
399 
400 void ScriptParser::readAsNeeded() {
401   expect("(");
402   bool Orig = Config->AsNeeded;
403   Config->AsNeeded = true;
404   while (!Error) {
405     StringRef Tok = next();
406     if (Tok == ")")
407       break;
408     addFile(Tok);
409   }
410   Config->AsNeeded = Orig;
411 }
412 
413 void ScriptParser::readEntry() {
414   // -e <symbol> takes predecence over ENTRY(<symbol>).
415   expect("(");
416   StringRef Tok = next();
417   if (Config->Entry.empty())
418     Config->Entry = Tok;
419   expect(")");
420 }
421 
422 void ScriptParser::readExtern() {
423   expect("(");
424   while (!Error) {
425     StringRef Tok = next();
426     if (Tok == ")")
427       return;
428     Config->Undefined.push_back(Tok);
429   }
430 }
431 
432 void ScriptParser::readGroup() {
433   expect("(");
434   while (!Error) {
435     StringRef Tok = next();
436     if (Tok == ")")
437       return;
438     if (Tok == "AS_NEEDED") {
439       readAsNeeded();
440       continue;
441     }
442     addFile(Tok);
443   }
444 }
445 
446 void ScriptParser::readInclude() {
447   StringRef Tok = next();
448   auto MBOrErr = MemoryBuffer::getFile(Tok);
449   if (!MBOrErr) {
450     setError("cannot open " + Tok);
451     return;
452   }
453   std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
454   StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
455   std::vector<StringRef> V = tokenize(S);
456   Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
457 }
458 
459 void ScriptParser::readOutput() {
460   // -o <file> takes predecence over OUTPUT(<file>).
461   expect("(");
462   StringRef Tok = next();
463   if (Config->OutputFile.empty())
464     Config->OutputFile = Tok;
465   expect(")");
466 }
467 
468 void ScriptParser::readOutputArch() {
469   // Error checking only for now.
470   expect("(");
471   next();
472   expect(")");
473 }
474 
475 void ScriptParser::readOutputFormat() {
476   // Error checking only for now.
477   expect("(");
478   next();
479   StringRef Tok = next();
480   if (Tok == ")")
481    return;
482   if (Tok != ",") {
483     setError("unexpected token: " + Tok);
484     return;
485   }
486   next();
487   expect(",");
488   next();
489   expect(")");
490 }
491 
492 void ScriptParser::readSearchDir() {
493   expect("(");
494   Config->SearchPaths.push_back(next());
495   expect(")");
496 }
497 
498 void ScriptParser::readSections() {
499   Opt.DoLayout = true;
500   expect("{");
501   while (!Error && !skip("}")) {
502     StringRef Tok = peek();
503     if (Tok == ".")
504       readLocationCounterValue();
505     else
506       readOutputSectionDescription();
507   }
508 }
509 
510 void ScriptParser::readLocationCounterValue() {
511   expect(".");
512   expect("=");
513   Opt.Commands.push_back({ExprKind, {}, ""});
514   SectionsCommand &Cmd = Opt.Commands.back();
515   while (!Error) {
516     StringRef Tok = next();
517     if (Tok == ";")
518       break;
519     Cmd.Expr.push_back(Tok);
520   }
521   if (Cmd.Expr.empty())
522     error("error in location counter expression");
523 }
524 
525 void ScriptParser::readOutputSectionDescription() {
526   StringRef OutSec = next();
527   Opt.Commands.push_back({SectionKind, {}, OutSec});
528   expect(":");
529   expect("{");
530 
531   while (!Error && !skip("}")) {
532     StringRef Tok = next();
533     if (Tok == "*") {
534       expect("(");
535       while (!Error && !skip(")"))
536         Opt.Sections.emplace_back(OutSec, next());
537     } else if (Tok == "KEEP") {
538       expect("(");
539       expect("*");
540       expect("(");
541       while (!Error && !skip(")")) {
542         StringRef Sec = next();
543         Opt.Sections.emplace_back(OutSec, Sec);
544         Opt.KeptSections.push_back(Sec);
545       }
546       expect(")");
547     } else {
548       setError("unknown command " + Tok);
549     }
550   }
551 
552   StringRef Tok = peek();
553   if (Tok.startswith("=")) {
554     if (!Tok.startswith("=0x")) {
555       setError("filler should be a hexadecimal value");
556       return;
557     }
558     Tok = Tok.substr(3);
559     Opt.Filler[OutSec] = parseHex(Tok);
560     next();
561   }
562 }
563 
564 static bool isUnderSysroot(StringRef Path) {
565   if (Config->Sysroot == "")
566     return false;
567   for (; !Path.empty(); Path = sys::path::parent_path(Path))
568     if (sys::fs::equivalent(Config->Sysroot, Path))
569       return true;
570   return false;
571 }
572 
573 // Entry point.
574 void elf::readLinkerScript(MemoryBufferRef MB) {
575   StringRef Path = MB.getBufferIdentifier();
576   ScriptParser(MB.getBuffer(), isUnderSysroot(Path)).run();
577 }
578 
579 template class elf::LinkerScript<ELF32LE>;
580 template class elf::LinkerScript<ELF32BE>;
581 template class elf::LinkerScript<ELF64LE>;
582 template class elf::LinkerScript<ELF64BE>;
583