Coverage Report

Created: 2018-10-20 12:32

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