1//===- Chunks.cpp ---------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "Chunks.h"
10#include "COFFLinkerContext.h"
11#include "InputFiles.h"
12#include "SymbolTable.h"
13#include "Symbols.h"
14#include "Writer.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/StringExtras.h"
17#include "llvm/ADT/Twine.h"
18#include "llvm/BinaryFormat/COFF.h"
19#include "llvm/Object/COFF.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/Endian.h"
22#include "llvm/Support/raw_ostream.h"
23#include <algorithm>
24#include <iterator>
25
26using namespace llvm;
27using namespace llvm::object;
28using namespace llvm::support::endian;
29using namespace llvm::COFF;
30using llvm::support::ulittle32_t;
31
32namespace lld::coff {
33
34SectionChunk::SectionChunk(ObjFile *f, const coff_section *h, Kind k)
35 : Chunk(k), file(f), header(h), repl(this) {
36 // Initialize relocs.
37 if (file)
38 setRelocs(file->getCOFFObj()->getRelocations(Sec: header));
39
40 // Initialize sectionName.
41 StringRef sectionName;
42 if (file) {
43 if (Expected<StringRef> e = file->getCOFFObj()->getSectionName(Sec: header))
44 sectionName = *e;
45 }
46 sectionNameData = sectionName.data();
47 sectionNameSize = sectionName.size();
48
49 setAlignment(header->getAlignment());
50
51 hasData = !(header->Characteristics & IMAGE_SCN_CNT_UNINITIALIZED_DATA);
52
53 // If linker GC is disabled, every chunk starts out alive. If linker GC is
54 // enabled, treat non-comdat sections as roots. Generally optimized object
55 // files will be built with -ffunction-sections or /Gy, so most things worth
56 // stripping will be in a comdat.
57 if (file)
58 live = !file->ctx.config.doGC || !isCOMDAT();
59 else
60 live = true;
61}
62
63// SectionChunk is one of the most frequently allocated classes, so it is
64// important to keep it as compact as possible. As of this writing, the number
65// below is the size of this class on x64 platforms.
66static_assert(sizeof(SectionChunk) <= 88, "SectionChunk grew unexpectedly");
67
68static void add16(uint8_t *p, int16_t v) { write16le(P: p, V: read16le(P: p) + v); }
69static void add32(uint8_t *p, int32_t v) { write32le(P: p, V: read32le(P: p) + v); }
70static void add64(uint8_t *p, int64_t v) { write64le(P: p, V: read64le(P: p) + v); }
71static void or16(uint8_t *p, uint16_t v) { write16le(P: p, V: read16le(P: p) | v); }
72static void or32(uint8_t *p, uint32_t v) { write32le(P: p, V: read32le(P: p) | v); }
73
74// Verify that given sections are appropriate targets for SECREL
75// relocations. This check is relaxed because unfortunately debug
76// sections have section-relative relocations against absolute symbols.
77static bool checkSecRel(const SectionChunk *sec, OutputSection *os) {
78 if (os)
79 return true;
80 if (sec->isCodeView())
81 return false;
82 error(msg: "SECREL relocation cannot be applied to absolute symbols");
83 return false;
84}
85
86static void applySecRel(const SectionChunk *sec, uint8_t *off,
87 OutputSection *os, uint64_t s) {
88 if (!checkSecRel(sec, os))
89 return;
90 uint64_t secRel = s - os->getRVA();
91 if (secRel > UINT32_MAX) {
92 error(msg: "overflow in SECREL relocation in section: " + sec->getSectionName());
93 return;
94 }
95 add32(p: off, v: secRel);
96}
97
98static void applySecIdx(uint8_t *off, OutputSection *os,
99 unsigned numOutputSections) {
100 // numOutputSections is the largest valid section index. Make sure that
101 // it fits in 16 bits.
102 assert(numOutputSections <= 0xffff && "size of outputSections is too big");
103
104 // Absolute symbol doesn't have section index, but section index relocation
105 // against absolute symbol should be resolved to one plus the last output
106 // section index. This is required for compatibility with MSVC.
107 if (os)
108 add16(p: off, v: os->sectionIndex);
109 else
110 add16(p: off, v: numOutputSections + 1);
111}
112
113void SectionChunk::applyRelX64(uint8_t *off, uint16_t type, OutputSection *os,
114 uint64_t s, uint64_t p,
115 uint64_t imageBase) const {
116 switch (type) {
117 case IMAGE_REL_AMD64_ADDR32:
118 add32(p: off, v: s + imageBase);
119 break;
120 case IMAGE_REL_AMD64_ADDR64:
121 add64(p: off, v: s + imageBase);
122 break;
123 case IMAGE_REL_AMD64_ADDR32NB: add32(p: off, v: s); break;
124 case IMAGE_REL_AMD64_REL32: add32(p: off, v: s - p - 4); break;
125 case IMAGE_REL_AMD64_REL32_1: add32(p: off, v: s - p - 5); break;
126 case IMAGE_REL_AMD64_REL32_2: add32(p: off, v: s - p - 6); break;
127 case IMAGE_REL_AMD64_REL32_3: add32(p: off, v: s - p - 7); break;
128 case IMAGE_REL_AMD64_REL32_4: add32(p: off, v: s - p - 8); break;
129 case IMAGE_REL_AMD64_REL32_5: add32(p: off, v: s - p - 9); break;
130 case IMAGE_REL_AMD64_SECTION:
131 applySecIdx(off, os, numOutputSections: file->ctx.outputSections.size());
132 break;
133 case IMAGE_REL_AMD64_SECREL: applySecRel(sec: this, off, os, s); break;
134 default:
135 error(msg: "unsupported relocation type 0x" + Twine::utohexstr(Val: type) + " in " +
136 toString(file));
137 }
138}
139
140void SectionChunk::applyRelX86(uint8_t *off, uint16_t type, OutputSection *os,
141 uint64_t s, uint64_t p,
142 uint64_t imageBase) const {
143 switch (type) {
144 case IMAGE_REL_I386_ABSOLUTE: break;
145 case IMAGE_REL_I386_DIR32:
146 add32(p: off, v: s + imageBase);
147 break;
148 case IMAGE_REL_I386_DIR32NB: add32(p: off, v: s); break;
149 case IMAGE_REL_I386_REL32: add32(p: off, v: s - p - 4); break;
150 case IMAGE_REL_I386_SECTION:
151 applySecIdx(off, os, numOutputSections: file->ctx.outputSections.size());
152 break;
153 case IMAGE_REL_I386_SECREL: applySecRel(sec: this, off, os, s); break;
154 default:
155 error(msg: "unsupported relocation type 0x" + Twine::utohexstr(Val: type) + " in " +
156 toString(file));
157 }
158}
159
160static void applyMOV(uint8_t *off, uint16_t v) {
161 write16le(P: off, V: (read16le(P: off) & 0xfbf0) | ((v & 0x800) >> 1) | ((v >> 12) & 0xf));
162 write16le(P: off + 2, V: (read16le(P: off + 2) & 0x8f00) | ((v & 0x700) << 4) | (v & 0xff));
163}
164
165static uint16_t readMOV(uint8_t *off, bool movt) {
166 uint16_t op1 = read16le(P: off);
167 if ((op1 & 0xfbf0) != (movt ? 0xf2c0 : 0xf240))
168 error(msg: "unexpected instruction in " + Twine(movt ? "MOVT" : "MOVW") +
169 " instruction in MOV32T relocation");
170 uint16_t op2 = read16le(P: off + 2);
171 if ((op2 & 0x8000) != 0)
172 error(msg: "unexpected instruction in " + Twine(movt ? "MOVT" : "MOVW") +
173 " instruction in MOV32T relocation");
174 return (op2 & 0x00ff) | ((op2 >> 4) & 0x0700) | ((op1 << 1) & 0x0800) |
175 ((op1 & 0x000f) << 12);
176}
177
178void applyMOV32T(uint8_t *off, uint32_t v) {
179 uint16_t immW = readMOV(off, movt: false); // read MOVW operand
180 uint16_t immT = readMOV(off: off + 4, movt: true); // read MOVT operand
181 uint32_t imm = immW | (immT << 16);
182 v += imm; // add the immediate offset
183 applyMOV(off, v); // set MOVW operand
184 applyMOV(off: off + 4, v: v >> 16); // set MOVT operand
185}
186
187static void applyBranch20T(uint8_t *off, int32_t v) {
188 if (!isInt<21>(x: v))
189 error(msg: "relocation out of range");
190 uint32_t s = v < 0 ? 1 : 0;
191 uint32_t j1 = (v >> 19) & 1;
192 uint32_t j2 = (v >> 18) & 1;
193 or16(p: off, v: (s << 10) | ((v >> 12) & 0x3f));
194 or16(p: off + 2, v: (j1 << 13) | (j2 << 11) | ((v >> 1) & 0x7ff));
195}
196
197void applyBranch24T(uint8_t *off, int32_t v) {
198 if (!isInt<25>(x: v))
199 error(msg: "relocation out of range");
200 uint32_t s = v < 0 ? 1 : 0;
201 uint32_t j1 = ((~v >> 23) & 1) ^ s;
202 uint32_t j2 = ((~v >> 22) & 1) ^ s;
203 or16(p: off, v: (s << 10) | ((v >> 12) & 0x3ff));
204 // Clear out the J1 and J2 bits which may be set.
205 write16le(P: off + 2, V: (read16le(P: off + 2) & 0xd000) | (j1 << 13) | (j2 << 11) | ((v >> 1) & 0x7ff));
206}
207
208void SectionChunk::applyRelARM(uint8_t *off, uint16_t type, OutputSection *os,
209 uint64_t s, uint64_t p,
210 uint64_t imageBase) const {
211 // Pointer to thumb code must have the LSB set.
212 uint64_t sx = s;
213 if (os && (os->header.Characteristics & IMAGE_SCN_MEM_EXECUTE))
214 sx |= 1;
215 switch (type) {
216 case IMAGE_REL_ARM_ADDR32:
217 add32(p: off, v: sx + imageBase);
218 break;
219 case IMAGE_REL_ARM_ADDR32NB: add32(p: off, v: sx); break;
220 case IMAGE_REL_ARM_MOV32T:
221 applyMOV32T(off, v: sx + imageBase);
222 break;
223 case IMAGE_REL_ARM_BRANCH20T: applyBranch20T(off, v: sx - p - 4); break;
224 case IMAGE_REL_ARM_BRANCH24T: applyBranch24T(off, v: sx - p - 4); break;
225 case IMAGE_REL_ARM_BLX23T: applyBranch24T(off, v: sx - p - 4); break;
226 case IMAGE_REL_ARM_SECTION:
227 applySecIdx(off, os, numOutputSections: file->ctx.outputSections.size());
228 break;
229 case IMAGE_REL_ARM_SECREL: applySecRel(sec: this, off, os, s); break;
230 case IMAGE_REL_ARM_REL32: add32(p: off, v: sx - p - 4); break;
231 default:
232 error(msg: "unsupported relocation type 0x" + Twine::utohexstr(Val: type) + " in " +
233 toString(file));
234 }
235}
236
237// Interpret the existing immediate value as a byte offset to the
238// target symbol, then update the instruction with the immediate as
239// the page offset from the current instruction to the target.
240void applyArm64Addr(uint8_t *off, uint64_t s, uint64_t p, int shift) {
241 uint32_t orig = read32le(P: off);
242 int64_t imm =
243 SignExtend64<21>(x: ((orig >> 29) & 0x3) | ((orig >> 3) & 0x1FFFFC));
244 s += imm;
245 imm = (s >> shift) - (p >> shift);
246 uint32_t immLo = (imm & 0x3) << 29;
247 uint32_t immHi = (imm & 0x1FFFFC) << 3;
248 uint64_t mask = (0x3 << 29) | (0x1FFFFC << 3);
249 write32le(P: off, V: (orig & ~mask) | immLo | immHi);
250}
251
252// Update the immediate field in a AARCH64 ldr, str, and add instruction.
253// Optionally limit the range of the written immediate by one or more bits
254// (rangeLimit).
255void applyArm64Imm(uint8_t *off, uint64_t imm, uint32_t rangeLimit) {
256 uint32_t orig = read32le(P: off);
257 imm += (orig >> 10) & 0xFFF;
258 orig &= ~(0xFFF << 10);
259 write32le(P: off, V: orig | ((imm & (0xFFF >> rangeLimit)) << 10));
260}
261
262// Add the 12 bit page offset to the existing immediate.
263// Ldr/str instructions store the opcode immediate scaled
264// by the load/store size (giving a larger range for larger
265// loads/stores). The immediate is always (both before and after
266// fixing up the relocation) stored scaled similarly.
267// Even if larger loads/stores have a larger range, limit the
268// effective offset to 12 bit, since it is intended to be a
269// page offset.
270static void applyArm64Ldr(uint8_t *off, uint64_t imm) {
271 uint32_t orig = read32le(P: off);
272 uint32_t size = orig >> 30;
273 // 0x04000000 indicates SIMD/FP registers
274 // 0x00800000 indicates 128 bit
275 if ((orig & 0x4800000) == 0x4800000)
276 size += 4;
277 if ((imm & ((1 << size) - 1)) != 0)
278 error(msg: "misaligned ldr/str offset");
279 applyArm64Imm(off, imm: imm >> size, rangeLimit: size);
280}
281
282static void applySecRelLow12A(const SectionChunk *sec, uint8_t *off,
283 OutputSection *os, uint64_t s) {
284 if (checkSecRel(sec, os))
285 applyArm64Imm(off, imm: (s - os->getRVA()) & 0xfff, rangeLimit: 0);
286}
287
288static void applySecRelHigh12A(const SectionChunk *sec, uint8_t *off,
289 OutputSection *os, uint64_t s) {
290 if (!checkSecRel(sec, os))
291 return;
292 uint64_t secRel = (s - os->getRVA()) >> 12;
293 if (0xfff < secRel) {
294 error(msg: "overflow in SECREL_HIGH12A relocation in section: " +
295 sec->getSectionName());
296 return;
297 }
298 applyArm64Imm(off, imm: secRel & 0xfff, rangeLimit: 0);
299}
300
301static void applySecRelLdr(const SectionChunk *sec, uint8_t *off,
302 OutputSection *os, uint64_t s) {
303 if (checkSecRel(sec, os))
304 applyArm64Ldr(off, imm: (s - os->getRVA()) & 0xfff);
305}
306
307void applyArm64Branch26(uint8_t *off, int64_t v) {
308 if (!isInt<28>(x: v))
309 error(msg: "relocation out of range");
310 or32(p: off, v: (v & 0x0FFFFFFC) >> 2);
311}
312
313static void applyArm64Branch19(uint8_t *off, int64_t v) {
314 if (!isInt<21>(x: v))
315 error(msg: "relocation out of range");
316 or32(p: off, v: (v & 0x001FFFFC) << 3);
317}
318
319static void applyArm64Branch14(uint8_t *off, int64_t v) {
320 if (!isInt<16>(x: v))
321 error(msg: "relocation out of range");
322 or32(p: off, v: (v & 0x0000FFFC) << 3);
323}
324
325void SectionChunk::applyRelARM64(uint8_t *off, uint16_t type, OutputSection *os,
326 uint64_t s, uint64_t p,
327 uint64_t imageBase) const {
328 switch (type) {
329 case IMAGE_REL_ARM64_PAGEBASE_REL21: applyArm64Addr(off, s, p, shift: 12); break;
330 case IMAGE_REL_ARM64_REL21: applyArm64Addr(off, s, p, shift: 0); break;
331 case IMAGE_REL_ARM64_PAGEOFFSET_12A: applyArm64Imm(off, imm: s & 0xfff, rangeLimit: 0); break;
332 case IMAGE_REL_ARM64_PAGEOFFSET_12L: applyArm64Ldr(off, imm: s & 0xfff); break;
333 case IMAGE_REL_ARM64_BRANCH26: applyArm64Branch26(off, v: s - p); break;
334 case IMAGE_REL_ARM64_BRANCH19: applyArm64Branch19(off, v: s - p); break;
335 case IMAGE_REL_ARM64_BRANCH14: applyArm64Branch14(off, v: s - p); break;
336 case IMAGE_REL_ARM64_ADDR32:
337 add32(p: off, v: s + imageBase);
338 break;
339 case IMAGE_REL_ARM64_ADDR32NB: add32(p: off, v: s); break;
340 case IMAGE_REL_ARM64_ADDR64:
341 add64(p: off, v: s + imageBase);
342 break;
343 case IMAGE_REL_ARM64_SECREL: applySecRel(sec: this, off, os, s); break;
344 case IMAGE_REL_ARM64_SECREL_LOW12A: applySecRelLow12A(sec: this, off, os, s); break;
345 case IMAGE_REL_ARM64_SECREL_HIGH12A: applySecRelHigh12A(sec: this, off, os, s); break;
346 case IMAGE_REL_ARM64_SECREL_LOW12L: applySecRelLdr(sec: this, off, os, s); break;
347 case IMAGE_REL_ARM64_SECTION:
348 applySecIdx(off, os, numOutputSections: file->ctx.outputSections.size());
349 break;
350 case IMAGE_REL_ARM64_REL32: add32(p: off, v: s - p - 4); break;
351 default:
352 error(msg: "unsupported relocation type 0x" + Twine::utohexstr(Val: type) + " in " +
353 toString(file));
354 }
355}
356
357static void maybeReportRelocationToDiscarded(const SectionChunk *fromChunk,
358 Defined *sym,
359 const coff_relocation &rel,
360 bool isMinGW) {
361 // Don't report these errors when the relocation comes from a debug info
362 // section or in mingw mode. MinGW mode object files (built by GCC) can
363 // have leftover sections with relocations against discarded comdat
364 // sections. Such sections are left as is, with relocations untouched.
365 if (fromChunk->isCodeView() || fromChunk->isDWARF() || isMinGW)
366 return;
367
368 // Get the name of the symbol. If it's null, it was discarded early, so we
369 // have to go back to the object file.
370 ObjFile *file = fromChunk->file;
371 StringRef name;
372 if (sym) {
373 name = sym->getName();
374 } else {
375 COFFSymbolRef coffSym =
376 check(e: file->getCOFFObj()->getSymbol(index: rel.SymbolTableIndex));
377 name = check(e: file->getCOFFObj()->getSymbolName(Symbol: coffSym));
378 }
379
380 std::vector<std::string> symbolLocations =
381 getSymbolLocations(file, symIndex: rel.SymbolTableIndex);
382
383 std::string out;
384 llvm::raw_string_ostream os(out);
385 os << "relocation against symbol in discarded section: " + name;
386 for (const std::string &s : symbolLocations)
387 os << s;
388 error(msg: os.str());
389}
390
391void SectionChunk::writeTo(uint8_t *buf) const {
392 if (!hasData)
393 return;
394 // Copy section contents from source object file to output file.
395 ArrayRef<uint8_t> a = getContents();
396 if (!a.empty())
397 memcpy(dest: buf, src: a.data(), n: a.size());
398
399 // Apply relocations.
400 size_t inputSize = getSize();
401 for (const coff_relocation &rel : getRelocs()) {
402 // Check for an invalid relocation offset. This check isn't perfect, because
403 // we don't have the relocation size, which is only known after checking the
404 // machine and relocation type. As a result, a relocation may overwrite the
405 // beginning of the following input section.
406 if (rel.VirtualAddress >= inputSize) {
407 error(msg: "relocation points beyond the end of its parent section");
408 continue;
409 }
410
411 applyRelocation(off: buf + rel.VirtualAddress, rel);
412 }
413
414 // Write the offset to EC entry thunk preceding section contents. The low bit
415 // is always set, so it's effectively an offset from the last byte of the
416 // offset.
417 if (Defined *entryThunk = getEntryThunk())
418 write32le(P: buf - sizeof(uint32_t), V: entryThunk->getRVA() - rva + 1);
419}
420
421void SectionChunk::applyRelocation(uint8_t *off,
422 const coff_relocation &rel) const {
423 auto *sym = dyn_cast_or_null<Defined>(Val: file->getSymbol(symbolIndex: rel.SymbolTableIndex));
424
425 // Get the output section of the symbol for this relocation. The output
426 // section is needed to compute SECREL and SECTION relocations used in debug
427 // info.
428 Chunk *c = sym ? sym->getChunk() : nullptr;
429 OutputSection *os = c ? file->ctx.getOutputSection(c) : nullptr;
430
431 // Skip the relocation if it refers to a discarded section, and diagnose it
432 // as an error if appropriate. If a symbol was discarded early, it may be
433 // null. If it was discarded late, the output section will be null, unless
434 // it was an absolute or synthetic symbol.
435 if (!sym ||
436 (!os && !isa<DefinedAbsolute>(Val: sym) && !isa<DefinedSynthetic>(Val: sym))) {
437 maybeReportRelocationToDiscarded(fromChunk: this, sym, rel, isMinGW: file->ctx.config.mingw);
438 return;
439 }
440
441 uint64_t s = sym->getRVA();
442
443 // Compute the RVA of the relocation for relative relocations.
444 uint64_t p = rva + rel.VirtualAddress;
445 uint64_t imageBase = file->ctx.config.imageBase;
446 switch (getArch()) {
447 case Triple::x86_64:
448 applyRelX64(off, type: rel.Type, os, s, p, imageBase);
449 break;
450 case Triple::x86:
451 applyRelX86(off, type: rel.Type, os, s, p, imageBase);
452 break;
453 case Triple::thumb:
454 applyRelARM(off, type: rel.Type, os, s, p, imageBase);
455 break;
456 case Triple::aarch64:
457 applyRelARM64(off, type: rel.Type, os, s, p, imageBase);
458 break;
459 default:
460 llvm_unreachable("unknown machine type");
461 }
462}
463
464// Defend against unsorted relocations. This may be overly conservative.
465void SectionChunk::sortRelocations() {
466 auto cmpByVa = [](const coff_relocation &l, const coff_relocation &r) {
467 return l.VirtualAddress < r.VirtualAddress;
468 };
469 if (llvm::is_sorted(Range: getRelocs(), C: cmpByVa))
470 return;
471 warn(msg: "some relocations in " + file->getName() + " are not sorted");
472 MutableArrayRef<coff_relocation> newRelocs(
473 bAlloc().Allocate<coff_relocation>(Num: relocsSize), relocsSize);
474 memcpy(dest: newRelocs.data(), src: relocsData, n: relocsSize * sizeof(coff_relocation));
475 llvm::sort(C&: newRelocs, Comp: cmpByVa);
476 setRelocs(newRelocs);
477}
478
479// Similar to writeTo, but suitable for relocating a subsection of the overall
480// section.
481void SectionChunk::writeAndRelocateSubsection(ArrayRef<uint8_t> sec,
482 ArrayRef<uint8_t> subsec,
483 uint32_t &nextRelocIndex,
484 uint8_t *buf) const {
485 assert(!subsec.empty() && !sec.empty());
486 assert(sec.begin() <= subsec.begin() && subsec.end() <= sec.end() &&
487 "subsection is not part of this section");
488 size_t vaBegin = std::distance(first: sec.begin(), last: subsec.begin());
489 size_t vaEnd = std::distance(first: sec.begin(), last: subsec.end());
490 memcpy(dest: buf, src: subsec.data(), n: subsec.size());
491 for (; nextRelocIndex < relocsSize; ++nextRelocIndex) {
492 const coff_relocation &rel = relocsData[nextRelocIndex];
493 // Only apply relocations that apply to this subsection. These checks
494 // assume that all subsections completely contain their relocations.
495 // Relocations must not straddle the beginning or end of a subsection.
496 if (rel.VirtualAddress < vaBegin)
497 continue;
498 if (rel.VirtualAddress + 1 >= vaEnd)
499 break;
500 applyRelocation(off: &buf[rel.VirtualAddress - vaBegin], rel);
501 }
502}
503
504void SectionChunk::addAssociative(SectionChunk *child) {
505 // Insert the child section into the list of associated children. Keep the
506 // list ordered by section name so that ICF does not depend on section order.
507 assert(child->assocChildren == nullptr &&
508 "associated sections cannot have their own associated children");
509 SectionChunk *prev = this;
510 SectionChunk *next = assocChildren;
511 for (; next != nullptr; prev = next, next = next->assocChildren) {
512 if (next->getSectionName() <= child->getSectionName())
513 break;
514 }
515
516 // Insert child between prev and next.
517 assert(prev->assocChildren == next);
518 prev->assocChildren = child;
519 child->assocChildren = next;
520}
521
522static uint8_t getBaserelType(const coff_relocation &rel,
523 Triple::ArchType arch) {
524 switch (arch) {
525 case Triple::x86_64:
526 if (rel.Type == IMAGE_REL_AMD64_ADDR64)
527 return IMAGE_REL_BASED_DIR64;
528 if (rel.Type == IMAGE_REL_AMD64_ADDR32)
529 return IMAGE_REL_BASED_HIGHLOW;
530 return IMAGE_REL_BASED_ABSOLUTE;
531 case Triple::x86:
532 if (rel.Type == IMAGE_REL_I386_DIR32)
533 return IMAGE_REL_BASED_HIGHLOW;
534 return IMAGE_REL_BASED_ABSOLUTE;
535 case Triple::thumb:
536 if (rel.Type == IMAGE_REL_ARM_ADDR32)
537 return IMAGE_REL_BASED_HIGHLOW;
538 if (rel.Type == IMAGE_REL_ARM_MOV32T)
539 return IMAGE_REL_BASED_ARM_MOV32T;
540 return IMAGE_REL_BASED_ABSOLUTE;
541 case Triple::aarch64:
542 if (rel.Type == IMAGE_REL_ARM64_ADDR64)
543 return IMAGE_REL_BASED_DIR64;
544 return IMAGE_REL_BASED_ABSOLUTE;
545 default:
546 llvm_unreachable("unknown machine type");
547 }
548}
549
550// Windows-specific.
551// Collect all locations that contain absolute addresses, which need to be
552// fixed by the loader if load-time relocation is needed.
553// Only called when base relocation is enabled.
554void SectionChunk::getBaserels(std::vector<Baserel> *res) {
555 for (const coff_relocation &rel : getRelocs()) {
556 uint8_t ty = getBaserelType(rel, arch: getArch());
557 if (ty == IMAGE_REL_BASED_ABSOLUTE)
558 continue;
559 Symbol *target = file->getSymbol(symbolIndex: rel.SymbolTableIndex);
560 if (!target || isa<DefinedAbsolute>(Val: target))
561 continue;
562 res->emplace_back(args: rva + rel.VirtualAddress, args&: ty);
563 }
564}
565
566// MinGW specific.
567// Check whether a static relocation of type Type can be deferred and
568// handled at runtime as a pseudo relocation (for references to a module
569// local variable, which turned out to actually need to be imported from
570// another DLL) This returns the size the relocation is supposed to update,
571// in bits, or 0 if the relocation cannot be handled as a runtime pseudo
572// relocation.
573static int getRuntimePseudoRelocSize(uint16_t type,
574 llvm::COFF::MachineTypes machine) {
575 // Relocations that either contain an absolute address, or a plain
576 // relative offset, since the runtime pseudo reloc implementation
577 // adds 8/16/32/64 bit values to a memory address.
578 //
579 // Given a pseudo relocation entry,
580 //
581 // typedef struct {
582 // DWORD sym;
583 // DWORD target;
584 // DWORD flags;
585 // } runtime_pseudo_reloc_item_v2;
586 //
587 // the runtime relocation performs this adjustment:
588 // *(base + .target) += *(base + .sym) - (base + .sym)
589 //
590 // This works for both absolute addresses (IMAGE_REL_*_ADDR32/64,
591 // IMAGE_REL_I386_DIR32, where the memory location initially contains
592 // the address of the IAT slot, and for relative addresses (IMAGE_REL*_REL32),
593 // where the memory location originally contains the relative offset to the
594 // IAT slot.
595 //
596 // This requires the target address to be writable, either directly out of
597 // the image, or temporarily changed at runtime with VirtualProtect.
598 // Since this only operates on direct address values, it doesn't work for
599 // ARM/ARM64 relocations, other than the plain ADDR32/ADDR64 relocations.
600 switch (machine) {
601 case AMD64:
602 switch (type) {
603 case IMAGE_REL_AMD64_ADDR64:
604 return 64;
605 case IMAGE_REL_AMD64_ADDR32:
606 case IMAGE_REL_AMD64_REL32:
607 case IMAGE_REL_AMD64_REL32_1:
608 case IMAGE_REL_AMD64_REL32_2:
609 case IMAGE_REL_AMD64_REL32_3:
610 case IMAGE_REL_AMD64_REL32_4:
611 case IMAGE_REL_AMD64_REL32_5:
612 return 32;
613 default:
614 return 0;
615 }
616 case I386:
617 switch (type) {
618 case IMAGE_REL_I386_DIR32:
619 case IMAGE_REL_I386_REL32:
620 return 32;
621 default:
622 return 0;
623 }
624 case ARMNT:
625 switch (type) {
626 case IMAGE_REL_ARM_ADDR32:
627 return 32;
628 default:
629 return 0;
630 }
631 case ARM64:
632 switch (type) {
633 case IMAGE_REL_ARM64_ADDR64:
634 return 64;
635 case IMAGE_REL_ARM64_ADDR32:
636 return 32;
637 default:
638 return 0;
639 }
640 default:
641 llvm_unreachable("unknown machine type");
642 }
643}
644
645// MinGW specific.
646// Append information to the provided vector about all relocations that
647// need to be handled at runtime as runtime pseudo relocations (references
648// to a module local variable, which turned out to actually need to be
649// imported from another DLL).
650void SectionChunk::getRuntimePseudoRelocs(
651 std::vector<RuntimePseudoReloc> &res) {
652 for (const coff_relocation &rel : getRelocs()) {
653 auto *target =
654 dyn_cast_or_null<Defined>(Val: file->getSymbol(symbolIndex: rel.SymbolTableIndex));
655 if (!target || !target->isRuntimePseudoReloc)
656 continue;
657 // If the target doesn't have a chunk allocated, it may be a
658 // DefinedImportData symbol which ended up unnecessary after GC.
659 // Normally we wouldn't eliminate section chunks that are referenced, but
660 // references within DWARF sections don't count for keeping section chunks
661 // alive. Thus such dangling references in DWARF sections are expected.
662 if (!target->getChunk())
663 continue;
664 int sizeInBits =
665 getRuntimePseudoRelocSize(type: rel.Type, machine: file->ctx.config.machine);
666 if (sizeInBits == 0) {
667 error(msg: "unable to automatically import from " + target->getName() +
668 " with relocation type " +
669 file->getCOFFObj()->getRelocationTypeName(Type: rel.Type) + " in " +
670 toString(file));
671 continue;
672 }
673 int addressSizeInBits = file->ctx.config.is64() ? 64 : 32;
674 if (sizeInBits < addressSizeInBits) {
675 warn(msg: "runtime pseudo relocation in " + toString(file) + " against " +
676 "symbol " + target->getName() + " is too narrow (only " +
677 Twine(sizeInBits) + " bits wide); this can fail at runtime " +
678 "depending on memory layout");
679 }
680 // sizeInBits is used to initialize the Flags field; currently no
681 // other flags are defined.
682 res.emplace_back(args&: target, args: this, args: rel.VirtualAddress, args&: sizeInBits);
683 }
684}
685
686bool SectionChunk::isCOMDAT() const {
687 return header->Characteristics & IMAGE_SCN_LNK_COMDAT;
688}
689
690void SectionChunk::printDiscardedMessage() const {
691 // Removed by dead-stripping. If it's removed by ICF, ICF already
692 // printed out the name, so don't repeat that here.
693 if (sym && this == repl)
694 log(msg: "Discarded " + sym->getName());
695}
696
697StringRef SectionChunk::getDebugName() const {
698 if (sym)
699 return sym->getName();
700 return "";
701}
702
703ArrayRef<uint8_t> SectionChunk::getContents() const {
704 ArrayRef<uint8_t> a;
705 cantFail(Err: file->getCOFFObj()->getSectionContents(Sec: header, Res&: a));
706 return a;
707}
708
709ArrayRef<uint8_t> SectionChunk::consumeDebugMagic() {
710 assert(isCodeView());
711 return consumeDebugMagic(data: getContents(), sectionName: getSectionName());
712}
713
714ArrayRef<uint8_t> SectionChunk::consumeDebugMagic(ArrayRef<uint8_t> data,
715 StringRef sectionName) {
716 if (data.empty())
717 return {};
718
719 // First 4 bytes are section magic.
720 if (data.size() < 4)
721 fatal(msg: "the section is too short: " + sectionName);
722
723 if (!sectionName.starts_with(Prefix: ".debug$"))
724 fatal(msg: "invalid section: " + sectionName);
725
726 uint32_t magic = support::endian::read32le(P: data.data());
727 uint32_t expectedMagic = sectionName == ".debug$H"
728 ? DEBUG_HASHES_SECTION_MAGIC
729 : DEBUG_SECTION_MAGIC;
730 if (magic != expectedMagic) {
731 warn(msg: "ignoring section " + sectionName + " with unrecognized magic 0x" +
732 utohexstr(X: magic));
733 return {};
734 }
735 return data.slice(N: 4);
736}
737
738SectionChunk *SectionChunk::findByName(ArrayRef<SectionChunk *> sections,
739 StringRef name) {
740 for (SectionChunk *c : sections)
741 if (c->getSectionName() == name)
742 return c;
743 return nullptr;
744}
745
746void SectionChunk::replace(SectionChunk *other) {
747 p2Align = std::max(a: p2Align, b: other->p2Align);
748 other->repl = repl;
749 other->live = false;
750}
751
752uint32_t SectionChunk::getSectionNumber() const {
753 DataRefImpl r;
754 r.p = reinterpret_cast<uintptr_t>(header);
755 SectionRef s(r, file->getCOFFObj());
756 return s.getIndex() + 1;
757}
758
759CommonChunk::CommonChunk(const COFFSymbolRef s) : sym(s) {
760 // The value of a common symbol is its size. Align all common symbols smaller
761 // than 32 bytes naturally, i.e. round the size up to the next power of two.
762 // This is what MSVC link.exe does.
763 setAlignment(std::min(a: 32U, b: uint32_t(PowerOf2Ceil(A: sym.getValue()))));
764 hasData = false;
765}
766
767uint32_t CommonChunk::getOutputCharacteristics() const {
768 return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
769 IMAGE_SCN_MEM_WRITE;
770}
771
772void StringChunk::writeTo(uint8_t *buf) const {
773 memcpy(dest: buf, src: str.data(), n: str.size());
774 buf[str.size()] = '\0';
775}
776
777ImportThunkChunkX64::ImportThunkChunkX64(COFFLinkerContext &ctx, Defined *s)
778 : ImportThunkChunk(ctx, s) {
779 // Intel Optimization Manual says that all branch targets
780 // should be 16-byte aligned. MSVC linker does this too.
781 setAlignment(16);
782}
783
784void ImportThunkChunkX64::writeTo(uint8_t *buf) const {
785 memcpy(dest: buf, src: importThunkX86, n: sizeof(importThunkX86));
786 // The first two bytes is a JMP instruction. Fill its operand.
787 write32le(P: buf + 2, V: impSymbol->getRVA() - rva - getSize());
788}
789
790void ImportThunkChunkX86::getBaserels(std::vector<Baserel> *res) {
791 res->emplace_back(args: getRVA() + 2, args&: ctx.config.machine);
792}
793
794void ImportThunkChunkX86::writeTo(uint8_t *buf) const {
795 memcpy(dest: buf, src: importThunkX86, n: sizeof(importThunkX86));
796 // The first two bytes is a JMP instruction. Fill its operand.
797 write32le(P: buf + 2, V: impSymbol->getRVA() + ctx.config.imageBase);
798}
799
800void ImportThunkChunkARM::getBaserels(std::vector<Baserel> *res) {
801 res->emplace_back(args: getRVA(), args: IMAGE_REL_BASED_ARM_MOV32T);
802}
803
804void ImportThunkChunkARM::writeTo(uint8_t *buf) const {
805 memcpy(dest: buf, src: importThunkARM, n: sizeof(importThunkARM));
806 // Fix mov.w and mov.t operands.
807 applyMOV32T(off: buf, v: impSymbol->getRVA() + ctx.config.imageBase);
808}
809
810void ImportThunkChunkARM64::writeTo(uint8_t *buf) const {
811 int64_t off = impSymbol->getRVA() & 0xfff;
812 memcpy(dest: buf, src: importThunkARM64, n: sizeof(importThunkARM64));
813 applyArm64Addr(off: buf, s: impSymbol->getRVA(), p: rva, shift: 12);
814 applyArm64Ldr(off: buf + 4, imm: off);
815}
816
817// A Thumb2, PIC, non-interworking range extension thunk.
818const uint8_t armThunk[] = {
819 0x40, 0xf2, 0x00, 0x0c, // P: movw ip,:lower16:S - (P + (L1-P) + 4)
820 0xc0, 0xf2, 0x00, 0x0c, // movt ip,:upper16:S - (P + (L1-P) + 4)
821 0xe7, 0x44, // L1: add pc, ip
822};
823
824size_t RangeExtensionThunkARM::getSize() const {
825 assert(ctx.config.machine == ARMNT);
826 (void)&ctx;
827 return sizeof(armThunk);
828}
829
830void RangeExtensionThunkARM::writeTo(uint8_t *buf) const {
831 assert(ctx.config.machine == ARMNT);
832 uint64_t offset = target->getRVA() - rva - 12;
833 memcpy(dest: buf, src: armThunk, n: sizeof(armThunk));
834 applyMOV32T(off: buf, v: uint32_t(offset));
835}
836
837// A position independent ARM64 adrp+add thunk, with a maximum range of
838// +/- 4 GB, which is enough for any PE-COFF.
839const uint8_t arm64Thunk[] = {
840 0x10, 0x00, 0x00, 0x90, // adrp x16, Dest
841 0x10, 0x02, 0x00, 0x91, // add x16, x16, :lo12:Dest
842 0x00, 0x02, 0x1f, 0xd6, // br x16
843};
844
845size_t RangeExtensionThunkARM64::getSize() const {
846 assert(ctx.config.machine == ARM64);
847 (void)&ctx;
848 return sizeof(arm64Thunk);
849}
850
851void RangeExtensionThunkARM64::writeTo(uint8_t *buf) const {
852 assert(ctx.config.machine == ARM64);
853 memcpy(dest: buf, src: arm64Thunk, n: sizeof(arm64Thunk));
854 applyArm64Addr(off: buf + 0, s: target->getRVA(), p: rva, shift: 12);
855 applyArm64Imm(off: buf + 4, imm: target->getRVA() & 0xfff, rangeLimit: 0);
856}
857
858LocalImportChunk::LocalImportChunk(COFFLinkerContext &c, Defined *s)
859 : sym(s), ctx(c) {
860 setAlignment(ctx.config.wordsize);
861}
862
863void LocalImportChunk::getBaserels(std::vector<Baserel> *res) {
864 res->emplace_back(args: getRVA(), args&: ctx.config.machine);
865}
866
867size_t LocalImportChunk::getSize() const { return ctx.config.wordsize; }
868
869void LocalImportChunk::writeTo(uint8_t *buf) const {
870 if (ctx.config.is64()) {
871 write64le(P: buf, V: sym->getRVA() + ctx.config.imageBase);
872 } else {
873 write32le(P: buf, V: sym->getRVA() + ctx.config.imageBase);
874 }
875}
876
877void RVATableChunk::writeTo(uint8_t *buf) const {
878 ulittle32_t *begin = reinterpret_cast<ulittle32_t *>(buf);
879 size_t cnt = 0;
880 for (const ChunkAndOffset &co : syms)
881 begin[cnt++] = co.inputChunk->getRVA() + co.offset;
882 llvm::sort(Start: begin, End: begin + cnt);
883 assert(std::unique(begin, begin + cnt) == begin + cnt &&
884 "RVA tables should be de-duplicated");
885}
886
887void RVAFlagTableChunk::writeTo(uint8_t *buf) const {
888 struct RVAFlag {
889 ulittle32_t rva;
890 uint8_t flag;
891 };
892 auto flags =
893 MutableArrayRef(reinterpret_cast<RVAFlag *>(buf), syms.size());
894 for (auto t : zip(t: syms, u&: flags)) {
895 const auto &sym = std::get<0>(t&: t);
896 auto &flag = std::get<1>(t&: t);
897 flag.rva = sym.inputChunk->getRVA() + sym.offset;
898 flag.flag = 0;
899 }
900 llvm::sort(C&: flags,
901 Comp: [](const RVAFlag &a, const RVAFlag &b) { return a.rva < b.rva; });
902 assert(llvm::unique(flags, [](const RVAFlag &a,
903 const RVAFlag &b) { return a.rva == b.rva; }) ==
904 flags.end() &&
905 "RVA tables should be de-duplicated");
906}
907
908size_t ECCodeMapChunk::getSize() const {
909 return map.size() * sizeof(chpe_range_entry);
910}
911
912void ECCodeMapChunk::writeTo(uint8_t *buf) const {
913 auto table = reinterpret_cast<chpe_range_entry *>(buf);
914 for (uint32_t i = 0; i < map.size(); i++) {
915 const ECCodeMapEntry &entry = map[i];
916 uint32_t start = entry.first->getRVA();
917 table[i].StartOffset = start | entry.type;
918 table[i].Length = entry.last->getRVA() + entry.last->getSize() - start;
919 }
920}
921
922// MinGW specific, for the "automatic import of variables from DLLs" feature.
923size_t PseudoRelocTableChunk::getSize() const {
924 if (relocs.empty())
925 return 0;
926 return 12 + 12 * relocs.size();
927}
928
929// MinGW specific.
930void PseudoRelocTableChunk::writeTo(uint8_t *buf) const {
931 if (relocs.empty())
932 return;
933
934 ulittle32_t *table = reinterpret_cast<ulittle32_t *>(buf);
935 // This is the list header, to signal the runtime pseudo relocation v2
936 // format.
937 table[0] = 0;
938 table[1] = 0;
939 table[2] = 1;
940
941 size_t idx = 3;
942 for (const RuntimePseudoReloc &rpr : relocs) {
943 table[idx + 0] = rpr.sym->getRVA();
944 table[idx + 1] = rpr.target->getRVA() + rpr.targetOffset;
945 table[idx + 2] = rpr.flags;
946 idx += 3;
947 }
948}
949
950// Windows-specific. This class represents a block in .reloc section.
951// The format is described here.
952//
953// On Windows, each DLL is linked against a fixed base address and
954// usually loaded to that address. However, if there's already another
955// DLL that overlaps, the loader has to relocate it. To do that, DLLs
956// contain .reloc sections which contain offsets that need to be fixed
957// up at runtime. If the loader finds that a DLL cannot be loaded to its
958// desired base address, it loads it to somewhere else, and add <actual
959// base address> - <desired base address> to each offset that is
960// specified by the .reloc section. In ELF terms, .reloc sections
961// contain relative relocations in REL format (as opposed to RELA.)
962//
963// This already significantly reduces the size of relocations compared
964// to ELF .rel.dyn, but Windows does more to reduce it (probably because
965// it was invented for PCs in the late '80s or early '90s.) Offsets in
966// .reloc are grouped by page where the page size is 12 bits, and
967// offsets sharing the same page address are stored consecutively to
968// represent them with less space. This is very similar to the page
969// table which is grouped by (multiple stages of) pages.
970//
971// For example, let's say we have 0x00030, 0x00500, 0x00700, 0x00A00,
972// 0x20004, and 0x20008 in a .reloc section for x64. The uppermost 4
973// bits have a type IMAGE_REL_BASED_DIR64 or 0xA. In the section, they
974// are represented like this:
975//
976// 0x00000 -- page address (4 bytes)
977// 16 -- size of this block (4 bytes)
978// 0xA030 -- entries (2 bytes each)
979// 0xA500
980// 0xA700
981// 0xAA00
982// 0x20000 -- page address (4 bytes)
983// 12 -- size of this block (4 bytes)
984// 0xA004 -- entries (2 bytes each)
985// 0xA008
986//
987// Usually we have a lot of relocations for each page, so the number of
988// bytes for one .reloc entry is close to 2 bytes on average.
989BaserelChunk::BaserelChunk(uint32_t page, Baserel *begin, Baserel *end) {
990 // Block header consists of 4 byte page RVA and 4 byte block size.
991 // Each entry is 2 byte. Last entry may be padding.
992 data.resize(new_size: alignTo(Value: (end - begin) * 2 + 8, Align: 4));
993 uint8_t *p = data.data();
994 write32le(P: p, V: page);
995 write32le(P: p + 4, V: data.size());
996 p += 8;
997 for (Baserel *i = begin; i != end; ++i) {
998 write16le(P: p, V: (i->type << 12) | (i->rva - page));
999 p += 2;
1000 }
1001}
1002
1003void BaserelChunk::writeTo(uint8_t *buf) const {
1004 memcpy(dest: buf, src: data.data(), n: data.size());
1005}
1006
1007uint8_t Baserel::getDefaultType(llvm::COFF::MachineTypes machine) {
1008 switch (machine) {
1009 case AMD64:
1010 case ARM64:
1011 return IMAGE_REL_BASED_DIR64;
1012 case I386:
1013 case ARMNT:
1014 return IMAGE_REL_BASED_HIGHLOW;
1015 default:
1016 llvm_unreachable("unknown machine type");
1017 }
1018}
1019
1020MergeChunk::MergeChunk(uint32_t alignment)
1021 : builder(StringTableBuilder::RAW, llvm::Align(alignment)) {
1022 setAlignment(alignment);
1023}
1024
1025void MergeChunk::addSection(COFFLinkerContext &ctx, SectionChunk *c) {
1026 assert(isPowerOf2_32(c->getAlignment()));
1027 uint8_t p2Align = llvm::Log2_32(Value: c->getAlignment());
1028 assert(p2Align < std::size(ctx.mergeChunkInstances));
1029 auto *&mc = ctx.mergeChunkInstances[p2Align];
1030 if (!mc)
1031 mc = make<MergeChunk>(args: c->getAlignment());
1032 mc->sections.push_back(x: c);
1033}
1034
1035void MergeChunk::finalizeContents() {
1036 assert(!finalized && "should only finalize once");
1037 for (SectionChunk *c : sections)
1038 if (c->live)
1039 builder.add(S: toStringRef(Input: c->getContents()));
1040 builder.finalize();
1041 finalized = true;
1042}
1043
1044void MergeChunk::assignSubsectionRVAs() {
1045 for (SectionChunk *c : sections) {
1046 if (!c->live)
1047 continue;
1048 size_t off = builder.getOffset(S: toStringRef(Input: c->getContents()));
1049 c->setRVA(rva + off);
1050 }
1051}
1052
1053uint32_t MergeChunk::getOutputCharacteristics() const {
1054 return IMAGE_SCN_MEM_READ | IMAGE_SCN_CNT_INITIALIZED_DATA;
1055}
1056
1057size_t MergeChunk::getSize() const {
1058 return builder.getSize();
1059}
1060
1061void MergeChunk::writeTo(uint8_t *buf) const {
1062 builder.write(Buf: buf);
1063}
1064
1065// MinGW specific.
1066size_t AbsolutePointerChunk::getSize() const { return ctx.config.wordsize; }
1067
1068void AbsolutePointerChunk::writeTo(uint8_t *buf) const {
1069 if (ctx.config.is64()) {
1070 write64le(P: buf, V: value);
1071 } else {
1072 write32le(P: buf, V: value);
1073 }
1074}
1075
1076} // namespace lld::coff
1077