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