ceph/src/common/intrusive_lru.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #pragma once
   5
   6 #include <boost/intrusive_ptr.hpp>
   7 #include <boost/intrusive/set.hpp>
   8 #include <boost/intrusive/list.hpp>
   9
  10 namespace ceph::common {
  11
  12 /**
  13  * intrusive_lru: lru implementation with embedded map and list hook
  14  *
  15  * Note, this implementation currently is entirely thread-unsafe.
  16  */
  17
  18 template <typename K, typename V, typename VToK>
  19 struct intrusive_lru_config {
  20   using key_type = K;
  21   using value_type = V;
  22   using key_of_value = VToK;
  23 };
  24
  25 template <typename Config>
  26 class intrusive_lru;
  27
  28 template <typename Config>
  29 class intrusive_lru_base;
  30
  31 template <typename Config>
  32 void intrusive_ptr_add_ref(intrusive_lru_base<Config> *p);
  33
  34 template <typename Config>
  35 void intrusive_ptr_release(intrusive_lru_base<Config> *p);
  36
  37
  38 template <typename Config>
  39 class intrusive_lru_base {
  40   unsigned use_count = 0;
  41
  42   // null if unreferenced
  43   intrusive_lru<Config> *lru = nullptr;
  44
  45 public:
  46   boost::intrusive::set_member_hook<> set_hook;
  47   boost::intrusive::list_member_hook<> list_hook;
  48
  49   using Ref = boost::intrusive_ptr<typename Config::value_type>;
  50   using lru_t = intrusive_lru<Config>;
  51
  52   friend intrusive_lru<Config>;
  53   friend void intrusive_ptr_add_ref<>(intrusive_lru_base<Config> *);
  54   friend void intrusive_ptr_release<>(intrusive_lru_base<Config> *);
  55
  56   virtual ~intrusive_lru_base() {}
  57 };
  58
  59 template <typename Config>
  60 class intrusive_lru {
  61   using base_t = intrusive_lru_base<Config>;
  62   using K = typename Config::key_type;
  63   using T = typename Config::value_type;
  64   using TRef = typename base_t::Ref;
  65
  66   using lru_set_option_t = boost::intrusive::member_hook<
  67     base_t,
  68     boost::intrusive::set_member_hook<>,
  69     &base_t::set_hook>;
  70
  71   using VToK = typename Config::key_of_value;
  72   struct VToKWrapped {
  73     using type = typename VToK::type;
  74     const type &operator()(const base_t &obc) {
  75       return VToK()(static_cast<const T&>(obc));
  76     }
  77   };
  78   using lru_set_t = boost::intrusive::set<
  79     base_t,
  80     lru_set_option_t,
  81     boost::intrusive::key_of_value<VToKWrapped>
  82     >;
  83   lru_set_t lru_set;
  84
  85   using lru_list_t = boost::intrusive::list<
  86     base_t,
  87     boost::intrusive::member_hook<
  88       base_t,
  89       boost::intrusive::list_member_hook<>,
  90       &base_t::list_hook>>;
  91   lru_list_t unreferenced_list;
  92
  93   size_t lru_target_size = 0;
  94
  95   void evict() {
  96     while (!unreferenced_list.empty() &&
  97            lru_set.size() > lru_target_size) {
  98       auto &b = unreferenced_list.front();
  99       assert(!b.lru);
 100       unreferenced_list.pop_front();
 101       lru_set.erase_and_dispose(
 102         lru_set.iterator_to(b),
 103         [](auto *p) { delete p; }
 104       );
 105     }
 106   }
 107
 108   void access(base_t &b) {
 109     if (b.lru)
 110       return;
 111     unreferenced_list.erase(lru_list_t::s_iterator_to(b));
 112     b.lru = this;
 113   }
 114
 115   void insert(base_t &b) {
 116     assert(!b.lru);
 117     lru_set.insert(b);
 118     b.lru = this;
 119     evict();
 120   }
 121
 122   void unreferenced(base_t &b) {
 123     assert(b.lru);
 124     unreferenced_list.push_back(b);
 125     b.lru = nullptr;
 126     evict();
 127   }
 128
 129 public:
 130   /**
 131    * Returns the TRef corresponding to k if it exists or
 132    * creates it otherwise.  Return is:
 133    * std::pair(reference_to_val, found)
 134    */
 135   std::pair<TRef, bool> get_or_create(const K &k) {
 136     typename lru_set_t::insert_commit_data icd;
 137     auto [iter, missing] = lru_set.insert_check(
 138       k,
 139       icd);
 140     if (missing) {
 141       auto ret = new T(k);
 142       lru_set.insert_commit(*ret, icd);
 143       insert(*ret);
 144       return {TRef(ret), false};
 145     } else {
 146       access(*iter);
 147       return {TRef(static_cast<T*>(&*iter)), true};
 148     }
 149   }
 150
 151   void set_target_size(size_t target_size) {
 152     lru_target_size = target_size;
 153     evict();
 154   }
 155
 156   friend void intrusive_ptr_add_ref<>(intrusive_lru_base<Config> *);
 157   friend void intrusive_ptr_release<>(intrusive_lru_base<Config> *);
 158 };
 159
 160 template <typename Config>
 161 void intrusive_ptr_add_ref(intrusive_lru_base<Config> *p) {
 162   assert(p);
 163   assert(p->lru);
 164   p->use_count++;
 165 }
 166
 167 template <typename Config>
 168 void intrusive_ptr_release(intrusive_lru_base<Config> *p) {
 169   assert(p);
 170   assert(p->use_count > 0);
 171   --p->use_count;
 172   if (p->use_count == 0) {
 173     p->lru->unreferenced(*p);
 174   }
 175 }
 176
 177
 178 }