Coverage Report

Created: 2019-07-24 05:18

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