[BOLT] Replace relocations container type

[yota9]

Summary

Synchronize binary function and binary section relocations container
type in order to be able to change relocation struct fields inplace.

[ayermolo]

bolt/include/bolt/Core/Relocation.h

58 ↗

(On Diff #416800)

Can you add description of this function.

[yota9]

bolt/include/bolt/Core/Relocation.h

58 ↗

(On Diff #416800)

Sure will do

[yota9]

clang format + comment

[yota9]

nit

[yota9]

Change runtime test to ordinary

[rafauler]

Thanks!

bolt/include/bolt/Core/BinarySection.h

290

Here you remove the accessors to the non-const version of relocs, but I suspect we will need them to avoid using the mutable hack.

bolt/include/bolt/Core/Relocation.h

53 ↗

(On Diff #418236)

Why mutable? Except when storing mutexes, usually mutable indicates a problem with the class that should be solved with a redesign (removing const where appropriate). Is there a way to use non-const Relocation objects?

[yota9]

bolt/include/bolt/Core/BinarySection.h

290

The problem is deeper as I understand. I'm not c++ expert, but the relocations are stored in std::set<Relocation, std::less<>>container, which does not give the in container edit abilities due to the std::less sorting. The mutable fields are hacky, but AFAIU such fields are not not participated in the container sorting mechanisms and though might be edited in place. Correct me if I wrong, I really don't like c++ some times like this :) Maybe you can suggest some of the alternatives to change the container type for example :)

[rafauler]

We can change BinarySection's RelocationSetType to be a sorted std::vector instead, as per https://llvm.org/docs/ProgrammersManual.html#a-sorted-vector

We would need to insert the relocations in any order, and then sort this vector and remove duplicates. Although I'm not convinced that we need to keep relocations in a sorted order or to remove duplicates. @maksfb What do you think?

[yota9]

@rafauler After some thinking I've desided to replace std::set with std::map. The relocations are identified by the offset field,
so it is good-enough solution that gives us fast search abilities and any inplace manipulations of the relocations struct.

[yota9]

clang-format

[yota9]

BTW the std::map is used as a container for the function relocations, so now we've got "synced up" them :)

[rafauler]

I think the strategy looks good. I've been looking at this at the memory profiler, and it doesn't increase memory utilization by much by adding these extra fields to the Relocation class because after BinaryFunction::disassembly(), we call clearList(Relocations), which frees the memory used by relocation objects that are in the text sections. Relocations associated with data sections still use 0.4% of all memory allocation. The increase in memory utilization is from 48B to 72B (50% increase for this class), which should translate to an overall 0.2% increase in memory utilization for one of our large binaries.

I'm concerned that by emitting so many labels in the data sections, we could slow down the emitter. Could you check by how much time BOLT is slowing down after this patch, in a typical large binary? Just so we are aware and tracking memory and time regressions.

Tagging @maksfb to be aware of the memory regression.

[rafauler]

I also recommend checking peak memory utilization with /usr/bin/time

[yota9]

Rebase

[yota9]

Hello @rafaelauler . I will try to measure the results later, but I see that something going on with the buildbots, some of the tests are failed with 60 sec timeout. Since now I'm able to run x86 test on arm I've tested it and everything went momentally, I don't see the reason why the tests are failing. Do you have any idea? Thank you!

[rafauler]

If there is a timeout, I guess we can just run/try again.

[yota9]

@rafaelauler I've tried couple of times, but the result seems to be the same...

[rafauler]

Do you have an environment that is the same as the one used in pre-merge checks? (Ubuntu, I guess). That might be important to repro the timeout.

[yota9]

@rafaelauler Right now I've got only ubuntu aarch64 :( I will try to check it on x86 ubuntu locally soon, although I don't really see the reason for such a strange behaviour..

[yota9]

nit
@rafauler It was my fault, not all tests should be OK, sorry for bothering :)

[yota9]

@rafauler I've checked the biggest binary I have. As for the time after couple of launches I see 380-390 sec before patch and 390-400sec after patch, which I assume is just a negligible difference. As for the memory the I've got 38279868kb before and 38348116kb after (+68mb or +0.2%) which is small amount too and matches yours results. So I assume it's a reasonable change with an acceptable overhead :)

[yota9]

@rafaelauler Gentle ping

[rafauler]

I suspect the regression in time might be because we are emitting too many labels unnecessarily. We are emitting a label for every relocation, right? Maybe the best approach would be to create a special class for DynamicRelocation and only that will have extra fields to store a label, and then change our emitter to emit a label only for those objects (as opposed to every static reloc), and then later in updateOutputValues fetch that label? I think this would avoid the memory/time regression, unless I'm missing something.

[yota9]

@rafauler Well, the time regression is about couple of %, even before patch I got up to 390sec, and 390+ sec after. The memory regression is negligible. It is possible to do what you're suggesting, but it looks to me like extra complication that personally me would like to avoid. I really don't think it is worse it, but it is discussible question

[yota9]

@rafauler I've decided to add extra arg for relocation emission, it is easy to add and easy to revert in case we won't need it anymore

[rafauler]

I've been discussing this diff with the team and in general people are not only concerned about the memory/time regression, but it feels like a hacky approach. We need proper support for dynamic relocations in BOLT, and in doing so, the code should become easier to understand and maintain. What's your take? Do you think that you could design things in a way to make these concerns go away? If you would like to, we can set up a time to discuss my suggestion over VC or text chat, if it's not clear.

[yota9]

@rafaelauler As I understand we will need to keep dynamic relocations in binary function/data like we do it for static relocation and emit labels in the right places. Let's discuss it in discord in the nearest time if you have any suggestion. I don't really like the binary function part of the code too (initially I've made the review NFC). As for this review I suggest to separate the container type refactoring and to think about the dynamic relocations emission separately, what do you think?

[rafauler]

I think we are on the same page. I'm fine with separating the refactoring in two separate diffs too.

[yota9]

Remove all changes but refactoring

[yota9]

@rafaelauler gentle ping

[yota9]

@rafaelauler Gentle ping

[rafauler]

This looks good to me, but I don't think it makes sense to commit this yet unless we have a real use case for this (perhaps in a follow-up diff).

bolt/include/bolt/Core/BinaryContext.h

public:
   void foldFunction(BinaryFunction &ChildBF, BinaryFunction &ParentBF);
 
   /// Add a Section relocation at a given \p Address.
   void addRelocation(uint64_t Address, MCSymbol *Symbol, uint64_t Type,
                      uint64_t Addend = 0, uint64_t Value = 0);
 
   /// Return a relocation registered at a given \p Address, or nullptr if there
   /// is no relocation at such address.
-  const Relocation *getRelocationAt(uint64_t Address);
+  const Relocation *getRelocationAt(uint64_t Address) const;
+
+  Relocation *getRelocationAt(uint64_t Address);
 
   /// Register a presence of PC-relative relocation at the given \p Address.
   void addPCRelativeDataRelocation(uint64_t Address) {
     DataPCRelocations.emplace(Address);
   }
 
   /// Register dynamic relocation at \p Address.
   void addDynamicRelocation(uint64_t Address, MCSymbol *Symbol, uint64_t Type,
                             uint64_t Addend, uint64_t Value = 0);
 
   /// Return a dynamic relocation registered at a given \p Address, or nullptr
   /// if there is no dynamic relocation at such address.
-  const Relocation *getDynamicRelocationAt(uint64_t Address);
+  const Relocation *getDynamicRelocationAt(uint64_t Address) const;
+
+  Relocation *getDynamicRelocationAt(uint64_t Address);
 
   /// Remove registered relocation at a given \p Address.
   bool removeRelocationAt(uint64_t Address);
 
   /// This function makes sure that symbols referenced by ambiguous relocations
   /// are marked as immovable. For now, if a section relocation points at the
   /// boundary between two symbols then those symbols are marked as immovable.
   void markAmbiguousRelocations(BinaryData &BD, const uint64_t Address);

bolt/include/bolt/Core/BinarySection.h

class BinarySection {
   const uint64_t Size;         // Input section size
   uint64_t InputFileOffset{0}; // Offset in the input binary
   unsigned Alignment;          // alignment in bytes (must be > 0)
   unsigned ELFType;            // ELF section type
   unsigned ELFFlags;           // ELF section flags
 
   // Relocations associated with this section. Relocation offsets are
   // wrt. to the original section address and size.
-  using RelocationSetType = std::set<Relocation, std::less<>>;
+  using RelocationSetType = std::map<uint64_t, Relocation>;
   RelocationSetType Relocations;
 
   // Dynamic relocations associated with this section. Relocation offsets are
   // from the original section address.
   RelocationSetType DynamicRelocations;
 
   // Pending relocations for this section.
   std::vector<Relocation> PendingRelocations;
public:
   }
 
   /// Does this section contain the range [\p Address, \p Address + \p Size)?
   /// Note: this is in terms of the original mapped binary addresses.
   bool containsRange(uint64_t Address, uint64_t Size) const {
     return containsAddress(Address) && Address + Size <= getEndAddress();
   }
 
-  /// Iterate over all non-pending relocations for this section.
   iterator_range<RelocationSetType::iterator> relocations() {
     return make_range(Relocations.begin(), Relocations.end());
   }
 
   /// Iterate over all non-pending relocations for this section.
   iterator_range<RelocationSetType::const_iterator> relocations() const {
     return make_range(Relocations.begin(), Relocations.end());
   }
 
public:
   void clearRelocations();
 
   /// Add a new relocation at the given /p Offset.
   void addRelocation(uint64_t Offset, MCSymbol *Symbol, uint64_t Type,
                      uint64_t Addend, uint64_t Value = 0,
                      bool Pending = false) {
     assert(Offset < getSize() && "offset not within section bounds");
     if (!Pending) {
-      Relocations.emplace(Relocation{Offset, Symbol, Type, Addend, Value});
+      Relocations[Offset] = Relocation{Offset, Symbol, Type, Addend, Value};
     } else {
       PendingRelocations.emplace_back(
           Relocation{Offset, Symbol, Type, Addend, Value});
     }
   }
 
   /// Add a dynamic relocation at the given /p Offset.
   void addDynamicRelocation(uint64_t Offset, MCSymbol *Symbol, uint64_t Type,
                             uint64_t Addend, uint64_t Value = 0) {
     assert(Offset < getSize() && "offset not within section bounds");
-    DynamicRelocations.emplace(Relocation{Offset, Symbol, Type, Addend, Value});
+    DynamicRelocations[Offset] =
+        Relocation{Offset, Symbol, Type, Addend, Value};
   }
 
   /// Add relocation against the original contents of this section.
   void addPendingRelocation(const Relocation &Rel) {
     PendingRelocations.push_back(Rel);
   }
 
   /// Add patch to the input contents of this section.
   void addPatch(uint64_t Offset, const SmallVectorImpl<char> &Bytes) {
     Patches.emplace_back(BinaryPatch(Offset, Bytes));
   }
 
   /// Register patcher for this section.
   void registerPatcher(std::unique_ptr<BinaryPatcher> BPatcher) {
     Patcher = std::move(BPatcher);
   }
 
   /// Returns the patcher
   BinaryPatcher *getPatcher() { return Patcher.get(); }
 
   /// Lookup the relocation (if any) at the given /p Offset.
-  const Relocation *getRelocationAt(uint64_t Offset) const {
+  Relocation *getRelocationAt(uint64_t Offset) {
     auto Itr = Relocations.find(Offset);
-    return Itr != Relocations.end() ? &*Itr : nullptr;
+    return Itr != Relocations.end() ? &Itr->second : nullptr;
+  }
+
+  const Relocation *getRelocationAt(uint64_t Offset) const {
+    return const_cast<BinarySection *>(this)->getRelocationAt(Offset);
   }
 
   /// Lookup the relocation (if any) at the given /p Offset.
+  Relocation *getDynamicRelocationAt(uint64_t Offset) {
+    auto Itr = DynamicRelocations.find(Offset);
+    return Itr != DynamicRelocations.end() ? &Itr->second : nullptr;
+  }
+
   const Relocation *getDynamicRelocationAt(uint64_t Offset) const {
-    Relocation Key{Offset, 0, 0, 0, 0};
-    auto Itr = DynamicRelocations.find(Key);
-    return Itr != DynamicRelocations.end() ? &*Itr : nullptr;
+    return const_cast<BinarySection *>(this)->getDynamicRelocationAt(Offset);
   }
 
   uint64_t hash(const BinaryData &BD) const {
     std::map<const BinaryData *, uint64_t> Cache;
     return hash(BD, Cache);
   }
 
   ///

bolt/lib/Core/BinaryContext.cpp

while (Itr != End) {
     Itr = Next;
   }
   return Valid;
 }
 
 bool BinaryContext::validateHoles() const {
   bool Valid = true;
   for (BinarySection &Section : sections()) {
-    for (const Relocation &Rel : Section.relocations()) {
+    for (const auto &It : Section.relocations()) {
+      const Relocation &Rel = It.second;
       uint64_t RelAddr = Rel.Offset + Section.getAddress();
       const BinaryData *BD = getBinaryDataContainingAddress(RelAddr);
       if (!BD) {
         errs() << "BOLT-WARNING: no BinaryData found for relocation at address"
                << " 0x" << Twine::utohexstr(RelAddr) << " in "
                << Section.getName() << "\n";
         Valid = false;
       } else if (!BD->getAtomicRoot()) {

 }
 
 bool BinaryContext::removeRelocationAt(uint64_t Address) {
   ErrorOr<BinarySection &> Section = getSectionForAddress(Address);
   assert(Section && "cannot find section for address");
   return Section->removeRelocationAt(Address - Section->getAddress());
 }
 
-const Relocation *BinaryContext::getRelocationAt(uint64_t Address) {
+Relocation *BinaryContext::getRelocationAt(uint64_t Address) {
   ErrorOr<BinarySection &> Section = getSectionForAddress(Address);
   if (!Section)
     return nullptr;
 
   return Section->getRelocationAt(Address - Section->getAddress());
 }
 
-const Relocation *BinaryContext::getDynamicRelocationAt(uint64_t Address) {
+const Relocation *BinaryContext::getRelocationAt(uint64_t Address) const {
+  return const_cast<BinaryContext *>(this)->getRelocationAt(Address);
+}
+
+Relocation *BinaryContext::getDynamicRelocationAt(uint64_t Address) {
   ErrorOr<BinarySection &> Section = getSectionForAddress(Address);
   if (!Section)
     return nullptr;
 
   return Section->getDynamicRelocationAt(Address - Section->getAddress());
 }
 
+const Relocation *
+BinaryContext::getDynamicRelocationAt(uint64_t Address) const {
+  return const_cast<BinaryContext *>(this)->getDynamicRelocationAt(Address);
+}
+
 void BinaryContext::markAmbiguousRelocations(BinaryData &BD,
                                              const uint64_t Address) {
   auto setImmovable = [&](BinaryData &BD) {
     BinaryData *Root = BD.getAtomicRoot();
     LLVM_DEBUG(if (Root->isMoveable()) {
       dbgs() << "BOLT-DEBUG: setting " << *Root << " as immovable "
              << "due to ambiguous relocation referencing 0x"
              << Twine::utohexstr(Address) << '\n';

bolt/lib/Core/BinarySection.cpp

BinarySection::hash(const BinaryData &BD,
   auto Itr = Cache.find(&BD);
   if (Itr != Cache.end())
     return Itr->second;
 
   Cache[&BD] = 0;
 
   uint64_t Offset = BD.getAddress() - getAddress();
   const uint64_t EndOffset = BD.getEndAddress() - getAddress();
-  auto Begin = Relocations.lower_bound(Relocation{Offset, 0, 0, 0, 0});
-  auto End = Relocations.upper_bound(Relocation{EndOffset, 0, 0, 0, 0});
+  auto Begin = Relocations.lower_bound(Offset);
+  auto End = Relocations.upper_bound(EndOffset);
   const StringRef Contents = getContents();
 
   hash_code Hash =
       hash_combine(hash_value(BD.getSize()), hash_value(BD.getSectionName()));
 
   while (Begin != End) {
-    const Relocation &Rel = *Begin++;
-    Hash = hash_combine(
-        Hash, hash_value(Contents.substr(Offset, Begin->Offset - Offset)));
+    const Relocation &Rel = Begin->second;
+    Begin = std::next(Begin, 1);
+    Hash = hash_combine(Hash, hash_value(Contents.substr(
+                                  Offset, Begin->second.Offset - Offset)));
     if (BinaryData *RelBD = BC.getBinaryDataByName(Rel.Symbol->getName()))
       Hash = hash_combine(Hash, hash(*RelBD, Cache));
     Offset = Rel.Offset + Rel.getSize();
   }
 
   Hash = hash_combine(Hash,
                       hash_value(Contents.substr(Offset, EndOffset - Offset)));
 
void BinarySection::emitAsData(MCStreamer &Streamer, StringRef NewName) const {
   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: emitting "
                     << (isAllocatable() ? "" : "non-")
                     << "allocatable data section " << SectionName << '\n');
 
   if (!hasRelocations()) {
     Streamer.emitBytes(SectionContents);
   } else {
     uint64_t SectionOffset = 0;
-    for (const Relocation &Relocation : relocations()) {
+    for (auto It : relocations()) {
+      Relocation &Relocation = It.second;
       assert(Relocation.Offset < SectionContents.size() && "overflow detected");
       // Skip undefined symbols.
       if (BC.UndefinedSymbols.count(Relocation.Symbol))
         continue;
       if (SectionOffset < Relocation.Offset) {
         Streamer.emitBytes(SectionContents.substr(
             SectionOffset, Relocation.Offset - SectionOffset));
         SectionOffset = Relocation.Offset;
if (isAllocatable())
     OS << " (allocatable)";
 
   if (isVirtual())
     OS << " (virtual)";
 
   if (isTLS())
     OS << " (tls)";
 
-  if (opts::PrintRelocations)
-    for (const Relocation &R : relocations())
-      OS << "\n  " << R;
+  if (opts::PrintRelocations) {
+    for (const auto &It : relocations()) {
+      const Relocation &Rel = It.second;
+      OS << "\n  " << Rel;
+    }
+  }
 }
 
 BinarySection::RelocationSetType
 BinarySection::reorderRelocations(bool Inplace) const {
   assert(PendingRelocations.empty() &&
          "reodering pending relocations not supported");
   RelocationSetType NewRelocations;
-  for (const Relocation &Rel : relocations()) {
+  for (const auto &It : relocations()) {
+    const Relocation &Rel = It.second;
     uint64_t RelAddr = Rel.Offset + getAddress();
     BinaryData *BD = BC.getBinaryDataContainingAddress(RelAddr);
     BD = BD->getAtomicRoot();
     assert(BD);
 
     if ((!BD->isMoved() && !Inplace) || BD->isJumpTable())
       continue;
 
     Relocation NewRel(Rel);
-    uint64_t RelOffset = RelAddr - BD->getAddress();
-    NewRel.Offset = BD->getOutputOffset() + RelOffset;
+    const uint64_t RelOffset =
+        BD->getOutputOffset() + (RelAddr - BD->getAddress());
+    NewRel.Offset = RelOffset;
     assert(NewRel.Offset < getSize());
     LLVM_DEBUG(dbgs() << "BOLT-DEBUG: moving " << Rel << " -> " << NewRel
                       << "\n");
-    auto Res = NewRelocations.emplace(std::move(NewRel));
-    (void)Res;
-    assert(Res.second && "Can't overwrite existing relocation");
+    NewRelocations[RelOffset] = std::move(NewRel);
   }
   return NewRelocations;
 }
 
 void BinarySection::reorderContents(const std::vector<BinaryData *> &Order,
                                     bool Inplace) {
   IsReordered = true;
 

bolt/lib/Rewrite/RewriteInstance.cpp

RewriteInstance::patchELFAllocatableRelaSections(ELFObjectFile<ELFT> *File) {
 
   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()) {
-      for (const Relocation &Rel : Section.dynamicRelocations()) {
+      for (const auto &It : Section.dynamicRelocations()) {
+        const Relocation &Rel = It.second;
         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;
 
         if (Rel.Symbol) {
-          SymbolIdx = getOutputDynamicSymbolIndex(Symbol);
+          SymbolIdx = getOutputDynamicSymbolIndex(Rel.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());