[lld] [COFF, ARM64] Handle ADRP immediate offsets in relocations

[mstorsjo]

Summary

Also handle overflow correctly in LDR/STR relocations. Even if the offset range of a 8 byte LDR instruction is 15 bit (even if the immediate itself is 12 bit) due to a 3 bit shift, only include up to 12 bits of byte level offset after doing the relocation, by limiting the range of the immediate by the number of shifted bits.

[ruiu]

It's not very clear to me if what this patch does is correct, even though I clearly understand each line of code. Can you write a function comment instead of writing a comment for each line?

[mstorsjo]

Wrote a new per-function comment as suggested by Rui, hopefully explaining better what is done now.

[ruiu]

COFF/Chunks.cpp

204

So this is more like a scale than a size?

(Is there any documentation about this relocation?)

213–215

You are shifting Imm to the right and then to the left, which looks a bit odd.

215

So, if I understand correctly, this is equivalent to

write32le(Off, (Orig & FFB003FF) | (Imm + ...));

(Sorry I cannot calculate it in my head but I think it should be simpler.)

[mstorsjo]

COFF/Chunks.cpp

204

Yes, it's actually a shift/scale. I picked the name Size originally, because that's the name of the bits in the opcode, from the ARMv8 architecture reference manual.

I don't know of any documentation of the relocation itself - the official pecoff document only lists the relocation names/numbers, but no description of what they should do. This code is based on testing how link.exe handles them.

213–215

I can get reduce the amount of shifting by doing the calculation in scaled units instead of in bytes - I did that for clarity, but perhaps it only obscured things.

In that case, it's probably simplest to extend the existing applyArm64Imm with a parameter that limits the wraparound range/mask from 0xFFF to 0xFFF >> Scale - that's the actual effect of this change.

[mstorsjo]

Updated handling of scaled ldr relocations by using applyArm64Imm as before, but with a new parameter instead. Hopefully this is clearer.

[ruiu]

COFF/Chunks.cpp

187

We do not use optional parameters that often, as it basically defines two or more functions with the same name which increases program complexity (even though the increase may be small.) Just pass 0 instead.

test/COFF/arm64-symbol-offset.yaml

1

Can you reduce the size of the test? I don't think you need a test case of 200 lines to verify this change.

[mstorsjo]

Removed use of a default parameter, squashed a smaller testcase into the existing arm64-relocs-imports.test instead.

[mstorsjo]

Rui, any further comments on this one?

[ruiu]

LGTM

COFF/Chunks.cpp

void SectionChunk::applyRelARM(uint8_t *Off, uint16_t Type, OutputSection *OS,
   case IMAGE_REL_ARM_BLX23T:    applyBranch24T(Off, SX - P - 4); break;
   case IMAGE_REL_ARM_SECTION:   applySecIdx(Off, OS); break;
   case IMAGE_REL_ARM_SECREL:    applySecRel(this, Off, OS, S); break;
   default:
     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
   }
 }
 
-static void applyArm64Addr(uint8_t *Off, uint64_t Imm) {
+// Interpret the existing immediate value as a byte offset to the
+// target symbol, then update the instruction with the immediate as
+// the page offset from the current instruction to the target.
+static void applyArm64Addr(uint8_t *Off, uint64_t S, uint64_t P) {
+  uint32_t Orig = read32le(Off);
+  uint64_t Imm = ((Orig >> 29) & 0x3) | ((Orig >> 3) & 0x1FFFFC);
+  S += Imm;
+  Imm = (S >> 12) - (P >> 12);
   uint32_t ImmLo = (Imm & 0x3) << 29;
   uint32_t ImmHi = (Imm & 0x1FFFFC) << 3;
   uint64_t Mask = (0x3 << 29) | (0x1FFFFC << 3);
-  write32le(Off, (read32le(Off) & ~Mask) | ImmLo | ImmHi);
+  write32le(Off, (Orig & ~Mask) | ImmLo | ImmHi);
 }
 
 // Update the immediate field in a AARCH64 ldr, str, and add instruction.
-static void applyArm64Imm(uint8_t *Off, uint64_t Imm) {
+// Optionally limit the range of the written immediate by one or more bits
+// (RangeLimit).
+static void applyArm64Imm(uint8_t *Off, uint64_t Imm, uint32_t RangeLimit = 0) {
   uint32_t Orig = read32le(Off);
   Imm += (Orig >> 10) & 0xFFF;
   Orig &= ~(0xFFF << 10);
-  write32le(Off, Orig | ((Imm & 0xFFF) << 10));
+  write32le(Off, Orig | ((Imm & (0xFFF >> RangeLimit)) << 10));
 }
 
+// Add the 12 bit page offset to the existing immediate.
+// Ldr/str instructions store the opcode immediate scaled
+// by the load/store size (giving a larger range for larger
+// loads/stores). The immediate is always (both before and after
+// fixing up the relocation) stored scaled similarly.
+// Even if larger loads/stores have a larger range, limit the
+// effective offset to 12 bit, since it is intended to be a
+// page offset.
 static void applyArm64Ldr(uint8_t *Off, uint64_t Imm) {
   uint32_t Orig = read32le(Off);
   uint32_t Size = Orig >> 30;
   // 0x04000000 indicates SIMD/FP registers
   // 0x00800000 indicates 128 bit
   if ((Orig & 0x4800000) == 0x4800000)
     Size += 4;
   if ((Imm & ((1 << Size) - 1)) != 0)
     fatal("misaligned ldr/str offset");
-  applyArm64Imm(Off, Imm >> Size);
+  applyArm64Imm(Off, Imm >> Size, Size);
 }
 
 void SectionChunk::applyRelARM64(uint8_t *Off, uint16_t Type, OutputSection *OS,
                                  uint64_t S, uint64_t P) const {
   switch (Type) {
-  case IMAGE_REL_ARM64_PAGEBASE_REL21: applyArm64Addr(Off, (S >> 12) - (P >> 12)); break;
+  case IMAGE_REL_ARM64_PAGEBASE_REL21: applyArm64Addr(Off, S, P); break;
   case IMAGE_REL_ARM64_PAGEOFFSET_12A: applyArm64Imm(Off, S & 0xfff); break;
   case IMAGE_REL_ARM64_PAGEOFFSET_12L: applyArm64Ldr(Off, S & 0xfff); break;
   case IMAGE_REL_ARM64_BRANCH26:       or32(Off, ((S - P) & 0x0FFFFFFC) >> 2); break;
   case IMAGE_REL_ARM64_ADDR32:         add32(Off, S + Config->ImageBase); break;
   case IMAGE_REL_ARM64_ADDR64:         add64(Off, S + Config->ImageBase); break;
   default:
     fatal("unsupported relocation type 0x" + Twine::utohexstr(Type));
   }

 
 void ImportThunkChunkARM::writeTo(uint8_t *Buf) const {
   memcpy(Buf + OutputSectionOff, ImportThunkARM, sizeof(ImportThunkARM));
   // Fix mov.w and mov.t operands.
   applyMOV32T(Buf + OutputSectionOff, ImpSymbol->getRVA() + Config->ImageBase);
 }
 
 void ImportThunkChunkARM64::writeTo(uint8_t *Buf) const {
-  int64_t PageOff = (ImpSymbol->getRVA() >> 12) - (RVA >> 12);
   int64_t Off = ImpSymbol->getRVA() & 0xfff;
   memcpy(Buf + OutputSectionOff, ImportThunkARM64, sizeof(ImportThunkARM64));
-  applyArm64Addr(Buf + OutputSectionOff, PageOff);
+  applyArm64Addr(Buf + OutputSectionOff, ImpSymbol->getRVA(), RVA);
   applyArm64Ldr(Buf + OutputSectionOff + 4, Off);
 }
 
 void LocalImportChunk::getBaserels(std::vector<Baserel> *Res) {
   Res->emplace_back(getRVA());
 }
 
 size_t LocalImportChunk::getSize() const {

test/COFF/arm64-symbol-offset.yaml

+# REQUIRES: aarch64
+
+# RUN: yaml2obj < %s > %t.obj
+# RUN: llvm-objdump -d %t.obj | FileCheck %s -check-prefix BEFORE
+# RUN: lld-link /entry:main /subsystem:console /out:%t.exe %t.obj
+# RUN: llvm-objdump -d %t.exe | FileCheck %s -check-prefix AFTER
+
+# adrp x0, .data
+# adrp x0, .Lvar2
+# adrp x0, .data+4000 == .Lvar2
+# adrp x0, .Lvar3
+# adrp x0, .data+5000 == .Lvar3
+# adrp x0, .Lvar2+1000 = .Lvar3
+# then the same for "add x0, x0", "ldrb w0, [x0, :lo12:<expr>], and
+# "ldr x0, [x0, :lo12:<expr>]"
+# Finally a "ldr x0, [x0, #8184]" with an immediate that after shifting
+# is > 12 bits, that gets clamped after relocation.
+
+# BEFORE: Disassembly of section .text:
+# BEFORE:        0:       00 00 00 90     adrp    x0, #0
+# BEFORE:        4:       00 00 00 90     adrp    x0, #0
+# BEFORE:        8:       00 7d 00 90     adrp    x0, #16384000
+# BEFORE:        c:       00 00 00 90     adrp    x0, #0
+# BEFORE:       10:       40 9c 00 90     adrp    x0, #20480000
+# BEFORE:       14:       40 1f 00 90     adrp    x0, #4096000
+# BEFORE:       18:       00 00 00 91     add     x0, x0, #0
+# BEFORE:       1c:       00 00 00 91     add     x0, x0, #0
+# BEFORE:       20:       00 80 3e 91     add     x0, x0, #4000
+# BEFORE:       24:       00 00 00 91     add     x0, x0, #0
+# BEFORE:       28:       00 20 0e 91     add     x0, x0, #904
+# BEFORE:       2c:       00 a0 0f 91     add     x0, x0, #1000
+# BEFORE:       30:       00 00 40 39     ldrb    w0, [x0]
+# BEFORE:       34:       00 00 40 39     ldrb    w0, [x0]
+# BEFORE:       38:       00 80 7e 39     ldrb    w0, [x0, #4000]
+# BEFORE:       3c:       00 00 40 39     ldrb    w0, [x0] 
+# BEFORE:       40:       00 20 4e 39     ldrb    w0, [x0, #904]
+# BEFORE:       44:       00 a0 4f 39     ldrb    w0, [x0, #1000]  
+# BEFORE:       48:       00 00 40 f9     ldr     x0, [x0]
+# BEFORE:       4c:       00 00 40 f9     ldr     x0, [x0]
+# BEFORE:       50:       00 d0 47 f9     ldr     x0, [x0, #4000]
+# BEFORE:       54:       00 00 40 f9     ldr     x0, [x0]
+# BEFORE:       58:       00 c4 41 f9     ldr     x0, [x0, #904]
+# BEFORE:       5c:       00 f4 41 f9     ldr     x0, [x0, #1000]
+# BEFORE:       60:       00 fc 4f f9     ldr     x0, [x0, #8184]
+# BEFORE:       64:       c0 03 5f d6     ret
+
+# AFTER: Disassembly of section .text:
+# AFTER:  140002000:      e0 ff ff f0     adrp    x0, #-4096
+# AFTER:  140002004:      e0 ff ff f0     adrp    x0, #-4096
+# AFTER:  140002008:      e0 ff ff f0     adrp    x0, #-4096
+# AFTER:  14000200c:      00 00 00 90     adrp    x0, #0
+# AFTER:  140002010:      00 00 00 90     adrp    x0, #0
+# AFTER:  140002014:      00 00 00 90     adrp    x0, #0
+# AFTER:  140002018:      00 00 00 91     add     x0, x0, #0
+# AFTER:  14000201c:      00 80 3e 91     add     x0, x0, #4000
+# AFTER:  140002020:      00 80 3e 91     add     x0, x0, #4000
+# AFTER:  140002024:      00 20 0e 91     add     x0, x0, #904
+# AFTER:  140002028:      00 20 0e 91     add     x0, x0, #904
+# AFTER:  14000202c:      00 20 0e 91     add     x0, x0, #904
+# AFTER:  140002030:      00 00 40 39     ldrb    w0, [x0]
+# AFTER:  140002034:      00 80 7e 39     ldrb    w0, [x0, #4000] 
+# AFTER:  140002038:      00 80 7e 39     ldrb    w0, [x0, #4000]
+# AFTER:  14000203c:      00 20 4e 39     ldrb    w0, [x0, #904]  
+# AFTER:  140002040:      00 20 4e 39     ldrb    w0, [x0, #904]
+# AFTER:  140002044:      00 20 4e 39     ldrb    w0, [x0, #904]
+# AFTER:  140002048:      00 00 40 f9     ldr     x0, [x0]
+# AFTER:  14000204c:      00 d0 47 f9     ldr     x0, [x0, #4000]
+# AFTER:  140002050:      00 d0 47 f9     ldr     x0, [x0, #4000]
+# AFTER:  140002054:      00 c4 41 f9     ldr     x0, [x0, #904]
+# AFTER:  140002058:      00 c4 41 f9     ldr     x0, [x0, #904]
+# AFTER:  14000205c:      00 c4 41 f9     ldr     x0, [x0, #904]
+# AFTER:  140002060:      00 fc 47 f9     ldr     x0, [x0, #4088]
+# AFTER:  140002064:      c0 03 5f d6     ret
+
+--- !COFF
+header:
+  Machine:         IMAGE_FILE_MACHINE_ARM64
+  Characteristics: [  ]
+sections:
+  - Name:            .text
+    Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
+    Alignment:       4
+    SectionData:     0000009000000090007d009000000090409c0090401f0090000000910000009100803e910000009100200e9100a00f91000040390000403900807e390000403900204e3900a04f39000040f9000040f900d047f9000040f900c441f900f441f900fc4ff9c0035fd6
+    Relocations:
+      - VirtualAddress:  0
+        SymbolName:      .data
+        Type:            4
+      - VirtualAddress:  4
+        SymbolName:      .Lvar2
+        Type:            4
+      - VirtualAddress:  8
+        SymbolName:      .data
+        Type:            4
+      - VirtualAddress:  12
+        SymbolName:      .Lvar3
+        Type:            4
+      - VirtualAddress:  16
+        SymbolName:      .data
+        Type:            4
+      - VirtualAddress:  20
+        SymbolName:      .Lvar2
+        Type:            4
+      - VirtualAddress:  24
+        SymbolName:      .data
+        Type:            6
+      - VirtualAddress:  28
+        SymbolName:      .Lvar2
+        Type:            6
+      - VirtualAddress:  32
+        SymbolName:      .data
+        Type:            6
+      - VirtualAddress:  36
+        SymbolName:      .Lvar3
+        Type:            6
+      - VirtualAddress:  40
+        SymbolName:      .data
+        Type:            6
+      - VirtualAddress:  44
+        SymbolName:      .Lvar2
+        Type:            6
+      - VirtualAddress:  48
+        SymbolName:      .data
+        Type:            7
+      - VirtualAddress:  52
+        SymbolName:      .Lvar2
+        Type:            7
+      - VirtualAddress:  56
+        SymbolName:      .data
+        Type:            7
+      - VirtualAddress:  60
+        SymbolName:      .Lvar3
+        Type:            7
+      - VirtualAddress:  64
+        SymbolName:      .data
+        Type:            7
+      - VirtualAddress:  68
+        SymbolName:      .Lvar2
+        Type:            7
+      - VirtualAddress:  72
+        SymbolName:      .data
+        Type:            7
+      - VirtualAddress:  76
+        SymbolName:      .Lvar2
+        Type:            7
+      - VirtualAddress:  80
+        SymbolName:      .data
+        Type:            7
+      - VirtualAddress:  84
+        SymbolName:      .Lvar3
+        Type:            7
+      - VirtualAddress:  88
+        SymbolName:      .data
+        Type:            7
+      - VirtualAddress:  92
+        SymbolName:      .Lvar2
+        Type:            7
+      - VirtualAddress:  96
+        SymbolName:      .data
+        Type:            7
+  - Name:            .data
+    Characteristics: [ IMAGE_SCN_CNT_INITIALIZED_DATA, IMAGE_SCN_MEM_READ, IMAGE_SCN_MEM_WRITE ]
+    Alignment:       4
+    SectionData:     '00000000'
+symbols:
+  - Name:            .text
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+    SectionDefinition:
+      Length:          104
+      NumberOfRelocations: 25
+      NumberOfLinenumbers: 0
+      CheckSum:        1438860354
+      Number:          1
+  - Name:            .data
+    Value:           0
+    SectionNumber:   2
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+    SectionDefinition:
+      Length:          16384
+      NumberOfRelocations: 0
+      NumberOfLinenumbers: 0
+      CheckSum:        0
+      Number:          2
+  - Name:            main
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
+  - Name:            .Lvar1
+    Value:           0
+    SectionNumber:   2
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+  - Name:            .Lvar2
+    Value:           4000
+    SectionNumber:   2
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+  - Name:            .Lvar3
+    Value:           5000
+    SectionNumber:   2
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+...