1 //===- Chunks.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 "Chunks.h"
11 #include "InputFiles.h"
12 #include "Symbols.h"
13 #include "Writer.h"
14 #include "SymbolTable.h"
15 #include "lld/Common/ErrorHandler.h"
16 #include "llvm/ADT/Twine.h"
17 #include "llvm/BinaryFormat/COFF.h"
18 #include "llvm/Object/COFF.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/Endian.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include <algorithm>
23
24 using namespace llvm;
25 using namespace llvm::object;
26 using namespace llvm::support::endian;
27 using namespace llvm::COFF;
28 using llvm::support::ulittle32_t;
29
30 namespace lld {
31 namespace coff {
32
SectionChunk(ObjFile * F,const coff_section * H)33 SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
34 : Chunk(SectionKind), Repl(this), Header(H), File(F),
35 Relocs(File->getCOFFObj()->getRelocations(Header)) {
36 // Initialize SectionName.
37 File->getCOFFObj()->getSectionName(Header, SectionName);
38
39 Alignment = Header->getAlignment();
40
41 // If linker GC is disabled, every chunk starts out alive. If linker GC is
42 // enabled, treat non-comdat sections as roots. Generally optimized object
43 // files will be built with -ffunction-sections or /Gy, so most things worth
44 // stripping will be in a comdat.
45 Live = !Config->DoGC || !isCOMDAT();
46 }
47
48 // Initialize the RelocTargets vector, to allow redirecting certain relocations
49 // to a thunk instead of the actual symbol the relocation's symbol table index
50 // indicates.
readRelocTargets()51 void SectionChunk::readRelocTargets() {
52 assert(RelocTargets.empty());
53 RelocTargets.reserve(Relocs.size());
54 for (const coff_relocation &Rel : Relocs)
55 RelocTargets.push_back(File->getSymbol(Rel.SymbolTableIndex));
56 }
57
58 // Reset RelocTargets to their original targets before thunks were added.
resetRelocTargets()59 void SectionChunk::resetRelocTargets() {
60 for (size_t I = 0, E = Relocs.size(); I < E; ++I)
61 RelocTargets[I] = File->getSymbol(Relocs[I].SymbolTableIndex);
62 }
63
add16(uint8_t * P,int16_t V)64 static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); }
add32(uint8_t * P,int32_t V)65 static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); }
add64(uint8_t * P,int64_t V)66 static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); }
or16(uint8_t * P,uint16_t V)67 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | V); }
or32(uint8_t * P,uint32_t V)68 static void or32(uint8_t *P, uint32_t V) { write32le(P, read32le(P) | V); }
69
70 // Verify that given sections are appropriate targets for SECREL
71 // relocations. This check is relaxed because unfortunately debug
72 // sections have section-relative relocations against absolute symbols.
checkSecRel(const SectionChunk * Sec,OutputSection * OS)73 static bool checkSecRel(const SectionChunk *Sec, OutputSection *OS) {
74 if (OS)
75 return true;
76 if (Sec->isCodeView())
77 return false;
78 error("SECREL relocation cannot be applied to absolute symbols");
79 return false;
80 }
81
applySecRel(const SectionChunk * Sec,uint8_t * Off,OutputSection * OS,uint64_t S)82 static void applySecRel(const SectionChunk *Sec, uint8_t *Off,
83 OutputSection *OS, uint64_t S) {
84 if (!checkSecRel(Sec, OS))
85 return;
86 uint64_t SecRel = S - OS->getRVA();
87 if (SecRel > UINT32_MAX) {
88 error("overflow in SECREL relocation in section: " + Sec->getSectionName());
89 return;
90 }
91 add32(Off, SecRel);
92 }
93
applySecIdx(uint8_t * Off,OutputSection * OS)94 static void applySecIdx(uint8_t *Off, OutputSection *OS) {
95 // Absolute symbol doesn't have section index, but section index relocation
96 // against absolute symbol should be resolved to one plus the last output
97 // section index. This is required for compatibility with MSVC.
98 if (OS)
99 add16(Off, OS->SectionIndex);
100 else
101 add16(Off, DefinedAbsolute::NumOutputSections + 1);
102 }
103
applyRelX64(uint8_t * Off,uint16_t Type,OutputSection * OS,uint64_t S,uint64_t P) const104 void SectionChunk::applyRelX64(uint8_t *Off, uint16_t Type, OutputSection *OS,
105 uint64_t S, uint64_t P) const {
106 switch (Type) {
107 case IMAGE_REL_AMD64_ADDR32: add32(Off, S + Config->ImageBase); break;
108 case IMAGE_REL_AMD64_ADDR64: add64(Off, S + Config->ImageBase); break;
109 case IMAGE_REL_AMD64_ADDR32NB: add32(Off, S); break;
110 case IMAGE_REL_AMD64_REL32: add32(Off, S - P - 4); break;
111 case IMAGE_REL_AMD64_REL32_1: add32(Off, S - P - 5); break;
112 case IMAGE_REL_AMD64_REL32_2: add32(Off, S - P - 6); break;
113 case IMAGE_REL_AMD64_REL32_3: add32(Off, S - P - 7); break;
114 case IMAGE_REL_AMD64_REL32_4: add32(Off, S - P - 8); break;
115 case IMAGE_REL_AMD64_REL32_5: add32(Off, S - P - 9); break;
116 case IMAGE_REL_AMD64_SECTION: applySecIdx(Off, OS); break;
117 case IMAGE_REL_AMD64_SECREL: applySecRel(this, Off, OS, S); break;
118 default:
119 error("unsupported relocation type 0x" + Twine::utohexstr(Type) + " in " +
120 toString(File));
121 }
122 }
123
applyRelX86(uint8_t * Off,uint16_t Type,OutputSection * OS,uint64_t S,uint64_t P) const124 void SectionChunk::applyRelX86(uint8_t *Off, uint16_t Type, OutputSection *OS,
125 uint64_t S, uint64_t P) const {
126 switch (Type) {
127 case IMAGE_REL_I386_ABSOLUTE: break;
128 case IMAGE_REL_I386_DIR32: add32(Off, S + Config->ImageBase); break;
129 case IMAGE_REL_I386_DIR32NB: add32(Off, S); break;
130 case IMAGE_REL_I386_REL32: add32(Off, S - P - 4); break;
131 case IMAGE_REL_I386_SECTION: applySecIdx(Off, OS); break;
132 case IMAGE_REL_I386_SECREL: applySecRel(this, Off, OS, S); break;
133 default:
134 error("unsupported relocation type 0x" + Twine::utohexstr(Type) + " in " +
135 toString(File));
136 }
137 }
138
applyMOV(uint8_t * Off,uint16_t V)139 static void applyMOV(uint8_t *Off, uint16_t V) {
140 write16le(Off, (read16le(Off) & 0xfbf0) | ((V & 0x800) >> 1) | ((V >> 12) & 0xf));
141 write16le(Off + 2, (read16le(Off + 2) & 0x8f00) | ((V & 0x700) << 4) | (V & 0xff));
142 }
143
readMOV(uint8_t * Off,bool MOVT)144 static uint16_t readMOV(uint8_t *Off, bool MOVT) {
145 uint16_t Op1 = read16le(Off);
146 if ((Op1 & 0xfbf0) != (MOVT ? 0xf2c0 : 0xf240))
147 error("unexpected instruction in " + Twine(MOVT ? "MOVT" : "MOVW") +
148 " instruction in MOV32T relocation");
149 uint16_t Op2 = read16le(Off + 2);
150 if ((Op2 & 0x8000) != 0)
151 error("unexpected instruction in " + Twine(MOVT ? "MOVT" : "MOVW") +
152 " instruction in MOV32T relocation");
153 return (Op2 & 0x00ff) | ((Op2 >> 4) & 0x0700) | ((Op1 << 1) & 0x0800) |
154 ((Op1 & 0x000f) << 12);
155 }
156
applyMOV32T(uint8_t * Off,uint32_t V)157 void applyMOV32T(uint8_t *Off, uint32_t V) {
158 uint16_t ImmW = readMOV(Off, false); // read MOVW operand
159 uint16_t ImmT = readMOV(Off + 4, true); // read MOVT operand
160 uint32_t Imm = ImmW | (ImmT << 16);
161 V += Imm; // add the immediate offset
162 applyMOV(Off, V); // set MOVW operand
163 applyMOV(Off + 4, V >> 16); // set MOVT operand
164 }
165
applyBranch20T(uint8_t * Off,int32_t V)166 static void applyBranch20T(uint8_t *Off, int32_t V) {
167 if (!isInt<21>(V))
168 error("relocation out of range");
169 uint32_t S = V < 0 ? 1 : 0;
170 uint32_t J1 = (V >> 19) & 1;
171 uint32_t J2 = (V >> 18) & 1;
172 or16(Off, (S << 10) | ((V >> 12) & 0x3f));
173 or16(Off + 2, (J1 << 13) | (J2 << 11) | ((V >> 1) & 0x7ff));
174 }
175
applyBranch24T(uint8_t * Off,int32_t V)176 void applyBranch24T(uint8_t *Off, int32_t V) {
177 if (!isInt<25>(V))
178 error("relocation out of range");
179 uint32_t S = V < 0 ? 1 : 0;
180 uint32_t J1 = ((~V >> 23) & 1) ^ S;
181 uint32_t J2 = ((~V >> 22) & 1) ^ S;
182 or16(Off, (S << 10) | ((V >> 12) & 0x3ff));
183 // Clear out the J1 and J2 bits which may be set.
184 write16le(Off + 2, (read16le(Off + 2) & 0xd000) | (J1 << 13) | (J2 << 11) | ((V >> 1) & 0x7ff));
185 }
186
applyRelARM(uint8_t * Off,uint16_t Type,OutputSection * OS,uint64_t S,uint64_t P) const187 void SectionChunk::applyRelARM(uint8_t *Off, uint16_t Type, OutputSection *OS,
188 uint64_t S, uint64_t P) const {
189 // Pointer to thumb code must have the LSB set.
190 uint64_t SX = S;
191 if (OS && (OS->Header.Characteristics & IMAGE_SCN_MEM_EXECUTE))
192 SX |= 1;
193 switch (Type) {
194 case IMAGE_REL_ARM_ADDR32: add32(Off, SX + Config->ImageBase); break;
195 case IMAGE_REL_ARM_ADDR32NB: add32(Off, SX); break;
196 case IMAGE_REL_ARM_MOV32T: applyMOV32T(Off, SX + Config->ImageBase); break;
197 case IMAGE_REL_ARM_BRANCH20T: applyBranch20T(Off, SX - P - 4); break;
198 case IMAGE_REL_ARM_BRANCH24T: applyBranch24T(Off, SX - P - 4); break;
199 case IMAGE_REL_ARM_BLX23T: applyBranch24T(Off, SX - P - 4); break;
200 case IMAGE_REL_ARM_SECTION: applySecIdx(Off, OS); break;
201 case IMAGE_REL_ARM_SECREL: applySecRel(this, Off, OS, S); break;
202 default:
203 error("unsupported relocation type 0x" + Twine::utohexstr(Type) + " in " +
204 toString(File));
205 }
206 }
207
208 // Interpret the existing immediate value as a byte offset to the
209 // target symbol, then update the instruction with the immediate as
210 // the page offset from the current instruction to the target.
applyArm64Addr(uint8_t * Off,uint64_t S,uint64_t P,int Shift)211 void applyArm64Addr(uint8_t *Off, uint64_t S, uint64_t P, int Shift) {
212 uint32_t Orig = read32le(Off);
213 uint64_t Imm = ((Orig >> 29) & 0x3) | ((Orig >> 3) & 0x1FFFFC);
214 S += Imm;
215 Imm = (S >> Shift) - (P >> Shift);
216 uint32_t ImmLo = (Imm & 0x3) << 29;
217 uint32_t ImmHi = (Imm & 0x1FFFFC) << 3;
218 uint64_t Mask = (0x3 << 29) | (0x1FFFFC << 3);
219 write32le(Off, (Orig & ~Mask) | ImmLo | ImmHi);
220 }
221
222 // Update the immediate field in a AARCH64 ldr, str, and add instruction.
223 // Optionally limit the range of the written immediate by one or more bits
224 // (RangeLimit).
applyArm64Imm(uint8_t * Off,uint64_t Imm,uint32_t RangeLimit)225 void applyArm64Imm(uint8_t *Off, uint64_t Imm, uint32_t RangeLimit) {
226 uint32_t Orig = read32le(Off);
227 Imm += (Orig >> 10) & 0xFFF;
228 Orig &= ~(0xFFF << 10);
229 write32le(Off, Orig | ((Imm & (0xFFF >> RangeLimit)) << 10));
230 }
231
232 // Add the 12 bit page offset to the existing immediate.
233 // Ldr/str instructions store the opcode immediate scaled
234 // by the load/store size (giving a larger range for larger
235 // loads/stores). The immediate is always (both before and after
236 // fixing up the relocation) stored scaled similarly.
237 // Even if larger loads/stores have a larger range, limit the
238 // effective offset to 12 bit, since it is intended to be a
239 // page offset.
applyArm64Ldr(uint8_t * Off,uint64_t Imm)240 static void applyArm64Ldr(uint8_t *Off, uint64_t Imm) {
241 uint32_t Orig = read32le(Off);
242 uint32_t Size = Orig >> 30;
243 // 0x04000000 indicates SIMD/FP registers
244 // 0x00800000 indicates 128 bit
245 if ((Orig & 0x4800000) == 0x4800000)
246 Size += 4;
247 if ((Imm & ((1 << Size) - 1)) != 0)
248 error("misaligned ldr/str offset");
249 applyArm64Imm(Off, Imm >> Size, Size);
250 }
251
applySecRelLow12A(const SectionChunk * Sec,uint8_t * Off,OutputSection * OS,uint64_t S)252 static void applySecRelLow12A(const SectionChunk *Sec, uint8_t *Off,
253 OutputSection *OS, uint64_t S) {
254 if (checkSecRel(Sec, OS))
255 applyArm64Imm(Off, (S - OS->getRVA()) & 0xfff, 0);
256 }
257
applySecRelHigh12A(const SectionChunk * Sec,uint8_t * Off,OutputSection * OS,uint64_t S)258 static void applySecRelHigh12A(const SectionChunk *Sec, uint8_t *Off,
259 OutputSection *OS, uint64_t S) {
260 if (!checkSecRel(Sec, OS))
261 return;
262 uint64_t SecRel = (S - OS->getRVA()) >> 12;
263 if (0xfff < SecRel) {
264 error("overflow in SECREL_HIGH12A relocation in section: " +
265 Sec->getSectionName());
266 return;
267 }
268 applyArm64Imm(Off, SecRel & 0xfff, 0);
269 }
270
applySecRelLdr(const SectionChunk * Sec,uint8_t * Off,OutputSection * OS,uint64_t S)271 static void applySecRelLdr(const SectionChunk *Sec, uint8_t *Off,
272 OutputSection *OS, uint64_t S) {
273 if (checkSecRel(Sec, OS))
274 applyArm64Ldr(Off, (S - OS->getRVA()) & 0xfff);
275 }
276
applyArm64Branch26(uint8_t * Off,int64_t V)277 void applyArm64Branch26(uint8_t *Off, int64_t V) {
278 if (!isInt<28>(V))
279 error("relocation out of range");
280 or32(Off, (V & 0x0FFFFFFC) >> 2);
281 }
282
applyArm64Branch19(uint8_t * Off,int64_t V)283 static void applyArm64Branch19(uint8_t *Off, int64_t V) {
284 if (!isInt<21>(V))
285 error("relocation out of range");
286 or32(Off, (V & 0x001FFFFC) << 3);
287 }
288
applyArm64Branch14(uint8_t * Off,int64_t V)289 static void applyArm64Branch14(uint8_t *Off, int64_t V) {
290 if (!isInt<16>(V))
291 error("relocation out of range");
292 or32(Off, (V & 0x0000FFFC) << 3);
293 }
294
applyRelARM64(uint8_t * Off,uint16_t Type,OutputSection * OS,uint64_t S,uint64_t P) const295 void SectionChunk::applyRelARM64(uint8_t *Off, uint16_t Type, OutputSection *OS,
296 uint64_t S, uint64_t P) const {
297 switch (Type) {
298 case IMAGE_REL_ARM64_PAGEBASE_REL21: applyArm64Addr(Off, S, P, 12); break;
299 case IMAGE_REL_ARM64_REL21: applyArm64Addr(Off, S, P, 0); break;
300 case IMAGE_REL_ARM64_PAGEOFFSET_12A: applyArm64Imm(Off, S & 0xfff, 0); break;
301 case IMAGE_REL_ARM64_PAGEOFFSET_12L: applyArm64Ldr(Off, S & 0xfff); break;
302 case IMAGE_REL_ARM64_BRANCH26: applyArm64Branch26(Off, S - P); break;
303 case IMAGE_REL_ARM64_BRANCH19: applyArm64Branch19(Off, S - P); break;
304 case IMAGE_REL_ARM64_BRANCH14: applyArm64Branch14(Off, S - P); break;
305 case IMAGE_REL_ARM64_ADDR32: add32(Off, S + Config->ImageBase); break;
306 case IMAGE_REL_ARM64_ADDR32NB: add32(Off, S); break;
307 case IMAGE_REL_ARM64_ADDR64: add64(Off, S + Config->ImageBase); break;
308 case IMAGE_REL_ARM64_SECREL: applySecRel(this, Off, OS, S); break;
309 case IMAGE_REL_ARM64_SECREL_LOW12A: applySecRelLow12A(this, Off, OS, S); break;
310 case IMAGE_REL_ARM64_SECREL_HIGH12A: applySecRelHigh12A(this, Off, OS, S); break;
311 case IMAGE_REL_ARM64_SECREL_LOW12L: applySecRelLdr(this, Off, OS, S); break;
312 case IMAGE_REL_ARM64_SECTION: applySecIdx(Off, OS); break;
313 default:
314 error("unsupported relocation type 0x" + Twine::utohexstr(Type) + " in " +
315 toString(File));
316 }
317 }
318
maybeReportRelocationToDiscarded(const SectionChunk * FromChunk,Defined * Sym,const coff_relocation & Rel)319 static void maybeReportRelocationToDiscarded(const SectionChunk *FromChunk,
320 Defined *Sym,
321 const coff_relocation &Rel) {
322 // Don't report these errors when the relocation comes from a debug info
323 // section or in mingw mode. MinGW mode object files (built by GCC) can
324 // have leftover sections with relocations against discarded comdat
325 // sections. Such sections are left as is, with relocations untouched.
326 if (FromChunk->isCodeView() || FromChunk->isDWARF() || Config->MinGW)
327 return;
328
329 // Get the name of the symbol. If it's null, it was discarded early, so we
330 // have to go back to the object file.
331 ObjFile *File = FromChunk->File;
332 StringRef Name;
333 if (Sym) {
334 Name = Sym->getName();
335 } else {
336 COFFSymbolRef COFFSym =
337 check(File->getCOFFObj()->getSymbol(Rel.SymbolTableIndex));
338 File->getCOFFObj()->getSymbolName(COFFSym, Name);
339 }
340
341 error("relocation against symbol in discarded section: " + Name +
342 getSymbolLocations(File, Rel.SymbolTableIndex));
343 }
344
writeTo(uint8_t * Buf) const345 void SectionChunk::writeTo(uint8_t *Buf) const {
346 if (!hasData())
347 return;
348 // Copy section contents from source object file to output file.
349 ArrayRef<uint8_t> A = getContents();
350 if (!A.empty())
351 memcpy(Buf + OutputSectionOff, A.data(), A.size());
352
353 // Apply relocations.
354 size_t InputSize = getSize();
355 for (size_t I = 0, E = Relocs.size(); I < E; I++) {
356 const coff_relocation &Rel = Relocs[I];
357
358 // Check for an invalid relocation offset. This check isn't perfect, because
359 // we don't have the relocation size, which is only known after checking the
360 // machine and relocation type. As a result, a relocation may overwrite the
361 // beginning of the following input section.
362 if (Rel.VirtualAddress >= InputSize) {
363 error("relocation points beyond the end of its parent section");
364 continue;
365 }
366
367 uint8_t *Off = Buf + OutputSectionOff + Rel.VirtualAddress;
368
369 // Use the potentially remapped Symbol instead of the one that the
370 // relocation points to.
371 auto *Sym = dyn_cast_or_null<Defined>(RelocTargets[I]);
372
373 // Get the output section of the symbol for this relocation. The output
374 // section is needed to compute SECREL and SECTION relocations used in debug
375 // info.
376 Chunk *C = Sym ? Sym->getChunk() : nullptr;
377 OutputSection *OS = C ? C->getOutputSection() : nullptr;
378
379 // Skip the relocation if it refers to a discarded section, and diagnose it
380 // as an error if appropriate. If a symbol was discarded early, it may be
381 // null. If it was discarded late, the output section will be null, unless
382 // it was an absolute or synthetic symbol.
383 if (!Sym ||
384 (!OS && !isa<DefinedAbsolute>(Sym) && !isa<DefinedSynthetic>(Sym))) {
385 maybeReportRelocationToDiscarded(this, Sym, Rel);
386 continue;
387 }
388
389 uint64_t S = Sym->getRVA();
390
391 // Compute the RVA of the relocation for relative relocations.
392 uint64_t P = RVA + Rel.VirtualAddress;
393 switch (Config->Machine) {
394 case AMD64:
395 applyRelX64(Off, Rel.Type, OS, S, P);
396 break;
397 case I386:
398 applyRelX86(Off, Rel.Type, OS, S, P);
399 break;
400 case ARMNT:
401 applyRelARM(Off, Rel.Type, OS, S, P);
402 break;
403 case ARM64:
404 applyRelARM64(Off, Rel.Type, OS, S, P);
405 break;
406 default:
407 llvm_unreachable("unknown machine type");
408 }
409 }
410 }
411
addAssociative(SectionChunk * Child)412 void SectionChunk::addAssociative(SectionChunk *Child) {
413 AssocChildren.push_back(Child);
414 }
415
getBaserelType(const coff_relocation & Rel)416 static uint8_t getBaserelType(const coff_relocation &Rel) {
417 switch (Config->Machine) {
418 case AMD64:
419 if (Rel.Type == IMAGE_REL_AMD64_ADDR64)
420 return IMAGE_REL_BASED_DIR64;
421 return IMAGE_REL_BASED_ABSOLUTE;
422 case I386:
423 if (Rel.Type == IMAGE_REL_I386_DIR32)
424 return IMAGE_REL_BASED_HIGHLOW;
425 return IMAGE_REL_BASED_ABSOLUTE;
426 case ARMNT:
427 if (Rel.Type == IMAGE_REL_ARM_ADDR32)
428 return IMAGE_REL_BASED_HIGHLOW;
429 if (Rel.Type == IMAGE_REL_ARM_MOV32T)
430 return IMAGE_REL_BASED_ARM_MOV32T;
431 return IMAGE_REL_BASED_ABSOLUTE;
432 case ARM64:
433 if (Rel.Type == IMAGE_REL_ARM64_ADDR64)
434 return IMAGE_REL_BASED_DIR64;
435 return IMAGE_REL_BASED_ABSOLUTE;
436 default:
437 llvm_unreachable("unknown machine type");
438 }
439 }
440
441 // Windows-specific.
442 // Collect all locations that contain absolute addresses, which need to be
443 // fixed by the loader if load-time relocation is needed.
444 // Only called when base relocation is enabled.
getBaserels(std::vector<Baserel> * Res)445 void SectionChunk::getBaserels(std::vector<Baserel> *Res) {
446 for (size_t I = 0, E = Relocs.size(); I < E; I++) {
447 const coff_relocation &Rel = Relocs[I];
448 uint8_t Ty = getBaserelType(Rel);
449 if (Ty == IMAGE_REL_BASED_ABSOLUTE)
450 continue;
451 // Use the potentially remapped Symbol instead of the one that the
452 // relocation points to.
453 Symbol *Target = RelocTargets[I];
454 if (!Target || isa<DefinedAbsolute>(Target))
455 continue;
456 Res->emplace_back(RVA + Rel.VirtualAddress, Ty);
457 }
458 }
459
460 // MinGW specific.
461 // Check whether a static relocation of type Type can be deferred and
462 // handled at runtime as a pseudo relocation (for references to a module
463 // local variable, which turned out to actually need to be imported from
464 // another DLL) This returns the size the relocation is supposed to update,
465 // in bits, or 0 if the relocation cannot be handled as a runtime pseudo
466 // relocation.
getRuntimePseudoRelocSize(uint16_t Type)467 static int getRuntimePseudoRelocSize(uint16_t Type) {
468 // Relocations that either contain an absolute address, or a plain
469 // relative offset, since the runtime pseudo reloc implementation
470 // adds 8/16/32/64 bit values to a memory address.
471 //
472 // Given a pseudo relocation entry,
473 //
474 // typedef struct {
475 // DWORD sym;
476 // DWORD target;
477 // DWORD flags;
478 // } runtime_pseudo_reloc_item_v2;
479 //
480 // the runtime relocation performs this adjustment:
481 // *(base + .target) += *(base + .sym) - (base + .sym)
482 //
483 // This works for both absolute addresses (IMAGE_REL_*_ADDR32/64,
484 // IMAGE_REL_I386_DIR32, where the memory location initially contains
485 // the address of the IAT slot, and for relative addresses (IMAGE_REL*_REL32),
486 // where the memory location originally contains the relative offset to the
487 // IAT slot.
488 //
489 // This requires the target address to be writable, either directly out of
490 // the image, or temporarily changed at runtime with VirtualProtect.
491 // Since this only operates on direct address values, it doesn't work for
492 // ARM/ARM64 relocations, other than the plain ADDR32/ADDR64 relocations.
493 switch (Config->Machine) {
494 case AMD64:
495 switch (Type) {
496 case IMAGE_REL_AMD64_ADDR64:
497 return 64;
498 case IMAGE_REL_AMD64_ADDR32:
499 case IMAGE_REL_AMD64_REL32:
500 case IMAGE_REL_AMD64_REL32_1:
501 case IMAGE_REL_AMD64_REL32_2:
502 case IMAGE_REL_AMD64_REL32_3:
503 case IMAGE_REL_AMD64_REL32_4:
504 case IMAGE_REL_AMD64_REL32_5:
505 return 32;
506 default:
507 return 0;
508 }
509 case I386:
510 switch (Type) {
511 case IMAGE_REL_I386_DIR32:
512 case IMAGE_REL_I386_REL32:
513 return 32;
514 default:
515 return 0;
516 }
517 case ARMNT:
518 switch (Type) {
519 case IMAGE_REL_ARM_ADDR32:
520 return 32;
521 default:
522 return 0;
523 }
524 case ARM64:
525 switch (Type) {
526 case IMAGE_REL_ARM64_ADDR64:
527 return 64;
528 case IMAGE_REL_ARM64_ADDR32:
529 return 32;
530 default:
531 return 0;
532 }
533 default:
534 llvm_unreachable("unknown machine type");
535 }
536 }
537
538 // MinGW specific.
539 // Append information to the provided vector about all relocations that
540 // need to be handled at runtime as runtime pseudo relocations (references
541 // to a module local variable, which turned out to actually need to be
542 // imported from another DLL).
getRuntimePseudoRelocs(std::vector<RuntimePseudoReloc> & Res)543 void SectionChunk::getRuntimePseudoRelocs(
544 std::vector<RuntimePseudoReloc> &Res) {
545 for (const coff_relocation &Rel : Relocs) {
546 auto *Target =
547 dyn_cast_or_null<Defined>(File->getSymbol(Rel.SymbolTableIndex));
548 if (!Target || !Target->IsRuntimePseudoReloc)
549 continue;
550 int SizeInBits = getRuntimePseudoRelocSize(Rel.Type);
551 if (SizeInBits == 0) {
552 error("unable to automatically import from " + Target->getName() +
553 " with relocation type " +
554 File->getCOFFObj()->getRelocationTypeName(Rel.Type) + " in " +
555 toString(File));
556 continue;
557 }
558 // SizeInBits is used to initialize the Flags field; currently no
559 // other flags are defined.
560 Res.emplace_back(
561 RuntimePseudoReloc(Target, this, Rel.VirtualAddress, SizeInBits));
562 }
563 }
564
hasData() const565 bool SectionChunk::hasData() const {
566 return !(Header->Characteristics & IMAGE_SCN_CNT_UNINITIALIZED_DATA);
567 }
568
getOutputCharacteristics() const569 uint32_t SectionChunk::getOutputCharacteristics() const {
570 return Header->Characteristics & (PermMask | TypeMask);
571 }
572
isCOMDAT() const573 bool SectionChunk::isCOMDAT() const {
574 return Header->Characteristics & IMAGE_SCN_LNK_COMDAT;
575 }
576
printDiscardedMessage() const577 void SectionChunk::printDiscardedMessage() const {
578 // Removed by dead-stripping. If it's removed by ICF, ICF already
579 // printed out the name, so don't repeat that here.
580 if (Sym && this == Repl)
581 message("Discarded " + Sym->getName());
582 }
583
getDebugName()584 StringRef SectionChunk::getDebugName() {
585 if (Sym)
586 return Sym->getName();
587 return "";
588 }
589
getContents() const590 ArrayRef<uint8_t> SectionChunk::getContents() const {
591 ArrayRef<uint8_t> A;
592 File->getCOFFObj()->getSectionContents(Header, A);
593 return A;
594 }
595
replace(SectionChunk * Other)596 void SectionChunk::replace(SectionChunk *Other) {
597 Alignment = std::max(Alignment, Other->Alignment);
598 Other->Repl = Repl;
599 Other->Live = false;
600 }
601
getSectionNumber() const602 uint32_t SectionChunk::getSectionNumber() const {
603 DataRefImpl R;
604 R.p = reinterpret_cast<uintptr_t>(Header);
605 SectionRef S(R, File->getCOFFObj());
606 return S.getIndex() + 1;
607 }
608
CommonChunk(const COFFSymbolRef S)609 CommonChunk::CommonChunk(const COFFSymbolRef S) : Sym(S) {
610 // Common symbols are aligned on natural boundaries up to 32 bytes.
611 // This is what MSVC link.exe does.
612 Alignment = std::min(uint64_t(32), PowerOf2Ceil(Sym.getValue()));
613 }
614
getOutputCharacteristics() const615 uint32_t CommonChunk::getOutputCharacteristics() const {
616 return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
617 IMAGE_SCN_MEM_WRITE;
618 }
619
writeTo(uint8_t * Buf) const620 void StringChunk::writeTo(uint8_t *Buf) const {
621 memcpy(Buf + OutputSectionOff, Str.data(), Str.size());
622 Buf[OutputSectionOff + Str.size()] = '\0';
623 }
624
ImportThunkChunkX64(Defined * S)625 ImportThunkChunkX64::ImportThunkChunkX64(Defined *S) : ImpSymbol(S) {
626 // Intel Optimization Manual says that all branch targets
627 // should be 16-byte aligned. MSVC linker does this too.
628 Alignment = 16;
629 }
630
writeTo(uint8_t * Buf) const631 void ImportThunkChunkX64::writeTo(uint8_t *Buf) const {
632 memcpy(Buf + OutputSectionOff, ImportThunkX86, sizeof(ImportThunkX86));
633 // The first two bytes is a JMP instruction. Fill its operand.
634 write32le(Buf + OutputSectionOff + 2, ImpSymbol->getRVA() - RVA - getSize());
635 }
636
getBaserels(std::vector<Baserel> * Res)637 void ImportThunkChunkX86::getBaserels(std::vector<Baserel> *Res) {
638 Res->emplace_back(getRVA() + 2);
639 }
640
writeTo(uint8_t * Buf) const641 void ImportThunkChunkX86::writeTo(uint8_t *Buf) const {
642 memcpy(Buf + OutputSectionOff, ImportThunkX86, sizeof(ImportThunkX86));
643 // The first two bytes is a JMP instruction. Fill its operand.
644 write32le(Buf + OutputSectionOff + 2,
645 ImpSymbol->getRVA() + Config->ImageBase);
646 }
647
getBaserels(std::vector<Baserel> * Res)648 void ImportThunkChunkARM::getBaserels(std::vector<Baserel> *Res) {
649 Res->emplace_back(getRVA(), IMAGE_REL_BASED_ARM_MOV32T);
650 }
651
writeTo(uint8_t * Buf) const652 void ImportThunkChunkARM::writeTo(uint8_t *Buf) const {
653 memcpy(Buf + OutputSectionOff, ImportThunkARM, sizeof(ImportThunkARM));
654 // Fix mov.w and mov.t operands.
655 applyMOV32T(Buf + OutputSectionOff, ImpSymbol->getRVA() + Config->ImageBase);
656 }
657
writeTo(uint8_t * Buf) const658 void ImportThunkChunkARM64::writeTo(uint8_t *Buf) const {
659 int64_t Off = ImpSymbol->getRVA() & 0xfff;
660 memcpy(Buf + OutputSectionOff, ImportThunkARM64, sizeof(ImportThunkARM64));
661 applyArm64Addr(Buf + OutputSectionOff, ImpSymbol->getRVA(), RVA, 12);
662 applyArm64Ldr(Buf + OutputSectionOff + 4, Off);
663 }
664
665 // A Thumb2, PIC, non-interworking range extension thunk.
666 const uint8_t ArmThunk[] = {
667 0x40, 0xf2, 0x00, 0x0c, // P: movw ip,:lower16:S - (P + (L1-P) + 4)
668 0xc0, 0xf2, 0x00, 0x0c, // movt ip,:upper16:S - (P + (L1-P) + 4)
669 0xe7, 0x44, // L1: add pc, ip
670 };
671
getSize() const672 size_t RangeExtensionThunkARM::getSize() const {
673 assert(Config->Machine == ARMNT);
674 return sizeof(ArmThunk);
675 }
676
writeTo(uint8_t * Buf) const677 void RangeExtensionThunkARM::writeTo(uint8_t *Buf) const {
678 assert(Config->Machine == ARMNT);
679 uint64_t Offset = Target->getRVA() - RVA - 12;
680 memcpy(Buf + OutputSectionOff, ArmThunk, sizeof(ArmThunk));
681 applyMOV32T(Buf + OutputSectionOff, uint32_t(Offset));
682 }
683
684 // A position independent ARM64 adrp+add thunk, with a maximum range of
685 // +/- 4 GB, which is enough for any PE-COFF.
686 const uint8_t Arm64Thunk[] = {
687 0x10, 0x00, 0x00, 0x90, // adrp x16, Dest
688 0x10, 0x02, 0x00, 0x91, // add x16, x16, :lo12:Dest
689 0x00, 0x02, 0x1f, 0xd6, // br x16
690 };
691
getSize() const692 size_t RangeExtensionThunkARM64::getSize() const {
693 assert(Config->Machine == ARM64);
694 return sizeof(Arm64Thunk);
695 }
696
writeTo(uint8_t * Buf) const697 void RangeExtensionThunkARM64::writeTo(uint8_t *Buf) const {
698 assert(Config->Machine == ARM64);
699 memcpy(Buf + OutputSectionOff, Arm64Thunk, sizeof(Arm64Thunk));
700 applyArm64Addr(Buf + OutputSectionOff + 0, Target->getRVA(), RVA, 12);
701 applyArm64Imm(Buf + OutputSectionOff + 4, Target->getRVA() & 0xfff, 0);
702 }
703
getBaserels(std::vector<Baserel> * Res)704 void LocalImportChunk::getBaserels(std::vector<Baserel> *Res) {
705 Res->emplace_back(getRVA());
706 }
707
getSize() const708 size_t LocalImportChunk::getSize() const { return Config->Wordsize; }
709
writeTo(uint8_t * Buf) const710 void LocalImportChunk::writeTo(uint8_t *Buf) const {
711 if (Config->is64()) {
712 write64le(Buf + OutputSectionOff, Sym->getRVA() + Config->ImageBase);
713 } else {
714 write32le(Buf + OutputSectionOff, Sym->getRVA() + Config->ImageBase);
715 }
716 }
717
writeTo(uint8_t * Buf) const718 void RVATableChunk::writeTo(uint8_t *Buf) const {
719 ulittle32_t *Begin = reinterpret_cast<ulittle32_t *>(Buf + OutputSectionOff);
720 size_t Cnt = 0;
721 for (const ChunkAndOffset &CO : Syms)
722 Begin[Cnt++] = CO.InputChunk->getRVA() + CO.Offset;
723 std::sort(Begin, Begin + Cnt);
724 assert(std::unique(Begin, Begin + Cnt) == Begin + Cnt &&
725 "RVA tables should be de-duplicated");
726 }
727
728 // MinGW specific, for the "automatic import of variables from DLLs" feature.
getSize() const729 size_t PseudoRelocTableChunk::getSize() const {
730 if (Relocs.empty())
731 return 0;
732 return 12 + 12 * Relocs.size();
733 }
734
735 // MinGW specific.
writeTo(uint8_t * Buf) const736 void PseudoRelocTableChunk::writeTo(uint8_t *Buf) const {
737 if (Relocs.empty())
738 return;
739
740 ulittle32_t *Table = reinterpret_cast<ulittle32_t *>(Buf + OutputSectionOff);
741 // This is the list header, to signal the runtime pseudo relocation v2
742 // format.
743 Table[0] = 0;
744 Table[1] = 0;
745 Table[2] = 1;
746
747 size_t Idx = 3;
748 for (const RuntimePseudoReloc &RPR : Relocs) {
749 Table[Idx + 0] = RPR.Sym->getRVA();
750 Table[Idx + 1] = RPR.Target->getRVA() + RPR.TargetOffset;
751 Table[Idx + 2] = RPR.Flags;
752 Idx += 3;
753 }
754 }
755
756 // Windows-specific. This class represents a block in .reloc section.
757 // The format is described here.
758 //
759 // On Windows, each DLL is linked against a fixed base address and
760 // usually loaded to that address. However, if there's already another
761 // DLL that overlaps, the loader has to relocate it. To do that, DLLs
762 // contain .reloc sections which contain offsets that need to be fixed
763 // up at runtime. If the loader finds that a DLL cannot be loaded to its
764 // desired base address, it loads it to somewhere else, and add <actual
765 // base address> - <desired base address> to each offset that is
766 // specified by the .reloc section. In ELF terms, .reloc sections
767 // contain relative relocations in REL format (as opposed to RELA.)
768 //
769 // This already significantly reduces the size of relocations compared
770 // to ELF .rel.dyn, but Windows does more to reduce it (probably because
771 // it was invented for PCs in the late '80s or early '90s.) Offsets in
772 // .reloc are grouped by page where the page size is 12 bits, and
773 // offsets sharing the same page address are stored consecutively to
774 // represent them with less space. This is very similar to the page
775 // table which is grouped by (multiple stages of) pages.
776 //
777 // For example, let's say we have 0x00030, 0x00500, 0x00700, 0x00A00,
778 // 0x20004, and 0x20008 in a .reloc section for x64. The uppermost 4
779 // bits have a type IMAGE_REL_BASED_DIR64 or 0xA. In the section, they
780 // are represented like this:
781 //
782 // 0x00000 -- page address (4 bytes)
783 // 16 -- size of this block (4 bytes)
784 // 0xA030 -- entries (2 bytes each)
785 // 0xA500
786 // 0xA700
787 // 0xAA00
788 // 0x20000 -- page address (4 bytes)
789 // 12 -- size of this block (4 bytes)
790 // 0xA004 -- entries (2 bytes each)
791 // 0xA008
792 //
793 // Usually we have a lot of relocations for each page, so the number of
794 // bytes for one .reloc entry is close to 2 bytes on average.
BaserelChunk(uint32_t Page,Baserel * Begin,Baserel * End)795 BaserelChunk::BaserelChunk(uint32_t Page, Baserel *Begin, Baserel *End) {
796 // Block header consists of 4 byte page RVA and 4 byte block size.
797 // Each entry is 2 byte. Last entry may be padding.
798 Data.resize(alignTo((End - Begin) * 2 + 8, 4));
799 uint8_t *P = Data.data();
800 write32le(P, Page);
801 write32le(P + 4, Data.size());
802 P += 8;
803 for (Baserel *I = Begin; I != End; ++I) {
804 write16le(P, (I->Type << 12) | (I->RVA - Page));
805 P += 2;
806 }
807 }
808
writeTo(uint8_t * Buf) const809 void BaserelChunk::writeTo(uint8_t *Buf) const {
810 memcpy(Buf + OutputSectionOff, Data.data(), Data.size());
811 }
812
getDefaultType()813 uint8_t Baserel::getDefaultType() {
814 switch (Config->Machine) {
815 case AMD64:
816 case ARM64:
817 return IMAGE_REL_BASED_DIR64;
818 case I386:
819 case ARMNT:
820 return IMAGE_REL_BASED_HIGHLOW;
821 default:
822 llvm_unreachable("unknown machine type");
823 }
824 }
825
826 std::map<uint32_t, MergeChunk *> MergeChunk::Instances;
827
MergeChunk(uint32_t Alignment)828 MergeChunk::MergeChunk(uint32_t Alignment)
829 : Builder(StringTableBuilder::RAW, Alignment) {
830 this->Alignment = Alignment;
831 }
832
addSection(SectionChunk * C)833 void MergeChunk::addSection(SectionChunk *C) {
834 auto *&MC = Instances[C->Alignment];
835 if (!MC)
836 MC = make<MergeChunk>(C->Alignment);
837 MC->Sections.push_back(C);
838 }
839
finalizeContents()840 void MergeChunk::finalizeContents() {
841 if (!Finalized) {
842 for (SectionChunk *C : Sections)
843 if (C->Live)
844 Builder.add(toStringRef(C->getContents()));
845 Builder.finalize();
846 Finalized = true;
847 }
848
849 for (SectionChunk *C : Sections) {
850 if (!C->Live)
851 continue;
852 size_t Off = Builder.getOffset(toStringRef(C->getContents()));
853 C->setOutputSection(Out);
854 C->setRVA(RVA + Off);
855 C->OutputSectionOff = OutputSectionOff + Off;
856 }
857 }
858
getOutputCharacteristics() const859 uint32_t MergeChunk::getOutputCharacteristics() const {
860 return IMAGE_SCN_MEM_READ | IMAGE_SCN_CNT_INITIALIZED_DATA;
861 }
862
getSize() const863 size_t MergeChunk::getSize() const {
864 return Builder.getSize();
865 }
866
writeTo(uint8_t * Buf) const867 void MergeChunk::writeTo(uint8_t *Buf) const {
868 Builder.write(Buf + OutputSectionOff);
869 }
870
871 // MinGW specific.
getSize() const872 size_t AbsolutePointerChunk::getSize() const { return Config->Wordsize; }
873
writeTo(uint8_t * Buf) const874 void AbsolutePointerChunk::writeTo(uint8_t *Buf) const {
875 if (Config->is64()) {
876 write64le(Buf + OutputSectionOff, Value);
877 } else {
878 write32le(Buf + OutputSectionOff, Value);
879 }
880 }
881
882 } // namespace coff
883 } // namespace lld
884