X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=src%2Fceph%2Fsrc%2Fcommon%2Fcohort_lru.h;fp=src%2Fceph%2Fsrc%2Fcommon%2Fcohort_lru.h;h=6c8264a5efd0c21ba071736fa872027e8b4dbfca;hb=812ff6ca9fcd3e629e49d4328905f33eee8ca3f5;hp=0000000000000000000000000000000000000000;hpb=15280273faafb77777eab341909a3f495cf248d9;p=stor4nfv.git diff --git a/src/ceph/src/common/cohort_lru.h b/src/ceph/src/common/cohort_lru.h new file mode 100644 index 0000000..6c8264a --- /dev/null +++ b/src/ceph/src/common/cohort_lru.h @@ -0,0 +1,493 @@ +// -*- 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 +#include + +#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 link_mode; + + class Object + { + private: + uint32_t lru_flags; + std::atomic lru_refcnt; + std::atomic lru_adj; + bi::list_member_hook< link_mode > lru_hook; + + typedef bi::list, + &Object::lru_hook >, + bi::constant_time_size> Queue; + + bi::slist_member_hook< link_mode > q2_hook; + + typedef bi::slist, + &Object::q2_hook >, + bi::constant_time_size> 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 + friend class LRU; + + template + 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 + 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 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 + 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 check_result; + typedef typename TTree::insert_commit_data insert_commit_data; + int n_part; + int csz; + + typedef std::unique_lock 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 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(&(*it)); + drain_q.erase(it); /* must precede uref(v) in safe_link mode */ + uref(v); + } + } /* drain */ + + private: + Partition *part; + std::vector locks; + }; + + } /* namespace LRU */ +} /* namespace cohort */ + +#endif /* COHORT_LRU_H */