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