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