Coverage Report

Created: 2018-06-25 02:00

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