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