Coverage Report

Created: 2018-10-20 12:32

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/lld/wasm/Writer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- Writer.cpp ---------------------------------------------------------===//
2
//
3
//                             The LLVM Linker
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
10
#include "Writer.h"
11
#include "Config.h"
12
#include "InputChunks.h"
13
#include "InputGlobal.h"
14
#include "OutputSections.h"
15
#include "OutputSegment.h"
16
#include "SymbolTable.h"
17
#include "WriterUtils.h"
18
#include "lld/Common/ErrorHandler.h"
19
#include "lld/Common/Memory.h"
20
#include "lld/Common/Strings.h"
21
#include "lld/Common/Threads.h"
22
#include "llvm/ADT/DenseSet.h"
23
#include "llvm/ADT/StringMap.h"
24
#include "llvm/BinaryFormat/Wasm.h"
25
#include "llvm/Object/WasmTraits.h"
26
#include "llvm/Support/FileOutputBuffer.h"
27
#include "llvm/Support/Format.h"
28
#include "llvm/Support/FormatVariadic.h"
29
#include "llvm/Support/LEB128.h"
30
31
#include <cstdarg>
32
#include <map>
33
34
#define DEBUG_TYPE "lld"
35
36
using namespace llvm;
37
using namespace llvm::wasm;
38
using namespace lld;
39
using namespace lld::wasm;
40
41
static constexpr int kStackAlignment = 16;
42
static constexpr int kInitialTableOffset = 1;
43
static constexpr const char *kFunctionTableName = "__indirect_function_table";
44
45
namespace {
46
47
// An init entry to be written to either the synthetic init func or the
48
// linking metadata.
49
struct WasmInitEntry {
50
  const FunctionSymbol *Sym;
51
  uint32_t Priority;
52
};
53
54
// The writer writes a SymbolTable result to a file.
55
class Writer {
56
public:
57
  void run();
58
59
private:
60
  void openFile();
61
62
  uint32_t lookupType(const WasmSignature &Sig);
63
  uint32_t registerType(const WasmSignature &Sig);
64
65
  void createCtorFunction();
66
  void calculateInitFunctions();
67
  void assignIndexes();
68
  void calculateImports();
69
  void calculateExports();
70
  void calculateCustomSections();
71
  void assignSymtab();
72
  void calculateTypes();
73
  void createOutputSegments();
74
  void layoutMemory();
75
  void createHeader();
76
  void createSections();
77
  SyntheticSection *createSyntheticSection(uint32_t Type, StringRef Name = "");
78
79
  // Builtin sections
80
  void createTypeSection();
81
  void createFunctionSection();
82
  void createTableSection();
83
  void createGlobalSection();
84
  void createExportSection();
85
  void createImportSection();
86
  void createMemorySection();
87
  void createElemSection();
88
  void createCodeSection();
89
  void createDataSection();
90
  void createCustomSections();
91
92
  // Custom sections
93
  void createRelocSections();
94
  void createLinkingSection();
95
  void createNameSection();
96
97
  void writeHeader();
98
  void writeSections();
99
100
  uint64_t FileSize = 0;
101
  uint32_t NumMemoryPages = 0;
102
  uint32_t MaxMemoryPages = 0;
103
104
  std::vector<const WasmSignature *> Types;
105
  DenseMap<WasmSignature, int32_t> TypeIndices;
106
  std::vector<const Symbol *> ImportedSymbols;
107
  unsigned NumImportedFunctions = 0;
108
  unsigned NumImportedGlobals = 0;
109
  std::vector<WasmExport> Exports;
110
  std::vector<const DefinedData *> DefinedFakeGlobals;
111
  std::vector<InputGlobal *> InputGlobals;
112
  std::vector<InputFunction *> InputFunctions;
113
  std::vector<const FunctionSymbol *> IndirectFunctions;
114
  std::vector<const Symbol *> SymtabEntries;
115
  std::vector<WasmInitEntry> InitFunctions;
116
117
  llvm::StringMap<std::vector<InputSection *>> CustomSectionMapping;
118
  llvm::StringMap<SectionSymbol *> CustomSectionSymbols;
119
120
  // Elements that are used to construct the final output
121
  std::string Header;
122
  std::vector<OutputSection *> OutputSections;
123
124
  std::unique_ptr<FileOutputBuffer> Buffer;
125
126
  std::vector<OutputSegment *> Segments;
127
  llvm::SmallDenseMap<StringRef, OutputSegment *> SegmentMap;
128
};
129
130
} // anonymous namespace
131
132
99
void Writer::createImportSection() {
133
99
  uint32_t NumImports = ImportedSymbols.size();
134
99
  if (Config->ImportMemory)
135
2
    ++NumImports;
136
99
  if (Config->ImportTable)
137
1
    ++NumImports;
138
99
139
99
  if (NumImports == 0)
140
82
    return;
141
17
142
17
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_IMPORT);
143
17
  raw_ostream &OS = Section->getStream();
144
17
145
17
  writeUleb128(OS, NumImports, "import count");
146
17
147
17
  if (Config->ImportMemory) {
148
2
    WasmImport Import;
149
2
    Import.Module = "env";
150
2
    Import.Field = "memory";
151
2
    Import.Kind = WASM_EXTERNAL_MEMORY;
152
2
    Import.Memory.Flags = 0;
153
2
    Import.Memory.Initial = NumMemoryPages;
154
2
    if (MaxMemoryPages != 0) {
155
1
      Import.Memory.Flags |= WASM_LIMITS_FLAG_HAS_MAX;
156
1
      Import.Memory.Maximum = MaxMemoryPages;
157
1
    }
158
2
    writeImport(OS, Import);
159
2
  }
160
17
161
17
  if (Config->ImportTable) {
162
1
    uint32_t TableSize = kInitialTableOffset + IndirectFunctions.size();
163
1
    WasmImport Import;
164
1
    Import.Module = "env";
165
1
    Import.Field = kFunctionTableName;
166
1
    Import.Kind = WASM_EXTERNAL_TABLE;
167
1
    Import.Table.ElemType = WASM_TYPE_ANYFUNC;
168
1
    Import.Table.Limits = {WASM_LIMITS_FLAG_HAS_MAX, TableSize, TableSize};
169
1
    writeImport(OS, Import);
170
1
  }
171
17
172
23
  for (const Symbol *Sym : ImportedSymbols) {
173
23
    WasmImport Import;
174
23
    Import.Module = "env";
175
23
    Import.Field = Sym->getName();
176
23
    if (auto *FunctionSym = dyn_cast<FunctionSymbol>(Sym)) {
177
16
      Import.Kind = WASM_EXTERNAL_FUNCTION;
178
16
      Import.SigIndex = lookupType(*FunctionSym->FunctionType);
179
16
    } else {
180
7
      auto *GlobalSym = cast<GlobalSymbol>(Sym);
181
7
      Import.Kind = WASM_EXTERNAL_GLOBAL;
182
7
      Import.Global = *GlobalSym->getGlobalType();
183
7
    }
184
23
    writeImport(OS, Import);
185
23
  }
186
17
}
187
188
99
void Writer::createTypeSection() {
189
99
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_TYPE);
190
99
  raw_ostream &OS = Section->getStream();
191
99
  writeUleb128(OS, Types.size(), "type count");
192
99
  for (const WasmSignature *Sig : Types)
193
167
    writeSig(OS, *Sig);
194
99
}
195
196
99
void Writer::createFunctionSection() {
197
99
  if (InputFunctions.empty())
198
1
    return;
199
98
200
98
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_FUNCTION);
201
98
  raw_ostream &OS = Section->getStream();
202
98
203
98
  writeUleb128(OS, InputFunctions.size(), "function count");
204
98
  for (const InputFunction *Func : InputFunctions)
205
478
    writeUleb128(OS, lookupType(Func->Signature), "sig index");
206
98
}
207
208
99
void Writer::createMemorySection() {
209
99
  if (Config->ImportMemory)
210
2
    return;
211
97
212
97
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_MEMORY);
213
97
  raw_ostream &OS = Section->getStream();
214
97
215
97
  bool HasMax = MaxMemoryPages != 0;
216
97
  writeUleb128(OS, 1, "memory count");
217
97
  writeUleb128(OS, HasMax ? 
static_cast<unsigned>(WASM_LIMITS_FLAG_HAS_MAX)1
:
096
,
218
97
               "memory limits flags");
219
97
  writeUleb128(OS, NumMemoryPages, "initial pages");
220
97
  if (HasMax)
221
1
    writeUleb128(OS, MaxMemoryPages, "max pages");
222
97
}
223
224
99
void Writer::createGlobalSection() {
225
99
  unsigned NumGlobals = InputGlobals.size() + DefinedFakeGlobals.size();
226
99
  if (NumGlobals == 0)
227
17
    return;
228
82
229
82
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_GLOBAL);
230
82
  raw_ostream &OS = Section->getStream();
231
82
232
82
  writeUleb128(OS, NumGlobals, "global count");
233
82
  for (const InputGlobal *G : InputGlobals)
234
85
    writeGlobal(OS, G->Global);
235
172
  for (const DefinedData *Sym : DefinedFakeGlobals) {
236
172
    WasmGlobal Global;
237
172
    Global.Type = {WASM_TYPE_I32, false};
238
172
    Global.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
239
172
    Global.InitExpr.Value.Int32 = Sym->getVirtualAddress();
240
172
    writeGlobal(OS, Global);
241
172
  }
242
82
}
243
244
99
void Writer::createTableSection() {
245
99
  if (Config->ImportTable)
246
1
    return;
247
98
248
98
  // Always output a table section (or table import), even if there are no
249
98
  // indirect calls.  There are two reasons for this:
250
98
  //  1. For executables it is useful to have an empty table slot at 0
251
98
  //     which can be filled with a null function call handler.
252
98
  //  2. If we don't do this, any program that contains a call_indirect but
253
98
  //     no address-taken function will fail at validation time since it is
254
98
  //     a validation error to include a call_indirect instruction if there
255
98
  //     is not table.
256
98
  uint32_t TableSize = kInitialTableOffset + IndirectFunctions.size();
257
98
258
98
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_TABLE);
259
98
  raw_ostream &OS = Section->getStream();
260
98
261
98
  writeUleb128(OS, 1, "table count");
262
98
  WasmLimits Limits = {WASM_LIMITS_FLAG_HAS_MAX, TableSize, TableSize};
263
98
  writeTableType(OS, WasmTable{WASM_TYPE_ANYFUNC, Limits});
264
98
}
265
266
99
void Writer::createExportSection() {
267
99
  if (!Exports.size())
268
17
    return;
269
82
270
82
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_EXPORT);
271
82
  raw_ostream &OS = Section->getStream();
272
82
273
82
  writeUleb128(OS, Exports.size(), "export count");
274
82
  for (const WasmExport &Export : Exports)
275
391
    writeExport(OS, Export);
276
82
}
277
278
99
void Writer::calculateCustomSections() {
279
99
  log("calculateCustomSections");
280
99
  bool StripDebug = Config->StripDebug || 
Config->StripAll96
;
281
163
  for (ObjFile *File : Symtab->ObjectFiles) {
282
286
    for (InputSection *Section : File->CustomSections) {
283
286
      StringRef Name = Section->getName();
284
286
      // These custom sections are known the linker and synthesized rather than
285
286
      // blindly copied
286
286
      if (Name == "linking" || 
Name == "name"123
||
Name.startswith("reloc.")123
)
287
260
        continue;
288
26
      // .. or it is a debug section
289
26
      if (StripDebug && 
Name.startswith(".debug_")0
)
290
0
        continue;
291
26
      CustomSectionMapping[Name].push_back(Section);
292
26
    }
293
163
  }
294
99
}
295
296
99
void Writer::createCustomSections() {
297
99
  log("createCustomSections");
298
99
  for (auto &Pair : CustomSectionMapping) {
299
18
    StringRef Name = Pair.first();
300
18
301
18
    auto P = CustomSectionSymbols.find(Name);
302
18
    if (P != CustomSectionSymbols.end()) {
303
0
      uint32_t SectionIndex = OutputSections.size();
304
0
      P->second->setOutputSectionIndex(SectionIndex);
305
0
    }
306
18
307
18
    LLVM_DEBUG(dbgs() << "createCustomSection: " << Name << "\n");
308
18
    OutputSections.push_back(make<CustomSection>(Name, Pair.second));
309
18
  }
310
99
}
311
312
99
void Writer::createElemSection() {
313
99
  if (IndirectFunctions.empty())
314
85
    return;
315
14
316
14
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_ELEM);
317
14
  raw_ostream &OS = Section->getStream();
318
14
319
14
  writeUleb128(OS, 1, "segment count");
320
14
  writeUleb128(OS, 0, "table index");
321
14
  WasmInitExpr InitExpr;
322
14
  InitExpr.Opcode = WASM_OPCODE_I32_CONST;
323
14
  InitExpr.Value.Int32 = kInitialTableOffset;
324
14
  writeInitExpr(OS, InitExpr);
325
14
  writeUleb128(OS, IndirectFunctions.size(), "elem count");
326
14
327
14
  uint32_t TableIndex = kInitialTableOffset;
328
41
  for (const FunctionSymbol *Sym : IndirectFunctions) {
329
41
    assert(Sym->getTableIndex() == TableIndex);
330
41
    writeUleb128(OS, Sym->getFunctionIndex(), "function index");
331
41
    ++TableIndex;
332
41
  }
333
14
}
334
335
99
void Writer::createCodeSection() {
336
99
  if (InputFunctions.empty())
337
1
    return;
338
98
339
98
  log("createCodeSection");
340
98
341
98
  auto Section = make<CodeSection>(InputFunctions);
342
98
  OutputSections.push_back(Section);
343
98
}
344
345
99
void Writer::createDataSection() {
346
99
  if (!Segments.size())
347
78
    return;
348
21
349
21
  log("createDataSection");
350
21
  auto Section = make<DataSection>(Segments);
351
21
  OutputSections.push_back(Section);
352
21
}
353
354
// Create relocations sections in the final output.
355
// These are only created when relocatable output is requested.
356
17
void Writer::createRelocSections() {
357
17
  log("createRelocSections");
358
17
  // Don't use iterator here since we are adding to OutputSection
359
17
  size_t OrigSize = OutputSections.size();
360
135
  for (size_t I = 0; I < OrigSize; 
I++118
) {
361
118
    OutputSection *OSec = OutputSections[I];
362
118
    uint32_t Count = OSec->numRelocations();
363
118
    if (!Count)
364
106
      continue;
365
12
366
12
    StringRef Name;
367
12
    if (OSec->Type == WASM_SEC_DATA)
368
3
      Name = "reloc.DATA";
369
9
    else if (OSec->Type == WASM_SEC_CODE)
370
9
      Name = "reloc.CODE";
371
0
    else if (OSec->Type == WASM_SEC_CUSTOM)
372
0
      Name = Saver.save("reloc." + OSec->Name);
373
0
    else
374
0
      llvm_unreachable(
375
12
          "relocations only supported for code, data, or custom sections");
376
12
377
12
    SyntheticSection *Section = createSyntheticSection(WASM_SEC_CUSTOM, Name);
378
12
    raw_ostream &OS = Section->getStream();
379
12
    writeUleb128(OS, I, "reloc section");
380
12
    writeUleb128(OS, Count, "reloc count");
381
12
    OSec->writeRelocations(OS);
382
12
  }
383
17
}
384
385
233
static uint32_t getWasmFlags(const Symbol *Sym) {
386
233
  uint32_t Flags = 0;
387
233
  if (Sym->isLocal())
388
20
    Flags |= WASM_SYMBOL_BINDING_LOCAL;
389
233
  if (Sym->isWeak())
390
6
    Flags |= WASM_SYMBOL_BINDING_WEAK;
391
233
  if (Sym->isHidden())
392
25
    Flags |= WASM_SYMBOL_VISIBILITY_HIDDEN;
393
233
  if (Sym->isUndefined())
394
13
    Flags |= WASM_SYMBOL_UNDEFINED;
395
233
  return Flags;
396
233
}
397
398
// Some synthetic sections (e.g. "name" and "linking") have subsections.
399
// Just like the synthetic sections themselves these need to be created before
400
// they can be written out (since they are preceded by their length). This
401
// class is used to create subsections and then write them into the stream
402
// of the parent section.
403
class SubSection {
404
public:
405
119
  explicit SubSection(uint32_t Type) : Type(Type) {}
406
407
119
  void writeTo(raw_ostream &To) {
408
119
    OS.flush();
409
119
    writeUleb128(To, Type, "subsection type");
410
119
    writeUleb128(To, Body.size(), "subsection size");
411
119
    To.write(Body.data(), Body.size());
412
119
  }
413
414
private:
415
  uint32_t Type;
416
  std::string Body;
417
418
public:
419
  raw_string_ostream OS{Body};
420
};
421
422
// Create the custom "linking" section containing linker metadata.
423
// This is only created when relocatable output is requested.
424
17
void Writer::createLinkingSection() {
425
17
  SyntheticSection *Section =
426
17
      createSyntheticSection(WASM_SEC_CUSTOM, "linking");
427
17
  raw_ostream &OS = Section->getStream();
428
17
429
17
  writeUleb128(OS, WasmMetadataVersion, "Version");
430
17
431
17
  if (!SymtabEntries.empty()) {
432
17
    SubSection Sub(WASM_SYMBOL_TABLE);
433
17
    writeUleb128(Sub.OS, SymtabEntries.size(), "num symbols");
434
17
435
233
    for (const Symbol *Sym : SymtabEntries) {
436
233
      assert(Sym->isDefined() || Sym->isUndefined());
437
233
      WasmSymbolType Kind = Sym->getWasmType();
438
233
      uint32_t Flags = getWasmFlags(Sym);
439
233
440
233
      writeU8(Sub.OS, Kind, "sym kind");
441
233
      writeUleb128(Sub.OS, Flags, "sym flags");
442
233
443
233
      if (auto *F = dyn_cast<FunctionSymbol>(Sym)) {
444
205
        writeUleb128(Sub.OS, F->getFunctionIndex(), "index");
445
205
        if (Sym->isDefined())
446
198
          writeStr(Sub.OS, Sym->getName(), "sym name");
447
205
      } else 
if (auto *28
G28
= dyn_cast<GlobalSymbol>(Sym)) {
448
4
        writeUleb128(Sub.OS, G->getGlobalIndex(), "index");
449
4
        if (Sym->isDefined())
450
0
          writeStr(Sub.OS, Sym->getName(), "sym name");
451
24
      } else if (isa<DataSymbol>(Sym)) {
452
24
        writeStr(Sub.OS, Sym->getName(), "sym name");
453
24
        if (auto *DataSym = dyn_cast<DefinedData>(Sym)) {
454
22
          writeUleb128(Sub.OS, DataSym->getOutputSegmentIndex(), "index");
455
22
          writeUleb128(Sub.OS, DataSym->getOutputSegmentOffset(),
456
22
                       "data offset");
457
22
          writeUleb128(Sub.OS, DataSym->getSize(), "data size");
458
22
        }
459
24
      } else {
460
0
        auto *S = cast<SectionSymbol>(Sym);
461
0
        writeUleb128(Sub.OS, S->getOutputSectionIndex(), "sym section index");
462
0
      }
463
233
    }
464
17
465
17
    Sub.writeTo(OS);
466
17
  }
467
17
468
17
  if (Segments.size()) {
469
5
    SubSection Sub(WASM_SEGMENT_INFO);
470
5
    writeUleb128(Sub.OS, Segments.size(), "num data segments");
471
19
    for (const OutputSegment *S : Segments) {
472
19
      writeStr(Sub.OS, S->Name, "segment name");
473
19
      writeUleb128(Sub.OS, S->Alignment, "alignment");
474
19
      writeUleb128(Sub.OS, 0, "flags");
475
19
    }
476
5
    Sub.writeTo(OS);
477
5
  }
478
17
479
17
  if (!InitFunctions.empty()) {
480
1
    SubSection Sub(WASM_INIT_FUNCS);
481
1
    writeUleb128(Sub.OS, InitFunctions.size(), "num init functions");
482
13
    for (const WasmInitEntry &F : InitFunctions) {
483
13
      writeUleb128(Sub.OS, F.Priority, "priority");
484
13
      writeUleb128(Sub.OS, F.Sym->getOutputSymbolIndex(), "function index");
485
13
    }
486
1
    Sub.writeTo(OS);
487
1
  }
488
17
489
17
  struct ComdatEntry {
490
17
    unsigned Kind;
491
17
    uint32_t Index;
492
17
  };
493
17
  std::map<StringRef, std::vector<ComdatEntry>> Comdats;
494
17
495
197
  for (const InputFunction *F : InputFunctions) {
496
197
    StringRef Comdat = F->getComdatName();
497
197
    if (!Comdat.empty())
498
1
      Comdats[Comdat].emplace_back(
499
1
          ComdatEntry{WASM_COMDAT_FUNCTION, F->getFunctionIndex()});
500
197
  }
501
36
  for (uint32_t I = 0; I < Segments.size(); 
++I19
) {
502
19
    const auto &InputSegments = Segments[I]->InputSegments;
503
19
    if (InputSegments.empty())
504
0
      continue;
505
19
    StringRef Comdat = InputSegments[0]->getComdatName();
506
#ifndef NDEBUG
507
    for (const InputSegment *IS : InputSegments)
508
      assert(IS->getComdatName() == Comdat);
509
#endif
510
19
    if (!Comdat.empty())
511
1
      Comdats[Comdat].emplace_back(ComdatEntry{WASM_COMDAT_DATA, I});
512
19
  }
513
17
514
17
  if (!Comdats.empty()) {
515
1
    SubSection Sub(WASM_COMDAT_INFO);
516
1
    writeUleb128(Sub.OS, Comdats.size(), "num comdats");
517
1
    for (const auto &C : Comdats) {
518
1
      writeStr(Sub.OS, C.first, "comdat name");
519
1
      writeUleb128(Sub.OS, 0, "comdat flags"); // flags for future use
520
1
      writeUleb128(Sub.OS, C.second.size(), "num entries");
521
2
      for (const ComdatEntry &Entry : C.second) {
522
2
        writeU8(Sub.OS, Entry.Kind, "entry kind");
523
2
        writeUleb128(Sub.OS, Entry.Index, "entry index");
524
2
      }
525
1
    }
526
1
    Sub.writeTo(OS);
527
1
  }
528
17
}
529
530
// Create the custom "name" section containing debug symbol names.
531
96
void Writer::createNameSection() {
532
96
  unsigned NumNames = NumImportedFunctions;
533
96
  for (const InputFunction *F : InputFunctions)
534
467
    if (!F->getName().empty() || 
!F->getDebugName().empty()0
)
535
467
      ++NumNames;
536
96
537
96
  if (NumNames == 0)
538
1
    return;
539
95
540
95
  SyntheticSection *Section = createSyntheticSection(WASM_SEC_CUSTOM, "name");
541
95
542
95
  SubSection Sub(WASM_NAMES_FUNCTION);
543
95
  writeUleb128(Sub.OS, NumNames, "name count");
544
95
545
95
  // Names must appear in function index order.  As it happens ImportedSymbols
546
95
  // and InputFunctions are numbered in order with imported functions coming
547
95
  // first.
548
95
  for (const Symbol *S : ImportedSymbols) {
549
23
    if (auto *F = dyn_cast<FunctionSymbol>(S)) {
550
16
      writeUleb128(Sub.OS, F->getFunctionIndex(), "func index");
551
16
      Optional<std::string> Name = demangleItanium(F->getName());
552
16
      writeStr(Sub.OS, Name ? 
StringRef(*Name)0
: F->getName(), "symbol name");
553
16
    }
554
23
  }
555
467
  for (const InputFunction *F : InputFunctions) {
556
467
    if (!F->getName().empty()) {
557
467
      writeUleb128(Sub.OS, F->getFunctionIndex(), "func index");
558
467
      if (!F->getDebugName().empty()) {
559
5
        writeStr(Sub.OS, F->getDebugName(), "symbol name");
560
462
      } else {
561
462
        Optional<std::string> Name = demangleItanium(F->getName());
562
462
        writeStr(Sub.OS, Name ? 
StringRef(*Name)2
:
F->getName()460
, "symbol name");
563
462
      }
564
467
    }
565
467
  }
566
95
567
95
  Sub.writeTo(Section->getStream());
568
95
}
569
570
98
void Writer::writeHeader() {
571
98
  memcpy(Buffer->getBufferStart(), Header.data(), Header.size());
572
98
}
573
574
void Writer::writeSections() {
575
  uint8_t *Buf = Buffer->getBufferStart();
576
840
  parallelForEach(OutputSections, [Buf](OutputSection *S) { S->writeTo(Buf); });
577
}
578
579
// Fix the memory layout of the output binary.  This assigns memory offsets
580
// to each of the input data sections as well as the explicit stack region.
581
// The default memory layout is as follows, from low to high.
582
//
583
//  - initialized data (starting at Config->GlobalBase)
584
//  - BSS data (not currently implemented in llvm)
585
//  - explicit stack (Config->ZStackSize)
586
//  - heap start / unallocated
587
//
588
// The --stack-first option means that stack is placed before any static data.
589
// This can be useful since it means that stack overflow traps immediately
590
// rather than overwriting global data, but also increases code size since all
591
// static data loads and stores requires larger offsets.
592
99
void Writer::layoutMemory() {
593
99
  createOutputSegments();
594
99
595
99
  uint32_t MemoryPtr = 0;
596
99
597
99
  auto PlaceStack = [&]() {
598
99
    if (Config->Relocatable)
599
17
      return;
600
82
    MemoryPtr = alignTo(MemoryPtr, kStackAlignment);
601
82
    if (Config->ZStackSize != alignTo(Config->ZStackSize, kStackAlignment))
602
1
      error("stack size must be " + Twine(kStackAlignment) + "-byte aligned");
603
82
    log("mem: stack size  = " + Twine(Config->ZStackSize));
604
82
    log("mem: stack base  = " + Twine(MemoryPtr));
605
82
    MemoryPtr += Config->ZStackSize;
606
82
    WasmSym::StackPointer->Global->Global.InitExpr.Value.Int32 = MemoryPtr;
607
82
    log("mem: stack top   = " + Twine(MemoryPtr));
608
82
  };
609
99
610
99
  if (Config->StackFirst) {
611
1
    PlaceStack();
612
98
  } else {
613
98
    MemoryPtr = Config->GlobalBase;
614
98
    log("mem: global base = " + Twine(Config->GlobalBase));
615
98
  }
616
99
617
99
  uint32_t DataStart = MemoryPtr;
618
99
619
99
  // Arbitrarily set __dso_handle handle to point to the start of the data
620
99
  // segments.
621
99
  if (WasmSym::DsoHandle)
622
82
    WasmSym::DsoHandle->setVirtualAddress(DataStart);
623
99
624
99
  for (OutputSegment *Seg : Segments) {
625
45
    MemoryPtr = alignTo(MemoryPtr, Seg->Alignment);
626
45
    Seg->StartVA = MemoryPtr;
627
45
    log(formatv("mem: {0,-15} offset={1,-8} size={2,-8} align={3}", Seg->Name,
628
45
                MemoryPtr, Seg->Size, Seg->Alignment));
629
45
    MemoryPtr += Seg->Size;
630
45
  }
631
99
632
99
  // TODO: Add .bss space here.
633
99
  if (WasmSym::DataEnd)
634
82
    WasmSym::DataEnd->setVirtualAddress(MemoryPtr);
635
99
636
99
  log("mem: static data = " + Twine(MemoryPtr - DataStart));
637
99
638
99
  if (!Config->StackFirst)
639
98
    PlaceStack();
640
99
641
99
  // Set `__heap_base` to directly follow the end of the stack or global data.
642
99
  // The fact that this comes last means that a malloc/brk implementation
643
99
  // can grow the heap at runtime.
644
99
  if (!Config->Relocatable) {
645
82
    WasmSym::HeapBase->setVirtualAddress(MemoryPtr);
646
82
    log("mem: heap base   = " + Twine(MemoryPtr));
647
82
  }
648
99
649
99
  if (Config->InitialMemory != 0) {
650
3
    if (Config->InitialMemory != alignTo(Config->InitialMemory, WasmPageSize))
651
0
      error("initial memory must be " + Twine(WasmPageSize) + "-byte aligned");
652
3
    if (MemoryPtr > Config->InitialMemory)
653
0
      error("initial memory too small, " + Twine(MemoryPtr) + " bytes needed");
654
3
    else
655
3
      MemoryPtr = Config->InitialMemory;
656
3
  }
657
99
  uint32_t MemSize = alignTo(MemoryPtr, WasmPageSize);
658
99
  NumMemoryPages = MemSize / WasmPageSize;
659
99
  log("mem: total pages = " + Twine(NumMemoryPages));
660
99
661
99
  if (Config->MaxMemory != 0) {
662
2
    if (Config->MaxMemory != alignTo(Config->MaxMemory, WasmPageSize))
663
0
      error("maximum memory must be " + Twine(WasmPageSize) + "-byte aligned");
664
2
    if (MemoryPtr > Config->MaxMemory)
665
0
      error("maximum memory too small, " + Twine(MemoryPtr) + " bytes needed");
666
2
    MaxMemoryPages = Config->MaxMemory / WasmPageSize;
667
2
    log("mem: max pages   = " + Twine(MaxMemoryPages));
668
2
  }
669
99
}
670
671
SyntheticSection *Writer::createSyntheticSection(uint32_t Type,
672
711
                                                 StringRef Name) {
673
711
  auto Sec = make<SyntheticSection>(Type, Name);
674
711
  log("createSection: " + toString(*Sec));
675
711
  OutputSections.push_back(Sec);
676
711
  return Sec;
677
711
}
678
679
void Writer::createSections() {
680
  // Known sections
681
  createTypeSection();
682
  createImportSection();
683
  createFunctionSection();
684
  createTableSection();
685
  createMemorySection();
686
  createGlobalSection();
687
  createExportSection();
688
  createElemSection();
689
  createCodeSection();
690
  createDataSection();
691
  createCustomSections();
692
693
  // Custom sections
694
  if (Config->Relocatable) {
695
    createLinkingSection();
696
    createRelocSections();
697
  }
698
  if (!Config->StripDebug && !Config->StripAll)
699
    createNameSection();
700
701
  for (OutputSection *S : OutputSections) {
702
    S->setOffset(FileSize);
703
    S->finalizeContents();
704
    FileSize += S->getSize();
705
  }
706
}
707
708
99
void Writer::calculateImports() {
709
893
  for (Symbol *Sym : Symtab->getSymbols()) {
710
893
    if (!Sym->isUndefined())
711
860
      continue;
712
33
    if (isa<DataSymbol>(Sym))
713
4
      continue;
714
29
    if (Sym->isWeak() && 
!Config->Relocatable1
)
715
0
      continue;
716
29
    if (!Sym->isLive())
717
6
      continue;
718
23
    if (!Sym->IsUsedInRegularObj)
719
0
      continue;
720
23
721
23
    LLVM_DEBUG(dbgs() << "import: " << Sym->getName() << "\n");
722
23
    ImportedSymbols.emplace_back(Sym);
723
23
    if (auto *F = dyn_cast<FunctionSymbol>(Sym))
724
16
      F->setFunctionIndex(NumImportedFunctions++);
725
7
    else
726
7
      cast<GlobalSymbol>(Sym)->setGlobalIndex(NumImportedGlobals++);
727
23
  }
728
99
}
729
730
99
void Writer::calculateExports() {
731
99
  if (Config->Relocatable)
732
17
    return;
733
82
734
82
  if (!Config->Relocatable && !Config->ImportMemory)
735
80
    Exports.push_back(WasmExport{"memory", WASM_EXTERNAL_MEMORY, 0});
736
82
737
82
  if (!Config->Relocatable && Config->ExportTable)
738
1
    Exports.push_back(WasmExport{kFunctionTableName, WASM_EXTERNAL_TABLE, 0});
739
82
740
82
  unsigned FakeGlobalIndex = NumImportedGlobals + InputGlobals.size();
741
82
742
677
  for (Symbol *Sym : Symtab->getSymbols()) {
743
677
    if (!Sym->isExported())
744
365
      continue;
745
312
    if (!Sym->isLive())
746
0
      continue;
747
312
748
312
    StringRef Name = Sym->getName();
749
312
    WasmExport Export;
750
312
    if (auto *F = dyn_cast<DefinedFunction>(Sym)) {
751
138
      Export = {Name, WASM_EXTERNAL_FUNCTION, F->getFunctionIndex()};
752
174
    } else if (auto *G = dyn_cast<DefinedGlobal>(Sym)) {
753
2
      // TODO(sbc): Remove this check once to mutable global proposal is
754
2
      // implement in all major browsers.
755
2
      // See: https://github.com/WebAssembly/mutable-global
756
2
      if (G->getGlobalType()->Mutable) {
757
2
        // Only the __stack_pointer should ever be create as mutable.
758
2
        assert(G == WasmSym::StackPointer);
759
2
        continue;
760
2
      }
761
0
      Export = {Name, WASM_EXTERNAL_GLOBAL, G->getGlobalIndex()};
762
172
    } else {
763
172
      auto *D = cast<DefinedData>(Sym);
764
172
      DefinedFakeGlobals.emplace_back(D);
765
172
      Export = {Name, WASM_EXTERNAL_GLOBAL, FakeGlobalIndex++};
766
172
    }
767
312
768
312
    
LLVM_DEBUG310
(dbgs() << "Export: " << Name << "\n");
769
310
    Exports.push_back(Export);
770
310
  }
771
82
}
772
773
99
void Writer::assignSymtab() {
774
99
  if (!Config->Relocatable)
775
82
    return;
776
17
777
17
  StringMap<uint32_t> SectionSymbolIndices;
778
17
779
17
  unsigned SymbolIndex = SymtabEntries.size();
780
34
  for (ObjFile *File : Symtab->ObjectFiles) {
781
34
    LLVM_DEBUG(dbgs() << "Symtab entries: " << File->getName() << "\n");
782
240
    for (Symbol *Sym : File->getSymbols()) {
783
240
      if (Sym->getFile() != File)
784
7
        continue;
785
233
786
233
      if (auto *S = dyn_cast<SectionSymbol>(Sym)) {
787
0
        StringRef Name = S->getName();
788
0
        if (CustomSectionMapping.count(Name) == 0)
789
0
          continue;
790
0
791
0
        auto SSI = SectionSymbolIndices.find(Name);
792
0
        if (SSI != SectionSymbolIndices.end()) {
793
0
          Sym->setOutputSymbolIndex(SSI->second);
794
0
          continue;
795
0
        }
796
0
797
0
        SectionSymbolIndices[Name] = SymbolIndex;
798
0
        CustomSectionSymbols[Name] = cast<SectionSymbol>(Sym);
799
0
800
0
        Sym->markLive();
801
0
      }
802
233
803
233
      // (Since this is relocatable output, GC is not performed so symbols must
804
233
      // be live.)
805
233
      assert(Sym->isLive());
806
233
      Sym->setOutputSymbolIndex(SymbolIndex++);
807
233
      SymtabEntries.emplace_back(Sym);
808
233
    }
809
34
  }
810
17
811
17
  // For the moment, relocatable output doesn't contain any synthetic functions,
812
17
  // so no need to look through the Symtab for symbols not referenced by
813
17
  // Symtab->ObjectFiles.
814
17
}
815
816
494
uint32_t Writer::lookupType(const WasmSignature &Sig) {
817
494
  auto It = TypeIndices.find(Sig);
818
494
  if (It == TypeIndices.end()) {
819
0
    error("type not found: " + toString(Sig));
820
0
    return 0;
821
0
  }
822
494
  return It->second;
823
494
}
824
825
514
uint32_t Writer::registerType(const WasmSignature &Sig) {
826
514
  auto Pair = TypeIndices.insert(std::make_pair(Sig, Types.size()));
827
514
  if (Pair.second) {
828
167
    LLVM_DEBUG(dbgs() << "type " << toString(Sig) << "\n");
829
167
    Types.push_back(&Sig);
830
167
  }
831
514
  return Pair.first->second;
832
514
}
833
834
99
void Writer::calculateTypes() {
835
99
  // The output type section is the union of the following sets:
836
99
  // 1. Any signature used in the TYPE relocation
837
99
  // 2. The signatures of all imported functions
838
99
  // 3. The signatures of all defined functions
839
99
840
163
  for (ObjFile *File : Symtab->ObjectFiles) {
841
163
    ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
842
378
    for (uint32_t I = 0; I < Types.size(); 
I++215
)
843
215
      if (File->TypeIsUsed[I])
844
10
        File->TypeMap[I] = registerType(Types[I]);
845
163
  }
846
99
847
99
  for (const Symbol *Sym : ImportedSymbols)
848
23
    if (auto *F = dyn_cast<FunctionSymbol>(Sym))
849
16
      registerType(*F->FunctionType);
850
99
851
99
  for (const InputFunction *F : InputFunctions)
852
478
    registerType(F->Signature);
853
99
}
854
855
99
void Writer::assignIndexes() {
856
99
  uint32_t FunctionIndex = NumImportedFunctions + InputFunctions.size();
857
497
  auto AddDefinedFunction = [&](InputFunction *Func) {
858
497
    if (!Func->Live)
859
19
      return;
860
478
    InputFunctions.emplace_back(Func);
861
478
    Func->setFunctionIndex(FunctionIndex++);
862
478
  };
863
99
864
99
  for (InputFunction *Func : Symtab->SyntheticFunctions)
865
89
    AddDefinedFunction(Func);
866
99
867
163
  for (ObjFile *File : Symtab->ObjectFiles) {
868
163
    LLVM_DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
869
163
    for (InputFunction *Func : File->Functions)
870
408
      AddDefinedFunction(Func);
871
163
  }
872
99
873
99
  uint32_t TableIndex = kInitialTableOffset;
874
773
  auto HandleRelocs = [&](InputChunk *Chunk) {
875
773
    if (!Chunk->Live)
876
222
      return;
877
551
    ObjFile *File = Chunk->File;
878
551
    ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
879
551
    for (const WasmRelocation &Reloc : Chunk->getRelocations()) {
880
369
      if (Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_I32 ||
881
369
          
Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_SLEB357
) {
882
49
        FunctionSymbol *Sym = File->getFunctionSymbol(Reloc.Index);
883
49
        if (Sym->hasTableIndex() || 
!Sym->hasFunctionIndex()41
)
884
8
          continue;
885
41
        Sym->setTableIndex(TableIndex++);
886
41
        IndirectFunctions.emplace_back(Sym);
887
320
      } else if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB) {
888
10
        // Mark target type as live
889
10
        File->TypeMap[Reloc.Index] = registerType(Types[Reloc.Index]);
890
10
        File->TypeIsUsed[Reloc.Index] = true;
891
10
      }
892
369
    }
893
551
  };
894
99
895
163
  for (ObjFile *File : Symtab->ObjectFiles) {
896
163
    LLVM_DEBUG(dbgs() << "Handle relocs: " << File->getName() << "\n");
897
163
    for (InputChunk *Chunk : File->Functions)
898
408
      HandleRelocs(Chunk);
899
163
    for (InputChunk *Chunk : File->Segments)
900
79
      HandleRelocs(Chunk);
901
163
    for (auto &P : File->CustomSections)
902
286
      HandleRelocs(P);
903
163
  }
904
99
905
99
  uint32_t GlobalIndex = NumImportedGlobals + InputGlobals.size();
906
99
  auto AddDefinedGlobal = [&](InputGlobal *Global) {
907
86
    if (Global->Live) {
908
85
      LLVM_DEBUG(dbgs() << "AddDefinedGlobal: " << GlobalIndex << "\n");
909
85
      Global->setGlobalIndex(GlobalIndex++);
910
85
      InputGlobals.push_back(Global);
911
85
    }
912
86
  };
913
99
914
99
  for (InputGlobal *Global : Symtab->SyntheticGlobals)
915
82
    AddDefinedGlobal(Global);
916
99
917
163
  for (ObjFile *File : Symtab->ObjectFiles) {
918
163
    LLVM_DEBUG(dbgs() << "Globals: " << File->getName() << "\n");
919
163
    for (InputGlobal *Global : File->Globals)
920
4
      AddDefinedGlobal(Global);
921
163
  }
922
99
}
923
924
70
static StringRef getOutputDataSegmentName(StringRef Name) {
925
70
  if (!Config->MergeDataSegments)
926
28
    return Name;
927
42
  if (Name.startswith(".text."))
928
0
    return ".text";
929
42
  if (Name.startswith(".data."))
930
29
    return ".data";
931
13
  if (Name.startswith(".bss."))
932
8
    return ".bss";
933
5
  if (Name.startswith(".rodata."))
934
5
    return ".rodata";
935
0
  return Name;
936
0
}
937
938
99
void Writer::createOutputSegments() {
939
163
  for (ObjFile *File : Symtab->ObjectFiles) {
940
163
    for (InputSegment *Segment : File->Segments) {
941
79
      if (!Segment->Live)
942
9
        continue;
943
70
      StringRef Name = getOutputDataSegmentName(Segment->getName());
944
70
      OutputSegment *&S = SegmentMap[Name];
945
70
      if (S == nullptr) {
946
45
        LLVM_DEBUG(dbgs() << "new segment: " << Name << "\n");
947
45
        S = make<OutputSegment>(Name, Segments.size());
948
45
        Segments.push_back(S);
949
45
      }
950
70
      S->addInputSegment(Segment);
951
70
      LLVM_DEBUG(dbgs() << "added data: " << Name << ": " << S->Size << "\n");
952
70
    }
953
163
  }
954
99
}
955
956
static const int OPCODE_CALL = 0x10;
957
static const int OPCODE_END = 0xb;
958
959
// Create synthetic "__wasm_call_ctors" function based on ctor functions
960
// in input object.
961
82
void Writer::createCtorFunction() {
962
82
  // First write the body's contents to a string.
963
82
  std::string BodyContent;
964
82
  {
965
82
    raw_string_ostream OS(BodyContent);
966
82
    writeUleb128(OS, 0, "num locals");
967
82
    for (const WasmInitEntry &F : InitFunctions) {
968
13
      writeU8(OS, OPCODE_CALL, "CALL");
969
13
      writeUleb128(OS, F.Sym->getFunctionIndex(), "function index");
970
13
    }
971
82
    writeU8(OS, OPCODE_END, "END");
972
82
  }
973
82
974
82
  // Once we know the size of the body we can create the final function body
975
82
  std::string FunctionBody;
976
82
  {
977
82
    raw_string_ostream OS(FunctionBody);
978
82
    writeUleb128(OS, BodyContent.size(), "function size");
979
82
    OS << BodyContent;
980
82
  }
981
82
982
82
  ArrayRef<uint8_t> Body = toArrayRef(Saver.save(FunctionBody));
983
82
  cast<SyntheticFunction>(WasmSym::CallCtors->Function)->setBody(Body);
984
82
}
985
986
// Populate InitFunctions vector with init functions from all input objects.
987
// This is then used either when creating the output linking section or to
988
// synthesize the "__wasm_call_ctors" function.
989
99
void Writer::calculateInitFunctions() {
990
163
  for (ObjFile *File : Symtab->ObjectFiles) {
991
163
    const WasmLinkingData &L = File->getWasmObj()->linkingData();
992
163
    for (const WasmInitFunc &F : L.InitFunctions) {
993
26
      FunctionSymbol *Sym = File->getFunctionSymbol(F.Symbol);
994
26
      if (*Sym->FunctionType != WasmSignature{{}, {}})
995
0
        error("invalid signature for init func: " + toString(*Sym));
996
26
      InitFunctions.emplace_back(WasmInitEntry{Sym, F.Priority});
997
26
    }
998
163
  }
999
99
1000
99
  // Sort in order of priority (lowest first) so that they are called
1001
99
  // in the correct order.
1002
99
  std::stable_sort(InitFunctions.begin(), InitFunctions.end(),
1003
99
                   [](const WasmInitEntry &L, const WasmInitEntry &R) {
1004
64
                     return L.Priority < R.Priority;
1005
64
                   });
1006
99
}
1007
1008
void Writer::run() {
1009
  if (Config->Relocatable)
1010
    Config->GlobalBase = 0;
1011
1012
  log("-- calculateImports");
1013
  calculateImports();
1014
  log("-- assignIndexes");
1015
  assignIndexes();
1016
  log("-- calculateInitFunctions");
1017
  calculateInitFunctions();
1018
  if (!Config->Relocatable)
1019
    createCtorFunction();
1020
  log("-- calculateTypes");
1021
  calculateTypes();
1022
  log("-- layoutMemory");
1023
  layoutMemory();
1024
  log("-- calculateExports");
1025
  calculateExports();
1026
  log("-- calculateCustomSections");
1027
  calculateCustomSections();
1028
  log("-- assignSymtab");
1029
  assignSymtab();
1030
1031
  if (errorHandler().Verbose) {
1032
    log("Defined Functions: " + Twine(InputFunctions.size()));
1033
    log("Defined Globals  : " + Twine(InputGlobals.size()));
1034
    log("Function Imports : " + Twine(NumImportedFunctions));
1035
    log("Global Imports   : " + Twine(NumImportedGlobals));
1036
    for (ObjFile *File : Symtab->ObjectFiles)
1037
      File->dumpInfo();
1038
  }
1039
1040
  createHeader();
1041
  log("-- createSections");
1042
  createSections();
1043
1044
  log("-- openFile");
1045
  openFile();
1046
  if (errorCount())
1047
    return;
1048
1049
  writeHeader();
1050
1051
  log("-- writeSections");
1052
  writeSections();
1053
  if (errorCount())
1054
    return;
1055
1056
  if (Error E = Buffer->commit())
1057
    fatal("failed to write the output file: " + toString(std::move(E)));
1058
}
1059
1060
// Open a result file.
1061
99
void Writer::openFile() {
1062
99
  log("writing: " + Config->OutputFile);
1063
99
1064
99
  Expected<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
1065
99
      FileOutputBuffer::create(Config->OutputFile, FileSize,
1066
99
                               FileOutputBuffer::F_executable);
1067
99
1068
99
  if (!BufferOrErr)
1069
0
    error("failed to open " + Config->OutputFile + ": " +
1070
0
          toString(BufferOrErr.takeError()));
1071
99
  else
1072
99
    Buffer = std::move(*BufferOrErr);
1073
99
}
1074
1075
99
void Writer::createHeader() {
1076
99
  raw_string_ostream OS(Header);
1077
99
  writeBytes(OS, WasmMagic, sizeof(WasmMagic), "wasm magic");
1078
99
  writeU32(OS, WasmVersion, "wasm version");
1079
99
  OS.flush();
1080
99
  FileSize += Header.size();
1081
99
}
1082
1083
99
void lld::wasm::writeResult() { Writer().run(); }