[BOLT] Improve dynamic relocations support for CI

[yota9]

Summary

This patch fixes few problems with supporting dynamic relocations in CI.

1. After dynamic relocations and functions were read search for dynamic

relocations located in functions. Currently we expected them only to be
relative and only to be in constant island. Mark islands of such
functions to have dynamic relocations and create CI access symbol on the
relocation offset, so the BD would be created for such place.

2. During function disassemble and handling address reference for

constant island check if the referred external CI has dynamic
relocation. And if it has one we would continue to refer original CI
rather then creating a local copy.

3. After function disassembly stage mark function that has dynamic reloc

in CI as non-simple. We don't want such functions to be optimized, since
such passes as split function would create 2 copies of CI which we
unable to support currently.

4. During updating output values for BF search for BD located in CI and

update their output locations.

5. On dynamic relocation patching stage search for binary data located

on relocation offset. If it was moved use new relocation offset value
rather then an old one.

Vladislav Khmelevsky,
Advanced Software Technology Lab, Huawei

[yota9]

nit
@rafauler Gentle ping :)

[yota9]

clang format

[rafauler]

bolt/include/bolt/Core/BinaryFunction.h

170

Can you expand this comment to:

Set true if constant island contains dynamic relocations, which happens if binary is linked with -znotext

1952

Add comment

Support dynamic relocations in constant islands, which happens if binary is linked with -znotext

1954

nit: Dynamic -> dynamic

bolt/lib/Core/BinaryContext.cpp

394–405

Is this because we don't support cloning dynamic relocs? If yes, we can expand this comment to clarify:

// Fall-back to referencing the original constant island in the presence of dynamic relocs, as we currently do not support cloning them. Notice: we might fail to link because of this, if the original constant island is far away.

[yota9]

Add comments to code

bolt/lib/Core/BinaryContext.cpp

394–405

Yes, it is true. Add comment

[rafauler]

LGTM

bolt/include/bolt/Core/BinaryFunction.h

struct IslandInfo {
     /// identifying the end of a chunk of data inside code. DataOffsets contain
     /// all offsets of $d symbols and CodeOffsets all offsets of $x symbols.
     std::set<uint64_t> DataOffsets;
     std::set<uint64_t> CodeOffsets;
 
     /// List of relocations associated with data in the constant island
     std::map<uint64_t, Relocation> Relocations;
 
+    /// Set true if constant island contains dynamic relocations, which may
+    /// happen if binary is linked with -z notext option.
+    bool HasDynamicRelocations{false};
+
     /// Offsets in function that are data values in a constant island identified
     /// after disassembling
     std::map<uint64_t, MCSymbol *> Offsets;
     SmallPtrSet<MCSymbol *, 4> Symbols;
     DenseMap<const MCSymbol *, BinaryFunction *> ProxySymbols;
     DenseMap<const MCSymbol *, MCSymbol *> ColdSymbols;
     /// Keeps track of other functions we depend on because there is a reference
     /// to the constant islands in them.
assert((!Islands->Offsets.count(Offset) ||
            "Inconsistent island symbol management");
     if (!Islands->Offsets.count(Offset)) {
       Islands->Offsets[Offset] = Symbol;
       Islands->Symbols.insert(Symbol);
     }
     return Symbol;
   }
 
+  /// Support dynamic relocations in constant islands, which may happen if
+  /// binary is linked with -z notext option.
+  void markIslandDynamicRelocationAtAddress(uint64_t Address) {
+    if (!isInConstantIsland(Address)) {
+      errs() << "BOLT-ERROR: dynamic relocation found for text section at 0x"
+             << Twine::utohexstr(Address) << "\n";
+      exit(1);
+    }
+
+    // Mark island to have dynamic relocation
+    Islands->HasDynamicRelocations = true;
+
+    // Create island access, so we would emit the label and
+    // move binary data during updateOutputValues, making us emit
+    // dynamic relocation with the right offset value.
+    getOrCreateIslandAccess(Address);
+  }
+
+  bool hasDynamicRelocationAtIsland() const {
+    return !!(Islands && Islands->HasDynamicRelocations);
+  }
+
   /// Called by an external function which wishes to emit references to constant
   /// island symbols of this function. We create a proxy for it, so we emit
   /// separate symbols when emitting our constant island on behalf of this other
   /// function.
   MCSymbol *getOrCreateProxyIslandAccess(uint64_t Address,
                                          BinaryFunction &Referrer) {
     MCSymbol *Symbol = getOrCreateIslandAccess(Address);
     if (!Symbol)

bolt/include/bolt/Rewrite/RewriteInstance.h

const PLTSectionInfo *getPLTSectionInfo(StringRef SectionName) {
 
     return nullptr;
   }
 
   /// Exception handling and stack unwinding information in this binary.
   ErrorOr<BinarySection &> LSDASection{std::errc::bad_address};
   ErrorOr<BinarySection &> EHFrameSection{std::errc::bad_address};
 
-  /// .got.plt sections.
-  ///
-  /// Contains jump slots (addresses) indirectly referenced by
-  /// instructions in .plt section.
-  ErrorOr<BinarySection &> GOTPLTSection{std::errc::bad_address};
-
-  /// .rela.plt section.
-  ///
-  /// Contains relocations against .got.plt.
-  ErrorOr<BinarySection &> RelaPLTSection{std::errc::bad_address};
-  ErrorOr<BinarySection &> RelaDynSection{std::errc::bad_address};
-
   /// .note.gnu.build-id section.
   ErrorOr<BinarySection &> BuildIDSection{std::errc::bad_address};
 
   /// .note.stapsdt section.
   /// Contains information about statically defined tracing points
   ErrorOr<BinarySection &> SDTSection{std::errc::bad_address};
 
   /// .pseudo_probe_desc section.

bolt/lib/Core/BinaryContext.cpp

if (isAArch64()) {
     auto IslandIter = AddressToConstantIslandMap.lower_bound(Address);
 
     if (IslandIter != AddressToConstantIslandMap.begin() &&
         (IslandIter == AddressToConstantIslandMap.end() ||
          IslandIter->first > Address))
       --IslandIter;
 
     if (IslandIter != AddressToConstantIslandMap.end()) {
-      if (MCSymbol *IslandSym =
-              IslandIter->second->getOrCreateProxyIslandAccess(Address, BF)) {
+      // Fall-back to referencing the original constant island in the presence
+      // of dynamic relocs, as we currently do not support cloning them.
+      // Notice: we might fail to link because of this, if the original constant
+      // island we are referring would be emitted too far away.
+      if (IslandIter->second->hasDynamicRelocationAtIsland()) {
+        MCSymbol *IslandSym =
+            IslandIter->second->getOrCreateIslandAccess(Address);
+        if (IslandSym)
+          return std::make_pair(IslandSym, 0);
+      } else if (MCSymbol *IslandSym =
+                     IslandIter->second->getOrCreateProxyIslandAccess(Address,
+                                                                      BF)) {
         BF.createIslandDependency(IslandSym, IslandIter->second);
         return std::make_pair(IslandSym, 0);
       }
     }
   }
 
   // Note that the address does not necessarily have to reside inside
   // a section, it could be an absolute address too.

bolt/lib/Core/BinaryFunction.cpp

if (BC.HasRelocations || isInjected()) {
     const uint64_t StartOffset = Layout.getSymbolOffset(*getSymbol());
     const uint64_t EndOffset = Layout.getSymbolOffset(*getFunctionEndLabel());
     setOutputAddress(BaseAddress + StartOffset);
     setOutputSize(EndOffset - StartOffset);
     if (hasConstantIsland()) {
       const uint64_t DataOffset =
           Layout.getSymbolOffset(*getFunctionConstantIslandLabel());
       setOutputDataAddress(BaseAddress + DataOffset);
+      for (auto It : Islands->Offsets) {
+        const uint64_t OldOffset = It.first;
+        BinaryData *BD = BC.getBinaryDataAtAddress(getAddress() + OldOffset);
+        if (!BD)
+          continue;
+
+        MCSymbol *Symbol = It.second;
+        const uint64_t NewOffset = Layout.getSymbolOffset(*Symbol);
+        BD->setOutputLocation(*getCodeSection(), NewOffset);
+      }
     }
     if (isSplit()) {
       for (FunctionFragment &FF : getLayout().getSplitFragments()) {
         ErrorOr<BinarySection &> ColdSection =
             getCodeSection(FF.getFragmentNum());
         // If fragment is empty, cold section might not exist
         if (FF.empty() && ColdSection.getError())
           continue;

bolt/lib/Rewrite/RewriteInstance.cpp

for (auto ISym = SortedMarkerSymbols.begin();
     if (ISym->Type == MarkerSymType::DATA) {
       BF->markDataAtOffset(EntryOffset);
       BC->AddressToConstantIslandMap[ISym->Address] = BF;
       continue;
     }
     llvm_unreachable("Unknown marker");
   }
 
+  if (BC->isAArch64()) {
+    // Check for dynamic relocations that might be contained in
+    // constant islands.
+    for (const BinarySection &Section : BC->allocatableSections()) {
+      const uint64_t SectionAddress = Section.getAddress();
+      for (const Relocation &Rel : Section.dynamicRelocations()) {
+        const uint64_t RelAddress = SectionAddress + Rel.Offset;
+        BinaryFunction *BF =
+            BC->getBinaryFunctionContainingAddress(RelAddress,
+                                                   /*CheckPastEnd*/ false,
+                                                   /*UseMaxSize*/ true);
+        if (BF) {
+          assert(Rel.isRelative() && "Expected relative relocation for island");
+          BF->markIslandDynamicRelocationAtAddress(RelAddress);
+        }
+      }
+    }
+  }
+
   if (opts::LinuxKernelMode) {
     // Read all special linux kernel sections and their relocations
     processLKSections();
   } else {
     // Read all relocations now that we have binary functions mapped.
     processRelocations();
   }
   registerFragments();
if (HasDebugInfo && !opts::UpdateDebugSections && !opts::AggregateOnly) {
     errs() << "BOLT-WARNING: debug info will be stripped from the binary. "
               "Use -update-debug-sections to keep it.\n";
   }
 
   HasTextRelocations = (bool)BC->getUniqueSectionByName(".rela.text");
   HasSymbolTable = (bool)BC->getUniqueSectionByName(".symtab");
   LSDASection = BC->getUniqueSectionByName(".gcc_except_table");
   EHFrameSection = BC->getUniqueSectionByName(".eh_frame");
-  GOTPLTSection = BC->getUniqueSectionByName(".got.plt");
-  RelaPLTSection = BC->getUniqueSectionByName(".rela.plt");
-  RelaDynSection = BC->getUniqueSectionByName(".rela.dyn");
   BuildIDSection = BC->getUniqueSectionByName(".note.gnu.build-id");
   SDTSection = BC->getUniqueSectionByName(".note.stapsdt");
   PseudoProbeDescSection = BC->getUniqueSectionByName(".pseudo_probe_desc");
   PseudoProbeSection = BC->getUniqueSectionByName(".pseudo_probe");
 
   if (ErrorOr<BinarySection &> BATSec =
           BC->getUniqueSectionByName(BoltAddressTranslation::SECTION_NAME)) {
     // Do not read BAT when plotting a heatmap
void RewriteInstance::postProcessFunctions() {
   BC->skipMarkedFragments();
   BC->clearFragmentsToSkip();
 
   BC->TotalScore = 0;
   BC->SumExecutionCount = 0;
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
+    // Set function as non-simple if it has dynamic relocations
+    // in constant island, we don't want this function to be optimized
+    // e.g. function splitting is unsupported.
+    if (Function.hasDynamicRelocationAtIsland())
+      Function.setSimple(false);
+
     if (Function.empty())
       continue;
 
     Function.postProcessCFG();
 
     if (opts::PrintAll || opts::PrintCFG)
       Function.print(outs(), "after building cfg");
 
RewriteInstance::patchELFAllocatableRelaSections(ELFObjectFile<ELFT> *File) {
   const ELFFile<ELFT> &EF = File->getELFFile();
 
   uint64_t RelDynOffset = 0, RelDynEndOffset = 0;
   uint64_t RelPltOffset = 0, RelPltEndOffset = 0;
 
   auto setSectionFileOffsets = [&](uint64_t Address, uint64_t &Start,
                                    uint64_t &End) {
     ErrorOr<BinarySection &> Section = BC->getSectionForAddress(Address);
+    assert(Section && "cannot get relocation section");
     Start = Section->getInputFileOffset();
     End = Start + Section->getSize();
   };
 
   if (!DynamicRelocationsAddress && !PLTRelocationsAddress)
     return;
 
   if (DynamicRelocationsAddress)
     setSectionFileOffsets(*DynamicRelocationsAddress, RelDynOffset,
                           RelDynEndOffset);
 
   if (PLTRelocationsAddress)
     setSectionFileOffsets(*PLTRelocationsAddress, RelPltOffset,
                           RelPltEndOffset);
 
   DynamicRelativeRelocationsCount = 0;
 
   auto writeRela = [&OS](const Elf_Rela *RelA, uint64_t &Offset) {
     OS.pwrite(reinterpret_cast<const char *>(RelA), sizeof(*RelA), Offset);
     Offset += sizeof(*RelA);
   };
 
   auto writeRelocations = [&](bool PatchRelative) {
     for (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()) {
         const bool IsRelative = Rel.isRelative();
         if (PatchRelative != IsRelative)
           continue;
 
         if (IsRelative)
           ++DynamicRelativeRelocationsCount;
 
         Elf_Rela NewRelA;
-        uint64_t SectionAddress = Section.getOutputAddress();
-        SectionAddress =
-            SectionAddress == 0 ? Section.getAddress() : SectionAddress;
         MCSymbol *Symbol = Rel.Symbol;
         uint32_t SymbolIdx = 0;
         uint64_t Addend = Rel.Addend;
+        uint64_t RelOffset =
+            getNewFunctionOrDataAddress(SectionInputAddress + Rel.Offset);
 
+        RelOffset = RelOffset == 0 ? SectionAddress + Rel.Offset : RelOffset;
         if (Rel.Symbol) {
           SymbolIdx = getOutputDynamicSymbolIndex(Symbol);
         } else {
           // Usually this case is used for R_*_(I)RELATIVE relocations
           const uint64_t Address = getNewFunctionOrDataAddress(Addend);
           if (Address)
             Addend = Address;
         }
 
         NewRelA.setSymbolAndType(SymbolIdx, Rel.Type, EF.isMips64EL());
-        NewRelA.r_offset = SectionAddress + Rel.Offset;
+        NewRelA.r_offset = RelOffset;
         NewRelA.r_addend = Addend;
 
         const bool IsJmpRel =
             !!(IsJmpRelocation.find(Rel.Type) != IsJmpRelocation.end());
         uint64_t &Offset = IsJmpRel ? RelPltOffset : RelDynOffset;
         const uint64_t &EndOffset =
             IsJmpRel ? RelPltEndOffset : RelDynEndOffset;
         if (!Offset || !EndOffset) {

bolt/test/AArch64/constant_island_pie_update.s

 // This test checks that the constant island value is updated if it
 // has dynamic relocation.
+// Also check that we don't duplicate CI if it has dynamic relocations.
 
-# RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown \
-# RUN:   %s -o %t.o
-# RUN: %clang %cflags -fPIC -pie %t.o -o %t.exe -Wl,-q -nostdlib -Wl,-z,notext
-# RUN: llvm-bolt %t.exe -o %t.bolt --use-old-text=0 --lite=0
-# RUN: llvm-objdump -j .text -dR %t.bolt | FileCheck %s
+# RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown %s -o %t.o
+# 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
 
-# CHECK: R_AARCH64_RELATIVE *ABS*+0x[[#%x,ADDR:]]
-# CHECK: [[#ADDR]] <exitLocal>:
+// Check that the CI value was updated
+# CHECK: [[#%x,ADDR:]] <exitLocal>:
 # CHECK: {{.*}} <$d>:
 # 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
+# ELFCHECK: [[#%x,OFF:]] [[#%x,INFO_DYN:]] R_AARCH64_RELATIVE
+# ELFCHECK: {{.*}}[[#OFF]] {{.*}} $d
+
   .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
   .size _start, .-_start
+
+  .global addressDynCi
+  .type addressDynCi, %function
+addressDynCi:
+  adr x1, .Lci
+  bl _start
+.size addressDynCi, .-addressDynCi