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 "SymbolTable.h"
21 #include "llvm/Support/FileSystem.h"
22 #include "llvm/Support/MemoryBuffer.h"
23 #include "llvm/Support/Path.h"
24 #include "llvm/Support/StringSaver.h"
25 
26 using namespace llvm;
27 using namespace llvm::object;
28 using namespace lld;
29 using namespace lld::elf2;
30 
31 LinkerScript *elf2::Script;
32 
33 template <class ELFT>
34 StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
35   for (SectionRule &R : Sections)
36     if (R.match(S))
37       return R.Dest;
38   return "";
39 }
40 
41 template <class ELFT>
42 bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
43   return getOutputSection(S) == "/DISCARD/";
44 }
45 
46 // A compartor to sort output sections. Returns -1 or 1 if both
47 // A and B are mentioned in linker scripts. Otherwise, returns 0
48 // to use the default rule which is implemented in Writer.cpp.
49 int LinkerScript::compareSections(StringRef A, StringRef B) {
50   auto E = SectionOrder.end();
51   auto I = std::find(SectionOrder.begin(), E, A);
52   auto J = std::find(SectionOrder.begin(), E, B);
53   if (I == E || J == E)
54     return 0;
55   return I < J ? -1 : 1;
56 }
57 
58 // Returns true if S matches T. S may contain a meta character '*'
59 // which matches zero or more occurrences of any character.
60 static bool matchStr(StringRef S, StringRef T) {
61   for (;;) {
62     if (S.empty())
63       return T.empty();
64     if (S[0] == '*') {
65       S = S.substr(1);
66       if (S.empty())
67         // Fast path. If a pattern is '*', it matches anything.
68         return true;
69       for (size_t I = 0, E = T.size(); I < E; ++I)
70         if (matchStr(S, T.substr(I)))
71           return true;
72       return false;
73     }
74     if (T.empty() || S[0] != T[0])
75       return false;
76     S = S.substr(1);
77     T = T.substr(1);
78   }
79 }
80 
81 template <class ELFT> bool SectionRule::match(InputSectionBase<ELFT> *S) {
82   return matchStr(SectionPattern, S->getSectionName());
83 }
84 
85 class elf2::ScriptParser {
86 public:
87   ScriptParser(BumpPtrAllocator *A, StringRef S, bool B)
88       : Saver(*A), Tokens(tokenize(S)), IsUnderSysroot(B) {}
89   void run();
90 
91 private:
92   void setError(const Twine &Msg);
93   static std::vector<StringRef> tokenize(StringRef S);
94   static StringRef skipSpace(StringRef S);
95   bool atEOF();
96   StringRef next();
97   bool skip(StringRef Tok);
98   void expect(StringRef Expect);
99 
100   void addFile(StringRef Path);
101 
102   void readAsNeeded();
103   void readEntry();
104   void readExtern();
105   void readGroup();
106   void readInclude();
107   void readOutput();
108   void readOutputArch();
109   void readOutputFormat();
110   void readSearchDir();
111   void readSections();
112 
113   void readOutputSectionDescription();
114 
115   StringSaver Saver;
116   std::vector<StringRef> Tokens;
117   bool Error = false;
118   size_t Pos = 0;
119   bool IsUnderSysroot;
120 };
121 
122 void ScriptParser::run() {
123   while (!atEOF()) {
124     StringRef Tok = next();
125     if (Tok == ";")
126       continue;
127     if (Tok == "ENTRY") {
128       readEntry();
129     } else if (Tok == "EXTERN") {
130       readExtern();
131     } else if (Tok == "GROUP" || Tok == "INPUT") {
132       readGroup();
133     } else if (Tok == "INCLUDE") {
134       readInclude();
135     } else if (Tok == "OUTPUT") {
136       readOutput();
137     } else if (Tok == "OUTPUT_ARCH") {
138       readOutputArch();
139     } else if (Tok == "OUTPUT_FORMAT") {
140       readOutputFormat();
141     } else if (Tok == "SEARCH_DIR") {
142       readSearchDir();
143     } else if (Tok == "SECTIONS") {
144       readSections();
145     } else {
146       setError("unknown directive: " + Tok);
147       return;
148     }
149   }
150 }
151 
152 // We don't want to record cascading errors. Keep only the first one.
153 void ScriptParser::setError(const Twine &Msg) {
154   if (Error)
155     return;
156   error(Msg);
157   Error = true;
158 }
159 
160 // Split S into linker script tokens.
161 std::vector<StringRef> ScriptParser::tokenize(StringRef S) {
162   std::vector<StringRef> Ret;
163   for (;;) {
164     S = skipSpace(S);
165     if (S.empty())
166       return Ret;
167 
168     // Quoted token
169     if (S.startswith("\"")) {
170       size_t E = S.find("\"", 1);
171       if (E == StringRef::npos) {
172         error("unclosed quote");
173         return {};
174       }
175       Ret.push_back(S.substr(1, E - 1));
176       S = S.substr(E + 1);
177       continue;
178     }
179 
180     // Unquoted token
181     size_t Pos = S.find_first_not_of(
182         "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
183         "0123456789_.$/\\~=+[]*?-:");
184     // A character that cannot start a word (which is usually a
185     // punctuation) forms a single character token.
186     if (Pos == 0)
187       Pos = 1;
188     Ret.push_back(S.substr(0, Pos));
189     S = S.substr(Pos);
190   }
191 }
192 
193 // Skip leading whitespace characters or /**/-style comments.
194 StringRef ScriptParser::skipSpace(StringRef S) {
195   for (;;) {
196     if (S.startswith("/*")) {
197       size_t E = S.find("*/", 2);
198       if (E == StringRef::npos) {
199         error("unclosed comment in a linker script");
200         return "";
201       }
202       S = S.substr(E + 2);
203       continue;
204     }
205     size_t Size = S.size();
206     S = S.ltrim();
207     if (S.size() == Size)
208       return S;
209   }
210 }
211 
212 // An errneous token is handled as if it were the last token before EOF.
213 bool ScriptParser::atEOF() { return Error || Tokens.size() == Pos; }
214 
215 StringRef ScriptParser::next() {
216   if (Error)
217     return "";
218   if (atEOF()) {
219     setError("unexpected EOF");
220     return "";
221   }
222   return Tokens[Pos++];
223 }
224 
225 bool ScriptParser::skip(StringRef Tok) {
226   if (Error)
227     return false;
228   if (atEOF()) {
229     setError("unexpected EOF");
230     return false;
231   }
232   if (Tok != Tokens[Pos])
233     return false;
234   ++Pos;
235   return true;
236 }
237 
238 void ScriptParser::expect(StringRef Expect) {
239   if (Error)
240     return;
241   StringRef Tok = next();
242   if (Tok != Expect)
243     setError(Expect + " expected, but got " + Tok);
244 }
245 
246 void ScriptParser::addFile(StringRef S) {
247   if (IsUnderSysroot && S.startswith("/")) {
248     SmallString<128> Path;
249     (Config->Sysroot + S).toStringRef(Path);
250     if (sys::fs::exists(Path)) {
251       Driver->addFile(Saver.save(Path.str()));
252       return;
253     }
254   }
255 
256   if (sys::path::is_absolute(S)) {
257     Driver->addFile(S);
258   } else if (S.startswith("=")) {
259     if (Config->Sysroot.empty())
260       Driver->addFile(S.substr(1));
261     else
262       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
263   } else if (S.startswith("-l")) {
264     Driver->addLibrary(S.substr(2));
265   } else if (sys::fs::exists(S)) {
266     Driver->addFile(S);
267   } else {
268     std::string Path = findFromSearchPaths(S);
269     if (Path.empty())
270       setError("Unable to find " + S);
271     else
272       Driver->addFile(Saver.save(Path));
273   }
274 }
275 
276 void ScriptParser::readAsNeeded() {
277   expect("(");
278   bool Orig = Config->AsNeeded;
279   Config->AsNeeded = true;
280   while (!Error) {
281     StringRef Tok = next();
282     if (Tok == ")")
283       break;
284     addFile(Tok);
285   }
286   Config->AsNeeded = Orig;
287 }
288 
289 void ScriptParser::readEntry() {
290   // -e <symbol> takes predecence over ENTRY(<symbol>).
291   expect("(");
292   StringRef Tok = next();
293   if (Config->Entry.empty())
294     Config->Entry = Tok;
295   expect(")");
296 }
297 
298 void ScriptParser::readExtern() {
299   expect("(");
300   while (!Error) {
301     StringRef Tok = next();
302     if (Tok == ")")
303       return;
304     Config->Undefined.push_back(Tok);
305   }
306 }
307 
308 void ScriptParser::readGroup() {
309   expect("(");
310   while (!Error) {
311     StringRef Tok = next();
312     if (Tok == ")")
313       return;
314     if (Tok == "AS_NEEDED") {
315       readAsNeeded();
316       continue;
317     }
318     addFile(Tok);
319   }
320 }
321 
322 void ScriptParser::readInclude() {
323   StringRef Tok = next();
324   auto MBOrErr = MemoryBuffer::getFile(Tok);
325   if (!MBOrErr) {
326     setError("cannot open " + Tok);
327     return;
328   }
329   std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
330   StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
331   std::vector<StringRef> V = tokenize(S);
332   Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
333 }
334 
335 void ScriptParser::readOutput() {
336   // -o <file> takes predecence over OUTPUT(<file>).
337   expect("(");
338   StringRef Tok = next();
339   if (Config->OutputFile.empty())
340     Config->OutputFile = Tok;
341   expect(")");
342 }
343 
344 void ScriptParser::readOutputArch() {
345   // Error checking only for now.
346   expect("(");
347   next();
348   expect(")");
349 }
350 
351 void ScriptParser::readOutputFormat() {
352   // Error checking only for now.
353   expect("(");
354   next();
355   StringRef Tok = next();
356   if (Tok == ")")
357    return;
358   if (Tok != ",") {
359     setError("unexpected token: " + Tok);
360     return;
361   }
362   next();
363   expect(",");
364   next();
365   expect(")");
366 }
367 
368 void ScriptParser::readSearchDir() {
369   expect("(");
370   Config->SearchPaths.push_back(next());
371   expect(")");
372 }
373 
374 void ScriptParser::readSections() {
375   expect("{");
376   while (!Error && !skip("}"))
377     readOutputSectionDescription();
378 }
379 
380 void ScriptParser::readOutputSectionDescription() {
381   StringRef OutSec = next();
382   Script->SectionOrder.push_back(OutSec);
383   expect(":");
384   expect("{");
385   while (!Error && !skip("}")) {
386     next(); // Skip input file name.
387     expect("(");
388     while (!Error && !skip(")"))
389       Script->Sections.push_back({OutSec, next()});
390   }
391 }
392 
393 static bool isUnderSysroot(StringRef Path) {
394   if (Config->Sysroot == "")
395     return false;
396   for (; !Path.empty(); Path = sys::path::parent_path(Path))
397     if (sys::fs::equivalent(Config->Sysroot, Path))
398       return true;
399   return false;
400 }
401 
402 // Entry point. The other functions or classes are private to this file.
403 void LinkerScript::read(MemoryBufferRef MB) {
404   StringRef Path = MB.getBufferIdentifier();
405   ScriptParser(&Alloc, MB.getBuffer(), isUnderSysroot(Path)).run();
406 }
407 
408 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32LE> *);
409 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32BE> *);
410 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64LE> *);
411 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64BE> *);
412 
413 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32LE> *);
414 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32BE> *);
415 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64LE> *);
416 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64BE> *);
417 
418 template bool SectionRule::match(InputSectionBase<ELF32LE> *);
419 template bool SectionRule::match(InputSectionBase<ELF32BE> *);
420 template bool SectionRule::match(InputSectionBase<ELF64LE> *);
421 template bool SectionRule::match(InputSectionBase<ELF64BE> *);
422