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