1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
8 * This is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License version 2.1, as published by the Free Software
11 * Foundation. See file COPYING.
15 #ifndef CEPH_SHAREDCACHE_H
16 #define CEPH_SHAREDCACHE_H
20 #include "common/Mutex.h"
21 #include "common/Cond.h"
22 #include "include/unordered_map.h"
24 // re-include our assert to clobber the system one; fix dout:
25 #include "include/assert.h"
27 template <class K, class V, class C = std::less<K>, class H = std::hash<K> >
30 typedef ceph::shared_ptr<V> VPtr;
31 typedef ceph::weak_ptr<V> WeakVPtr;
39 ceph::unordered_map<K, typename list<pair<K, VPtr> >::iterator, H> contents;
40 list<pair<K, VPtr> > lru;
42 map<K, pair<WeakVPtr, V*>, C> weak_refs;
44 void trim_cache(list<VPtr> *to_release) {
45 while (size > max_size) {
46 to_release->push_back(lru.back().second);
47 lru_remove(lru.back().first);
51 void lru_remove(const K& key) {
52 typename ceph::unordered_map<K, typename list<pair<K, VPtr> >::iterator, H>::iterator i =
54 if (i == contents.end())
61 void lru_add(const K& key, const VPtr& val, list<VPtr> *to_release) {
62 typename ceph::unordered_map<K, typename list<pair<K, VPtr> >::iterator, H>::iterator i =
64 if (i != contents.end()) {
65 lru.splice(lru.begin(), lru, i->second);
68 lru.push_front(make_pair(key, val));
69 contents[key] = lru.begin();
70 trim_cache(to_release);
74 void remove(const K& key, V *valptr) {
75 Mutex::Locker l(lock);
76 typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
77 if (i != weak_refs.end() && i->second.second == valptr) {
85 SharedLRU<K, V, C> *cache;
87 Cleanup(SharedLRU<K, V, C> *cache, K key) : cache(cache), key(key) {}
88 void operator()(V *ptr) {
89 cache->remove(key, ptr);
95 SharedLRU(CephContext *cct = NULL, size_t max_size = 20)
96 : cct(cct), lock("SharedLRU::lock"), max_size(max_size),
98 contents.rehash(max_size);
104 if (!weak_refs.empty()) {
105 lderr(cct) << "leaked refs:\n";
106 dump_weak_refs(*_dout);
108 if (cct->_conf->get_val<bool>("debug_asserts_on_shutdown")) {
109 assert(weak_refs.empty());
114 /// adjust container comparator (for purposes of get_next sort order)
115 void reset_comparator(C comp) {
116 // get_next uses weak_refs; that's the only container we need to
118 map<K, pair<WeakVPtr, V*>, C> temp;
120 Mutex::Locker l(lock);
121 temp.swap(weak_refs);
123 // reconstruct with new comparator
124 weak_refs = map<K, pair<WeakVPtr, V*>, C>(comp);
125 weak_refs.insert(temp.begin(), temp.end());
129 return weak_refs.key_comp();
132 void set_cct(CephContext *c) {
136 void dump_weak_refs() {
137 lderr(cct) << "leaked refs:\n";
138 dump_weak_refs(*_dout);
142 void dump_weak_refs(ostream& out) {
143 for (typename map<K, pair<WeakVPtr, V*>, C>::iterator p = weak_refs.begin();
144 p != weak_refs.end();
146 out << __func__ << " " << this << " weak_refs: "
147 << p->first << " = " << p->second.second
148 << " with " << p->second.first.use_count() << " refs"
153 //clear all strong reference from the lru.
156 VPtr val; // release any ref we have after we drop the lock
157 Mutex::Locker l(lock);
161 val = lru.back().second;
162 lru_remove(lru.back().first);
166 void clear(const K& key) {
167 VPtr val; // release any ref we have after we drop the lock
169 Mutex::Locker l(lock);
170 typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
171 if (i != weak_refs.end()) {
172 val = i->second.first.lock();
178 void purge(const K &key) {
179 VPtr val; // release any ref we have after we drop the lock
181 Mutex::Locker l(lock);
182 typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
183 if (i != weak_refs.end()) {
184 val = i->second.first.lock();
191 void set_size(size_t new_size) {
192 list<VPtr> to_release;
194 Mutex::Locker l(lock);
196 trim_cache(&to_release);
200 // Returns K key s.t. key <= k for all currently cached k,v
201 K cached_key_lower_bound() {
202 Mutex::Locker l(lock);
203 return weak_refs.begin()->first;
206 VPtr lower_bound(const K& key) {
208 list<VPtr> to_release;
210 Mutex::Locker l(lock);
215 if (weak_refs.empty())
217 typename map<K, pair<WeakVPtr, V*>, C>::iterator i =
218 weak_refs.lower_bound(key);
219 if (i == weak_refs.end())
221 val = i->second.first.lock();
223 lru_add(i->first, val, &to_release);
234 bool get_next(const K &key, pair<K, VPtr> *next) {
237 Mutex::Locker l(lock);
239 typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.upper_bound(key);
241 while (i != weak_refs.end() &&
242 !(next_val = i->second.first.lock()))
245 if (i == weak_refs.end())
249 r = make_pair(i->first, next_val);
255 bool get_next(const K &key, pair<K, V> *next) {
257 bool found = get_next(key, &r);
260 next->first = r.first;
262 next->second = *(r.second);
266 VPtr lookup(const K& key) {
268 list<VPtr> to_release;
270 Mutex::Locker l(lock);
275 typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
276 if (i != weak_refs.end()) {
277 val = i->second.first.lock();
279 lru_add(key, val, &to_release);
291 VPtr lookup_or_create(const K &key) {
293 list<VPtr> to_release;
295 Mutex::Locker l(lock);
299 typename map<K, pair<WeakVPtr, V*>, C>::iterator i = weak_refs.find(key);
300 if (i != weak_refs.end()) {
301 val = i->second.first.lock();
303 lru_add(key, val, &to_release);
313 V *new_value = new V();
314 VPtr new_val(new_value, Cleanup(this, key));
315 weak_refs.insert(make_pair(key, make_pair(new_val, new_value)));
316 lru_add(key, new_val, &to_release);
324 * Returns true iff there are no live references left to anything that has been
328 Mutex::Locker l(lock);
329 return weak_refs.empty();
333 * Inserts a key if not present, or bumps it to the front of the LRU if
334 * it is, and then gives you a reference to the value. If the key already
335 * existed, you are responsible for deleting the new value you tried to
338 * @param key The key to insert
339 * @param value The value that goes with the key
340 * @param existed Set to true if the value was already in the
341 * map, false otherwise
342 * @return A reference to the map's value for the given key
344 VPtr add(const K& key, V *value, bool *existed = NULL) {
346 list<VPtr> to_release;
348 Mutex::Locker l(lock);
349 typename map<K, pair<WeakVPtr, V*>, C>::iterator actual =
350 weak_refs.lower_bound(key);
351 if (actual != weak_refs.end() && actual->first == key) {
355 return actual->second.first.lock();
361 val = VPtr(value, Cleanup(this, key));
362 weak_refs.insert(actual, make_pair(key, make_pair(val, value)));
363 lru_add(key, val, &to_release);
368 friend class SharedLRUTest;