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     bodyOutputStream.flush();
  60     createHeader(body.size());
  61   }
  62
  63   raw_ostream &getStream() { return bodyOutputStream; }
  64
  65   std::string body;
  66
  67 protected:
  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
  75 class DylinkSection : public SyntheticSection {
  76 public:
  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
  85 class TypeSection : public SyntheticSection {
  86 public:
  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
  94 protected:
  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  */
 104 template <typename T> struct ImportKey {
 105 public:
 106   enum class State { Plain, Empty, Tombstone };
 107
 108 public:
 109   T type;
 110   std::optional<StringRef> importModule;
 111   std::optional<StringRef> importName;
 112   State state;
 113
 114 public:
 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
 123 template <typename T>
 124 inline 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`.
 133 namespace llvm {
 134 template <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
 159 namespace lld {
 160 namespace wasm {
 161
 162 class ImportSection : public SyntheticSection {
 163 public:
 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
 191 protected:
 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
 203 class FunctionSection : public SyntheticSection {
 204 public:
 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
 213 protected:
 214 };
 215
 216 class TableSection : public SyntheticSection {
 217 public:
 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
 228 class MemorySection : public SyntheticSection {
 229 public:
 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.)
 248 class TagSection : public SyntheticSection {
 249 public:
 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
 258 class GlobalSection : public SyntheticSection {
 259 public:
 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(internalGotSymbols,
 293                         [=](Symbol *sym) { return !sym->isTLS(); });
 294   }
 295   bool needsTLSRelocations() {
 296     return llvm::any_of(internalGotSymbols,
 297                         [=](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
 305 protected:
 306   bool isSealed = false;
 307 };
 308
 309 class ExportSection : public SyntheticSection {
 310 public:
 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
 319 class StartSection : public SyntheticSection {
 320 public:
 321   StartSection() : SyntheticSection(llvm::wasm::WASM_SEC_START) {}
 322   bool isNeeded() const override;
 323   void writeBody() override;
 324 };
 325
 326 class ElemSection : public SyntheticSection {
 327 public:
 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
 335 protected:
 336   std::vector<const FunctionSymbol *> indirectFunctions;
 337 };
 338
 339 class DataCountSection : public SyntheticSection {
 340 public:
 341   DataCountSection(ArrayRef<OutputSegment *> segments);
 342   bool isNeeded() const override;
 343   void writeBody() override;
 344
 345 protected:
 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.
 351 class LinkingSection : public SyntheticSection {
 352 public:
 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
 363 protected:
 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.
 371 class NameSection : public SyntheticSection {
 372 public:
 373   NameSection(ArrayRef<OutputSegment *> segments)
 374       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "name"),
 375         segments(segments) {}
 376   bool isNeeded() const override { return !config->stripAll && numNames() > 0; }
 377   void writeBody() override;
 378   unsigned numNames() const {
 379     // We always write at least one name which is the name of the
 380     // module itself.
 381     return 1 + numNamedGlobals() + numNamedFunctions();
 382   }
 383   unsigned numNamedGlobals() const;
 384   unsigned numNamedFunctions() const;
 385   unsigned numNamedDataSegments() const;
 386
 387 protected:
 388   ArrayRef<OutputSegment *> segments;
 389 };
 390
 391 class ProducersSection : public SyntheticSection {
 392 public:
 393   ProducersSection()
 394       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "producers") {}
 395   bool isNeeded() const override {
 396     return !config->stripAll && fieldCount() > 0;
 397   }
 398   void writeBody() override;
 399   void addInfo(const llvm::wasm::WasmProducerInfo &info);
 400
 401 protected:
 402   int fieldCount() const {
 403     return int(!languages.empty()) + int(!tools.empty()) + int(!sDKs.empty());
 404   }
 405   SmallVector<std::pair<std::string, std::string>, 8> languages;
 406   SmallVector<std::pair<std::string, std::string>, 8> tools;
 407   SmallVector<std::pair<std::string, std::string>, 8> sDKs;
 408 };
 409
 410 class TargetFeaturesSection : public SyntheticSection {
 411 public:
 412   TargetFeaturesSection()
 413       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, "target_features") {}
 414   bool isNeeded() const override {
 415     return !config->stripAll && features.size() > 0;
 416   }
 417   void writeBody() override;
 418
 419   llvm::SmallSet<std::string, 8> features;
 420 };
 421
 422 class RelocSection : public SyntheticSection {
 423 public:
 424   RelocSection(StringRef name, OutputSection *sec)
 425       : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, std::string(name)),
 426         sec(sec) {}
 427   void writeBody() override;
 428   bool isNeeded() const override { return sec->getNumRelocations() > 0; };
 429
 430 protected:
 431   OutputSection *sec;
 432 };
 433
 434 class BuildIdSection : public SyntheticSection {
 435 public:
 436   BuildIdSection();
 437   void writeBody() override;
 438   bool isNeeded() const override {
 439     return config->buildId != BuildIdKind::None;
 440   }
 441   void writeBuildId(llvm::ArrayRef<uint8_t> buf);
 442   void writeTo(uint8_t *buf) override {
 443     LLVM_DEBUG(llvm::dbgs()
 444                << "BuildId writeto buf " << buf << " offset " << offset
 445                << " headersize " << header.size() << '\n');
 446     // The actual build ID is derived from a hash of all of the output
 447     // sections, so it can't be calculated until they are written. Here
 448     // we write the section leaving zeros in place of the hash.
 449     SyntheticSection::writeTo(buf);
 450     // Calculate and store the location where the hash will be written.
 451     hashPlaceholderPtr = buf + offset + header.size() +
 452                          +sizeof(buildIdSectionName) /*name string*/ +
 453                          1 /* hash size */;
 454   }
 455
 456   const uint32_t hashSize;
 457
 458 private:
 459   static constexpr char buildIdSectionName[] = "build_id";
 460   uint8_t *hashPlaceholderPtr = nullptr;
 461 };
 462
 463 // Linker generated output sections
 464 struct OutStruct {
 465   DylinkSection *dylinkSec;
 466   TypeSection *typeSec;
 467   FunctionSection *functionSec;
 468   ImportSection *importSec;
 469   TableSection *tableSec;
 470   MemorySection *memorySec;
 471   GlobalSection *globalSec;
 472   TagSection *tagSec;
 473   ExportSection *exportSec;
 474   StartSection *startSec;
 475   ElemSection *elemSec;
 476   DataCountSection *dataCountSec;
 477   LinkingSection *linkingSec;
 478   NameSection *nameSec;
 479   ProducersSection *producersSec;
 480   TargetFeaturesSection *targetFeaturesSec;
 481   BuildIdSection *buildIdSec;
 482 };
 483
 484 extern OutStruct out;
 485
 486 } // namespace wasm
 487 } // namespace lld
 488
 489 #endif