Coverage Report

Created: 2019-05-19 14:56

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