1 //===- OutputSections.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 "OutputSections.h"
11 
12 #include "Config.h"
13 #include "InputFiles.h"
14 #include "OutputSegment.h"
15 #include "SymbolTable.h"
16 #include "lld/Common/ErrorHandler.h"
17 #include "lld/Common/Memory.h"
18 #include "lld/Common/Threads.h"
19 #include "llvm/ADT/Twine.h"
20 #include "llvm/Support/LEB128.h"
21 
22 #define DEBUG_TYPE "lld"
23 
24 using namespace llvm;
25 using namespace llvm::wasm;
26 using namespace lld;
27 using namespace lld::wasm;
28 
29 enum class RelocEncoding {
30   Uleb128,
31   Sleb128,
32   I32,
33 };
34 
35 static StringRef sectionTypeToString(uint32_t SectionType) {
36   switch (SectionType) {
37   case WASM_SEC_CUSTOM:
38     return "CUSTOM";
39   case WASM_SEC_TYPE:
40     return "TYPE";
41   case WASM_SEC_IMPORT:
42     return "IMPORT";
43   case WASM_SEC_FUNCTION:
44     return "FUNCTION";
45   case WASM_SEC_TABLE:
46     return "TABLE";
47   case WASM_SEC_MEMORY:
48     return "MEMORY";
49   case WASM_SEC_GLOBAL:
50     return "GLOBAL";
51   case WASM_SEC_EXPORT:
52     return "EXPORT";
53   case WASM_SEC_START:
54     return "START";
55   case WASM_SEC_ELEM:
56     return "ELEM";
57   case WASM_SEC_CODE:
58     return "CODE";
59   case WASM_SEC_DATA:
60     return "DATA";
61   default:
62     fatal("invalid section type");
63   }
64 }
65 
66 std::string lld::toString(OutputSection *Section) {
67   std::string rtn = sectionTypeToString(Section->Type);
68   if (!Section->Name.empty())
69     rtn += "(" + Section->Name + ")";
70   return rtn;
71 }
72 
73 static void applyRelocation(uint8_t *Buf, const OutputRelocation &Reloc) {
74   DEBUG(dbgs() << "write reloc: type=" << Reloc.Reloc.Type
75                << " index=" << Reloc.Reloc.Index << " new=" << Reloc.NewIndex
76                << " value=" << Reloc.Value << " offset=" << Reloc.Reloc.Offset
77                << "\n");
78   Buf += Reloc.Reloc.Offset;
79   int64_t ExistingValue;
80   switch (Reloc.Reloc.Type) {
81   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
82   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
83     ExistingValue = decodeULEB128(Buf);
84     if (ExistingValue != Reloc.Reloc.Index) {
85       DEBUG(dbgs() << "existing value: " << decodeULEB128(Buf) << "\n");
86       assert(decodeULEB128(Buf) == Reloc.Reloc.Index);
87     }
88     LLVM_FALLTHROUGH;
89   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
90   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
91     encodeULEB128(Reloc.Value, Buf, 5);
92     break;
93   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
94     ExistingValue = decodeSLEB128(Buf);
95     if (ExistingValue != Reloc.Reloc.Index) {
96       DEBUG(dbgs() << "existing value: " << decodeSLEB128(Buf) << "\n");
97       assert(decodeSLEB128(Buf) == Reloc.Reloc.Index);
98     }
99     LLVM_FALLTHROUGH;
100   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
101     encodeSLEB128(static_cast<int32_t>(Reloc.Value), Buf, 5);
102     break;
103   case R_WEBASSEMBLY_TABLE_INDEX_I32:
104   case R_WEBASSEMBLY_MEMORY_ADDR_I32:
105     support::endian::write32<support::little>(Buf, Reloc.Value);
106     break;
107   default:
108     llvm_unreachable("unknown relocation type");
109   }
110 }
111 
112 static void applyRelocations(uint8_t *Buf,
113                              const std::vector<OutputRelocation> &Relocs) {
114   log("applyRelocations: count=" + Twine(Relocs.size()));
115   for (const OutputRelocation &Reloc : Relocs) {
116     applyRelocation(Buf, Reloc);
117   }
118 }
119 
120 // Relocations contain an index into the function, global or table index
121 // space of the input file.  This function takes a relocation and returns the
122 // relocated index (i.e. translates from the input index space to the output
123 // index space).
124 static uint32_t calcNewIndex(const ObjFile &File, const WasmRelocation &Reloc) {
125   switch (Reloc.Type) {
126   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
127     return File.relocateTypeIndex(Reloc.Index);
128   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
129     return File.relocateFunctionIndex(Reloc.Index);
130   case R_WEBASSEMBLY_TABLE_INDEX_I32:
131   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
132     return File.relocateTableIndex(Reloc.Index);
133   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
134   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
135   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
136   case R_WEBASSEMBLY_MEMORY_ADDR_I32:
137     return File.relocateGlobalIndex(Reloc.Index);
138   default:
139     llvm_unreachable("unknown relocation type");
140   }
141 }
142 
143 // Take a vector of relocations from an input file and create output
144 // relocations based on them. Calculates the updated index and offset for
145 // each relocation as well as the value to write out in the final binary.
146 static void calcRelocations(const ObjFile &File,
147                             ArrayRef<WasmRelocation> Relocs,
148                             std::vector<OutputRelocation> &OutputRelocs,
149                             int32_t OutputOffset) {
150   log("calcRelocations: " + File.getName() + " offset=" + Twine(OutputOffset));
151   for (const WasmRelocation &Reloc : Relocs) {
152     int64_t NewIndex = calcNewIndex(File, Reloc);
153     OutputRelocation NewReloc;
154     NewReloc.Reloc = Reloc;
155     NewReloc.Reloc.Offset += OutputOffset;
156     NewReloc.NewIndex = NewIndex;
157     DEBUG(dbgs() << "reloc: type=" << Reloc.Type << " index=" << Reloc.Index
158                  << " offset=" << Reloc.Offset << " new=" << NewIndex
159                  << " newOffset=" << NewReloc.Reloc.Offset << "\n");
160 
161     switch (Reloc.Type) {
162     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
163     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
164     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
165       NewReloc.Value = File.getRelocatedAddress(Reloc.Index);
166       if (NewReloc.Value != UINT32_MAX)
167         NewReloc.Value += Reloc.Addend;
168       break;
169     default:
170       NewReloc.Value = NewIndex;
171     }
172 
173     OutputRelocs.emplace_back(NewReloc);
174   }
175 }
176 
177 void OutputSection::createHeader(size_t BodySize) {
178   raw_string_ostream OS(Header);
179   debugWrite(OS.tell(),
180              "section type [" + Twine(sectionTypeToString(Type)) + "]");
181   writeUleb128(OS, Type, nullptr);
182   writeUleb128(OS, BodySize, "section size");
183   OS.flush();
184   log("createHeader: " + toString(this) + " body=" + Twine(BodySize) +
185       " total=" + Twine(getSize()));
186 }
187 
188 CodeSection::CodeSection(uint32_t NumFunctions, std::vector<ObjFile *> &Objs)
189     : OutputSection(WASM_SEC_CODE), InputObjects(Objs) {
190   raw_string_ostream OS(CodeSectionHeader);
191   writeUleb128(OS, NumFunctions, "function count");
192   OS.flush();
193   BodySize = CodeSectionHeader.size();
194 
195   for (ObjFile *File : InputObjects) {
196     if (!File->CodeSection)
197       continue;
198 
199     File->CodeOffset = BodySize;
200     ArrayRef<uint8_t> Content = File->CodeSection->Content;
201     unsigned HeaderSize = 0;
202     decodeULEB128(Content.data(), &HeaderSize);
203 
204     calcRelocations(*File, File->CodeSection->Relocations,
205                     File->CodeRelocations, BodySize - HeaderSize);
206 
207     size_t PayloadSize = Content.size() - HeaderSize;
208     BodySize += PayloadSize;
209   }
210 
211   createHeader(BodySize);
212 }
213 
214 void CodeSection::writeTo(uint8_t *Buf) {
215   log("writing " + toString(this));
216   log(" size=" + Twine(getSize()));
217   Buf += Offset;
218 
219   // Write section header
220   memcpy(Buf, Header.data(), Header.size());
221   Buf += Header.size();
222 
223   uint8_t *ContentsStart = Buf;
224 
225   // Write code section headers
226   memcpy(Buf, CodeSectionHeader.data(), CodeSectionHeader.size());
227   Buf += CodeSectionHeader.size();
228 
229   // Write code section bodies
230   parallelForEach(InputObjects, [ContentsStart](ObjFile *File) {
231     if (!File->CodeSection)
232       return;
233 
234     ArrayRef<uint8_t> Content(File->CodeSection->Content);
235 
236     // Payload doesn't include the initial header (function count)
237     unsigned HeaderSize = 0;
238     decodeULEB128(Content.data(), &HeaderSize);
239 
240     size_t PayloadSize = Content.size() - HeaderSize;
241     memcpy(ContentsStart + File->CodeOffset, Content.data() + HeaderSize,
242            PayloadSize);
243 
244     log("applying relocations for: " + File->getName());
245     if (File->CodeRelocations.size())
246       applyRelocations(ContentsStart, File->CodeRelocations);
247   });
248 }
249 
250 uint32_t CodeSection::numRelocations() const {
251   uint32_t Count = 0;
252   for (ObjFile *File : InputObjects)
253     Count += File->CodeRelocations.size();
254   return Count;
255 }
256 
257 void CodeSection::writeRelocations(raw_ostream &OS) const {
258   for (ObjFile *File : InputObjects)
259     for (const OutputRelocation &Reloc : File->CodeRelocations)
260       writeReloc(OS, Reloc);
261 }
262 
263 DataSection::DataSection(std::vector<OutputSegment *> &Segments)
264     : OutputSection(WASM_SEC_DATA), Segments(Segments) {
265   raw_string_ostream OS(DataSectionHeader);
266 
267   writeUleb128(OS, Segments.size(), "data segment count");
268   OS.flush();
269   BodySize = DataSectionHeader.size();
270 
271   for (OutputSegment *Segment : Segments) {
272     raw_string_ostream OS(Segment->Header);
273     writeUleb128(OS, 0, "memory index");
274     writeUleb128(OS, WASM_OPCODE_I32_CONST, "opcode:i32const");
275     writeSleb128(OS, Segment->StartVA, "memory offset");
276     writeUleb128(OS, WASM_OPCODE_END, "opcode:end");
277     writeUleb128(OS, Segment->Size, "segment size");
278     OS.flush();
279     Segment->setSectionOffset(BodySize);
280     BodySize += Segment->Header.size();
281     log("Data segment: size=" + Twine(Segment->Size));
282     for (const InputSegment *InputSeg : Segment->InputSegments) {
283       uint32_t InputOffset = InputSeg->getInputSectionOffset();
284       uint32_t OutputOffset = Segment->getSectionOffset() +
285                               Segment->Header.size() +
286                               InputSeg->getOutputSegmentOffset();
287       calcRelocations(*InputSeg->File, InputSeg->Relocations, Relocations,
288                       OutputOffset - InputOffset);
289     }
290     BodySize += Segment->Size;
291   }
292 
293   createHeader(BodySize);
294 }
295 
296 void DataSection::writeTo(uint8_t *Buf) {
297   log("writing " + toString(this) + " size=" + Twine(getSize()) +
298       " body=" + Twine(BodySize));
299   Buf += Offset;
300 
301   // Write section header
302   memcpy(Buf, Header.data(), Header.size());
303   Buf += Header.size();
304 
305   uint8_t *ContentsStart = Buf;
306 
307   // Write data section headers
308   memcpy(Buf, DataSectionHeader.data(), DataSectionHeader.size());
309 
310   parallelForEach(Segments, [ContentsStart](const OutputSegment *Segment) {
311     // Write data segment header
312     uint8_t *SegStart = ContentsStart + Segment->getSectionOffset();
313     memcpy(SegStart, Segment->Header.data(), Segment->Header.size());
314 
315     // Write segment data payload
316     for (const InputSegment *Input : Segment->InputSegments) {
317       ArrayRef<uint8_t> Content(Input->Segment->Data.Content);
318       memcpy(SegStart + Segment->Header.size() +
319                  Input->getOutputSegmentOffset(),
320              Content.data(), Content.size());
321     }
322   });
323 
324   applyRelocations(ContentsStart, Relocations);
325 }
326 
327 void DataSection::writeRelocations(raw_ostream &OS) const {
328   for (const OutputRelocation &Reloc : Relocations)
329     writeReloc(OS, Reloc);
330 }
331