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