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 "lld/Common/ErrorHandler.h"
  15 #include "llvm/ADT/Twine.h"
  16 #include "llvm/BinaryFormat/COFF.h"
  17 #include "llvm/Object/COFF.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/Support/Endian.h"
  20 #include "llvm/Support/raw_ostream.h"
  21 #include <algorithm>
  22
  23 using namespace llvm;
  24 using namespace llvm::object;
  25 using namespace llvm::support::endian;
  26 using namespace llvm::COFF;
  27 using llvm::support::ulittle32_t;
  28
  29 namespace lld {
  30 namespace coff {
  31
  32 SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
  33     : Chunk(SectionKind), Repl(this), Header(H), File(F),
  34       Relocs(File->getCOFFObj()->getRelocations(Header)),
  35       NumRelocs(std::distance(Relocs.begin(), Relocs.end())) {
  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 static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); }
  49 static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); }
  50 static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); }
  51 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | V); }
  52 static void or32(uint8_t *P, uint32_t V) { write32le(P, read32le(P) | V); }
  53
  54 static void applySecRel(const SectionChunk *Sec, uint8_t *Off,
  55                         OutputSection *OS, uint64_t S) {
  56   if (!OS) {
  57     if (Sec->isCodeView())
  58       return;
  59     fatal("SECREL relocation cannot be applied to absolute symbols");
  60   }
  61   uint64_t SecRel = S - OS->getRVA();
  62   if (SecRel > UINT32_MAX) {
  63     error("overflow in SECREL relocation in section: " + Sec->getSectionName());
  64     return;
  65   }
  66   add32(Off, SecRel);
  67 }
  68
  69 static void applySecIdx(uint8_t *Off, OutputSection *OS) {
  70   // If we have no output section, this must be an absolute symbol. Use the
  71   // sentinel absolute symbol section index.
  72   uint16_t SecIdx = OS ? OS->SectionIndex : DefinedAbsolute::OutputSectionIndex;
  73   add16(Off, SecIdx);
  74 }
  75
  76 void SectionChunk::applyRelX64(uint8_t *Off, uint16_t Type, OutputSection *OS,
  77                                uint64_t S, uint64_t P) const {
  78   switch (Type) {
  79   case IMAGE_REL_AMD64_ADDR32:   add32(Off, S + Config->ImageBase); break;
  80   case IMAGE_REL_AMD64_ADDR64:   add64(Off, S + Config->ImageBase); break;
  81   case IMAGE_REL_AMD64_ADDR32NB: add32(Off, S); break;
  82   case IMAGE_REL_AMD64_REL32:    add32(Off, S - P - 4); break;
  83   case IMAGE_REL_AMD64_REL32_1:  add32(Off, S - P - 5); break;
  84   case IMAGE_REL_AMD64_REL32_2:  add32(Off, S - P - 6); break;
  85   case IMAGE_REL_AMD64_REL32_3:  add32(Off, S - P - 7); break;
  86   case IMAGE_REL_AMD64_REL32_4:  add32(Off, S - P - 8); break;
  87   case IMAGE_REL_AMD64_REL32_5:  add32(Off, S - P - 9); break;
  88   case IMAGE_REL_AMD64_SECTION:  applySecIdx(Off, OS); break;
  89   case IMAGE_REL_AMD64_SECREL:   applySecRel(this, Off, OS, S); break;
  90   default:
  91     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
  92   }
  93 }
  94
  95 void SectionChunk::applyRelX86(uint8_t *Off, uint16_t Type, OutputSection *OS,
  96                                uint64_t S, uint64_t P) const {
  97   switch (Type) {
  98   case IMAGE_REL_I386_ABSOLUTE: break;
  99   case IMAGE_REL_I386_DIR32:    add32(Off, S + Config->ImageBase); break;
 100   case IMAGE_REL_I386_DIR32NB:  add32(Off, S); break;
 101   case IMAGE_REL_I386_REL32:    add32(Off, S - P - 4); break;
 102   case IMAGE_REL_I386_SECTION:  applySecIdx(Off, OS); break;
 103   case IMAGE_REL_I386_SECREL:   applySecRel(this, Off, OS, S); break;
 104   default:
 105     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
 106   }
 107 }
 108
 109 static void applyMOV(uint8_t *Off, uint16_t V) {
 110   write16le(Off, (read16le(Off) & 0xfbf0) | ((V & 0x800) >> 1) | ((V >> 12) & 0xf));
 111   write16le(Off + 2, (read16le(Off + 2) & 0x8f00) | ((V & 0x700) << 4) | (V & 0xff));
 112 }
 113
 114 static uint16_t readMOV(uint8_t *Off) {
 115   uint16_t Opcode1 = read16le(Off);
 116   uint16_t Opcode2 = read16le(Off + 2);
 117   uint16_t Imm = (Opcode2 & 0x00ff) | ((Opcode2 >> 4) & 0x0700);
 118   Imm |= ((Opcode1 << 1) & 0x0800) | ((Opcode1 & 0x000f) << 12);
 119   return Imm;
 120 }
 121
 122 void applyMOV32T(uint8_t *Off, uint32_t V) {
 123   uint16_t ImmW = readMOV(Off);     // read MOVW operand
 124   uint16_t ImmT = readMOV(Off + 4); // read MOVT operand
 125   uint32_t Imm = ImmW | (ImmT << 16);
 126   V += Imm;                         // add the immediate offset
 127   applyMOV(Off, V);           // set MOVW operand
 128   applyMOV(Off + 4, V >> 16); // set MOVT operand
 129 }
 130
 131 static void applyBranch20T(uint8_t *Off, int32_t V) {
 132   if (!isInt<21>(V))
 133     fatal("relocation out of range");
 134   uint32_t S = V < 0 ? 1 : 0;
 135   uint32_t J1 = (V >> 19) & 1;
 136   uint32_t J2 = (V >> 18) & 1;
 137   or16(Off, (S << 10) | ((V >> 12) & 0x3f));
 138   or16(Off + 2, (J1 << 13) | (J2 << 11) | ((V >> 1) & 0x7ff));
 139 }
 140
 141 void applyBranch24T(uint8_t *Off, int32_t V) {
 142   if (!isInt<25>(V))
 143     fatal("relocation out of range");
 144   uint32_t S = V < 0 ? 1 : 0;
 145   uint32_t J1 = ((~V >> 23) & 1) ^ S;
 146   uint32_t J2 = ((~V >> 22) & 1) ^ S;
 147   or16(Off, (S << 10) | ((V >> 12) & 0x3ff));
 148   // Clear out the J1 and J2 bits which may be set.
 149   write16le(Off + 2, (read16le(Off + 2) & 0xd000) | (J1 << 13) | (J2 << 11) | ((V >> 1) & 0x7ff));
 150 }
 151
 152 void SectionChunk::applyRelARM(uint8_t *Off, uint16_t Type, OutputSection *OS,
 153                                uint64_t S, uint64_t P) const {
 154   // Pointer to thumb code must have the LSB set.
 155   uint64_t SX = S;
 156   if (OS && (OS->getPermissions() & IMAGE_SCN_MEM_EXECUTE))
 157     SX |= 1;
 158   switch (Type) {
 159   case IMAGE_REL_ARM_ADDR32:    add32(Off, SX + Config->ImageBase); break;
 160   case IMAGE_REL_ARM_ADDR32NB:  add32(Off, SX); break;
 161   case IMAGE_REL_ARM_MOV32T:    applyMOV32T(Off, SX + Config->ImageBase); break;
 162   case IMAGE_REL_ARM_BRANCH20T: applyBranch20T(Off, SX - P - 4); break;
 163   case IMAGE_REL_ARM_BRANCH24T: applyBranch24T(Off, SX - P - 4); break;
 164   case IMAGE_REL_ARM_BLX23T:    applyBranch24T(Off, SX - P - 4); break;
 165   case IMAGE_REL_ARM_SECTION:   applySecIdx(Off, OS); break;
 166   case IMAGE_REL_ARM_SECREL:    applySecRel(this, Off, OS, S); break;
 167   default:
 168     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
 169   }
 170 }
 171
 172 // Interpret the existing immediate value as a byte offset to the
 173 // target symbol, then update the instruction with the immediate as
 174 // the page offset from the current instruction to the target.
 175 static void applyArm64Addr(uint8_t *Off, uint64_t S, uint64_t P) {
 176   uint32_t Orig = read32le(Off);
 177   uint64_t Imm = ((Orig >> 29) & 0x3) | ((Orig >> 3) & 0x1FFFFC);
 178   S += Imm;
 179   Imm = (S >> 12) - (P >> 12);
 180   uint32_t ImmLo = (Imm & 0x3) << 29;
 181   uint32_t ImmHi = (Imm & 0x1FFFFC) << 3;
 182   uint64_t Mask = (0x3 << 29) | (0x1FFFFC << 3);
 183   write32le(Off, (Orig & ~Mask) | ImmLo | ImmHi);
 184 }
 185
 186 // Update the immediate field in a AARCH64 ldr, str, and add instruction.
 187 // Optionally limit the range of the written immediate by one or more bits
 188 // (RangeLimit).
 189 static void applyArm64Imm(uint8_t *Off, uint64_t Imm, uint32_t RangeLimit) {
 190   uint32_t Orig = read32le(Off);
 191   Imm += (Orig >> 10) & 0xFFF;
 192   Orig &= ~(0xFFF << 10);
 193   write32le(Off, Orig | ((Imm & (0xFFF >> RangeLimit)) << 10));
 194 }
 195
 196 // Add the 12 bit page offset to the existing immediate.
 197 // Ldr/str instructions store the opcode immediate scaled
 198 // by the load/store size (giving a larger range for larger
 199 // loads/stores). The immediate is always (both before and after
 200 // fixing up the relocation) stored scaled similarly.
 201 // Even if larger loads/stores have a larger range, limit the
 202 // effective offset to 12 bit, since it is intended to be a
 203 // page offset.
 204 static void applyArm64Ldr(uint8_t *Off, uint64_t Imm) {
 205   uint32_t Orig = read32le(Off);
 206   uint32_t Size = Orig >> 30;
 207   // 0x04000000 indicates SIMD/FP registers
 208   // 0x00800000 indicates 128 bit
 209   if ((Orig & 0x4800000) == 0x4800000)
 210     Size += 4;
 211   if ((Imm & ((1 << Size) - 1)) != 0)
 212     fatal("misaligned ldr/str offset");
 213   applyArm64Imm(Off, Imm >> Size, Size);
 214 }
 215
 216 void SectionChunk::applyRelARM64(uint8_t *Off, uint16_t Type, OutputSection *OS,
 217                                  uint64_t S, uint64_t P) const {
 218   switch (Type) {
 219   case IMAGE_REL_ARM64_PAGEBASE_REL21: applyArm64Addr(Off, S, P); break;
 220   case IMAGE_REL_ARM64_PAGEOFFSET_12A: applyArm64Imm(Off, S & 0xfff, 0); break;
 221   case IMAGE_REL_ARM64_PAGEOFFSET_12L: applyArm64Ldr(Off, S & 0xfff); break;
 222   case IMAGE_REL_ARM64_BRANCH26:       or32(Off, ((S - P) & 0x0FFFFFFC) >> 2); break;
 223   case IMAGE_REL_ARM64_ADDR32:         add32(Off, S + Config->ImageBase); break;
 224   case IMAGE_REL_ARM64_ADDR32NB:       add32(Off, S); break;
 225   case IMAGE_REL_ARM64_ADDR64:         add64(Off, S + Config->ImageBase); break;
 226   case IMAGE_REL_ARM64_SECREL:         applySecRel(this, Off, OS, S); break;
 227   default:
 228     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
 229   }
 230 }
 231
 232 void SectionChunk::writeTo(uint8_t *Buf) const {
 233   if (!hasData())
 234     return;
 235   // Copy section contents from source object file to output file.
 236   ArrayRef<uint8_t> A = getContents();
 237   memcpy(Buf + OutputSectionOff, A.data(), A.size());
 238
 239   // Apply relocations.
 240   size_t InputSize = getSize();
 241   for (const coff_relocation &Rel : Relocs) {
 242     // Check for an invalid relocation offset. This check isn't perfect, because
 243     // we don't have the relocation size, which is only known after checking the
 244     // machine and relocation type. As a result, a relocation may overwrite the
 245     // beginning of the following input section.
 246     if (Rel.VirtualAddress >= InputSize)
 247       fatal("relocation points beyond the end of its parent section");
 248
 249     uint8_t *Off = Buf + OutputSectionOff + Rel.VirtualAddress;
 250
 251     // Get the output section of the symbol for this relocation.  The output
 252     // section is needed to compute SECREL and SECTION relocations used in debug
 253     // info.
 254     auto *Sym =
 255         dyn_cast_or_null<Defined>(File->getSymbol(Rel.SymbolTableIndex));
 256     if (!Sym) {
 257       if (isCodeView() || isDWARF())
 258         continue;
 259       // Symbols in early discarded sections are represented using null pointers,
 260       // so we need to retrieve the name from the object file.
 261       COFFSymbolRef Sym =
 262           check(File->getCOFFObj()->getSymbol(Rel.SymbolTableIndex));
 263       StringRef Name;
 264       File->getCOFFObj()->getSymbolName(Sym, Name);
 265       fatal("relocation against symbol in discarded section: " + Name);
 266     }
 267     Chunk *C = Sym->getChunk();
 268     OutputSection *OS = C ? C->getOutputSection() : nullptr;
 269
 270     // Only absolute and __ImageBase symbols lack an output section. For any
 271     // other symbol, this indicates that the chunk was discarded.  Normally
 272     // relocations against discarded sections are an error.  However, debug info
 273     // sections are not GC roots and can end up with these kinds of relocations.
 274     // Skip these relocations.
 275     if (!OS && !isa<DefinedAbsolute>(Sym) && !isa<DefinedSynthetic>(Sym)) {
 276       if (isCodeView() || isDWARF())
 277         continue;
 278       fatal("relocation against symbol in discarded section: " +
 279             Sym->getName());
 280     }
 281     uint64_t S = Sym->getRVA();
 282
 283     // Compute the RVA of the relocation for relative relocations.
 284     uint64_t P = RVA + Rel.VirtualAddress;
 285     switch (Config->Machine) {
 286     case AMD64:
 287       applyRelX64(Off, Rel.Type, OS, S, P);
 288       break;
 289     case I386:
 290       applyRelX86(Off, Rel.Type, OS, S, P);
 291       break;
 292     case ARMNT:
 293       applyRelARM(Off, Rel.Type, OS, S, P);
 294       break;
 295     case ARM64:
 296       applyRelARM64(Off, Rel.Type, OS, S, P);
 297       break;
 298     default:
 299       llvm_unreachable("unknown machine type");
 300     }
 301   }
 302 }
 303
 304 void SectionChunk::addAssociative(SectionChunk *Child) {
 305   AssocChildren.push_back(Child);
 306 }
 307
 308 static uint8_t getBaserelType(const coff_relocation &Rel) {
 309   switch (Config->Machine) {
 310   case AMD64:
 311     if (Rel.Type == IMAGE_REL_AMD64_ADDR64)
 312       return IMAGE_REL_BASED_DIR64;
 313     return IMAGE_REL_BASED_ABSOLUTE;
 314   case I386:
 315     if (Rel.Type == IMAGE_REL_I386_DIR32)
 316       return IMAGE_REL_BASED_HIGHLOW;
 317     return IMAGE_REL_BASED_ABSOLUTE;
 318   case ARMNT:
 319     if (Rel.Type == IMAGE_REL_ARM_ADDR32)
 320       return IMAGE_REL_BASED_HIGHLOW;
 321     if (Rel.Type == IMAGE_REL_ARM_MOV32T)
 322       return IMAGE_REL_BASED_ARM_MOV32T;
 323     return IMAGE_REL_BASED_ABSOLUTE;
 324   case ARM64:
 325     if (Rel.Type == IMAGE_REL_ARM64_ADDR64)
 326       return IMAGE_REL_BASED_DIR64;
 327     return IMAGE_REL_BASED_ABSOLUTE;
 328   default:
 329     llvm_unreachable("unknown machine type");
 330   }
 331 }
 332
 333 // Windows-specific.
 334 // Collect all locations that contain absolute addresses, which need to be
 335 // fixed by the loader if load-time relocation is needed.
 336 // Only called when base relocation is enabled.
 337 void SectionChunk::getBaserels(std::vector<Baserel> *Res) {
 338   for (const coff_relocation &Rel : Relocs) {
 339     uint8_t Ty = getBaserelType(Rel);
 340     if (Ty == IMAGE_REL_BASED_ABSOLUTE)
 341       continue;
 342     Symbol *Target = File->getSymbol(Rel.SymbolTableIndex);
 343     if (!Target || isa<DefinedAbsolute>(Target))
 344       continue;
 345     Res->emplace_back(RVA + Rel.VirtualAddress, Ty);
 346   }
 347 }
 348
 349 bool SectionChunk::hasData() const {
 350   return !(Header->Characteristics & IMAGE_SCN_CNT_UNINITIALIZED_DATA);
 351 }
 352
 353 uint32_t SectionChunk::getPermissions() const {
 354   return Header->Characteristics & PermMask;
 355 }
 356
 357 bool SectionChunk::isCOMDAT() const {
 358   return Header->Characteristics & IMAGE_SCN_LNK_COMDAT;
 359 }
 360
 361 void SectionChunk::printDiscardedMessage() const {
 362   // Removed by dead-stripping. If it's removed by ICF, ICF already
 363   // printed out the name, so don't repeat that here.
 364   if (Sym && this == Repl)
 365     message("Discarded " + Sym->getName());
 366 }
 367
 368 StringRef SectionChunk::getDebugName() {
 369   if (Sym)
 370     return Sym->getName();
 371   return "";
 372 }
 373
 374 ArrayRef<uint8_t> SectionChunk::getContents() const {
 375   ArrayRef<uint8_t> A;
 376   File->getCOFFObj()->getSectionContents(Header, A);
 377   return A;
 378 }
 379
 380 void SectionChunk::replace(SectionChunk *Other) {
 381   Other->Repl = Repl;
 382   Other->Live = false;
 383 }
 384
 385 CommonChunk::CommonChunk(const COFFSymbolRef S) : Sym(S) {
 386   // Common symbols are aligned on natural boundaries up to 32 bytes.
 387   // This is what MSVC link.exe does.
 388   Alignment = std::min(uint64_t(32), PowerOf2Ceil(Sym.getValue()));
 389 }
 390
 391 uint32_t CommonChunk::getPermissions() const {
 392   return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
 393          IMAGE_SCN_MEM_WRITE;
 394 }
 395
 396 void StringChunk::writeTo(uint8_t *Buf) const {
 397   memcpy(Buf + OutputSectionOff, Str.data(), Str.size());
 398 }
 399
 400 ImportThunkChunkX64::ImportThunkChunkX64(Defined *S) : ImpSymbol(S) {
 401   // Intel Optimization Manual says that all branch targets
 402   // should be 16-byte aligned. MSVC linker does this too.
 403   Alignment = 16;
 404 }
 405
 406 void ImportThunkChunkX64::writeTo(uint8_t *Buf) const {
 407   memcpy(Buf + OutputSectionOff, ImportThunkX86, sizeof(ImportThunkX86));
 408   // The first two bytes is a JMP instruction. Fill its operand.
 409   write32le(Buf + OutputSectionOff + 2, ImpSymbol->getRVA() - RVA - getSize());
 410 }
 411
 412 void ImportThunkChunkX86::getBaserels(std::vector<Baserel> *Res) {
 413   Res->emplace_back(getRVA() + 2);
 414 }
 415
 416 void ImportThunkChunkX86::writeTo(uint8_t *Buf) const {
 417   memcpy(Buf + OutputSectionOff, ImportThunkX86, sizeof(ImportThunkX86));
 418   // The first two bytes is a JMP instruction. Fill its operand.
 419   write32le(Buf + OutputSectionOff + 2,
 420             ImpSymbol->getRVA() + Config->ImageBase);
 421 }
 422
 423 void ImportThunkChunkARM::getBaserels(std::vector<Baserel> *Res) {
 424   Res->emplace_back(getRVA(), IMAGE_REL_BASED_ARM_MOV32T);
 425 }
 426
 427 void ImportThunkChunkARM::writeTo(uint8_t *Buf) const {
 428   memcpy(Buf + OutputSectionOff, ImportThunkARM, sizeof(ImportThunkARM));
 429   // Fix mov.w and mov.t operands.
 430   applyMOV32T(Buf + OutputSectionOff, ImpSymbol->getRVA() + Config->ImageBase);
 431 }
 432
 433 void ImportThunkChunkARM64::writeTo(uint8_t *Buf) const {
 434   int64_t Off = ImpSymbol->getRVA() & 0xfff;
 435   memcpy(Buf + OutputSectionOff, ImportThunkARM64, sizeof(ImportThunkARM64));
 436   applyArm64Addr(Buf + OutputSectionOff, ImpSymbol->getRVA(), RVA);
 437   applyArm64Ldr(Buf + OutputSectionOff + 4, Off);
 438 }
 439
 440 void LocalImportChunk::getBaserels(std::vector<Baserel> *Res) {
 441   Res->emplace_back(getRVA());
 442 }
 443
 444 size_t LocalImportChunk::getSize() const {
 445   return Config->is64() ? 8 : 4;
 446 }
 447
 448 void LocalImportChunk::writeTo(uint8_t *Buf) const {
 449   if (Config->is64()) {
 450     write64le(Buf + OutputSectionOff, Sym->getRVA() + Config->ImageBase);
 451   } else {
 452     write32le(Buf + OutputSectionOff, Sym->getRVA() + Config->ImageBase);
 453   }
 454 }
 455
 456 void SEHTableChunk::writeTo(uint8_t *Buf) const {
 457   ulittle32_t *Begin = reinterpret_cast<ulittle32_t *>(Buf + OutputSectionOff);
 458   size_t Cnt = 0;
 459   for (Defined *D : Syms)
 460     Begin[Cnt++] = D->getRVA();
 461   std::sort(Begin, Begin + Cnt);
 462 }
 463
 464 // Windows-specific. This class represents a block in .reloc section.
 465 // The format is described here.
 466 //
 467 // On Windows, each DLL is linked against a fixed base address and
 468 // usually loaded to that address. However, if there's already another
 469 // DLL that overlaps, the loader has to relocate it. To do that, DLLs
 470 // contain .reloc sections which contain offsets that need to be fixed
 471 // up at runtime. If the loader finds that a DLL cannot be loaded to its
 472 // desired base address, it loads it to somewhere else, and add <actual
 473 // base address> - <desired base address> to each offset that is
 474 // specified by the .reloc section. In ELF terms, .reloc sections
 475 // contain relative relocations in REL format (as opposed to RELA.)
 476 //
 477 // This already significantly reduces the size of relocations compared
 478 // to ELF .rel.dyn, but Windows does more to reduce it (probably because
 479 // it was invented for PCs in the late '80s or early '90s.)  Offsets in
 480 // .reloc are grouped by page where the page size is 12 bits, and
 481 // offsets sharing the same page address are stored consecutively to
 482 // represent them with less space. This is very similar to the page
 483 // table which is grouped by (multiple stages of) pages.
 484 //
 485 // For example, let's say we have 0x00030, 0x00500, 0x00700, 0x00A00,
 486 // 0x20004, and 0x20008 in a .reloc section for x64. The uppermost 4
 487 // bits have a type IMAGE_REL_BASED_DIR64 or 0xA. In the section, they
 488 // are represented like this:
 489 //
 490 //   0x00000  -- page address (4 bytes)
 491 //   16       -- size of this block (4 bytes)
 492 //     0xA030 -- entries (2 bytes each)
 493 //     0xA500
 494 //     0xA700
 495 //     0xAA00
 496 //   0x20000  -- page address (4 bytes)
 497 //   12       -- size of this block (4 bytes)
 498 //     0xA004 -- entries (2 bytes each)
 499 //     0xA008
 500 //
 501 // Usually we have a lot of relocations for each page, so the number of
 502 // bytes for one .reloc entry is close to 2 bytes on average.
 503 BaserelChunk::BaserelChunk(uint32_t Page, Baserel *Begin, Baserel *End) {
 504   // Block header consists of 4 byte page RVA and 4 byte block size.
 505   // Each entry is 2 byte. Last entry may be padding.
 506   Data.resize(alignTo((End - Begin) * 2 + 8, 4));
 507   uint8_t *P = Data.data();
 508   write32le(P, Page);
 509   write32le(P + 4, Data.size());
 510   P += 8;
 511   for (Baserel *I = Begin; I != End; ++I) {
 512     write16le(P, (I->Type << 12) | (I->RVA - Page));
 513     P += 2;
 514   }
 515 }
 516
 517 void BaserelChunk::writeTo(uint8_t *Buf) const {
 518   memcpy(Buf + OutputSectionOff, Data.data(), Data.size());
 519 }
 520
 521 uint8_t Baserel::getDefaultType() {
 522   switch (Config->Machine) {
 523   case AMD64:
 524   case ARM64:
 525     return IMAGE_REL_BASED_DIR64;
 526   case I386:
 527   case ARMNT:
 528     return IMAGE_REL_BASED_HIGHLOW;
 529   default:
 530     llvm_unreachable("unknown machine type");
 531   }
 532 }
 533
 534 } // namespace coff
 535 } // namespace lld