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 "Error.h"
  12 #include "InputFiles.h"
  13 #include "Symbols.h"
  14 #include "llvm/ADT/Twine.h"
  15 #include "llvm/Object/COFF.h"
  16 #include "llvm/Support/COFF.h"
  17 #include "llvm/Support/Debug.h"
  18 #include "llvm/Support/Endian.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include <algorithm>
  21
  22 using namespace llvm;
  23 using namespace llvm::object;
  24 using namespace llvm::support::endian;
  25 using namespace llvm::COFF;
  26 using llvm::support::ulittle32_t;
  27
  28 namespace lld {
  29 namespace coff {
  30
  31 SectionChunk::SectionChunk(ObjectFile *F, const coff_section *H)
  32     : Chunk(SectionKind), Repl(this), Header(H), File(F),
  33       Relocs(File->getCOFFObj()->getRelocations(Header)),
  34       NumRelocs(std::distance(Relocs.begin(), Relocs.end())) {
  35   // Initialize SectionName.
  36   File->getCOFFObj()->getSectionName(Header, SectionName);
  37
  38   Align = Header->getAlignment();
  39
  40   // Only COMDAT sections are subject of dead-stripping.
  41   Live = !isCOMDAT();
  42 }
  43
  44 static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); }
  45 static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); }
  46 static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); }
  47 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | V); }
  48
  49 void SectionChunk::applyRelX64(uint8_t *Off, uint16_t Type, Defined *Sym,
  50                                uint64_t P) const {
  51   uint64_t S = Sym->getRVA();
  52   switch (Type) {
  53   case IMAGE_REL_AMD64_ADDR32:   add32(Off, S + Config->ImageBase); break;
  54   case IMAGE_REL_AMD64_ADDR64:   add64(Off, S + Config->ImageBase); break;
  55   case IMAGE_REL_AMD64_ADDR32NB: add32(Off, S); break;
  56   case IMAGE_REL_AMD64_REL32:    add32(Off, S - P - 4); break;
  57   case IMAGE_REL_AMD64_REL32_1:  add32(Off, S - P - 5); break;
  58   case IMAGE_REL_AMD64_REL32_2:  add32(Off, S - P - 6); break;
  59   case IMAGE_REL_AMD64_REL32_3:  add32(Off, S - P - 7); break;
  60   case IMAGE_REL_AMD64_REL32_4:  add32(Off, S - P - 8); break;
  61   case IMAGE_REL_AMD64_REL32_5:  add32(Off, S - P - 9); break;
  62   case IMAGE_REL_AMD64_SECTION:  add16(Off, Sym->getSectionIndex()); break;
  63   case IMAGE_REL_AMD64_SECREL:   add32(Off, Sym->getSecrel()); break;
  64   default:
  65     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
  66   }
  67 }
  68
  69 void SectionChunk::applyRelX86(uint8_t *Off, uint16_t Type, Defined *Sym,
  70                                uint64_t P) const {
  71   uint64_t S = Sym->getRVA();
  72   switch (Type) {
  73   case IMAGE_REL_I386_ABSOLUTE: break;
  74   case IMAGE_REL_I386_DIR32:    add32(Off, S + Config->ImageBase); break;
  75   case IMAGE_REL_I386_DIR32NB:  add32(Off, S); break;
  76   case IMAGE_REL_I386_REL32:    add32(Off, S - P - 4); break;
  77   case IMAGE_REL_I386_SECTION:  add16(Off, Sym->getSectionIndex()); break;
  78   case IMAGE_REL_I386_SECREL:   add32(Off, Sym->getSecrel()); break;
  79   default:
  80     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
  81   }
  82 }
  83
  84 static void applyMOV(uint8_t *Off, uint16_t V) {
  85   write16le(Off, (read16le(Off) & 0xfbf0) | ((V & 0x800) >> 1) | ((V >> 12) & 0xf));
  86   write16le(Off + 2, (read16le(Off + 2) & 0x8f00) | ((V & 0x700) << 4) | (V & 0xff));
  87 }
  88
  89 static uint16_t readMOV(uint8_t *Off) {
  90   uint16_t Opcode1 = read16le(Off);
  91   uint16_t Opcode2 = read16le(Off + 2);
  92   uint16_t Imm = (Opcode2 & 0x00ff) | ((Opcode2 >> 4) & 0x0700);
  93   Imm |= ((Opcode1 << 1) & 0x0800) | ((Opcode1 & 0x000f) << 12);
  94   return Imm;
  95 }
  96
  97 static void applyMOV32T(uint8_t *Off, uint32_t V) {
  98   uint16_t ImmW = readMOV(Off);     // read MOVW operand
  99   uint16_t ImmT = readMOV(Off + 4); // read MOVT operand
 100   uint32_t Imm = ImmW | (ImmT << 16);
 101   V += Imm;                         // add the immediate offset
 102   applyMOV(Off, V);           // set MOVW operand
 103   applyMOV(Off + 4, V >> 16); // set MOVT operand
 104 }
 105
 106 static void applyBranch20T(uint8_t *Off, int32_t V) {
 107   uint32_t S = V < 0 ? 1 : 0;
 108   uint32_t J1 = (V >> 19) & 1;
 109   uint32_t J2 = (V >> 18) & 1;
 110   or16(Off, (S << 10) | ((V >> 12) & 0x3f));
 111   or16(Off + 2, (J1 << 13) | (J2 << 11) | ((V >> 1) & 0x7ff));
 112 }
 113
 114 static void applyBranch24T(uint8_t *Off, int32_t V) {
 115   if (!isInt<25>(V))
 116     fatal("relocation out of range");
 117   uint32_t S = V < 0 ? 1 : 0;
 118   uint32_t J1 = ((~V >> 23) & 1) ^ S;
 119   uint32_t J2 = ((~V >> 22) & 1) ^ S;
 120   or16(Off, (S << 10) | ((V >> 12) & 0x3ff));
 121   // Clear out the J1 and J2 bits which may be set.
 122   write16le(Off + 2, (read16le(Off + 2) & 0xd000) | (J1 << 13) | (J2 << 11) | ((V >> 1) & 0x7ff));
 123 }
 124
 125 void SectionChunk::applyRelARM(uint8_t *Off, uint16_t Type, Defined *Sym,
 126                                uint64_t P) const {
 127   uint64_t S = Sym->getRVA();
 128   // Pointer to thumb code must have the LSB set.
 129   if (Sym->isExecutable())
 130     S |= 1;
 131   switch (Type) {
 132   case IMAGE_REL_ARM_ADDR32:    add32(Off, S + Config->ImageBase); break;
 133   case IMAGE_REL_ARM_ADDR32NB:  add32(Off, S); break;
 134   case IMAGE_REL_ARM_MOV32T:    applyMOV32T(Off, S + Config->ImageBase); break;
 135   case IMAGE_REL_ARM_BRANCH20T: applyBranch20T(Off, S - P - 4); break;
 136   case IMAGE_REL_ARM_BRANCH24T: applyBranch24T(Off, S - P - 4); break;
 137   case IMAGE_REL_ARM_BLX23T:    applyBranch24T(Off, S - P - 4); break;
 138   case IMAGE_REL_ARM_SECREL:    add32(Off, Sym->getSecrel()); break;
 139   default:
 140     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
 141   }
 142 }
 143
 144 void SectionChunk::writeTo(uint8_t *Buf) const {
 145   if (!hasData())
 146     return;
 147   // Copy section contents from source object file to output file.
 148   ArrayRef<uint8_t> A = getContents();
 149   memcpy(Buf + OutputSectionOff, A.data(), A.size());
 150
 151   // Apply relocations.
 152   for (const coff_relocation &Rel : Relocs) {
 153     uint8_t *Off = Buf + OutputSectionOff + Rel.VirtualAddress;
 154     SymbolBody *Body = File->getSymbolBody(Rel.SymbolTableIndex);
 155     Defined *Sym = cast<Defined>(Body);
 156     uint64_t P = RVA + Rel.VirtualAddress;
 157     switch (Config->Machine) {
 158     case AMD64:
 159       applyRelX64(Off, Rel.Type, Sym, P);
 160       break;
 161     case I386:
 162       applyRelX86(Off, Rel.Type, Sym, P);
 163       break;
 164     case ARMNT:
 165       applyRelARM(Off, Rel.Type, Sym, P);
 166       break;
 167     default:
 168       llvm_unreachable("unknown machine type");
 169     }
 170   }
 171 }
 172
 173 void SectionChunk::addAssociative(SectionChunk *Child) {
 174   AssocChildren.push_back(Child);
 175 }
 176
 177 static uint8_t getBaserelType(const coff_relocation &Rel) {
 178   switch (Config->Machine) {
 179   case AMD64:
 180     if (Rel.Type == IMAGE_REL_AMD64_ADDR64)
 181       return IMAGE_REL_BASED_DIR64;
 182     return IMAGE_REL_BASED_ABSOLUTE;
 183   case I386:
 184     if (Rel.Type == IMAGE_REL_I386_DIR32)
 185       return IMAGE_REL_BASED_HIGHLOW;
 186     return IMAGE_REL_BASED_ABSOLUTE;
 187   case ARMNT:
 188     if (Rel.Type == IMAGE_REL_ARM_ADDR32)
 189       return IMAGE_REL_BASED_HIGHLOW;
 190     if (Rel.Type == IMAGE_REL_ARM_MOV32T)
 191       return IMAGE_REL_BASED_ARM_MOV32T;
 192     return IMAGE_REL_BASED_ABSOLUTE;
 193   default:
 194     llvm_unreachable("unknown machine type");
 195   }
 196 }
 197
 198 // Windows-specific.
 199 // Collect all locations that contain absolute addresses, which need to be
 200 // fixed by the loader if load-time relocation is needed.
 201 // Only called when base relocation is enabled.
 202 void SectionChunk::getBaserels(std::vector<Baserel> *Res) {
 203   for (const coff_relocation &Rel : Relocs) {
 204     uint8_t Ty = getBaserelType(Rel);
 205     if (Ty == IMAGE_REL_BASED_ABSOLUTE)
 206       continue;
 207     SymbolBody *Body = File->getSymbolBody(Rel.SymbolTableIndex);
 208     if (isa<DefinedAbsolute>(Body))
 209       continue;
 210     Res->emplace_back(RVA + Rel.VirtualAddress, Ty);
 211   }
 212 }
 213
 214 bool SectionChunk::hasData() const {
 215   return !(Header->Characteristics & IMAGE_SCN_CNT_UNINITIALIZED_DATA);
 216 }
 217
 218 uint32_t SectionChunk::getPermissions() const {
 219   return Header->Characteristics & PermMask;
 220 }
 221
 222 bool SectionChunk::isCOMDAT() const {
 223   return Header->Characteristics & IMAGE_SCN_LNK_COMDAT;
 224 }
 225
 226 void SectionChunk::printDiscardedMessage() const {
 227   // Removed by dead-stripping. If it's removed by ICF, ICF already
 228   // printed out the name, so don't repeat that here.
 229   if (Sym && this == Repl)
 230     message("Discarded " + Sym->getName());
 231 }
 232
 233 StringRef SectionChunk::getDebugName() {
 234   if (Sym)
 235     return Sym->getName();
 236   return "";
 237 }
 238
 239 ArrayRef<uint8_t> SectionChunk::getContents() const {
 240   ArrayRef<uint8_t> A;
 241   File->getCOFFObj()->getSectionContents(Header, A);
 242   return A;
 243 }
 244
 245 void SectionChunk::replace(SectionChunk *Other) {
 246   Other->Repl = Repl;
 247   Other->Live = false;
 248 }
 249
 250 CommonChunk::CommonChunk(const COFFSymbolRef S) : Sym(S) {
 251   // Common symbols are aligned on natural boundaries up to 32 bytes.
 252   // This is what MSVC link.exe does.
 253   Align = std::min(uint64_t(32), PowerOf2Ceil(Sym.getValue()));
 254 }
 255
 256 uint32_t CommonChunk::getPermissions() const {
 257   return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
 258          IMAGE_SCN_MEM_WRITE;
 259 }
 260
 261 void StringChunk::writeTo(uint8_t *Buf) const {
 262   memcpy(Buf + OutputSectionOff, Str.data(), Str.size());
 263 }
 264
 265 ImportThunkChunkX64::ImportThunkChunkX64(Defined *S) : ImpSymbol(S) {
 266   // Intel Optimization Manual says that all branch targets
 267   // should be 16-byte aligned. MSVC linker does this too.
 268   Align = 16;
 269 }
 270
 271 void ImportThunkChunkX64::writeTo(uint8_t *Buf) const {
 272   memcpy(Buf + OutputSectionOff, ImportThunkX86, sizeof(ImportThunkX86));
 273   // The first two bytes is a JMP instruction. Fill its operand.
 274   write32le(Buf + OutputSectionOff + 2, ImpSymbol->getRVA() - RVA - getSize());
 275 }
 276
 277 void ImportThunkChunkX86::getBaserels(std::vector<Baserel> *Res) {
 278   Res->emplace_back(getRVA() + 2);
 279 }
 280
 281 void ImportThunkChunkX86::writeTo(uint8_t *Buf) const {
 282   memcpy(Buf + OutputSectionOff, ImportThunkX86, sizeof(ImportThunkX86));
 283   // The first two bytes is a JMP instruction. Fill its operand.
 284   write32le(Buf + OutputSectionOff + 2,
 285             ImpSymbol->getRVA() + Config->ImageBase);
 286 }
 287
 288 void ImportThunkChunkARM::getBaserels(std::vector<Baserel> *Res) {
 289   Res->emplace_back(getRVA(), IMAGE_REL_BASED_ARM_MOV32T);
 290 }
 291
 292 void ImportThunkChunkARM::writeTo(uint8_t *Buf) const {
 293   memcpy(Buf + OutputSectionOff, ImportThunkARM, sizeof(ImportThunkARM));
 294   // Fix mov.w and mov.t operands.
 295   applyMOV32T(Buf + OutputSectionOff, ImpSymbol->getRVA() + Config->ImageBase);
 296 }
 297
 298 void LocalImportChunk::getBaserels(std::vector<Baserel> *Res) {
 299   Res->emplace_back(getRVA());
 300 }
 301
 302 size_t LocalImportChunk::getSize() const {
 303   return Config->is64() ? 8 : 4;
 304 }
 305
 306 void LocalImportChunk::writeTo(uint8_t *Buf) const {
 307   if (Config->is64()) {
 308     write64le(Buf + OutputSectionOff, Sym->getRVA() + Config->ImageBase);
 309   } else {
 310     write32le(Buf + OutputSectionOff, Sym->getRVA() + Config->ImageBase);
 311   }
 312 }
 313
 314 void SEHTableChunk::writeTo(uint8_t *Buf) const {
 315   ulittle32_t *Begin = reinterpret_cast<ulittle32_t *>(Buf + OutputSectionOff);
 316   size_t Cnt = 0;
 317   for (Defined *D : Syms)
 318     Begin[Cnt++] = D->getRVA();
 319   std::sort(Begin, Begin + Cnt);
 320 }
 321
 322 // Windows-specific. This class represents a block in .reloc section.
 323 // The format is described here.
 324 //
 325 // On Windows, each DLL is linked against a fixed base address and
 326 // usually loaded to that address. However, if there's already another
 327 // DLL that overlaps, the loader has to relocate it. To do that, DLLs
 328 // contain .reloc sections which contain offsets that need to be fixed
 329 // up at runtime. If the loader find that a DLL cannot be loaded to its
 330 // desired base address, it loads it to somewhere else, and add <actual
 331 // base address> - <desired base address> to each offset that is
 332 // specified by .reloc section.
 333 //
 334 // In ELF terms, .reloc sections contain arrays of relocation offsets.
 335 // All these offsets in the section are implicitly R_*_RELATIVE, and
 336 // addends are read from section contents (so it is REL as opposed to
 337 // RELA).
 338 //
 339 // This already reduce the size of relocations to 1/3 compared to ELF
 340 // .dynrel, but Windows does more to reduce it (probably because it was
 341 // invented for PCs in the late '80s or early '90s.) Offsets in .reloc
 342 // are grouped by page where page size is 16 bits, and offsets sharing
 343 // the same page address are stored consecutively to represent them with
 344 // less space. This is a very similar to the page table which is grouped
 345 // by (multiple stages of) pages.
 346 //
 347 // For example, let's say we have 0x00030, 0x00500, 0x01000, 0x01100,
 348 // 0x20004, and 0x20008 in a .reloc section. In the section, they are
 349 // represented like this:
 350 //
 351 //   0x00000  -- page address (4 bytes)
 352 //   16       -- size of this block (4 bytes)
 353 //     0x0030 -- entries (2 bytes each)
 354 //     0x0500
 355 //     0x1000
 356 //     0x1100
 357 //   0x20000  -- page address (4 bytes)
 358 //   12       -- size of this block (4 bytes)
 359 //     0x0004 -- entries (2 bytes each)
 360 //     0x0008
 361 //
 362 // Usually we have a lot of relocatinos for each page, so the number of
 363 // bytes for one .reloc entry is close to 2 bytes.
 364 BaserelChunk::BaserelChunk(uint32_t Page, Baserel *Begin, Baserel *End) {
 365   // Block header consists of 4 byte page RVA and 4 byte block size.
 366   // Each entry is 2 byte. Last entry may be padding.
 367   Data.resize(alignTo((End - Begin) * 2 + 8, 4));
 368   uint8_t *P = Data.data();
 369   write32le(P, Page);
 370   write32le(P + 4, Data.size());
 371   P += 8;
 372   for (Baserel *I = Begin; I != End; ++I) {
 373     write16le(P, (I->Type << 12) | (I->RVA - Page));
 374     P += 2;
 375   }
 376 }
 377
 378 void BaserelChunk::writeTo(uint8_t *Buf) const {
 379   memcpy(Buf + OutputSectionOff, Data.data(), Data.size());
 380 }
 381
 382 uint8_t Baserel::getDefaultType() {
 383   switch (Config->Machine) {
 384   case AMD64:
 385     return IMAGE_REL_BASED_DIR64;
 386   case I386:
 387     return IMAGE_REL_BASED_HIGHLOW;
 388   default:
 389     llvm_unreachable("unknown machine type");
 390   }
 391 }
 392
 393 } // namespace coff
 394 } // namespace lld