lld/wasm/InputChunks.h

   1 //===- InputChunks.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 // An InputChunks represents an indivisible opaque region of a input wasm file.
  10 // i.e. a single wasm data segment or a single wasm function.
  11 //
  12 // They are written directly to the mmap'd output file after which relocations
  13 // are applied.  Because each Chunk is independent they can be written in
  14 // parallel.
  15 //
  16 // Chunks are also unit on which garbage collection (--gc-sections) operates.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef LLD_WASM_INPUT_CHUNKS_H
  21 #define LLD_WASM_INPUT_CHUNKS_H
  22
  23 #include "Config.h"
  24 #include "InputFiles.h"
  25 #include "lld/Common/ErrorHandler.h"
  26 #include "lld/Common/LLVM.h"
  27 #include "llvm/ADT/CachedHashString.h"
  28 #include "llvm/MC/StringTableBuilder.h"
  29 #include "llvm/Object/Wasm.h"
  30
  31 namespace lld {
  32 namespace wasm {
  33
  34 class ObjFile;
  35 class OutputSegment;
  36 class OutputSection;
  37
  38 class InputChunk {
  39 public:
  40   enum Kind {
  41     DataSegment,
  42     Merge,
  43     MergedChunk,
  44     Function,
  45     SyntheticFunction,
  46     Section,
  47   };
  48
  49   StringRef name;
  50   StringRef debugName;
  51
  52   StringRef getName() const { return name; }
  53   StringRef getDebugName() const { return debugName; }
  54   Kind kind() const { return (Kind)sectionKind; }
  55
  56   uint32_t getSize() const;
  57   uint32_t getInputSize() const;
  58
  59   void writeTo(uint8_t *buf) const;
  60   void relocate(uint8_t *buf) const;
  61
  62   ArrayRef<WasmRelocation> getRelocations() const { return relocations; }
  63   void setRelocations(ArrayRef<WasmRelocation> rs) { relocations = rs; }
  64
  65   // Translate an offset into the input chunk to an offset in the output
  66   // section.
  67   uint64_t getOffset(uint64_t offset) const;
  68   // Translate an offset into the input chunk into an offset into the output
  69   // chunk.  For data segments (InputSegment) this will return and offset into
  70   // the output segment.  For MergeInputChunk, this will return an offset into
  71   // the parent merged chunk.  For other chunk types this is no-op and we just
  72   // return unmodified offset.
  73   uint64_t getChunkOffset(uint64_t offset) const;
  74   uint64_t getVA(uint64_t offset = 0) const;
  75
  76   uint32_t getComdat() const { return comdat; }
  77   StringRef getComdatName() const;
  78   uint32_t getInputSectionOffset() const { return inputSectionOffset; }
  79
  80   size_t getNumRelocations() const { return relocations.size(); }
  81   void writeRelocations(llvm::raw_ostream &os) const;
  82   void generateRelocationCode(raw_ostream &os) const;
  83
  84   bool isTLS() const {
  85     // Older object files don't include WASM_SEG_FLAG_TLS and instead
  86     // relied on the naming convention.
  87     return flags & llvm::wasm::WASM_SEG_FLAG_TLS || name.startswith(".tdata") ||
  88            name.startswith(".tbss");
  89   }
  90
  91   ObjFile *file;
  92   OutputSection *outputSec = nullptr;
  93   uint32_t comdat = UINT32_MAX;
  94   uint32_t inputSectionOffset = 0;
  95   uint32_t alignment;
  96   uint32_t flags;
  97
  98   // Only applies to data segments.
  99   uint32_t outputSegmentOffset = 0;
 100   const OutputSegment *outputSeg = nullptr;
 101
 102   // After assignAddresses is called, this represents the offset from
 103   // the beginning of the output section this chunk was assigned to.
 104   int32_t outSecOff = 0;
 105
 106   uint8_t sectionKind : 3;
 107
 108   // Signals that the section is part of the output.  The garbage collector,
 109   // and COMDAT handling can set a sections' Live bit.
 110   // If GC is disabled, all sections start out as live by default.
 111   unsigned live : 1;
 112
 113   // Signals the chunk was discarded by COMDAT handling.
 114   unsigned discarded : 1;
 115
 116 protected:
 117   InputChunk(ObjFile *f, Kind k, StringRef name, uint32_t alignment = 0,
 118              uint32_t flags = 0)
 119       : name(name), file(f), alignment(alignment), flags(flags), sectionKind(k),
 120         live(!config->gcSections), discarded(false) {}
 121   ArrayRef<uint8_t> data() const { return rawData; }
 122   uint64_t getTombstone() const;
 123
 124   ArrayRef<WasmRelocation> relocations;
 125   ArrayRef<uint8_t> rawData;
 126 };
 127
 128 // Represents a WebAssembly data segment which can be included as part of
 129 // an output data segments.  Note that in WebAssembly, unlike ELF and other
 130 // formats, used the term "data segment" to refer to the continuous regions of
 131 // memory that make on the data section. See:
 132 // https://webassembly.github.io/spec/syntax/modules.html#syntax-data
 133 //
 134 // For example, by default, clang will produce a separate data section for
 135 // each global variable.
 136 class InputSegment : public InputChunk {
 137 public:
 138   InputSegment(const WasmSegment &seg, ObjFile *f)
 139       : InputChunk(f, InputChunk::DataSegment, seg.Data.Name,
 140                    seg.Data.Alignment, seg.Data.LinkingFlags),
 141         segment(seg) {
 142     rawData = segment.Data.Content;
 143     comdat = segment.Data.Comdat;
 144     inputSectionOffset = segment.SectionOffset;
 145   }
 146
 147   static bool classof(const InputChunk *c) { return c->kind() == DataSegment; }
 148
 149 protected:
 150   const WasmSegment &segment;
 151 };
 152
 153 class SyntheticMergedChunk;
 154
 155 // Merge segment handling copied from lld/ELF/InputSection.h.  Keep in sync
 156 // where possible.
 157
 158 // SectionPiece represents a piece of splittable segment contents.
 159 // We allocate a lot of these and binary search on them. This means that they
 160 // have to be as compact as possible, which is why we don't store the size (can
 161 // be found by looking at the next one).
 162 struct SectionPiece {
 163   SectionPiece(size_t off, uint32_t hash, bool live)
 164       : inputOff(off), live(live || !config->gcSections), hash(hash >> 1) {}
 165
 166   uint32_t inputOff;
 167   uint32_t live : 1;
 168   uint32_t hash : 31;
 169   uint64_t outputOff = 0;
 170 };
 171
 172 static_assert(sizeof(SectionPiece) == 16, "SectionPiece is too big");
 173
 174 // This corresponds segments marked as WASM_SEG_FLAG_STRINGS.
 175 class MergeInputChunk : public InputChunk {
 176 public:
 177   MergeInputChunk(const WasmSegment &seg, ObjFile *f)
 178       : InputChunk(f, Merge, seg.Data.Name, seg.Data.Alignment,
 179                    seg.Data.LinkingFlags) {
 180     rawData = seg.Data.Content;
 181     comdat = seg.Data.Comdat;
 182     inputSectionOffset = seg.SectionOffset;
 183   }
 184
 185   MergeInputChunk(const WasmSection &s, ObjFile *f)
 186       : InputChunk(f, Merge, s.Name, 0, llvm::wasm::WASM_SEG_FLAG_STRINGS) {
 187     assert(s.Type == llvm::wasm::WASM_SEC_CUSTOM);
 188     comdat = s.Comdat;
 189     rawData = s.Content;
 190   }
 191
 192   static bool classof(const InputChunk *s) { return s->kind() == Merge; }
 193   void splitIntoPieces();
 194
 195   // Translate an offset in the input section to an offset in the parent
 196   // MergeSyntheticSection.
 197   uint64_t getParentOffset(uint64_t offset) const;
 198
 199   // Splittable sections are handled as a sequence of data
 200   // rather than a single large blob of data.
 201   std::vector<SectionPiece> pieces;
 202
 203   // Returns I'th piece's data. This function is very hot when
 204   // string merging is enabled, so we want to inline.
 205   LLVM_ATTRIBUTE_ALWAYS_INLINE
 206   llvm::CachedHashStringRef getData(size_t i) const {
 207     size_t begin = pieces[i].inputOff;
 208     size_t end =
 209         (pieces.size() - 1 == i) ? data().size() : pieces[i + 1].inputOff;
 210     return {toStringRef(data().slice(begin, end - begin)), pieces[i].hash};
 211   }
 212
 213   // Returns the SectionPiece at a given input section offset.
 214   SectionPiece *getSectionPiece(uint64_t offset);
 215   const SectionPiece *getSectionPiece(uint64_t offset) const {
 216     return const_cast<MergeInputChunk *>(this)->getSectionPiece(offset);
 217   }
 218
 219   SyntheticMergedChunk *parent = nullptr;
 220
 221 private:
 222   void splitStrings(ArrayRef<uint8_t> a);
 223 };
 224
 225 // SyntheticMergedChunk is a class that allows us to put mergeable
 226 // sections with different attributes in a single output sections. To do that we
 227 // put them into SyntheticMergedChunk synthetic input sections which are
 228 // attached to regular output sections.
 229 class SyntheticMergedChunk : public InputChunk {
 230 public:
 231   SyntheticMergedChunk(StringRef name, uint32_t alignment, uint32_t flags)
 232       : InputChunk(nullptr, InputChunk::MergedChunk, name, alignment, flags),
 233         builder(llvm::StringTableBuilder::RAW, 1ULL << alignment) {}
 234
 235   static bool classof(const InputChunk *c) {
 236     return c->kind() == InputChunk::MergedChunk;
 237   }
 238
 239   void addMergeChunk(MergeInputChunk *ms) {
 240     comdat = ms->getComdat();
 241     ms->parent = this;
 242     chunks.push_back(ms);
 243   }
 244
 245   void finalizeContents();
 246
 247   llvm::StringTableBuilder builder;
 248
 249 protected:
 250   std::vector<MergeInputChunk *> chunks;
 251 };
 252
 253 // Represents a single wasm function within and input file.  These are
 254 // combined to create the final output CODE section.
 255 class InputFunction : public InputChunk {
 256 public:
 257   InputFunction(const WasmSignature &s, const WasmFunction *func, ObjFile *f)
 258       : InputChunk(f, InputChunk::Function, func->SymbolName), signature(s),
 259         function(func), exportName(func && func->ExportName.hasValue()
 260                                        ? (*func->ExportName).str()
 261                                        : llvm::Optional<std::string>()) {
 262     inputSectionOffset = function->CodeSectionOffset;
 263     rawData =
 264         file->codeSection->Content.slice(inputSectionOffset, function->Size);
 265     debugName = function->DebugName;
 266     comdat = function->Comdat;
 267   }
 268
 269   InputFunction(StringRef name, const WasmSignature &s)
 270       : InputChunk(nullptr, InputChunk::Function, name), signature(s) {}
 271
 272   static bool classof(const InputChunk *c) {
 273     return c->kind() == InputChunk::Function ||
 274            c->kind() == InputChunk::SyntheticFunction;
 275   }
 276
 277   llvm::Optional<StringRef> getExportName() const {
 278     return exportName.hasValue() ? llvm::Optional<StringRef>(*exportName)
 279                                  : llvm::Optional<StringRef>();
 280   }
 281   void setExportName(std::string exportName) { this->exportName = exportName; }
 282   uint32_t getFunctionInputOffset() const { return getInputSectionOffset(); }
 283   uint32_t getFunctionCodeOffset() const { return function->CodeOffset; }
 284   uint32_t getFunctionIndex() const { return functionIndex.getValue(); }
 285   bool hasFunctionIndex() const { return functionIndex.hasValue(); }
 286   void setFunctionIndex(uint32_t index);
 287   uint32_t getTableIndex() const { return tableIndex.getValue(); }
 288   bool hasTableIndex() const { return tableIndex.hasValue(); }
 289   void setTableIndex(uint32_t index);
 290   void writeCompressed(uint8_t *buf) const;
 291
 292   // The size of a given input function can depend on the values of the
 293   // LEB relocations within it.  This finalizeContents method is called after
 294   // all the symbol values have be calculated but before getSize() is ever
 295   // called.
 296   void calculateSize();
 297
 298   const WasmSignature &signature;
 299
 300   uint32_t getCompressedSize() const {
 301     assert(compressedSize);
 302     return compressedSize;
 303   }
 304
 305   const WasmFunction *function;
 306
 307 protected:
 308   llvm::Optional<std::string> exportName;
 309   llvm::Optional<uint32_t> functionIndex;
 310   llvm::Optional<uint32_t> tableIndex;
 311   uint32_t compressedFuncSize = 0;
 312   uint32_t compressedSize = 0;
 313 };
 314
 315 class SyntheticFunction : public InputFunction {
 316 public:
 317   SyntheticFunction(const WasmSignature &s, StringRef name,
 318                     StringRef debugName = {})
 319       : InputFunction(name, s) {
 320     sectionKind = InputChunk::SyntheticFunction;
 321     this->debugName = debugName;
 322   }
 323
 324   static bool classof(const InputChunk *c) {
 325     return c->kind() == InputChunk::SyntheticFunction;
 326   }
 327
 328   void setBody(ArrayRef<uint8_t> body) { rawData = body; }
 329 };
 330
 331 // Represents a single Wasm Section within an input file.
 332 class InputSection : public InputChunk {
 333 public:
 334   InputSection(const WasmSection &s, ObjFile *f)
 335       : InputChunk(f, InputChunk::Section, s.Name),
 336         tombstoneValue(getTombstoneForSection(s.Name)), section(s) {
 337     assert(section.Type == llvm::wasm::WASM_SEC_CUSTOM);
 338     comdat = section.Comdat;
 339     rawData = section.Content;
 340   }
 341
 342   static bool classof(const InputChunk *c) {
 343     return c->kind() == InputChunk::Section;
 344   }
 345
 346   const uint64_t tombstoneValue;
 347
 348 protected:
 349   static uint64_t getTombstoneForSection(StringRef name);
 350   const WasmSection &section;
 351 };
 352
 353 } // namespace wasm
 354
 355 std::string toString(const wasm::InputChunk *);
 356 StringRef relocTypeToString(uint8_t relocType);
 357
 358 } // namespace lld
 359
 360 #endif // LLD_WASM_INPUT_CHUNKS_H