llvm-project

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, Kind k)
35
    : Chunk(k), 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
  // Write the offset to EC entry thunk preceding section contents. The low bit
415
  // is always set, so it's effectively an offset from the last byte of the
416
  // offset.
417
  if (Defined *entryThunk = getEntryThunk())
418
    write32le(buf - sizeof(uint32_t), entryThunk->getRVA() - rva + 1);
419
}
420

421
void SectionChunk::applyRelocation(uint8_t *off,
422
                                   const coff_relocation &rel) const {
423
  auto *sym = dyn_cast_or_null<Defined>(file->getSymbol(rel.SymbolTableIndex));
424

425
  // Get the output section of the symbol for this relocation.  The output
426
  // section is needed to compute SECREL and SECTION relocations used in debug
427
  // info.
428
  Chunk *c = sym ? sym->getChunk() : nullptr;
429
  OutputSection *os = c ? file->ctx.getOutputSection(c) : nullptr;
430

431
  // Skip the relocation if it refers to a discarded section, and diagnose it
432
  // as an error if appropriate. If a symbol was discarded early, it may be
433
  // null. If it was discarded late, the output section will be null, unless
434
  // it was an absolute or synthetic symbol.
435
  if (!sym ||
436
      (!os && !isa<DefinedAbsolute>(sym) && !isa<DefinedSynthetic>(sym))) {
437
    maybeReportRelocationToDiscarded(this, sym, rel, file->ctx.config.mingw);
438
    return;
439
  }
440

441
  uint64_t s = sym->getRVA();
442

443
  // Compute the RVA of the relocation for relative relocations.
444
  uint64_t p = rva + rel.VirtualAddress;
445
  uint64_t imageBase = file->ctx.config.imageBase;
446
  switch (getArch()) {
447
  case Triple::x86_64:
448
    applyRelX64(off, rel.Type, os, s, p, imageBase);
449
    break;
450
  case Triple::x86:
451
    applyRelX86(off, rel.Type, os, s, p, imageBase);
452
    break;
453
  case Triple::thumb:
454
    applyRelARM(off, rel.Type, os, s, p, imageBase);
455
    break;
456
  case Triple::aarch64:
457
    applyRelARM64(off, rel.Type, os, s, p, imageBase);
458
    break;
459
  default:
460
    llvm_unreachable("unknown machine type");
461
  }
462
}
463

464
// Defend against unsorted relocations. This may be overly conservative.
465
void SectionChunk::sortRelocations() {
466
  auto cmpByVa = [](const coff_relocation &l, const coff_relocation &r) {
467
    return l.VirtualAddress < r.VirtualAddress;
468
  };
469
  if (llvm::is_sorted(getRelocs(), cmpByVa))
470
    return;
471
  warn("some relocations in " + file->getName() + " are not sorted");
472
  MutableArrayRef<coff_relocation> newRelocs(
473
      bAlloc().Allocate<coff_relocation>(relocsSize), relocsSize);
474
  memcpy(newRelocs.data(), relocsData, relocsSize * sizeof(coff_relocation));
475
  llvm::sort(newRelocs, cmpByVa);
476
  setRelocs(newRelocs);
477
}
478

479
// Similar to writeTo, but suitable for relocating a subsection of the overall
480
// section.
481
void SectionChunk::writeAndRelocateSubsection(ArrayRef<uint8_t> sec,
482
                                              ArrayRef<uint8_t> subsec,
483
                                              uint32_t &nextRelocIndex,
484
                                              uint8_t *buf) const {
485
  assert(!subsec.empty() && !sec.empty());
486
  assert(sec.begin() <= subsec.begin() && subsec.end() <= sec.end() &&
487
         "subsection is not part of this section");
488
  size_t vaBegin = std::distance(sec.begin(), subsec.begin());
489
  size_t vaEnd = std::distance(sec.begin(), subsec.end());
490
  memcpy(buf, subsec.data(), subsec.size());
491
  for (; nextRelocIndex < relocsSize; ++nextRelocIndex) {
492
    const coff_relocation &rel = relocsData[nextRelocIndex];
493
    // Only apply relocations that apply to this subsection. These checks
494
    // assume that all subsections completely contain their relocations.
495
    // Relocations must not straddle the beginning or end of a subsection.
496
    if (rel.VirtualAddress < vaBegin)
497
      continue;
498
    if (rel.VirtualAddress + 1 >= vaEnd)
499
      break;
500
    applyRelocation(&buf[rel.VirtualAddress - vaBegin], rel);
501
  }
502
}
503

504
void SectionChunk::addAssociative(SectionChunk *child) {
505
  // Insert the child section into the list of associated children. Keep the
506
  // list ordered by section name so that ICF does not depend on section order.
507
  assert(child->assocChildren == nullptr &&
508
         "associated sections cannot have their own associated children");
509
  SectionChunk *prev = this;
510
  SectionChunk *next = assocChildren;
511
  for (; next != nullptr; prev = next, next = next->assocChildren) {
512
    if (next->getSectionName() <= child->getSectionName())
513
      break;
514
  }
515

516
  // Insert child between prev and next.
517
  assert(prev->assocChildren == next);
518
  prev->assocChildren = child;
519
  child->assocChildren = next;
520
}
521

522
static uint8_t getBaserelType(const coff_relocation &rel,
523
                              Triple::ArchType arch) {
524
  switch (arch) {
525
  case Triple::x86_64:
526
    if (rel.Type == IMAGE_REL_AMD64_ADDR64)
527
      return IMAGE_REL_BASED_DIR64;
528
    if (rel.Type == IMAGE_REL_AMD64_ADDR32)
529
      return IMAGE_REL_BASED_HIGHLOW;
530
    return IMAGE_REL_BASED_ABSOLUTE;
531
  case Triple::x86:
532
    if (rel.Type == IMAGE_REL_I386_DIR32)
533
      return IMAGE_REL_BASED_HIGHLOW;
534
    return IMAGE_REL_BASED_ABSOLUTE;
535
  case Triple::thumb:
536
    if (rel.Type == IMAGE_REL_ARM_ADDR32)
537
      return IMAGE_REL_BASED_HIGHLOW;
538
    if (rel.Type == IMAGE_REL_ARM_MOV32T)
539
      return IMAGE_REL_BASED_ARM_MOV32T;
540
    return IMAGE_REL_BASED_ABSOLUTE;
541
  case Triple::aarch64:
542
    if (rel.Type == IMAGE_REL_ARM64_ADDR64)
543
      return IMAGE_REL_BASED_DIR64;
544
    return IMAGE_REL_BASED_ABSOLUTE;
545
  default:
546
    llvm_unreachable("unknown machine type");
547
  }
548
}
549

550
// Windows-specific.
551
// Collect all locations that contain absolute addresses, which need to be
552
// fixed by the loader if load-time relocation is needed.
553
// Only called when base relocation is enabled.
554
void SectionChunk::getBaserels(std::vector<Baserel> *res) {
555
  for (const coff_relocation &rel : getRelocs()) {
556
    uint8_t ty = getBaserelType(rel, getArch());
557
    if (ty == IMAGE_REL_BASED_ABSOLUTE)
558
      continue;
559
    Symbol *target = file->getSymbol(rel.SymbolTableIndex);
560
    if (!target || isa<DefinedAbsolute>(target))
561
      continue;
562
    res->emplace_back(rva + rel.VirtualAddress, ty);
563
  }
564
}
565

566
// MinGW specific.
567
// Check whether a static relocation of type Type can be deferred and
568
// handled at runtime as a pseudo relocation (for references to a module
569
// local variable, which turned out to actually need to be imported from
570
// another DLL) This returns the size the relocation is supposed to update,
571
// in bits, or 0 if the relocation cannot be handled as a runtime pseudo
572
// relocation.
573
static int getRuntimePseudoRelocSize(uint16_t type,
574
                                     llvm::COFF::MachineTypes machine) {
575
  // Relocations that either contain an absolute address, or a plain
576
  // relative offset, since the runtime pseudo reloc implementation
577
  // adds 8/16/32/64 bit values to a memory address.
578
  //
579
  // Given a pseudo relocation entry,
580
  //
581
  // typedef struct {
582
  //   DWORD sym;
583
  //   DWORD target;
584
  //   DWORD flags;
585
  // } runtime_pseudo_reloc_item_v2;
586
  //
587
  // the runtime relocation performs this adjustment:
588
  //     *(base + .target) += *(base + .sym) - (base + .sym)
589
  //
590
  // This works for both absolute addresses (IMAGE_REL_*_ADDR32/64,
591
  // IMAGE_REL_I386_DIR32, where the memory location initially contains
592
  // the address of the IAT slot, and for relative addresses (IMAGE_REL*_REL32),
593
  // where the memory location originally contains the relative offset to the
594
  // IAT slot.
595
  //
596
  // This requires the target address to be writable, either directly out of
597
  // the image, or temporarily changed at runtime with VirtualProtect.
598
  // Since this only operates on direct address values, it doesn't work for
599
  // ARM/ARM64 relocations, other than the plain ADDR32/ADDR64 relocations.
600
  switch (machine) {
601
  case AMD64:
602
    switch (type) {
603
    case IMAGE_REL_AMD64_ADDR64:
604
      return 64;
605
    case IMAGE_REL_AMD64_ADDR32:
606
    case IMAGE_REL_AMD64_REL32:
607
    case IMAGE_REL_AMD64_REL32_1:
608
    case IMAGE_REL_AMD64_REL32_2:
609
    case IMAGE_REL_AMD64_REL32_3:
610
    case IMAGE_REL_AMD64_REL32_4:
611
    case IMAGE_REL_AMD64_REL32_5:
612
      return 32;
613
    default:
614
      return 0;
615
    }
616
  case I386:
617
    switch (type) {
618
    case IMAGE_REL_I386_DIR32:
619
    case IMAGE_REL_I386_REL32:
620
      return 32;
621
    default:
622
      return 0;
623
    }
624
  case ARMNT:
625
    switch (type) {
626
    case IMAGE_REL_ARM_ADDR32:
627
      return 32;
628
    default:
629
      return 0;
630
    }
631
  case ARM64:
632
    switch (type) {
633
    case IMAGE_REL_ARM64_ADDR64:
634
      return 64;
635
    case IMAGE_REL_ARM64_ADDR32:
636
      return 32;
637
    default:
638
      return 0;
639
    }
640
  default:
641
    llvm_unreachable("unknown machine type");
642
  }
643
}
644

645
// MinGW specific.
646
// Append information to the provided vector about all relocations that
647
// need to be handled at runtime as runtime pseudo relocations (references
648
// to a module local variable, which turned out to actually need to be
649
// imported from another DLL).
650
void SectionChunk::getRuntimePseudoRelocs(
651
    std::vector<RuntimePseudoReloc> &res) {
652
  for (const coff_relocation &rel : getRelocs()) {
653
    auto *target =
654
        dyn_cast_or_null<Defined>(file->getSymbol(rel.SymbolTableIndex));
655
    if (!target || !target->isRuntimePseudoReloc)
656
      continue;
657
    // If the target doesn't have a chunk allocated, it may be a
658
    // DefinedImportData symbol which ended up unnecessary after GC.
659
    // Normally we wouldn't eliminate section chunks that are referenced, but
660
    // references within DWARF sections don't count for keeping section chunks
661
    // alive. Thus such dangling references in DWARF sections are expected.
662
    if (!target->getChunk())
663
      continue;
664
    int sizeInBits =
665
        getRuntimePseudoRelocSize(rel.Type, file->ctx.config.machine);
666
    if (sizeInBits == 0) {
667
      error("unable to automatically import from " + target->getName() +
668
            " with relocation type " +
669
            file->getCOFFObj()->getRelocationTypeName(rel.Type) + " in " +
670
            toString(file));
671
      continue;
672
    }
673
    int addressSizeInBits = file->ctx.config.is64() ? 64 : 32;
674
    if (sizeInBits < addressSizeInBits) {
675
      warn("runtime pseudo relocation in " + toString(file) + " against " +
676
           "symbol " + target->getName() + " is too narrow (only " +
677
           Twine(sizeInBits) + " bits wide); this can fail at runtime " +
678
           "depending on memory layout");
679
    }
680
    // sizeInBits is used to initialize the Flags field; currently no
681
    // other flags are defined.
682
    res.emplace_back(target, this, rel.VirtualAddress, sizeInBits);
683
  }
684
}
685

686
bool SectionChunk::isCOMDAT() const {
687
  return header->Characteristics & IMAGE_SCN_LNK_COMDAT;
688
}
689

690
void SectionChunk::printDiscardedMessage() const {
691
  // Removed by dead-stripping. If it's removed by ICF, ICF already
692
  // printed out the name, so don't repeat that here.
693
  if (sym && this == repl)
694
    log("Discarded " + sym->getName());
695
}
696

697
StringRef SectionChunk::getDebugName() const {
698
  if (sym)
699
    return sym->getName();
700
  return "";
701
}
702

703
ArrayRef<uint8_t> SectionChunk::getContents() const {
704
  ArrayRef<uint8_t> a;
705
  cantFail(file->getCOFFObj()->getSectionContents(header, a));
706
  return a;
707
}
708

709
ArrayRef<uint8_t> SectionChunk::consumeDebugMagic() {
710
  assert(isCodeView());
711
  return consumeDebugMagic(getContents(), getSectionName());
712
}
713

714
ArrayRef<uint8_t> SectionChunk::consumeDebugMagic(ArrayRef<uint8_t> data,
715
                                                  StringRef sectionName) {
716
  if (data.empty())
717
    return {};
718

719
  // First 4 bytes are section magic.
720
  if (data.size() < 4)
721
    fatal("the section is too short: " + sectionName);
722

723
  if (!sectionName.starts_with(".debug$"))
724
    fatal("invalid section: " + sectionName);
725

726
  uint32_t magic = support::endian::read32le(data.data());
727
  uint32_t expectedMagic = sectionName == ".debug$H"
728
                               ? DEBUG_HASHES_SECTION_MAGIC
729
                               : DEBUG_SECTION_MAGIC;
730
  if (magic != expectedMagic) {
731
    warn("ignoring section " + sectionName + " with unrecognized magic 0x" +
732
         utohexstr(magic));
733
    return {};
734
  }
735
  return data.slice(4);
736
}
737

738
SectionChunk *SectionChunk::findByName(ArrayRef<SectionChunk *> sections,
739
                                       StringRef name) {
740
  for (SectionChunk *c : sections)
741
    if (c->getSectionName() == name)
742
      return c;
743
  return nullptr;
744
}
745

746
void SectionChunk::replace(SectionChunk *other) {
747
  p2Align = std::max(p2Align, other->p2Align);
748
  other->repl = repl;
749
  other->live = false;
750
}
751

752
uint32_t SectionChunk::getSectionNumber() const {
753
  DataRefImpl r;
754
  r.p = reinterpret_cast<uintptr_t>(header);
755
  SectionRef s(r, file->getCOFFObj());
756
  return s.getIndex() + 1;
757
}
758

759
CommonChunk::CommonChunk(const COFFSymbolRef s) : sym(s) {
760
  // The value of a common symbol is its size. Align all common symbols smaller
761
  // than 32 bytes naturally, i.e. round the size up to the next power of two.
762
  // This is what MSVC link.exe does.
763
  setAlignment(std::min(32U, uint32_t(PowerOf2Ceil(sym.getValue()))));
764
  hasData = false;
765
}
766

767
uint32_t CommonChunk::getOutputCharacteristics() const {
768
  return IMAGE_SCN_CNT_UNINITIALIZED_DATA | IMAGE_SCN_MEM_READ |
769
         IMAGE_SCN_MEM_WRITE;
770
}
771

772
void StringChunk::writeTo(uint8_t *buf) const {
773
  memcpy(buf, str.data(), str.size());
774
  buf[str.size()] = '\0';
775
}
776

777
ImportThunkChunkX64::ImportThunkChunkX64(COFFLinkerContext &ctx, Defined *s)
778
    : ImportThunkChunk(ctx, s) {
779
  // Intel Optimization Manual says that all branch targets
780
  // should be 16-byte aligned. MSVC linker does this too.
781
  setAlignment(16);
782
}
783

784
void ImportThunkChunkX64::writeTo(uint8_t *buf) const {
785
  memcpy(buf, importThunkX86, sizeof(importThunkX86));
786
  // The first two bytes is a JMP instruction. Fill its operand.
787
  write32le(buf + 2, impSymbol->getRVA() - rva - getSize());
788
}
789

790
void ImportThunkChunkX86::getBaserels(std::vector<Baserel> *res) {
791
  res->emplace_back(getRVA() + 2, ctx.config.machine);
792
}
793

794
void ImportThunkChunkX86::writeTo(uint8_t *buf) const {
795
  memcpy(buf, importThunkX86, sizeof(importThunkX86));
796
  // The first two bytes is a JMP instruction. Fill its operand.
797
  write32le(buf + 2, impSymbol->getRVA() + ctx.config.imageBase);
798
}
799

800
void ImportThunkChunkARM::getBaserels(std::vector<Baserel> *res) {
801
  res->emplace_back(getRVA(), IMAGE_REL_BASED_ARM_MOV32T);
802
}
803

804
void ImportThunkChunkARM::writeTo(uint8_t *buf) const {
805
  memcpy(buf, importThunkARM, sizeof(importThunkARM));
806
  // Fix mov.w and mov.t operands.
807
  applyMOV32T(buf, impSymbol->getRVA() + ctx.config.imageBase);
808
}
809

810
void ImportThunkChunkARM64::writeTo(uint8_t *buf) const {
811
  int64_t off = impSymbol->getRVA() & 0xfff;
812
  memcpy(buf, importThunkARM64, sizeof(importThunkARM64));
813
  applyArm64Addr(buf, impSymbol->getRVA(), rva, 12);
814
  applyArm64Ldr(buf + 4, off);
815
}
816

817
// A Thumb2, PIC, non-interworking range extension thunk.
818
const uint8_t armThunk[] = {
819
    0x40, 0xf2, 0x00, 0x0c, // P:  movw ip,:lower16:S - (P + (L1-P) + 4)
820
    0xc0, 0xf2, 0x00, 0x0c, //     movt ip,:upper16:S - (P + (L1-P) + 4)
821
    0xe7, 0x44,             // L1: add  pc, ip
822
};
823

824
size_t RangeExtensionThunkARM::getSize() const {
825
  assert(ctx.config.machine == ARMNT);
826
  (void)&ctx;
827
  return sizeof(armThunk);
828
}
829

830
void RangeExtensionThunkARM::writeTo(uint8_t *buf) const {
831
  assert(ctx.config.machine == ARMNT);
832
  uint64_t offset = target->getRVA() - rva - 12;
833
  memcpy(buf, armThunk, sizeof(armThunk));
834
  applyMOV32T(buf, uint32_t(offset));
835
}
836

837
// A position independent ARM64 adrp+add thunk, with a maximum range of
838
// +/- 4 GB, which is enough for any PE-COFF.
839
const uint8_t arm64Thunk[] = {
840
    0x10, 0x00, 0x00, 0x90, // adrp x16, Dest
841
    0x10, 0x02, 0x00, 0x91, // add  x16, x16, :lo12:Dest
842
    0x00, 0x02, 0x1f, 0xd6, // br   x16
843
};
844

845
size_t RangeExtensionThunkARM64::getSize() const {
846
  assert(ctx.config.machine == ARM64);
847
  (void)&ctx;
848
  return sizeof(arm64Thunk);
849
}
850

851
void RangeExtensionThunkARM64::writeTo(uint8_t *buf) const {
852
  assert(ctx.config.machine == ARM64);
853
  memcpy(buf, arm64Thunk, sizeof(arm64Thunk));
854
  applyArm64Addr(buf + 0, target->getRVA(), rva, 12);
855
  applyArm64Imm(buf + 4, target->getRVA() & 0xfff, 0);
856
}
857

858
LocalImportChunk::LocalImportChunk(COFFLinkerContext &c, Defined *s)
859
    : sym(s), ctx(c) {
860
  setAlignment(ctx.config.wordsize);
861
}
862

863
void LocalImportChunk::getBaserels(std::vector<Baserel> *res) {
864
  res->emplace_back(getRVA(), ctx.config.machine);
865
}
866

867
size_t LocalImportChunk::getSize() const { return ctx.config.wordsize; }
868

869
void LocalImportChunk::writeTo(uint8_t *buf) const {
870
  if (ctx.config.is64()) {
871
    write64le(buf, sym->getRVA() + ctx.config.imageBase);
872
  } else {
873
    write32le(buf, sym->getRVA() + ctx.config.imageBase);
874
  }
875
}
876

877
void RVATableChunk::writeTo(uint8_t *buf) const {
878
  ulittle32_t *begin = reinterpret_cast<ulittle32_t *>(buf);
879
  size_t cnt = 0;
880
  for (const ChunkAndOffset &co : syms)
881
    begin[cnt++] = co.inputChunk->getRVA() + co.offset;
882
  llvm::sort(begin, begin + cnt);
883
  assert(std::unique(begin, begin + cnt) == begin + cnt &&
884
         "RVA tables should be de-duplicated");
885
}
886

887
void RVAFlagTableChunk::writeTo(uint8_t *buf) const {
888
  struct RVAFlag {
889
    ulittle32_t rva;
890
    uint8_t flag;
891
  };
892
  auto flags =
893
      MutableArrayRef(reinterpret_cast<RVAFlag *>(buf), syms.size());
894
  for (auto t : zip(syms, flags)) {
895
    const auto &sym = std::get<0>(t);
896
    auto &flag = std::get<1>(t);
897
    flag.rva = sym.inputChunk->getRVA() + sym.offset;
898
    flag.flag = 0;
899
  }
900
  llvm::sort(flags,
901
             [](const RVAFlag &a, const RVAFlag &b) { return a.rva < b.rva; });
902
  assert(llvm::unique(flags, [](const RVAFlag &a,
903
                                const RVAFlag &b) { return a.rva == b.rva; }) ==
904
             flags.end() &&
905
         "RVA tables should be de-duplicated");
906
}
907

908
size_t ECCodeMapChunk::getSize() const {
909
  return map.size() * sizeof(chpe_range_entry);
910
}
911

912
void ECCodeMapChunk::writeTo(uint8_t *buf) const {
913
  auto table = reinterpret_cast<chpe_range_entry *>(buf);
914
  for (uint32_t i = 0; i < map.size(); i++) {
915
    const ECCodeMapEntry &entry = map[i];
916
    uint32_t start = entry.first->getRVA();
917
    table[i].StartOffset = start | entry.type;
918
    table[i].Length = entry.last->getRVA() + entry.last->getSize() - start;
919
  }
920
}
921

922
// MinGW specific, for the "automatic import of variables from DLLs" feature.
923
size_t PseudoRelocTableChunk::getSize() const {
924
  if (relocs.empty())
925
    return 0;
926
  return 12 + 12 * relocs.size();
927
}
928

929
// MinGW specific.
930
void PseudoRelocTableChunk::writeTo(uint8_t *buf) const {
931
  if (relocs.empty())
932
    return;
933

934
  ulittle32_t *table = reinterpret_cast<ulittle32_t *>(buf);
935
  // This is the list header, to signal the runtime pseudo relocation v2
936
  // format.
937
  table[0] = 0;
938
  table[1] = 0;
939
  table[2] = 1;
940

941
  size_t idx = 3;
942
  for (const RuntimePseudoReloc &rpr : relocs) {
943
    table[idx + 0] = rpr.sym->getRVA();
944
    table[idx + 1] = rpr.target->getRVA() + rpr.targetOffset;
945
    table[idx + 2] = rpr.flags;
946
    idx += 3;
947
  }
948
}
949

950
// Windows-specific. This class represents a block in .reloc section.
951
// The format is described here.
952
//
953
// On Windows, each DLL is linked against a fixed base address and
954
// usually loaded to that address. However, if there's already another
955
// DLL that overlaps, the loader has to relocate it. To do that, DLLs
956
// contain .reloc sections which contain offsets that need to be fixed
957
// up at runtime. If the loader finds that a DLL cannot be loaded to its
958
// desired base address, it loads it to somewhere else, and add <actual
959
// base address> - <desired base address> to each offset that is
960
// specified by the .reloc section. In ELF terms, .reloc sections
961
// contain relative relocations in REL format (as opposed to RELA.)
962
//
963
// This already significantly reduces the size of relocations compared
964
// to ELF .rel.dyn, but Windows does more to reduce it (probably because
965
// it was invented for PCs in the late '80s or early '90s.)  Offsets in
966
// .reloc are grouped by page where the page size is 12 bits, and
967
// offsets sharing the same page address are stored consecutively to
968
// represent them with less space. This is very similar to the page
969
// table which is grouped by (multiple stages of) pages.
970
//
971
// For example, let's say we have 0x00030, 0x00500, 0x00700, 0x00A00,
972
// 0x20004, and 0x20008 in a .reloc section for x64. The uppermost 4
973
// bits have a type IMAGE_REL_BASED_DIR64 or 0xA. In the section, they
974
// are represented like this:
975
//
976
//   0x00000  -- page address (4 bytes)
977
//   16       -- size of this block (4 bytes)
978
//     0xA030 -- entries (2 bytes each)
979
//     0xA500
980
//     0xA700
981
//     0xAA00
982
//   0x20000  -- page address (4 bytes)
983
//   12       -- size of this block (4 bytes)
984
//     0xA004 -- entries (2 bytes each)
985
//     0xA008
986
//
987
// Usually we have a lot of relocations for each page, so the number of
988
// bytes for one .reloc entry is close to 2 bytes on average.
989
BaserelChunk::BaserelChunk(uint32_t page, Baserel *begin, Baserel *end) {
990
  // Block header consists of 4 byte page RVA and 4 byte block size.
991
  // Each entry is 2 byte. Last entry may be padding.
992
  data.resize(alignTo((end - begin) * 2 + 8, 4));
993
  uint8_t *p = data.data();
994
  write32le(p, page);
995
  write32le(p + 4, data.size());
996
  p += 8;
997
  for (Baserel *i = begin; i != end; ++i) {
998
    write16le(p, (i->type << 12) | (i->rva - page));
999
    p += 2;
1000
  }
1001
}
1002

1003
void BaserelChunk::writeTo(uint8_t *buf) const {
1004
  memcpy(buf, data.data(), data.size());
1005
}
1006

1007
uint8_t Baserel::getDefaultType(llvm::COFF::MachineTypes machine) {
1008
  switch (machine) {
1009
  case AMD64:
1010
  case ARM64:
1011
    return IMAGE_REL_BASED_DIR64;
1012
  case I386:
1013
  case ARMNT:
1014
    return IMAGE_REL_BASED_HIGHLOW;
1015
  default:
1016
    llvm_unreachable("unknown machine type");
1017
  }
1018
}
1019

1020
MergeChunk::MergeChunk(uint32_t alignment)
1021
    : builder(StringTableBuilder::RAW, llvm::Align(alignment)) {
1022
  setAlignment(alignment);
1023
}
1024

1025
void MergeChunk::addSection(COFFLinkerContext &ctx, SectionChunk *c) {
1026
  assert(isPowerOf2_32(c->getAlignment()));
1027
  uint8_t p2Align = llvm::Log2_32(c->getAlignment());
1028
  assert(p2Align < std::size(ctx.mergeChunkInstances));
1029
  auto *&mc = ctx.mergeChunkInstances[p2Align];
1030
  if (!mc)
1031
    mc = make<MergeChunk>(c->getAlignment());
1032
  mc->sections.push_back(c);
1033
}
1034

1035
void MergeChunk::finalizeContents() {
1036
  assert(!finalized && "should only finalize once");
1037
  for (SectionChunk *c : sections)
1038
    if (c->live)
1039
      builder.add(toStringRef(c->getContents()));
1040
  builder.finalize();
1041
  finalized = true;
1042
}
1043

1044
void MergeChunk::assignSubsectionRVAs() {
1045
  for (SectionChunk *c : sections) {
1046
    if (!c->live)
1047
      continue;
1048
    size_t off = builder.getOffset(toStringRef(c->getContents()));
1049
    c->setRVA(rva + off);
1050
  }
1051
}
1052

1053
uint32_t MergeChunk::getOutputCharacteristics() const {
1054
  return IMAGE_SCN_MEM_READ | IMAGE_SCN_CNT_INITIALIZED_DATA;
1055
}
1056

1057
size_t MergeChunk::getSize() const {
1058
  return builder.getSize();
1059
}
1060

1061
void MergeChunk::writeTo(uint8_t *buf) const {
1062
  builder.write(buf);
1063
}
1064

1065
// MinGW specific.
1066
size_t AbsolutePointerChunk::getSize() const { return ctx.config.wordsize; }
1067

1068
void AbsolutePointerChunk::writeTo(uint8_t *buf) const {
1069
  if (ctx.config.is64()) {
1070
    write64le(buf, value);
1071
  } else {
1072
    write32le(buf, value);
1073
  }
1074
}
1075

1076
} // namespace lld::coff
1077