blob: 5b3ca1e7e2a00bf20e5c201f5555effb59d1df82 [file] [log] [blame] [edit]
// Copyright 2023 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include <condition_variable>
#include <functional>
#include <mutex>
#include <string>
#include <thread>
#include <vector>
#include "dawn/common/ContentLessObjectCache.h"
#include "dawn/utils/BinarySemaphore.h"
#include "gtest/gtest.h"
namespace dawn {
namespace {
using utils::BinarySemaphore;
class CacheableT : public RefCounted, public ContentLessObjectCacheable<CacheableT> {
public:
explicit CacheableT(size_t value) : mHash(value), mValue(value) {}
CacheableT(size_t hash, size_t value) : mHash(hash), mValue(value) {}
~CacheableT() override { mDeleteFn(this); }
struct HashFunc {
size_t operator()(const CacheableT* x) const {
x->mHashFn(x);
return x->mHash;
}
};
struct EqualityFunc {
bool operator()(const CacheableT* l, const CacheableT* r) const {
l->mEqualFn(l);
r->mEqualFn(r);
return l->mValue == r->mValue;
}
};
void SetHashFn(std::function<void(const CacheableT*)> fn) { mHashFn = fn; }
void SetEqualFn(std::function<void(const CacheableT*)> fn) { mEqualFn = fn; }
void SetDeleteFn(std::function<void(CacheableT*)> fn) { mDeleteFn = fn; }
private:
size_t mHash;
size_t mValue;
// Injectable functions to allow for isolated thread testing.
std::function<void(const CacheableT*)> mHashFn = [](const CacheableT*) -> void {};
std::function<void(const CacheableT*)> mEqualFn = [](const CacheableT*) -> void {};
std::function<void(CacheableT*)> mDeleteFn = [](CacheableT*) -> void {};
};
// Empty cache returns true on Empty().
TEST(ContentLessObjectCacheTest, Empty) {
ContentLessObjectCache<CacheableT> cache;
EXPECT_TRUE(cache.Empty());
}
// Non-empty cache returns false on Empty().
TEST(ContentLessObjectCacheTest, NonEmpty) {
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object = AcquireRef(new CacheableT(1));
object->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object.Get()).second);
EXPECT_FALSE(cache.Empty());
}
// Object inserted into the cache are findable.
TEST(ContentLessObjectCacheTest, Insert) {
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object = AcquireRef(new CacheableT(1));
object->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object.Get()).second);
CacheableT blueprint(1);
Ref<CacheableT> cached = cache.Find(&blueprint);
EXPECT_TRUE(object.Get() == cached.Get());
}
// Duplicate insert calls on different equivalent objects only inserts the first.
TEST(ContentLessObjectCacheTest, InsertDuplicate) {
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object1 = AcquireRef(new CacheableT(1));
object1->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object1.Get()).second);
Ref<CacheableT> object2 = AcquireRef(new CacheableT(1));
EXPECT_FALSE(cache.Insert(object2.Get()).second);
CacheableT blueprint(1);
Ref<CacheableT> cached = cache.Find(&blueprint);
EXPECT_TRUE(object1.Get() == cached.Get());
}
// Duplicate insert calls on different objects with the same hash inserts both objects.
TEST(ContentLessObjectCacheTest, InsertHashDuplicate) {
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object1 = AcquireRef(new CacheableT(1, 1));
object1->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object1.Get()).second);
Ref<CacheableT> object2 = AcquireRef(new CacheableT(1, 2));
object2->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object2.Get()).second);
CacheableT blueprint1(1, 1);
Ref<CacheableT> cached1 = cache.Find(&blueprint1);
EXPECT_TRUE(object1.Get() == cached1.Get());
CacheableT blueprint2(1, 2);
Ref<CacheableT> cached2 = cache.Find(&blueprint2);
EXPECT_TRUE(object2.Get() == cached2.Get());
}
// Erasing the only entry leaves the cache empty.
TEST(ContentLessObjectCacheTest, Erase) {
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object = AcquireRef(new CacheableT(1));
EXPECT_TRUE(cache.Insert(object.Get()).second);
EXPECT_FALSE(cache.Empty());
cache.Erase(object.Get());
EXPECT_TRUE(cache.Empty());
}
// Erasing an equivalent but not pointer equivalent entry is a no-op.
TEST(ContentLessObjectCacheTest, EraseDuplicate) {
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object1 = AcquireRef(new CacheableT(1));
object1->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object1.Get()).second);
EXPECT_FALSE(cache.Empty());
Ref<CacheableT> object2 = AcquireRef(new CacheableT(1));
cache.Erase(object2.Get());
EXPECT_FALSE(cache.Empty());
}
// Inserting and finding elements should respect the results from the insert call.
TEST(ContentLessObjectCacheTest, InsertingAndFinding) {
constexpr size_t kNumObjects = 100;
constexpr size_t kNumThreads = 8;
ContentLessObjectCache<CacheableT> cache;
std::vector<Ref<CacheableT>> objects(kNumObjects);
auto f = [&] {
for (size_t i = 0; i < kNumObjects; i++) {
Ref<CacheableT> object = AcquireRef(new CacheableT(i));
object->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
if (cache.Insert(object.Get()).second) {
// This shouldn't race because exactly 1 thread should successfully insert.
objects[i] = object;
}
}
for (size_t i = 0; i < kNumObjects; i++) {
CacheableT blueprint(i);
Ref<CacheableT> cached = cache.Find(&blueprint);
EXPECT_NE(cached.Get(), nullptr);
EXPECT_EQ(cached.Get(), objects[i].Get());
}
};
std::vector<std::thread> threads;
for (size_t t = 0; t < kNumThreads; t++) {
threads.emplace_back(f);
}
for (size_t t = 0; t < kNumThreads; t++) {
threads[t].join();
}
}
// Finding an element that is in the process of deletion should return nullptr.
TEST(ContentLessObjectCacheTest, FindDeleting) {
BinarySemaphore semA, semB;
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object = AcquireRef(new CacheableT(1));
object->SetDeleteFn([&](CacheableT* x) {
semA.Release();
semB.Acquire();
cache.Erase(x);
});
EXPECT_TRUE(cache.Insert(object.Get()).second);
// Thread A will release the last reference of the original object.
auto threadA = [&] { object = nullptr; };
// Thread B will try to Find the entry before it is completely destroyed.
auto threadB = [&] {
semA.Acquire();
CacheableT blueprint(1);
EXPECT_TRUE(cache.Find(&blueprint) == nullptr);
semB.Release();
};
std::thread tA(threadA);
std::thread tB(threadB);
tA.join();
tB.join();
}
// Finding an equivalent element when the cached version is in the process of deletion and the
// last ref of the object is actually the one acquired inside the find operation does not deadlock
// and returns the cached value. This is a regression test for dawn:1993.
TEST(ContentLessObjectCacheTest, FindDeletingLastRef) {
BinarySemaphore semA, semB;
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object = AcquireRef(new CacheableT(1));
object->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object.Get()).second);
CacheableT* objectPtr = object.Get();
std::atomic_flag eqOnceFlag;
object->SetEqualFn([&](const CacheableT* x) {
if (!eqOnceFlag.test_and_set()) {
semA.Release();
semB.Acquire();
}
});
// Thread A will release the last reference of the original object after the object has been
// promoted internally for equality check.
auto threadA = [&] {
semA.Acquire();
object = nullptr;
semB.Release();
};
// Thread B will try to Find the entry before the original object is destroyed.
auto threadB = [&] {
CacheableT blueprint(1);
EXPECT_TRUE(cache.Find(&blueprint) == objectPtr);
};
std::thread tA(threadA);
std::thread tB(threadB);
tA.join();
tB.join();
}
// Finding a non-equivalent but hash equivalent element when the cached version is in the process
// of deletion and the last ref of the object is actually the one acquired inside the find operation
// does not deadlock and returns nullptr. This is a regression test for dawn:1993.
TEST(ContentLessObjectCacheTest, FindDeletingLastRefHashEquivalent) {
BinarySemaphore semA, semB;
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object = AcquireRef(new CacheableT(1, 1));
object->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object.Get()).second);
std::atomic_flag eqOnceFlag;
object->SetEqualFn([&](const CacheableT* x) {
if (!eqOnceFlag.test_and_set()) {
semA.Release();
semB.Acquire();
}
});
// Thread A will release the last reference of the original object after the object has been
// promoted internally for equality check.
auto threadA = [&] {
semA.Acquire();
object = nullptr;
semB.Release();
};
// Thread B will try to Find a hash-equivalent entry before the original object is destroyed.
auto threadB = [&] {
CacheableT blueprint(1, 2);
EXPECT_TRUE(cache.Find(&blueprint) == nullptr);
};
std::thread tA(threadA);
std::thread tB(threadB);
tA.join();
tB.join();
}
// Inserting an element that has an entry which is in process of deletion should insert the new
// object.
TEST(ContentLessObjectCacheTest, InsertDeleting) {
BinarySemaphore semA, semB;
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object1 = AcquireRef(new CacheableT(1));
object1->SetDeleteFn([&](CacheableT* x) {
semA.Release();
semB.Acquire();
cache.Erase(x);
});
EXPECT_TRUE(cache.Insert(object1.Get()).second);
Ref<CacheableT> object2 = AcquireRef(new CacheableT(1));
object2->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
// Thread A will release the last reference of the original object.
auto threadA = [&] { object1 = nullptr; };
// Thread B will try to Insert an equivalent entry before the original is completely
// destroyed.
auto threadB = [&] {
semA.Acquire();
EXPECT_TRUE(cache.Insert(object2.Get()).second);
semB.Release();
};
std::thread tA(threadA);
std::thread tB(threadB);
tA.join();
tB.join();
CacheableT blueprint(1);
Ref<CacheableT> cached = cache.Find(&blueprint);
EXPECT_TRUE(object2.Get() == cached.Get());
}
// Inserting an equivalent element when the cached version is in the process of deletion and the
// last ref of the object is actually the one acquired inside the find operation does not deadlock
// and no insert happens. This is a regression test for dawn:1993.
TEST(ContentLessObjectCacheTest, InsertDeletingLastRef) {
BinarySemaphore semA, semB;
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object1 = AcquireRef(new CacheableT(1));
object1->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object1.Get()).second);
CacheableT* object1Ptr = object1.Get();
std::atomic_flag eqOnceFlag;
object1->SetEqualFn([&](const CacheableT* x) {
if (!eqOnceFlag.test_and_set()) {
semA.Release();
semB.Acquire();
}
});
// Thread A will release the last reference of the original object after the object has been
// promoted internally for equality check.
auto threadA = [&] {
semA.Acquire();
object1 = nullptr;
semB.Release();
};
// Thread B will try to Insert an equivalent entry before the original object is destroyed.
auto threadB = [&] {
Ref<CacheableT> object2 = AcquireRef(new CacheableT(1));
auto result = cache.Insert(object2.Get());
EXPECT_FALSE(result.second);
EXPECT_TRUE(result.first == object1Ptr);
};
std::thread tA(threadA);
std::thread tB(threadB);
tA.join();
tB.join();
}
// Inserting a non-equivalent but hash equivalent element when the cached version is in the process
// of deletion and the last ref of the object is actually the one acquired inside the find operation
// does not deadlock and the insert occurs successfully. This is a regression test for dawn:1993.
TEST(ContentLessObjectCacheTest, InsertDeletingLastRefHashEquivalent) {
BinarySemaphore semA, semB;
ContentLessObjectCache<CacheableT> cache;
Ref<CacheableT> object1 = AcquireRef(new CacheableT(1, 1));
object1->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
EXPECT_TRUE(cache.Insert(object1.Get()).second);
std::atomic_flag eqOnceFlag;
object1->SetEqualFn([&](const CacheableT* x) {
if (!eqOnceFlag.test_and_set()) {
semA.Release();
semB.Acquire();
}
});
// Thread A will release the last reference of the original object after the object has been
// promoted internally for equality check.
auto threadA = [&] {
semA.Acquire();
object1 = nullptr;
semB.Release();
};
// Thread B will try to Insert a hash equivalent entry before the original object is destroyed.
auto threadB = [&] {
Ref<CacheableT> object2 = AcquireRef(new CacheableT(1, 2));
object2->SetDeleteFn([&](CacheableT* x) { cache.Erase(x); });
auto result = cache.Insert(object2.Get());
EXPECT_TRUE(result.second);
EXPECT_TRUE(result.first == object2.Get());
};
std::thread tA(threadA);
std::thread tB(threadB);
tA.join();
tB.join();
}
} // anonymous namespace
} // namespace dawn