--- /dev/null
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+/*
+ * Copyright (C) 2015 CohortFS, LLC.
+ *
+ * This is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1, as published by the Free Software
+ * Foundation. See file COPYING.
+ *
+ */
+
+#ifndef COHORT_LRU_H
+#define COHORT_LRU_H
+
+#include <boost/intrusive/list.hpp>
+#include <boost/intrusive/slist.hpp>
+
+#include "common/likely.h"
+
+#ifndef CACHE_LINE_SIZE
+#define CACHE_LINE_SIZE 64 /* XXX arch-specific define */
+#endif
+#define CACHE_PAD(_n) char __pad ## _n [CACHE_LINE_SIZE]
+
+namespace cohort {
+
+ namespace lru {
+
+ namespace bi = boost::intrusive;
+
+ /* public flag values */
+ constexpr uint32_t FLAG_NONE = 0x0000;
+ constexpr uint32_t FLAG_INITIAL = 0x0001;
+
+ enum class Edge : std::uint8_t
+ {
+ MRU = 0,
+ LRU
+ };
+
+ typedef bi::link_mode<bi::safe_link> link_mode;
+
+ class Object
+ {
+ private:
+ uint32_t lru_flags;
+ std::atomic<uint32_t> lru_refcnt;
+ std::atomic<uint32_t> lru_adj;
+ bi::list_member_hook< link_mode > lru_hook;
+
+ typedef bi::list<Object,
+ bi::member_hook<
+ Object, bi::list_member_hook< link_mode >,
+ &Object::lru_hook >,
+ bi::constant_time_size<true>> Queue;
+
+ bi::slist_member_hook< link_mode > q2_hook;
+
+ typedef bi::slist<Object,
+ bi::member_hook<
+ Object, bi::slist_member_hook< link_mode >,
+ &Object::q2_hook >,
+ bi::constant_time_size<true>> Queue2;
+
+ public:
+
+ Object() : lru_flags(FLAG_NONE), lru_refcnt(0), lru_adj(0) {}
+
+ uint32_t get_refcnt() const { return lru_refcnt; }
+
+ virtual bool reclaim() = 0;
+
+ virtual ~Object() {}
+
+ private:
+ template <typename LK>
+ friend class LRU;
+
+ template <typename T, typename TTree, typename CLT, typename CEQ,
+ typename K, typename LK>
+ friend class TreeX;
+ };
+
+ /* allocator & recycler interface (create or re-use LRU objects) */
+ class ObjectFactory
+ {
+ public:
+ virtual Object* alloc(void) = 0;
+ virtual void recycle(Object*) = 0;
+ virtual ~ObjectFactory() {};
+ };
+
+ template <typename LK>
+ class LRU
+ {
+ private:
+
+ struct Lane {
+ LK lock;
+ Object::Queue q;
+ // Object::Queue pinned; /* placeholder for possible expansion */
+ CACHE_PAD(0);
+ Lane() {}
+ };
+
+ Lane *qlane;
+ int n_lanes;
+ std::atomic<uint32_t> evict_lane;
+ const uint32_t lane_hiwat;
+
+ static constexpr uint32_t lru_adj_modulus = 5;
+
+ static constexpr uint32_t SENTINEL_REFCNT = 1;
+
+ /* internal flag values */
+ static constexpr uint32_t FLAG_INLRU = 0x0001;
+ static constexpr uint32_t FLAG_PINNED = 0x0002; // possible future use
+ static constexpr uint32_t FLAG_EVICTING = 0x0004;
+
+ Lane& lane_of(void* addr) {
+ return qlane[(uint64_t)(addr) % n_lanes];
+ }
+
+ uint32_t next_evict_lane() {
+ return (evict_lane++ % n_lanes);
+ }
+
+ bool can_reclaim(Object* o) {
+ return ((o->lru_refcnt == SENTINEL_REFCNT) &&
+ (!(o->lru_flags & FLAG_EVICTING)));
+ }
+
+ Object* evict_block() {
+ uint32_t lane_ix = next_evict_lane();
+ for (int ix = 0; ix < n_lanes; ++ix,
+ lane_ix = next_evict_lane()) {
+ Lane& lane = qlane[lane_ix];
+ lane.lock.lock();
+ /* if object at LRU has refcnt==1, it may be reclaimable */
+ Object* o = &(lane.q.back());
+ if (can_reclaim(o)) {
+ ++(o->lru_refcnt);
+ o->lru_flags |= FLAG_EVICTING;
+ lane.lock.unlock();
+ if (o->reclaim()) {
+ lane.lock.lock();
+ --(o->lru_refcnt);
+ /* assertions that o state has not changed across
+ * relock */
+ assert(o->lru_refcnt == SENTINEL_REFCNT);
+ assert(o->lru_flags & FLAG_INLRU);
+ Object::Queue::iterator it =
+ Object::Queue::s_iterator_to(*o);
+ lane.q.erase(it);
+ lane.lock.unlock();
+ return o;
+ } else {
+ // XXX can't make unreachable (means what?)
+ --(o->lru_refcnt);
+ o->lru_flags &= ~FLAG_EVICTING;
+ /* unlock in next block */
+ }
+ } /* can_reclaim(o) */
+ lane.lock.unlock();
+ } /* each lane */
+ return nullptr;
+ } /* evict_block */
+
+ public:
+
+ LRU(int lanes, uint32_t _hiwat)
+ : n_lanes(lanes), evict_lane(0), lane_hiwat(_hiwat)
+ {
+ assert(n_lanes > 0);
+ qlane = new Lane[n_lanes];
+ }
+
+ ~LRU() { delete[] qlane; }
+
+ bool ref(Object* o, uint32_t flags) {
+ ++(o->lru_refcnt);
+ if (flags & FLAG_INITIAL) {
+ if ((++(o->lru_adj) % lru_adj_modulus) == 0) {
+ Lane& lane = lane_of(o);
+ lane.lock.lock();
+ /* move to MRU */
+ Object::Queue::iterator it =
+ Object::Queue::s_iterator_to(*o);
+ lane.q.erase(it);
+ lane.q.push_front(*o);
+ lane.lock.unlock();
+ } /* adj */
+ } /* initial ref */
+ return true;
+ } /* ref */
+
+ void unref(Object* o, uint32_t flags) {
+ uint32_t refcnt = --(o->lru_refcnt);
+ Object* tdo = nullptr;
+ if (unlikely(refcnt == 0)) {
+ Lane& lane = lane_of(o);
+ lane.lock.lock();
+ refcnt = o->lru_refcnt.load();
+ if (unlikely(refcnt == 0)) {
+ Object::Queue::iterator it =
+ Object::Queue::s_iterator_to(*o);
+ lane.q.erase(it);
+ tdo = o;
+ }
+ lane.lock.unlock();
+ } else if (unlikely(refcnt == SENTINEL_REFCNT)) {
+ Lane& lane = lane_of(o);
+ lane.lock.lock();
+ refcnt = o->lru_refcnt.load();
+ if (likely(refcnt == SENTINEL_REFCNT)) {
+ /* move to LRU */
+ Object::Queue::iterator it =
+ Object::Queue::s_iterator_to(*o);
+ lane.q.erase(it);
+ /* hiwat check */
+ if (lane.q.size() > lane_hiwat) {
+ tdo = o;
+ } else {
+ lane.q.push_back(*o);
+ }
+ }
+ lane.lock.unlock();
+ }
+ /* unref out-of-line && !LOCKED */
+ if (tdo)
+ delete tdo;
+ } /* unref */
+
+ Object* insert(ObjectFactory* fac, Edge edge, uint32_t flags) {
+ /* use supplied functor to re-use an evicted object, or
+ * allocate a new one of the descendant type */
+ Object* o = evict_block();
+ if (o)
+ fac->recycle(o); /* recycle existing object */
+ else
+ o = fac->alloc(); /* get a new one */
+
+ o->lru_flags = FLAG_INLRU;
+
+ Lane& lane = lane_of(o);
+ lane.lock.lock();
+ switch (edge) {
+ case Edge::MRU:
+ lane.q.push_front(*o);
+ break;
+ case Edge::LRU:
+ lane.q.push_back(*o);
+ break;
+ default:
+ abort();
+ break;
+ }
+ if (flags & FLAG_INITIAL)
+ o->lru_refcnt += 2; /* sentinel ref + initial */
+ else
+ ++(o->lru_refcnt); /* sentinel */
+ lane.lock.unlock();
+ return o;
+ } /* insert */
+
+ };
+
+ template <typename T, typename TTree, typename CLT, typename CEQ,
+ typename K, typename LK>
+ class TreeX
+ {
+ public:
+
+ static constexpr uint32_t FLAG_NONE = 0x0000;
+ static constexpr uint32_t FLAG_LOCK = 0x0001;
+ static constexpr uint32_t FLAG_UNLOCK = 0x0002;
+ static constexpr uint32_t FLAG_UNLOCK_ON_MISS = 0x0004;
+
+ typedef T value_type;
+ typedef TTree container_type;
+ typedef typename TTree::iterator iterator;
+ typedef std::pair<iterator, bool> check_result;
+ typedef typename TTree::insert_commit_data insert_commit_data;
+ int n_part;
+ int csz;
+
+ typedef std::unique_lock<LK> unique_lock;
+
+ struct Partition {
+ LK lock;
+ TTree tr;
+ T** cache;
+ int csz;
+ CACHE_PAD(0);
+
+ Partition() : tr(), cache(nullptr), csz(0) {}
+
+ ~Partition() {
+ if (csz)
+ ::operator delete(cache);
+ }
+ };
+
+ struct Latch {
+ Partition* p;
+ LK* lock;
+ insert_commit_data commit_data;
+
+ Latch() : p(nullptr), lock(nullptr) {}
+ };
+
+ Partition& partition_of_scalar(uint64_t x) {
+ return part[x % n_part];
+ }
+
+ Partition& get(uint8_t x) {
+ return part[x];
+ }
+
+ Partition*& get() {
+ return part;
+ }
+
+ void lock() {
+ std::for_each(locks.begin(), locks.end(),
+ [](LK* lk){ lk->lock(); });
+ }
+
+ void unlock() {
+ std::for_each(locks.begin(), locks.end(),
+ [](LK* lk){ lk->unlock(); });
+ }
+
+ TreeX(int n_part=1, int csz=127) : n_part(n_part), csz(csz) {
+ assert(n_part > 0);
+ part = new Partition[n_part];
+ for (int ix = 0; ix < n_part; ++ix) {
+ Partition& p = part[ix];
+ if (csz) {
+ p.csz = csz;
+ p.cache = (T**) ::operator new(csz * sizeof(T*));
+ memset(p.cache, 0, csz * sizeof(T*));
+ }
+ locks.push_back(&p.lock);
+ }
+ }
+
+ ~TreeX() {
+ delete[] part;
+ }
+
+ T* find(uint64_t hk, const K& k, uint32_t flags) {
+ T* v;
+ Latch lat;
+ uint32_t slot = 0;
+ lat.p = &(partition_of_scalar(hk));
+ if (flags & FLAG_LOCK) {
+ lat.lock = &lat.p->lock;
+ lat.lock->lock();
+ }
+ if (csz) { /* template specialize? */
+ slot = hk % csz;
+ v = lat.p->cache[slot];
+ if (v) {
+ if (CEQ()(*v, k)) {
+ if (flags & FLAG_LOCK)
+ lat.lock->unlock();
+ return v;
+ }
+ v = nullptr;
+ }
+ } else {
+ v = nullptr;
+ }
+ iterator it = lat.p->tr.find(k, CLT());
+ if (it != lat.p->tr.end()){
+ v = &(*(it));
+ if (csz) {
+ /* fill cache slot at hk */
+ lat.p->cache[slot] = v;
+ }
+ }
+ if (flags & FLAG_LOCK)
+ lat.lock->unlock();
+ return v;
+ } /* find */
+
+ T* find_latch(uint64_t hk, const K& k, Latch& lat,
+ uint32_t flags) {
+ uint32_t slot = 0;
+ T* v;
+ lat.p = &(partition_of_scalar(hk));
+ lat.lock = &lat.p->lock;
+ if (flags & FLAG_LOCK)
+ lat.lock->lock();
+ if (csz) { /* template specialize? */
+ slot = hk % csz;
+ v = lat.p->cache[slot];
+ if (v) {
+ if (CEQ()(*v, k)) {
+ if ((flags & FLAG_LOCK) && (flags & FLAG_UNLOCK))
+ lat.lock->unlock();
+ return v;
+ }
+ v = nullptr;
+ }
+ } else {
+ v = nullptr;
+ }
+ check_result r = lat.p->tr.insert_unique_check(
+ k, CLT(), lat.commit_data);
+ if (! r.second /* !insertable (i.e., !found) */) {
+ v = &(*(r.first));
+ if (csz) {
+ /* fill cache slot at hk */
+ lat.p->cache[slot] = v;
+ }
+ }
+ if ((flags & FLAG_LOCK) && (flags & FLAG_UNLOCK))
+ lat.lock->unlock();
+ return v;
+ } /* find_latch */
+
+ void insert_latched(T* v, Latch& lat, uint32_t flags) {
+ (void) lat.p->tr.insert_unique_commit(*v, lat.commit_data);
+ if (flags & FLAG_UNLOCK)
+ lat.lock->unlock();
+ } /* insert_latched */
+
+ void insert(uint64_t hk, T* v, uint32_t flags) {
+ Partition& p = partition_of_scalar(hk);
+ if (flags & FLAG_LOCK)
+ p.lock.lock();
+ p.tr.insert_unique(*v);
+ if (flags & FLAG_LOCK)
+ p.lock.unlock();
+ } /* insert */
+
+ void remove(uint64_t hk, T* v, uint32_t flags) {
+ Partition& p = partition_of_scalar(hk);
+ iterator it = TTree::s_iterator_to(*v);
+ if (flags & FLAG_LOCK)
+ p.lock.lock();
+ p.tr.erase(it);
+ if (csz) { /* template specialize? */
+ uint32_t slot = hk % csz;
+ T* v2 = p.cache[slot];
+ /* we are intrusive, just compare addresses */
+ if (v == v2)
+ p.cache[slot] = nullptr;
+ }
+ if (flags & FLAG_LOCK)
+ p.lock.unlock();
+ } /* remove */
+
+ void drain(std::function<void(T*)> uref,
+ uint32_t flags = FLAG_NONE) {
+ /* clear a table, call supplied function on
+ * each element found (e.g., retuns sentinel
+ * references) */
+ Object::Queue2 drain_q;
+ for (int t_ix = 0; t_ix < n_part; ++t_ix) {
+ Partition& p = part[t_ix];
+ if (flags & FLAG_LOCK) /* LOCKED */
+ p.lock.lock();
+ while (p.tr.size() > 0) {
+ iterator it = p.tr.begin();
+ T* v = &(*it);
+ p.tr.erase(it);
+ drain_q.push_front(*v);
+ }
+ if (flags & FLAG_LOCK) /* we locked it, !LOCKED */
+ p.lock.unlock();
+ } /* each partition */
+ /* unref out-of-line && !LOCKED */
+ while (drain_q.size() > 0) {
+ Object::Queue2::iterator it = drain_q.begin();
+ T* v = static_cast<T*>(&(*it));
+ drain_q.erase(it); /* must precede uref(v) in safe_link mode */
+ uref(v);
+ }
+ } /* drain */
+
+ private:
+ Partition *part;
+ std::vector<LK*> locks;
+ };
+
+ } /* namespace LRU */
+} /* namespace cohort */
+
+#endif /* COHORT_LRU_H */
Code Review / stor4nfv.git / blobdiff