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/Support/ELF.h"
24 #include "llvm/Support/FileSystem.h"
25 #include "llvm/Support/MemoryBuffer.h"
26 #include "llvm/Support/Path.h"
27 #include "llvm/Support/StringSaver.h"
28 
29 using namespace llvm;
30 using namespace llvm::ELF;
31 using namespace llvm::object;
32 using namespace lld;
33 using namespace lld::elf;
34 
35 LinkerScript *elf::Script;
36 
37 static uint64_t getInteger(StringRef S) {
38   uint64_t V;
39   if (S.getAsInteger(0, V)) {
40     error("malformed number: " + S);
41     return 0;
42   }
43   return V;
44 }
45 
46 // Evaluates the expression given by list of tokens.
47 uint64_t LinkerScript::evaluate(std::vector<StringRef> &Tokens,
48                                 uint64_t LocCounter) {
49   uint64_t Result = 0;
50   for (size_t I = 0, E = Tokens.size(); I < E; ++I) {
51     // Each second token should be '+' as this is the
52     // only operator we support now.
53     if (I % 2 == 1) {
54       if (Tokens[I] == "+")
55         continue;
56       error("error in location counter expression");
57       return 0;
58     }
59 
60     StringRef Tok = Tokens[I];
61     if (Tok == ".")
62       Result += LocCounter;
63     else
64       Result += getInteger(Tok);
65   }
66   return Result;
67 }
68 
69 template <class ELFT>
70 SectionRule *LinkerScript::find(InputSectionBase<ELFT> *S) {
71   for (SectionRule &R : Sections)
72     if (R.match(S))
73       return &R;
74   return nullptr;
75 }
76 
77 template <class ELFT>
78 StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
79   SectionRule *R = find(S);
80   return R ? R->Dest : "";
81 }
82 
83 template <class ELFT>
84 bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
85   return getOutputSection(S) == "/DISCARD/";
86 }
87 
88 template <class ELFT> bool LinkerScript::shouldKeep(InputSectionBase<ELFT> *S) {
89   SectionRule *R = find(S);
90   return R && R->Keep;
91 }
92 
93 // This method finalizes the Locations list. Adds neccesary locations for
94 // orphan sections, what prepares it for futher use without
95 // changes in LinkerScript::assignAddresses().
96 template <class ELFT>
97 void LinkerScript::fixupLocations(std::vector<OutputSectionBase<ELFT> *> &S) {
98   // Orphan sections are sections present in the input files which
99   // are not explicitly placed into the output file by the linker
100   // script. We place orphan sections at end of file. Other linkers places
101   // them using some heuristics as described in
102   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
103   for (OutputSectionBase<ELFT> *Sec : S) {
104     StringRef Name = Sec->getName();
105     auto I = std::find(SectionOrder.begin(), SectionOrder.end(), Name);
106     if (I == SectionOrder.end())
107       Locations.push_back({Command::Section, {}, {Name}});
108   }
109 }
110 
111 template <class ELFT>
112 void LinkerScript::assignAddresses(std::vector<OutputSectionBase<ELFT> *> &S) {
113   typedef typename ELFT::uint uintX_t;
114 
115   Script->fixupLocations(S);
116 
117   uintX_t ThreadBssOffset = 0;
118   uintX_t VA =
119       Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
120 
121   for (LocationNode &Node : Locations) {
122     if (Node.Type == Command::Expr) {
123       VA = evaluate(Node.Expr, VA);
124       continue;
125     }
126 
127     auto I =
128         std::find_if(S.begin(), S.end(), [&](OutputSectionBase<ELFT> *Sec) {
129           return Sec->getName() == Node.SectionName;
130         });
131     if (I == S.end())
132       continue;
133 
134     OutputSectionBase<ELFT> *Sec = *I;
135     uintX_t Align = Sec->getAlign();
136     if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
137       uintX_t TVA = VA + ThreadBssOffset;
138       TVA = alignTo(TVA, Align);
139       Sec->setVA(TVA);
140       ThreadBssOffset = TVA - VA + Sec->getSize();
141       continue;
142     }
143 
144     if (Sec->getFlags() & SHF_ALLOC) {
145       VA = alignTo(VA, Align);
146       Sec->setVA(VA);
147       VA += Sec->getSize();
148       continue;
149     }
150   }
151 }
152 
153 ArrayRef<uint8_t> LinkerScript::getFiller(StringRef Name) {
154   auto I = Filler.find(Name);
155   if (I == Filler.end())
156     return {};
157   return I->second;
158 }
159 
160 // A compartor to sort output sections. Returns -1 or 1 if both
161 // A and B are mentioned in linker scripts. Otherwise, returns 0
162 // to use the default rule which is implemented in Writer.cpp.
163 int LinkerScript::compareSections(StringRef A, StringRef B) {
164   auto E = SectionOrder.end();
165   auto I = std::find(SectionOrder.begin(), E, A);
166   auto J = std::find(SectionOrder.begin(), E, B);
167   if (I == E || J == E)
168     return 0;
169   return I < J ? -1 : 1;
170 }
171 
172 // Returns true if S matches T. S can contain glob meta-characters.
173 // The asterisk ('*') matches zero or more characacters, and the question
174 // mark ('?') matches one character.
175 static bool matchStr(StringRef S, StringRef T) {
176   for (;;) {
177     if (S.empty())
178       return T.empty();
179     if (S[0] == '*') {
180       S = S.substr(1);
181       if (S.empty())
182         // Fast path. If a pattern is '*', it matches anything.
183         return true;
184       for (size_t I = 0, E = T.size(); I < E; ++I)
185         if (matchStr(S, T.substr(I)))
186           return true;
187       return false;
188     }
189     if (T.empty() || (S[0] != T[0] && S[0] != '?'))
190       return false;
191     S = S.substr(1);
192     T = T.substr(1);
193   }
194 }
195 
196 template <class ELFT> bool SectionRule::match(InputSectionBase<ELFT> *S) {
197   return matchStr(SectionPattern, S->getSectionName());
198 }
199 
200 class elf::ScriptParser final : public elf::ScriptParserBase {
201   typedef void (ScriptParser::*Handler)();
202 
203 public:
204   ScriptParser(BumpPtrAllocator *A, StringRef S, bool B)
205       : ScriptParserBase(S), Saver(*A), IsUnderSysroot(B) {}
206 
207   void run() override;
208 
209 private:
210   void addFile(StringRef Path);
211 
212   void readAsNeeded();
213   void readEntry();
214   void readExtern();
215   void readGroup();
216   void readInclude();
217   void readNothing() {}
218   void readOutput();
219   void readOutputArch();
220   void readOutputFormat();
221   void readSearchDir();
222   void readSections();
223 
224   void readLocationCounterValue();
225   void readOutputSectionDescription();
226   void readSectionPatterns(StringRef OutSec, bool Keep);
227 
228   StringSaver Saver;
229   const static StringMap<Handler> Cmd;
230   bool IsUnderSysroot;
231 };
232 
233 const StringMap<elf::ScriptParser::Handler> elf::ScriptParser::Cmd = {
234     {"ENTRY", &ScriptParser::readEntry},
235     {"EXTERN", &ScriptParser::readExtern},
236     {"GROUP", &ScriptParser::readGroup},
237     {"INCLUDE", &ScriptParser::readInclude},
238     {"INPUT", &ScriptParser::readGroup},
239     {"OUTPUT", &ScriptParser::readOutput},
240     {"OUTPUT_ARCH", &ScriptParser::readOutputArch},
241     {"OUTPUT_FORMAT", &ScriptParser::readOutputFormat},
242     {"SEARCH_DIR", &ScriptParser::readSearchDir},
243     {"SECTIONS", &ScriptParser::readSections},
244     {";", &ScriptParser::readNothing}};
245 
246 void ScriptParser::run() {
247   while (!atEOF()) {
248     StringRef Tok = next();
249     if (Handler Fn = Cmd.lookup(Tok))
250       (this->*Fn)();
251     else
252       setError("unknown directive: " + Tok);
253   }
254 }
255 
256 void ScriptParser::addFile(StringRef S) {
257   if (IsUnderSysroot && S.startswith("/")) {
258     SmallString<128> Path;
259     (Config->Sysroot + S).toStringRef(Path);
260     if (sys::fs::exists(Path)) {
261       Driver->addFile(Saver.save(Path.str()));
262       return;
263     }
264   }
265 
266   if (sys::path::is_absolute(S)) {
267     Driver->addFile(S);
268   } else if (S.startswith("=")) {
269     if (Config->Sysroot.empty())
270       Driver->addFile(S.substr(1));
271     else
272       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
273   } else if (S.startswith("-l")) {
274     Driver->addLibrary(S.substr(2));
275   } else if (sys::fs::exists(S)) {
276     Driver->addFile(S);
277   } else {
278     std::string Path = findFromSearchPaths(S);
279     if (Path.empty())
280       setError("unable to find " + S);
281     else
282       Driver->addFile(Saver.save(Path));
283   }
284 }
285 
286 void ScriptParser::readAsNeeded() {
287   expect("(");
288   bool Orig = Config->AsNeeded;
289   Config->AsNeeded = true;
290   while (!Error) {
291     StringRef Tok = next();
292     if (Tok == ")")
293       break;
294     addFile(Tok);
295   }
296   Config->AsNeeded = Orig;
297 }
298 
299 void ScriptParser::readEntry() {
300   // -e <symbol> takes predecence over ENTRY(<symbol>).
301   expect("(");
302   StringRef Tok = next();
303   if (Config->Entry.empty())
304     Config->Entry = Tok;
305   expect(")");
306 }
307 
308 void ScriptParser::readExtern() {
309   expect("(");
310   while (!Error) {
311     StringRef Tok = next();
312     if (Tok == ")")
313       return;
314     Config->Undefined.push_back(Tok);
315   }
316 }
317 
318 void ScriptParser::readGroup() {
319   expect("(");
320   while (!Error) {
321     StringRef Tok = next();
322     if (Tok == ")")
323       return;
324     if (Tok == "AS_NEEDED") {
325       readAsNeeded();
326       continue;
327     }
328     addFile(Tok);
329   }
330 }
331 
332 void ScriptParser::readInclude() {
333   StringRef Tok = next();
334   auto MBOrErr = MemoryBuffer::getFile(Tok);
335   if (!MBOrErr) {
336     setError("cannot open " + Tok);
337     return;
338   }
339   std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
340   StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
341   std::vector<StringRef> V = tokenize(S);
342   Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
343 }
344 
345 void ScriptParser::readOutput() {
346   // -o <file> takes predecence over OUTPUT(<file>).
347   expect("(");
348   StringRef Tok = next();
349   if (Config->OutputFile.empty())
350     Config->OutputFile = Tok;
351   expect(")");
352 }
353 
354 void ScriptParser::readOutputArch() {
355   // Error checking only for now.
356   expect("(");
357   next();
358   expect(")");
359 }
360 
361 void ScriptParser::readOutputFormat() {
362   // Error checking only for now.
363   expect("(");
364   next();
365   StringRef Tok = next();
366   if (Tok == ")")
367    return;
368   if (Tok != ",") {
369     setError("unexpected token: " + Tok);
370     return;
371   }
372   next();
373   expect(",");
374   next();
375   expect(")");
376 }
377 
378 void ScriptParser::readSearchDir() {
379   expect("(");
380   Config->SearchPaths.push_back(next());
381   expect(")");
382 }
383 
384 void ScriptParser::readSections() {
385   Script->DoLayout = true;
386   expect("{");
387   while (!Error && !skip("}")) {
388     StringRef Tok = peek();
389     if (Tok == ".")
390       readLocationCounterValue();
391     else
392       readOutputSectionDescription();
393   }
394 }
395 
396 void ScriptParser::readSectionPatterns(StringRef OutSec, bool Keep) {
397   expect("(");
398   while (!Error && !skip(")"))
399     Script->Sections.emplace_back(OutSec, next(), Keep);
400 }
401 
402 void ScriptParser::readLocationCounterValue() {
403   expect(".");
404   expect("=");
405   Script->Locations.push_back({Command::Expr, {}, {}});
406   LocationNode &Node = Script->Locations.back();
407   while (!Error) {
408     StringRef Tok = next();
409     if (Tok == ";")
410       break;
411     Node.Expr.push_back(Tok);
412   }
413   if (Node.Expr.empty())
414     error("error in location counter expression");
415 }
416 
417 void ScriptParser::readOutputSectionDescription() {
418   StringRef OutSec = next();
419   Script->SectionOrder.push_back(OutSec);
420   Script->Locations.push_back({Command::Section, {}, {OutSec}});
421   expect(":");
422   expect("{");
423   while (!Error && !skip("}")) {
424     StringRef Tok = next();
425     if (Tok == "*") {
426       readSectionPatterns(OutSec, false);
427     } else if (Tok == "KEEP") {
428       expect("(");
429       next(); // Skip *
430       readSectionPatterns(OutSec, true);
431       expect(")");
432     } else {
433       setError("unknown command " + Tok);
434     }
435   }
436   StringRef Tok = peek();
437   if (Tok.startswith("=")) {
438     if (!Tok.startswith("=0x")) {
439       setError("filler should be a hexadecimal value");
440       return;
441     }
442     Tok = Tok.substr(3);
443     Script->Filler[OutSec] = parseHex(Tok);
444     next();
445   }
446 }
447 
448 static bool isUnderSysroot(StringRef Path) {
449   if (Config->Sysroot == "")
450     return false;
451   for (; !Path.empty(); Path = sys::path::parent_path(Path))
452     if (sys::fs::equivalent(Config->Sysroot, Path))
453       return true;
454   return false;
455 }
456 
457 // Entry point. The other functions or classes are private to this file.
458 void LinkerScript::read(MemoryBufferRef MB) {
459   StringRef Path = MB.getBufferIdentifier();
460   ScriptParser(&Alloc, MB.getBuffer(), isUnderSysroot(Path)).run();
461 }
462 
463 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32LE> *);
464 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32BE> *);
465 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64LE> *);
466 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64BE> *);
467 
468 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32LE> *);
469 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32BE> *);
470 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64LE> *);
471 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64BE> *);
472 
473 template bool LinkerScript::shouldKeep(InputSectionBase<ELF32LE> *);
474 template bool LinkerScript::shouldKeep(InputSectionBase<ELF32BE> *);
475 template bool LinkerScript::shouldKeep(InputSectionBase<ELF64LE> *);
476 template bool LinkerScript::shouldKeep(InputSectionBase<ELF64BE> *);
477 
478 template void
479 LinkerScript::assignAddresses(std::vector<OutputSectionBase<ELF32LE> *> &);
480 template void
481 LinkerScript::assignAddresses(std::vector<OutputSectionBase<ELF32BE> *> &);
482 template void
483 LinkerScript::assignAddresses(std::vector<OutputSectionBase<ELF64LE> *> &);
484 template void
485 LinkerScript::assignAddresses(std::vector<OutputSectionBase<ELF64BE> *> &);
486