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 using namespace lld;
23 using namespace lld::wasm;
24 
25 StringRef lld::relocTypeToString(uint8_t RelocType) {
26   switch (RelocType) {
27 #define WASM_RELOC(NAME, REL)                                                  \
28   case REL:                                                                    \
29     return #NAME;
30 #include "llvm/BinaryFormat/WasmRelocs.def"
31 #undef WASM_RELOC
32   }
33   llvm_unreachable("unknown reloc type");
34 }
35 
36 std::string lld::toString(const InputChunk *C) {
37   return (toString(C->File) + ":(" + C->getName() + ")").str();
38 }
39 
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: " << getName()
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                       << " addend=" << Rel.Addend << " index=" << Rel.Index
112                       << " value=" << Value << " offset=" << Rel.Offset
113                       << "\n");
114 
115     switch (Rel.Type) {
116     case R_WASM_TYPE_INDEX_LEB:
117     case R_WASM_FUNCTION_INDEX_LEB:
118     case R_WASM_GLOBAL_INDEX_LEB:
119     case R_WASM_EVENT_INDEX_LEB:
120     case R_WASM_MEMORY_ADDR_LEB:
121       encodeULEB128(Value, Loc, 5);
122       break;
123     case R_WASM_TABLE_INDEX_SLEB:
124     case R_WASM_TABLE_INDEX_REL_SLEB:
125     case R_WASM_MEMORY_ADDR_SLEB:
126     case R_WASM_MEMORY_ADDR_REL_SLEB:
127       encodeSLEB128(static_cast<int32_t>(Value), Loc, 5);
128       break;
129     case R_WASM_TABLE_INDEX_I32:
130     case R_WASM_MEMORY_ADDR_I32:
131     case R_WASM_FUNCTION_OFFSET_I32:
132     case R_WASM_SECTION_OFFSET_I32:
133       write32le(Loc, Value);
134       break;
135     default:
136       llvm_unreachable("unknown relocation type");
137     }
138   }
139 }
140 
141 // Copy relocation entries to a given output stream.
142 // This function is used only when a user passes "-r". For a regular link,
143 // we consume relocations instead of copying them to an output file.
144 void InputChunk::writeRelocations(raw_ostream &OS) const {
145   if (Relocations.empty())
146     return;
147 
148   int32_t Off = OutputOffset - getInputSectionOffset();
149   LLVM_DEBUG(dbgs() << "writeRelocations: " << File->getName()
150                     << " offset=" << Twine(Off) << "\n");
151 
152   for (const WasmRelocation &Rel : Relocations) {
153     writeUleb128(OS, Rel.Type, "reloc type");
154     writeUleb128(OS, Rel.Offset + Off, "reloc offset");
155     writeUleb128(OS, File->calcNewIndex(Rel), "reloc index");
156 
157     switch (Rel.Type) {
158     case R_WASM_MEMORY_ADDR_LEB:
159     case R_WASM_MEMORY_ADDR_SLEB:
160     case R_WASM_MEMORY_ADDR_I32:
161     case R_WASM_FUNCTION_OFFSET_I32:
162     case R_WASM_SECTION_OFFSET_I32:
163       writeSleb128(OS, File->calcNewAddend(Rel), "reloc addend");
164       break;
165     }
166   }
167 }
168 
169 void InputFunction::setFunctionIndex(uint32_t Index) {
170   LLVM_DEBUG(dbgs() << "InputFunction::setFunctionIndex: " << getName()
171                     << " -> " << Index << "\n");
172   assert(!hasFunctionIndex());
173   FunctionIndex = Index;
174 }
175 
176 void InputFunction::setTableIndex(uint32_t Index) {
177   LLVM_DEBUG(dbgs() << "InputFunction::setTableIndex: " << getName() << " -> "
178                     << Index << "\n");
179   assert(!hasTableIndex());
180   TableIndex = Index;
181 }
182 
183 // Write a relocation value without padding and return the number of bytes
184 // witten.
185 static unsigned writeCompressedReloc(uint8_t *Buf, const WasmRelocation &Rel,
186                                      uint32_t Value) {
187   switch (Rel.Type) {
188   case R_WASM_TYPE_INDEX_LEB:
189   case R_WASM_FUNCTION_INDEX_LEB:
190   case R_WASM_GLOBAL_INDEX_LEB:
191   case R_WASM_EVENT_INDEX_LEB:
192   case R_WASM_MEMORY_ADDR_LEB:
193     return encodeULEB128(Value, Buf);
194   case R_WASM_TABLE_INDEX_SLEB:
195   case R_WASM_MEMORY_ADDR_SLEB:
196     return encodeSLEB128(static_cast<int32_t>(Value), Buf);
197   default:
198     llvm_unreachable("unexpected relocation type");
199   }
200 }
201 
202 static unsigned getRelocWidthPadded(const WasmRelocation &Rel) {
203   switch (Rel.Type) {
204   case R_WASM_TYPE_INDEX_LEB:
205   case R_WASM_FUNCTION_INDEX_LEB:
206   case R_WASM_GLOBAL_INDEX_LEB:
207   case R_WASM_EVENT_INDEX_LEB:
208   case R_WASM_MEMORY_ADDR_LEB:
209   case R_WASM_TABLE_INDEX_SLEB:
210   case R_WASM_MEMORY_ADDR_SLEB:
211     return 5;
212   default:
213     llvm_unreachable("unexpected relocation type");
214   }
215 }
216 
217 static unsigned getRelocWidth(const WasmRelocation &Rel, uint32_t Value) {
218   uint8_t Buf[5];
219   return writeCompressedReloc(Buf, Rel, Value);
220 }
221 
222 // Relocations of type LEB and SLEB in the code section are padded to 5 bytes
223 // so that a fast linker can blindly overwrite them without needing to worry
224 // about the number of bytes needed to encode the values.
225 // However, for optimal output the code section can be compressed to remove
226 // the padding then outputting non-relocatable files.
227 // In this case we need to perform a size calculation based on the value at each
228 // relocation.  At best we end up saving 4 bytes for each relocation entry.
229 //
230 // This function only computes the final output size.  It must be called
231 // before getSize() is used to calculate of layout of the code section.
232 void InputFunction::calculateSize() {
233   if (!File || !Config->CompressRelocations)
234     return;
235 
236   LLVM_DEBUG(dbgs() << "calculateSize: " << getName() << "\n");
237 
238   const uint8_t *SecStart = File->CodeSection->Content.data();
239   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
240   uint32_t FunctionSizeLength;
241   decodeULEB128(FuncStart, &FunctionSizeLength);
242 
243   uint32_t Start = getInputSectionOffset();
244   uint32_t End = Start + Function->Size;
245 
246   uint32_t LastRelocEnd = Start + FunctionSizeLength;
247   for (const WasmRelocation &Rel : Relocations) {
248     LLVM_DEBUG(dbgs() << "  region: " << (Rel.Offset - LastRelocEnd) << "\n");
249     CompressedFuncSize += Rel.Offset - LastRelocEnd;
250     CompressedFuncSize += getRelocWidth(Rel, File->calcNewValue(Rel));
251     LastRelocEnd = Rel.Offset + getRelocWidthPadded(Rel);
252   }
253   LLVM_DEBUG(dbgs() << "  final region: " << (End - LastRelocEnd) << "\n");
254   CompressedFuncSize += End - LastRelocEnd;
255 
256   // Now we know how long the resulting function is we can add the encoding
257   // of its length
258   uint8_t Buf[5];
259   CompressedSize = CompressedFuncSize + encodeULEB128(CompressedFuncSize, Buf);
260 
261   LLVM_DEBUG(dbgs() << "  calculateSize orig: " << Function->Size << "\n");
262   LLVM_DEBUG(dbgs() << "  calculateSize  new: " << CompressedSize << "\n");
263 }
264 
265 // Override the default writeTo method so that we can (optionally) write the
266 // compressed version of the function.
267 void InputFunction::writeTo(uint8_t *Buf) const {
268   if (!File || !Config->CompressRelocations)
269     return InputChunk::writeTo(Buf);
270 
271   Buf += OutputOffset;
272   uint8_t *Orig = Buf;
273   (void)Orig;
274 
275   const uint8_t *SecStart = File->CodeSection->Content.data();
276   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
277   const uint8_t *End = FuncStart + Function->Size;
278   uint32_t Count;
279   decodeULEB128(FuncStart, &Count);
280   FuncStart += Count;
281 
282   LLVM_DEBUG(dbgs() << "write func: " << getName() << "\n");
283   Buf += encodeULEB128(CompressedFuncSize, Buf);
284   const uint8_t *LastRelocEnd = FuncStart;
285   for (const WasmRelocation &Rel : Relocations) {
286     unsigned ChunkSize = (SecStart + Rel.Offset) - LastRelocEnd;
287     LLVM_DEBUG(dbgs() << "  write chunk: " << ChunkSize << "\n");
288     memcpy(Buf, LastRelocEnd, ChunkSize);
289     Buf += ChunkSize;
290     Buf += writeCompressedReloc(Buf, Rel, File->calcNewValue(Rel));
291     LastRelocEnd = SecStart + Rel.Offset + getRelocWidthPadded(Rel);
292   }
293 
294   unsigned ChunkSize = End - LastRelocEnd;
295   LLVM_DEBUG(dbgs() << "  write final chunk: " << ChunkSize << "\n");
296   memcpy(Buf, LastRelocEnd, ChunkSize);
297   LLVM_DEBUG(dbgs() << "  total: " << (Buf + ChunkSize - Orig) << "\n");
298 }
299 
300 // Generate code to apply relocations to the data section at runtime.
301 // This is only called when generating shared libaries (PIC) where address are
302 // not known at static link time.
303 void InputSegment::generateRelocationCode(raw_ostream &OS) const {
304   uint32_t SegmentVA = OutputSeg->StartVA + OutputSegmentOffset;
305   for (const WasmRelocation &Rel : Relocations) {
306     uint32_t Offset = Rel.Offset - getInputSectionOffset();
307     uint32_t OutputVA = SegmentVA + Offset;
308 
309     // Get __memory_base
310     writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
311     writeUleb128(OS, WasmSym::MemoryBase->getGlobalIndex(), "memory_base");
312 
313     // Add the offset of the relocation
314     writeU8(OS, WASM_OPCODE_I32_CONST, "I32_CONST");
315     writeSleb128(OS, OutputVA, "offset");
316     writeU8(OS, WASM_OPCODE_I32_ADD, "ADD");
317 
318     // Now figure out what we want to store
319     switch (Rel.Type) {
320     case R_WASM_TABLE_INDEX_I32:
321       // Add the table index to the __table_base
322       writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
323       writeUleb128(OS, WasmSym::TableBase->getGlobalIndex(), "table_base");
324       writeU8(OS, WASM_OPCODE_I32_CONST, "CONST");
325       writeSleb128(OS, File->calcNewValue(Rel), "new table index");
326       writeU8(OS, WASM_OPCODE_I32_ADD, "ADD");
327       break;
328     case R_WASM_MEMORY_ADDR_I32: {
329       Symbol *Sym = File->getSymbol(Rel);
330       if (Sym->isLocal() || Sym->isHidden()) {
331         // Hidden/Local data symbols are accessed via known offset from
332         // __memory_base
333         writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
334         writeUleb128(OS, WasmSym::MemoryBase->getGlobalIndex(), "memory_base");
335         writeU8(OS, WASM_OPCODE_I32_CONST, "CONST");
336         writeSleb128(OS, File->calcNewValue(Rel), "new memory offset");
337         writeU8(OS, WASM_OPCODE_I32_ADD, "ADD");
338       } else {
339         // Default data symbols are accessed via imported GOT globals
340         writeU8(OS, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
341         writeUleb128(OS, Sym->getGOTIndex(), "global index");
342       }
343       break;
344     }
345     default:
346       llvm_unreachable("unexpected relocation type in data segment");
347     }
348 
349     // Store that value at the virtual address
350     writeU8(OS, WASM_OPCODE_I32_STORE, "I32_STORE");
351     writeUleb128(OS, 2, "align");
352     writeUleb128(OS, 0, "offset");
353   }
354 }
355