summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
authorGravatar Evan Brown <ezb@google.com>2023-02-14 12:30:41 -0800
committerGravatar Copybara-Service <copybara-worker@google.com>2023-02-14 12:31:43 -0800
commit15957950d997cd9e09c61add5200361d5d1e7e11 (patch)
tree14b8da124467d5b9399819b12fda697b600b2cd2 /absl/container
parentae2f0378dc0e8c10e1e12b6d866568682bde684c (diff)
Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so that we can distinguish between end() iterators and default-constructed iterators in debug mode.
PiperOrigin-RevId: 509606271 Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/internal/raw_hash_set.h53
-rw-r--r--absl/container/internal/raw_hash_set_test.cc21
2 files changed, 41 insertions, 33 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index a2ada0cb..33e05736 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -816,6 +816,10 @@ class CommonFieldsGenerationInfoEnabled {
// the code more complicated, and there's a benefit in having the sizes of
// raw_hash_set in sanitizer mode and non-sanitizer mode a bit more different,
// which is that tests are less likely to rely on the size remaining the same.
+ // 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. Another option would be to have N
+ // empty generations and use a random one for empty hashtables.
GenerationType* generation_ = EmptyGeneration();
};
@@ -853,9 +857,6 @@ 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_;
};
@@ -1040,10 +1041,10 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last,
#define ABSL_INTERNAL_ASSERT_IS_FULL(ctrl, generation, generation_ptr, \
operation) \
do { \
- ABSL_HARDENING_ASSERT( \
- (ctrl != nullptr) && operation \
- " called on invalid iterator. The iterator might be an end() " \
- "iterator or may have been default constructed."); \
+ ABSL_HARDENING_ASSERT((ctrl != nullptr) && operation \
+ " called on end() iterator."); \
+ ABSL_HARDENING_ASSERT((ctrl != EmptyGroup()) && operation \
+ " called on default-constructed iterator."); \
if (SwisstableGenerationsEnabled() && generation != *generation_ptr) \
ABSL_INTERNAL_LOG(FATAL, operation \
" called on invalidated iterator. The table could " \
@@ -1058,9 +1059,10 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last,
inline void AssertIsValidForComparison(const ctrl_t* ctrl,
GenerationType generation,
const GenerationType* generation_ptr) {
- ABSL_HARDENING_ASSERT((ctrl == nullptr || IsFull(*ctrl)) &&
- "Invalid iterator comparison. The element might have "
- "been erased or the table might have rehashed.");
+ ABSL_HARDENING_ASSERT(
+ (ctrl == nullptr || ctrl == EmptyGroup() || IsFull(*ctrl)) &&
+ "Invalid iterator comparison. The element might have "
+ "been erased or the table might have rehashed.");
if (SwisstableGenerationsEnabled() && generation != *generation_ptr) {
ABSL_INTERNAL_LOG(FATAL,
"Invalid iterator comparison. The table could have "
@@ -1095,16 +1097,27 @@ inline void AssertSameContainer(const ctrl_t* ctrl_a, const ctrl_t* ctrl_b,
const void* const& slot_b,
const GenerationType* generation_ptr_a,
const GenerationType* generation_ptr_b) {
+#if defined(ABSL_SWISSTABLE_ENABLE_GENERATIONS) || \
+ ABSL_OPTION_HARDENED == 1 || !defined(NDEBUG)
+ const bool a_is_default = ctrl_a == EmptyGroup();
+ const bool b_is_default = ctrl_b == EmptyGroup();
+ if (a_is_default != b_is_default) {
+ ABSL_INTERNAL_LOG(
+ FATAL,
+ "Invalid iterator comparison. Comparing default-constructed iterator "
+ "with non-default-constructed iterator.");
+ }
+ if (a_is_default && b_is_default) return;
+#endif
+
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) {
+ const bool a_is_empty = generation_ptr_a == EmptyGeneration();
+ const bool b_is_empty = generation_ptr_b == EmptyGeneration();
+ if (a_is_empty != b_is_empty) {
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.");
+ "hashtable.");
}
const bool a_is_end = ctrl_a == nullptr;
const bool b_is_end = ctrl_b == nullptr;
@@ -1509,7 +1522,7 @@ class raw_hash_set {
}
// For end() iterators.
explicit iterator(const GenerationType* generation_ptr)
- : HashSetIteratorGenerationInfo(generation_ptr) {}
+ : HashSetIteratorGenerationInfo(generation_ptr), ctrl_(nullptr) {}
// Fixes up `ctrl_` to point to a full by advancing it and `slot_` until
// they reach one.
@@ -1524,9 +1537,9 @@ 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;
+ // We use EmptyGroup() for default-constructed iterators so that they can
+ // be distinguished from end iterators, which have nullptr ctrl_.
+ ctrl_t* ctrl_ = EmptyGroup();
// To avoid uninitialized member warnings, put slot_ in an anonymous union.
// The member is not initialized on singleton and end iterators.
union {
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index f7ec1456..4f2d006d 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2060,22 +2060,17 @@ TEST(TableDeathTest, InvalidIteratorAsserts) {
IntTable t;
// Extra simple "regexp" as regexp support is highly varied across platforms.
- EXPECT_DEATH_IF_SUPPORTED(
- t.erase(t.end()),
- "erase.* called on invalid iterator. The iterator might be an "
- "end.*iterator or may have been default constructed.");
+ EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()),
+ "erase.* called on end.. iterator.");
typename IntTable::iterator iter;
EXPECT_DEATH_IF_SUPPORTED(
- ++iter,
- "operator.* called on invalid iterator. The iterator might be an "
- "end.*iterator or may have been default constructed.");
+ ++iter, "operator.* called on default-constructed iterator.");
t.insert(0);
iter = t.begin();
t.erase(iter);
- EXPECT_DEATH_IF_SUPPORTED(
- ++iter,
- "operator.* called on invalid iterator. The element might have been "
- "erased or .*the table might have rehashed.");
+ EXPECT_DEATH_IF_SUPPORTED(++iter,
+ "operator.* called on invalid iterator. The "
+ "element might have been erased");
}
// Invalid iterator use can trigger heap-use-after-free in asan,
@@ -2363,8 +2358,8 @@ TEST(Iterator, InvalidComparisonDifferentTables) {
// 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...");
+ EXPECT_DEATH_IF_SUPPORTED(void(t1.end() == default_constructed_iter),
+ "Invalid iterator comparison.*default-constructed");
t1.insert(0);
EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == t2.end()),
"Invalid iterator comparison.*empty hashtable");