Coverage Report

Created: 2019-01-18 03:29

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