lld/COFF/Chunks.cpp

   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