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