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_MEMORY_ADDR_SLEB:
63       ExistingValue = static_cast<uint32_t>(decodeSLEB128(Loc, &BytesRead));
64       break;
65     case R_WASM_TABLE_INDEX_I32:
66     case R_WASM_MEMORY_ADDR_I32:
67     case R_WASM_FUNCTION_OFFSET_I32:
68     case R_WASM_SECTION_OFFSET_I32:
69       ExistingValue = static_cast<uint32_t>(read32le(Loc));
70       break;
71     default:
72       llvm_unreachable("unknown relocation type");
73     }
74 
75     if (BytesRead && BytesRead != 5)
76       warn("expected LEB at relocation site be 5-byte padded");
77 
78     if (Rel.Type != R_WASM_GLOBAL_INDEX_LEB) {
79       uint32_t ExpectedValue = File->calcExpectedValue(Rel);
80       if (ExpectedValue != ExistingValue)
81         warn("unexpected existing value for " + relocTypeToString(Rel.Type) +
82              ": existing=" + Twine(ExistingValue) +
83              " expected=" + Twine(ExpectedValue));
84     }
85   }
86 }
87 
88 // Copy this input chunk to an mmap'ed output file and apply relocations.
89 void InputChunk::writeTo(uint8_t *Buf) const {
90   // Copy contents
91   memcpy(Buf + OutputOffset, data().data(), data().size());
92 
93   // Apply relocations
94   if (Relocations.empty())
95     return;
96 
97 #ifndef NDEBUG
98   verifyRelocTargets();
99 #endif
100 
101   LLVM_DEBUG(dbgs() << "applying relocations: " << getName()
102                     << " count=" << Relocations.size() << "\n");
103   int32_t Off = OutputOffset - getInputSectionOffset();
104 
105   for (const WasmRelocation &Rel : Relocations) {
106     uint8_t *Loc = Buf + Rel.Offset + Off;
107     uint32_t Value = File->calcNewValue(Rel);
108     LLVM_DEBUG(dbgs() << "apply reloc: type=" << relocTypeToString(Rel.Type)
109                       << " addend=" << Rel.Addend << " index=" << Rel.Index
110                       << " value=" << Value << " offset=" << Rel.Offset
111                       << "\n");
112 
113     switch (Rel.Type) {
114     case R_WASM_TYPE_INDEX_LEB:
115     case R_WASM_FUNCTION_INDEX_LEB:
116     case R_WASM_GLOBAL_INDEX_LEB:
117     case R_WASM_EVENT_INDEX_LEB:
118     case R_WASM_MEMORY_ADDR_LEB:
119       encodeULEB128(Value, Loc, 5);
120       break;
121     case R_WASM_TABLE_INDEX_SLEB:
122     case R_WASM_MEMORY_ADDR_SLEB:
123       encodeSLEB128(static_cast<int32_t>(Value), Loc, 5);
124       break;
125     case R_WASM_TABLE_INDEX_I32:
126     case R_WASM_MEMORY_ADDR_I32:
127     case R_WASM_FUNCTION_OFFSET_I32:
128     case R_WASM_SECTION_OFFSET_I32:
129       write32le(Loc, Value);
130       break;
131     default:
132       llvm_unreachable("unknown relocation type");
133     }
134   }
135 }
136 
137 // Copy relocation entries to a given output stream.
138 // This function is used only when a user passes "-r". For a regular link,
139 // we consume relocations instead of copying them to an output file.
140 void InputChunk::writeRelocations(raw_ostream &OS) const {
141   if (Relocations.empty())
142     return;
143 
144   int32_t Off = OutputOffset - getInputSectionOffset();
145   LLVM_DEBUG(dbgs() << "writeRelocations: " << File->getName()
146                     << " offset=" << Twine(Off) << "\n");
147 
148   for (const WasmRelocation &Rel : Relocations) {
149     writeUleb128(OS, Rel.Type, "reloc type");
150     writeUleb128(OS, Rel.Offset + Off, "reloc offset");
151     writeUleb128(OS, File->calcNewIndex(Rel), "reloc index");
152 
153     switch (Rel.Type) {
154     case R_WASM_MEMORY_ADDR_LEB:
155     case R_WASM_MEMORY_ADDR_SLEB:
156     case R_WASM_MEMORY_ADDR_I32:
157     case R_WASM_FUNCTION_OFFSET_I32:
158     case R_WASM_SECTION_OFFSET_I32:
159       writeSleb128(OS, File->calcNewAddend(Rel), "reloc addend");
160       break;
161     }
162   }
163 }
164 
165 void InputFunction::setFunctionIndex(uint32_t Index) {
166   LLVM_DEBUG(dbgs() << "InputFunction::setFunctionIndex: " << getName()
167                     << " -> " << Index << "\n");
168   assert(!hasFunctionIndex());
169   FunctionIndex = Index;
170 }
171 
172 void InputFunction::setTableIndex(uint32_t Index) {
173   LLVM_DEBUG(dbgs() << "InputFunction::setTableIndex: " << getName() << " -> "
174                     << Index << "\n");
175   assert(!hasTableIndex());
176   TableIndex = Index;
177 }
178 
179 // Write a relocation value without padding and return the number of bytes
180 // witten.
181 static unsigned writeCompressedReloc(uint8_t *Buf, const WasmRelocation &Rel,
182                                      uint32_t Value) {
183   switch (Rel.Type) {
184   case R_WASM_TYPE_INDEX_LEB:
185   case R_WASM_FUNCTION_INDEX_LEB:
186   case R_WASM_GLOBAL_INDEX_LEB:
187   case R_WASM_EVENT_INDEX_LEB:
188   case R_WASM_MEMORY_ADDR_LEB:
189     return encodeULEB128(Value, Buf);
190   case R_WASM_TABLE_INDEX_SLEB:
191   case R_WASM_MEMORY_ADDR_SLEB:
192     return encodeSLEB128(static_cast<int32_t>(Value), Buf);
193   default:
194     llvm_unreachable("unexpected relocation type");
195   }
196 }
197 
198 static unsigned getRelocWidthPadded(const WasmRelocation &Rel) {
199   switch (Rel.Type) {
200   case R_WASM_TYPE_INDEX_LEB:
201   case R_WASM_FUNCTION_INDEX_LEB:
202   case R_WASM_GLOBAL_INDEX_LEB:
203   case R_WASM_EVENT_INDEX_LEB:
204   case R_WASM_MEMORY_ADDR_LEB:
205   case R_WASM_TABLE_INDEX_SLEB:
206   case R_WASM_MEMORY_ADDR_SLEB:
207     return 5;
208   default:
209     llvm_unreachable("unexpected relocation type");
210   }
211 }
212 
213 static unsigned getRelocWidth(const WasmRelocation &Rel, uint32_t Value) {
214   uint8_t Buf[5];
215   return writeCompressedReloc(Buf, Rel, Value);
216 }
217 
218 // Relocations of type LEB and SLEB in the code section are padded to 5 bytes
219 // so that a fast linker can blindly overwrite them without needing to worry
220 // about the number of bytes needed to encode the values.
221 // However, for optimal output the code section can be compressed to remove
222 // the padding then outputting non-relocatable files.
223 // In this case we need to perform a size calculation based on the value at each
224 // relocation.  At best we end up saving 4 bytes for each relocation entry.
225 //
226 // This function only computes the final output size.  It must be called
227 // before getSize() is used to calculate of layout of the code section.
228 void InputFunction::calculateSize() {
229   if (!File || !Config->CompressRelocations)
230     return;
231 
232   LLVM_DEBUG(dbgs() << "calculateSize: " << getName() << "\n");
233 
234   const uint8_t *SecStart = File->CodeSection->Content.data();
235   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
236   uint32_t FunctionSizeLength;
237   decodeULEB128(FuncStart, &FunctionSizeLength);
238 
239   uint32_t Start = getInputSectionOffset();
240   uint32_t End = Start + Function->Size;
241 
242   uint32_t LastRelocEnd = Start + FunctionSizeLength;
243   for (const WasmRelocation &Rel : Relocations) {
244     LLVM_DEBUG(dbgs() << "  region: " << (Rel.Offset - LastRelocEnd) << "\n");
245     CompressedFuncSize += Rel.Offset - LastRelocEnd;
246     CompressedFuncSize += getRelocWidth(Rel, File->calcNewValue(Rel));
247     LastRelocEnd = Rel.Offset + getRelocWidthPadded(Rel);
248   }
249   LLVM_DEBUG(dbgs() << "  final region: " << (End - LastRelocEnd) << "\n");
250   CompressedFuncSize += End - LastRelocEnd;
251 
252   // Now we know how long the resulting function is we can add the encoding
253   // of its length
254   uint8_t Buf[5];
255   CompressedSize = CompressedFuncSize + encodeULEB128(CompressedFuncSize, Buf);
256 
257   LLVM_DEBUG(dbgs() << "  calculateSize orig: " << Function->Size << "\n");
258   LLVM_DEBUG(dbgs() << "  calculateSize  new: " << CompressedSize << "\n");
259 }
260 
261 // Override the default writeTo method so that we can (optionally) write the
262 // compressed version of the function.
263 void InputFunction::writeTo(uint8_t *Buf) const {
264   if (!File || !Config->CompressRelocations)
265     return InputChunk::writeTo(Buf);
266 
267   Buf += OutputOffset;
268   uint8_t *Orig = Buf;
269   (void)Orig;
270 
271   const uint8_t *SecStart = File->CodeSection->Content.data();
272   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
273   const uint8_t *End = FuncStart + Function->Size;
274   uint32_t Count;
275   decodeULEB128(FuncStart, &Count);
276   FuncStart += Count;
277 
278   LLVM_DEBUG(dbgs() << "write func: " << getName() << "\n");
279   Buf += encodeULEB128(CompressedFuncSize, Buf);
280   const uint8_t *LastRelocEnd = FuncStart;
281   for (const WasmRelocation &Rel : Relocations) {
282     unsigned ChunkSize = (SecStart + Rel.Offset) - LastRelocEnd;
283     LLVM_DEBUG(dbgs() << "  write chunk: " << ChunkSize << "\n");
284     memcpy(Buf, LastRelocEnd, ChunkSize);
285     Buf += ChunkSize;
286     Buf += writeCompressedReloc(Buf, Rel, File->calcNewValue(Rel));
287     LastRelocEnd = SecStart + Rel.Offset + getRelocWidthPadded(Rel);
288   }
289 
290   unsigned ChunkSize = End - LastRelocEnd;
291   LLVM_DEBUG(dbgs() << "  write final chunk: " << ChunkSize << "\n");
292   memcpy(Buf, LastRelocEnd, ChunkSize);
293   LLVM_DEBUG(dbgs() << "  total: " << (Buf + ChunkSize - Orig) << "\n");
294 }
295