Coverage Report

Created: 2018-08-19 14:04

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/lld/ELF/ScriptParser.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ScriptParser.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 a recursive-descendent parser for linker scripts.
11
// Parsed results are stored to Config and Script global objects.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "ScriptParser.h"
16
#include "Config.h"
17
#include "Driver.h"
18
#include "InputSection.h"
19
#include "LinkerScript.h"
20
#include "OutputSections.h"
21
#include "ScriptLexer.h"
22
#include "Symbols.h"
23
#include "Target.h"
24
#include "lld/Common/Memory.h"
25
#include "llvm/ADT/SmallString.h"
26
#include "llvm/ADT/StringRef.h"
27
#include "llvm/ADT/StringSet.h"
28
#include "llvm/ADT/StringSwitch.h"
29
#include "llvm/BinaryFormat/ELF.h"
30
#include "llvm/Support/Casting.h"
31
#include "llvm/Support/ErrorHandling.h"
32
#include "llvm/Support/FileSystem.h"
33
#include "llvm/Support/Path.h"
34
#include <cassert>
35
#include <limits>
36
#include <vector>
37
38
using namespace llvm;
39
using namespace llvm::ELF;
40
using namespace llvm::support::endian;
41
using namespace lld;
42
using namespace lld::elf;
43
44
static bool isUnderSysroot(StringRef Path);
45
46
namespace {
47
class ScriptParser final : ScriptLexer {
48
public:
49
  ScriptParser(MemoryBufferRef MB)
50
      : ScriptLexer(MB),
51
703
        IsUnderSysroot(isUnderSysroot(MB.getBufferIdentifier())) {}
52
53
  void readLinkerScript();
54
  void readVersionScript();
55
  void readDynamicList();
56
  void readDefsym(StringRef Name);
57
58
private:
59
  void addFile(StringRef Path);
60
61
  void readAsNeeded();
62
  void readEntry();
63
  void readExtern();
64
  void readGroup();
65
  void readInclude();
66
  void readInput();
67
  void readMemory();
68
  void readOutput();
69
  void readOutputArch();
70
  void readOutputFormat();
71
  void readPhdrs();
72
  void readRegionAlias();
73
  void readSearchDir();
74
  void readSections();
75
  void readTarget();
76
  void readVersion();
77
  void readVersionScriptCommand();
78
79
  SymbolAssignment *readSymbolAssignment(StringRef Name);
80
  ByteCommand *readByteCommand(StringRef Tok);
81
  uint32_t readFill();
82
  uint32_t parseFill(StringRef Tok);
83
  void readSectionAddressType(OutputSection *Cmd);
84
  OutputSection *readOverlaySectionDescription();
85
  OutputSection *readOutputSectionDescription(StringRef OutSec);
86
  std::vector<BaseCommand *> readOverlay();
87
  std::vector<StringRef> readOutputSectionPhdrs();
88
  InputSectionDescription *readInputSectionDescription(StringRef Tok);
89
  StringMatcher readFilePatterns();
90
  std::vector<SectionPattern> readInputSectionsList();
91
  InputSectionDescription *readInputSectionRules(StringRef FilePattern);
92
  unsigned readPhdrType();
93
  SortSectionPolicy readSortKind();
94
  SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
95
  SymbolAssignment *readAssignment(StringRef Tok);
96
  void readSort();
97
  Expr readAssert();
98
  Expr readConstant();
99
  Expr getPageSize();
100
101
  uint64_t readMemoryAssignment(StringRef, StringRef, StringRef);
102
  std::pair<uint32_t, uint32_t> readMemoryAttributes();
103
104
  Expr combine(StringRef Op, Expr L, Expr R);
105
  Expr readExpr();
106
  Expr readExpr1(Expr Lhs, int MinPrec);
107
  StringRef readParenLiteral();
108
  Expr readPrimary();
109
  Expr readTernary(Expr Cond);
110
  Expr readParenExpr();
111
112
  // For parsing version script.
113
  std::vector<SymbolVersion> readVersionExtern();
114
  void readAnonymousDeclaration();
115
  void readVersionDeclaration(StringRef VerStr);
116
117
  std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
118
  readSymbols();
119
120
  // True if a script being read is in a subdirectory specified by -sysroot.
121
  bool IsUnderSysroot;
122
123
  // A set to detect an INCLUDE() cycle.
124
  StringSet<> Seen;
125
};
126
} // namespace
127
128
266
static StringRef unquote(StringRef S) {
129
266
  if (S.startswith("\""))
130
77
    return S.substr(1, S.size() - 2);
131
189
  return S;
132
189
}
133
134
703
static bool isUnderSysroot(StringRef Path) {
135
703
  if (Config->Sysroot == "")
136
696
    return false;
137
40
  
for (; 7
!Path.empty();
Path = sys::path::parent_path(Path)33
)
138
34
    if (sys::fs::equivalent(Config->Sysroot, Path))
139
1
      return true;
140
7
  
return false6
;
141
7
}
142
143
// Some operations only support one non absolute value. Move the
144
// absolute one to the right hand side for convenience.
145
171
static void moveAbsRight(ExprValue &A, ExprValue &B) {
146
171
  if (A.Sec == nullptr || 
(81
A.ForceAbsolute81
&&
!B.isAbsolute()9
))
147
92
    std::swap(A, B);
148
171
  if (!B.isAbsolute())
149
1
    error(A.Loc + ": at least one side of the expression must be absolute");
150
171
}
151
152
143
static ExprValue add(ExprValue A, ExprValue B) {
153
143
  moveAbsRight(A, B);
154
143
  return {A.Sec, A.ForceAbsolute, A.getSectionOffset() + B.getValue(), A.Loc};
155
143
}
156
157
34
static ExprValue sub(ExprValue A, ExprValue B) {
158
34
  // The distance between two symbols in sections is absolute.
159
34
  if (!A.isAbsolute() && 
!B.isAbsolute()19
)
160
2
    return A.getValue() - B.getValue();
161
32
  return {A.Sec, false, A.getSectionOffset() - B.getValue(), A.Loc};
162
32
}
163
164
13
static ExprValue bitAnd(ExprValue A, ExprValue B) {
165
13
  moveAbsRight(A, B);
166
13
  return {A.Sec, A.ForceAbsolute,
167
13
          (A.getValue() & B.getValue()) - A.getSecAddr(), A.Loc};
168
13
}
169
170
15
static ExprValue bitOr(ExprValue A, ExprValue B) {
171
15
  moveAbsRight(A, B);
172
15
  return {A.Sec, A.ForceAbsolute,
173
15
          (A.getValue() | B.getValue()) - A.getSecAddr(), A.Loc};
174
15
}
175
176
24
void ScriptParser::readDynamicList() {
177
24
  Config->HasDynamicList = true;
178
24
  expect("{");
179
24
  std::vector<SymbolVersion> Locals;
180
24
  std::vector<SymbolVersion> Globals;
181
24
  std::tie(Locals, Globals) = readSymbols();
182
24
  expect(";");
183
24
184
24
  if (!atEOF()) {
185
1
    setError("EOF expected, but got " + next());
186
1
    return;
187
1
  }
188
23
  if (!Locals.empty()) {
189
1
    setError("\"local:\" scope not supported in --dynamic-list");
190
1
    return;
191
1
  }
192
22
193
22
  for (SymbolVersion V : Globals)
194
26
    Config->DynamicList.push_back(V);
195
22
}
196
197
81
void ScriptParser::readVersionScript() {
198
81
  readVersionScriptCommand();
199
81
  if (!atEOF())
200
1
    setError("EOF expected, but got " + next());
201
81
}
202
203
86
void ScriptParser::readVersionScriptCommand() {
204
86
  if (consume("{")) {
205
23
    readAnonymousDeclaration();
206
23
    return;
207
23
  }
208
63
209
151
  
while (63
!atEOF() &&
!errorCount()94
&&
peek() != "}"94
) {
210
89
    StringRef VerStr = next();
211
89
    if (VerStr == "{") {
212
1
      setError("anonymous version definition is used in "
213
1
               "combination with other version definitions");
214
1
      return;
215
1
    }
216
88
    expect("{");
217
88
    readVersionDeclaration(VerStr);
218
88
  }
219
63
}
220
221
5
void ScriptParser::readVersion() {
222
5
  expect("{");
223
5
  readVersionScriptCommand();
224
5
  expect("}");
225
5
}
226
227
570
void ScriptParser::readLinkerScript() {
228
1.26k
  while (!atEOF()) {
229
696
    StringRef Tok = next();
230
696
    if (Tok == ";")
231
39
      continue;
232
657
233
657
    if (Tok == "ENTRY") {
234
6
      readEntry();
235
651
    } else if (Tok == "EXTERN") {
236
5
      readExtern();
237
646
    } else if (Tok == "GROUP") {
238
22
      readGroup();
239
624
    } else if (Tok == "INCLUDE") {
240
17
      readInclude();
241
607
    } else if (Tok == "INPUT") {
242
6
      readInput();
243
601
    } else if (Tok == "MEMORY") {
244
39
      readMemory();
245
562
    } else if (Tok == "OUTPUT") {
246
7
      readOutput();
247
555
    } else if (Tok == "OUTPUT_ARCH") {
248
1
      readOutputArch();
249
554
    } else if (Tok == "OUTPUT_FORMAT") {
250
4
      readOutputFormat();
251
550
    } else if (Tok == "PHDRS") {
252
32
      readPhdrs();
253
518
    } else if (Tok == "REGION_ALIAS") {
254
8
      readRegionAlias();
255
510
    } else if (Tok == "SEARCH_DIR") {
256
6
      readSearchDir();
257
504
    } else if (Tok == "SECTIONS") {
258
459
      readSections();
259
459
    } else 
if (45
Tok == "TARGET"45
) {
260
3
      readTarget();
261
42
    } else if (Tok == "VERSION") {
262
5
      readVersion();
263
37
    } else if (SymbolAssignment *Cmd = readAssignment(Tok)) {
264
34
      Script->SectionCommands.push_back(Cmd);
265
34
    } else {
266
3
      setError("unknown directive: " + Tok);
267
3
    }
268
657
  }
269
570
}
270
271
28
void ScriptParser::readDefsym(StringRef Name) {
272
28
  Expr E = readExpr();
273
28
  if (!atEOF())
274
1
    setError("EOF expected, but got " + next());
275
28
  SymbolAssignment *Cmd = make<SymbolAssignment>(Name, E, getCurrentLocation());
276
28
  Script->SectionCommands.push_back(Cmd);
277
28
}
278
279
45
void ScriptParser::addFile(StringRef S) {
280
45
  if (IsUnderSysroot && 
S.startswith("/")2
) {
281
2
    SmallString<128> PathData;
282
2
    StringRef Path = (Config->Sysroot + S).toStringRef(PathData);
283
2
    if (sys::fs::exists(Path)) {
284
1
      Driver->addFile(Saver.save(Path), /*WithLOption=*/false);
285
1
      return;
286
1
    }
287
44
  }
288
44
289
44
  if (S.startswith("/")) {
290
36
    Driver->addFile(S, /*WithLOption=*/false);
291
36
  } else 
if (8
S.startswith("=")8
) {
292
2
    if (Config->Sysroot.empty())
293
1
      Driver->addFile(S.substr(1), /*WithLOption=*/false);
294
1
    else
295
1
      Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)),
296
1
                      /*WithLOption=*/false);
297
6
  } else if (S.startswith("-l")) {
298
2
    Driver->addLibrary(S.substr(2));
299
4
  } else if (sys::fs::exists(S)) {
300
0
    Driver->addFile(S, /*WithLOption=*/false);
301
4
  } else {
302
4
    if (Optional<std::string> Path = findFromSearchPaths(S))
303
2
      Driver->addFile(Saver.save(*Path), /*WithLOption=*/true);
304
2
    else
305
2
      setError("unable to find " + S);
306
4
  }
307
44
}
308
309
2
void ScriptParser::readAsNeeded() {
310
2
  expect("(");
311
2
  bool Orig = Config->AsNeeded;
312
2
  Config->AsNeeded = true;
313
6
  while (!errorCount() && !consume(")"))
314
4
    addFile(unquote(next()));
315
2
  Config->AsNeeded = Orig;
316
2
}
317
318
6
void ScriptParser::readEntry() {
319
6
  // -e <symbol> takes predecence over ENTRY(<symbol>).
320
6
  expect("(");
321
6
  StringRef Tok = next();
322
6
  if (Config->Entry.empty())
323
5
    Config->Entry = Tok;
324
6
  expect(")");
325
6
}
326
327
5
void ScriptParser::readExtern() {
328
5
  expect("(");
329
11
  while (!errorCount() && 
!consume(")")8
)
330
6
    Config->Undefined.push_back(next());
331
5
}
332
333
22
void ScriptParser::readGroup() {
334
22
  bool Orig = InputFile::IsInGroup;
335
22
  InputFile::IsInGroup = true;
336
22
  readInput();
337
22
  InputFile::IsInGroup = Orig;
338
22
  if (!Orig)
339
20
    ++InputFile::NextGroupId;
340
22
}
341
342
17
void ScriptParser::readInclude() {
343
17
  StringRef Tok = unquote(next());
344
17
345
17
  if (!Seen.insert(Tok).second) {
346
2
    setError("there is a cycle in linker script INCLUDEs");
347
2
    return;
348
2
  }
349
15
350
15
  if (Optional<std::string> Path = searchScript(Tok)) {
351
13
    if (Optional<MemoryBufferRef> MB = readFile(*Path))
352
13
      tokenize(*MB);
353
13
    return;
354
13
  }
355
2
  setError("cannot find linker script " + Tok);
356
2
}
357
358
28
void ScriptParser::readInput() {
359
28
  expect("(");
360
71
  while (!errorCount() && 
!consume(")")65
) {
361
43
    if (consume("AS_NEEDED"))
362
2
      readAsNeeded();
363
41
    else
364
41
      addFile(unquote(next()));
365
43
  }
366
28
}
367
368
7
void ScriptParser::readOutput() {
369
7
  // -o <file> takes predecence over OUTPUT(<file>).
370
7
  expect("(");
371
7
  StringRef Tok = next();
372
7
  if (Config->OutputFile.empty())
373
6
    Config->OutputFile = unquote(Tok);
374
7
  expect(")");
375
7
}
376
377
1
void ScriptParser::readOutputArch() {
378
1
  // OUTPUT_ARCH is ignored for now.
379
1
  expect("(");
380
7
  while (!errorCount() && !consume(")"))
381
6
    skip();
382
1
}
383
384
4
void ScriptParser::readOutputFormat() {
385
4
  // Error checking only for now.
386
4
  expect("(");
387
4
  skip();
388
4
  if (consume(")"))
389
1
    return;
390
3
  expect(",");
391
3
  skip();
392
3
  expect(",");
393
3
  skip();
394
3
  expect(")");
395
3
}
396
397
32
void ScriptParser::readPhdrs() {
398
32
  expect("{");
399
32
400
73
  while (!errorCount() && 
!consume("}")71
) {
401
41
    PhdrsCommand Cmd;
402
41
    Cmd.Name = next();
403
41
    Cmd.Type = readPhdrType();
404
41
405
79
    while (!errorCount() && 
!consume(";")77
) {
406
38
      if (consume("FILEHDR"))
407
12
        Cmd.HasFilehdr = true;
408
26
      else if (consume("PHDRS"))
409
15
        Cmd.HasPhdrs = true;
410
11
      else if (consume("AT"))
411
1
        Cmd.LMAExpr = readParenExpr();
412
10
      else if (consume("FLAGS"))
413
9
        Cmd.Flags = readParenExpr()().getValue();
414
1
      else
415
1
        setError("unexpected header attribute: " + next());
416
38
    }
417
41
418
41
    Script->PhdrsCommands.push_back(Cmd);
419
41
  }
420
32
}
421
422
8
void ScriptParser::readRegionAlias() {
423
8
  expect("(");
424
8
  StringRef Alias = unquote(next());
425
8
  expect(",");
426
8
  StringRef Name = next();
427
8
  expect(")");
428
8
429
8
  if (Script->MemoryRegions.count(Alias))
430
2
    setError("redefinition of memory region '" + Alias + "'");
431
8
  if (!Script->MemoryRegions.count(Name))
432
1
    setError("memory region '" + Name + "' is not defined");
433
8
  Script->MemoryRegions.insert({Alias, Script->MemoryRegions[Name]});
434
8
}
435
436
6
void ScriptParser::readSearchDir() {
437
6
  expect("(");
438
6
  StringRef Tok = next();
439
6
  if (!Config->Nostdlib)
440
5
    Config->SearchPaths.push_back(unquote(Tok));
441
6
  expect(")");
442
6
}
443
444
// This reads an overlay description. Overlays are used to describe output
445
// sections that use the same virtual memory range and normally would trigger
446
// linker's sections sanity check failures.
447
// https://sourceware.org/binutils/docs/ld/Overlay-Description.html#Overlay-Description
448
3
std::vector<BaseCommand *> ScriptParser::readOverlay() {
449
3
  // VA and LMA expressions are optional, though for simplicity of
450
3
  // implementation we assume they are not. That is what OVERLAY was designed
451
3
  // for first of all: to allow sections with overlapping VAs at different LMAs.
452
3
  Expr AddrExpr = readExpr();
453
3
  expect(":");
454
3
  expect("AT");
455
3
  Expr LMAExpr = readParenExpr();
456
3
  expect("{");
457
3
458
3
  std::vector<BaseCommand *> V;
459
3
  OutputSection *Prev = nullptr;
460
8
  while (!errorCount() && 
!consume("}")6
) {
461
5
    // VA is the same for all sections. The LMAs are consecutive in memory
462
5
    // starting from the base load address specified.
463
5
    OutputSection *OS = readOverlaySectionDescription();
464
5
    OS->AddrExpr = AddrExpr;
465
5
    if (Prev)
466
2
      OS->LMAExpr = [=] 
{ return Prev->getLMA() + Prev->Size; }1
;
467
3
    else
468
3
      OS->LMAExpr = LMAExpr;
469
5
    V.push_back(OS);
470
5
    Prev = OS;
471
5
  }
472
3
473
3
  // According to the specification, at the end of the overlay, the location
474
3
  // counter should be equal to the overlay base address plus size of the
475
3
  // largest section seen in the overlay.
476
3
  // Here we want to create the Dot assignment command to achieve that.
477
3
  Expr MoveDot = [=] {
478
1
    uint64_t Max = 0;
479
1
    for (BaseCommand *Cmd : V)
480
2
      Max = std::max(Max, cast<OutputSection>(Cmd)->Size);
481
1
    return AddrExpr().getValue() + Max;
482
1
  };
483
3
  V.push_back(make<SymbolAssignment>(".", MoveDot, getCurrentLocation()));
484
3
  return V;
485
3
}
486
487
459
void ScriptParser::readSections() {
488
459
  Script->HasSectionsCommand = true;
489
459
490
459
  // -no-rosegment is used to avoid placing read only non-executable sections in
491
459
  // their own segment. We do the same if SECTIONS command is present in linker
492
459
  // script. See comment for computeFlags().
493
459
  Config->SingleRoRx = true;
494
459
495
459
  expect("{");
496
459
  std::vector<BaseCommand *> V;
497
1.47k
  while (!errorCount() && 
!consume("}")1.45k
) {
498
1.02k
    StringRef Tok = next();
499
1.02k
    if (Tok == "OVERLAY") {
500
3
      for (BaseCommand *Cmd : readOverlay())
501
8
        V.push_back(Cmd);
502
3
      continue;
503
3
    }
504
1.01k
505
1.01k
    if (BaseCommand *Cmd = readAssignment(Tok))
506
313
      V.push_back(Cmd);
507
704
    else
508
704
      V.push_back(readOutputSectionDescription(Tok));
509
1.01k
  }
510
459
511
459
  if (!atEOF() && 
consume("INSERT")31
) {
512
9
    std::vector<BaseCommand *> *Dest = nullptr;
513
9
    if (consume("AFTER"))
514
4
      Dest = &Script->InsertAfterCommands[next()];
515
5
    else if (consume("BEFORE"))
516
4
      Dest = &Script->InsertBeforeCommands[next()];
517
1
    else
518
1
      setError("expected AFTER/BEFORE, but got '" + next() + "'");
519
9
    if (Dest)
520
8
      Dest->insert(Dest->end(), V.begin(), V.end());
521
9
    return;
522
9
  }
523
450
524
450
  Script->SectionCommands.insert(Script->SectionCommands.end(), V.begin(),
525
450
                                 V.end());
526
450
}
527
528
3
void ScriptParser::readTarget() {
529
3
  // TARGET(foo) is an alias for "--format foo". Unlike GNU linkers,
530
3
  // we accept only a limited set of BFD names (i.e. "elf" or "binary")
531
3
  // for --format. We recognize only /^elf/ and "binary" in the linker
532
3
  // script as well.
533
3
  expect("(");
534
3
  StringRef Tok = next();
535
3
  expect(")");
536
3
537
3
  if (Tok.startswith("elf"))
538
1
    Config->FormatBinary = false;
539
2
  else if (Tok == "binary")
540
1
    Config->FormatBinary = true;
541
1
  else
542
1
    setError("unknown target: " + Tok);
543
3
}
544
545
1.35k
static int precedence(StringRef Op) {
546
1.35k
  return StringSwitch<int>(Op)
547
1.35k
      .Cases("*", "/", "%", 8)
548
1.35k
      .Cases("+", "-", 7)
549
1.35k
      .Cases("<<", ">>", 6)
550
1.35k
      .Cases("<", "<=", ">", ">=", "==", "!=", 5)
551
1.35k
      .Case("&", 4)
552
1.35k
      .Case("|", 3)
553
1.35k
      .Case("&&", 2)
554
1.35k
      .Case("||", 1)
555
1.35k
      .Default(-1);
556
1.35k
}
557
558
7
StringMatcher ScriptParser::readFilePatterns() {
559
7
  std::vector<StringRef> V;
560
14
  while (!errorCount() && !consume(")"))
561
7
    V.push_back(next());
562
7
  return StringMatcher(V);
563
7
}
564
565
754
SortSectionPolicy ScriptParser::readSortKind() {
566
754
  if (consume("SORT") || 
consume("SORT_BY_NAME")749
)
567
11
    return SortSectionPolicy::Name;
568
743
  if (consume("SORT_BY_ALIGNMENT"))
569
4
    return SortSectionPolicy::Alignment;
570
739
  if (consume("SORT_BY_INIT_PRIORITY"))
571
1
    return SortSectionPolicy::Priority;
572
738
  if (consume("SORT_NONE"))
573
3
    return SortSectionPolicy::None;
574
735
  return SortSectionPolicy::Default;
575
735
}
576
577
// Reads SECTIONS command contents in the following form:
578
//
579
// <contents> ::= <elem>*
580
// <elem>     ::= <exclude>? <glob-pattern>
581
// <exclude>  ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
582
//
583
// For example,
584
//
585
// *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
586
//
587
// is parsed as ".foo", ".bar" with "a.o", and ".baz" with "b.o".
588
// The semantics of that is section .foo in any file, section .bar in
589
// any file but a.o, and section .baz in any file but b.o.
590
738
std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
591
738
  std::vector<SectionPattern> Ret;
592
1.47k
  while (!errorCount() && 
peek() != ")"1.47k
) {
593
741
    StringMatcher ExcludeFilePat;
594
741
    if (consume("EXCLUDE_FILE")) {
595
7
      expect("(");
596
7
      ExcludeFilePat = readFilePatterns();
597
7
    }
598
741
599
741
    std::vector<StringRef> V;
600
1.49k
    while (!errorCount() && peek() != ")" && 
peek() != "EXCLUDE_FILE"754
)
601
750
      V.push_back(next());
602
741
603
741
    if (!V.empty())
604
739
      Ret.push_back({std::move(ExcludeFilePat), StringMatcher(V)});
605
2
    else
606
2
      setError("section pattern is expected");
607
741
  }
608
738
  return Ret;
609
738
}
610
611
// Reads contents of "SECTIONS" directive. That directive contains a
612
// list of glob patterns for input sections. The grammar is as follows.
613
//
614
// <patterns> ::= <section-list>
615
//              | <sort> "(" <section-list> ")"
616
//              | <sort> "(" <sort> "(" <section-list> ")" ")"
617
//
618
// <sort>     ::= "SORT" | "SORT_BY_NAME" | "SORT_BY_ALIGNMENT"
619
//              | "SORT_BY_INIT_PRIORITY" | "SORT_NONE"
620
//
621
// <section-list> is parsed by readInputSectionsList().
622
InputSectionDescription *
623
736
ScriptParser::readInputSectionRules(StringRef FilePattern) {
624
736
  auto *Cmd = make<InputSectionDescription>(FilePattern);
625
736
  expect("(");
626
736
627
1.47k
  while (!errorCount() && 
!consume(")")1.47k
) {
628
738
    SortSectionPolicy Outer = readSortKind();
629
738
    SortSectionPolicy Inner = SortSectionPolicy::Default;
630
738
    std::vector<SectionPattern> V;
631
738
    if (Outer != SortSectionPolicy::Default) {
632
16
      expect("(");
633
16
      Inner = readSortKind();
634
16
      if (Inner != SortSectionPolicy::Default) {
635
3
        expect("(");
636
3
        V = readInputSectionsList();
637
3
        expect(")");
638
13
      } else {
639
13
        V = readInputSectionsList();
640
13
      }
641
16
      expect(")");
642
722
    } else {
643
722
      V = readInputSectionsList();
644
722
    }
645
738
646
739
    for (SectionPattern &Pat : V) {
647
739
      Pat.SortInner = Inner;
648
739
      Pat.SortOuter = Outer;
649
739
    }
650
738
651
738
    std::move(V.begin(), V.end(), std::back_inserter(Cmd->SectionPatterns));
652
738
  }
653
736
  return Cmd;
654
736
}
655
656
InputSectionDescription *
657
733
ScriptParser::readInputSectionDescription(StringRef Tok) {
658
733
  // Input section wildcard can be surrounded by KEEP.
659
733
  // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
660
733
  if (Tok == "KEEP") {
661
14
    expect("(");
662
14
    StringRef FilePattern = next();
663
14
    InputSectionDescription *Cmd = readInputSectionRules(FilePattern);
664
14
    expect(")");
665
14
    Script->KeptSections.push_back(Cmd);
666
14
    return Cmd;
667
14
  }
668
719
  return readInputSectionRules(Tok);
669
719
}
670
671
1
void ScriptParser::readSort() {
672
1
  expect("(");
673
1
  expect("CONSTRUCTORS");
674
1
  expect(")");
675
1
}
676
677
8
Expr ScriptParser::readAssert() {
678
8
  expect("(");
679
8
  Expr E = readExpr();
680
8
  expect(",");
681
8
  StringRef Msg = unquote(next());
682
8
  expect(")");
683
8
684
8
  return [=] {
685
8
    if (!E().getValue())
686
1
      error(Msg);
687
8
    return Script->getDot();
688
8
  };
689
8
}
690
691
// Reads a FILL(expr) command. We handle the FILL command as an
692
// alias for =fillexp section attribute, which is different from
693
// what GNU linkers do.
694
// https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
695
4
uint32_t ScriptParser::readFill() {
696
4
  expect("(");
697
4
  uint32_t V = parseFill(next());
698
4
  expect(")");
699
4
  return V;
700
4
}
701
702
// Reads an expression and/or the special directive for an output
703
// section definition. Directive is one of following: "(NOLOAD)",
704
// "(COPY)", "(INFO)" or "(OVERLAY)".
705
//
706
// An output section name can be followed by an address expression
707
// and/or directive. This grammar is not LL(1) because "(" can be
708
// interpreted as either the beginning of some expression or beginning
709
// of directive.
710
//
711
// https://sourceware.org/binutils/docs/ld/Output-Section-Address.html
712
// https://sourceware.org/binutils/docs/ld/Output-Section-Type.html
713
85
void ScriptParser::readSectionAddressType(OutputSection *Cmd) {
714
85
  if (consume("(")) {
715
8
    if (consume("NOLOAD")) {
716
2
      expect(")");
717
2
      Cmd->Noload = true;
718
2
      return;
719
2
    }
720
6
    if (consume("COPY") || 
consume("INFO")5
||
consume("OVERLAY")4
) {
721
3
      expect(")");
722
3
      Cmd->NonAlloc = true;
723
3
      return;
724
3
    }
725
3
    Cmd->AddrExpr = readExpr();
726
3
    expect(")");
727
77
  } else {
728
77
    Cmd->AddrExpr = readExpr();
729
77
  }
730
85
731
85
  
if (80
consume("(")80
) {
732
1
    expect("NOLOAD");
733
1
    expect(")");
734
1
    Cmd->Noload = true;
735
1
  }
736
80
}
737
738
54
static Expr checkAlignment(Expr E, std::string &Loc) {
739
67
  return [=] {
740
67
    uint64_t Alignment = std::max((uint64_t)1, E().getValue());
741
67
    if (!isPowerOf2_64(Alignment)) {
742
3
      error(Loc + ": alignment must be power of 2");
743
3
      return (uint64_t)1; // Return a dummy value.
744
3
    }
745
64
    return Alignment;
746
64
  };
747
54
}
748
749
5
OutputSection *ScriptParser::readOverlaySectionDescription() {
750
5
  OutputSection *Cmd =
751
5
      Script->createOutputSection(next(), getCurrentLocation());
752
5
  Cmd->InOverlay = true;
753
5
  expect("{");
754
8
  while (!errorCount() && 
!consume("}")6
)
755
3
    Cmd->SectionCommands.push_back(readInputSectionRules(next()));
756
5
  Cmd->Phdrs = readOutputSectionPhdrs();
757
5
  return Cmd;
758
5
}
759
760
704
OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec) {
761
704
  OutputSection *Cmd =
762
704
      Script->createOutputSection(OutSec, getCurrentLocation());
763
704
764
704
  size_t SymbolsReferenced = Script->ReferencedSymbols.size();
765
704
766
704
  if (peek() != ":")
767
85
    readSectionAddressType(Cmd);
768
704
  expect(":");
769
704
770
704
  std::string Location = getCurrentLocation();
771
704
  if (consume("AT"))
772
35
    Cmd->LMAExpr = readParenExpr();
773
704
  if (consume("ALIGN"))
774
15
    Cmd->AlignExpr = checkAlignment(readParenExpr(), Location);
775
704
  if (consume("SUBALIGN"))
776
5
    Cmd->SubalignExpr = checkAlignment(readParenExpr(), Location);
777
704
778
704
  // Parse constraints.
779
704
  if (consume("ONLY_IF_RO"))
780
9
    Cmd->Constraint = ConstraintKind::ReadOnly;
781
704
  if (consume("ONLY_IF_RW"))
782
5
    Cmd->Constraint = ConstraintKind::ReadWrite;
783
704
  expect("{");
784
704
785
1.62k
  while (!errorCount() && 
!consume("}")1.62k
) {
786
925
    StringRef Tok = next();
787
925
    if (Tok == ";") {
788
20
      // Empty commands are allowed. Do nothing here.
789
905
    } else if (SymbolAssignment *Assign = readAssignment(Tok)) {
790
124
      Cmd->SectionCommands.push_back(Assign);
791
781
    } else if (ByteCommand *Data = readByteCommand(Tok)) {
792
41
      Cmd->SectionCommands.push_back(Data);
793
740
    } else if (Tok == "CONSTRUCTORS") {
794
1
      // CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
795
1
      // by name. This is for very old file formats such as ECOFF/XCOFF.
796
1
      // For ELF, we should ignore.
797
739
    } else if (Tok == "FILL") {
798
4
      Cmd->Filler = readFill();
799
735
    } else if (Tok == "SORT") {
800
1
      readSort();
801
734
    } else if (peek() == "(") {
802
733
      Cmd->SectionCommands.push_back(readInputSectionDescription(Tok));
803
733
    } else {
804
1
      setError("unknown command " + Tok);
805
1
    }
806
925
  }
807
704
808
704
  if (consume(">"))
809
43
    Cmd->MemoryRegionName = next();
810
704
811
704
  if (consume("AT")) {
812
15
    expect(">");
813
15
    Cmd->LMARegionName = next();
814
15
  }
815
704
816
704
  if (Cmd->LMAExpr && 
!Cmd->LMARegionName.empty()35
)
817
1
    error("section can't have both LMA and a load region");
818
704
819
704
  Cmd->Phdrs = readOutputSectionPhdrs();
820
704
821
704
  if (consume("="))
822
1
    Cmd->Filler = parseFill(next());
823
703
  else if (peek().startswith("="))
824
8
    Cmd->Filler = parseFill(next().drop_front());
825
704
826
704
  // Consume optional comma following output section command.
827
704
  consume(",");
828
704
829
704
  if (Script->ReferencedSymbols.size() > SymbolsReferenced)
830
18
    Cmd->ExpressionsUseSymbols = true;
831
704
  return Cmd;
832
704
}
833
834
// Parses a given string as a octal/decimal/hexadecimal number and
835
// returns it as a big-endian number. Used for `=<fillexp>`.
836
// https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
837
//
838
// When reading a hexstring, ld.bfd handles it as a blob of arbitrary
839
// size, while ld.gold always handles it as a 32-bit big-endian number.
840
// We are compatible with ld.gold because it's easier to implement.
841
13
uint32_t ScriptParser::parseFill(StringRef Tok) {
842
13
  uint32_t V = 0;
843
13
  if (!to_integer(Tok, V))
844
1
    setError("invalid filler expression: " + Tok);
845
13
846
13
  uint32_t Buf;
847
13
  write32be(&Buf, V);
848
13
  return Buf;
849
13
}
850
851
49
SymbolAssignment *ScriptParser::readProvideHidden(bool Provide, bool Hidden) {
852
49
  expect("(");
853
49
  SymbolAssignment *Cmd = readSymbolAssignment(next());
854
49
  Cmd->Provide = Provide;
855
49
  Cmd->Hidden = Hidden;
856
49
  expect(")");
857
49
  return Cmd;
858
49
}
859
860
1.95k
SymbolAssignment *ScriptParser::readAssignment(StringRef Tok) {
861
1.95k
  // Assert expression returns Dot, so this is equal to ".=."
862
1.95k
  if (Tok == "ASSERT")
863
6
    return make<SymbolAssignment>(".", readAssert(), getCurrentLocation());
864
1.95k
865
1.95k
  size_t OldPos = Pos;
866
1.95k
  SymbolAssignment *Cmd = nullptr;
867
1.95k
  if (peek() == "=" || 
peek() == "+="1.55k
)
868
416
    Cmd = readSymbolAssignment(Tok);
869
1.53k
  else if (Tok == "PROVIDE")
870
21
    Cmd = readProvideHidden(true, false);
871
1.51k
  else if (Tok == "HIDDEN")
872
3
    Cmd = readProvideHidden(false, true);
873
1.51k
  else if (Tok == "PROVIDE_HIDDEN")
874
25
    Cmd = readProvideHidden(true, true);
875
1.95k
876
1.95k
  if (Cmd) {
877
465
    Cmd->CommandString =
878
465
        Tok.str() + " " +
879
465
        llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
880
465
    expect(";");
881
465
  }
882
1.95k
  return Cmd;
883
1.95k
}
884
885
465
SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef Name) {
886
465
  StringRef Op = next();
887
465
  assert(Op == "=" || Op == "+=");
888
465
  Expr E = readExpr();
889
465
  if (Op == "+=") {
890
21
    std::string Loc = getCurrentLocation();
891
23
    E = [=] { return add(Script->getSymbolValue(Name, Loc), E()); };
892
21
  }
893
465
  return make<SymbolAssignment>(Name, E, getCurrentLocation());
894
465
}
895
896
// This is an operator-precedence parser to parse a linker
897
// script expression.
898
939
Expr ScriptParser::readExpr() {
899
939
  // Our lexer is context-aware. Set the in-expression bit so that
900
939
  // they apply different tokenization rules.
901
939
  bool Orig = InExpr;
902
939
  InExpr = true;
903
939
  Expr E = readExpr1(readPrimary(), 0);
904
939
  InExpr = Orig;
905
939
  return E;
906
939
}
907
908
150
Expr ScriptParser::combine(StringRef Op, Expr L, Expr R) {
909
150
  if (Op == "+")
910
120
    
return [=] 69
{ return add(L(), R()); };
911
81
  if (Op == "-")
912
34
    
return [=] 19
{ return sub(L(), R()); };
913
62
  if (Op == "*")
914
20
    
return [=] 15
{ return L().getValue() * R().getValue(); };
915
47
  if (Op == "/") {
916
3
    std::string Loc = getCurrentLocation();
917
5
    return [=]() -> uint64_t {
918
5
      if (uint64_t RV = R().getValue())
919
4
        return L().getValue() / RV;
920
1
      error(Loc + ": division by zero");
921
1
      return 0;
922
1
    };
923
3
  }
924
44
  if (Op == "%") {
925
2
    std::string Loc = getCurrentLocation();
926
3
    return [=]() -> uint64_t {
927
3
      if (uint64_t RV = R().getValue())
928
2
        return L().getValue() % RV;
929
1
      error(Loc + ": modulo by zero");
930
1
      return 0;
931
1
    };
932
2
  }
933
42
  if (Op == "<<")
934
6
    
return [=] 3
{ return L().getValue() << R().getValue(); };
935
39
  if (Op == ">>")
936
2
    
return [=] 1
{ return L().getValue() >> R().getValue(); };
937
38
  if (Op == "<")
938
4
    
return [=] 3
{ return L().getValue() < R().getValue(); };
939
35
  if (Op == ">")
940
2
    
return [=] 1
{ return L().getValue() > R().getValue(); };
941
34
  if (Op == ">=")
942
2
    
return [=] 1
{ return L().getValue() >= R().getValue(); };
943
33
  if (Op == "<=")
944
2
    
return [=] 1
{ return L().getValue() <= R().getValue(); };
945
32
  if (Op == "==")
946
5
    
return [=] 4
{ return L().getValue() == R().getValue(); };
947
28
  if (Op == "!=")
948
4
    
return [=] 2
{ return L().getValue() != R().getValue(); };
949
26
  if (Op == "||")
950
8
    
return [=] 4
{ return L().getValue() ||
R().getValue()4
; };
951
22
  if (Op == "&&")
952
8
    
return [=] 4
{ return L().getValue() &&
R().getValue()4
; };
953
18
  if (Op == "&")
954
13
    
return [=] 7
{ return bitAnd(L(), R()); };
955
11
  if (Op == "|")
956
15
    
return [=] 11
{ return bitOr(L(), R()); };
957
0
  llvm_unreachable("invalid operator");
958
0
}
959
960
// This is a part of the operator-precedence parser. This function
961
// assumes that the remaining token stream starts with an operator.
962
947
Expr ScriptParser::readExpr1(Expr Lhs, int MinPrec) {
963
1.09k
  while (!atEOF() && 
!errorCount()1.04k
) {
964
1.04k
    // Read an operator and an expression.
965
1.04k
    if (consume("?"))
966
14
      return readTernary(Lhs);
967
1.03k
    StringRef Op1 = peek();
968
1.03k
    if (precedence(Op1) < MinPrec)
969
885
      break;
970
150
    skip();
971
150
    Expr Rhs = readPrimary();
972
150
973
150
    // Evaluate the remaining part of the expression first if the
974
150
    // next operator has greater precedence than the previous one.
975
150
    // For example, if we have read "+" and "3", and if the next
976
150
    // operator is "*", then we'll evaluate 3 * ... part first.
977
158
    while (!atEOF()) {
978
154
      StringRef Op2 = peek();
979
154
      if (precedence(Op2) <= precedence(Op1))
980
146
        break;
981
8
      Rhs = readExpr1(Rhs, precedence(Op2));
982
8
    }
983
150
984
150
    Lhs = combine(Op1, Lhs, Rhs);
985
150
  }
986
947
  
return Lhs933
;
987
947
}
988
989
7
Expr ScriptParser::getPageSize() {
990
7
  std::string Location = getCurrentLocation();
991
7
  return [=]() -> uint64_t {
992
6
    if (Target)
993
4
      return Target->PageSize;
994
2
    error(Location + ": unable to calculate page size");
995
2
    return 4096; // Return a dummy value.
996
2
  };
997
7
}
998
999
20
Expr ScriptParser::readConstant() {
1000
20
  StringRef S = readParenLiteral();
1001
20
  if (S == "COMMONPAGESIZE")
1002
4
    return getPageSize();
1003
16
  if (S == "MAXPAGESIZE")
1004
21
    
return [] 15
{ return Config->MaxPageSize; };
1005
1
  setError("unknown constant: " + S);
1006
1
  return [] { return 0; };
1007
1
}
1008
1009
// Parses Tok as an integer. It recognizes hexadecimal (prefixed with
1010
// "0x" or suffixed with "H") and decimal numbers. Decimal numbers may
1011
// have "K" (Ki) or "M" (Mi) suffixes.
1012
797
static Optional<uint64_t> parseInt(StringRef Tok) {
1013
797
  // Hexadecimal
1014
797
  uint64_t Val;
1015
797
  if (Tok.startswith_lower("0x")) {
1016
400
    if (!to_integer(Tok.substr(2), Val, 16))
1017
4
      return None;
1018
396
    return Val;
1019
396
  }
1020
397
  if (Tok.endswith_lower("H")) {
1021
3
    if (!to_integer(Tok.drop_back(), Val, 16))
1022
1
      return None;
1023
2
    return Val;
1024
2
  }
1025
394
1026
394
  // Decimal
1027
394
  if (Tok.endswith_lower("K")) {
1028
16
    if (!to_integer(Tok.drop_back(), Val, 10))
1029
1
      return None;
1030
15
    return Val * 1024;
1031
15
  }
1032
378
  if (Tok.endswith_lower("M")) {
1033
9
    if (!to_integer(Tok.drop_back(), Val, 10))
1034
1
      return None;
1035
8
    return Val * 1024 * 1024;
1036
8
  }
1037
369
  if (!to_integer(Tok, Val, 10))
1038
123
    return None;
1039
246
  return Val;
1040
246
}
1041
1042
781
ByteCommand *ScriptParser::readByteCommand(StringRef Tok) {
1043
781
  int Size = StringSwitch<int>(Tok)
1044
781
                 .Case("BYTE", 1)
1045
781
                 .Case("SHORT", 2)
1046
781
                 .Case("LONG", 4)
1047
781
                 .Case("QUAD", 8)
1048
781
                 .Default(-1);
1049
781
  if (Size == -1)
1050
740
    return nullptr;
1051
41
1052
41
  size_t OldPos = Pos;
1053
41
  Expr E = readParenExpr();
1054
41
  std::string CommandString =
1055
41
      Tok.str() + " " +
1056
41
      llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
1057
41
  return make<ByteCommand>(E, Size, CommandString);
1058
41
}
1059
1060
78
StringRef ScriptParser::readParenLiteral() {
1061
78
  expect("(");
1062
78
  bool Orig = InExpr;
1063
78
  InExpr = false;
1064
78
  StringRef Tok = next();
1065
78
  InExpr = Orig;
1066
78
  expect(")");
1067
78
  return Tok;
1068
78
}
1069
1070
57
static void checkIfExists(OutputSection *Cmd, StringRef Location) {
1071
57
  if (Cmd->Location.empty() && 
Script->ErrorOnMissingSection10
)
1072
2
    error(Location + ": undefined section " + Cmd->Name);
1073
57
}
1074
1075
1.10k
Expr ScriptParser::readPrimary() {
1076
1.10k
  if (peek() == "(")
1077
16
    return readParenExpr();
1078
1.08k
1079
1.08k
  if (consume("~")) {
1080
5
    Expr E = readPrimary();
1081
10
    return [=] { return ~E().getValue(); };
1082
5
  }
1083
1.07k
  if (consume("!")) {
1084
2
    Expr E = readPrimary();
1085
4
    return [=] { return !E().getValue(); };
1086
2
  }
1087
1.07k
  if (consume("-")) {
1088
4
    Expr E = readPrimary();
1089
8
    return [=] { return -E().getValue(); };
1090
4
  }
1091
1.07k
1092
1.07k
  StringRef Tok = next();
1093
1.07k
  std::string Location = getCurrentLocation();
1094
1.07k
1095
1.07k
  // Built-in functions are parsed here.
1096
1.07k
  // https://sourceware.org/binutils/docs/ld/Builtin-Functions.html.
1097
1.07k
  if (Tok == "ABSOLUTE") {
1098
15
    Expr Inner = readParenExpr();
1099
32
    return [=] {
1100
32
      ExprValue I = Inner();
1101
32
      I.ForceAbsolute = true;
1102
32
      return I;
1103
32
    };
1104
15
  }
1105
1.05k
  if (Tok == "ADDR") {
1106
22
    StringRef Name = readParenLiteral();
1107
22
    OutputSection *Sec = Script->getOrCreateOutputSection(Name);
1108
35
    return [=]() -> ExprValue {
1109
35
      checkIfExists(Sec, Location);
1110
35
      return {Sec, false, 0, Location};
1111
35
    };
1112
22
  }
1113
1.03k
  if (Tok == "ALIGN") {
1114
34
    expect("(");
1115
34
    Expr E = readExpr();
1116
34
    if (consume(")")) {
1117
18
      E = checkAlignment(E, Location);
1118
21
      return [=] { return alignTo(Script->getDot(), E().getValue()); };
1119
18
    }
1120
16
    expect(",");
1121
16
    Expr E2 = checkAlignment(readExpr(), Location);
1122
16
    expect(")");
1123
26
    return [=] {
1124
26
      ExprValue V = E();
1125
26
      V.Alignment = E2().getValue();
1126
26
      return V;
1127
26
    };
1128
16
  }
1129
1.00k
  if (Tok == "ALIGNOF") {
1130
5
    StringRef Name = readParenLiteral();
1131
5
    OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1132
10
    return [=] {
1133
10
      checkIfExists(Cmd, Location);
1134
10
      return Cmd->Alignment;
1135
10
    };
1136
5
  }
1137
997
  if (Tok == "ASSERT")
1138
2
    return readAssert();
1139
995
  if (Tok == "CONSTANT")
1140
20
    return readConstant();
1141
975
  if (Tok == "DATA_SEGMENT_ALIGN") {
1142
4
    expect("(");
1143
4
    Expr E = readExpr();
1144
4
    expect(",");
1145
4
    readExpr();
1146
4
    expect(")");
1147
6
    return [=] {
1148
6
      return alignTo(Script->getDot(), std::max((uint64_t)1, E().getValue()));
1149
6
    };
1150
4
  }
1151
971
  if (Tok == "DATA_SEGMENT_END") {
1152
2
    expect("(");
1153
2
    expect(".");
1154
2
    expect(")");
1155
2
    return [] { return Script->getDot(); };
1156
2
  }
1157
969
  if (Tok == "DATA_SEGMENT_RELRO_END") {
1158
3
    // GNU linkers implements more complicated logic to handle
1159
3
    // DATA_SEGMENT_RELRO_END. We instead ignore the arguments and
1160
3
    // just align to the next page boundary for simplicity.
1161
3
    expect("(");
1162
3
    readExpr();
1163
3
    expect(",");
1164
3
    readExpr();
1165
3
    expect(")");
1166
3
    Expr E = getPageSize();
1167
3
    return [=] { return alignTo(Script->getDot(), E().getValue()); };
1168
3
  }
1169
966
  if (Tok == "DEFINED") {
1170
2
    StringRef Name = readParenLiteral();
1171
2
    return [=] { return Symtab->find(Name) ? 
11
:
01
; };
1172
2
  }
1173
964
  if (Tok == "LENGTH") {
1174
3
    StringRef Name = readParenLiteral();
1175
3
    if (Script->MemoryRegions.count(Name) == 0) {
1176
1
      setError("memory region not defined: " + Name);
1177
1
      return [] { return 0; };
1178
1
    }
1179
4
    
return [=] 2
{ return Script->MemoryRegions[Name]->Length; };
1180
2
  }
1181
961
  if (Tok == "LOADADDR") {
1182
6
    StringRef Name = readParenLiteral();
1183
6
    OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1184
12
    return [=] {
1185
12
      checkIfExists(Cmd, Location);
1186
12
      return Cmd->getLMA();
1187
12
    };
1188
6
  }
1189
955
  if (Tok == "MAX" || 
Tok == "MIN"954
) {
1190
2
    expect("(");
1191
2
    Expr A = readExpr();
1192
2
    expect(",");
1193
2
    Expr B = readExpr();
1194
2
    expect(")");
1195
2
    if (Tok == "MIN")
1196
2
      
return [=] 1
{ return std::min(A().getValue(), B().getValue()); };
1197
2
    
return [=] 1
{ return std::max(A().getValue(), B().getValue()); };
1198
1
  }
1199
953
  if (Tok == "ORIGIN") {
1200
4
    StringRef Name = readParenLiteral();
1201
4
    if (Script->MemoryRegions.count(Name) == 0) {
1202
2
      setError("memory region not defined: " + Name);
1203
2
      return [] 
{ return 0; }1
;
1204
2
    }
1205
4
    
return [=] 2
{ return Script->MemoryRegions[Name]->Origin; };
1206
2
  }
1207
949
  if (Tok == "SEGMENT_START") {
1208
5
    expect("(");
1209
5
    skip();
1210
5
    expect(",");
1211
5
    Expr E = readExpr();
1212
5
    expect(")");
1213
9
    return [=] { return E(); };
1214
5
  }
1215
944
  if (Tok == "SIZEOF") {
1216
16
    StringRef Name = readParenLiteral();
1217
16
    OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1218
16
    // Linker script does not create an output section if its content is empty.
1219
16
    // We want to allow SIZEOF(.foo) where .foo is a section which happened to
1220
16
    // be empty.
1221
29
    return [=] { return Cmd->Size; };
1222
16
  }
1223
928
  if (Tok == "SIZEOF_HEADERS")
1224
63
    
return [=] 48
{ return elf::getHeaderSize(); };
1225
880
1226
880
  // Tok is the dot.
1227
880
  if (Tok == ".")
1228
227
    
return [=] 124
{ return Script->getSymbolValue(Tok, Location); };
1229
756
1230
756
  // Tok is a literal number.
1231
756
  if (Optional<uint64_t> Val = parseInt(Tok))
1232
887
    
return [=] 665
{ return *Val; };
1233
91
1234
91
  // Tok is a symbol name.
1235
91
  if (!isValidCIdentifier(Tok))
1236
15
    setError("malformed number: " + Tok);
1237
91
  Script->ReferencedSymbols.push_back(Tok);
1238
122
  return [=] { return Script->getSymbolValue(Tok, Location); };
1239
91
}
1240
1241
14
Expr ScriptParser::readTernary(Expr Cond) {
1242
14
  Expr L = readExpr();
1243
14
  expect(":");
1244
14
  Expr R = readExpr();
1245
19
  return [=] { return Cond().getValue() ? 
L()10
:
R()9
; };
1246
14
}
1247
1248
140
Expr ScriptParser::readParenExpr() {
1249
140
  expect("(");
1250
140
  Expr E = readExpr();
1251
140
  expect(")");
1252
140
  return E;
1253
140
}
1254
1255
709
std::vector<StringRef> ScriptParser::readOutputSectionPhdrs() {
1256
709
  std::vector<StringRef> Phdrs;
1257
748
  while (!errorCount() && 
peek().startswith(":")738
) {
1258
39
    StringRef Tok = next();
1259
39
    Phdrs.push_back((Tok.size() == 1) ? 
next()16
:
Tok.substr(1)23
);
1260
39
  }
1261
709
  return Phdrs;
1262
709
}
1263
1264
// Read a program header type name. The next token must be a
1265
// name of a program header type or a constant (e.g. "0x3").
1266
41
unsigned ScriptParser::readPhdrType() {
1267
41
  StringRef Tok = next();
1268
41
  if (Optional<uint64_t> Val = parseInt(Tok))
1269
2
    return *Val;
1270
39
1271
39
  unsigned Ret = StringSwitch<unsigned>(Tok)
1272
39
                     .Case("PT_NULL", PT_NULL)
1273
39
                     .Case("PT_LOAD", PT_LOAD)
1274
39
                     .Case("PT_DYNAMIC", PT_DYNAMIC)
1275
39
                     .Case("PT_INTERP", PT_INTERP)
1276
39
                     .Case("PT_NOTE", PT_NOTE)
1277
39
                     .Case("PT_SHLIB", PT_SHLIB)
1278
39
                     .Case("PT_PHDR", PT_PHDR)
1279
39
                     .Case("PT_TLS", PT_TLS)
1280
39
                     .Case("PT_GNU_EH_FRAME", PT_GNU_EH_FRAME)
1281
39
                     .Case("PT_GNU_STACK", PT_GNU_STACK)
1282
39
                     .Case("PT_GNU_RELRO", PT_GNU_RELRO)
1283
39
                     .Case("PT_OPENBSD_RANDOMIZE", PT_OPENBSD_RANDOMIZE)
1284
39
                     .Case("PT_OPENBSD_WXNEEDED", PT_OPENBSD_WXNEEDED)
1285
39
                     .Case("PT_OPENBSD_BOOTDATA", PT_OPENBSD_BOOTDATA)
1286
39
                     .Default(-1);
1287
39
1288
39
  if (Ret == (unsigned)-1) {
1289
1
    setError("invalid program header type: " + Tok);
1290
1
    return PT_NULL;
1291
1
  }
1292
38
  return Ret;
1293
38
}
1294
1295
// Reads an anonymous version declaration.
1296
23
void ScriptParser::readAnonymousDeclaration() {
1297
23
  std::vector<SymbolVersion> Locals;
1298
23
  std::vector<SymbolVersion> Globals;
1299
23
  std::tie(Locals, Globals) = readSymbols();
1300
23
1301
23
  for (SymbolVersion V : Locals) {
1302
19
    if (V.Name == "*")
1303
18
      Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1304
1
    else
1305
1
      Config->VersionScriptLocals.push_back(V);
1306
19
  }
1307
23
1308
23
  for (SymbolVersion V : Globals)
1309
22
    Config->VersionScriptGlobals.push_back(V);
1310
23
1311
23
  expect(";");
1312
23
}
1313
1314
// Reads a non-anonymous version definition,
1315
// e.g. "VerStr { global: foo; bar; local: *; };".
1316
88
void ScriptParser::readVersionDeclaration(StringRef VerStr) {
1317
88
  // Read a symbol list.
1318
88
  std::vector<SymbolVersion> Locals;
1319
88
  std::vector<SymbolVersion> Globals;
1320
88
  std::tie(Locals, Globals) = readSymbols();
1321
88
1322
88
  for (SymbolVersion V : Locals) {
1323
40
    if (V.Name == "*")
1324
33
      Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1325
7
    else
1326
7
      Config->VersionScriptLocals.push_back(V);
1327
40
  }
1328
88
1329
88
  // Create a new version definition and add that to the global symbols.
1330
88
  VersionDefinition Ver;
1331
88
  Ver.Name = VerStr;
1332
88
  Ver.Globals = Globals;
1333
88
1334
88
  // User-defined version number starts from 2 because 0 and 1 are
1335
88
  // reserved for VER_NDX_LOCAL and VER_NDX_GLOBAL, respectively.
1336
88
  Ver.Id = Config->VersionDefinitions.size() + 2;
1337
88
  Config->VersionDefinitions.push_back(Ver);
1338
88
1339
88
  // Each version may have a parent version. For example, "Ver2"
1340
88
  // defined as "Ver2 { global: foo; local: *; } Ver1;" has "Ver1"
1341
88
  // as a parent. This version hierarchy is, probably against your
1342
88
  // instinct, purely for hint; the runtime doesn't care about it
1343
88
  // at all. In LLD, we simply ignore it.
1344
88
  if (peek() != ";")
1345
3
    skip();
1346
88
  expect(";");
1347
88
}
1348
1349
168
static bool hasWildcard(StringRef S) {
1350
168
  return S.find_first_of("?*[") != StringRef::npos;
1351
168
}
1352
1353
// Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
1354
std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
1355
135
ScriptParser::readSymbols() {
1356
135
  std::vector<SymbolVersion> Locals;
1357
135
  std::vector<SymbolVersion> Globals;
1358
135
  std::vector<SymbolVersion> *V = &Globals;
1359
135
1360
439
  while (!errorCount()) {
1361
434
    if (consume("}"))
1362
130
      break;
1363
304
    if (consumeLabel("local")) {
1364
60
      V = &Locals;
1365
60
      continue;
1366
60
    }
1367
244
    if (consumeLabel("global")) {
1368
72
      V = &Globals;
1369
72
      continue;
1370
72
    }
1371
172
1372
172
    if (consume("extern")) {
1373
27
      std::vector<SymbolVersion> Ext = readVersionExtern();
1374
27
      V->insert(V->end(), Ext.begin(), Ext.end());
1375
145
    } else {
1376
145
      StringRef Tok = next();
1377
145
      V->push_back({unquote(Tok), false, hasWildcard(Tok)});
1378
145
    }
1379
172
    expect(";");
1380
172
  }
1381
135
  return {Locals, Globals};
1382
135
}
1383
1384
// Reads an "extern C++" directive, e.g.,
1385
// "extern "C++" { ns::*; "f(int, double)"; };"
1386
//
1387
// The last semicolon is optional. E.g. this is OK:
1388
// "extern "C++" { ns::*; "f(int, double)" };"
1389
27
std::vector<SymbolVersion> ScriptParser::readVersionExtern() {
1390
27
  StringRef Tok = next();
1391
27
  bool IsCXX = Tok == "\"C++\"";
1392
27
  if (!IsCXX && 
Tok != "\"C\""4
)
1393
1
    setError("Unknown language");
1394
27
  expect("{");
1395
27
1396
27
  std::vector<SymbolVersion> Ret;
1397
57
  while (!errorCount() && 
peek() != "}"56
) {
1398
32
    StringRef Tok = next();
1399
32
    bool HasWildcard = !Tok.startswith("\"") && 
hasWildcard(Tok)23
;
1400
32
    Ret.push_back({unquote(Tok), IsCXX, HasWildcard});
1401
32
    if (consume("}"))
1402
2
      return Ret;
1403
30
    expect(";");
1404
30
  }
1405
27
1406
27
  expect("}");
1407
25
  return Ret;
1408
27
}
1409
1410
uint64_t ScriptParser::readMemoryAssignment(StringRef S1, StringRef S2,
1411
124
                                            StringRef S3) {
1412
124
  if (!consume(S1) && 
!consume(S2)32
&&
!consume(S3)16
) {
1413
10
    setError("expected one of: " + S1 + ", " + S2 + ", or " + S3);
1414
10
    return 0;
1415
10
  }
1416
114
  expect("=");
1417
114
  return readExpr()().getValue();
1418
114
}
1419
1420
// Parse the MEMORY command as specified in:
1421
// https://sourceware.org/binutils/docs/ld/MEMORY.html
1422
//
1423
// MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
1424
39
void ScriptParser::readMemory() {
1425
39
  expect("{");
1426
101
  while (!errorCount() && 
!consume("}")91
) {
1427
62
    StringRef Name = next();
1428
62
1429
62
    uint32_t Flags = 0;
1430
62
    uint32_t NegFlags = 0;
1431
62
    if (consume("(")) {
1432
54
      std::tie(Flags, NegFlags) = readMemoryAttributes();
1433
54
      expect(")");
1434
54
    }
1435
62
    expect(":");
1436
62
1437
62
    uint64_t Origin = readMemoryAssignment("ORIGIN", "org", "o");
1438
62
    expect(",");
1439
62
    uint64_t Length = readMemoryAssignment("LENGTH", "len", "l");
1440
62
1441
62
    // Add the memory region to the region map.
1442
62
    MemoryRegion *MR =
1443
62
        make<MemoryRegion>(Name, Origin, Length, Flags, NegFlags);
1444
62
    if (!Script->MemoryRegions.insert({Name, MR}).second)
1445
1
      setError("region '" + Name + "' already defined");
1446
62
  }
1447
39
}
1448
1449
// This function parses the attributes used to match against section
1450
// flags when placing output sections in a memory region. These flags
1451
// are only used when an explicit memory region name is not used.
1452
54
std::pair<uint32_t, uint32_t> ScriptParser::readMemoryAttributes() {
1453
54
  uint32_t Flags = 0;
1454
54
  uint32_t NegFlags = 0;
1455
54
  bool Invert = false;
1456
54
1457
140
  for (char C : next().lower()) {
1458
140
    uint32_t Flag = 0;
1459
140
    if (C == '!')
1460
2
      Invert = !Invert;
1461
138
    else if (C == 'w')
1462
32
      Flag = SHF_WRITE;
1463
106
    else if (C == 'x')
1464
50
      Flag = SHF_EXECINSTR;
1465
56
    else if (C == 'a')
1466
18
      Flag = SHF_ALLOC;
1467
38
    else if (C != 'r')
1468
2
      setError("invalid memory region attribute");
1469
140
1470
140
    if (Invert)
1471
6
      NegFlags |= Flag;
1472
134
    else
1473
134
      Flags |= Flag;
1474
140
  }
1475
54
  return {Flags, NegFlags};
1476
54
}
1477
1478
570
void elf::readLinkerScript(MemoryBufferRef MB) {
1479
570
  ScriptParser(MB).readLinkerScript();
1480
570
}
1481
1482
81
void elf::readVersionScript(MemoryBufferRef MB) {
1483
81
  ScriptParser(MB).readVersionScript();
1484
81
}
1485
1486
24
void elf::readDynamicList(MemoryBufferRef MB) {
1487
24
  ScriptParser(MB).readDynamicList();
1488
24
}
1489
1490
28
void elf::readDefsym(StringRef Name, MemoryBufferRef MB) {
1491
28
  ScriptParser(MB).readDefsym(Name);
1492
28
}