From fc8f8855e4e87330f7f6d3b4e4ae05a640af7ec4 Mon Sep 17 00:00:00 2001 From: Samuel Just Date: Thu, 3 Oct 2019 22:22:09 -0700 Subject: [PATCH] common/: introduce intrusive_lru Signed-off-by: Samuel Just --- src/common/intrusive_lru.h | 178 ++++++++++++++++++++++++++ src/test/common/CMakeLists.txt | 7 + src/test/common/test_intrusive_lru.cc | 149 +++++++++++++++++++++ 3 files changed, 334 insertions(+) create mode 100644 src/common/intrusive_lru.h create mode 100644 src/test/common/test_intrusive_lru.cc diff --git a/src/common/intrusive_lru.h b/src/common/intrusive_lru.h new file mode 100644 index 00000000000..31bbde38e65 --- /dev/null +++ b/src/common/intrusive_lru.h @@ -0,0 +1,178 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#pragma once + +#include +#include +#include + +namespace ceph::common { + +/** + * intrusive_lru: lru implementation with embedded map and list hook + * + * Note, this implementation currently is entirely thread-unsafe. + */ + +template +struct intrusive_lru_config { + using key_type = K; + using value_type = V; + using key_of_value = VToK; +}; + +template +class intrusive_lru; + +template +class intrusive_lru_base; + +template +void intrusive_ptr_add_ref(intrusive_lru_base *p); + +template +void intrusive_ptr_release(intrusive_lru_base *p); + + +template +class intrusive_lru_base { + unsigned use_count = 0; + + // null if unreferenced + intrusive_lru *lru = nullptr; + +public: + boost::intrusive::set_member_hook<> set_hook; + boost::intrusive::list_member_hook<> list_hook; + + using Ref = boost::intrusive_ptr; + using lru_t = intrusive_lru; + + friend intrusive_lru; + friend void intrusive_ptr_add_ref<>(intrusive_lru_base *); + friend void intrusive_ptr_release<>(intrusive_lru_base *); + + virtual ~intrusive_lru_base() {} +}; + +template +class intrusive_lru { + using base_t = intrusive_lru_base; + using K = typename Config::key_type; + using T = typename Config::value_type; + using TRef = typename base_t::Ref; + + using lru_set_option_t = boost::intrusive::member_hook< + base_t, + boost::intrusive::set_member_hook<>, + &base_t::set_hook>; + + using VToK = typename Config::key_of_value; + struct VToKWrapped { + using type = typename VToK::type; + const type &operator()(const base_t &obc) { + return VToK()(static_cast(obc)); + } + }; + using lru_set_t = boost::intrusive::set< + base_t, + lru_set_option_t, + boost::intrusive::key_of_value + >; + lru_set_t lru_set; + + using lru_list_t = boost::intrusive::list< + base_t, + boost::intrusive::member_hook< + base_t, + boost::intrusive::list_member_hook<>, + &base_t::list_hook>>; + lru_list_t unreferenced_list; + + size_t lru_target_size = 0; + + void evict() { + while (!unreferenced_list.empty() && + lru_set.size() > lru_target_size) { + auto &b = unreferenced_list.front(); + assert(!b.lru); + unreferenced_list.pop_front(); + lru_set.erase_and_dispose( + lru_set.iterator_to(b), + [](auto *p) { delete p; } + ); + } + } + + void access(base_t &b) { + if (b.lru) + return; + unreferenced_list.erase(lru_list_t::s_iterator_to(b)); + b.lru = this; + } + + void insert(base_t &b) { + assert(!b.lru); + lru_set.insert(b); + b.lru = this; + evict(); + } + + void unreferenced(base_t &b) { + assert(b.lru); + unreferenced_list.push_back(b); + b.lru = nullptr; + evict(); + } + +public: + /** + * Returns the TRef corresponding to k if it exists or + * creates it otherwise. Return is: + * std::pair(reference_to_val, found) + */ + std::pair get_or_create(const K &k) { + typename lru_set_t::insert_commit_data icd; + auto [iter, missing] = lru_set.insert_check( + k, + icd); + if (missing) { + auto ret = new T(k); + lru_set.insert_commit(*ret, icd); + insert(*ret); + return {TRef(ret), false}; + } else { + access(*iter); + return {TRef(static_cast(&*iter)), true}; + } + } + + void set_target_size(size_t target_size) { + lru_target_size = target_size; + evict(); + } + + friend void intrusive_ptr_add_ref<>(intrusive_lru_base *); + friend void intrusive_ptr_release<>(intrusive_lru_base *); +}; + +template +void intrusive_ptr_add_ref(intrusive_lru_base *p) { + assert(p); + assert(p->lru); + p->use_count++; +} + +template +void intrusive_ptr_release(intrusive_lru_base *p) { + assert(p); + assert(p->use_count > 0); + --p->use_count; + if (p->use_count == 0) { + p->lru->unreferenced(*p); + } +} + + +} diff --git a/src/test/common/CMakeLists.txt b/src/test/common/CMakeLists.txt index a3074d4319f..f5c23649d21 100644 --- a/src/test/common/CMakeLists.txt +++ b/src/test/common/CMakeLists.txt @@ -151,6 +151,13 @@ add_executable(unittest_lru add_ceph_unittest(unittest_lru) target_link_libraries(unittest_lru ceph-common) +# unittest_intrusive_lru +add_executable(unittest_intrusive_lru + test_intrusive_lru.cc + ) +add_ceph_unittest(unittest_intrusive_lru) +target_link_libraries(unittest_intrusive_lru ceph-common) + # unittest_crc32c add_executable(unittest_crc32c test_crc32c.cc diff --git a/src/test/common/test_intrusive_lru.cc b/src/test/common/test_intrusive_lru.cc new file mode 100644 index 00000000000..f242bdba160 --- /dev/null +++ b/src/test/common/test_intrusive_lru.cc @@ -0,0 +1,149 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include +#include "gtest/gtest.h" +#include "common/intrusive_lru.h" + +template +struct item_to_unsigned { + using type = unsigned; + const type &operator()(const TestLRUItem &item) { + return item.key; + } +}; + +struct TestLRUItem : public ceph::common::intrusive_lru_base< + ceph::common::intrusive_lru_config< + unsigned, TestLRUItem, item_to_unsigned>> { + unsigned key = 0; + int value = 0; + bool seen = false; + + TestLRUItem(unsigned key) : key(key) {} +}; + +class LRUTest : public TestLRUItem::lru_t { +public: + auto add(unsigned int key, int value) { + auto [ref, key_existed] = get_or_create(key); + if (!key_existed) { + ref->value = value; + } + return std::pair(ref, key_existed); + } +}; + +TEST(LRU, add_immediate_evict) { + LRUTest cache; + unsigned int key = 1; + int value1 = 2; + int value2 = 3; + { + auto [ref, existed] = cache.add(key, value1); + ASSERT_TRUE(ref); + ASSERT_EQ(value1, ref->value); + ASSERT_FALSE(existed); + } + { + auto [ref2, existed] = cache.add(key, value2); + ASSERT_EQ(value2, ref2->value); + ASSERT_FALSE(existed); + } +} + +TEST(LRU, lookup_lru_size) { + LRUTest cache; + int key = 1; + int value = 1; + cache.set_target_size(1); + { + auto [ref, existed] = cache.add(key, value); + ASSERT_TRUE(ref); + ASSERT_FALSE(existed); + } + { + auto [ref, existed] = cache.add(key, value); + ASSERT_TRUE(ref); + ASSERT_TRUE(existed); + } + cache.set_target_size(0); + auto [ref2, existed2] = cache.add(key, value); + ASSERT_TRUE(ref2); + ASSERT_FALSE(existed2); + { + auto [ref, existed] = cache.add(key, value); + ASSERT_TRUE(ref); + ASSERT_TRUE(existed); + } +} + +TEST(LRU, eviction) { + const unsigned SIZE = 3; + LRUTest cache; + cache.set_target_size(SIZE); + + for (unsigned i = 0; i < SIZE; ++i) { + auto [ref, existed] = cache.add(i, i); + ASSERT_TRUE(ref && !existed); + } + + { + auto [ref, existed] = cache.add(0, 0); + ASSERT_TRUE(ref && existed); + } + + for (unsigned i = SIZE; i < (2*SIZE) - 1; ++i) { + auto [ref, existed] = cache.add(i, i); + ASSERT_TRUE(ref && !existed); + } + + { + auto [ref, existed] = cache.add(0, 0); + ASSERT_TRUE(ref && existed); + } + + for (unsigned i = 1; i < SIZE; ++i) { + auto [ref, existed] = cache.add(i, i); + ASSERT_TRUE(ref && !existed); + } +} + +TEST(LRU, eviction_live_ref) { + const unsigned SIZE = 3; + LRUTest cache; + cache.set_target_size(SIZE); + + auto [live_ref, existed2] = cache.add(1, 1); + ASSERT_TRUE(live_ref && !existed2); + + for (unsigned i = 0; i < SIZE; ++i) { + auto [ref, existed] = cache.add(i, i); + ASSERT_TRUE(ref); + if (i == 1) { + ASSERT_TRUE(existed); + } else { + ASSERT_FALSE(existed); + } + } + + { + auto [ref, existed] = cache.add(0, 0); + ASSERT_TRUE(ref && existed); + } + + for (unsigned i = SIZE; i < (2*SIZE) - 1; ++i) { + auto [ref, existed] = cache.add(i, i); + ASSERT_TRUE(ref && !existed); + } + + for (unsigned i = 0; i < SIZE; ++i) { + auto [ref, existed] = cache.add(i, i); + ASSERT_TRUE(ref); + if (i == 1) { + ASSERT_TRUE(existed); + } else { + ASSERT_FALSE(existed); + } + } +} -- 2.39.5