[ELF] Update .relr.dyn once in the absence of SECTIONS commands

[MaskRay]

Summary

If an output section does not have internal . = ALIGN(x);, the spacing among
its input sections remain unchanged after script->assignAddresses is called
for the first time.

r_offset is inputSec->getOutputSection().addr + inputSec->outSecOff + offsetInSec
If we delay inputSec->getOutputSection().addr addition to writeTo,
updateAllocSize can be called only once.

Conservatively use !hasSectionsCommand to mean .relr.dyn only needs one update.

With this change, the problem described by D67164 is very difficult to trigger.
I cannot figure out a case to get the ".relr.dyn needs ... padding word(s)"
diagnostic, but keep it just in case.

My --threads=8 chrome link is 1% faster.

[peter.smith]

Will have to have a think to see if I can spot any problems.

If an output section does not have internal . = ALIGN(x);, the spacing among its input sections remain unchanged after script->assignAddresses is called for the first time.

Are you referring to an individual InputSection or an InputSectionDescription as one might have in a LinkerScript? In the presence of thunks you can have situations like:
// First call to assignAddresses, for brevity the first column is outSecOff. The second section has been overaligned to a cache-line size boundary which isn't unheard of at -O3.

0x0 section1 align 4 size 4
// 12 bytes padding
0x10 section2 align 16 size 4

// Case add a single range extension thunk in the middle, no change in overall size

0x0 section1 align 4 size 4
0x4 thunk align 4 size 8
// 4 bytes padding
0x10 section2 align 16 size 4

// Case add two range extension thunks in the middle, cross an alignment boundary.

0x0 section1 align 4 size 4
0x4 thunk align 4 size 8
0xc thunk align 4 size 8
// 12 bytes padding
0x20 section2 align 16 size 4

It is true that we won't see a range extension thunk in the middle of a .relr.dyn section, so this may not be important. It would certainly be true that the input sections in executable output sections might change address due to range-extension thunks. This is not hugely likely in AArch64 though as it would need > 128 MiB of code to trigger.

[MaskRay]

You are right. target->needsThunks targets cannot use this optimization, either. InputSectionDescription spacing is not fixed in the presence of thunks.

Now this optimization seems unworthy because of the complexity to finalizeAddressDependentContent.

---

If !script->hasSectionsCommand and there is no symbol assignment (the majority of x86 programs), script->assignAddresses can be called only once.
But adding the condition make need to complicate finalizeAddressDependentContent (D117528).

lld/ELF/SyntheticSections.h

public:
   SmallVector<RelativeReloc, 0> relocs;
 };
 
 // RelrSection is used to encode offsets for relative relocations.
 // Proposal for adding SHT_RELR sections to generic-abi is here:
 //   https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg
 // For more details, see the comment in RelrSection::updateAllocSize().
 template <class ELFT> class RelrSection final : public RelrBaseSection {
-  using Elf_Relr = typename ELFT::Relr;
+  using uint = typename ELFT::uint;
 
 public:
   RelrSection();
 
   bool updateAllocSize() override;
-  size_t getSize() const override { return relrRelocs.size() * this->entsize; }
-  void writeTo(uint8_t *buf) override {
-    memcpy(buf, relrRelocs.data(), getSize());
-  }
+  size_t getSize() const override { return size * this->entsize; }
+  void writeTo(uint8_t *buf) override;
 
 private:
-  SmallVector<Elf_Relr, 0> relrRelocs;
+  SmallVector<std::pair<const OutputSection *, SmallVector<uint, 0>>, 0> vec;
+  size_t size = 0;
 };
 
 struct SymbolTableEntry {
   Symbol *sym;
   size_t strTabOffset;
 };
 
 class SymbolTableBaseSection : public SyntheticSection {

lld/ELF/SyntheticSections.cpp

template <class ELFT> bool RelrSection<ELFT>::updateAllocSize() {
   // a single bitmap can encode up to 31 relocations in a 32-bit object, and
   // 63 relocations in a 64-bit object.
   //
   // This encoding has a couple of interesting properties:
   // 1. Looking at any entry, it is clear whether it's an address or a bitmap:
   //    even means address, odd means bitmap.
   // 2. Just a simple list of addresses is a valid encoding.
 
-  size_t oldSize = relrRelocs.size();
-  relrRelocs.clear();
-
   // Same as Config->Wordsize but faster because this is a compile-time
   // constant.
   const size_t wordsize = sizeof(typename ELFT::uint);
 
   // Number of bits to use for the relocation offsets bitmap.
   // Must be either 63 or 31.
   const size_t nBits = wordsize * 8 - 1;
 
-  // Get offsets for all relative relocations and sort them.
-  std::vector<uint64_t> offsets;
-  for (const RelativeReloc &rel : relocs)
-    offsets.push_back(rel.getOffset());
+  const size_t oldSize = size;
+  size = 0;
+  vec.clear();
+  SmallVector<uint, 0> offsets;
+  for (size_t i = 0, e = relocs.size(); i != e;) {
+    const OutputSection *osec = relocs[i].inputSec->getOutputSection();
+    do
+      offsets.push_back(relocs[i].inputSec->getOffset(relocs[i].offsetInSec));
+    while (++i != e && relocs[i].inputSec->getOutputSection() == osec);
     llvm::sort(offsets);
 
-  // For each leading relocation, find following ones that can be folded
-  // as a bitmap and fold them.
-  for (size_t i = 0, e = offsets.size(); i < e;) {
-    // Add a leading relocation.
-    relrRelocs.push_back(Elf_Relr(offsets[i]));
-    uint64_t base = offsets[i] + wordsize;
-    ++i;
+    SmallVector<uint, 0> entries;
+    for (size_t j = 0, end = offsets.size(); j != end;) {
+      entries.push_back(offsets[j]);
+      uint64_t base = offsets[j] + wordsize;
+      ++j;
 
-    // Find foldable relocations to construct bitmaps.
-    while (i < e) {
+      for (;;) {
         uint64_t bitmap = 0;
-
-      while (i < e) {
-        uint64_t delta = offsets[i] - base;
-
-        // If it is too far, it cannot be folded.
-        if (delta >= nBits * wordsize)
-          break;
-
-        // If it is not a multiple of wordsize away, it cannot be folded.
-        if (delta % wordsize)
+        for (; j != end; ++j) {
+          uint64_t d = offsets[j] - base;
+          if (d >= nBits * wordsize || d % wordsize)
             break;
-
-        // Fold it.
-        bitmap |= 1ULL << (delta / wordsize);
-        ++i;
+          bitmap |= uint64_t(1) << (d / wordsize);
         }
-
         if (!bitmap)
           break;
-
-      relrRelocs.push_back(Elf_Relr((bitmap << 1) | 1));
+        entries.push_back((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));
+    size += entries.size();
+    vec.emplace_back(osec, std::move(entries));
+    offsets.clear();
   }
 
-  return relrRelocs.size() != oldSize;
+  // 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 (size < oldSize) {
+    log(".relr.dyn needs " + Twine(oldSize - size) + " padding word(s)");
+    size = oldSize;
+  }
+  return size != oldSize;
+}
+
+template <class ELFT> void RelrSection<ELFT>::writeTo(uint8_t *buf) {
+  auto *out = reinterpret_cast<typename ELFT::Relr *>(buf);
+  for (const auto &v : vec) {
+    uint64_t addr = v.first->addr;
+    for (uint entry : v.second)
+      *out++ = entry & 1 ? entry : addr + entry;
+    size -= v.second.size();
+  }
+  // See the comment above.
+  for (; size; --size)
+    *out++ = 1;
 }
 
 SymbolTableBaseSection::SymbolTableBaseSection(StringTableSection &strTabSec)
     : SyntheticSection(strTabSec.isDynamic() ? (uint64_t)SHF_ALLOC : 0,
                        strTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
                        config->wordsize,
                        strTabSec.isDynamic() ? ".dynsym" : ".symtab"),
       strTabSec(strTabSec) {}

lld/ELF/Writer.cpp

if (config->fixCortexA8) {
       changed |= a32p.createFixes();
     }
 
     if (in.mipsGot)
       in.mipsGot->updateAllocSize();
 
     for (Partition &part : partitions) {
       changed |= part.relaDyn->updateAllocSize();
-      if (part.relrDyn)
-        changed |= part.relrDyn->updateAllocSize();
+
+      // OutptSection address addition in .relr.dyn's computation is delayed to
+      // writeTo. RelrSection::vec is fixed (no need to call updateAllocSize
+      // again) if InputSections' outSecOff values remain unchanged, which is
+      // the case if no output section has . = ALIGN(x). We emulate the
+      // condition with hasSectionsCommand.
+      if (part.relrDyn) {
+        if (assignPasses == 0 || script->hasSectionsCommand)
+          part.relrDyn->updateAllocSize();
+        else
+          assert(!part.relrDyn->updateAllocSize());
+      }
     }
 
     const Defined *changedSym = script->assignAddresses();
     if (!changed) {
       // Some symbols may be dependent on section addresses. When we break the
       // loop, the symbol values are finalized because a previous
       // assignAddresses() finalized section addresses.
       if (!changedSym)

lld/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: ld.lld -pie --pack-dyn-relocs=relr -z max-page-size=4096 %t.o -o %t
 # 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:   0x2F30 R_AARCH64_RELATIVE -
 # RELR-NEXT:   0x2F38 R_AARCH64_RELATIVE -
 # RELR-NEXT:   0x3000 R_AARCH64_RELATIVE -
 # RELR-NEXT: }
 
 .section .data.rel.ro
 .align 3