1 //===- InputChunks.cpp ----------------------------------------------------===//
2 //
3 //                             The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "InputChunks.h"
11 #include "Config.h"
12 #include "OutputSegment.h"
13 #include "WriterUtils.h"
14 #include "lld/Common/ErrorHandler.h"
15 #include "lld/Common/LLVM.h"
16 #include "llvm/Support/LEB128.h"
17 
18 #define DEBUG_TYPE "lld"
19 
20 using namespace llvm;
21 using namespace llvm::wasm;
22 using namespace llvm::support::endian;
23 using namespace lld;
24 using namespace lld::wasm;
25 
26 static StringRef ReloctTypeToString(uint8_t RelocType) {
27   switch (RelocType) {
28 #define WASM_RELOC(NAME, REL)                                                  \
29   case REL:                                                                    \
30     return #NAME;
31 #include "llvm/BinaryFormat/WasmRelocs.def"
32 #undef WASM_RELOC
33   }
34   llvm_unreachable("unknown reloc type");
35 }
36 
37 std::string lld::toString(const InputChunk *C) {
38   return (toString(C->File) + ":(" + C->getName() + ")").str();
39 }
40 
41 StringRef InputChunk::getComdatName() const {
42   uint32_t Index = getComdat();
43   if (Index == UINT32_MAX)
44     return StringRef();
45   return File->getWasmObj()->linkingData().Comdats[Index];
46 }
47 
48 void InputChunk::verifyRelocTargets() const {
49   for (const WasmRelocation &Rel : Relocations) {
50     uint32_t ExistingValue;
51     unsigned BytesRead = 0;
52     uint32_t Offset = Rel.Offset - getInputSectionOffset();
53     const uint8_t *Loc = data().data() + Offset;
54     switch (Rel.Type) {
55     case R_WEBASSEMBLY_TYPE_INDEX_LEB:
56     case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
57     case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
58     case R_WEBASSEMBLY_EVENT_INDEX_LEB:
59     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
60       ExistingValue = decodeULEB128(Loc, &BytesRead);
61       break;
62     case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
63     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
64       ExistingValue = static_cast<uint32_t>(decodeSLEB128(Loc, &BytesRead));
65       break;
66     case R_WEBASSEMBLY_TABLE_INDEX_I32:
67     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
68     case R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
69     case R_WEBASSEMBLY_SECTION_OFFSET_I32:
70       ExistingValue = static_cast<uint32_t>(read32le(Loc));
71       break;
72     default:
73       llvm_unreachable("unknown relocation type");
74     }
75 
76     if (BytesRead && BytesRead != 5)
77       warn("expected LEB at relocation site be 5-byte padded");
78     uint32_t ExpectedValue = File->calcExpectedValue(Rel);
79     if (ExpectedValue != ExistingValue)
80       warn("unexpected existing value for " + ReloctTypeToString(Rel.Type) +
81            ": existing=" + Twine(ExistingValue) +
82            " expected=" + Twine(ExpectedValue));
83   }
84 }
85 
86 // Copy this input chunk to an mmap'ed output file and apply relocations.
87 void InputChunk::writeTo(uint8_t *Buf) const {
88   // Copy contents
89   memcpy(Buf + OutputOffset, data().data(), data().size());
90 
91   // Apply relocations
92   if (Relocations.empty())
93     return;
94 
95 #ifndef NDEBUG
96   verifyRelocTargets();
97 #endif
98 
99   LLVM_DEBUG(dbgs() << "applying relocations: " << getName()
100                     << " count=" << Relocations.size() << "\n");
101   int32_t Off = OutputOffset - getInputSectionOffset();
102 
103   for (const WasmRelocation &Rel : Relocations) {
104     uint8_t *Loc = Buf + Rel.Offset + Off;
105     uint32_t Value = File->calcNewValue(Rel);
106     LLVM_DEBUG(dbgs() << "apply reloc: type=" << ReloctTypeToString(Rel.Type)
107                       << " addend=" << Rel.Addend << " index=" << Rel.Index
108                       << " value=" << Value << " offset=" << Rel.Offset
109                       << "\n");
110 
111     switch (Rel.Type) {
112     case R_WEBASSEMBLY_TYPE_INDEX_LEB:
113     case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
114     case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
115     case R_WEBASSEMBLY_EVENT_INDEX_LEB:
116     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
117       encodeULEB128(Value, Loc, 5);
118       break;
119     case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
120     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
121       encodeSLEB128(static_cast<int32_t>(Value), Loc, 5);
122       break;
123     case R_WEBASSEMBLY_TABLE_INDEX_I32:
124     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
125     case R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
126     case R_WEBASSEMBLY_SECTION_OFFSET_I32:
127       write32le(Loc, Value);
128       break;
129     default:
130       llvm_unreachable("unknown relocation type");
131     }
132   }
133 }
134 
135 // Copy relocation entries to a given output stream.
136 // This function is used only when a user passes "-r". For a regular link,
137 // we consume relocations instead of copying them to an output file.
138 void InputChunk::writeRelocations(raw_ostream &OS) const {
139   if (Relocations.empty())
140     return;
141 
142   int32_t Off = OutputOffset - getInputSectionOffset();
143   LLVM_DEBUG(dbgs() << "writeRelocations: " << File->getName()
144                     << " offset=" << Twine(Off) << "\n");
145 
146   for (const WasmRelocation &Rel : Relocations) {
147     writeUleb128(OS, Rel.Type, "reloc type");
148     writeUleb128(OS, Rel.Offset + Off, "reloc offset");
149     writeUleb128(OS, File->calcNewIndex(Rel), "reloc index");
150 
151     switch (Rel.Type) {
152     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
153     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
154     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
155     case R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
156     case R_WEBASSEMBLY_SECTION_OFFSET_I32:
157       writeSleb128(OS, File->calcNewAddend(Rel), "reloc addend");
158       break;
159     }
160   }
161 }
162 
163 void InputFunction::setFunctionIndex(uint32_t Index) {
164   LLVM_DEBUG(dbgs() << "InputFunction::setFunctionIndex: " << getName()
165                     << " -> " << Index << "\n");
166   assert(!hasFunctionIndex());
167   FunctionIndex = Index;
168 }
169 
170 void InputFunction::setTableIndex(uint32_t Index) {
171   LLVM_DEBUG(dbgs() << "InputFunction::setTableIndex: " << getName() << " -> "
172                     << Index << "\n");
173   assert(!hasTableIndex());
174   TableIndex = Index;
175 }
176 
177 // Write a relocation value without padding and return the number of bytes
178 // witten.
179 static unsigned writeCompressedReloc(uint8_t *Buf, const WasmRelocation &Rel,
180                                      uint32_t Value) {
181   switch (Rel.Type) {
182   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
183   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
184   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
185   case R_WEBASSEMBLY_EVENT_INDEX_LEB:
186   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
187     return encodeULEB128(Value, Buf);
188   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
189   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
190     return encodeSLEB128(static_cast<int32_t>(Value), Buf);
191   default:
192     llvm_unreachable("unexpected relocation type");
193   }
194 }
195 
196 static unsigned getRelocWidthPadded(const WasmRelocation &Rel) {
197   switch (Rel.Type) {
198   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
199   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
200   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
201   case R_WEBASSEMBLY_EVENT_INDEX_LEB:
202   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
203   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
204   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
205     return 5;
206   default:
207     llvm_unreachable("unexpected relocation type");
208   }
209 }
210 
211 static unsigned getRelocWidth(const WasmRelocation &Rel, uint32_t Value) {
212   uint8_t Buf[5];
213   return writeCompressedReloc(Buf, Rel, Value);
214 }
215 
216 // Relocations of type LEB and SLEB in the code section are padded to 5 bytes
217 // so that a fast linker can blindly overwrite them without needing to worry
218 // about the number of bytes needed to encode the values.
219 // However, for optimal output the code section can be compressed to remove
220 // the padding then outputting non-relocatable files.
221 // In this case we need to perform a size calculation based on the value at each
222 // relocation.  At best we end up saving 4 bytes for each relocation entry.
223 //
224 // This function only computes the final output size.  It must be called
225 // before getSize() is used to calculate of layout of the code section.
226 void InputFunction::calculateSize() {
227   if (!File || !Config->CompressRelocations)
228     return;
229 
230   LLVM_DEBUG(dbgs() << "calculateSize: " << getName() << "\n");
231 
232   const uint8_t *SecStart = File->CodeSection->Content.data();
233   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
234   uint32_t FunctionSizeLength;
235   decodeULEB128(FuncStart, &FunctionSizeLength);
236 
237   uint32_t Start = getInputSectionOffset();
238   uint32_t End = Start + Function->Size;
239 
240   uint32_t LastRelocEnd = Start + FunctionSizeLength;
241   for (const WasmRelocation &Rel : Relocations) {
242     LLVM_DEBUG(dbgs() << "  region: " << (Rel.Offset - LastRelocEnd) << "\n");
243     CompressedFuncSize += Rel.Offset - LastRelocEnd;
244     CompressedFuncSize += getRelocWidth(Rel, File->calcNewValue(Rel));
245     LastRelocEnd = Rel.Offset + getRelocWidthPadded(Rel);
246   }
247   LLVM_DEBUG(dbgs() << "  final region: " << (End - LastRelocEnd) << "\n");
248   CompressedFuncSize += End - LastRelocEnd;
249 
250   // Now we know how long the resulting function is we can add the encoding
251   // of its length
252   uint8_t Buf[5];
253   CompressedSize = CompressedFuncSize + encodeULEB128(CompressedFuncSize, Buf);
254 
255   LLVM_DEBUG(dbgs() << "  calculateSize orig: " << Function->Size << "\n");
256   LLVM_DEBUG(dbgs() << "  calculateSize  new: " << CompressedSize << "\n");
257 }
258 
259 // Override the default writeTo method so that we can (optionally) write the
260 // compressed version of the function.
261 void InputFunction::writeTo(uint8_t *Buf) const {
262   if (!File || !Config->CompressRelocations)
263     return InputChunk::writeTo(Buf);
264 
265   Buf += OutputOffset;
266   uint8_t *Orig = Buf;
267   (void)Orig;
268 
269   const uint8_t *SecStart = File->CodeSection->Content.data();
270   const uint8_t *FuncStart = SecStart + getInputSectionOffset();
271   const uint8_t *End = FuncStart + Function->Size;
272   uint32_t Count;
273   decodeULEB128(FuncStart, &Count);
274   FuncStart += Count;
275 
276   LLVM_DEBUG(dbgs() << "write func: " << getName() << "\n");
277   Buf += encodeULEB128(CompressedFuncSize, Buf);
278   const uint8_t *LastRelocEnd = FuncStart;
279   for (const WasmRelocation &Rel : Relocations) {
280     unsigned ChunkSize = (SecStart + Rel.Offset) - LastRelocEnd;
281     LLVM_DEBUG(dbgs() << "  write chunk: " << ChunkSize << "\n");
282     memcpy(Buf, LastRelocEnd, ChunkSize);
283     Buf += ChunkSize;
284     Buf += writeCompressedReloc(Buf, Rel, File->calcNewValue(Rel));
285     LastRelocEnd = SecStart + Rel.Offset + getRelocWidthPadded(Rel);
286   }
287 
288   unsigned ChunkSize = End - LastRelocEnd;
289   LLVM_DEBUG(dbgs() << "  write final chunk: " << ChunkSize << "\n");
290   memcpy(Buf, LastRelocEnd, ChunkSize);
291   LLVM_DEBUG(dbgs() << "  total: " << (Buf + ChunkSize - Orig) << "\n");
292 }
293