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

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.  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.

Differential Revision: https://reviews.llvm.org/D53003

llvm-svn: 344300

2 files changed, 71 insertions, 0 deletions

diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index e32b8c29fc1..92cad5a0ce3 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -1724,6 +1724,11 @@ bool AndroidPackedRelocationSection<ELFT>::updateAllocSize() {
     }
   }
 
+  // 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
diff --git a/lld/test/ELF/pack-dyn-relocs-loop.s b/lld/test/ELF/pack-dyn-relocs-loop.s
new file mode 100644
index 00000000000..308ead5cf5f
--- /dev/null
+++ b/lld/test/ELF/pack-dyn-relocs-loop.s
@@ -0,0 +1,66 @@
+// 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: