--- /dev/null
+// -*- 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) 2004-2006 Sage Weil <sage@newdream.net>
+ *
+ * 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 CEPH_SHAREDCACHE_H
+#define CEPH_SHAREDCACHE_H
+
+#include <map>
+#include <list>
+#include "common/Mutex.h"
+#include "common/Cond.h"
+#include "include/unordered_map.h"
+
+// re-include our assert to clobber the system one; fix dout:
+#include "include/assert.h"
+
+template <class K, class V, class C = std::less<K>, class H = std::hash<K> >
+class SharedLRU {
+ CephContext *cct;
+ typedef ceph::shared_ptr<V> VPtr;
+ typedef ceph::weak_ptr<V> WeakVPtr;
+ Mutex lock;
+ size_t max_size;
+ Cond cond;
+ unsigned size;
+public:
+ int waiting;
+private:
+ ceph::unordered_map<K, typename list<pair<K, VPtr> >::iterator, H> contents;
+ list<pair<K, VPtr> > lru;
+
+ map<K, pair<WeakVPtr, V*>, C> weak_refs;
+
+ void trim_cache(list<VPtr> *to_release) {
+ while (size > max_size) {
+ to_release->push_back(lru.back().second);
+ lru_remove(lru.back().first);
+ }
+ }
+
+ void lru_remove(const K& key) {
+ typename ceph::unordered_map<K, typename list<pair<K, VPtr> >::iterator, H>::iterator i =
+ contents.find(key);
+ if (i == contents.end())
+ return;
+ lru.erase(i->second);
+ --size;
+ contents.erase(i);
+ }
+
+ void lru_add(const K& key, const VPtr& val, list<VPtr> *to_release) {
+ typename ceph::unordered_map<K, typename list<pair<K, VPtr> >::iterator, H>::iterator i =
+ contents.find(key);
+ if (i != contents.end()) {
+ lru.splice(lru.begin(), lru, i->second);
+ } else {
+ ++size;
+ lru.push_front(make_pair(key, val));
+ contents[key] = lru.begin();
+ trim_cache(to_release);
+ }
+ }
+
+ void remove(const K& key, V *valptr) {
+ Mutex::Locker l(lock);
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
+ if (i != weak_refs.end() && i->second.second == valptr) {
+ weak_refs.erase(i);
+ }
+ cond.Signal();
+ }
+
+ class Cleanup {
+ public:
+ SharedLRU<K, V, C> *cache;
+ K key;
+ Cleanup(SharedLRU<K, V, C> *cache, K key) : cache(cache), key(key) {}
+ void operator()(V *ptr) {
+ cache->remove(key, ptr);
+ delete ptr;
+ }
+ };
+
+public:
+ SharedLRU(CephContext *cct = NULL, size_t max_size = 20)
+ : cct(cct), lock("SharedLRU::lock"), max_size(max_size),
+ size(0), waiting(0) {
+ contents.rehash(max_size);
+ }
+
+ ~SharedLRU() {
+ contents.clear();
+ lru.clear();
+ if (!weak_refs.empty()) {
+ lderr(cct) << "leaked refs:\n";
+ dump_weak_refs(*_dout);
+ *_dout << dendl;
+ assert(weak_refs.empty());
+ }
+ }
+
+ /// adjust container comparator (for purposes of get_next sort order)
+ void reset_comparator(C comp) {
+ // get_next uses weak_refs; that's the only container we need to
+ // reorder.
+ map<K, pair<WeakVPtr, V*>, C> temp;
+
+ Mutex::Locker l(lock);
+ temp.swap(weak_refs);
+
+ // reconstruct with new comparator
+ weak_refs = map<K, pair<WeakVPtr, V*>, C>(comp);
+ weak_refs.insert(temp.begin(), temp.end());
+ }
+
+ C get_comparator() {
+ return weak_refs.key_comp();
+ }
+
+ void set_cct(CephContext *c) {
+ cct = c;
+ }
+
+ void dump_weak_refs() {
+ lderr(cct) << "leaked refs:\n";
+ dump_weak_refs(*_dout);
+ *_dout << dendl;
+ }
+
+ void dump_weak_refs(ostream& out) {
+ for (typename map<K, pair<WeakVPtr, V*>, C>::iterator p = weak_refs.begin();
+ p != weak_refs.end();
+ ++p) {
+ out << __func__ << " " << this << " weak_refs: "
+ << p->first << " = " << p->second.second
+ << " with " << p->second.first.use_count() << " refs"
+ << std::endl;
+ }
+ }
+
+ //clear all strong reference from the lru.
+ void clear() {
+ while (true) {
+ VPtr val; // release any ref we have after we drop the lock
+ Mutex::Locker l(lock);
+ if (size == 0)
+ break;
+
+ val = lru.back().second;
+ lru_remove(lru.back().first);
+ }
+ }
+
+ void clear(const K& key) {
+ VPtr val; // release any ref we have after we drop the lock
+ {
+ Mutex::Locker l(lock);
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
+ if (i != weak_refs.end()) {
+ val = i->second.first.lock();
+ }
+ lru_remove(key);
+ }
+ }
+
+ void purge(const K &key) {
+ VPtr val; // release any ref we have after we drop the lock
+ {
+ Mutex::Locker l(lock);
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
+ if (i != weak_refs.end()) {
+ val = i->second.first.lock();
+ weak_refs.erase(i);
+ }
+ lru_remove(key);
+ }
+ }
+
+ void set_size(size_t new_size) {
+ list<VPtr> to_release;
+ {
+ Mutex::Locker l(lock);
+ max_size = new_size;
+ trim_cache(&to_release);
+ }
+ }
+
+ // Returns K key s.t. key <= k for all currently cached k,v
+ K cached_key_lower_bound() {
+ Mutex::Locker l(lock);
+ return weak_refs.begin()->first;
+ }
+
+ VPtr lower_bound(const K& key) {
+ VPtr val;
+ list<VPtr> to_release;
+ {
+ Mutex::Locker l(lock);
+ ++waiting;
+ bool retry = false;
+ do {
+ retry = false;
+ if (weak_refs.empty())
+ break;
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator i =
+ weak_refs.lower_bound(key);
+ if (i == weak_refs.end())
+ --i;
+ val = i->second.first.lock();
+ if (val) {
+ lru_add(i->first, val, &to_release);
+ } else {
+ retry = true;
+ }
+ if (retry)
+ cond.Wait(lock);
+ } while (retry);
+ --waiting;
+ }
+ return val;
+ }
+ bool get_next(const K &key, pair<K, VPtr> *next) {
+ pair<K, VPtr> r;
+ {
+ Mutex::Locker l(lock);
+ VPtr next_val;
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.upper_bound(key);
+
+ while (i != weak_refs.end() &&
+ !(next_val = i->second.first.lock()))
+ ++i;
+
+ if (i == weak_refs.end())
+ return false;
+
+ if (next)
+ r = make_pair(i->first, next_val);
+ }
+ if (next)
+ *next = r;
+ return true;
+ }
+ bool get_next(const K &key, pair<K, V> *next) {
+ pair<K, VPtr> r;
+ bool found = get_next(key, &r);
+ if (!found || !next)
+ return found;
+ next->first = r.first;
+ assert(r.second);
+ next->second = *(r.second);
+ return found;
+ }
+
+ VPtr lookup(const K& key) {
+ VPtr val;
+ list<VPtr> to_release;
+ {
+ Mutex::Locker l(lock);
+ ++waiting;
+ bool retry = false;
+ do {
+ retry = false;
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
+ if (i != weak_refs.end()) {
+ val = i->second.first.lock();
+ if (val) {
+ lru_add(key, val, &to_release);
+ } else {
+ retry = true;
+ }
+ }
+ if (retry)
+ cond.Wait(lock);
+ } while (retry);
+ --waiting;
+ }
+ return val;
+ }
+ VPtr lookup_or_create(const K &key) {
+ VPtr val;
+ list<VPtr> to_release;
+ {
+ Mutex::Locker l(lock);
+ bool retry = false;
+ do {
+ retry = false;
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
+ if (i != weak_refs.end()) {
+ val = i->second.first.lock();
+ if (val) {
+ lru_add(key, val, &to_release);
+ return val;
+ } else {
+ retry = true;
+ }
+ }
+ if (retry)
+ cond.Wait(lock);
+ } while (retry);
+
+ V *new_value = new V();
+ VPtr new_val(new_value, Cleanup(this, key));
+ weak_refs.insert(make_pair(key, make_pair(new_val, new_value)));
+ lru_add(key, new_val, &to_release);
+ return new_val;
+ }
+ }
+
+ /**
+ * empty()
+ *
+ * Returns true iff there are no live references left to anything that has been
+ * in the cache.
+ */
+ bool empty() {
+ Mutex::Locker l(lock);
+ return weak_refs.empty();
+ }
+
+ /***
+ * 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
+ */
+ VPtr add(const K& key, V *value, bool *existed = NULL) {
+ VPtr val;
+ list<VPtr> to_release;
+ {
+ Mutex::Locker l(lock);
+ typename map<K, pair<WeakVPtr, V*>, C>::iterator actual =
+ weak_refs.lower_bound(key);
+ if (actual != weak_refs.end() && actual->first == key) {
+ if (existed)
+ *existed = true;
+
+ return actual->second.first.lock();
+ }
+
+ if (existed)
+ *existed = false;
+
+ val = VPtr(value, Cleanup(this, key));
+ weak_refs.insert(actual, make_pair(key, make_pair(val, value)));
+ lru_add(key, val, &to_release);
+ }
+ return val;
+ }
+
+ friend class SharedLRUTest;
+};
+
+#endif
Code Review / stor4nfv.git / blobdiff