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