contrib/llvm/tools/lld/COFF/Chunks.cpp

   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
  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.
  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.
  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
  64 static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); }
  65 static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); }
  66 static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); }
  67 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | 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.
  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
  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
  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
 104 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
 124 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
 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
 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
 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
 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
 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
 187 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.
 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).
 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.
 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
 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
 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
 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
 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
 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
 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
 295 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
 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
 345 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
 412 void SectionChunk::addAssociative(SectionChunk *Child) {
 413   AssocChildren.push_back(Child);
 414 }
 415
 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.
 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.
 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).
 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
 565 bool SectionChunk::hasData() const {
 566   return !(Header->Characteristics & IMAGE_SCN_CNT_UNINITIALIZED_DATA);
 567 }
 568
 569 uint32_t SectionChunk::getOutputCharacteristics() const {
 570   return Header->Characteristics & (PermMask | TypeMask);
 571 }
 572
 573 bool SectionChunk::isCOMDAT() const {
 574   return Header->Characteristics & IMAGE_SCN_LNK_COMDAT;
 575 }
 576
 577 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
 584 StringRef SectionChunk::getDebugName() {
 585   if (Sym)
 586     return Sym->getName();
 587   return "";
 588 }
 589
 590 ArrayRef<uint8_t> SectionChunk::getContents() const {
 591   ArrayRef<uint8_t> A;
 592   File->getCOFFObj()->getSectionContents(Header, A);
 593   return A;
 594 }
 595
 596 void SectionChunk::replace(SectionChunk *Other) {
 597   Alignment = std::max(Alignment, Other->Alignment);
 598   Other->Repl = Repl;
 599   Other->Live = false;
 600 }
 601
 602 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
 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
 615 uint32_t CommonChunk::getOutputCharacteristics() const {
 616   return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
 617          IMAGE_SCN_MEM_WRITE;
 618 }
 619
 620 void StringChunk::writeTo(uint8_t *Buf) const {
 621   memcpy(Buf + OutputSectionOff, Str.data(), Str.size());
 622   Buf[OutputSectionOff + Str.size()] = '\0';
 623 }
 624
 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
 631 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
 637 void ImportThunkChunkX86::getBaserels(std::vector<Baserel> *Res) {
 638   Res->emplace_back(getRVA() + 2);
 639 }
 640
 641 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
 648 void ImportThunkChunkARM::getBaserels(std::vector<Baserel> *Res) {
 649   Res->emplace_back(getRVA(), IMAGE_REL_BASED_ARM_MOV32T);
 650 }
 651
 652 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
 658 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
 672 size_t RangeExtensionThunkARM::getSize() const {
 673   assert(Config->Machine == ARMNT);
 674   return sizeof(ArmThunk);
 675 }
 676
 677 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
 692 size_t RangeExtensionThunkARM64::getSize() const {
 693   assert(Config->Machine == ARM64);
 694   return sizeof(Arm64Thunk);
 695 }
 696
 697 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
 704 void LocalImportChunk::getBaserels(std::vector<Baserel> *Res) {
 705   Res->emplace_back(getRVA());
 706 }
 707
 708 size_t LocalImportChunk::getSize() const { return Config->Wordsize; }
 709
 710 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
 718 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.
 729 size_t PseudoRelocTableChunk::getSize() const {
 730   if (Relocs.empty())
 731     return 0;
 732   return 12 + 12 * Relocs.size();
 733 }
 734
 735 // MinGW specific.
 736 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.
 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
 809 void BaserelChunk::writeTo(uint8_t *Buf) const {
 810   memcpy(Buf + OutputSectionOff, Data.data(), Data.size());
 811 }
 812
 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
 828 MergeChunk::MergeChunk(uint32_t Alignment)
 829     : Builder(StringTableBuilder::RAW, Alignment) {
 830   this->Alignment = Alignment;
 831 }
 832
 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
 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
 859 uint32_t MergeChunk::getOutputCharacteristics() const {
 860   return IMAGE_SCN_MEM_READ | IMAGE_SCN_CNT_INITIALIZED_DATA;
 861 }
 862
 863 size_t MergeChunk::getSize() const {
 864   return Builder.getSize();
 865 }
 866
 867 void MergeChunk::writeTo(uint8_t *Buf) const {
 868   Builder.write(Buf + OutputSectionOff);
 869 }
 870
 871 // MinGW specific.
 872 size_t AbsolutePointerChunk::getSize() const { return Config->Wordsize; }
 873
 874 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