wasm/InputChunks.cpp

   1 //===- InputChunks.cpp ----------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "InputChunks.h"
  11 #include "Config.h"
  12 #include "OutputSegment.h"
  13 #include "WriterUtils.h"
  14 #include "lld/Common/ErrorHandler.h"
  15 #include "lld/Common/LLVM.h"
  16 #include "llvm/Support/LEB128.h"
  17
  18 #define DEBUG_TYPE "lld"
  19
  20 using namespace llvm;
  21 using namespace llvm::wasm;
  22 using namespace llvm::support::endian;
  23 using namespace lld;
  24 using namespace lld::wasm;
  25
  26 static StringRef ReloctTypeToString(uint8_t RelocType) {
  27   switch (RelocType) {
  28 #define WASM_RELOC(NAME, REL) case REL: return #NAME;
  29 #include "llvm/BinaryFormat/WasmRelocs.def"
  30 #undef WASM_RELOC
  31   }
  32   llvm_unreachable("unknown reloc type");
  33 }
  34
  35 std::string lld::toString(const InputChunk *C) {
  36   return (toString(C->File) + ":(" + C->getName() + ")").str();
  37 }
  38
  39 StringRef InputChunk::getComdatName() const {
  40   uint32_t Index = getComdat();
  41   if (Index == UINT32_MAX)
  42     return StringRef();
  43   return File->getWasmObj()->linkingData().Comdats[Index];
  44 }
  45
  46 void InputChunk::copyRelocations(const WasmSection &Section) {
  47   if (Section.Relocations.empty())
  48     return;
  49   size_t Start = getInputSectionOffset();
  50   size_t Size = getInputSize();
  51   for (const WasmRelocation &R : Section.Relocations)
  52     if (R.Offset >= Start && R.Offset < Start + Size)
  53       Relocations.push_back(R);
  54 }
  55
  56 void InputChunk::verifyRelocTargets() const {
  57   for (const WasmRelocation &Rel : Relocations) {
  58     uint32_t ExistingValue;
  59     unsigned BytesRead = 0;
  60     uint32_t Offset = Rel.Offset - getInputSectionOffset();
  61     const uint8_t *Loc = data().data() + Offset;
  62     switch (Rel.Type) {
  63     case R_WEBASSEMBLY_TYPE_INDEX_LEB:
  64     case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
  65     case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
  66     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
  67       ExistingValue = decodeULEB128(Loc, &BytesRead);
  68       break;
  69     case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
  70     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
  71       ExistingValue = static_cast<uint32_t>(decodeSLEB128(Loc, &BytesRead));
  72       break;
  73     case R_WEBASSEMBLY_TABLE_INDEX_I32:
  74     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
  75     case R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
  76     case R_WEBASSEMBLY_SECTION_OFFSET_I32:
  77       ExistingValue = static_cast<uint32_t>(read32le(Loc));
  78       break;
  79     default:
  80       llvm_unreachable("unknown relocation type");
  81     }
  82
  83     if (BytesRead && BytesRead != 5)
  84       warn("expected LEB at relocation site be 5-byte padded");
  85     uint32_t ExpectedValue = File->calcExpectedValue(Rel);
  86     if (ExpectedValue != ExistingValue)
  87       warn("unexpected existing value for " + ReloctTypeToString(Rel.Type) +
  88            ": existing=" + Twine(ExistingValue) +
  89            " expected=" + Twine(ExpectedValue));
  90   }
  91 }
  92
  93 // Copy this input chunk to an mmap'ed output file and apply relocations.
  94 void InputChunk::writeTo(uint8_t *Buf) const {
  95   // Copy contents
  96   memcpy(Buf + OutputOffset, data().data(), data().size());
  97
  98   // Apply relocations
  99   if (Relocations.empty())
 100     return;
 101
 102 #ifndef NDEBUG
 103   verifyRelocTargets();
 104 #endif
 105
 106   LLVM_DEBUG(dbgs() << "applying relocations: " << getName()
 107                     << " count=" << Relocations.size() << "\n");
 108   int32_t Off = OutputOffset - getInputSectionOffset();
 109
 110   for (const WasmRelocation &Rel : Relocations) {
 111     uint8_t *Loc = Buf + Rel.Offset + Off;
 112     uint32_t Value = File->calcNewValue(Rel);
 113     LLVM_DEBUG(dbgs() << "apply reloc: type=" << ReloctTypeToString(Rel.Type)
 114                       << " addend=" << Rel.Addend << " index=" << Rel.Index
 115                       << " value=" << Value << " offset=" << Rel.Offset
 116                       << "\n");
 117
 118     switch (Rel.Type) {
 119     case R_WEBASSEMBLY_TYPE_INDEX_LEB:
 120     case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
 121     case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
 122     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
 123       encodeULEB128(Value, Loc, 5);
 124       break;
 125     case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
 126     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
 127       encodeSLEB128(static_cast<int32_t>(Value), Loc, 5);
 128       break;
 129     case R_WEBASSEMBLY_TABLE_INDEX_I32:
 130     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
 131     case R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
 132     case R_WEBASSEMBLY_SECTION_OFFSET_I32:
 133       write32le(Loc, Value);
 134       break;
 135     default:
 136       llvm_unreachable("unknown relocation type");
 137     }
 138   }
 139 }
 140
 141 // Copy relocation entries to a given output stream.
 142 // This function is used only when a user passes "-r". For a regular link,
 143 // we consume relocations instead of copying them to an output file.
 144 void InputChunk::writeRelocations(raw_ostream &OS) const {
 145   if (Relocations.empty())
 146     return;
 147
 148   int32_t Off = OutputOffset - getInputSectionOffset();
 149   LLVM_DEBUG(dbgs() << "writeRelocations: " << File->getName()
 150                     << " offset=" << Twine(Off) << "\n");
 151
 152   for (const WasmRelocation &Rel : Relocations) {
 153     writeUleb128(OS, Rel.Type, "reloc type");
 154     writeUleb128(OS, Rel.Offset + Off, "reloc offset");
 155     writeUleb128(OS, File->calcNewIndex(Rel), "reloc index");
 156
 157     switch (Rel.Type) {
 158     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
 159     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
 160     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
 161     case R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
 162     case R_WEBASSEMBLY_SECTION_OFFSET_I32:
 163       writeSleb128(OS, File->calcNewAddend(Rel), "reloc addend");
 164       break;
 165     }
 166   }
 167 }
 168
 169 void InputFunction::setFunctionIndex(uint32_t Index) {
 170   LLVM_DEBUG(dbgs() << "InputFunction::setFunctionIndex: " << getName()
 171                     << " -> " << Index << "\n");
 172   assert(!hasFunctionIndex());
 173   FunctionIndex = Index;
 174 }
 175
 176 void InputFunction::setTableIndex(uint32_t Index) {
 177   LLVM_DEBUG(dbgs() << "InputFunction::setTableIndex: " << getName() << " -> "
 178                     << Index << "\n");
 179   assert(!hasTableIndex());
 180   TableIndex = Index;
 181 }
 182
 183 // Write a relocation value without padding and return the number of bytes
 184 // witten.
 185 static unsigned writeCompressedReloc(uint8_t *Buf, const WasmRelocation &Rel,
 186                                      uint32_t Value) {
 187   switch (Rel.Type) {
 188   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
 189   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
 190   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
 191   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
 192     return encodeULEB128(Value, Buf);
 193   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
 194   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
 195     return encodeSLEB128(static_cast<int32_t>(Value), Buf);
 196   default:
 197     llvm_unreachable("unexpected relocation type");
 198   }
 199 }
 200
 201 static unsigned getRelocWidthPadded(const WasmRelocation &Rel) {
 202   switch (Rel.Type) {
 203   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
 204   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
 205   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
 206   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
 207   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
 208   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
 209     return 5;
 210   default:
 211     llvm_unreachable("unexpected relocation type");
 212   }
 213 }
 214
 215 static unsigned getRelocWidth(const WasmRelocation &Rel, uint32_t Value) {
 216   uint8_t Buf[5];
 217   return writeCompressedReloc(Buf, Rel, Value);
 218 }
 219
 220 // Relocations of type LEB and SLEB in the code section are padded to 5 bytes
 221 // so that a fast linker can blindly overwrite them without needing to worry
 222 // about the number of bytes needed to encode the values.
 223 // However, for optimal output the code section can be compressed to remove
 224 // the padding then outputting non-relocatable files.
 225 // In this case we need to perform a size calculation based on the value at each
 226 // relocation.  At best we end up saving 4 bytes for each relocation entry.
 227 //
 228 // This function only computes the final output size.  It must be called
 229 // before getSize() is used to calculate of layout of the code section.
 230 void InputFunction::calculateSize() {
 231   if (!File || !Config->CompressRelocTargets)
 232     return;
 233
 234   LLVM_DEBUG(dbgs() << "calculateSize: " << getName() << "\n");
 235
 236   const uint8_t *SecStart = File->CodeSection->Content.data();
 237   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
 238   uint32_t FunctionSizeLength;
 239   decodeULEB128(FuncStart, &FunctionSizeLength);
 240
 241   uint32_t Start = getInputSectionOffset();
 242   uint32_t End = Start + Function->Size;
 243
 244   uint32_t LastRelocEnd = Start + FunctionSizeLength;
 245   for (WasmRelocation &Rel : Relocations) {
 246     LLVM_DEBUG(dbgs() << "  region: " << (Rel.Offset - LastRelocEnd) << "\n");
 247     CompressedFuncSize += Rel.Offset - LastRelocEnd;
 248     CompressedFuncSize += getRelocWidth(Rel, File->calcNewValue(Rel));
 249     LastRelocEnd = Rel.Offset + getRelocWidthPadded(Rel);
 250   }
 251   LLVM_DEBUG(dbgs() << "  final region: " << (End - LastRelocEnd) << "\n");
 252   CompressedFuncSize += End - LastRelocEnd;
 253
 254   // Now we know how long the resulting function is we can add the encoding
 255   // of its length
 256   uint8_t Buf[5];
 257   CompressedSize = CompressedFuncSize + encodeULEB128(CompressedFuncSize, Buf);
 258
 259   LLVM_DEBUG(dbgs() << "  calculateSize orig: " << Function->Size << "\n");
 260   LLVM_DEBUG(dbgs() << "  calculateSize  new: " << CompressedSize << "\n");
 261 }
 262
 263 // Override the default writeTo method so that we can (optionally) write the
 264 // compressed version of the function.
 265 void InputFunction::writeTo(uint8_t *Buf) const {
 266   if (!File || !Config->CompressRelocTargets)
 267     return InputChunk::writeTo(Buf);
 268
 269   Buf += OutputOffset;
 270   uint8_t *Orig = Buf; (void)Orig;
 271
 272   const uint8_t *SecStart = File->CodeSection->Content.data();
 273   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
 274   const uint8_t *End = FuncStart + Function->Size;
 275   uint32_t Count;
 276   decodeULEB128(FuncStart, &Count);
 277   FuncStart += Count;
 278
 279   LLVM_DEBUG(dbgs() << "write func: " << getName() << "\n");
 280   Buf += encodeULEB128(CompressedFuncSize, Buf);
 281   const uint8_t *LastRelocEnd = FuncStart;
 282   for (const WasmRelocation &Rel : Relocations) {
 283     unsigned ChunkSize = (SecStart + Rel.Offset) - LastRelocEnd;
 284     LLVM_DEBUG(dbgs() << "  write chunk: " << ChunkSize << "\n");
 285     memcpy(Buf, LastRelocEnd, ChunkSize);
 286     Buf += ChunkSize;
 287     Buf += writeCompressedReloc(Buf, Rel, File->calcNewValue(Rel));
 288     LastRelocEnd = SecStart + Rel.Offset + getRelocWidthPadded(Rel);
 289   }
 290
 291   unsigned ChunkSize = End - LastRelocEnd;
 292   LLVM_DEBUG(dbgs() << "  write final chunk: " << ChunkSize << "\n");
 293   memcpy(Buf, LastRelocEnd, ChunkSize);
 294   LLVM_DEBUG(dbgs() << "  total: " << (Buf + ChunkSize - Orig) << "\n");
 295 }