[DenseMap] Invalidate iterators on erase#199369
Conversation
Tighten DenseMap's `erase` contract so that, like `insert` and `grow`, it invalidates iterators and references obtained before the call. Under the current tombstone-based deletion this is purely an LLVM_ENABLE_ABI_BREAKING_CHECKS check — the bucket array is not actually mutated for other entries — but it surfaces stale-iterator-after-erase patterns now rather than when DenseMap's deletion scheme changes. Mirrors the SmallPtrSet change in llvm#96762, which dropped tombstones in small mode and likewise had `erase` invalidate iterators. Depends on llvm#198982 and llvm#199365
|
@llvm/pr-subscribers-llvm-adt Author: Fangrui Song (MaskRay) ChangesTighten DenseMap's Mirrors the SmallPtrSet change in #96762, which dropped tombstones in Depends on #198982 and #199365 2 Files Affected:
diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h
index b8b548a31acbc..3dac5f6f1e371 100644
--- a/llvm/include/llvm/ADT/DenseMap.h
+++ b/llvm/include/llvm/ADT/DenseMap.h
@@ -330,6 +330,7 @@ class DenseMapBase : public DebugEpochBase {
if (!TheBucket)
return false; // not in map.
+ incrementEpoch();
TheBucket->getSecond().~ValueT();
TheBucket->getFirst() = KeyInfoT::getTombstoneKey();
decrementNumEntries();
@@ -338,6 +339,7 @@ class DenseMapBase : public DebugEpochBase {
}
void erase(iterator I) {
BucketT *TheBucket = &*I;
+ incrementEpoch();
TheBucket->getSecond().~ValueT();
TheBucket->getFirst() = KeyInfoT::getTombstoneKey();
decrementNumEntries();
diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp
index 553d159d33b1a..27bd2a3ef66d0 100644
--- a/llvm/unittests/ADT/DenseMapTest.cpp
+++ b/llvm/unittests/ADT/DenseMapTest.cpp
@@ -1108,4 +1108,24 @@ TEST(DenseMapCustomTest, ValueDtor) {
EXPECT_EQ(0u, CtorTester::getNumConstructed());
}
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+TEST(DenseMapCustomTest, EraseInvalidatesIterators) {
+ DenseMap<int, int> M;
+ M.try_emplace(1, 10);
+ M.try_emplace(2, 20);
+ auto It = M.find(1);
+ M.erase(2);
+ EXPECT_DEATH((void)It->second, "invalid iterator access!");
+}
+
+TEST(DenseMapCustomTest, EraseIteratorInvalidatesOtherIterators) {
+ DenseMap<int, int> M;
+ M.try_emplace(1, 10);
+ M.try_emplace(2, 20);
+ auto Keep = M.find(1);
+ M.erase(M.find(2));
+ EXPECT_DEATH((void)Keep->second, "invalid iterator access!");
+}
+#endif
+
} // namespace
|
aengelke
left a comment
aengelke
left a comment
There was a problem hiding this comment.
Also update ProgrammersManual.
aengelke
left a comment
aengelke
left a comment
There was a problem hiding this comment.
Changes LGTM once the CI passes and all previous PRs have been merged without outstanding regressions (perf/functionality).
The cleanup patches have all been merged. Per the "Explain Error" feature, "Build and Test Linux" and "Build and Test Linux aarch64" jobs are passing except the unrelated |
aengelke
left a comment
aengelke
left a comment
There was a problem hiding this comment.
The MLIR failure (MLIR :: Dialect/GPU/test-nvvm-pipeline.mlir) looks related, it hits the epoch assertion. Likewise the Clang and LLVM-AMDGPU failures.
Also, the perf regression from #198982 should be addressed.
Per the "Explain Error" feature,
Then we should absolutely not trust this.
Commented there and created a fix.
Good catch. I should open https://github.com/llvm/llvm-project/actions/runs/26412583595/job/77750081628?pr=199369 (My laptop isn't powerful enough - opening this in Chrome freezes for a moment...) and then search for |
FWIW, I always go straight to "View raw logs", which works for me on older hardware (in fact, I also blocked *.core.windows.net so that the site doesn't even attempt to load the logs inline for that reason). |
|
This PR broke the Solaris/amd64 and Solaris/sparcv9 buildbots. |
|
I'm also seeing the same test failures on one of my bots https://lab.llvm.org/buildbot/#/builders/174/builds/36084. |
What looks like the same failures also appear in compiler-rt pre-merge CI, e.g. #179926. |
The loop erases from AllocsForIndirectGlobals while walking it, which now hits the iterator invalidation assert in DenseMap::erase. Use remove_if instead. Started with #199369.
…symbols (#199655) processObjCImageInfo iterated the section's DenseSet of symbols while calling removeDefinedSymbol, which erases from that same set. Re-fetch begin() each iteration so the iterator is always fresh. Started with llvm/llvm-project#199369.
The loop erases from AllocsForIndirectGlobals while walking it, which now hits the iterator invalidation assert in DenseMap::erase. Use remove_if instead. Started with llvm/llvm-project#199369.
…symbols (#199655) processObjCImageInfo iterated the section's DenseSet of symbols while calling removeDefinedSymbol, which erases from that same set. Re-fetch begin() each iteration so the iterator is always fresh. Started with llvm/llvm-project#199369.
The loop erases from AllocsForIndirectGlobals while walking it, which now hits the iterator invalidation assert in DenseMap::erase. Use remove_if instead. Started with llvm/llvm-project#199369.
… for CTT) Squash of the landed SmallPtrSet/DenseMap optimization series plus the IR/Analysis getTombstoneKey/getEmptyKey cleanups, on top of the pre-SmallPtrSet baseline (parent of llvm#197637), so the compile-time tracker measures the whole series' cumulative impact as one from->to. The ADT DenseMapInfo getEmptyKey/getTombstoneKey definitions are intentionally kept: the primitive/generic specializations have direct callers tree-wide (e.g. CodeView TypeIndex.h, TableGen), so their removal needs the whole-tree caller cleanup that is out of scope here. Includes: llvm#197637 [SmallPtrSet] Drop tombstones in large mode llvm#198982 Don't assume non-erased DenseMap entries remain valid after erase llvm#199369 [DenseMap] Invalidate iterators on erase llvm#200540 [IR] Fix PoisoningVH relocation of a poisoned handle llvm#200595 [DenseMap] Replace tombstone deletion with TAOCP 6.4 Algorithm R llvm#200958 [IR][Analysis] Remove unused DenseMapInfo::getTombstoneKey llvm#201281 [DenseMap] Store occupancy in a packed used-bit array llvm#201742 [DenseMap] Fix ubsan error after llvm#201281 llvm#201997 [IR][Analysis] Remove unused DenseMapInfo::getEmptyKey Not for merge; measurement aid only.
5 participants
Tighten DenseMap's
erasecontract so that, likeinsertandgrow,it invalidates iterators and references obtained before the call.
Under the current tombstone-based deletion this is purely an
LLVM_ENABLE_ABI_BREAKING_CHECKS check — the bucket array is not actually
mutated for other entries — but it surfaces stale-iterator-after-erase
patterns now rather than when DenseMap's deletion scheme changes.
Mirrors the SmallPtrSet change in #96762, which dropped tombstones in
small mode and likewise had
eraseinvalidate iterators.Depends on #198982 and #199365