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