summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
authorGravatar Evan Brown <ezb@google.com>2023-02-09 14:12:52 -0800
committerGravatar Copybara-Service <copybara-worker@google.com>2023-02-09 14:13:42 -0800
commit823b837839db2a754af37095c72f97ce6733d32b (patch)
tree1cd960f3d5e28218df5345ae9bac1bd4ba437fe3 /absl/container
parentdcaed1a05a813e95b65219e0d1f6a2a684e13028 (diff)
In sanitizer mode, detect when end iterators from different swisstables are compared.
We change AssertSameContainer to be after AssertIsValidForComparison calls so that we can have more specific failure messages. PiperOrigin-RevId: 508472485 Change-Id: Iff2f7512086948a4aca7fd403596e8d4fde53b2a
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/internal/raw_hash_set.h37
-rw-r--r--absl/container/internal/raw_hash_set_test.cc62
2 files changed, 77 insertions, 22 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 65dc66c2..a2ada0cb 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -853,6 +853,9 @@ class HashSetIteratorGenerationInfoEnabled {
void set_generation_ptr(const GenerationType* ptr) { generation_ptr_ = ptr; }
private:
+ // TODO(b/254649633): use a different static generation for default
+ // constructed iterators so that we can detect when default constructed
+ // iterators are compared to iterators from empty tables.
const GenerationType* generation_ptr_ = EmptyGeneration();
GenerationType generation_ = *generation_ptr_;
};
@@ -1087,12 +1090,33 @@ inline bool AreItersFromSameContainer(const ctrl_t* ctrl_a,
// Asserts that two iterators come from the same container.
// Note: we take slots by reference so that it's not UB if they're uninitialized
// as long as we don't read them (when ctrl is null).
-// TODO(b/254649633): when generations are enabled, we can detect more cases of
-// different containers by comparing the pointers to the generations - this
-// can cover cases of end iterators that we would otherwise miss.
inline void AssertSameContainer(const ctrl_t* ctrl_a, const ctrl_t* ctrl_b,
const void* const& slot_a,
- const void* const& slot_b) {
+ const void* const& slot_b,
+ const GenerationType* generation_ptr_a,
+ const GenerationType* generation_ptr_b) {
+ if (SwisstableGenerationsEnabled() && generation_ptr_a != generation_ptr_b) {
+ // TODO(b/254649633): use a different static generation for default
+ // constructed iterators so that we can split the empty/default cases.
+ const bool a_is_empty_or_default = generation_ptr_a == EmptyGeneration();
+ const bool b_is_empty_or_default = generation_ptr_b == EmptyGeneration();
+ if (a_is_empty_or_default != b_is_empty_or_default) {
+ ABSL_INTERNAL_LOG(FATAL,
+ "Invalid iterator comparison. Comparing iterator from "
+ "a non-empty hashtable with an iterator from an empty "
+ "hashtable or a default-constructed iterator.");
+ }
+ const bool a_is_end = ctrl_a == nullptr;
+ const bool b_is_end = ctrl_b == nullptr;
+ if (a_is_end || b_is_end) {
+ ABSL_INTERNAL_LOG(FATAL,
+ "Invalid iterator comparison. Comparing iterator with "
+ "an end() iterator from a different hashtable.");
+ }
+ ABSL_INTERNAL_LOG(FATAL,
+ "Invalid iterator comparison. Comparing non-end() "
+ "iterators from different hashtables.");
+ }
ABSL_HARDENING_ASSERT(
AreItersFromSameContainer(ctrl_a, ctrl_b, slot_a, slot_b) &&
"Invalid iterator comparison. The iterators may be from different "
@@ -1463,9 +1487,10 @@ class raw_hash_set {
}
friend bool operator==(const iterator& a, const iterator& b) {
- AssertSameContainer(a.ctrl_, b.ctrl_, a.slot_, b.slot_);
AssertIsValidForComparison(a.ctrl_, a.generation(), a.generation_ptr());
AssertIsValidForComparison(b.ctrl_, b.generation(), b.generation_ptr());
+ AssertSameContainer(a.ctrl_, b.ctrl_, a.slot_, b.slot_,
+ a.generation_ptr(), b.generation_ptr());
return a.ctrl_ == b.ctrl_;
}
friend bool operator!=(const iterator& a, const iterator& b) {
@@ -1499,6 +1524,8 @@ class raw_hash_set {
if (ABSL_PREDICT_FALSE(*ctrl_ == ctrl_t::kSentinel)) ctrl_ = nullptr;
}
+ // TODO(b/254649633): use non-null control for default-constructed iterators
+ // so that we can distinguish between them and end iterators in debug mode.
ctrl_t* ctrl_ = nullptr;
// To avoid uninitialized member warnings, put slot_ in an anonymous union.
// The member is not initialized on singleton and end iterators.
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index e33fda20..f7ec1456 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2078,6 +2078,19 @@ TEST(TableDeathTest, InvalidIteratorAsserts) {
"erased or .*the table might have rehashed.");
}
+// Invalid iterator use can trigger heap-use-after-free in asan,
+// use-of-uninitialized-value in msan, or invalidated iterator assertions.
+constexpr const char* kInvalidIteratorDeathMessage =
+ "heap-use-after-free|use-of-uninitialized-value|invalidated "
+ "iterator|Invalid iterator";
+
+// MSVC doesn't support | in regex.
+#if defined(_MSC_VER)
+constexpr bool kMsvc = true;
+#else
+constexpr bool kMsvc = false;
+#endif
+
TEST(TableDeathTest, IteratorInvalidAssertsEqualityOperator) {
if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
@@ -2105,15 +2118,18 @@ TEST(TableDeathTest, IteratorInvalidAssertsEqualityOperator) {
iter1 = t1.begin();
iter2 = t2.begin();
const char* const kContainerDiffDeathMessage =
- "Invalid iterator comparison. The iterators may be from different "
- ".*containers or the container might have rehashed.";
+ SwisstableGenerationsEnabled()
+ ? "Invalid iterator comparison.*non-end"
+ : "Invalid iterator comparison. The iterators may be from different "
+ ".*containers or the container might have rehashed.";
EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kContainerDiffDeathMessage);
EXPECT_DEATH_IF_SUPPORTED(void(iter2 == iter1), kContainerDiffDeathMessage);
for (int i = 0; i < 10; ++i) t1.insert(i);
// There should have been a rehash in t1.
+ if (kMsvc) return; // MSVC doesn't support | in regex.
EXPECT_DEATH_IF_SUPPORTED(void(iter1 == t1.begin()),
- kContainerDiffDeathMessage);
+ kInvalidIteratorDeathMessage);
}
#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
@@ -2258,21 +2274,9 @@ TEST(Table, AlignOne) {
}
}
-// Invalid iterator use can trigger heap-use-after-free in asan,
-// use-of-uninitialized-value in msan, or invalidated iterator assertions.
-constexpr const char* kInvalidIteratorDeathMessage =
- "heap-use-after-free|use-of-uninitialized-value|invalidated "
- "iterator|Invalid iterator";
-
-#if defined(__clang__) && defined(_MSC_VER)
-constexpr bool kLexan = true;
-#else
-constexpr bool kLexan = false;
-#endif
-
TEST(Iterator, InvalidUseCrashesWithSanitizers) {
if (!SwisstableGenerationsEnabled()) GTEST_SKIP() << "Generations disabled.";
- if (kLexan) GTEST_SKIP() << "Lexan doesn't support | in regexp.";
+ if (kMsvc) GTEST_SKIP() << "MSVC doesn't support | in regexp.";
IntTable t;
// Start with 1 element so that `it` is never an end iterator.
@@ -2288,7 +2292,7 @@ TEST(Iterator, InvalidUseCrashesWithSanitizers) {
TEST(Iterator, InvalidUseWithReserveCrashesWithSanitizers) {
if (!SwisstableGenerationsEnabled()) GTEST_SKIP() << "Generations disabled.";
- if (kLexan) GTEST_SKIP() << "Lexan doesn't support | in regexp.";
+ if (kMsvc) GTEST_SKIP() << "MSVC doesn't support | in regexp.";
IntTable t;
t.reserve(10);
@@ -2349,6 +2353,30 @@ TEST(Table, InvalidReferenceUseCrashesWithSanitizers) {
}
}
+TEST(Iterator, InvalidComparisonDifferentTables) {
+ if (!SwisstableGenerationsEnabled()) GTEST_SKIP() << "Generations disabled.";
+
+ IntTable t1, t2;
+ IntTable::iterator default_constructed_iter;
+ // TODO(b/254649633): Currently, we can't detect when end iterators from
+ // different empty tables are compared. If we allocate generations separately
+ // from control bytes, then we could do so.
+ // EXPECT_DEATH_IF_SUPPORTED(void(t1.end() == t2.end()),
+ // "Invalid iterator comparison.*empty hashtable");
+ // EXPECT_DEATH_IF_SUPPORTED(void(t1.end() == default_constructed_iter),
+ // "Invalid iterator comparison.*default-const...");
+ t1.insert(0);
+ EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == t2.end()),
+ "Invalid iterator comparison.*empty hashtable");
+ EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == default_constructed_iter),
+ "Invalid iterator comparison.*default-constructed");
+ t2.insert(0);
+ EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == t2.end()),
+ "Invalid iterator comparison.*end.. iterator");
+ EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == t2.begin()),
+ "Invalid iterator comparison.*non-end");
+}
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END