[ELF] Fix link failure with Android compressed relocation support.

[efriedma]

Summary

Android uses a compressed relocation format, which means the size of the relocation section isn't predictable based on the number of relocations, and can vary if the layout changes in any way. To deal with this, the linker normally runs multiple passes until the layout converges.

The layout should converge if the size of the compressed relocation section increases monotonically: if the size of an encoded offset increases by one byte, the larget value which can be encoded is multiplied by 128, so the representable offsets grow much faster than the size of the section itself.

The problem here is that there is no code to ensure the size of the section doesn't decrease. If the size of the relocation section decreases, the relative offsets can increase due to alignment restrictions, so that can force the size of the relocation section to increase again. The end result is an infinite loop; the loop gets cut off after 10 iterations with the message "thunk creation not converged".

To avoid this issue, this patch adds padding to the end of the relocation section if its size would decrease. I think the extra padding is harmless because of the way the format is defined: decoding stops after it reaches the number of relocations specified in the section's header. Not completely sure about that, though.

[ruiu]

How did you find it? If you find it in the wild, how large is the padding you added to workaround the issue for your program?

[efriedma]

Found as a build failure testing a new compiler on Android.

For the library that failed to build, this patch adds one byte "extra" padding to rela.dyn.

[rprichard]

Adding zero padding to the end of the SHT_ANDROID_REL[A] section shouldn't be a problem. It looks like the original Android relocation_packer tool left up to a page of zero bytes at the end of the packed section, and the decoders in Bionic and LLVM would ignore the trailing bytes. relocation_packer doesn't loop stabilizing SLEB sizes, but I think it didn't need to. When it shrunk a .rel[a].dyn section, it apparently only shrunk the section by a multiple of the page size. It left the virtual addresses of the sections following .rel[a].dyn unchanged, and I don't think it adjusted the offset/addend values of the relocations.

FWIW: I fixed a similar issue in the LLVM assembler with the exception table: https://reviews.llvm.org/D42722

I wonder if a non-contrived input could require more than 10 rounds to converge. It seems unlikely to happen, at least.

This change seems fine to me.

test/ELF/pack-dyn-relocs-loop.s

13

s/abd/and/ ?

[peter.smith]

FWIW: I fixed a similar issue in the LLVM assembler with the exception table: https://reviews.llvm.org/D42722

I wonder if a non-contrived input could require more than 10 rounds to converge. It seems unlikely to happen, at least.

This change seems fine to me.

I think that this change makes sense as well. The Thunks code has to be careful with Short branch selection in order to not oscillate between short and long branches. One thing that may be worth doing (not necessarily in this patch) is to make the error message less specific to Thunks, and potentially extract it from the Thunks code. At the moment all the Targets supporting packed relocations also support Thunks but this might always be the case.

I had originally chosen 10 for the pass limit for Thunks based on the relative sizes of the Thunks and the Thumb 1 branch range, and the practical experience of never seeing a working program go past 5 passes. Anything that had reached 10 had always been a bug. I suspect that a similar calculation could be done for the relocation packer if we were worried that 10 might not be enough.

[ruiu]

Looking good, but I'd like to wait for pcc's response for a few days if he's okay to have a padding at the end of the section.

[ruiu]

LGTM

Please submit.

ELF/SyntheticSections.cpp

for (Elf_Rela &R : NonRelatives) {
       Add(R.r_info);
       if (Config->IsRela) {
         Add(R.r_addend - Addend);
         Addend = R.r_addend;
       }
     }
   }
 
+  // Don't allow the section to shrink; otherwise the size of the section can
+  // oscillate infinitely.
+  if (RelocData.size() < OldSize)
+    RelocData.append(OldSize - RelocData.size(), 0);
+
   // Returns whether the section size changed. We need to keep recomputing both
   // section layout and the contents of this section until the size converges
   // because changing this section's size can affect section layout, which in
   // turn can affect the sizes of the LEB-encoded integers stored in this
   // section.
   return RelocData.size() != OldSize;
 }
 

test/ELF/pack-dyn-relocs-loop.s

+// REQUIRES: arm, aarch64
+
+// RUN: llvm-mc -filetype=obj -triple=aarch64-none-linux-android %s -o %t.o
+// RUN: ld.lld -shared %t.o -o %t.so --pack-dyn-relocs=android
+// RUN: llvm-readobj -s %t.so | FileCheck %s
+
+// This test is making sure the Android packed relocation support doesn't
+// cause an infinite loop due to the size of the section oscillating
+// (because the size of the section impacts the layout of the following
+// sections).
+
+// This test is very sensitive to the exact section sizes and offsets,
+// so check that they don't change.
+// CHECK:         Name: .rela.dyn (33)
+// CHECK-NEXT:    Type: SHT_ANDROID_RELA (0x60000002)
+// CHECK-NEXT:    Flags [ (0x2)
+// CHECK-NEXT:      SHF_ALLOC (0x2)
+// CHECK-NEXT:    ]
+// CHECK-NEXT:    Address: 0x210
+// CHECK-NEXT:    Offset: 0x210
+// CHECK-NEXT:    Size: 21
+
+// CHECK:         Name: x (43)
+// CHECK-NEXT:    Type: SHT_PROGBITS (0x1)
+// CHECK-NEXT:    Flags [ (0x2)
+// CHECK-NEXT:      SHF_ALLOC (0x2)
+// CHECK-NEXT:    ]
+// CHECK-NEXT:    Address: 0x225
+// CHECK-NEXT:    Offset: 0x225
+// CHECK-NEXT:    Size: 64980
+
+// CHECK:         Name: barr (45)
+// CHECK-NEXT:    Type: SHT_PROGBITS (0x1)
+// CHECK-NEXT:    Flags [ (0x2)
+// CHECK-NEXT:      SHF_ALLOC (0x2)
+// CHECK-NEXT:    ]
+// CHECK-NEXT:    Address: 0xFFFA
+// CHECK-NEXT:    Offset: 0xFFFA
+// CHECK-NEXT:    Size: 0
+
+// CHECK:         Name: foo (62)
+// CHECK-NEXT:    Type: SHT_PROGBITS (0x1)
+// CHECK-NEXT:    Flags [ (0x3)
+// CHECK-NEXT:      SHF_ALLOC (0x2)
+// CHECK-NEXT:      SHF_WRITE (0x1)
+// CHECK-NEXT:    ]
+// CHECK-NEXT:    Address: 0x10004
+// CHECK-NEXT:    Offset: 0x10004
+// CHECK-NEXT:    Size: 12
+
+
+.data
+.long 0
+
+.section foo,"aw"
+foof:
+.long foof
+.long bar-53
+.long bar
+
+.section x,"a"
+.zero 64980
+
+.section barr,"a"
+.p2align 1
+bar: