diff --git a/llvm/include/llvm/DWARFLinker/DWARFLinker.h b/llvm/include/llvm/DWARFLinker/DWARFLinker.h --- a/llvm/include/llvm/DWARFLinker/DWARFLinker.h +++ b/llvm/include/llvm/DWARFLinker/DWARFLinker.h @@ -61,26 +61,26 @@ virtual bool areRelocationsResolved() const = 0; /// Checks that there are valid relocations against a .debug_info - /// section. Reset current relocation pointer if neccessary. - virtual bool hasValidRelocs(bool ResetRelocsPtr = true) = 0; + /// section. + virtual bool hasValidRelocs() = 0; /// Checks that the specified DIE has a DW_AT_Location attribute - /// that references into a live code section. This function - /// must be called with DIE offsets in strictly ascending order. + /// that references into a live code section. + /// + /// \returns true and sets Info.InDebugMap if it is the case. virtual bool hasLiveMemoryLocation(const DWARFDie &DIE, CompileUnit::DIEInfo &Info) = 0; /// Checks that the specified DIE has a DW_AT_Low_pc attribute - /// that references into a live code section. This function - /// must be called with DIE offsets in strictly ascending order. + /// that references into a live code section. + /// + /// \returns true and sets Info.InDebugMap if it is the case. virtual bool hasLiveAddressRange(const DWARFDie &DIE, CompileUnit::DIEInfo &Info) = 0; /// Apply the valid relocations to the buffer \p Data, taking into /// account that Data is at \p BaseOffset in the debug_info section. /// - /// This function must be called with monotonic \p BaseOffset values. - /// /// \returns true whether any reloc has been applied. virtual bool applyValidRelocs(MutableArrayRef Data, uint64_t BaseOffset, bool IsLittleEndian) = 0; diff --git a/llvm/tools/dsymutil/DwarfLinkerForBinary.h b/llvm/tools/dsymutil/DwarfLinkerForBinary.h --- a/llvm/tools/dsymutil/DwarfLinkerForBinary.h +++ b/llvm/tools/dsymutil/DwarfLinkerForBinary.h @@ -78,14 +78,17 @@ /// This vector is sorted by relocation offset. std::vector ValidRelocs; - /// Index into ValidRelocs of the next relocation to consider. As we walk - /// the DIEs in acsending file offset and as ValidRelocs is sorted by file - /// offset, keeping this index up to date is all we have to do to have a - /// cheap lookup during the root DIE selection and during DIE cloning. - unsigned NextValidReloc = 0; - RangesTy AddressRanges; + /// Enumerate valid relocations in ValidRelocs starting + /// from StartPos. Call RelHandler for each found relocation. + /// Stop enumeration if EndPos is reached or RelHandler + /// returned false. Return true if any relocation was + /// enumerated. + bool + enumerateRelocations(uint64_t StartPos, uint64_t EndPos, + function_ref RelHandler); + public: AddressManager(DwarfLinkerForBinary &Linker, const object::ObjectFile &Obj, const DebugMapObject &DMO) @@ -121,11 +124,7 @@ virtual bool areRelocationsResolved() const override { return true; } - bool hasValidRelocs(bool ResetRelocsPtr = true) override { - if (ResetRelocsPtr) - NextValidReloc = 0; - return !ValidRelocs.empty(); - } + bool hasValidRelocs() override { return !ValidRelocs.empty(); } /// \defgroup FindValidRelocations Translate debug map into a list /// of relevant relocations @@ -159,7 +158,6 @@ void clear() override { AddressRanges.clear(); ValidRelocs.clear(); - NextValidReloc = 0; } }; diff --git a/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp b/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp --- a/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp +++ b/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp @@ -605,48 +605,56 @@ return false; } +/// Enumerate valid relocations in ValidRelocs starting +/// from StartPos. Call RelHandler for each found relocation. +/// Stop enumeration if EndPos is reached or RelHandler +/// returned false. Return true if any relocation was +/// enumerated. +bool DwarfLinkerForBinary::AddressManager::enumerateRelocations( + uint64_t StartPos, uint64_t EndPos, + function_ref RelHandler) { + auto CurReloc = + partition_point(ValidRelocs, [StartPos](const ValidReloc &Reloc) { + return Reloc.Offset < StartPos; + }); + + bool Res = false; + while (CurReloc != ValidRelocs.end() && CurReloc->Offset >= StartPos && + CurReloc->Offset < EndPos) { + if (!RelHandler(*CurReloc)) + return true; + CurReloc++; + Res = true; + } + + return Res; +} + /// Checks that there is a relocation against an actual debug /// map entry between \p StartOffset and \p NextOffset. /// -/// This function must be called with offsets in strictly ascending -/// order because it never looks back at relocations it already 'went past'. /// \returns true and sets Info.InDebugMap if it is the case. bool DwarfLinkerForBinary::AddressManager::hasValidRelocationAt( uint64_t StartOffset, uint64_t EndOffset, CompileUnit::DIEInfo &Info) { - assert(NextValidReloc == 0 || - StartOffset > ValidRelocs[NextValidReloc - 1].Offset); - if (NextValidReloc >= ValidRelocs.size()) - return false; - - uint64_t RelocOffset = ValidRelocs[NextValidReloc].Offset; - - // We might need to skip some relocs that we didn't consider. For - // example the high_pc of a discarded DIE might contain a reloc that - // is in the list because it actually corresponds to the start of a - // function that is in the debug map. - while (RelocOffset < StartOffset && NextValidReloc < ValidRelocs.size() - 1) - RelocOffset = ValidRelocs[++NextValidReloc].Offset; - - if (RelocOffset < StartOffset || RelocOffset >= EndOffset) - return false; - - const auto &ValidReloc = ValidRelocs[NextValidReloc++]; - const auto &Mapping = ValidReloc.Mapping->getValue(); - const uint64_t BinaryAddress = Mapping.BinaryAddress; - const uint64_t ObjectAddress = Mapping.ObjectAddress - ? uint64_t(*Mapping.ObjectAddress) - : std::numeric_limits::max(); - if (Linker.Options.Verbose) - outs() << "Found valid debug map entry: " << ValidReloc.Mapping->getKey() - << "\t" - << format("0x%016" PRIx64 " => 0x%016" PRIx64 "\n", ObjectAddress, - BinaryAddress); - - Info.AddrAdjust = BinaryAddress + ValidReloc.Addend; - if (Mapping.ObjectAddress) - Info.AddrAdjust -= ObjectAddress; - Info.InDebugMap = true; - return true; + return enumerateRelocations( + StartOffset, EndOffset, [&](const ValidReloc &Reloc) -> bool { + const auto &Mapping = Reloc.Mapping->getValue(); + const uint64_t BinaryAddress = Mapping.BinaryAddress; + const uint64_t ObjectAddress = + Mapping.ObjectAddress ? uint64_t(*Mapping.ObjectAddress) + : std::numeric_limits::max(); + if (Linker.Options.Verbose) + outs() << "Found valid debug map entry: " << Reloc.Mapping->getKey() + << "\t" + << format("0x%016" PRIx64 " => 0x%016" PRIx64 "\n", + ObjectAddress, BinaryAddress); + + Info.AddrAdjust = BinaryAddress + Reloc.Addend; + if (Mapping.ObjectAddress) + Info.AddrAdjust -= ObjectAddress; + Info.InDebugMap = true; + return false; + }); } /// Get the starting and ending (exclusive) offset for the @@ -714,38 +722,23 @@ bool DwarfLinkerForBinary::AddressManager::applyValidRelocs( MutableArrayRef Data, uint64_t BaseOffset, bool IsLittleEndian) { assert(areRelocationsResolved()); - assert((NextValidReloc == 0 || - BaseOffset > ValidRelocs[NextValidReloc - 1].Offset) && - "BaseOffset should only be increasing."); - if (NextValidReloc >= ValidRelocs.size()) - return false; - // Skip relocs that haven't been applied. - while (NextValidReloc < ValidRelocs.size() && - ValidRelocs[NextValidReloc].Offset < BaseOffset) - ++NextValidReloc; - - bool Applied = false; - uint64_t EndOffset = BaseOffset + Data.size(); - while (NextValidReloc < ValidRelocs.size() && - ValidRelocs[NextValidReloc].Offset >= BaseOffset && - ValidRelocs[NextValidReloc].Offset < EndOffset) { - const auto &ValidReloc = ValidRelocs[NextValidReloc++]; - assert(ValidReloc.Offset - BaseOffset < Data.size()); - assert(ValidReloc.Offset - BaseOffset + ValidReloc.Size <= Data.size()); - char Buf[8]; - uint64_t Value = ValidReloc.Mapping->getValue().BinaryAddress; - Value += ValidReloc.Addend; - for (unsigned I = 0; I != ValidReloc.Size; ++I) { - unsigned Index = IsLittleEndian ? I : (ValidReloc.Size - I - 1); - Buf[I] = uint8_t(Value >> (Index * 8)); - } - assert(ValidReloc.Size <= sizeof(Buf)); - memcpy(&Data[ValidReloc.Offset - BaseOffset], Buf, ValidReloc.Size); - Applied = true; - } - - return Applied; + return enumerateRelocations( + BaseOffset, BaseOffset + Data.size(), + [=](const ValidReloc &Reloc) -> bool { + assert(Reloc.Offset - BaseOffset < Data.size()); + assert(Reloc.Offset - BaseOffset + Reloc.Size <= Data.size()); + char Buf[8]; + uint64_t Value = Reloc.Mapping->getValue().BinaryAddress; + Value += Reloc.Addend; + for (unsigned I = 0; I != Reloc.Size; ++I) { + unsigned Index = IsLittleEndian ? I : (Reloc.Size - I - 1); + Buf[I] = uint8_t(Value >> (Index * 8)); + } + assert(Reloc.Size <= sizeof(Buf)); + memcpy(&Data[Reloc.Offset - BaseOffset], Buf, Reloc.Size); + return true; + }); } bool linkDwarf(raw_fd_ostream &OutFile, BinaryHolder &BinHolder,