| // Copyright 2017 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #if defined(THREAD_SANITIZER) |
| |
| #include "testing/gtest/include/gtest/gtest.h" |
| #include "third_party/blink/renderer/platform/bindings/script_forbidden_scope.h" |
| #include "third_party/blink/renderer/platform/heap/garbage_collected.h" |
| #include "third_party/blink/renderer/platform/heap/heap_allocator.h" |
| #include "third_party/blink/renderer/platform/heap/heap_test_utilities.h" |
| #include "third_party/blink/renderer/platform/heap/member.h" |
| #include "third_party/blink/renderer/platform/heap/persistent.h" |
| #include "third_party/blink/renderer/platform/heap/thread_state.h" |
| |
| namespace blink { |
| |
| class ConcurrentMarkingTest : public TestSupportingGC {}; |
| |
| namespace concurrent_marking_test { |
| |
| template <typename T> |
| class CollectionWrapper : public GarbageCollected<CollectionWrapper<T>> { |
| public: |
| CollectionWrapper() : collection_(MakeGarbageCollected<T>()) {} |
| |
| void Trace(Visitor* visitor) const { visitor->Trace(collection_); } |
| |
| T* GetCollection() { return collection_.Get(); } |
| |
| private: |
| Member<T> collection_; |
| }; |
| |
| // ============================================================================= |
| // Tests that expose data races when modifying collections ===================== |
| // ============================================================================= |
| |
| template <typename T> |
| struct MethodAdapterBase { |
| template <typename U> |
| static void insert(T& t, U&& u) { |
| t.insert(std::forward<U>(u)); |
| } |
| |
| static void erase(T& t, typename T::iterator&& it) { |
| t.erase(std::forward<typename T::iterator>(it)); |
| } |
| |
| static void Swap(T& a, T& b) { a.swap(b); } |
| }; |
| |
| template <typename T> |
| struct MethodAdapter : public MethodAdapterBase<T> {}; |
| |
| template <typename C> |
| void AddToCollection() { |
| constexpr int kIterations = 10; |
| IncrementalMarkingTestDriver driver(ThreadState::Current()); |
| Persistent<CollectionWrapper<C>> persistent = |
| MakeGarbageCollected<CollectionWrapper<C>>(); |
| C* collection = persistent->GetCollection(); |
| driver.Start(); |
| for (int i = 0; i < kIterations; ++i) { |
| driver.SingleConcurrentStep(); |
| for (int j = 0; j < kIterations; ++j) { |
| int num = kIterations * i + j; |
| MethodAdapter<C>::insert(*collection, |
| MakeGarbageCollected<IntegerObject>(num)); |
| } |
| } |
| driver.FinishSteps(); |
| driver.FinishGC(); |
| } |
| |
| template <typename C, typename GetLocation> |
| void RemoveFromCollectionAtLocation(GetLocation location) { |
| constexpr int kIterations = 10; |
| IncrementalMarkingTestDriver driver(ThreadState::Current()); |
| Persistent<CollectionWrapper<C>> persistent = |
| MakeGarbageCollected<CollectionWrapper<C>>(); |
| C* collection = persistent->GetCollection(); |
| for (int i = 0; i < (kIterations * kIterations); ++i) { |
| MethodAdapter<C>::insert(*collection, |
| MakeGarbageCollected<IntegerObject>(i)); |
| } |
| driver.Start(); |
| for (int i = 0; i < kIterations; ++i) { |
| driver.SingleConcurrentStep(); |
| for (int j = 0; j < kIterations; ++j) { |
| MethodAdapter<C>::erase(*collection, location(collection)); |
| } |
| } |
| driver.FinishSteps(); |
| driver.FinishGC(); |
| } |
| |
| template <typename C> |
| void RemoveFromBeginningOfCollection() { |
| RemoveFromCollectionAtLocation<C>( |
| [](C* collection) { return collection->begin(); }); |
| } |
| |
| template <typename C> |
| void RemoveFromMiddleOfCollection() { |
| RemoveFromCollectionAtLocation<C>([](C* collection) { |
| auto iterator = collection->begin(); |
| // Move iterator to middle of collection. |
| for (size_t i = 0; i < collection->size() / 2; ++i) { |
| ++iterator; |
| } |
| return iterator; |
| }); |
| } |
| |
| template <typename C> |
| void RemoveFromEndOfCollection() { |
| RemoveFromCollectionAtLocation<C>([](C* collection) { |
| auto iterator = collection->end(); |
| return --iterator; |
| }); |
| } |
| |
| template <typename C> |
| void ClearCollection() { |
| constexpr int kIterations = 10; |
| IncrementalMarkingTestDriver driver(ThreadState::Current()); |
| Persistent<CollectionWrapper<C>> persistent = |
| MakeGarbageCollected<CollectionWrapper<C>>(); |
| C* collection = persistent->GetCollection(); |
| driver.Start(); |
| for (int i = 0; i < kIterations; ++i) { |
| driver.SingleConcurrentStep(); |
| for (int j = 0; j < kIterations; ++j) { |
| MethodAdapter<C>::insert(*collection, |
| MakeGarbageCollected<IntegerObject>(i)); |
| } |
| collection->clear(); |
| } |
| driver.FinishSteps(); |
| driver.FinishGC(); |
| } |
| |
| template <typename C> |
| void SwapCollections() { |
| constexpr int kIterations = 10; |
| IncrementalMarkingTestDriver driver(ThreadState::Current()); |
| Persistent<CollectionWrapper<C>> persistent = |
| MakeGarbageCollected<CollectionWrapper<C>>(); |
| C* collection = persistent->GetCollection(); |
| driver.Start(); |
| for (int i = 0; i < (kIterations * kIterations); ++i) { |
| C* new_collection = MakeGarbageCollected<C>(); |
| for (int j = 0; j < kIterations * i; ++j) { |
| MethodAdapter<C>::insert(*new_collection, |
| MakeGarbageCollected<IntegerObject>(j)); |
| } |
| driver.SingleConcurrentStep(); |
| MethodAdapter<C>::Swap(*collection, *new_collection); |
| } |
| driver.FinishSteps(); |
| driver.FinishGC(); |
| } |
| |
| // HeapHashMap |
| |
| template <typename T> |
| using IdentityHashMap = HeapHashMap<T, T>; |
| |
| template <typename T> |
| struct MethodAdapter<HeapHashMap<T, T>> |
| : public MethodAdapterBase<HeapHashMap<T, T>> { |
| template <typename U> |
| static void insert(HeapHashMap<T, T>& map, U&& u) { |
| map.insert(u, u); |
| } |
| }; |
| |
| TEST_F(ConcurrentMarkingTest, AddToHashMap) { |
| AddToCollection<IdentityHashMap<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfHashMap) { |
| RemoveFromBeginningOfCollection<IdentityHashMap<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfHashMap) { |
| RemoveFromMiddleOfCollection<IdentityHashMap<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfHashMap) { |
| RemoveFromEndOfCollection<IdentityHashMap<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearHashMap) { |
| ClearCollection<IdentityHashMap<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapHashMap) { |
| SwapCollections<IdentityHashMap<Member<IntegerObject>>>(); |
| } |
| |
| // HeapHashSet |
| |
| TEST_F(ConcurrentMarkingTest, AddToHashSet) { |
| AddToCollection<HeapHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfHashSet) { |
| RemoveFromBeginningOfCollection<HeapHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfHashSet) { |
| RemoveFromMiddleOfCollection<HeapHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfHashSet) { |
| RemoveFromEndOfCollection<HeapHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearHashSet) { |
| ClearCollection<HeapHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapHashSet) { |
| SwapCollections<HeapHashSet<Member<IntegerObject>>>(); |
| } |
| |
| template <typename T> |
| struct MethodAdapter<HeapLinkedHashSet<T>> |
| : public MethodAdapterBase<HeapLinkedHashSet<T>> { |
| static void Swap(HeapLinkedHashSet<T>& a, HeapLinkedHashSet<T>& b) { |
| a.Swap(b); |
| } |
| }; |
| |
| TEST_F(ConcurrentMarkingTest, AddToLinkedHashSet) { |
| AddToCollection<HeapLinkedHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfLinkedHashSet) { |
| RemoveFromBeginningOfCollection<HeapLinkedHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfLinkedHashSet) { |
| RemoveFromMiddleOfCollection<HeapLinkedHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfLinkedHashSet) { |
| RemoveFromEndOfCollection<HeapLinkedHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearLinkedHashSet) { |
| ClearCollection<HeapLinkedHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapLinkedHashSet) { |
| SwapCollections<HeapLinkedHashSet<Member<IntegerObject>>>(); |
| } |
| |
| // HeapListHashSet |
| |
| template <typename T> |
| struct MethodAdapter<HeapListHashSet<T>> |
| : public MethodAdapterBase<HeapListHashSet<T>> { |
| static void Swap(HeapListHashSet<T>& a, HeapListHashSet<T>& b) { a.Swap(b); } |
| }; |
| |
| TEST_F(ConcurrentMarkingTest, AddToListHashSet) { |
| AddToCollection<HeapListHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfListHashSet) { |
| RemoveFromBeginningOfCollection<HeapListHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfListHashSet) { |
| RemoveFromMiddleOfCollection<HeapListHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfListHashSet) { |
| RemoveFromEndOfCollection<HeapListHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearListHashSet) { |
| ClearCollection<HeapListHashSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapListHashSet) { |
| SwapCollections<HeapListHashSet<Member<IntegerObject>>>(); |
| } |
| |
| // HeapHashCountedSet |
| |
| TEST_F(ConcurrentMarkingTest, AddToHashCountedSet) { |
| AddToCollection<HeapHashCountedSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfHashCountedSet) { |
| RemoveFromBeginningOfCollection<HeapHashCountedSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfHashCountedSet) { |
| RemoveFromMiddleOfCollection<HeapHashCountedSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfHashCountedSet) { |
| RemoveFromEndOfCollection<HeapHashCountedSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearHashCountedSet) { |
| ClearCollection<HeapHashCountedSet<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapHashCountedSet) { |
| SwapCollections<HeapHashCountedSet<Member<IntegerObject>>>(); |
| } |
| |
| // HeapVector |
| |
| // Additional test for vectors and deques |
| template <typename V> |
| void PopFromCollection() { |
| constexpr int kIterations = 10; |
| IncrementalMarkingTestDriver driver(ThreadState::Current()); |
| Persistent<CollectionWrapper<V>> persistent = |
| MakeGarbageCollected<CollectionWrapper<V>>(); |
| V* vector = persistent->GetCollection(); |
| for (int i = 0; i < (kIterations * kIterations); ++i) { |
| MethodAdapter<V>::insert(*vector, MakeGarbageCollected<IntegerObject>(i)); |
| } |
| driver.Start(); |
| for (int i = 0; i < kIterations; ++i) { |
| driver.SingleConcurrentStep(); |
| for (int j = 0; j < kIterations; ++j) { |
| vector->pop_back(); |
| } |
| } |
| driver.FinishSteps(); |
| driver.FinishGC(); |
| } |
| |
| #define TEST_VECTOR_COLLECTION(name, type) \ |
| TEST_F(ConcurrentMarkingTest, AddTo##name) { AddToCollection<type>(); } \ |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOf##name) { \ |
| RemoveFromBeginningOfCollection<type>(); \ |
| } \ |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOf##name) { \ |
| RemoveFromMiddleOfCollection<type>(); \ |
| } \ |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOf##name) { \ |
| RemoveFromEndOfCollection<type>(); \ |
| } \ |
| TEST_F(ConcurrentMarkingTest, Clear##name) { ClearCollection<type>(); } \ |
| TEST_F(ConcurrentMarkingTest, Swap##name) { SwapCollections<type>(); } \ |
| TEST_F(ConcurrentMarkingTest, PopFrom##name) { PopFromCollection<type>(); } |
| |
| template <typename T, wtf_size_t inlineCapacity> |
| struct MethodAdapter<HeapVector<T, inlineCapacity>> |
| : public MethodAdapterBase<HeapVector<T, inlineCapacity>> { |
| template <typename U> |
| static void insert(HeapVector<T, inlineCapacity>& vector, U&& u) { |
| vector.push_back(std::forward<U>(u)); |
| } |
| }; |
| |
| TEST_F(ConcurrentMarkingTest, AddToVector) { |
| AddToCollection<HeapVector<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfVector) { |
| RemoveFromBeginningOfCollection<HeapVector<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfVector) { |
| RemoveFromMiddleOfCollection<HeapVector<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfVector) { |
| RemoveFromEndOfCollection<HeapVector<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearVector) { |
| ClearCollection<HeapVector<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapVector) { |
| SwapCollections<HeapVector<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, PopFromVector) { |
| PopFromCollection<HeapVector<Member<IntegerObject>>>(); |
| } |
| |
| // HeapVector with inlined buffer |
| |
| template <typename T> |
| using HeapVectorWithInlineStorage = HeapVector<T, 10>; |
| |
| TEST_F(ConcurrentMarkingTest, AddToInlinedVector) { |
| AddToCollection<HeapVectorWithInlineStorage<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfInlinedVector) { |
| RemoveFromBeginningOfCollection< |
| HeapVectorWithInlineStorage<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfInlinedVector) { |
| RemoveFromMiddleOfCollection< |
| HeapVectorWithInlineStorage<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfInlinedVector) { |
| RemoveFromEndOfCollection< |
| HeapVectorWithInlineStorage<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearInlinedVector) { |
| ClearCollection<HeapVectorWithInlineStorage<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapInlinedVector) { |
| SwapCollections<HeapVectorWithInlineStorage<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, PopFromInlinedVector) { |
| PopFromCollection<HeapVectorWithInlineStorage<Member<IntegerObject>>>(); |
| } |
| |
| // HeapVector of std::pairs |
| |
| template <typename T> |
| using HeapVectorOfPairs = HeapVector<std::pair<T, T>>; |
| |
| template <typename T, wtf_size_t inlineCapacity> |
| struct MethodAdapter<HeapVector<std::pair<T, T>, inlineCapacity>> |
| : public MethodAdapterBase<HeapVector<std::pair<T, T>, inlineCapacity>> { |
| template <typename U> |
| static void insert(HeapVector<std::pair<T, T>, inlineCapacity>& vector, |
| U&& u) { |
| vector.push_back(std::make_pair<U&, U&>(u, u)); |
| } |
| }; |
| |
| TEST_F(ConcurrentMarkingTest, AddToVectorOfPairs) { |
| AddToCollection<HeapVectorOfPairs<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfVectorOfPairs) { |
| RemoveFromBeginningOfCollection<HeapVectorOfPairs<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfVectorOfPairs) { |
| RemoveFromMiddleOfCollection<HeapVectorOfPairs<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfVectorOfPairs) { |
| RemoveFromEndOfCollection<HeapVectorOfPairs<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearVectorOfPairs) { |
| ClearCollection<HeapVectorOfPairs<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapVectorOfPairs) { |
| SwapCollections<HeapVectorOfPairs<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, PopFromVectorOfPairs) { |
| PopFromCollection<HeapVectorOfPairs<Member<IntegerObject>>>(); |
| } |
| |
| // HeapDeque |
| |
| template <typename T> |
| struct MethodAdapter<HeapDeque<T>> : public MethodAdapterBase<HeapDeque<T>> { |
| template <typename U> |
| static void insert(HeapDeque<T>& deque, U&& u) { |
| deque.push_back(std::forward<U>(u)); |
| } |
| |
| static void erase(HeapDeque<T>& deque, typename HeapDeque<T>::iterator&& it) { |
| deque.pop_back(); |
| } |
| |
| static void Swap(HeapDeque<T>& a, HeapDeque<T>& b) { a.Swap(b); } |
| }; |
| |
| TEST_F(ConcurrentMarkingTest, AddToDeque) { |
| AddToCollection<HeapDeque<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromBeginningOfDeque) { |
| RemoveFromBeginningOfCollection<HeapDeque<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromMiddleOfDeque) { |
| RemoveFromMiddleOfCollection<HeapDeque<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, RemoveFromEndOfDeque) { |
| RemoveFromEndOfCollection<HeapDeque<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, ClearDeque) { |
| ClearCollection<HeapDeque<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, SwapDeque) { |
| SwapCollections<HeapDeque<Member<IntegerObject>>>(); |
| } |
| TEST_F(ConcurrentMarkingTest, PopFromDeque) { |
| PopFromCollection<HeapDeque<Member<IntegerObject>>>(); |
| } |
| |
| namespace { |
| |
| class RegisteredMixin; |
| |
| class CollectsMixins : public GarbageCollected<CollectsMixins> { |
| using MixinSet = HeapHashSet<Member<RegisteredMixin>>; |
| |
| public: |
| CollectsMixins() : set_(MakeGarbageCollected<MixinSet>()) {} |
| void RegisterMixin(RegisteredMixin* mixin) { set_->insert(mixin); } |
| void Trace(Visitor* visitor) const { visitor->Trace(set_); } |
| |
| private: |
| Member<MixinSet> set_; |
| }; |
| |
| class RegisteredMixin : public GarbageCollectedMixin { |
| public: |
| RegisteredMixin(CollectsMixins* collector) { collector->RegisterMixin(this); } |
| }; |
| |
| class GCedWithRegisteredMixin |
| : public GarbageCollected<GCedWithRegisteredMixin>, |
| public RegisteredMixin { |
| public: |
| GCedWithRegisteredMixin(CollectsMixins* collector) |
| : RegisteredMixin(collector) {} |
| void Trace(Visitor*) const override {} |
| }; |
| |
| } // namespace |
| |
| TEST_F(ConcurrentMarkingTest, MarkingInConstructionMixin) { |
| constexpr int kIterations = 10; |
| IncrementalMarkingTestDriver driver(ThreadState::Current()); |
| Persistent<CollectsMixins> collector = MakeGarbageCollected<CollectsMixins>(); |
| driver.Start(); |
| for (int i = 0; i < kIterations; ++i) { |
| driver.SingleConcurrentStep(); |
| for (int j = 0; j < kIterations; ++j) { |
| MakeGarbageCollected<GCedWithRegisteredMixin>(collector.Get()); |
| } |
| } |
| driver.FinishSteps(); |
| driver.FinishGC(); |
| } |
| |
| } // namespace concurrent_marking_test |
| } // namespace blink |
| |
| #endif // defined(THREAD_SANITIZER) |