src/binaryen/src/wasm-linker.h

   1 /*
   2  * Copyright 2016 WebAssembly Community Group participants
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 // (very) basic linking functionality for s2wasm.
  18 // Performs some of the tasks that will eventually be done by a real linker.
  19 // Currently can allocate static variables and the stack, lay out memory
  20 // and initial segment contents, and process relocations. (In particular, there
  21 // is no merging of multiple modules). Currently this is only inteded to turn
  22 // a .s file produced by LLVM into a usable wast file.
  23
  24 #ifndef wasm_wasm_linker_h
  25 #define wasm_wasm_linker_h
  26
  27 #include "support/archive.h"
  28 #include "support/name.h"
  29 #include "support/utilities.h"
  30 #include "wasm.h"
  31
  32 namespace wasm {
  33
  34 class S2WasmBuilder;
  35
  36 inline void exportFunction(Module& wasm, Name name, bool must_export) {
  37   if (!wasm.getFunctionOrNull(name)) {
  38     assert(!must_export);
  39     return;
  40   }
  41   if (wasm.getExportOrNull(name)) return; // Already exported
  42   auto exp = new Export;
  43   exp->name = exp->value = name;
  44   exp->kind = ExternalKind::Function;
  45   wasm.addExport(exp);
  46 }
  47
  48 // An "object file" for linking. Contains a wasm module, plus the associated
  49 // information needed for linking/layout.
  50 class LinkerObject {
  51  public:
  52   struct Relocation {
  53     enum Kind { kData, kFunction };
  54     Kind kind; // Whether the symbol refers to data or a function.
  55     // Instead of section offsets as relocation targets, for now this is just
  56     // a pointer to the memory to rewrite.
  57     uint32_t* data;
  58     Name symbol; // Like the symbol index in ELF r_info field
  59     int addend; // Like the ELF r_addend field
  60     Relocation(Kind kind, uint32_t* data, Name symbol, int addend) :
  61         kind(kind), data(data), symbol(symbol), addend(addend) {}
  62   };
  63   struct SymbolAlias {
  64     Name symbol;
  65     Relocation::Kind kind;
  66     Offset offset;
  67     SymbolAlias(Name symbol, Relocation::Kind kind, Offset offset) :
  68       symbol(symbol), kind(kind), offset(offset) {}
  69   };
  70   // Information about symbols
  71   struct SymbolInfo {
  72     std::unordered_set<cashew::IString> implementedFunctions;
  73     std::unordered_set<cashew::IString> undefinedFunctions;
  74     std::unordered_set<cashew::IString> importedObjects;
  75     // TODO: it's not clear that this really belongs here.
  76     std::unordered_map<cashew::IString, SymbolAlias> aliasedSymbols;
  77
  78     // For now, do not support weak symbols or anything special. Just directly
  79     // merge the functions together, and remove any newly-defined functions
  80     // from undefinedFunction
  81     void merge(SymbolInfo& other) {
  82       for (const auto& func : other.implementedFunctions) {
  83         undefinedFunctions.erase(func);
  84       }
  85       implementedFunctions.insert(other.implementedFunctions.begin(),
  86                                   other.implementedFunctions.end());
  87       importedObjects.insert(other.importedObjects.begin(),
  88                              other.importedObjects.end());
  89       aliasedSymbols.insert(other.aliasedSymbols.begin(),
  90                             other.aliasedSymbols.end());
  91     }
  92   };
  93
  94   LinkerObject() {}
  95
  96   // Allocate a static object
  97   void addStatic(Address allocSize, Address alignment, Name name) {
  98     staticObjects.emplace_back(allocSize, alignment, name);
  99   }
 100
 101   void addGlobal(Name name) {
 102     globls.push_back(name);
 103   }
 104
 105   // This takes ownership of the added Relocation
 106   void addRelocation(Relocation* relocation) {
 107     relocations.emplace_back(relocation);
 108   }
 109
 110   bool isFunctionImplemented(Name name) {
 111     return symbolInfo.implementedFunctions.count(name) != 0;
 112   }
 113
 114   // An object is considered implemented if it is not imported
 115   bool isObjectImplemented(Name name) {
 116     return symbolInfo.importedObjects.count(name) == 0;
 117   }
 118
 119   // If name is an alias, return what it points to. Otherwise return name.
 120   Name resolveAlias(Name name, Relocation::Kind kind) {
 121     auto aliased = symbolInfo.aliasedSymbols.find(name);
 122     if (aliased != symbolInfo.aliasedSymbols.end() && aliased->second.kind == kind) return aliased->second.symbol;
 123     return name;
 124   }
 125
 126   SymbolAlias *getAlias(Name name, Relocation::Kind kind) {
 127     auto aliased = symbolInfo.aliasedSymbols.find(name);
 128     if (aliased != symbolInfo.aliasedSymbols.end() && aliased->second.kind == kind) return &aliased->second;
 129     return nullptr;
 130   }
 131
 132   // Add an initializer segment for the named static variable.
 133   void addSegment(Name name, const char* data, Address size) {
 134     segments[name] = wasm.memory.segments.size();
 135     wasm.memory.segments.emplace_back(wasm.allocator.alloc<Const>()->set(Literal(uint32_t(0))), data, size);
 136   }
 137
 138   void addSegment(Name name, std::vector<char>& data) {
 139     segments[name] = wasm.memory.segments.size();
 140     wasm.memory.segments.emplace_back(wasm.allocator.alloc<Const>()->set(Literal(uint32_t(0))), data);
 141   }
 142
 143   void addInitializerFunction(Name name) {
 144     initializerFunctions.emplace_back(name);
 145     assert(symbolInfo.implementedFunctions.count(name));
 146   }
 147
 148   void addUndefinedFunctionCall(Call* call) {
 149     symbolInfo.undefinedFunctions.insert(call->target);
 150     undefinedFunctionCalls[call->target].push_back(call);
 151   }
 152
 153   void addExternType(Name name, FunctionType* ty) {
 154     externTypesMap[name] = ty;
 155   }
 156   FunctionType* getExternType(Name name) {
 157     auto f = externTypesMap.find(name);
 158     if (f == externTypesMap.end()) return nullptr;
 159     return f->second;
 160   }
 161
 162   void addIndirectIndex(Name name, Address index) {
 163     assert(!indirectIndexes.count(name));
 164     indirectIndexes[name] = index;
 165   }
 166
 167   bool isEmpty() {
 168     return wasm.functions.empty();
 169   }
 170
 171   std::vector<Name> const& getInitializerFunctions() const {
 172     return initializerFunctions;
 173   }
 174
 175   friend class Linker;
 176
 177   Module wasm;
 178
 179  private:
 180   struct StaticObject {
 181     Address allocSize;
 182     Address alignment;
 183     Name name;
 184     StaticObject(Address allocSize, Address alignment, Name name) :
 185         allocSize(allocSize), alignment(alignment), name(name) {}
 186   };
 187
 188   std::vector<Name> globls;
 189
 190   std::vector<StaticObject> staticObjects;
 191   std::vector<std::unique_ptr<Relocation>> relocations;
 192
 193   SymbolInfo symbolInfo;
 194
 195   using CallList = std::vector<Call*>;
 196   std::map<Name, CallList> undefinedFunctionCalls;
 197
 198   // Types of functions which are declared but not defined.
 199   std::unordered_map<cashew::IString, FunctionType*> externTypesMap;
 200
 201   std::map<Name, Address> segments; // name => segment index (in wasm module)
 202
 203   // preassigned indexes for functions called indirectly
 204   std::map<Name, Address> indirectIndexes;
 205
 206   std::vector<Name> initializerFunctions;
 207
 208   LinkerObject(const LinkerObject&) = delete;
 209   LinkerObject& operator=(const LinkerObject&) = delete;
 210
 211 };
 212
 213 // Class which performs some linker-like functionality; namely taking an object
 214 // file with relocations, laying out the linear memory and segments, and
 215 // applying the relocations, resulting in an executable wasm module.
 216 class Linker {
 217  public:
 218   Linker(Address globalBase, Address stackAllocation, Address userInitialMemory,
 219          Address userMaxMemory, bool importMemory, bool ignoreUnknownSymbols,
 220          Name startFunction, bool debug)
 221       : ignoreUnknownSymbols(ignoreUnknownSymbols),
 222         startFunction(startFunction),
 223         globalBase(globalBase),
 224         nextStatic(globalBase),
 225         userInitialMemory(userInitialMemory),
 226         userMaxMemory(userMaxMemory),
 227         importMemory(importMemory),
 228         stackAllocation(stackAllocation),
 229         debug(debug) {
 230     if (userMaxMemory && userMaxMemory < userInitialMemory) {
 231       Fatal() << "Specified max memory " << userMaxMemory <<
 232           " is < specified initial memory " << userInitialMemory;
 233     }
 234     if (roundUpToPageSize(userMaxMemory) != userMaxMemory) {
 235       Fatal() << "Specified max memory " << userMaxMemory <<
 236           " is not a multiple of 64k";
 237     }
 238     if (roundUpToPageSize(userInitialMemory) != userInitialMemory) {
 239       Fatal() << "Specified initial memory " << userInitialMemory <<
 240           " is not a multiple of 64k";
 241     }
 242
 243     // Don't allow anything to be allocated at address 0
 244     if (globalBase == 0) nextStatic = 1;
 245
 246     // Place the stack pointer at the bottom of the linear memory, to keep its
 247     // address small (and thus with a small encoding).
 248     placeStackPointer(stackAllocation);
 249     // Allocate __dso_handle. For asm.js, emscripten provides this in JS, but
 250     // wasm modules can't import data objects. Its value is 0 for the main
 251     // executable, which is all we have with static linking. In the future this
 252     // can go in a crtbegin or similar file.
 253     out.addStatic(4, 4, "__dso_handle");
 254   }
 255
 256   // Return a reference to the LinkerObject for the main executable. If empty,
 257   // it can be passed to an S2WasmBuilder and constructed.
 258   LinkerObject& getOutput() { return out; }
 259
 260   // Allocate the user stack, set up the initial memory size of the module, lay
 261   // out the linear memory, process the relocations, and set up the indirect
 262   // function table.
 263   void layout();
 264
 265   // Add an object to the link by constructing it in-place with a builder.
 266   // Returns false if an error occurred.
 267   bool linkObject(S2WasmBuilder& builder);
 268
 269   // Add an archive to the link. Any objects in the archive that satisfy a
 270   // currently-undefined reference will be added to the link.
 271   // Returns false if an error occurred.
 272   bool linkArchive(Archive& archive);
 273
 274   // Returns the address of the stack pointer.
 275   Address getStackPointerAddress() const;
 276
 277   // Returns the total size of all static allocations.
 278   Address getStaticBump() const;
 279
 280  private:
 281   // Allocate a static variable and return its address in linear memory
 282   Address allocateStatic(Address allocSize, Address alignment, Name name) {
 283     Address address = alignAddr(nextStatic, alignment);
 284     staticAddresses[name] = address;
 285     nextStatic = address + allocSize;
 286     return address;
 287   }
 288
 289   // Allocate space for a stack pointer and (if stackAllocation > 0) set up a
 290   // relocation for it to point to the top of the stack.
 291   void placeStackPointer(Address stackAllocation);
 292
 293   void ensureFunctionImport(Name target, std::string signature);
 294   void ensureObjectImport(Name target);
 295
 296   // Makes sure the table has a single segment, with offset 0,
 297   // to which we can add content.
 298   void ensureTableSegment();
 299
 300   std::vector<Name>& getTableDataRef();
 301   std::vector<Name> getTableData();
 302
 303   // Retrieves (and assigns) an entry index in the indirect function table for
 304   // a given function.
 305   Index getFunctionIndex(Name name);
 306
 307   // Adds a dummy function in the indirect table at slot 0 to prevent NULL
 308   // pointer miscomparisons.
 309   void makeDummyFunction();
 310
 311   static Address roundUpToPageSize(Address size) {
 312     return (size + Memory::kPageSize - 1) & Memory::kPageMask;
 313   }
 314
 315   Function* getImportThunk(Name name, const FunctionType* t);
 316
 317   // The output module (linked executable)
 318   LinkerObject out;
 319
 320   bool ignoreUnknownSymbols;
 321   Name startFunction;
 322
 323   // where globals can start to be statically allocated, i.e., the data segment
 324   Address globalBase;
 325   Address nextStatic; // location of next static allocation
 326   Address userInitialMemory; // Initial memory size (in bytes) specified by the user.
 327   Address userMaxMemory; // Max memory size (in bytes) specified by the user.
 328   //(after linking, this is rounded and set on the wasm object in pages)
 329   bool importMemory;  // Whether the memory should be imported instead of
 330                       // defined.
 331   Address stackAllocation;
 332   bool debug;
 333
 334   std::unordered_map<cashew::IString, int32_t> staticAddresses; // name => address
 335   std::unordered_map<Address, Address> segmentsByAddress; // address => segment index
 336   std::unordered_map<cashew::IString, Address> functionIndexes;
 337   std::map<Address, cashew::IString> functionNames;
 338 };
 339
 340 }
 341
 342 #endif // wasm_wasm_linker_h