xref: /freebsd/contrib/llvm-project/lld/COFF/Chunks.cpp (revision a4e5e0106ac7145f56eb39a691e302cabb4635be)
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 
26 using namespace llvm;
27 using namespace llvm::object;
28 using namespace llvm::support::endian;
29 using namespace llvm::COFF;
30 using llvm::support::ulittle32_t;
31 
32 namespace lld::coff {
33 
34 SectionChunk::SectionChunk(ObjFile *f, const coff_section *h)
35     : Chunk(SectionKind), file(f), header(h), repl(this) {
36   // Initialize relocs.
37   if (file)
38     setRelocs(file->getCOFFObj()->getRelocations(header));
39 
40   // Initialize sectionName.
41   StringRef sectionName;
42   if (file) {
43     if (Expected<StringRef> e = file->getCOFFObj()->getSectionName(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.
66 static_assert(sizeof(SectionChunk) <= 88, "SectionChunk grew unexpectedly");
67 
68 static void add16(uint8_t *p, int16_t v) { write16le(p, read16le(p) + v); }
69 static void add32(uint8_t *p, int32_t v) { write32le(p, read32le(p) + v); }
70 static void add64(uint8_t *p, int64_t v) { write64le(p, read64le(p) + v); }
71 static void or16(uint8_t *p, uint16_t v) { write16le(p, read16le(p) | v); }
72 static void or32(uint8_t *p, uint32_t v) { write32le(p, read32le(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.
77 static bool checkSecRel(const SectionChunk *sec, OutputSection *os) {
78   if (os)
79     return true;
80   if (sec->isCodeView())
81     return false;
82   error("SECREL relocation cannot be applied to absolute symbols");
83   return false;
84 }
85 
86 static 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("overflow in SECREL relocation in section: " + sec->getSectionName());
93     return;
94   }
95   add32(off, secRel);
96 }
97 
98 static 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(off, os->sectionIndex);
109   else
110     add16(off, numOutputSections + 1);
111 }
112 
113 void 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(off, s + imageBase);
119     break;
120   case IMAGE_REL_AMD64_ADDR64:
121     add64(off, s + imageBase);
122     break;
123   case IMAGE_REL_AMD64_ADDR32NB: add32(off, s); break;
124   case IMAGE_REL_AMD64_REL32:    add32(off, s - p - 4); break;
125   case IMAGE_REL_AMD64_REL32_1:  add32(off, s - p - 5); break;
126   case IMAGE_REL_AMD64_REL32_2:  add32(off, s - p - 6); break;
127   case IMAGE_REL_AMD64_REL32_3:  add32(off, s - p - 7); break;
128   case IMAGE_REL_AMD64_REL32_4:  add32(off, s - p - 8); break;
129   case IMAGE_REL_AMD64_REL32_5:  add32(off, s - p - 9); break;
130   case IMAGE_REL_AMD64_SECTION:
131     applySecIdx(off, os, file->ctx.outputSections.size());
132     break;
133   case IMAGE_REL_AMD64_SECREL:   applySecRel(this, off, os, s); break;
134   default:
135     error("unsupported relocation type 0x" + Twine::utohexstr(type) + " in " +
136           toString(file));
137   }
138 }
139 
140 void 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(off, s + imageBase);
147     break;
148   case IMAGE_REL_I386_DIR32NB:  add32(off, s); break;
149   case IMAGE_REL_I386_REL32:    add32(off, s - p - 4); break;
150   case IMAGE_REL_I386_SECTION:
151     applySecIdx(off, os, file->ctx.outputSections.size());
152     break;
153   case IMAGE_REL_I386_SECREL:   applySecRel(this, off, os, s); break;
154   default:
155     error("unsupported relocation type 0x" + Twine::utohexstr(type) + " in " +
156           toString(file));
157   }
158 }
159 
160 static void applyMOV(uint8_t *off, uint16_t v) {
161   write16le(off, (read16le(off) & 0xfbf0) | ((v & 0x800) >> 1) | ((v >> 12) & 0xf));
162   write16le(off + 2, (read16le(off + 2) & 0x8f00) | ((v & 0x700) << 4) | (v & 0xff));
163 }
164 
165 static uint16_t readMOV(uint8_t *off, bool movt) {
166   uint16_t op1 = read16le(off);
167   if ((op1 & 0xfbf0) != (movt ? 0xf2c0 : 0xf240))
168     error("unexpected instruction in " + Twine(movt ? "MOVT" : "MOVW") +
169           " instruction in MOV32T relocation");
170   uint16_t op2 = read16le(off + 2);
171   if ((op2 & 0x8000) != 0)
172     error("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 
178 void applyMOV32T(uint8_t *off, uint32_t v) {
179   uint16_t immW = readMOV(off, false);    // read MOVW operand
180   uint16_t immT = readMOV(off + 4, 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 + 4, v >> 16); // set MOVT operand
185 }
186 
187 static void applyBranch20T(uint8_t *off, int32_t v) {
188   if (!isInt<21>(v))
189     error("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(off, (s << 10) | ((v >> 12) & 0x3f));
194   or16(off + 2, (j1 << 13) | (j2 << 11) | ((v >> 1) & 0x7ff));
195 }
196 
197 void applyBranch24T(uint8_t *off, int32_t v) {
198   if (!isInt<25>(v))
199     error("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(off, (s << 10) | ((v >> 12) & 0x3ff));
204   // Clear out the J1 and J2 bits which may be set.
205   write16le(off + 2, (read16le(off + 2) & 0xd000) | (j1 << 13) | (j2 << 11) | ((v >> 1) & 0x7ff));
206 }
207 
208 void 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(off, sx + imageBase);
218     break;
219   case IMAGE_REL_ARM_ADDR32NB:  add32(off, sx); break;
220   case IMAGE_REL_ARM_MOV32T:
221     applyMOV32T(off, sx + imageBase);
222     break;
223   case IMAGE_REL_ARM_BRANCH20T: applyBranch20T(off, sx - p - 4); break;
224   case IMAGE_REL_ARM_BRANCH24T: applyBranch24T(off, sx - p - 4); break;
225   case IMAGE_REL_ARM_BLX23T:    applyBranch24T(off, sx - p - 4); break;
226   case IMAGE_REL_ARM_SECTION:
227     applySecIdx(off, os, file->ctx.outputSections.size());
228     break;
229   case IMAGE_REL_ARM_SECREL:    applySecRel(this, off, os, s); break;
230   case IMAGE_REL_ARM_REL32:     add32(off, sx - p - 4); break;
231   default:
232     error("unsupported relocation type 0x" + Twine::utohexstr(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.
240 void applyArm64Addr(uint8_t *off, uint64_t s, uint64_t p, int shift) {
241   uint32_t orig = read32le(off);
242   int64_t imm =
243       SignExtend64<21>(((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(off, (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).
255 void applyArm64Imm(uint8_t *off, uint64_t imm, uint32_t rangeLimit) {
256   uint32_t orig = read32le(off);
257   imm += (orig >> 10) & 0xFFF;
258   orig &= ~(0xFFF << 10);
259   write32le(off, 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.
270 static void applyArm64Ldr(uint8_t *off, uint64_t imm) {
271   uint32_t orig = read32le(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("misaligned ldr/str offset");
279   applyArm64Imm(off, imm >> size, size);
280 }
281 
282 static void applySecRelLow12A(const SectionChunk *sec, uint8_t *off,
283                               OutputSection *os, uint64_t s) {
284   if (checkSecRel(sec, os))
285     applyArm64Imm(off, (s - os->getRVA()) & 0xfff, 0);
286 }
287 
288 static 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("overflow in SECREL_HIGH12A relocation in section: " +
295           sec->getSectionName());
296     return;
297   }
298   applyArm64Imm(off, secRel & 0xfff, 0);
299 }
300 
301 static void applySecRelLdr(const SectionChunk *sec, uint8_t *off,
302                            OutputSection *os, uint64_t s) {
303   if (checkSecRel(sec, os))
304     applyArm64Ldr(off, (s - os->getRVA()) & 0xfff);
305 }
306 
307 void applyArm64Branch26(uint8_t *off, int64_t v) {
308   if (!isInt<28>(v))
309     error("relocation out of range");
310   or32(off, (v & 0x0FFFFFFC) >> 2);
311 }
312 
313 static void applyArm64Branch19(uint8_t *off, int64_t v) {
314   if (!isInt<21>(v))
315     error("relocation out of range");
316   or32(off, (v & 0x001FFFFC) << 3);
317 }
318 
319 static void applyArm64Branch14(uint8_t *off, int64_t v) {
320   if (!isInt<16>(v))
321     error("relocation out of range");
322   or32(off, (v & 0x0000FFFC) << 3);
323 }
324 
325 void 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, 12); break;
330   case IMAGE_REL_ARM64_REL21:          applyArm64Addr(off, s, p, 0); break;
331   case IMAGE_REL_ARM64_PAGEOFFSET_12A: applyArm64Imm(off, s & 0xfff, 0); break;
332   case IMAGE_REL_ARM64_PAGEOFFSET_12L: applyArm64Ldr(off, s & 0xfff); break;
333   case IMAGE_REL_ARM64_BRANCH26:       applyArm64Branch26(off, s - p); break;
334   case IMAGE_REL_ARM64_BRANCH19:       applyArm64Branch19(off, s - p); break;
335   case IMAGE_REL_ARM64_BRANCH14:       applyArm64Branch14(off, s - p); break;
336   case IMAGE_REL_ARM64_ADDR32:
337     add32(off, s + imageBase);
338     break;
339   case IMAGE_REL_ARM64_ADDR32NB:       add32(off, s); break;
340   case IMAGE_REL_ARM64_ADDR64:
341     add64(off, s + imageBase);
342     break;
343   case IMAGE_REL_ARM64_SECREL:         applySecRel(this, off, os, s); break;
344   case IMAGE_REL_ARM64_SECREL_LOW12A:  applySecRelLow12A(this, off, os, s); break;
345   case IMAGE_REL_ARM64_SECREL_HIGH12A: applySecRelHigh12A(this, off, os, s); break;
346   case IMAGE_REL_ARM64_SECREL_LOW12L:  applySecRelLdr(this, off, os, s); break;
347   case IMAGE_REL_ARM64_SECTION:
348     applySecIdx(off, os, file->ctx.outputSections.size());
349     break;
350   case IMAGE_REL_ARM64_REL32:          add32(off, s - p - 4); break;
351   default:
352     error("unsupported relocation type 0x" + Twine::utohexstr(type) + " in " +
353           toString(file));
354   }
355 }
356 
357 static 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(file->getCOFFObj()->getSymbol(rel.SymbolTableIndex));
377     name = check(file->getCOFFObj()->getSymbolName(coffSym));
378   }
379 
380   std::vector<std::string> symbolLocations =
381       getSymbolLocations(file, 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(os.str());
389 }
390 
391 void 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(buf, a.data(), 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("relocation points beyond the end of its parent section");
408       continue;
409     }
410 
411     applyRelocation(buf + rel.VirtualAddress, rel);
412   }
413 }
414 
415 void SectionChunk::applyRelocation(uint8_t *off,
416                                    const coff_relocation &rel) const {
417   auto *sym = dyn_cast_or_null<Defined>(file->getSymbol(rel.SymbolTableIndex));
418 
419   // Get the output section of the symbol for this relocation.  The output
420   // section is needed to compute SECREL and SECTION relocations used in debug
421   // info.
422   Chunk *c = sym ? sym->getChunk() : nullptr;
423   OutputSection *os = c ? file->ctx.getOutputSection(c) : nullptr;
424 
425   // Skip the relocation if it refers to a discarded section, and diagnose it
426   // as an error if appropriate. If a symbol was discarded early, it may be
427   // null. If it was discarded late, the output section will be null, unless
428   // it was an absolute or synthetic symbol.
429   if (!sym ||
430       (!os && !isa<DefinedAbsolute>(sym) && !isa<DefinedSynthetic>(sym))) {
431     maybeReportRelocationToDiscarded(this, sym, rel, file->ctx.config.mingw);
432     return;
433   }
434 
435   uint64_t s = sym->getRVA();
436 
437   // Compute the RVA of the relocation for relative relocations.
438   uint64_t p = rva + rel.VirtualAddress;
439   uint64_t imageBase = file->ctx.config.imageBase;
440   switch (file->ctx.config.machine) {
441   case AMD64:
442     applyRelX64(off, rel.Type, os, s, p, imageBase);
443     break;
444   case I386:
445     applyRelX86(off, rel.Type, os, s, p, imageBase);
446     break;
447   case ARMNT:
448     applyRelARM(off, rel.Type, os, s, p, imageBase);
449     break;
450   case ARM64:
451   case ARM64EC:
452   case ARM64X:
453     applyRelARM64(off, rel.Type, os, s, p, imageBase);
454     break;
455   default:
456     llvm_unreachable("unknown machine type");
457   }
458 }
459 
460 // Defend against unsorted relocations. This may be overly conservative.
461 void SectionChunk::sortRelocations() {
462   auto cmpByVa = [](const coff_relocation &l, const coff_relocation &r) {
463     return l.VirtualAddress < r.VirtualAddress;
464   };
465   if (llvm::is_sorted(getRelocs(), cmpByVa))
466     return;
467   warn("some relocations in " + file->getName() + " are not sorted");
468   MutableArrayRef<coff_relocation> newRelocs(
469       bAlloc().Allocate<coff_relocation>(relocsSize), relocsSize);
470   memcpy(newRelocs.data(), relocsData, relocsSize * sizeof(coff_relocation));
471   llvm::sort(newRelocs, cmpByVa);
472   setRelocs(newRelocs);
473 }
474 
475 // Similar to writeTo, but suitable for relocating a subsection of the overall
476 // section.
477 void SectionChunk::writeAndRelocateSubsection(ArrayRef<uint8_t> sec,
478                                               ArrayRef<uint8_t> subsec,
479                                               uint32_t &nextRelocIndex,
480                                               uint8_t *buf) const {
481   assert(!subsec.empty() && !sec.empty());
482   assert(sec.begin() <= subsec.begin() && subsec.end() <= sec.end() &&
483          "subsection is not part of this section");
484   size_t vaBegin = std::distance(sec.begin(), subsec.begin());
485   size_t vaEnd = std::distance(sec.begin(), subsec.end());
486   memcpy(buf, subsec.data(), subsec.size());
487   for (; nextRelocIndex < relocsSize; ++nextRelocIndex) {
488     const coff_relocation &rel = relocsData[nextRelocIndex];
489     // Only apply relocations that apply to this subsection. These checks
490     // assume that all subsections completely contain their relocations.
491     // Relocations must not straddle the beginning or end of a subsection.
492     if (rel.VirtualAddress < vaBegin)
493       continue;
494     if (rel.VirtualAddress + 1 >= vaEnd)
495       break;
496     applyRelocation(&buf[rel.VirtualAddress - vaBegin], rel);
497   }
498 }
499 
500 void SectionChunk::addAssociative(SectionChunk *child) {
501   // Insert the child section into the list of associated children. Keep the
502   // list ordered by section name so that ICF does not depend on section order.
503   assert(child->assocChildren == nullptr &&
504          "associated sections cannot have their own associated children");
505   SectionChunk *prev = this;
506   SectionChunk *next = assocChildren;
507   for (; next != nullptr; prev = next, next = next->assocChildren) {
508     if (next->getSectionName() <= child->getSectionName())
509       break;
510   }
511 
512   // Insert child between prev and next.
513   assert(prev->assocChildren == next);
514   prev->assocChildren = child;
515   child->assocChildren = next;
516 }
517 
518 static uint8_t getBaserelType(const coff_relocation &rel,
519                               llvm::COFF::MachineTypes machine) {
520   switch (machine) {
521   case AMD64:
522     if (rel.Type == IMAGE_REL_AMD64_ADDR64)
523       return IMAGE_REL_BASED_DIR64;
524     if (rel.Type == IMAGE_REL_AMD64_ADDR32)
525       return IMAGE_REL_BASED_HIGHLOW;
526     return IMAGE_REL_BASED_ABSOLUTE;
527   case I386:
528     if (rel.Type == IMAGE_REL_I386_DIR32)
529       return IMAGE_REL_BASED_HIGHLOW;
530     return IMAGE_REL_BASED_ABSOLUTE;
531   case ARMNT:
532     if (rel.Type == IMAGE_REL_ARM_ADDR32)
533       return IMAGE_REL_BASED_HIGHLOW;
534     if (rel.Type == IMAGE_REL_ARM_MOV32T)
535       return IMAGE_REL_BASED_ARM_MOV32T;
536     return IMAGE_REL_BASED_ABSOLUTE;
537   case ARM64:
538   case ARM64EC:
539   case ARM64X:
540     if (rel.Type == IMAGE_REL_ARM64_ADDR64)
541       return IMAGE_REL_BASED_DIR64;
542     return IMAGE_REL_BASED_ABSOLUTE;
543   default:
544     llvm_unreachable("unknown machine type");
545   }
546 }
547 
548 // Windows-specific.
549 // Collect all locations that contain absolute addresses, which need to be
550 // fixed by the loader if load-time relocation is needed.
551 // Only called when base relocation is enabled.
552 void SectionChunk::getBaserels(std::vector<Baserel> *res) {
553   for (const coff_relocation &rel : getRelocs()) {
554     uint8_t ty = getBaserelType(rel, file->ctx.config.machine);
555     if (ty == IMAGE_REL_BASED_ABSOLUTE)
556       continue;
557     Symbol *target = file->getSymbol(rel.SymbolTableIndex);
558     if (!target || isa<DefinedAbsolute>(target))
559       continue;
560     res->emplace_back(rva + rel.VirtualAddress, ty);
561   }
562 }
563 
564 // MinGW specific.
565 // Check whether a static relocation of type Type can be deferred and
566 // handled at runtime as a pseudo relocation (for references to a module
567 // local variable, which turned out to actually need to be imported from
568 // another DLL) This returns the size the relocation is supposed to update,
569 // in bits, or 0 if the relocation cannot be handled as a runtime pseudo
570 // relocation.
571 static int getRuntimePseudoRelocSize(uint16_t type,
572                                      llvm::COFF::MachineTypes machine) {
573   // Relocations that either contain an absolute address, or a plain
574   // relative offset, since the runtime pseudo reloc implementation
575   // adds 8/16/32/64 bit values to a memory address.
576   //
577   // Given a pseudo relocation entry,
578   //
579   // typedef struct {
580   //   DWORD sym;
581   //   DWORD target;
582   //   DWORD flags;
583   // } runtime_pseudo_reloc_item_v2;
584   //
585   // the runtime relocation performs this adjustment:
586   //     *(base + .target) += *(base + .sym) - (base + .sym)
587   //
588   // This works for both absolute addresses (IMAGE_REL_*_ADDR32/64,
589   // IMAGE_REL_I386_DIR32, where the memory location initially contains
590   // the address of the IAT slot, and for relative addresses (IMAGE_REL*_REL32),
591   // where the memory location originally contains the relative offset to the
592   // IAT slot.
593   //
594   // This requires the target address to be writable, either directly out of
595   // the image, or temporarily changed at runtime with VirtualProtect.
596   // Since this only operates on direct address values, it doesn't work for
597   // ARM/ARM64 relocations, other than the plain ADDR32/ADDR64 relocations.
598   switch (machine) {
599   case AMD64:
600     switch (type) {
601     case IMAGE_REL_AMD64_ADDR64:
602       return 64;
603     case IMAGE_REL_AMD64_ADDR32:
604     case IMAGE_REL_AMD64_REL32:
605     case IMAGE_REL_AMD64_REL32_1:
606     case IMAGE_REL_AMD64_REL32_2:
607     case IMAGE_REL_AMD64_REL32_3:
608     case IMAGE_REL_AMD64_REL32_4:
609     case IMAGE_REL_AMD64_REL32_5:
610       return 32;
611     default:
612       return 0;
613     }
614   case I386:
615     switch (type) {
616     case IMAGE_REL_I386_DIR32:
617     case IMAGE_REL_I386_REL32:
618       return 32;
619     default:
620       return 0;
621     }
622   case ARMNT:
623     switch (type) {
624     case IMAGE_REL_ARM_ADDR32:
625       return 32;
626     default:
627       return 0;
628     }
629   case ARM64:
630     switch (type) {
631     case IMAGE_REL_ARM64_ADDR64:
632       return 64;
633     case IMAGE_REL_ARM64_ADDR32:
634       return 32;
635     default:
636       return 0;
637     }
638   default:
639     llvm_unreachable("unknown machine type");
640   }
641 }
642 
643 // MinGW specific.
644 // Append information to the provided vector about all relocations that
645 // need to be handled at runtime as runtime pseudo relocations (references
646 // to a module local variable, which turned out to actually need to be
647 // imported from another DLL).
648 void SectionChunk::getRuntimePseudoRelocs(
649     std::vector<RuntimePseudoReloc> &res) {
650   for (const coff_relocation &rel : getRelocs()) {
651     auto *target =
652         dyn_cast_or_null<Defined>(file->getSymbol(rel.SymbolTableIndex));
653     if (!target || !target->isRuntimePseudoReloc)
654       continue;
655     int sizeInBits =
656         getRuntimePseudoRelocSize(rel.Type, file->ctx.config.machine);
657     if (sizeInBits == 0) {
658       error("unable to automatically import from " + target->getName() +
659             " with relocation type " +
660             file->getCOFFObj()->getRelocationTypeName(rel.Type) + " in " +
661             toString(file));
662       continue;
663     }
664     int addressSizeInBits = file->ctx.config.is64() ? 64 : 32;
665     if (sizeInBits < addressSizeInBits) {
666       warn("runtime pseudo relocation in " + toString(file) + " against " +
667            "symbol " + target->getName() + " is too narrow (only " +
668            Twine(sizeInBits) + " bits wide); this can fail at runtime " +
669            "depending on memory layout");
670     }
671     // sizeInBits is used to initialize the Flags field; currently no
672     // other flags are defined.
673     res.emplace_back(target, this, rel.VirtualAddress, sizeInBits);
674   }
675 }
676 
677 bool SectionChunk::isCOMDAT() const {
678   return header->Characteristics & IMAGE_SCN_LNK_COMDAT;
679 }
680 
681 void SectionChunk::printDiscardedMessage() const {
682   // Removed by dead-stripping. If it's removed by ICF, ICF already
683   // printed out the name, so don't repeat that here.
684   if (sym && this == repl)
685     log("Discarded " + sym->getName());
686 }
687 
688 StringRef SectionChunk::getDebugName() const {
689   if (sym)
690     return sym->getName();
691   return "";
692 }
693 
694 ArrayRef<uint8_t> SectionChunk::getContents() const {
695   ArrayRef<uint8_t> a;
696   cantFail(file->getCOFFObj()->getSectionContents(header, a));
697   return a;
698 }
699 
700 ArrayRef<uint8_t> SectionChunk::consumeDebugMagic() {
701   assert(isCodeView());
702   return consumeDebugMagic(getContents(), getSectionName());
703 }
704 
705 ArrayRef<uint8_t> SectionChunk::consumeDebugMagic(ArrayRef<uint8_t> data,
706                                                   StringRef sectionName) {
707   if (data.empty())
708     return {};
709 
710   // First 4 bytes are section magic.
711   if (data.size() < 4)
712     fatal("the section is too short: " + sectionName);
713 
714   if (!sectionName.starts_with(".debug$"))
715     fatal("invalid section: " + sectionName);
716 
717   uint32_t magic = support::endian::read32le(data.data());
718   uint32_t expectedMagic = sectionName == ".debug$H"
719                                ? DEBUG_HASHES_SECTION_MAGIC
720                                : DEBUG_SECTION_MAGIC;
721   if (magic != expectedMagic) {
722     warn("ignoring section " + sectionName + " with unrecognized magic 0x" +
723          utohexstr(magic));
724     return {};
725   }
726   return data.slice(4);
727 }
728 
729 SectionChunk *SectionChunk::findByName(ArrayRef<SectionChunk *> sections,
730                                        StringRef name) {
731   for (SectionChunk *c : sections)
732     if (c->getSectionName() == name)
733       return c;
734   return nullptr;
735 }
736 
737 void SectionChunk::replace(SectionChunk *other) {
738   p2Align = std::max(p2Align, other->p2Align);
739   other->repl = repl;
740   other->live = false;
741 }
742 
743 uint32_t SectionChunk::getSectionNumber() const {
744   DataRefImpl r;
745   r.p = reinterpret_cast<uintptr_t>(header);
746   SectionRef s(r, file->getCOFFObj());
747   return s.getIndex() + 1;
748 }
749 
750 CommonChunk::CommonChunk(const COFFSymbolRef s) : sym(s) {
751   // The value of a common symbol is its size. Align all common symbols smaller
752   // than 32 bytes naturally, i.e. round the size up to the next power of two.
753   // This is what MSVC link.exe does.
754   setAlignment(std::min(32U, uint32_t(PowerOf2Ceil(sym.getValue()))));
755   hasData = false;
756 }
757 
758 uint32_t CommonChunk::getOutputCharacteristics() const {
759   return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
760          IMAGE_SCN_MEM_WRITE;
761 }
762 
763 void StringChunk::writeTo(uint8_t *buf) const {
764   memcpy(buf, str.data(), str.size());
765   buf[str.size()] = '\0';
766 }
767 
768 ImportThunkChunkX64::ImportThunkChunkX64(COFFLinkerContext &ctx, Defined *s)
769     : ImportThunkChunk(ctx, s) {
770   // Intel Optimization Manual says that all branch targets
771   // should be 16-byte aligned. MSVC linker does this too.
772   setAlignment(16);
773 }
774 
775 void ImportThunkChunkX64::writeTo(uint8_t *buf) const {
776   memcpy(buf, importThunkX86, sizeof(importThunkX86));
777   // The first two bytes is a JMP instruction. Fill its operand.
778   write32le(buf + 2, impSymbol->getRVA() - rva - getSize());
779 }
780 
781 void ImportThunkChunkX86::getBaserels(std::vector<Baserel> *res) {
782   res->emplace_back(getRVA() + 2, ctx.config.machine);
783 }
784 
785 void ImportThunkChunkX86::writeTo(uint8_t *buf) const {
786   memcpy(buf, importThunkX86, sizeof(importThunkX86));
787   // The first two bytes is a JMP instruction. Fill its operand.
788   write32le(buf + 2, impSymbol->getRVA() + ctx.config.imageBase);
789 }
790 
791 void ImportThunkChunkARM::getBaserels(std::vector<Baserel> *res) {
792   res->emplace_back(getRVA(), IMAGE_REL_BASED_ARM_MOV32T);
793 }
794 
795 void ImportThunkChunkARM::writeTo(uint8_t *buf) const {
796   memcpy(buf, importThunkARM, sizeof(importThunkARM));
797   // Fix mov.w and mov.t operands.
798   applyMOV32T(buf, impSymbol->getRVA() + ctx.config.imageBase);
799 }
800 
801 void ImportThunkChunkARM64::writeTo(uint8_t *buf) const {
802   int64_t off = impSymbol->getRVA() & 0xfff;
803   memcpy(buf, importThunkARM64, sizeof(importThunkARM64));
804   applyArm64Addr(buf, impSymbol->getRVA(), rva, 12);
805   applyArm64Ldr(buf + 4, off);
806 }
807 
808 // A Thumb2, PIC, non-interworking range extension thunk.
809 const uint8_t armThunk[] = {
810     0x40, 0xf2, 0x00, 0x0c, // P:  movw ip,:lower16:S - (P + (L1-P) + 4)
811     0xc0, 0xf2, 0x00, 0x0c, //     movt ip,:upper16:S - (P + (L1-P) + 4)
812     0xe7, 0x44,             // L1: add  pc, ip
813 };
814 
815 size_t RangeExtensionThunkARM::getSize() const {
816   assert(ctx.config.machine == ARMNT);
817   (void)&ctx;
818   return sizeof(armThunk);
819 }
820 
821 void RangeExtensionThunkARM::writeTo(uint8_t *buf) const {
822   assert(ctx.config.machine == ARMNT);
823   uint64_t offset = target->getRVA() - rva - 12;
824   memcpy(buf, armThunk, sizeof(armThunk));
825   applyMOV32T(buf, uint32_t(offset));
826 }
827 
828 // A position independent ARM64 adrp+add thunk, with a maximum range of
829 // +/- 4 GB, which is enough for any PE-COFF.
830 const uint8_t arm64Thunk[] = {
831     0x10, 0x00, 0x00, 0x90, // adrp x16, Dest
832     0x10, 0x02, 0x00, 0x91, // add  x16, x16, :lo12:Dest
833     0x00, 0x02, 0x1f, 0xd6, // br   x16
834 };
835 
836 size_t RangeExtensionThunkARM64::getSize() const {
837   assert(ctx.config.machine == ARM64);
838   (void)&ctx;
839   return sizeof(arm64Thunk);
840 }
841 
842 void RangeExtensionThunkARM64::writeTo(uint8_t *buf) const {
843   assert(ctx.config.machine == ARM64);
844   memcpy(buf, arm64Thunk, sizeof(arm64Thunk));
845   applyArm64Addr(buf + 0, target->getRVA(), rva, 12);
846   applyArm64Imm(buf + 4, target->getRVA() & 0xfff, 0);
847 }
848 
849 LocalImportChunk::LocalImportChunk(COFFLinkerContext &c, Defined *s)
850     : sym(s), ctx(c) {
851   setAlignment(ctx.config.wordsize);
852 }
853 
854 void LocalImportChunk::getBaserels(std::vector<Baserel> *res) {
855   res->emplace_back(getRVA(), ctx.config.machine);
856 }
857 
858 size_t LocalImportChunk::getSize() const { return ctx.config.wordsize; }
859 
860 void LocalImportChunk::writeTo(uint8_t *buf) const {
861   if (ctx.config.is64()) {
862     write64le(buf, sym->getRVA() + ctx.config.imageBase);
863   } else {
864     write32le(buf, sym->getRVA() + ctx.config.imageBase);
865   }
866 }
867 
868 void RVATableChunk::writeTo(uint8_t *buf) const {
869   ulittle32_t *begin = reinterpret_cast<ulittle32_t *>(buf);
870   size_t cnt = 0;
871   for (const ChunkAndOffset &co : syms)
872     begin[cnt++] = co.inputChunk->getRVA() + co.offset;
873   llvm::sort(begin, begin + cnt);
874   assert(std::unique(begin, begin + cnt) == begin + cnt &&
875          "RVA tables should be de-duplicated");
876 }
877 
878 void RVAFlagTableChunk::writeTo(uint8_t *buf) const {
879   struct RVAFlag {
880     ulittle32_t rva;
881     uint8_t flag;
882   };
883   auto flags =
884       MutableArrayRef(reinterpret_cast<RVAFlag *>(buf), syms.size());
885   for (auto t : zip(syms, flags)) {
886     const auto &sym = std::get<0>(t);
887     auto &flag = std::get<1>(t);
888     flag.rva = sym.inputChunk->getRVA() + sym.offset;
889     flag.flag = 0;
890   }
891   llvm::sort(flags,
892              [](const RVAFlag &a, const RVAFlag &b) { return a.rva < b.rva; });
893   assert(llvm::unique(flags, [](const RVAFlag &a,
894                                 const RVAFlag &b) { return a.rva == b.rva; }) ==
895              flags.end() &&
896          "RVA tables should be de-duplicated");
897 }
898 
899 // MinGW specific, for the "automatic import of variables from DLLs" feature.
900 size_t PseudoRelocTableChunk::getSize() const {
901   if (relocs.empty())
902     return 0;
903   return 12 + 12 * relocs.size();
904 }
905 
906 // MinGW specific.
907 void PseudoRelocTableChunk::writeTo(uint8_t *buf) const {
908   if (relocs.empty())
909     return;
910 
911   ulittle32_t *table = reinterpret_cast<ulittle32_t *>(buf);
912   // This is the list header, to signal the runtime pseudo relocation v2
913   // format.
914   table[0] = 0;
915   table[1] = 0;
916   table[2] = 1;
917 
918   size_t idx = 3;
919   for (const RuntimePseudoReloc &rpr : relocs) {
920     table[idx + 0] = rpr.sym->getRVA();
921     table[idx + 1] = rpr.target->getRVA() + rpr.targetOffset;
922     table[idx + 2] = rpr.flags;
923     idx += 3;
924   }
925 }
926 
927 // Windows-specific. This class represents a block in .reloc section.
928 // The format is described here.
929 //
930 // On Windows, each DLL is linked against a fixed base address and
931 // usually loaded to that address. However, if there's already another
932 // DLL that overlaps, the loader has to relocate it. To do that, DLLs
933 // contain .reloc sections which contain offsets that need to be fixed
934 // up at runtime. If the loader finds that a DLL cannot be loaded to its
935 // desired base address, it loads it to somewhere else, and add <actual
936 // base address> - <desired base address> to each offset that is
937 // specified by the .reloc section. In ELF terms, .reloc sections
938 // contain relative relocations in REL format (as opposed to RELA.)
939 //
940 // This already significantly reduces the size of relocations compared
941 // to ELF .rel.dyn, but Windows does more to reduce it (probably because
942 // it was invented for PCs in the late '80s or early '90s.)  Offsets in
943 // .reloc are grouped by page where the page size is 12 bits, and
944 // offsets sharing the same page address are stored consecutively to
945 // represent them with less space. This is very similar to the page
946 // table which is grouped by (multiple stages of) pages.
947 //
948 // For example, let's say we have 0x00030, 0x00500, 0x00700, 0x00A00,
949 // 0x20004, and 0x20008 in a .reloc section for x64. The uppermost 4
950 // bits have a type IMAGE_REL_BASED_DIR64 or 0xA. In the section, they
951 // are represented like this:
952 //
953 //   0x00000  -- page address (4 bytes)
954 //   16       -- size of this block (4 bytes)
955 //     0xA030 -- entries (2 bytes each)
956 //     0xA500
957 //     0xA700
958 //     0xAA00
959 //   0x20000  -- page address (4 bytes)
960 //   12       -- size of this block (4 bytes)
961 //     0xA004 -- entries (2 bytes each)
962 //     0xA008
963 //
964 // Usually we have a lot of relocations for each page, so the number of
965 // bytes for one .reloc entry is close to 2 bytes on average.
966 BaserelChunk::BaserelChunk(uint32_t page, Baserel *begin, Baserel *end) {
967   // Block header consists of 4 byte page RVA and 4 byte block size.
968   // Each entry is 2 byte. Last entry may be padding.
969   data.resize(alignTo((end - begin) * 2 + 8, 4));
970   uint8_t *p = data.data();
971   write32le(p, page);
972   write32le(p + 4, data.size());
973   p += 8;
974   for (Baserel *i = begin; i != end; ++i) {
975     write16le(p, (i->type << 12) | (i->rva - page));
976     p += 2;
977   }
978 }
979 
980 void BaserelChunk::writeTo(uint8_t *buf) const {
981   memcpy(buf, data.data(), data.size());
982 }
983 
984 uint8_t Baserel::getDefaultType(llvm::COFF::MachineTypes machine) {
985   switch (machine) {
986   case AMD64:
987   case ARM64:
988     return IMAGE_REL_BASED_DIR64;
989   case I386:
990   case ARMNT:
991     return IMAGE_REL_BASED_HIGHLOW;
992   default:
993     llvm_unreachable("unknown machine type");
994   }
995 }
996 
997 MergeChunk::MergeChunk(uint32_t alignment)
998     : builder(StringTableBuilder::RAW, llvm::Align(alignment)) {
999   setAlignment(alignment);
1000 }
1001 
1002 void MergeChunk::addSection(COFFLinkerContext &ctx, SectionChunk *c) {
1003   assert(isPowerOf2_32(c->getAlignment()));
1004   uint8_t p2Align = llvm::Log2_32(c->getAlignment());
1005   assert(p2Align < std::size(ctx.mergeChunkInstances));
1006   auto *&mc = ctx.mergeChunkInstances[p2Align];
1007   if (!mc)
1008     mc = make<MergeChunk>(c->getAlignment());
1009   mc->sections.push_back(c);
1010 }
1011 
1012 void MergeChunk::finalizeContents() {
1013   assert(!finalized && "should only finalize once");
1014   for (SectionChunk *c : sections)
1015     if (c->live)
1016       builder.add(toStringRef(c->getContents()));
1017   builder.finalize();
1018   finalized = true;
1019 }
1020 
1021 void MergeChunk::assignSubsectionRVAs() {
1022   for (SectionChunk *c : sections) {
1023     if (!c->live)
1024       continue;
1025     size_t off = builder.getOffset(toStringRef(c->getContents()));
1026     c->setRVA(rva + off);
1027   }
1028 }
1029 
1030 uint32_t MergeChunk::getOutputCharacteristics() const {
1031   return IMAGE_SCN_MEM_READ | IMAGE_SCN_CNT_INITIALIZED_DATA;
1032 }
1033 
1034 size_t MergeChunk::getSize() const {
1035   return builder.getSize();
1036 }
1037 
1038 void MergeChunk::writeTo(uint8_t *buf) const {
1039   builder.write(buf);
1040 }
1041 
1042 // MinGW specific.
1043 size_t AbsolutePointerChunk::getSize() const { return ctx.config.wordsize; }
1044 
1045 void AbsolutePointerChunk::writeTo(uint8_t *buf) const {
1046   if (ctx.config.is64()) {
1047     write64le(buf, value);
1048   } else {
1049     write32le(buf, value);
1050   }
1051 }
1052 
1053 } // namespace lld::coff
1054