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 {
relocTypeToString(uint8_t relocType)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
relocIs64(uint8_t relocType)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
toString(const wasm::InputChunk * c)47 std::string toString(const wasm::InputChunk *c) {
48 return (toString(c->file) + ":(" + c->getName() + ")").str();
49 }
50
51 namespace wasm {
getComdatName() const52 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
verifyRelocTargets() const59 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.
writeTo(uint8_t * buf) const111 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.
writeRelocations(raw_ostream & os) const177 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
setFunctionIndex(uint32_t index)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
setTableIndex(uint32_t index)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.
writeCompressedReloc(uint8_t * buf,const WasmRelocation & rel,uint64_t value)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
getRelocWidthPadded(const WasmRelocation & rel)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
getRelocWidth(const WasmRelocation & rel,uint64_t value)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.
calculateSize()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.
writeTo(uint8_t * buf) const298 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.
generateRelocationCode(raw_ostream & os) const334 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