1//===- SyntheticSection.h ---------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Synthetic sections represent chunks of linker-created data. If you
10// need to create a chunk of data that to be included in some section
11// in the result, you probably want to create that as a synthetic section.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLD_WASM_SYNTHETIC_SECTIONS_H
16#define LLD_WASM_SYNTHETIC_SECTIONS_H
17
18#include "OutputSections.h"
19
20#include "llvm/ADT/SmallSet.h"
21#include "llvm/ADT/StringMap.h"
22#include "llvm/BinaryFormat/WasmTraits.h"
23#include <optional>
24
25#define DEBUG_TYPE "lld"
26
27namespace lld::wasm {
28
29// An init entry to be written to either the synthetic init func or the
30// linking metadata.
31struct WasmInitEntry {
32 const FunctionSymbol *sym;
33 uint32_t priority;
34};
35
36class SyntheticSection : public OutputSection {
37public:
38 SyntheticSection(uint32_t type, std::string name = "")
39 : OutputSection(type, name), bodyOutputStream(body) {
40 if (!name.empty())
41 writeStr(os&: bodyOutputStream, string: name, msg: "section name");
42 }
43
44 void writeTo(uint8_t *buf) override {
45 assert(offset);
46 log(msg: "writing " + toString(section: *this));
47 memcpy(dest: buf + offset, src: header.data(), n: header.size());
48 memcpy(dest: buf + offset + header.size(), src: body.data(), n: body.size());
49 }
50
51 size_t getSize() const override { return header.size() + body.size(); }
52
53 virtual void writeBody() {}
54
55 virtual void assignIndexes() {}
56
57 void finalizeContents() override {
58 writeBody();
59 createHeader(bodySize: body.size());
60 }
61
62 raw_ostream &getStream() { return bodyOutputStream; }
63
64 std::string body;
65
66protected:
67 llvm::raw_string_ostream bodyOutputStream;
68};
69
70// Create the custom "dylink" section containing information for the dynamic
71// linker.
72// See
73// https://github.com/WebAssembly/tool-conventions/blob/main/DynamicLinking.md
74class DylinkSection : public SyntheticSection {
75public:
76 DylinkSection() : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "dylink.0") {}
77 bool isNeeded() const override;
78 void writeBody() override;
79
80 uint32_t memAlign = 0;
81 uint32_t memSize = 0;
82};
83
84class TypeSection : public SyntheticSection {
85public:
86 TypeSection() : SyntheticSection(llvm::wasm::WASM_SEC_TYPE) {}
87
88 bool isNeeded() const override { return types.size() > 0; };
89 void writeBody() override;
90 uint32_t registerType(const WasmSignature &sig);
91 uint32_t lookupType(const WasmSignature &sig);
92
93protected:
94 std::vector<const WasmSignature *> types;
95 llvm::DenseMap<WasmSignature, int32_t> typeIndices;
96};
97
98/**
99 * A key for some kind of imported entity of type `T`.
100 *
101 * Used when de-duplicating imports.
102 */
103template <typename T> struct ImportKey {
104public:
105 enum class State { Plain, Empty, Tombstone };
106
107public:
108 T type;
109 std::optional<StringRef> importModule;
110 std::optional<StringRef> importName;
111 State state;
112
113public:
114 ImportKey(T type) : type(type), state(State::Plain) {}
115 ImportKey(T type, State state) : type(type), state(state) {}
116 ImportKey(T type, std::optional<StringRef> importModule,
117 std::optional<StringRef> importName)
118 : type(type), importModule(importModule), importName(importName),
119 state(State::Plain) {}
120};
121
122template <typename T>
123inline bool operator==(const ImportKey<T> &lhs, const ImportKey<T> &rhs) {
124 return lhs.state == rhs.state && lhs.importModule == rhs.importModule &&
125 lhs.importName == rhs.importName && lhs.type == rhs.type;
126}
127
128} // namespace lld::wasm
129
130// `ImportKey<T>` can be used as a key in a `DenseMap` if `T` can be used as a
131// key in a `DenseMap`.
132namespace llvm {
133template <typename T> struct DenseMapInfo<lld::wasm::ImportKey<T>> {
134 static lld::wasm::ImportKey<T> getEmptyKey() {
135 typename lld::wasm::ImportKey<T> key(llvm::DenseMapInfo<T>::getEmptyKey());
136 key.state = lld::wasm::ImportKey<T>::State::Empty;
137 return key;
138 }
139 static lld::wasm::ImportKey<T> getTombstoneKey() {
140 typename lld::wasm::ImportKey<T> key(llvm::DenseMapInfo<T>::getEmptyKey());
141 key.state = lld::wasm::ImportKey<T>::State::Tombstone;
142 return key;
143 }
144 static unsigned getHashValue(const lld::wasm::ImportKey<T> &key) {
145 uintptr_t hash = hash_value(key.importModule);
146 hash = hash_combine(hash, key.importName);
147 hash = hash_combine(hash, llvm::DenseMapInfo<T>::getHashValue(key.type));
148 hash = hash_combine(hash, key.state);
149 return hash;
150 }
151 static bool isEqual(const lld::wasm::ImportKey<T> &lhs,
152 const lld::wasm::ImportKey<T> &rhs) {
153 return lhs == rhs;
154 }
155};
156} // end namespace llvm
157
158namespace lld {
159namespace wasm {
160
161class ImportSection : public SyntheticSection {
162public:
163 ImportSection() : SyntheticSection(llvm::wasm::WASM_SEC_IMPORT) {}
164 bool isNeeded() const override { return getNumImports() > 0; }
165 void writeBody() override;
166 void addImport(Symbol *sym);
167 void addGOTEntry(Symbol *sym);
168 void seal() { isSealed = true; }
169 uint32_t getNumImports() const;
170 uint32_t getNumImportedGlobals() const {
171 assert(isSealed);
172 return numImportedGlobals;
173 }
174 uint32_t getNumImportedFunctions() const {
175 assert(isSealed);
176 return numImportedFunctions;
177 }
178 uint32_t getNumImportedTags() const {
179 assert(isSealed);
180 return numImportedTags;
181 }
182 uint32_t getNumImportedTables() const {
183 assert(isSealed);
184 return numImportedTables;
185 }
186
187 std::vector<const Symbol *> importedSymbols;
188 std::vector<const Symbol *> gotSymbols;
189
190protected:
191 bool isSealed = false;
192 unsigned numImportedGlobals = 0;
193 unsigned numImportedFunctions = 0;
194 unsigned numImportedTags = 0;
195 unsigned numImportedTables = 0;
196 llvm::DenseMap<ImportKey<WasmGlobalType>, uint32_t> importedGlobals;
197 llvm::DenseMap<ImportKey<WasmSignature>, uint32_t> importedFunctions;
198 llvm::DenseMap<ImportKey<WasmTableType>, uint32_t> importedTables;
199 llvm::DenseMap<ImportKey<WasmSignature>, uint32_t> importedTags;
200};
201
202class FunctionSection : public SyntheticSection {
203public:
204 FunctionSection() : SyntheticSection(llvm::wasm::WASM_SEC_FUNCTION) {}
205
206 bool isNeeded() const override { return inputFunctions.size() > 0; };
207 void writeBody() override;
208 void addFunction(InputFunction *func);
209
210 std::vector<InputFunction *> inputFunctions;
211
212protected:
213};
214
215class TableSection : public SyntheticSection {
216public:
217 TableSection() : SyntheticSection(llvm::wasm::WASM_SEC_TABLE) {}
218
219 bool isNeeded() const override { return inputTables.size() > 0; };
220 void assignIndexes() override;
221 void writeBody() override;
222 void addTable(InputTable *table);
223
224 std::vector<InputTable *> inputTables;
225};
226
227class MemorySection : public SyntheticSection {
228public:
229 MemorySection() : SyntheticSection(llvm::wasm::WASM_SEC_MEMORY) {}
230
231 bool isNeeded() const override { return !ctx.arg.memoryImport.has_value(); }
232 void writeBody() override;
233
234 uint64_t numMemoryPages = 0;
235 uint64_t maxMemoryPages = 0;
236};
237
238// The tag section contains a list of declared wasm tags associated with the
239// module. Currently the only supported tag kind is exceptions. All C++
240// exceptions are represented by a single tag. A tag entry in this section
241// contains information on what kind of tag it is (e.g. exception) and the type
242// of values associated with the tag. (In Wasm, a tag can contain multiple
243// values of primitive types. But for C++ exceptions, we just throw a pointer
244// which is an i32 value (for wasm32 architecture), so the signature of C++
245// exception is (i32)->(void), because all exception tag types are assumed to
246// have void return type to share WasmSignature with functions.)
247class TagSection : public SyntheticSection {
248public:
249 TagSection() : SyntheticSection(llvm::wasm::WASM_SEC_TAG) {}
250 void writeBody() override;
251 bool isNeeded() const override { return inputTags.size() > 0; }
252 void addTag(InputTag *tag);
253
254 std::vector<InputTag *> inputTags;
255};
256
257class GlobalSection : public SyntheticSection {
258public:
259 GlobalSection() : SyntheticSection(llvm::wasm::WASM_SEC_GLOBAL) {}
260
261 static bool classof(const OutputSection *sec) {
262 return sec->type == llvm::wasm::WASM_SEC_GLOBAL;
263 }
264
265 uint32_t numGlobals() const {
266 assert(isSealed);
267 return inputGlobals.size() + dataAddressGlobals.size() +
268 internalGotSymbols.size();
269 }
270 bool isNeeded() const override { return numGlobals() > 0; }
271 void assignIndexes() override;
272 void writeBody() override;
273 void addGlobal(InputGlobal *global);
274
275 // Add an internal GOT entry global that corresponds to the given symbol.
276 // Normally GOT entries are imported and assigned by the external dynamic
277 // linker. However, when linking PIC code statically or when linking with
278 // -Bsymbolic we can internalize GOT entries by declaring globals the hold
279 // symbol addresses.
280 //
281 // For the static linking case these internal globals can be completely
282 // eliminated by a post-link optimizer such as wasm-opt.
283 //
284 // TODO(sbc): Another approach to optimizing these away could be to use
285 // specific relocation types combined with linker relaxation which could
286 // transform a `global.get` to an `i32.const`.
287 void addInternalGOTEntry(Symbol *sym);
288 bool needsRelocations() {
289 if (ctx.arg.extendedConst)
290 return false;
291 return llvm::any_of(Range&: internalGotSymbols,
292 P: [=](Symbol *sym) { return !sym->isTLS(); });
293 }
294 bool needsTLSRelocations() {
295 return llvm::any_of(Range&: internalGotSymbols,
296 P: [=](Symbol *sym) { return sym->isTLS(); });
297 }
298 void generateRelocationCode(raw_ostream &os, bool TLS) const;
299
300 std::vector<DefinedData *> dataAddressGlobals;
301 std::vector<InputGlobal *> inputGlobals;
302 std::vector<Symbol *> internalGotSymbols;
303
304protected:
305 bool isSealed = false;
306};
307
308class ExportSection : public SyntheticSection {
309public:
310 ExportSection() : SyntheticSection(llvm::wasm::WASM_SEC_EXPORT) {}
311 bool isNeeded() const override { return exports.size() > 0; }
312 void writeBody() override;
313
314 std::vector<llvm::wasm::WasmExport> exports;
315 std::vector<const Symbol *> exportedSymbols;
316};
317
318class StartSection : public SyntheticSection {
319public:
320 StartSection() : SyntheticSection(llvm::wasm::WASM_SEC_START) {}
321 bool isNeeded() const override;
322 void writeBody() override;
323};
324
325class ElemSection : public SyntheticSection {
326public:
327 ElemSection() : SyntheticSection(llvm::wasm::WASM_SEC_ELEM) {}
328 bool isNeeded() const override { return indirectFunctions.size() > 0; };
329 void writeBody() override;
330 void addEntry(FunctionSymbol *sym);
331 uint32_t numEntries() const { return indirectFunctions.size(); }
332
333protected:
334 std::vector<const FunctionSymbol *> indirectFunctions;
335};
336
337class DataCountSection : public SyntheticSection {
338public:
339 DataCountSection(ArrayRef<OutputSegment *> segments);
340 bool isNeeded() const override;
341 void writeBody() override;
342
343protected:
344 uint32_t numSegments;
345};
346
347// Create the custom "linking" section containing linker metadata.
348// This is only created when relocatable output is requested.
349class LinkingSection : public SyntheticSection {
350public:
351 LinkingSection(const std::vector<WasmInitEntry> &initFunctions,
352 const std::vector<OutputSegment *> &dataSegments)
353 : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "linking"),
354 initFunctions(initFunctions), dataSegments(dataSegments) {}
355 bool isNeeded() const override {
356 return ctx.arg.relocatable || ctx.arg.emitRelocs;
357 }
358 void writeBody() override;
359 void addToSymtab(Symbol *sym);
360
361protected:
362 std::vector<const Symbol *> symtabEntries;
363 llvm::StringMap<uint32_t> sectionSymbolIndices;
364 const std::vector<WasmInitEntry> &initFunctions;
365 const std::vector<OutputSegment *> &dataSegments;
366};
367
368// Create the custom "name" section containing debug symbol names.
369class NameSection : public SyntheticSection {
370public:
371 NameSection(ArrayRef<OutputSegment *> segments)
372 : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "name"),
373 segments(segments) {}
374 bool isNeeded() const override {
375 if (ctx.arg.stripAll && !ctx.arg.keepSections.contains(key: name))
376 return false;
377 return numNames() > 0;
378 }
379 void writeBody() override;
380 unsigned numNames() const {
381 // We always write at least one name which is the name of the
382 // module itself.
383 return 1 + numNamedGlobals() + numNamedFunctions();
384 }
385 unsigned numNamedGlobals() const;
386 unsigned numNamedFunctions() const;
387 unsigned numNamedDataSegments() const;
388
389protected:
390 ArrayRef<OutputSegment *> segments;
391};
392
393class ProducersSection : public SyntheticSection {
394public:
395 ProducersSection()
396 : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "producers") {}
397 bool isNeeded() const override {
398 if (ctx.arg.stripAll && !ctx.arg.keepSections.contains(key: name))
399 return false;
400 return fieldCount() > 0;
401 }
402 void writeBody() override;
403 void addInfo(const llvm::wasm::WasmProducerInfo &info);
404
405protected:
406 int fieldCount() const {
407 return int(!languages.empty()) + int(!tools.empty()) + int(!sDKs.empty());
408 }
409 SmallVector<std::pair<std::string, std::string>, 8> languages;
410 SmallVector<std::pair<std::string, std::string>, 8> tools;
411 SmallVector<std::pair<std::string, std::string>, 8> sDKs;
412};
413
414class TargetFeaturesSection : public SyntheticSection {
415public:
416 TargetFeaturesSection()
417 : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "target_features") {}
418 bool isNeeded() const override {
419 if (ctx.arg.stripAll && !ctx.arg.keepSections.contains(key: name))
420 return false;
421 return features.size() > 0;
422 }
423 void writeBody() override;
424
425 llvm::SmallSet<std::string, 8> features;
426};
427
428class RelocSection : public SyntheticSection {
429public:
430 RelocSection(StringRef name, OutputSection *sec)
431 : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, std::string(name)),
432 sec(sec) {}
433 void writeBody() override;
434 bool isNeeded() const override { return sec->getNumRelocations() > 0; };
435
436protected:
437 OutputSection *sec;
438};
439
440class BuildIdSection : public SyntheticSection {
441public:
442 BuildIdSection();
443 void writeBody() override;
444 bool isNeeded() const override {
445 return ctx.arg.buildId != BuildIdKind::None;
446 }
447 void writeBuildId(llvm::ArrayRef<uint8_t> buf);
448 void writeTo(uint8_t *buf) override {
449 LLVM_DEBUG(llvm::dbgs()
450 << "BuildId writeto buf " << buf << " offset " << offset
451 << " headersize " << header.size() << '\n');
452 // The actual build ID is derived from a hash of all of the output
453 // sections, so it can't be calculated until they are written. Here
454 // we write the section leaving zeros in place of the hash.
455 SyntheticSection::writeTo(buf);
456 // Calculate and store the location where the hash will be written.
457 hashPlaceholderPtr = buf + offset + header.size() +
458 +sizeof(buildIdSectionName) /*name string*/ +
459 1 /* hash size */;
460 }
461
462 const uint32_t hashSize;
463
464private:
465 static constexpr char buildIdSectionName[] = "build_id";
466 uint8_t *hashPlaceholderPtr = nullptr;
467};
468
469// Linker generated output sections
470struct OutStruct {
471 DylinkSection *dylinkSec;
472 TypeSection *typeSec;
473 FunctionSection *functionSec;
474 ImportSection *importSec;
475 TableSection *tableSec;
476 MemorySection *memorySec;
477 GlobalSection *globalSec;
478 TagSection *tagSec;
479 ExportSection *exportSec;
480 StartSection *startSec;
481 ElemSection *elemSec;
482 DataCountSection *dataCountSec;
483 LinkingSection *linkingSec;
484 NameSection *nameSec;
485 ProducersSection *producersSec;
486 TargetFeaturesSection *targetFeaturesSec;
487 BuildIdSection *buildIdSec;
488};
489
490extern OutStruct out;
491
492} // namespace wasm
493} // namespace lld
494
495#endif
496