src/dawn/tests/unittests/ContentLessObjectCacheTests.cpp

// 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