diff --git a/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h b/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h --- a/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h +++ b/llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h @@ -112,6 +112,78 @@ bool dumpName(ScopedPrinter &W, SmallVectorImpl &AtomForms, uint64_t *DataOffset) const; + /// Reads an uint32_t from the accelerator table at Offset, which is + /// incremented by the number of bytes read. + std::optional readU32FromAccel(uint64_t &Offset, + bool UseRelocation = false) const; + + /// Reads a StringRef from the string table at Offset. + std::optional + readStringFromStrSection(uint64_t StringSectionOffset) const; + + /// Return the offset into the section where the Buckets begin. + uint64_t getBucketBase() const { return sizeof(Hdr) + Hdr.HeaderDataLength; } + + /// Return the offset into the section where the I-th bucket is. + uint64_t getIthBucketBase(uint32_t I) const { + return getBucketBase() + I * 4; + } + + /// Return the offset into the section where the hash list begins. + uint64_t getHashBase() const { return getBucketBase() + getNumBuckets() * 4; } + + /// Return the offset into the section where the I-th hash is. + uint64_t getIthHashBase(uint32_t I) const { return getHashBase() + I * 4; } + + /// Return the offset into the section where the offset list begins. + uint64_t getOffsetBase() const { return getHashBase() + getNumHashes() * 4; } + + /// Return the offset into the section where the I-th offset is. + uint64_t getIthOffsetBase(uint32_t I) const { + return getOffsetBase() + I * 4; + } + + /// Returns the index of the bucket where a hypothetical Hash would be. + uint32_t hashToBucketIdx(uint32_t Hash) const { + return Hash % getNumBuckets(); + } + + /// Returns true iff a hypothetical Hash would be assigned to the BucketIdx-th + /// bucket. + bool wouldHashBeInBucket(uint32_t Hash, uint32_t BucketIdx) const { + return hashToBucketIdx(Hash) == BucketIdx; + } + + /// Reads the contents of the I-th bucket, that is, the index in the hash list + /// where the hashes corresponding to this bucket begin. + std::optional readIthBucket(uint32_t I) const { + uint64_t Offset = getIthBucketBase(I); + return readU32FromAccel(Offset); + } + + /// Reads the I-th hash in the hash list. + std::optional readIthHash(uint32_t I) const { + uint64_t Offset = getIthHashBase(I); + return readU32FromAccel(Offset); + } + + /// Reads the I-th offset in the offset list. + std::optional readIthOffset(uint32_t I) const { + uint64_t Offset = getIthOffsetBase(I); + return readU32FromAccel(Offset); + } + + /// Reads a string offset from the accelerator table at Offset, which is + /// incremented by the number of bytes read. + std::optional readStringOffsetAt(uint64_t &Offset) const { + return readU32FromAccel(Offset, /*UseRelocation*/ true); + } + + /// Scans through all Hashes in the BucketIdx-th bucket, attempting to find + /// HashToFind. If it is found, its index in the list of hashes is returned. + std::optional idxOfHashInBucket(uint32_t HashToFind, + uint32_t BucketIdx) const; + public: /// Apple-specific implementation of an Accelerator Entry. class Entry final : public DWARFAcceleratorTable::Entry { @@ -183,10 +255,10 @@ : DWARFAcceleratorTable(AccelSection, StringSection) {} Error extract() override; - uint32_t getNumBuckets(); - uint32_t getNumHashes(); - uint32_t getSizeHdr(); - uint32_t getHeaderDataLength(); + uint32_t getNumBuckets() const; + uint32_t getNumHashes() const; + uint32_t getSizeHdr() const; + uint32_t getHeaderDataLength() const; /// Return the Atom description, which can be used to interpret the raw values /// of the Accelerator Entries in this table. diff --git a/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp b/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp --- a/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp +++ b/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp @@ -57,10 +57,7 @@ // Check that we can read all the hashes and offsets from the // section (see SourceLevelDebugging.rst for the structure of the index). - // We need to substract one because we're checking for an *offset* which is - // equal to the size for an empty table and hence pointer after the section. - if (!AccelSection.isValidOffset(sizeof(Hdr) + Hdr.HeaderDataLength + - Hdr.BucketCount * 4 + Hdr.HashCount * 8 - 1)) + if (!AccelSection.isValidOffset(getIthBucketBase(Hdr.BucketCount - 1))) return createStringError( errc::illegal_byte_sequence, "Section too small: cannot read buckets and hashes."); @@ -78,10 +75,12 @@ return Error::success(); } -uint32_t AppleAcceleratorTable::getNumBuckets() { return Hdr.BucketCount; } -uint32_t AppleAcceleratorTable::getNumHashes() { return Hdr.HashCount; } -uint32_t AppleAcceleratorTable::getSizeHdr() { return sizeof(Hdr); } -uint32_t AppleAcceleratorTable::getHeaderDataLength() { +uint32_t AppleAcceleratorTable::getNumBuckets() const { + return Hdr.BucketCount; +} +uint32_t AppleAcceleratorTable::getNumHashes() const { return Hdr.HashCount; } +uint32_t AppleAcceleratorTable::getSizeHdr() const { return sizeof(Hdr); } +uint32_t AppleAcceleratorTable::getHeaderDataLength() const { return Hdr.HeaderDataLength; } @@ -327,39 +326,82 @@ iterator_range AppleAcceleratorTable::equal_range(StringRef Key) const { + const auto EmptyRange = make_range(ValueIterator(), ValueIterator()); if (!IsValid) - return make_range(ValueIterator(), ValueIterator()); + return EmptyRange; // Find the bucket. - unsigned HashValue = djbHash(Key); - unsigned Bucket = HashValue % Hdr.BucketCount; - uint64_t BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength; - uint64_t HashesBase = BucketBase + Hdr.BucketCount * 4; - uint64_t OffsetsBase = HashesBase + Hdr.HashCount * 4; - - uint64_t BucketOffset = BucketBase + Bucket * 4; - unsigned Index = AccelSection.getU32(&BucketOffset); - - // Search through all hashes in the bucket. - for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) { - uint64_t HashOffset = HashesBase + HashIdx * 4; - uint64_t OffsetsOffset = OffsetsBase + HashIdx * 4; - uint32_t Hash = AccelSection.getU32(&HashOffset); - - if (Hash % Hdr.BucketCount != Bucket) - // We are already in the next bucket. - break; + uint32_t SearchHash = djbHash(Key); + uint32_t BucketIdx = hashToBucketIdx(SearchHash); + std::optional HashIdx = idxOfHashInBucket(SearchHash, BucketIdx); + if (!HashIdx) + return EmptyRange; + + std::optional MaybeDataOffset = readIthOffset(*HashIdx); + if (!MaybeDataOffset) + return EmptyRange; + + uint64_t DataOffset = *MaybeDataOffset; + if (DataOffset >= AccelSection.size()) + return EmptyRange; + + std::optional StrOffset = readStringOffsetAt(DataOffset); + + // Invalid input or no more strings in this hash. + if (!StrOffset || *StrOffset == 0) + return EmptyRange; + + std::optional MaybeStr = readStringFromStrSection(*StrOffset); + if (!MaybeStr) + return EmptyRange; + if (Key == *MaybeStr) + return make_range({*this, DataOffset}, ValueIterator()); + + // FIXME: this shouldn't return, we haven't checked all the colliding strings + // in the bucket! + return EmptyRange; +} + +std::optional +AppleAcceleratorTable::idxOfHashInBucket(uint32_t HashToFind, + uint32_t BucketIdx) const { + std::optional HashStartIdx = readIthBucket(BucketIdx); + if (!HashStartIdx) + return std::nullopt; - uint64_t DataOffset = AccelSection.getU32(&OffsetsOffset); - uint64_t StringOffset = AccelSection.getRelocatedValue(4, &DataOffset); - if (!StringOffset) + for (uint32_t HashIdx = *HashStartIdx; HashIdx < getNumHashes(); HashIdx++) { + std::optional MaybeHash = readIthHash(HashIdx); + if (!MaybeHash || !wouldHashBeInBucket(*MaybeHash, BucketIdx)) break; + if (*MaybeHash == HashToFind) + return HashIdx; + } + return std::nullopt; +} - // Finally, compare the key. - if (Key == StringSection.getCStr(&StringOffset)) - return make_range({*this, DataOffset}, ValueIterator()); +std::optional AppleAcceleratorTable::readStringFromStrSection( + uint64_t StringSectionOffset) const { + Error E = Error::success(); + StringRef Str = StringSection.getCStrRef(&StringSectionOffset, &E); + if (E) { + consumeError(std::move(E)); + return std::nullopt; + } + return Str; +} + +std::optional +AppleAcceleratorTable::readU32FromAccel(uint64_t &Offset, + bool UseRelocation) const { + Error E = Error::success(); + uint32_t Data = UseRelocation + ? AccelSection.getRelocatedValue(4, &Offset, nullptr, &E) + : AccelSection.getU32(&Offset, &E); + if (E) { + consumeError(std::move(E)); + return std::nullopt; } - return make_range(ValueIterator(), ValueIterator()); + return Data; } void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {