From dd34fdb361cde5a32d392520a833526c5ad39b04 Mon Sep 17 00:00:00 2001 From: Jianpeng Ma Date: Thu, 22 Nov 2018 16:25:20 +0800 Subject: [PATCH] crimson/common: added templated LRU cache the implementation is modeled after src/common/shared_cache.hpp, with following changes/improvements * split the implementation into two parts: - simple_lru.h: for the basic LRU cache. which tracks the least recently used (LRU) cache using a list, and uses a map for lookup. in future, we could use boost's multiple-index-container to replace this combination. - shared_lru.h: for the improved version of LRU cache, it also tries to track the evcited but still alive objects using a customized deleter of shared_ptr, and it keeps a map of weak_ptr pointing to these objects. the customized deleter will remove the tracked item in weak_ptr map once all shared_ptrs are destroyed. * specialize LRUCache for ordered and non-ordered lookup. in existing OSD, `SimpleLRU` is used for caching the encoded osdmaps, and we don't use `lower_bound()`, `upper_bound()` or `get_next()` accessors for accessing these maps, so no need to store them with `std::map`. and in crimson-osd, it would be great if we can ditch `SimpleLRU`, and reuse `LRUCache` directly if `SharedLRU` is overkill. so let's prepare for this by specializing for the `unordered_map<>`. * remove (not yet) unused methods from SharedLRU, like `purge()`, dump_weak_refs() * change some function signatures to resemble those in `std::map`, for instance, - change `lookup()` to `find()` - change `lookup_or_create()` to `operator[]()` * add comment to document `SharedLRU` class * add test for SharedLRU Signed-off-by: Jianpeng Ma Signed-off-by: Kefu Chai --- src/crimson/common/shared_lru.h | 167 +++++++++++++++++++++++++ src/crimson/common/simple_lru.h | 141 +++++++++++++++++++++ src/test/crimson/CMakeLists.txt | 5 + src/test/crimson/test_lru.cc | 213 ++++++++++++++++++++++++++++++++ 4 files changed, 526 insertions(+) create mode 100644 src/crimson/common/shared_lru.h create mode 100644 src/crimson/common/simple_lru.h create mode 100644 src/test/crimson/test_lru.cc diff --git a/src/crimson/common/shared_lru.h b/src/crimson/common/shared_lru.h new file mode 100644 index 00000000000..14f2d4e85ef --- /dev/null +++ b/src/crimson/common/shared_lru.h @@ -0,0 +1,167 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#pragma once + +#include +#include +#include +#include +#include "simple_lru.h" + +/// SharedLRU does its best to cache objects. It not only tracks the objects +/// in its LRU cache with strong references, it also tracks objects with +/// weak_ptr even if the cache does not hold any strong references to them. so +/// that it can return the objects after they are evicted, as long as they've +/// ever been cached and have not been destroyed yet. +template +class SharedLRU { + using shared_ptr_t = boost::local_shared_ptr; + using weak_ptr_t = boost::weak_ptr; + using value_type = std::pair; + + // weak_refs is already ordered, and we don't use accessors like + // LRUCache::lower_bound(), so unordered LRUCache would suffice. + SimpleLRU cache; + std::map> weak_refs; + + struct Deleter { + SharedLRU* cache; + const K key; + void operator()(V* ptr) { + cache->_erase(key); + delete ptr; + } + }; + void _erase(const K& key) { + weak_refs.erase(key); + } +public: + SharedLRU(size_t max_size = 20) + : cache{max_size} + {} + ~SharedLRU() { + cache.clear(); + // use plain assert() in utiliy classes to avoid dependencies on logging + assert(weak_refs.empty()); + } + /** + * Returns a reference to the given key, and perform an insertion if such + * key does not already exist + */ + shared_ptr_t operator[](const K& key); + /** + * Returns true iff there are no live references left to anything that has been + * in the cache. + */ + bool empty() const { + return weak_refs.empty(); + } + size_t size() const { + return cache.size(); + } + size_t capacity() const { + return cache.capacity(); + } + /*** + * Inserts a key if not present, or bumps it to the front of the LRU if + * it is, and then gives you a reference to the value. If the key already + * existed, you are responsible for deleting the new value you tried to + * insert. + * + * @param key The key to insert + * @param value The value that goes with the key + * @param existed Set to true if the value was already in the + * map, false otherwise + * @return A reference to the map's value for the given key + */ + shared_ptr_t insert(const K& key, std::unique_ptr value); + // clear all strong reference from the lru. + void clear() { + cache.clear(); + } + shared_ptr_t find(const K& key); + // return the last element that is not greater than key + shared_ptr_t lower_bound(const K& key); + // return the first element that is greater than key + std::optional upper_bound(const K& key); +}; + +template +typename SharedLRU::shared_ptr_t +SharedLRU::insert(const K& key, std::unique_ptr value) +{ + shared_ptr_t val; + if (auto found = weak_refs.find(key); found != weak_refs.end()) { + val = found->second.first.lock(); + } + if (!val) { + val.reset(value.release(), Deleter{this, key}); + weak_refs.emplace(key, std::make_pair(val, val.get())); + } + cache.insert(key, val); + return val; +} + +template +typename SharedLRU::shared_ptr_t +SharedLRU::operator[](const K& key) +{ + shared_ptr_t val; + if (auto found = weak_refs.find(key); found != weak_refs.end()) { + val = found->second.first.lock(); + } + if (!val) { + val.reset(new V{}, Deleter{this, key}); + weak_refs.emplace(key, std::make_pair(val, val.get())); + } + cache.insert(key, val); + return val; +} + +template +typename SharedLRU::shared_ptr_t +SharedLRU::find(const K& key) +{ + shared_ptr_t val; + if (auto found = weak_refs.find(key); found != weak_refs.end()) { + val = found->second.first.lock(); + } + if (val) { + cache.insert(key, val); + } + return val; +} + +template +typename SharedLRU::shared_ptr_t +SharedLRU::lower_bound(const K& key) +{ + if (weak_refs.empty()) { + return {}; + } + auto found = weak_refs.lower_bound(key); + if (found == weak_refs.end()) { + --found; + } + if (auto val = found->second.first.lock(); val) { + cache.insert(key, val); + return val; + } else { + return {}; + } +} + +template +std::optional::value_type> +SharedLRU::upper_bound(const K& key) +{ + for (auto found = weak_refs.upper_bound(key); + found != weak_refs.end(); + ++found) { + if (auto val = found->second.first.lock(); val) { + return std::make_pair(found->first, val); + } + } + return std::nullopt; +} diff --git a/src/crimson/common/simple_lru.h b/src/crimson/common/simple_lru.h new file mode 100644 index 00000000000..fca1061fd8c --- /dev/null +++ b/src/crimson/common/simple_lru.h @@ -0,0 +1,141 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#pragma once + +#include +#include +#include +#include +#include + +template +class SimpleLRU { + static_assert(std::is_default_constructible_v); + using list_type = std::list; + template + using map_t = std::conditional_t, + std::unordered_map>; + using map_type = map_t>; + list_type lru; + map_type cache; + const size_t max_size; + +public: + SimpleLRU(size_t size = 20) + : cache(size), + max_size(size) + {} + size_t size() const { + return cache.size(); + } + size_t capacity() const { + return max_size; + } + using insert_return_type = std::pair; + insert_return_type insert(const Key& key, Value value); + std::optional find(const Key& key); + std::optional> lower_bound(const Key& key); + void erase(const Key& key); + void clear(); +private: + // bump the item to the front of the lru list + Value _lru_add(typename map_type::iterator found); + // evict the last element of most recently used list + void _evict(); +}; + +template +typename SimpleLRU::insert_return_type +SimpleLRU::insert(const Key& key, Value value) +{ + if constexpr(Ordered) { + auto found = cache.lower_bound(key); + if (found != cache.end() && found->first == key) { + // already exists + return {found->second.first, true}; + } else { + if (size() >= capacity()) { + _evict(); + } + lru.push_front(key); + // use lower_bound as hint to save the lookup + cache.emplace_hint(found, key, std::make_pair(value, lru.begin())); + return {std::move(value), false}; + } + } else { + // cache is not ordered + auto found = cache.find(key); + if (found != cache.end()) { + // already exists + return {found->second.first, true}; + } else { + if (size() >= capacity()) { + _evict(); + } + lru.push_front(key); + cache.emplace(key, std::make_pair(value, lru.begin())); + return {std::move(value), false}; + } + } +} + +template +std::optional SimpleLRU::find(const Key& key) +{ + if (auto found = cache.find(key); found != cache.end()){ + return _lru_add(found); + } else { + return {}; + } +} + +template +std::optional> +SimpleLRU::lower_bound(const Key& key) +{ + if (auto found = cache.lower_bound(key); found != cache.end()) { + return _lru_add(found); + } else { + return {}; + } +} + +template +void SimpleLRU::clear() +{ + lru.clear(); + cache.clear(); +} + +template +void SimpleLRU::erase(const Key& key) +{ + if (auto found = cache.find(key); found != cache.end()) { + lru.erase(found->second->second); + cache.erase(found); + } +} + +template +Value SimpleLRU::_lru_add( + typename SimpleLRU::map_type::iterator found) +{ + auto& [value, in_lru] = found->second; + if (in_lru != lru.begin()){ + // move item to the front + lru.splice(lru.begin(), lru, in_lru); + } + // the item is already at the front + return value; +} + +template +void SimpleLRU::_evict() +{ + // evict the last element of most recently used list + auto last = --lru.end(); + cache.erase(*last); + lru.erase(last); +} diff --git a/src/test/crimson/CMakeLists.txt b/src/test/crimson/CMakeLists.txt index 0feb616d24e..8626b7e6d1d 100644 --- a/src/test/crimson/CMakeLists.txt +++ b/src/test/crimson/CMakeLists.txt @@ -37,3 +37,8 @@ add_executable(unittest_seastar_perfcounters add_ceph_unittest(unittest_seastar_perfcounters) target_link_libraries(unittest_seastar_perfcounters crimson) +add_executable(unittest_seastar_lru + test_lru.cc) +add_ceph_unittest(unittest_seastar_lru) +target_link_libraries(unittest_seastar_lru crimson GTest::Main) + diff --git a/src/test/crimson/test_lru.cc b/src/test/crimson/test_lru.cc new file mode 100644 index 00000000000..40ab415393e --- /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: -- 2.39.5