[BOLT] Add .relr.dyn section support

[yota9]

Summary

Vladislav Khmelevsky,
Advanced Software Technology Lab, Huawei

[rafauler]

We have a build error in premerge checks:

/var/lib/buildkite-agent/builds/llvm-project/bolt/lib/Core/Relocation.cpp:644:36: error: function definition is not allowed here
uint64_t Relocation::getRelative() {

[yota9]

Fix merge

[rafauler]

Code looks good. A few comments.

bolt/lib/Rewrite/RewriteInstance.cpp

2393

for -> in

2421

assert that DynamicRelrSize is a multiple of DynamicRelrEntrySize?

2423–2439

This has untested code because our testcase currently is very simple and doesn't have entries with bitmaps. Can we come up with a slightly more complicated testcase, just for relr, that exercises this decoding mechanism? (I'm not saying the code is wrong, it's just nice to have a testcase in case we ever change this and need to verify that it still works as intended).

5463

Is it possible to have some relocations in input RELA and some others in RELR? e.g. does the RELR extension allow for this?

5692

I guess you also rely on DynamicRelrEntrySize being non-zero for this patch to work, so maybe check here too, in addition to DynamicRelrAddress and DynamicRelrSize.

[yota9]

bolt/lib/Rewrite/RewriteInstance.cpp

2421

Would add check on dynamic reading

2423–2439

Extended the testcase a bit

5463

I was thinking about this too, but for now I don't see a reason a linker to make such a strange thing. Theoretically it is possible, but in practice - I don't think so. Even if I don't think we can currently handle such situations since we're not preserving input section information for each relocation. The same problem might appear when patching RELA and JMPREL relocations, currently we're saving only which type goes where, but theoretically there might be a problem e.g. different linkers might place some TLS relocations in any of these sections. When and if we would support rewriting binary and we would be able to remove old relocation section and create new we would be able to handle such cases, but for now I think the logic would stay as-is..

5692

Would add error check

[yota9]

Address comments

[rafauler]

LGTM with nits:

bolt/lib/Rewrite/RewriteInstance.cpp

5696

expected
presented -> present

5697

\n

5700

Expected -> expected

5701

\n

bolt/include/bolt/Core/BinarySection.h

public:
   bool isBSS() const {
     return (ELFType == ELF::SHT_NOBITS &&
             (ELFFlags & (ELF::SHF_ALLOC | ELF::SHF_WRITE)));
   }
   bool isTLS() const { return (ELFFlags & ELF::SHF_TLS); }
   bool isTBSS() const { return isBSS() && isTLS(); }
   bool isVirtual() const { return ELFType == ELF::SHT_NOBITS; }
   bool isRela() const { return ELFType == ELF::SHT_RELA; }
+  bool isRelr() const { return ELFType == ELF::SHT_RELR; }
   bool isWritable() const { return (ELFFlags & ELF::SHF_WRITE); }
   bool isAllocatable() const {
     if (isELF()) {
       return (ELFFlags & ELF::SHF_ALLOC) && !isTBSS();
     } else {
       // On non-ELF assume all sections are allocatable.
       return true;
     }

bolt/include/bolt/Core/Relocation.h

struct Relocation {
   static uint64_t getPC32();
 
   /// Return code for a PC-relative 8-byte relocation
   static uint64_t getPC64();
 
   /// Return code for a ABS 8-byte relocation
   static uint64_t getAbs64();
 
+  /// Return code for a RELATIVE relocation
+  static uint64_t getRelative();
+
   /// Return true if this relocation is PC-relative. Return false otherwise.
   bool isPCRelative() const { return isPCRelative(Type); }
 
   /// Return true if this relocation is R_*_RELATIVE type. Return false
   /// otherwise.
   bool isRelative() const { return isRelative(Type); }
 
   /// Emit relocation at a current \p Streamer' position. The caller is

bolt/include/bolt/Rewrite/RewriteInstance.h

private:
   void processLKBugTable();
 
   /// Process special linux kernel section, .smp_locks.
   void processLKSMPLocks();
 
   /// Read relocations from a given section.
   void readDynamicRelocations(const object::SectionRef &Section, bool IsJmpRel);
 
+  /// Read relocations from a given RELR section.
+  void readDynamicRelrRelocations(BinarySection &Section);
+
   /// Print relocation information.
   void printRelocationInfo(const RelocationRef &Rel, StringRef SymbolName,
                            uint64_t SymbolAddress, uint64_t Addend,
                            uint64_t ExtractedValue) const;
 
   /// Read relocations from a given section.
   void readRelocations(const object::SectionRef &Section);
 
#define ELF_FUNCTION(TYPE, FUNC)                                               \
   ELF_FUNCTION(void, patchELFDynamic);
 
   /// Patch .got
   ELF_FUNCTION(void, patchELFGOT);
 
   /// Patch allocatable relocation sections.
   ELF_FUNCTION(void, patchELFAllocatableRelaSections);
 
+  /// Patch allocatable relr section.
+  ELF_FUNCTION(void, patchELFAllocatableRelrSection);
+
   /// Finalize memory image of section header string table.
   ELF_FUNCTION(void, finalizeSectionStringTable);
 
   /// Return a list of all sections to include in the output binary.
   /// Populate \p NewSectionIndex with a map of input to output indices.
   template <typename ELFT>
   std::vector<typename object::ELFObjectFile<ELFT>::Elf_Shdr>
   getOutputSections(object::ELFObjectFile<ELFT> *File,
private:
   /// Track next available address for new allocatable sections.
   uint64_t NextAvailableAddress{0};
 
   /// Location and size of dynamic relocations.
   std::optional<uint64_t> DynamicRelocationsAddress;
   uint64_t DynamicRelocationsSize{0};
   uint64_t DynamicRelativeRelocationsCount{0};
 
+  // Location and size of .relr.dyn relocations.
+  std::optional<uint64_t> DynamicRelrAddress;
+  uint64_t DynamicRelrSize{0};
+  uint64_t DynamicRelrEntrySize{0};
+
   /// PLT relocations are special kind of dynamic relocations stored separately.
   std::optional<uint64_t> PLTRelocationsAddress;
   uint64_t PLTRelocationsSize{0};
 
   /// True if relocation of specified type came from .rela.plt
   DenseMap<uint64_t, bool> IsJmpRelocation;
 
   /// Index of specified symbol in the dynamic symbol table. NOTE Currently it

bolt/lib/Core/Relocation.cpp

 }
 
 uint64_t Relocation::getAbs64() {
   if (Arch == Triple::aarch64)
     return ELF::R_AARCH64_ABS64;
   return ELF::R_X86_64_64;
 }
 
+uint64_t Relocation::getRelative() {
+  if (Arch == Triple::aarch64)
+    return ELF::R_AARCH64_RELATIVE;
+  return ELF::R_X86_64_RELATIVE;
+}
+
 size_t Relocation::emit(MCStreamer *Streamer) const {
   const size_t Size = getSizeForType(Type);
   MCContext &Ctx = Streamer->getContext();
   if (isPCRelative(Type)) {
     MCSymbol *TempLabel = Ctx.createNamedTempSymbol();
     Streamer->emitLabel(TempLabel);
     const MCExpr *Value = nullptr;
     if (Symbol) {

bolt/lib/Rewrite/RewriteInstance.cpp

bool RewriteInstance::analyzeRelocation(
 
   (void)verifyExtractedValue;
   assert(verifyExtractedValue() && "mismatched extracted relocation value");
 
   return true;
 }
 
 void RewriteInstance::processDynamicRelocations() {
+  // Read .relr.dyn section containing compressed R_*_RELATIVE relocations.
+  if (DynamicRelrSize > 0) {
+    ErrorOr<BinarySection &> DynamicRelrSectionOrErr =
+        BC->getSectionForAddress(*DynamicRelrAddress);
+    if (!DynamicRelrSectionOrErr)
+      report_error("unable to find section corresponding to DT_RELR",
+                   DynamicRelrSectionOrErr.getError());
+    if (DynamicRelrSectionOrErr->getSize() != DynamicRelrSize)
+      report_error("section size mismatch for DT_RELRSZ",
+                   errc::executable_format_error);
+    readDynamicRelrRelocations(*DynamicRelrSectionOrErr);
+  }
+
   // Read relocations for PLT - DT_JMPREL.
   if (PLTRelocationsSize > 0) {
     ErrorOr<BinarySection &> PLTRelSectionOrErr =
         BC->getSectionForAddress(*PLTRelocationsAddress);
     if (!PLTRelSectionOrErr)
       report_error("unable to find section corresponding to DT_JMPREL",
                    PLTRelSectionOrErr.getError());
     if (PLTRelSectionOrErr->getSize() != PLTRelocationsSize)
for (const RelocationRef &Rel : Section.relocations()) {
 
     if (Symbol)
       SymbolIndex[Symbol] = getRelocationSymbol(InputFile, Rel);
 
     BC->addDynamicRelocation(Rel.getOffset(), Symbol, RType, Addend);
   }
 }
 
+void RewriteInstance::readDynamicRelrRelocations(BinarySection &Section) {
+  assert(Section.isAllocatable() && "allocatable expected");
+
+  LLVM_DEBUG({
+    StringRef SectionName = Section.getName();
+    dbgs() << "BOLT-DEBUG: reading relocations in section " << SectionName
+           << ":\n";
+  });
+
+  const uint64_t RType = Relocation::getRelative();
+  const uint8_t PSize = BC->AsmInfo->getCodePointerSize();
+  const uint64_t MaxDelta = ((CHAR_BIT * DynamicRelrEntrySize) - 1) * PSize;
+
+  auto ExtractAddendValue = [&](uint64_t Address) -> uint64_t {
+    ErrorOr<BinarySection &> Section = BC->getSectionForAddress(Address);
+    assert(Section && "cannot get section for data address from RELR");
+    DataExtractor DE = DataExtractor(Section->getContents(),
+                                     BC->AsmInfo->isLittleEndian(), PSize);
+    uint64_t Offset = Address - Section->getAddress();
+    return DE.getUnsigned(&Offset, PSize);
+  };
+
+  auto AddRelocation = [&](uint64_t Address) {
+    uint64_t Addend = ExtractAddendValue(Address);
+    LLVM_DEBUG(dbgs() << "BOLT-DEBUG: R_*_RELATIVE relocation at 0x"
+                      << Twine::utohexstr(Address) << " to 0x"
+                      << Twine::utohexstr(Addend) << '\n';);
+    BC->addDynamicRelocation(Address, nullptr, RType, Addend);
+  };
+
+  DataExtractor DE = DataExtractor(Section.getContents(),
+                                   BC->AsmInfo->isLittleEndian(), PSize);
+  uint64_t Offset = 0, Address = 0;
+  uint64_t RelrCount = DynamicRelrSize / DynamicRelrEntrySize;
+  while (RelrCount--) {
+    assert(DE.isValidOffset(Offset));
+    uint64_t Entry = DE.getUnsigned(&Offset, DynamicRelrEntrySize);
+    if ((Entry & 1) == 0) {
+      AddRelocation(Entry);
+      Address = Entry + PSize;
+    } else {
+      const uint64_t StartAddress = Address;
+      while (Entry >>= 1) {
+        if (Entry & 1)
+          AddRelocation(Address);
+
+        Address += PSize;
+      }
+
+      Address = StartAddress + MaxDelta;
+    }
+  }
+}
+
 void RewriteInstance::printRelocationInfo(const RelocationRef &Rel,
                                           StringRef SymbolName,
                                           uint64_t SymbolAddress,
                                           uint64_t Addend,
                                           uint64_t ExtractedValue) const {
   SmallString<16> TypeName;
   Rel.getTypeName(TypeName);
   const uint64_t Address = SymbolAddress + Addend;
BC->registerOrUpdateNoteSection(StrSecName,
                                   copyByteArray(NewStrTab),
                                   NewStrTab.size(),
                                   /*Alignment=*/1,
                                   /*IsReadOnly=*/true,
                                   ELF::SHT_STRTAB);
 }
 
 template <typename ELFT>
+void RewriteInstance::patchELFAllocatableRelrSection(
+    ELFObjectFile<ELFT> *File) {
+  if (!DynamicRelrAddress)
+    return;
+
+  raw_fd_ostream &OS = Out->os();
+  const uint8_t PSize = BC->AsmInfo->getCodePointerSize();
+  const uint64_t MaxDelta = ((CHAR_BIT * DynamicRelrEntrySize) - 1) * PSize;
+
+  auto FixAddend = [&](const BinarySection &Section, const Relocation &Rel) {
+    // Fix relocation symbol value in place if no static relocation found
+    // on the same address
+    if (Section.getRelocationAt(Rel.Offset))
+      return;
+
+    // No fixup needed if symbol address was not changed
+    const uint64_t Addend = getNewFunctionOrDataAddress(Rel.Addend);
+    if (!Addend)
+      return;
+
+    uint64_t FileOffset = Section.getOutputFileOffset();
+    if (!FileOffset)
+      FileOffset = Section.getInputFileOffset();
+
+    FileOffset += Rel.Offset;
+    OS.pwrite(reinterpret_cast<const char *>(&Addend), PSize, FileOffset);
+  };
+
+  // Fill new relative relocation offsets set
+  std::set<uint64_t> RelOffsets;
+  for (const BinarySection &Section : BC->allocatableSections()) {
+    const uint64_t SectionInputAddress = Section.getAddress();
+    uint64_t SectionAddress = Section.getOutputAddress();
+    if (!SectionAddress)
+      SectionAddress = SectionInputAddress;
+
+    for (const Relocation &Rel : Section.dynamicRelocations()) {
+      if (!Rel.isRelative())
+        continue;
+
+      uint64_t RelOffset =
+          getNewFunctionOrDataAddress(SectionInputAddress + Rel.Offset);
+
+      RelOffset = RelOffset == 0 ? SectionAddress + Rel.Offset : RelOffset;
+      assert((RelOffset & 1) == 0 && "Wrong relocation offset");
+      RelOffsets.emplace(RelOffset);
+      FixAddend(Section, Rel);
+    }
+  }
+
+  ErrorOr<BinarySection &> Section =
+      BC->getSectionForAddress(*DynamicRelrAddress);
+  assert(Section && "cannot get .relr.dyn section");
+  assert(Section->isRelr() && "Expected section to be SHT_RELR type");
+  uint64_t RelrDynOffset = Section->getInputFileOffset();
+  const uint64_t RelrDynEndOffset = RelrDynOffset + Section->getSize();
+
+  auto WriteRelr = [&](uint64_t Value) {
+    if (RelrDynOffset + DynamicRelrEntrySize > RelrDynEndOffset) {
+      errs() << "BOLT-ERROR: Offset overflow for relr.dyn section\n";
+      exit(1);
+    }
+
+    OS.pwrite(reinterpret_cast<const char *>(&Value), DynamicRelrEntrySize,
+              RelrDynOffset);
+    RelrDynOffset += DynamicRelrEntrySize;
+  };
+
+  for (auto RelIt = RelOffsets.begin(); RelIt != RelOffsets.end();) {
+    WriteRelr(*RelIt);
+    uint64_t Base = *RelIt++ + PSize;
+    while (1) {
+      uint64_t Bitmap = 0;
+      for (; RelIt != RelOffsets.end(); ++RelIt) {
+        const uint64_t Delta = *RelIt - Base;
+        if (Delta >= MaxDelta || Delta % PSize)
+          break;
+
+        Bitmap |= (1ULL << (Delta / PSize));
+      }
+
+      if (!Bitmap)
+        break;
+
+      WriteRelr((Bitmap << 1) | 1);
+      Base += MaxDelta;
+    }
+  }
+
+  // Fill the rest of the section with empty bitmap value
+  while (RelrDynOffset != RelrDynEndOffset)
+    WriteRelr(1);
+}
+
+template <typename ELFT>
 void
 RewriteInstance::patchELFAllocatableRelaSections(ELFObjectFile<ELFT> *File) {
   using Elf_Rela = typename ELFT::Rela;
   raw_fd_ostream &OS = Out->os();
   const ELFFile<ELFT> &EF = File->getELFFile();
 
   uint64_t RelDynOffset = 0, RelDynEndOffset = 0;
   uint64_t RelPltOffset = 0, RelPltEndOffset = 0;
for (BinarySection &Section : BC->allocatableSections()) {
           exit(1);
         }
 
         writeRela(&NewRelA, Offset);
       }
     }
   };
 
-  // The dynamic linker expects R_*_RELATIVE relocations to be emitted first
+  // Place R_*_RELATIVE relocations in RELA section if RELR is not presented.
+  // The dynamic linker expects all R_*_RELATIVE relocations in RELA
+  // to be emitted first.
+  if (!DynamicRelrAddress)
     writeRelocations(/* PatchRelative */ true);
   writeRelocations(/* PatchRelative */ false);
 
   auto fillNone = [&](uint64_t &Offset, uint64_t EndOffset) {
     if (!Offset)
       return;
 
     typename ELFObjectFile<ELFT>::Elf_Rela RelA;
     RelA.setSymbolAndType(0, Relocation::getNone(), EF.isMips64EL());
case ELF::DT_JMPREL:
       PLTRelocationsAddress = Dyn.getPtr();
       break;
     case ELF::DT_PLTRELSZ:
       PLTRelocationsSize = Dyn.getVal();
       break;
     case ELF::DT_RELACOUNT:
       DynamicRelativeRelocationsCount = Dyn.getVal();
       break;
+    case ELF::DT_RELR:
+      DynamicRelrAddress = Dyn.getPtr();
+      break;
+    case ELF::DT_RELRSZ:
+      DynamicRelrSize = Dyn.getVal();
+      break;
+    case ELF::DT_RELRENT:
+      DynamicRelrEntrySize = Dyn.getVal();
+      break;
     }
   }
 
   if (!DynamicRelocationsAddress || !DynamicRelocationsSize) {
     DynamicRelocationsAddress.reset();
     DynamicRelocationsSize = 0;
   }
 
   if (!PLTRelocationsAddress || !PLTRelocationsSize) {
     PLTRelocationsAddress.reset();
     PLTRelocationsSize = 0;
   }
+
+  if (!DynamicRelrAddress || !DynamicRelrSize) {
+    DynamicRelrAddress.reset();
+    DynamicRelrSize = 0;
+  } else if (!DynamicRelrEntrySize) {
+    errs() << "BOLT-ERROR: expeting DT_RELRENT to be presented "
+           << "in DYNAMIC section";
+    exit(1);
+  } else if (DynamicRelrSize % DynamicRelrEntrySize) {
+    errs() << "BOLT-ERROR: Expected RELR table size to be divisible "
+           << "by RELR entry size";
+    exit(1);
+  }
+
   return Error::success();
 }
 
 uint64_t RewriteInstance::getNewFunctionAddress(uint64_t OldAddress) {
   const BinaryFunction *Function = BC->getBinaryFunctionAtAddress(OldAddress);
   if (!Function)
     return 0;
 
void RewriteInstance::rewriteFile() {
   if (opts::EnableBAT)
     encodeBATSection();
 
   // Copy non-allocatable sections once allocatable part is finished.
   rewriteNoteSections();
 
   if (BC->HasRelocations) {
     patchELFAllocatableRelaSections();
+    patchELFAllocatableRelrSection();
     patchELFGOT();
   }
 
   // Patch dynamic section/segment.
   patchELFDynamic();
 
   // Update ELF book-keeping info.
   patchELFSectionHeaderTable();

bolt/test/AArch64/constant_island_pie_update.s

-// This test checks that the constant island value is updated if it
-// has dynamic relocation.
+// This test checks that the constant island offset and value is updated if
+// it has dynamic relocation. The tests checks both .rela.dyn and relr.dyn
+// dynamic relocations.
 // Also check that we don't duplicate CI if it has dynamic relocations.
 
 # RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown %s -o %t.o
+// .rela.dyn
 # RUN: %clang %cflags -fPIC -pie %t.o -o %t.rela.exe -nostdlib \
 # RUN:   -Wl,-q -Wl,-z,notext
 # RUN: llvm-bolt %t.rela.exe -o %t.rela.bolt --use-old-text=0 --lite=0
 # RUN: llvm-objdump -j .text -d %t.rela.bolt | FileCheck %s
 # RUN: llvm-readelf -rsW %t.rela.bolt | FileCheck --check-prefix=ELFCHECK %s
+// .relr.dyn
+# RUN: %clang %cflags -fPIC -pie %t.o -o %t.relr.exe -nostdlib \
+# RUN:   -Wl,-q -Wl,-z,notext -Wl,--pack-dyn-relocs=relr
+# RUN: llvm-bolt %t.relr.exe -o %t.relr.bolt --use-old-text=0 --lite=0
+# RUN: llvm-objdump -j .text -d %t.relr.bolt | FileCheck %s
+# RUN: llvm-readelf -rsW %t.relr.bolt | FileCheck --check-prefix=ELFCHECK %s
+# RUN: llvm-readelf -SW %t.relr.bolt | FileCheck --check-prefix=RELRSZCHECK %s
 
 // Check that the CI value was updated
 # CHECK: [[#%x,ADDR:]] <exitLocal>:
 # CHECK: {{.*}} <$d>:
 # CHECK-NEXT: {{.*}} .word 0x{{[0]+}}[[#ADDR]]
 # CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x{{[0]+}}[[#ADDR]]
+# CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x{{[0]+}}[[#ADDR]]
+# CHECK-NEXT: {{.*}} .word 0x00000000
+
 
 // Check that we've relaxed adr to adrp + add to refer external CI
 # CHECK: <addressDynCi>:
 # CHECK-NEXT: adrp
 # CHECK-NEXT: add
 
-// Check that relocation offset was updated
+// Check that relocation offsets were updated
 # ELFCHECK: [[#%x,OFF:]] [[#%x,INFO_DYN:]] R_AARCH64_RELATIVE
+# ELFCHECK-NEXT: [[#OFF + 8]] {{0*}}[[#INFO_DYN]] R_AARCH64_RELATIVE
+# ELFCHECK-NEXT: [[#OFF + 24]] {{0*}}[[#INFO_DYN]] R_AARCH64_RELATIVE
 # ELFCHECK: {{.*}}[[#OFF]] {{.*}} $d
 
+// Check that .relr.dyn size is 2 bytes to ensure that last 2 relocations were
+// encoded as a bitmap so the total section size for 3 relocations is 2 bytes.
+# RELRSZCHECK: .relr.dyn RELR [[#%x,ADDR:]] [[#%x,OFF:]] {{0*}}10
+
   .text
   .align 4
   .local exitLocal
   .type exitLocal, %function
 exitLocal:
   add x1, x1, #1
   add x1, x1, #1
   nop
   nop
   ret
   .size exitLocal, .-exitLocal
 
   .global _start
   .type _start, %function
 _start:
   mov x0, #0
   adr x1, .Lci
   ldr x1, [x1]
   blr x1
   mov x0, #1
   bl exitLocal
   nop
 .Lci:
   .xword exitLocal
+  .xword exitLocal
+  .xword 0
+  .xword exitLocal
   .size _start, .-_start
 
   .global addressDynCi
   .type addressDynCi, %function
 addressDynCi:
   adr x1, .Lci
   bl _start
 .size addressDynCi, .-addressDynCi