[ELF] Don't shrink RelrSection

[MaskRay]

Summary

Fixes PR43214.

The size of SHT_RELR may oscillate between 2 numbers (see D53003 for a
similar --pack-dyn-relocs=android issue). This can happen if the shrink
of SHT_RELR causes it to take more words to encode relocation offsets
(this can happen with thunks or segments with overlapping p_offset
ranges), and the expansion of SHT_RELR causes it to take fewer words to
encode relocation offsets.

To avoid the issue, add padding 1s to the end of the relocation section
if its size would decrease. Trailing 1s do not decode to more
relocations.

[MaskRay]

Add a test

[grimar]

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

11 ↗

(On Diff #218697)

Just an idea, not sure how much is reasonable:

LLD sometimes calls log() and print().
The latter is used to test ICF:

1. CHECK: selected section {{.*}}:(.text.f1)
2. CHECK: removing identical section {{.*}}:(.text.f2)

You can probably add a log() call and -v and check that resize happened.

[MaskRay]

Add log() as grimar suggested

[peter.smith]

As far as I can tell this will definitely prevent the oscillation and has already seen success in the Android relocation side. As Rui mentioned on the PR, it would be useful to put a generic convergence limit on finalizeAddressDependentContent() to catch an infinite loop that we'd not thought possible. This could be done separately though.

[MaskRay]

In D67164#1657824, @peter.smith wrote:

As far as I can tell this will definitely prevent the oscillation and has already seen success in the Android relocation side. As Rui mentioned on the PR, it would be useful to put a generic convergence limit on finalizeAddressDependentContent() to catch an infinite loop that we'd not thought possible. This could be done separately though.

Thanks! As grimar suggested, we may need some log() in these iterating loops as well.

lld/trunk/ELF/SyntheticSections.cpp

while (i < e) {
       if (!bitmap)
         break;
 
       relrRelocs.push_back(Elf_Relr((bitmap << 1) | 1));
       base += nBits * wordsize;
     }
   }
 
+  // Don't allow the section to shrink; otherwise the size of the section can
+  // oscillate infinitely. Trailing 1s do not decode to more relocations.
+  if (relrRelocs.size() < oldSize) {
+    log(".relr.dyn needs " + Twine(oldSize - relrRelocs.size()) +
+        " padding word(s)");
+    relrRelocs.resize(oldSize, Elf_Relr(1));
+  }
+
   return relrRelocs.size() != oldSize;
 }
 
 SymbolTableBaseSection::SymbolTableBaseSection(StringTableSection &strTabSec)
     : SyntheticSection(strTabSec.isDynamic() ? (uint64_t)SHF_ALLOC : 0,
                        strTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
                        config->wordsize,
                        strTabSec.isDynamic() ? ".dynsym" : ".symtab"),

lld/trunk/test/ELF/pack-dyn-relocs-relr-loop.s

+# REQUIRES: aarch64
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %s -o %t.o
+# RUN: ld.lld -pie --pack-dyn-relocs=relr -z max-page-size=4096 --verbose %t.o -o %t 2>&1 | FileCheck %s
+# RUN: llvm-readobj -r %t | FileCheck --check-prefix=RELR %s
+
+## This test makes sure we don't shrink .relr.dyn, otherwise its size may
+## oscillate between 2 words and 3 words.
+
+## The test is very sensitive to the exact section sizes and offsets,
+## make sure .data is located at a page boundary.
+
+# CHECK: .relr.dyn needs 1 padding word(s)
+
+# RELR:      .relr.dyn {
+# RELR-NEXT:   0x2F40 R_AARCH64_RELATIVE - 0x0
+# RELR-NEXT:   0x2F48 R_AARCH64_RELATIVE - 0x0
+# RELR-NEXT:   0x3000 R_AARCH64_RELATIVE - 0x0
+# RELR-NEXT: }
+
+.section .data.rel.ro
+.align 3
+.space 0xce0
+foo:
+## Encoded by the first word of .relr.dyn
+.quad foo
+
+## Encoded by the second word of .relr.dyn
+.quad foo
+
+.section .data
+.align 3
+## If .data is at 0x3000, the relocation will be encoded by the second word.
+## If we shrink .relr.dyn, the end of .dynamic will be at 0x2ff8 and .data
+## will be at 0x3ff8, we will need the third word to encode this relocation,
+## which will cause .relr.dyn to expand again.
+.quad foo