1 //===- InputChunks.cpp ----------------------------------------------------===// 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 #include "InputChunks.h" 10 #include "Config.h" 11 #include "OutputSegment.h" 12 #include "WriterUtils.h" 13 #include "lld/Common/ErrorHandler.h" 14 #include "lld/Common/LLVM.h" 15 #include "llvm/Support/LEB128.h" 16 17 #define DEBUG_TYPE "lld" 18 19 using namespace llvm; 20 using namespace llvm::wasm; 21 using namespace llvm::support::endian; 22 23 namespace lld { 24 StringRef relocTypeToString(uint8_t relocType) { 25 switch (relocType) { 26 #define WASM_RELOC(NAME, REL) \ 27 case REL: \ 28 return #NAME; 29 #include "llvm/BinaryFormat/WasmRelocs.def" 30 #undef WASM_RELOC 31 } 32 llvm_unreachable("unknown reloc type"); 33 } 34 35 bool relocIs64(uint8_t relocType) { 36 switch (relocType) { 37 case R_WASM_MEMORY_ADDR_LEB64: 38 case R_WASM_MEMORY_ADDR_SLEB64: 39 case R_WASM_MEMORY_ADDR_REL_SLEB64: 40 case R_WASM_MEMORY_ADDR_I64: 41 return true; 42 default: 43 return false; 44 } 45 } 46 47 std::string toString(const wasm::InputChunk *c) { 48 return (toString(c->file) + ":(" + c->getName() + ")").str(); 49 } 50 51 namespace wasm { 52 StringRef InputChunk::getComdatName() const { 53 uint32_t index = getComdat(); 54 if (index == UINT32_MAX) 55 return StringRef(); 56 return file->getWasmObj()->linkingData().Comdats[index]; 57 } 58 59 void InputChunk::verifyRelocTargets() const { 60 for (const WasmRelocation &rel : relocations) { 61 uint64_t existingValue; 62 unsigned bytesRead = 0; 63 auto offset = rel.Offset - getInputSectionOffset(); 64 const uint8_t *loc = data().data() + offset; 65 switch (rel.Type) { 66 case R_WASM_TYPE_INDEX_LEB: 67 case R_WASM_FUNCTION_INDEX_LEB: 68 case R_WASM_GLOBAL_INDEX_LEB: 69 case R_WASM_EVENT_INDEX_LEB: 70 case R_WASM_MEMORY_ADDR_LEB: 71 case R_WASM_MEMORY_ADDR_LEB64: 72 existingValue = decodeULEB128(loc, &bytesRead); 73 break; 74 case R_WASM_TABLE_INDEX_SLEB: 75 case R_WASM_TABLE_INDEX_REL_SLEB: 76 case R_WASM_MEMORY_ADDR_SLEB: 77 case R_WASM_MEMORY_ADDR_SLEB64: 78 case R_WASM_MEMORY_ADDR_REL_SLEB: 79 case R_WASM_MEMORY_ADDR_REL_SLEB64: 80 existingValue = static_cast<uint64_t>(decodeSLEB128(loc, &bytesRead)); 81 break; 82 case R_WASM_TABLE_INDEX_I32: 83 case R_WASM_MEMORY_ADDR_I32: 84 case R_WASM_FUNCTION_OFFSET_I32: 85 case R_WASM_SECTION_OFFSET_I32: 86 case R_WASM_GLOBAL_INDEX_I32: 87 existingValue = read32le(loc); 88 break; 89 case R_WASM_MEMORY_ADDR_I64: 90 existingValue = read64le(loc); 91 break; 92 default: 93 llvm_unreachable("unknown relocation type"); 94 } 95 96 if (bytesRead && bytesRead != 5) 97 warn("expected LEB at relocation site be 5-byte padded"); 98 99 if (rel.Type != R_WASM_GLOBAL_INDEX_LEB && 100 rel.Type != R_WASM_GLOBAL_INDEX_I32) { 101 auto expectedValue = file->calcExpectedValue(rel); 102 if (expectedValue != existingValue) 103 warn("unexpected existing value for " + relocTypeToString(rel.Type) + 104 ": existing=" + Twine(existingValue) + 105 " expected=" + Twine(expectedValue)); 106 } 107 } 108 } 109 110 // Copy this input chunk to an mmap'ed output file and apply relocations. 111 void InputChunk::writeTo(uint8_t *buf) const { 112 // Copy contents 113 memcpy(buf + outputOffset, data().data(), data().size()); 114 115 // Apply relocations 116 if (relocations.empty()) 117 return; 118 119 #ifndef NDEBUG 120 verifyRelocTargets(); 121 #endif 122 123 LLVM_DEBUG(dbgs() << "applying relocations: " << toString(this) 124 << " count=" << relocations.size() << "\n"); 125 int32_t off = outputOffset - getInputSectionOffset(); 126 127 for (const WasmRelocation &rel : relocations) { 128 uint8_t *loc = buf + rel.Offset + off; 129 auto value = file->calcNewValue(rel); 130 LLVM_DEBUG(dbgs() << "apply reloc: type=" << relocTypeToString(rel.Type)); 131 if (rel.Type != R_WASM_TYPE_INDEX_LEB) 132 LLVM_DEBUG(dbgs() << " sym=" << file->getSymbols()[rel.Index]->getName()); 133 LLVM_DEBUG(dbgs() << " addend=" << rel.Addend << " index=" << rel.Index 134 << " value=" << value << " offset=" << rel.Offset 135 << "\n"); 136 137 switch (rel.Type) { 138 case R_WASM_TYPE_INDEX_LEB: 139 case R_WASM_FUNCTION_INDEX_LEB: 140 case R_WASM_GLOBAL_INDEX_LEB: 141 case R_WASM_EVENT_INDEX_LEB: 142 case R_WASM_MEMORY_ADDR_LEB: 143 encodeULEB128(value, loc, 5); 144 break; 145 case R_WASM_MEMORY_ADDR_LEB64: 146 encodeULEB128(value, loc, 10); 147 break; 148 case R_WASM_TABLE_INDEX_SLEB: 149 case R_WASM_TABLE_INDEX_REL_SLEB: 150 case R_WASM_MEMORY_ADDR_SLEB: 151 case R_WASM_MEMORY_ADDR_REL_SLEB: 152 encodeSLEB128(static_cast<int32_t>(value), loc, 5); 153 break; 154 case R_WASM_MEMORY_ADDR_SLEB64: 155 case R_WASM_MEMORY_ADDR_REL_SLEB64: 156 encodeSLEB128(static_cast<int64_t>(value), loc, 10); 157 break; 158 case R_WASM_TABLE_INDEX_I32: 159 case R_WASM_MEMORY_ADDR_I32: 160 case R_WASM_FUNCTION_OFFSET_I32: 161 case R_WASM_SECTION_OFFSET_I32: 162 case R_WASM_GLOBAL_INDEX_I32: 163 write32le(loc, value); 164 break; 165 case R_WASM_MEMORY_ADDR_I64: 166 write64le(loc, value); 167 break; 168 default: 169 llvm_unreachable("unknown relocation type"); 170 } 171 } 172 } 173 174 // Copy relocation entries to a given output stream. 175 // This function is used only when a user passes "-r". For a regular link, 176 // we consume relocations instead of copying them to an output file. 177 void InputChunk::writeRelocations(raw_ostream &os) const { 178 if (relocations.empty()) 179 return; 180 181 int32_t off = outputOffset - getInputSectionOffset(); 182 LLVM_DEBUG(dbgs() << "writeRelocations: " << file->getName() 183 << " offset=" << Twine(off) << "\n"); 184 185 for (const WasmRelocation &rel : relocations) { 186 writeUleb128(os, rel.Type, "reloc type"); 187 writeUleb128(os, rel.Offset + off, "reloc offset"); 188 writeUleb128(os, file->calcNewIndex(rel), "reloc index"); 189 190 if (relocTypeHasAddend(rel.Type)) 191 writeSleb128(os, file->calcNewAddend(rel), "reloc addend"); 192 } 193 } 194 195 void InputFunction::setFunctionIndex(uint32_t index) { 196 LLVM_DEBUG(dbgs() << "InputFunction::setFunctionIndex: " << getName() 197 << " -> " << index << "\n"); 198 assert(!hasFunctionIndex()); 199 functionIndex = index; 200 } 201 202 void InputFunction::setTableIndex(uint32_t index) { 203 LLVM_DEBUG(dbgs() << "InputFunction::setTableIndex: " << getName() << " -> " 204 << index << "\n"); 205 assert(!hasTableIndex()); 206 tableIndex = index; 207 } 208 209 // Write a relocation value without padding and return the number of bytes 210 // witten. 211 static unsigned writeCompressedReloc(uint8_t *buf, const WasmRelocation &rel, 212 uint64_t value) { 213 switch (rel.Type) { 214 case R_WASM_TYPE_INDEX_LEB: 215 case R_WASM_FUNCTION_INDEX_LEB: 216 case R_WASM_GLOBAL_INDEX_LEB: 217 case R_WASM_EVENT_INDEX_LEB: 218 case R_WASM_MEMORY_ADDR_LEB: 219 case R_WASM_MEMORY_ADDR_LEB64: 220 return encodeULEB128(value, buf); 221 case R_WASM_TABLE_INDEX_SLEB: 222 case R_WASM_MEMORY_ADDR_SLEB: 223 case R_WASM_MEMORY_ADDR_SLEB64: 224 return encodeSLEB128(static_cast<int64_t>(value), buf); 225 default: 226 llvm_unreachable("unexpected relocation type"); 227 } 228 } 229 230 static unsigned getRelocWidthPadded(const WasmRelocation &rel) { 231 switch (rel.Type) { 232 case R_WASM_TYPE_INDEX_LEB: 233 case R_WASM_FUNCTION_INDEX_LEB: 234 case R_WASM_GLOBAL_INDEX_LEB: 235 case R_WASM_EVENT_INDEX_LEB: 236 case R_WASM_MEMORY_ADDR_LEB: 237 case R_WASM_TABLE_INDEX_SLEB: 238 case R_WASM_MEMORY_ADDR_SLEB: 239 return 5; 240 case R_WASM_MEMORY_ADDR_LEB64: 241 case R_WASM_MEMORY_ADDR_SLEB64: 242 return 10; 243 default: 244 llvm_unreachable("unexpected relocation type"); 245 } 246 } 247 248 static unsigned getRelocWidth(const WasmRelocation &rel, uint64_t value) { 249 uint8_t buf[10]; 250 return writeCompressedReloc(buf, rel, value); 251 } 252 253 // Relocations of type LEB and SLEB in the code section are padded to 5 bytes 254 // so that a fast linker can blindly overwrite them without needing to worry 255 // about the number of bytes needed to encode the values. 256 // However, for optimal output the code section can be compressed to remove 257 // the padding then outputting non-relocatable files. 258 // In this case we need to perform a size calculation based on the value at each 259 // relocation. At best we end up saving 4 bytes for each relocation entry. 260 // 261 // This function only computes the final output size. It must be called 262 // before getSize() is used to calculate of layout of the code section. 263 void InputFunction::calculateSize() { 264 if (!file || !config->compressRelocations) 265 return; 266 267 LLVM_DEBUG(dbgs() << "calculateSize: " << getName() << "\n"); 268 269 const uint8_t *secStart = file->codeSection->Content.data(); 270 const uint8_t *funcStart = secStart + getInputSectionOffset(); 271 uint32_t functionSizeLength; 272 decodeULEB128(funcStart, &functionSizeLength); 273 274 uint32_t start = getInputSectionOffset(); 275 uint32_t end = start + function->Size; 276 277 uint32_t lastRelocEnd = start + functionSizeLength; 278 for (const WasmRelocation &rel : relocations) { 279 LLVM_DEBUG(dbgs() << " region: " << (rel.Offset - lastRelocEnd) << "\n"); 280 compressedFuncSize += rel.Offset - lastRelocEnd; 281 compressedFuncSize += getRelocWidth(rel, file->calcNewValue(rel)); 282 lastRelocEnd = rel.Offset + getRelocWidthPadded(rel); 283 } 284 LLVM_DEBUG(dbgs() << " final region: " << (end - lastRelocEnd) << "\n"); 285 compressedFuncSize += end - lastRelocEnd; 286 287 // Now we know how long the resulting function is we can add the encoding 288 // of its length 289 uint8_t buf[5]; 290 compressedSize = compressedFuncSize + encodeULEB128(compressedFuncSize, buf); 291 292 LLVM_DEBUG(dbgs() << " calculateSize orig: " << function->Size << "\n"); 293 LLVM_DEBUG(dbgs() << " calculateSize new: " << compressedSize << "\n"); 294 } 295 296 // Override the default writeTo method so that we can (optionally) write the 297 // compressed version of the function. 298 void InputFunction::writeTo(uint8_t *buf) const { 299 if (!file || !config->compressRelocations) 300 return InputChunk::writeTo(buf); 301 302 buf += outputOffset; 303 uint8_t *orig = buf; 304 (void)orig; 305 306 const uint8_t *secStart = file->codeSection->Content.data(); 307 const uint8_t *funcStart = secStart + getInputSectionOffset(); 308 const uint8_t *end = funcStart + function->Size; 309 uint32_t count; 310 decodeULEB128(funcStart, &count); 311 funcStart += count; 312 313 LLVM_DEBUG(dbgs() << "write func: " << getName() << "\n"); 314 buf += encodeULEB128(compressedFuncSize, buf); 315 const uint8_t *lastRelocEnd = funcStart; 316 for (const WasmRelocation &rel : relocations) { 317 unsigned chunkSize = (secStart + rel.Offset) - lastRelocEnd; 318 LLVM_DEBUG(dbgs() << " write chunk: " << chunkSize << "\n"); 319 memcpy(buf, lastRelocEnd, chunkSize); 320 buf += chunkSize; 321 buf += writeCompressedReloc(buf, rel, file->calcNewValue(rel)); 322 lastRelocEnd = secStart + rel.Offset + getRelocWidthPadded(rel); 323 } 324 325 unsigned chunkSize = end - lastRelocEnd; 326 LLVM_DEBUG(dbgs() << " write final chunk: " << chunkSize << "\n"); 327 memcpy(buf, lastRelocEnd, chunkSize); 328 LLVM_DEBUG(dbgs() << " total: " << (buf + chunkSize - orig) << "\n"); 329 } 330 331 // Generate code to apply relocations to the data section at runtime. 332 // This is only called when generating shared libaries (PIC) where address are 333 // not known at static link time. 334 void InputSegment::generateRelocationCode(raw_ostream &os) const { 335 LLVM_DEBUG(dbgs() << "generating runtime relocations: " << getName() 336 << " count=" << relocations.size() << "\n"); 337 338 unsigned opcode_ptr_const = 339 config->is64 ? WASM_OPCODE_I64_CONST : WASM_OPCODE_I32_CONST; 340 unsigned opcode_ptr_add = 341 config->is64 ? WASM_OPCODE_I64_ADD : WASM_OPCODE_I32_ADD; 342 343 // TODO(sbc): Encode the relocations in the data section and write a loop 344 // here to apply them. 345 uint32_t segmentVA = outputSeg->startVA + outputSegmentOffset; 346 for (const WasmRelocation &rel : relocations) { 347 uint64_t offset = rel.Offset - getInputSectionOffset(); 348 uint64_t outputOffset = segmentVA + offset; 349 350 LLVM_DEBUG(dbgs() << "gen reloc: type=" << relocTypeToString(rel.Type) 351 << " addend=" << rel.Addend << " index=" << rel.Index 352 << " output offset=" << outputOffset << "\n"); 353 354 // Get __memory_base 355 writeU8(os, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET"); 356 writeUleb128(os, WasmSym::memoryBase->getGlobalIndex(), "memory_base"); 357 358 // Add the offset of the relocation 359 writeU8(os, opcode_ptr_const, "CONST"); 360 writeSleb128(os, outputOffset, "offset"); 361 writeU8(os, opcode_ptr_add, "ADD"); 362 363 bool is64 = relocIs64(rel.Type); 364 unsigned opcode_reloc_const = 365 is64 ? WASM_OPCODE_I64_CONST : WASM_OPCODE_I32_CONST; 366 unsigned opcode_reloc_add = 367 is64 ? WASM_OPCODE_I64_ADD : WASM_OPCODE_I32_ADD; 368 unsigned opcode_reloc_store = 369 is64 ? WASM_OPCODE_I64_STORE : WASM_OPCODE_I32_STORE; 370 371 Symbol *sym = file->getSymbol(rel); 372 // Now figure out what we want to store 373 if (sym->hasGOTIndex()) { 374 writeU8(os, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET"); 375 writeUleb128(os, sym->getGOTIndex(), "global index"); 376 if (rel.Addend) { 377 writeU8(os, opcode_reloc_const, "CONST"); 378 writeSleb128(os, rel.Addend, "addend"); 379 writeU8(os, opcode_reloc_add, "ADD"); 380 } 381 } else { 382 const GlobalSymbol* baseSymbol = WasmSym::memoryBase; 383 if (rel.Type == R_WASM_TABLE_INDEX_I32) 384 baseSymbol = WasmSym::tableBase; 385 writeU8(os, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET"); 386 writeUleb128(os, baseSymbol->getGlobalIndex(), "base"); 387 writeU8(os, opcode_reloc_const, "CONST"); 388 writeSleb128(os, file->calcNewValue(rel), "offset"); 389 writeU8(os, opcode_reloc_add, "ADD"); 390 } 391 392 // Store that value at the virtual address 393 writeU8(os, opcode_reloc_store, "I32_STORE"); 394 writeUleb128(os, 2, "align"); 395 writeUleb128(os, 0, "offset"); 396 } 397 } 398 399 } // namespace wasm 400 } // namespace lld 401