Merge "Remove sequential search from DwarfEhFrameWithHdr."
diff --git a/libunwindstack/DwarfEhFrameWithHdr.cpp b/libunwindstack/DwarfEhFrameWithHdr.cpp
index 668527a..802beca 100644
--- a/libunwindstack/DwarfEhFrameWithHdr.cpp
+++ b/libunwindstack/DwarfEhFrameWithHdr.cpp
@@ -61,6 +61,14 @@
table_encoding_ = data[3];
table_entry_size_ = memory_.template GetEncodedSize<AddressType>(table_encoding_);
+ // If we can't perform a binary search on the entries, it's not worth
+ // using this object. The calling code will fall back to the DwarfEhFrame
+ // object in this case.
+ if (table_entry_size_ == 0) {
+ last_error_.code = DWARF_ERROR_ILLEGAL_VALUE;
+ return false;
+ }
+
memory_.set_pc_offset(memory_.cur_offset());
if (!memory_.template ReadEncodedValue<AddressType>(ptr_encoding_, &ptr_offset_)) {
last_error_.code = DWARF_ERROR_MEMORY_INVALID;
@@ -137,13 +145,13 @@
}
template <typename AddressType>
-bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetBinary(uint64_t pc, uint64_t* fde_offset,
- uint64_t total_entries) {
- CHECK(fde_count_ > 0);
- CHECK(total_entries <= fde_count_);
+bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetFromPc(uint64_t pc, uint64_t* fde_offset) {
+ if (fde_count_ == 0) {
+ return false;
+ }
size_t first = 0;
- size_t last = total_entries;
+ size_t last = fde_count_;
while (first < last) {
size_t current = (first + last) / 2;
const FdeInfo* info = GetFdeInfoFromIndex(current);
@@ -172,87 +180,6 @@
}
template <typename AddressType>
-bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetSequential(uint64_t pc, uint64_t* fde_offset) {
- CHECK(fde_count_ != 0);
- last_error_.code = DWARF_ERROR_NONE;
- last_error_.address = 0;
-
- // We can do a binary search if the pc is in the range of the elements
- // that have already been cached.
- if (!fde_info_.empty()) {
- const FdeInfo* info = &fde_info_[fde_info_.size() - 1];
- if (pc >= info->pc) {
- *fde_offset = info->offset;
- return true;
- }
- if (pc < info->pc) {
- return GetFdeOffsetBinary(pc, fde_offset, fde_info_.size());
- }
- }
-
- if (cur_entries_offset_ == 0) {
- // All entries read, or error encountered.
- return false;
- }
-
- memory_.set_data_offset(entries_data_offset_);
- memory_.set_cur_offset(cur_entries_offset_);
- memory_.set_pc_offset(0);
- cur_entries_offset_ = 0;
-
- FdeInfo* prev_info = nullptr;
- for (size_t current = fde_info_.size();
- current < fde_count_ && memory_.cur_offset() < entries_end_; current++) {
- FdeInfo* info = &fde_info_[current];
- uint64_t value;
- if (!memory_.template ReadEncodedValue<AddressType>(table_encoding_, &value) ||
- !memory_.template ReadEncodedValue<AddressType>(table_encoding_, &info->offset)) {
- fde_info_.erase(current);
- last_error_.code = DWARF_ERROR_MEMORY_INVALID;
- last_error_.address = memory_.cur_offset();
- return false;
- }
-
- // Relative encodings require adding in the load bias.
- if (IsEncodingRelative(table_encoding_)) {
- value += load_bias_;
- }
- info->pc = value;
-
- if (pc < info->pc) {
- if (prev_info == nullptr) {
- return false;
- }
- cur_entries_offset_ = memory_.cur_offset();
- *fde_offset = prev_info->offset;
- return true;
- }
- prev_info = info;
- }
-
- if (fde_count_ == fde_info_.size() && pc >= prev_info->pc) {
- *fde_offset = prev_info->offset;
- return true;
- }
- return false;
-}
-
-template <typename AddressType>
-bool DwarfEhFrameWithHdr<AddressType>::GetFdeOffsetFromPc(uint64_t pc, uint64_t* fde_offset) {
- if (fde_count_ == 0) {
- return false;
- }
-
- if (table_entry_size_ > 0) {
- // Do a binary search since the size of each table entry is fixed.
- return GetFdeOffsetBinary(pc, fde_offset, fde_count_);
- } else {
- // Do a sequential search since each table entry size is variable.
- return GetFdeOffsetSequential(pc, fde_offset);
- }
-}
-
-template <typename AddressType>
void DwarfEhFrameWithHdr<AddressType>::GetFdes(std::vector<const DwarfFde*>* fdes) {
for (size_t i = 0; i < fde_count_; i++) {
const FdeInfo* info = GetFdeInfoFromIndex(i);
diff --git a/libunwindstack/DwarfEhFrameWithHdr.h b/libunwindstack/DwarfEhFrameWithHdr.h
index e3e9ca8..0e5eef7 100644
--- a/libunwindstack/DwarfEhFrameWithHdr.h
+++ b/libunwindstack/DwarfEhFrameWithHdr.h
@@ -69,10 +69,6 @@
const FdeInfo* GetFdeInfoFromIndex(size_t index);
- bool GetFdeOffsetSequential(uint64_t pc, uint64_t* fde_offset);
-
- bool GetFdeOffsetBinary(uint64_t pc, uint64_t* fde_offset, uint64_t total_entries);
-
void GetFdes(std::vector<const DwarfFde*>* fdes) override;
protected:
diff --git a/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp b/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp
index 910ae36..be9e721 100644
--- a/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp
+++ b/libunwindstack/tests/DwarfEhFrameWithHdrTest.cpp
@@ -95,6 +95,13 @@
EXPECT_EQ(0x1000U, this->eh_frame_->TestGetEntriesDataOffset());
EXPECT_EQ(0x100aU, this->eh_frame_->TestGetCurEntriesOffset());
+ // Verify a zero table entry size fails to init.
+ this->memory_.SetData8(0x1003, 0x1);
+ ASSERT_FALSE(this->eh_frame_->Init(0x1000, 0x100, 0));
+ ASSERT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->eh_frame_->LastErrorCode());
+ // Reset the value back to the original.
+ this->memory_.SetData8(0x1003, DW_EH_PE_sdata4);
+
// Verify a zero fde count fails to init.
this->memory_.SetData32(0x1006, 0);
ASSERT_FALSE(this->eh_frame_->Init(0x1000, 0x100, 0));
@@ -276,9 +283,8 @@
EXPECT_EQ(0x500U, info->offset);
}
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetBinary_verify) {
+TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_verify) {
this->eh_frame_->TestSetTableEntrySize(0x10);
- this->eh_frame_->TestSetFdeCount(10);
typename DwarfEhFrameWithHdr<TypeParam>::FdeInfo info;
for (size_t i = 0; i < 10; i++) {
@@ -288,105 +294,42 @@
}
uint64_t fde_offset;
- EXPECT_FALSE(this->eh_frame_->GetFdeOffsetBinary(0x100, &fde_offset, 10));
+ this->eh_frame_->TestSetFdeCount(10);
+ EXPECT_FALSE(this->eh_frame_->GetFdeOffsetFromPc(0x100, &fde_offset));
// Not an error, just not found.
ASSERT_EQ(DWARF_ERROR_NONE, this->eh_frame_->LastErrorCode());
// Even number of elements.
for (size_t i = 0; i < 10; i++) {
+ SCOPED_TRACE(testing::Message() << "Failed at index " << i);
TypeParam pc = 0x1000 * (i + 1);
- EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc, &fde_offset, 10)) << "Failed at index " << i;
- EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
- EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 1, &fde_offset, 10))
- << "Failed at index " << i;
- EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
- EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 0xfff, &fde_offset, 10))
- << "Failed at index " << i;
- EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
+ EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc, &fde_offset));
+ EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+ EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 1, &fde_offset));
+ EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+ EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 0xfff, &fde_offset));
+ EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
}
+
// Odd number of elements.
+ this->eh_frame_->TestSetFdeCount(9);
for (size_t i = 0; i < 9; i++) {
+ SCOPED_TRACE(testing::Message() << "Failed at index " << i);
TypeParam pc = 0x1000 * (i + 1);
- EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc, &fde_offset, 9)) << "Failed at index " << i;
- EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
- EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 1, &fde_offset, 9))
- << "Failed at index " << i;
- EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
- EXPECT_TRUE(this->eh_frame_->GetFdeOffsetBinary(pc + 0xfff, &fde_offset, 9))
- << "Failed at index " << i;
- EXPECT_EQ(0x5000 + i * 0x20, fde_offset) << "Failed at index " << i;
+ EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc, &fde_offset));
+ EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+ EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 1, &fde_offset));
+ EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
+ EXPECT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(pc + 0xfff, &fde_offset));
+ EXPECT_EQ(0x5000 + i * 0x20, fde_offset);
}
}
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetBinary_index_fail) {
+TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_index_fail) {
this->eh_frame_->TestSetTableEntrySize(0x10);
this->eh_frame_->TestSetFdeCount(10);
uint64_t fde_offset;
- EXPECT_FALSE(this->eh_frame_->GetFdeOffsetBinary(0x1000, &fde_offset, 10));
-}
-
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetSequential) {
- this->eh_frame_->TestSetFdeCount(10);
- this->eh_frame_->TestSetEntriesDataOffset(0x100);
- this->eh_frame_->TestSetEntriesEnd(0x2000);
- this->eh_frame_->TestSetTableEncoding(DW_EH_PE_udata4);
-
- this->memory_.SetData32(0x1040, 0x340);
- this->memory_.SetData32(0x1044, 0x500);
-
- this->memory_.SetData32(0x1048, 0x440);
- this->memory_.SetData32(0x104c, 0x600);
-
- // Verify that if entries is zero, that it fails.
- uint64_t fde_offset;
- ASSERT_FALSE(this->eh_frame_->GetFdeOffsetSequential(0x344, &fde_offset));
- this->eh_frame_->TestSetCurEntriesOffset(0x1040);
-
- ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x344, &fde_offset));
- EXPECT_EQ(0x500U, fde_offset);
-
- ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x444, &fde_offset));
- EXPECT_EQ(0x600U, fde_offset);
-
- // Expect that the data is cached so no more memory reads will occur.
- this->memory_.Clear();
- ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x444, &fde_offset));
- EXPECT_EQ(0x600U, fde_offset);
-}
-
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetSequential_last_element) {
- this->eh_frame_->TestSetFdeCount(2);
- this->eh_frame_->TestSetEntriesDataOffset(0x100);
- this->eh_frame_->TestSetEntriesEnd(0x2000);
- this->eh_frame_->TestSetTableEncoding(DW_EH_PE_udata4);
- this->eh_frame_->TestSetCurEntriesOffset(0x1040);
-
- this->memory_.SetData32(0x1040, 0x340);
- this->memory_.SetData32(0x1044, 0x500);
-
- this->memory_.SetData32(0x1048, 0x440);
- this->memory_.SetData32(0x104c, 0x600);
-
- uint64_t fde_offset;
- ASSERT_TRUE(this->eh_frame_->GetFdeOffsetSequential(0x540, &fde_offset));
- EXPECT_EQ(0x600U, fde_offset);
-}
-
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetSequential_end_check) {
- this->eh_frame_->TestSetFdeCount(2);
- this->eh_frame_->TestSetEntriesDataOffset(0x100);
- this->eh_frame_->TestSetEntriesEnd(0x1048);
- this->eh_frame_->TestSetTableEncoding(DW_EH_PE_udata4);
-
- this->memory_.SetData32(0x1040, 0x340);
- this->memory_.SetData32(0x1044, 0x500);
-
- this->memory_.SetData32(0x1048, 0x440);
- this->memory_.SetData32(0x104c, 0x600);
-
- uint64_t fde_offset;
- ASSERT_FALSE(this->eh_frame_->GetFdeOffsetSequential(0x540, &fde_offset));
- ASSERT_EQ(DWARF_ERROR_NONE, this->eh_frame_->LastErrorCode());
+ EXPECT_FALSE(this->eh_frame_->GetFdeOffsetFromPc(0x1000, &fde_offset));
}
TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_fail_fde_count) {
@@ -397,7 +340,7 @@
ASSERT_EQ(DWARF_ERROR_NONE, this->eh_frame_->LastErrorCode());
}
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_binary_search) {
+TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_search) {
this->eh_frame_->TestSetTableEntrySize(16);
this->eh_frame_->TestSetFdeCount(10);
@@ -417,26 +360,6 @@
EXPECT_EQ(0x10700U, fde_offset);
}
-TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetFdeOffsetFromPc_sequential_search) {
- this->eh_frame_->TestSetFdeCount(10);
- this->eh_frame_->TestSetTableEntrySize(0);
-
- typename DwarfEhFrameWithHdr<TypeParam>::FdeInfo info;
- info.pc = 0x50;
- info.offset = 0x10000;
- this->eh_frame_->TestSetFdeInfo(0, info);
- info.pc = 0x150;
- info.offset = 0x10100;
- this->eh_frame_->TestSetFdeInfo(1, info);
- info.pc = 0x250;
- info.offset = 0x10200;
- this->eh_frame_->TestSetFdeInfo(2, info);
-
- uint64_t fde_offset;
- ASSERT_TRUE(this->eh_frame_->GetFdeOffsetFromPc(0x200, &fde_offset));
- EXPECT_EQ(0x10100U, fde_offset);
-}
-
TYPED_TEST_P(DwarfEhFrameWithHdrTest, GetCieFde32) {
// CIE 32 information.
this->memory_.SetData32(0xf000, 0x100);
@@ -526,10 +449,8 @@
REGISTER_TYPED_TEST_CASE_P(DwarfEhFrameWithHdrTest, Init, Init_non_zero_load_bias, GetFdes,
GetFdeInfoFromIndex_expect_cache_fail, GetFdeInfoFromIndex_read_pcrel,
GetFdeInfoFromIndex_read_datarel, GetFdeInfoFromIndex_cached,
- GetFdeOffsetBinary_verify, GetFdeOffsetBinary_index_fail,
- GetFdeOffsetSequential, GetFdeOffsetSequential_last_element,
- GetFdeOffsetSequential_end_check, GetFdeOffsetFromPc_fail_fde_count,
- GetFdeOffsetFromPc_binary_search, GetFdeOffsetFromPc_sequential_search,
+ GetFdeOffsetFromPc_verify, GetFdeOffsetFromPc_index_fail,
+ GetFdeOffsetFromPc_fail_fde_count, GetFdeOffsetFromPc_search,
GetCieFde32, GetCieFde64, GetFdeFromPc_fde_not_found);
typedef ::testing::Types<uint32_t, uint64_t> DwarfEhFrameWithHdrTestTypes;