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