From e6918187568dbd01842d8d1d2c808ce16a894239 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 21 Apr 2024 13:54:28 +0200 Subject: Adding upstream version 18.2.2. Signed-off-by: Daniel Baumann --- src/test/crimson/test_lru.cc | 213 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 213 insertions(+) create mode 100644 src/test/crimson/test_lru.cc (limited to 'src/test/crimson/test_lru.cc') diff --git a/src/test/crimson/test_lru.cc b/src/test/crimson/test_lru.cc new file mode 100644 index 000000000..40ab41539 --- /dev/null +++ b/src/test/crimson/test_lru.cc @@ -0,0 +1,213 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab +/* + * Ceph - scalable distributed file system + * + * Copyright (C) 2013 Cloudwatt + * + * Author: Loic Dachary + * Cheng Cheng + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library Public License for more details. + * + */ + +#include +#include "gtest/gtest.h" +#include "crimson/common/shared_lru.h" + +class LRUTest : public SharedLRU { +public: + auto add(unsigned int key, int value, bool* existed = nullptr) { + auto pv = new int{value}; + auto ptr = insert(key, std::unique_ptr{pv}); + if (existed) { + *existed = (ptr.get() != pv); + } + return ptr; + } +}; + +TEST(LRU, add) { + LRUTest cache; + unsigned int key = 1; + int value1 = 2; + bool existed = false; + { + auto ptr = cache.add(key, value1, &existed); + ASSERT_TRUE(ptr); + ASSERT_TRUE(ptr.get()); + ASSERT_EQ(value1, *ptr); + ASSERT_FALSE(existed); + } + { + auto ptr = cache.add(key, 3, &existed); + ASSERT_EQ(value1, *ptr); + ASSERT_TRUE(existed); + } +} + +TEST(LRU, empty) { + LRUTest cache; + unsigned int key = 1; + bool existed = false; + + ASSERT_TRUE(cache.empty()); + { + int value1 = 2; + auto ptr = cache.add(key, value1, &existed); + ASSERT_EQ(value1, *ptr); + ASSERT_FALSE(existed); + } + ASSERT_FALSE(cache.empty()); + + cache.clear(); + ASSERT_TRUE(cache.empty()); +} + +TEST(LRU, lookup) { + LRUTest cache; + unsigned int key = 1; + { + int value = 2; + auto ptr = cache.add(key, value); + ASSERT_TRUE(ptr); + ASSERT_TRUE(ptr.get()); + ASSERT_TRUE(cache.find(key).get()); + ASSERT_EQ(value, *cache.find(key)); + } + ASSERT_TRUE(cache.find(key).get()); +} + +TEST(LRU, lookup_or_create) { + LRUTest cache; + { + int value = 2; + unsigned int key = 1; + ASSERT_TRUE(cache.add(key, value).get()); + ASSERT_TRUE(cache[key].get()); + ASSERT_EQ(value, *cache.find(key)); + } + { + unsigned int key = 2; + ASSERT_TRUE(cache[key].get()); + ASSERT_EQ(0, *cache.find(key)); + } + ASSERT_TRUE(cache.find(1).get()); + ASSERT_TRUE(cache.find(2).get()); +} + +TEST(LRU, lower_bound) { + LRUTest cache; + + { + unsigned int key = 1; + ASSERT_FALSE(cache.lower_bound(key)); + int value = 2; + + ASSERT_TRUE(cache.add(key, value).get()); + ASSERT_TRUE(cache.lower_bound(key).get()); + EXPECT_EQ(value, *cache.lower_bound(key)); + } +} + +TEST(LRU, get_next) { + + { + LRUTest cache; + const unsigned int key = 0; + EXPECT_FALSE(cache.upper_bound(key)); + } + { + LRUTest cache; + const unsigned int key1 = 111; + auto ptr1 = cache[key1]; + const unsigned int key2 = 222; + auto ptr2 = cache[key2]; + + auto i = cache.upper_bound(0); + ASSERT_TRUE(i); + EXPECT_EQ(i->first, key1); + auto j = cache.upper_bound(i->first); + ASSERT_TRUE(j); + EXPECT_EQ(j->first, key2); + } +} + +TEST(LRU, clear) { + LRUTest cache; + unsigned int key = 1; + int value = 2; + cache.add(key, value); + { + auto found = cache.find(key); + ASSERT_TRUE(found); + ASSERT_EQ(value, *found); + } + ASSERT_TRUE(cache.find(key).get()); + cache.clear(); + ASSERT_FALSE(cache.find(key)); + ASSERT_TRUE(cache.empty()); +} + +TEST(LRU, eviction) { + LRUTest cache{5}; + bool existed; + // add a bunch of elements, some of them will be evicted + for (size_t i = 0; i < 2 * cache.capacity(); ++i) { + cache.add(i, i, &existed); + ASSERT_FALSE(existed); + } + size_t i = 0; + for (; i < cache.capacity(); ++i) { + ASSERT_FALSE(cache.find(i)); + } + for (; i < 2 * cache.capacity(); ++i) { + ASSERT_TRUE(cache.find(i)); + } +} + +TEST(LRU, track_weak) { + constexpr int SIZE = 5; + LRUTest cache{SIZE}; + + bool existed = false; + // strong reference to keep 0 alive + auto ptr = cache.add(0, 0, &existed); + ASSERT_FALSE(existed); + + // add a bunch of elements to get 0 evicted + for (size_t i = 1; i < 2 * cache.capacity(); ++i) { + cache.add(i, i, &existed); + ASSERT_FALSE(existed); + } + // 0 is still reachable via the cache + ASSERT_TRUE(cache.find(0)); + ASSERT_TRUE(cache.find(0).get()); + ASSERT_EQ(0, *cache.find(0)); + + // [0..SIZE) are evicted when adding [SIZE..2*SIZE) + // [SIZE..SIZE * 2) were still in the cache before accessing 0, + // but SIZE got evicted when accessing 0 + ASSERT_FALSE(cache.find(SIZE-1)); + ASSERT_FALSE(cache.find(SIZE)); + ASSERT_TRUE(cache.find(SIZE+1)); + ASSERT_TRUE(cache.find(SIZE+1).get()); + ASSERT_EQ((int)SIZE+1, *cache.find(SIZE+1)); + + ptr.reset(); + // 0 is still reachable, as it is now put back into LRU cache + ASSERT_TRUE(cache.find(0)); +} + +// Local Variables: +// compile-command: "cmake --build ../../../build -j 8 --target unittest_seastar_lru && ctest -R unittest_seastar_lru # --gtest_filter=*.* --log-to-stderr=true" +// End: -- cgit v1.2.3