From 823b837839db2a754af37095c72f97ce6733d32b Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Thu, 9 Feb 2023 14:12:52 -0800 Subject: 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 --- absl/container/internal/raw_hash_set.h | 37 ++++++++++++++--- absl/container/internal/raw_hash_set_test.cc | 62 ++++++++++++++++++++-------- 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 -- cgit v1.2.3