lld/wasm/SyntheticSections.h

   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
  27 namespace lld::wasm {
  28
  29 // An init entry to be written to either the synthetic init func or the
  30 // linking metadata.
  31 struct WasmInitEntry {
  32   const FunctionSymbol *sym;
  33   uint32_t priority;
  34 };
  35
  36 class SyntheticSection : public OutputSection {
  37 public:
  38   SyntheticSection(uint32_t type, std::string name = "")
  39       : OutputSection(type, name), bodyOutputStream(body) {
  40     if (!name.empty())
  41       writeStr(bodyOutputStream, name, "section name");
  42   }
  43
  44   void writeTo(uint8_t *buf) override {
  45     assert(offset);
  46     log("writing " + toString(*this));
  47     memcpy(buf + offset, header.data(), header.size());
  48     memcpy(buf + offset + header.size(), body.data(), 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(body.size());
  60   }
  61
  62   raw_ostream &getStream() { return bodyOutputStream; }
  63
  64   std::string body;
  65
  66 protected:
  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
  74 class DylinkSection : public SyntheticSection {
  75 public:
  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
  84 class TypeSection : public SyntheticSection {
  85 public:
  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
  93 protected:
  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  */
 103 template <typename T> struct ImportKey {
 104 public:
 105   enum class State { Plain, Empty, Tombstone };
 106
 107 public:
 108   T type;
 109   std::optional<StringRef> importModule;
 110   std::optional<StringRef> importName;
 111   State state;
 112
 113 public:
 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
 122 template <typename T>
 123 inline 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 wasm::lld
 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`.
 132 namespace llvm {
 133 template <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
 158 namespace lld {
 159 namespace wasm {
 160
 161 class ImportSection : public SyntheticSection {
 162 public:
 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
 190 protected:
 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
 202 class FunctionSection : public SyntheticSection {
 203 public:
 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
 212 protected:
 213 };
 214
 215 class TableSection : public SyntheticSection {
 216 public:
 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
 227 class MemorySection : public SyntheticSection {
 228 public:
 229   MemorySection() : SyntheticSection(llvm::wasm::WASM_SEC_MEMORY) {}
 230
 231   bool isNeeded() const override { return !config->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.)
 247 class TagSection : public SyntheticSection {
 248 public:
 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
 257 class GlobalSection : public SyntheticSection {
 258 public:
 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 (config->extendedConst)
 290       return false;
 291     return llvm::any_of(internalGotSymbols,
 292                         [=](Symbol *sym) { return !sym->isTLS(); });
 293   }
 294   bool needsTLSRelocations() {
 295     return llvm::any_of(internalGotSymbols,
 296                         [=](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
 304 protected:
 305   bool isSealed = false;
 306 };
 307
 308 class ExportSection : public SyntheticSection {
 309 public:
 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
 318 class StartSection : public SyntheticSection {
 319 public:
 320   StartSection() : SyntheticSection(llvm::wasm::WASM_SEC_START) {}
 321   bool isNeeded() const override;
 322   void writeBody() override;
 323 };
 324
 325 class ElemSection : public SyntheticSection {
 326 public:
 327   ElemSection()
 328       : SyntheticSection(llvm::wasm::WASM_SEC_ELEM) {}
 329   bool isNeeded() const override { return indirectFunctions.size() > 0; };
 330   void writeBody() override;
 331   void addEntry(FunctionSymbol *sym);
 332   uint32_t numEntries() const { return indirectFunctions.size(); }
 333
 334 protected:
 335   std::vector<const FunctionSymbol *> indirectFunctions;
 336 };
 337
 338 class DataCountSection : public SyntheticSection {
 339 public:
 340   DataCountSection(ArrayRef<OutputSegment *> segments);
 341   bool isNeeded() const override;
 342   void writeBody() override;
 343
 344 protected:
 345   uint32_t numSegments;
 346 };
 347
 348 // Create the custom "linking" section containing linker metadata.
 349 // This is only created when relocatable output is requested.
 350 class LinkingSection : public SyntheticSection {
 351 public:
 352   LinkingSection(const std::vector<WasmInitEntry> &initFunctions,
 353                  const std::vector<OutputSegment *> &dataSegments)
 354       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "linking"),
 355         initFunctions(initFunctions), dataSegments(dataSegments) {}
 356   bool isNeeded() const override {
 357     return config->relocatable || config->emitRelocs;
 358   }
 359   void writeBody() override;
 360   void addToSymtab(Symbol *sym);
 361
 362 protected:
 363   std::vector<const Symbol *> symtabEntries;
 364   llvm::StringMap<uint32_t> sectionSymbolIndices;
 365   const std::vector<WasmInitEntry> &initFunctions;
 366   const std::vector<OutputSegment *> &dataSegments;
 367 };
 368
 369 // Create the custom "name" section containing debug symbol names.
 370 class NameSection : public SyntheticSection {
 371 public:
 372   NameSection(ArrayRef<OutputSegment *> segments)
 373       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "name"),
 374         segments(segments) {}
 375   bool isNeeded() const override {
 376     if (config->stripAll && !config->keepSections.count(name))
 377       return false;
 378     return numNames() > 0;
 379   }
 380   void writeBody() override;
 381   unsigned numNames() const {
 382     // We always write at least one name which is the name of the
 383     // module itself.
 384     return 1 + numNamedGlobals() + numNamedFunctions();
 385   }
 386   unsigned numNamedGlobals() const;
 387   unsigned numNamedFunctions() const;
 388   unsigned numNamedDataSegments() const;
 389
 390 protected:
 391   ArrayRef<OutputSegment *> segments;
 392 };
 393
 394 class ProducersSection : public SyntheticSection {
 395 public:
 396   ProducersSection()
 397       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "producers") {}
 398   bool isNeeded() const override {
 399     if (config->stripAll && !config->keepSections.count(name))
 400       return false;
 401     return fieldCount() > 0;
 402   }
 403   void writeBody() override;
 404   void addInfo(const llvm::wasm::WasmProducerInfo &info);
 405
 406 protected:
 407   int fieldCount() const {
 408     return int(!languages.empty()) + int(!tools.empty()) + int(!sDKs.empty());
 409   }
 410   SmallVector<std::pair<std::string, std::string>, 8> languages;
 411   SmallVector<std::pair<std::string, std::string>, 8> tools;
 412   SmallVector<std::pair<std::string, std::string>, 8> sDKs;
 413 };
 414
 415 class TargetFeaturesSection : public SyntheticSection {
 416 public:
 417   TargetFeaturesSection()
 418       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "target_features") {}
 419   bool isNeeded() const override {
 420     if (config->stripAll && !config->keepSections.count(name))
 421       return false;
 422     return features.size() > 0;
 423   }
 424   void writeBody() override;
 425
 426   llvm::SmallSet<std::string, 8> features;
 427 };
 428
 429 class RelocSection : public SyntheticSection {
 430 public:
 431   RelocSection(StringRef name, OutputSection *sec)
 432       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, std::string(name)),
 433         sec(sec) {}
 434   void writeBody() override;
 435   bool isNeeded() const override { return sec->getNumRelocations() > 0; };
 436
 437 protected:
 438   OutputSection *sec;
 439 };
 440
 441 class BuildIdSection : public SyntheticSection {
 442 public:
 443   BuildIdSection();
 444   void writeBody() override;
 445   bool isNeeded() const override {
 446     return config->buildId != BuildIdKind::None;
 447   }
 448   void writeBuildId(llvm::ArrayRef<uint8_t> buf);
 449   void writeTo(uint8_t *buf) override {
 450     LLVM_DEBUG(llvm::dbgs()
 451                << "BuildId writeto buf " << buf << " offset " << offset
 452                << " headersize " << header.size() << '\n');
 453     // The actual build ID is derived from a hash of all of the output
 454     // sections, so it can't be calculated until they are written. Here
 455     // we write the section leaving zeros in place of the hash.
 456     SyntheticSection::writeTo(buf);
 457     // Calculate and store the location where the hash will be written.
 458     hashPlaceholderPtr = buf + offset + header.size() +
 459                          +sizeof(buildIdSectionName) /*name string*/ +
 460                          1 /* hash size */;
 461   }
 462
 463   const uint32_t hashSize;
 464
 465 private:
 466   static constexpr char buildIdSectionName[] = "build_id";
 467   uint8_t *hashPlaceholderPtr = nullptr;
 468 };
 469
 470 // Linker generated output sections
 471 struct OutStruct {
 472   DylinkSection *dylinkSec;
 473   TypeSection *typeSec;
 474   FunctionSection *functionSec;
 475   ImportSection *importSec;
 476   TableSection *tableSec;
 477   MemorySection *memorySec;
 478   GlobalSection *globalSec;
 479   TagSection *tagSec;
 480   ExportSection *exportSec;
 481   StartSection *startSec;
 482   ElemSection *elemSec;
 483   DataCountSection *dataCountSec;
 484   LinkingSection *linkingSec;
 485   NameSection *nameSec;
 486   ProducersSection *producersSec;
 487   TargetFeaturesSection *targetFeaturesSec;
 488   BuildIdSection *buildIdSec;
 489 };
 490
 491 extern OutStruct out;
 492
 493 } // namespace wasm
 494 } // namespace lld
 495
 496 #endif