Coverage Report

Created: 2018-08-19 21:11

/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->FunctionType);
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->isExported())
744
0
      continue;
745
0
    if (!Sym->isLive())
746
0
      continue;
747
0
748
0
    StringRef Name = Sym->getName();
749
0
    WasmExport Export;
750
0
    if (auto *F = dyn_cast<DefinedFunction>(Sym)) {
751
0
      Export = {Name, WASM_EXTERNAL_FUNCTION, F->getFunctionIndex()};
752
0
    } else if (auto *G = dyn_cast<DefinedGlobal>(Sym)) {
753
0
      // TODO(sbc): Remove this check once to mutable global proposal is
754
0
      // implement in all major browsers.
755
0
      // See: https://github.com/WebAssembly/mutable-global
756
0
      if (G->getGlobalType()->Mutable) {
757
0
        // Only the __stack_pointer should ever be create as mutable.
758
0
        assert(G == WasmSym::StackPointer);
759
0
        continue;
760
0
      }
761
0
      Export = {Name, WASM_EXTERNAL_GLOBAL, G->getGlobalIndex()};
762
0
    } else {
763
0
      auto *D = cast<DefinedData>(Sym);
764
0
      DefinedFakeGlobals.emplace_back(D);
765
0
      Export = {Name, WASM_EXTERNAL_GLOBAL, FakeGlobalIndex++};
766
0
    }
767
0
768
0
    LLVM_DEBUG(dbgs() << "Export: " << Name << "\n");
769
0
    Exports.push_back(Export);
770
0
  }
771
0
}
772
773
0
void Writer::assignSymtab() {
774
0
  if (!Config->Relocatable)
775
0
    return;
776
0
777
0
  StringMap<uint32_t> SectionSymbolIndices;
778
0
779
0
  unsigned SymbolIndex = SymtabEntries.size();
780
0
  for (ObjFile *File : Symtab->ObjectFiles) {
781
0
    LLVM_DEBUG(dbgs() << "Symtab entries: " << File->getName() << "\n");
782
0
    for (Symbol *Sym : File->getSymbols()) {
783
0
      if (Sym->getFile() != File)
784
0
        continue;
785
0
786
0
      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
0
803
0
      // (Since this is relocatable output, GC is not performed so symbols must
804
0
      // be live.)
805
0
      assert(Sym->isLive());
806
0
      Sym->setOutputSymbolIndex(SymbolIndex++);
807
0
      SymtabEntries.emplace_back(Sym);
808
0
    }
809
0
  }
810
0
811
0
  // For the moment, relocatable output doesn't contain any synthetic functions,
812
0
  // so no need to look through the Symtab for symbols not referenced by
813
0
  // Symtab->ObjectFiles.
814
0
}
815
816
0
uint32_t Writer::lookupType(const WasmSignature &Sig) {
817
0
  auto It = TypeIndices.find(Sig);
818
0
  if (It == TypeIndices.end()) {
819
0
    error("type not found: " + toString(Sig));
820
0
    return 0;
821
0
  }
822
0
  return It->second;
823
0
}
824
825
0
uint32_t Writer::registerType(const WasmSignature &Sig) {
826
0
  auto Pair = TypeIndices.insert(std::make_pair(Sig, Types.size()));
827
0
  if (Pair.second) {
828
0
    LLVM_DEBUG(dbgs() << "type " << toString(Sig) << "\n");
829
0
    Types.push_back(&Sig);
830
0
  }
831
0
  return Pair.first->second;
832
0
}
833
834
0
void Writer::calculateTypes() {
835
0
  // The output type section is the union of the following sets:
836
0
  // 1. Any signature used in the TYPE relocation
837
0
  // 2. The signatures of all imported functions
838
0
  // 3. The signatures of all defined functions
839
0
840
0
  for (ObjFile *File : Symtab->ObjectFiles) {
841
0
    ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
842
0
    for (uint32_t I = 0; I < Types.size(); I++)
843
0
      if (File->TypeIsUsed[I])
844
0
        File->TypeMap[I] = registerType(Types[I]);
845
0
  }
846
0
847
0
  for (const Symbol *Sym : ImportedSymbols)
848
0
    if (auto *F = dyn_cast<FunctionSymbol>(Sym))
849
0
      registerType(*F->FunctionType);
850
0
851
0
  for (const InputFunction *F : InputFunctions)
852
0
    registerType(F->Signature);
853
0
}
854
855
0
void Writer::assignIndexes() {
856
0
  uint32_t FunctionIndex = NumImportedFunctions + InputFunctions.size();
857
0
  auto AddDefinedFunction = [&](InputFunction *Func) {
858
0
    if (!Func->Live)
859
0
      return;
860
0
    InputFunctions.emplace_back(Func);
861
0
    Func->setFunctionIndex(FunctionIndex++);
862
0
  };
863
0
864
0
  for (InputFunction *Func : Symtab->SyntheticFunctions)
865
0
    AddDefinedFunction(Func);
866
0
867
0
  for (ObjFile *File : Symtab->ObjectFiles) {
868
0
    LLVM_DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
869
0
    for (InputFunction *Func : File->Functions)
870
0
      AddDefinedFunction(Func);
871
0
  }
872
0
873
0
  uint32_t TableIndex = kInitialTableOffset;
874
0
  auto HandleRelocs = [&](InputChunk *Chunk) {
875
0
    if (!Chunk->Live)
876
0
      return;
877
0
    ObjFile *File = Chunk->File;
878
0
    ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
879
0
    for (const WasmRelocation &Reloc : Chunk->getRelocations()) {
880
0
      if (Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_I32 ||
881
0
          Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_SLEB) {
882
0
        FunctionSymbol *Sym = File->getFunctionSymbol(Reloc.Index);
883
0
        if (Sym->hasTableIndex() || !Sym->hasFunctionIndex())
884
0
          continue;
885
0
        Sym->setTableIndex(TableIndex++);
886
0
        IndirectFunctions.emplace_back(Sym);
887
0
      } else if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB) {
888
0
        // Mark target type as live
889
0
        File->TypeMap[Reloc.Index] = registerType(Types[Reloc.Index]);
890
0
        File->TypeIsUsed[Reloc.Index] = true;
891
0
      }
892
0
    }
893
0
  };
894
0
895
0
  for (ObjFile *File : Symtab->ObjectFiles) {
896
0
    LLVM_DEBUG(dbgs() << "Handle relocs: " << File->getName() << "\n");
897
0
    for (InputChunk *Chunk : File->Functions)
898
0
      HandleRelocs(Chunk);
899
0
    for (InputChunk *Chunk : File->Segments)
900
0
      HandleRelocs(Chunk);
901
0
    for (auto &P : File->CustomSections)
902
0
      HandleRelocs(P);
903
0
  }
904
0
905
0
  uint32_t GlobalIndex = NumImportedGlobals + InputGlobals.size();
906
0
  auto AddDefinedGlobal = [&](InputGlobal *Global) {
907
0
    if (Global->Live) {
908
0
      LLVM_DEBUG(dbgs() << "AddDefinedGlobal: " << GlobalIndex << "\n");
909
0
      Global->setGlobalIndex(GlobalIndex++);
910
0
      InputGlobals.push_back(Global);
911
0
    }
912
0
  };
913
0
914
0
  for (InputGlobal *Global : Symtab->SyntheticGlobals)
915
0
    AddDefinedGlobal(Global);
916
0
917
0
  for (ObjFile *File : Symtab->ObjectFiles) {
918
0
    LLVM_DEBUG(dbgs() << "Globals: " << File->getName() << "\n");
919
0
    for (InputGlobal *Global : File->Globals)
920
0
      AddDefinedGlobal(Global);
921
0
  }
922
0
}
923
924
0
static StringRef getOutputDataSegmentName(StringRef Name) {
925
0
  if (!Config->MergeDataSegments)
926
0
    return Name;
927
0
  if (Name.startswith(".text."))
928
0
    return ".text";
929
0
  if (Name.startswith(".data."))
930
0
    return ".data";
931
0
  if (Name.startswith(".bss."))
932
0
    return ".bss";
933
0
  if (Name.startswith(".rodata."))
934
0
    return ".rodata";
935
0
  return Name;
936
0
}
937
938
0
void Writer::createOutputSegments() {
939
0
  for (ObjFile *File : Symtab->ObjectFiles) {
940
0
    for (InputSegment *Segment : File->Segments) {
941
0
      if (!Segment->Live)
942
0
        continue;
943
0
      StringRef Name = getOutputDataSegmentName(Segment->getName());
944
0
      OutputSegment *&S = SegmentMap[Name];
945
0
      if (S == nullptr) {
946
0
        LLVM_DEBUG(dbgs() << "new segment: " << Name << "\n");
947
0
        S = make<OutputSegment>(Name, Segments.size());
948
0
        Segments.push_back(S);
949
0
      }
950
0
      S->addInputSegment(Segment);
951
0
      LLVM_DEBUG(dbgs() << "added data: " << Name << ": " << S->Size << "\n");
952
0
    }
953
0
  }
954
0
}
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
0
void Writer::createCtorFunction() {
962
0
  // First write the body's contents to a string.
963
0
  std::string BodyContent;
964
0
  {
965
0
    raw_string_ostream OS(BodyContent);
966
0
    writeUleb128(OS, 0, "num locals");
967
0
    for (const WasmInitEntry &F : InitFunctions) {
968
0
      writeU8(OS, OPCODE_CALL, "CALL");
969
0
      writeUleb128(OS, F.Sym->getFunctionIndex(), "function index");
970
0
    }
971
0
    writeU8(OS, OPCODE_END, "END");
972
0
  }
973
0
974
0
  // Once we know the size of the body we can create the final function body
975
0
  std::string FunctionBody;
976
0
  {
977
0
    raw_string_ostream OS(FunctionBody);
978
0
    writeUleb128(OS, BodyContent.size(), "function size");
979
0
    OS << BodyContent;
980
0
  }
981
0
982
0
  ArrayRef<uint8_t> Body = toArrayRef(Saver.save(FunctionBody));
983
0
  cast<SyntheticFunction>(WasmSym::CallCtors->Function)->setBody(Body);
984
0
}
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
0
void Writer::calculateInitFunctions() {
990
0
  for (ObjFile *File : Symtab->ObjectFiles) {
991
0
    const WasmLinkingData &L = File->getWasmObj()->linkingData();
992
0
    for (const WasmInitFunc &F : L.InitFunctions) {
993
0
      FunctionSymbol *Sym = File->getFunctionSymbol(F.Symbol);
994
0
      if (*Sym->FunctionType != WasmSignature{{}, WASM_TYPE_NORESULT})
995
0
        error("invalid signature for init func: " + toString(*Sym));
996
0
      InitFunctions.emplace_back(WasmInitEntry{Sym, F.Priority});
997
0
    }
998
0
  }
999
0
1000
0
  // Sort in order of priority (lowest first) so that they are called
1001
0
  // in the correct order.
1002
0
  std::stable_sort(InitFunctions.begin(), InitFunctions.end(),
1003
0
                   [](const WasmInitEntry &L, const WasmInitEntry &R) {
1004
0
                     return L.Priority < R.Priority;
1005
0
                   });
1006
0
}
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
0
void Writer::openFile() {
1062
0
  log("writing: " + Config->OutputFile);
1063
0
1064
0
  Expected<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
1065
0
      FileOutputBuffer::create(Config->OutputFile, FileSize,
1066
0
                               FileOutputBuffer::F_executable);
1067
0
1068
0
  if (!BufferOrErr)
1069
0
    error("failed to open " + Config->OutputFile + ": " +
1070
0
          toString(BufferOrErr.takeError()));
1071
0
  else
1072
0
    Buffer = std::move(*BufferOrErr);
1073
0
}
1074
1075
0
void Writer::createHeader() {
1076
0
  raw_string_ostream OS(Header);
1077
0
  writeBytes(OS, WasmMagic, sizeof(WasmMagic), "wasm magic");
1078
0
  writeU32(OS, WasmVersion, "wasm version");
1079
0
  OS.flush();
1080
0
  FileSize += Header.size();
1081
0
}
1082
1083
0
void lld::wasm::writeResult() { Writer().run(); }