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.
23 #include "common/config.h"
28 LRUObject() : lru(), lru_link(this), lru_pinned(false) { }
31 // pin/unpin item in cache
34 bool lru_is_expireable() const { return !lru_pinned; }
39 xlist<LRUObject *>::item lru_link;
45 LRU() : num_pinned(0), midpoint(0.6) {}
47 uint64_t lru_get_size() const { return lru_get_top()+lru_get_bot()+lru_get_pintail(); }
48 uint64_t lru_get_top() const { return top.size(); }
49 uint64_t lru_get_bot() const{ return bottom.size(); }
50 uint64_t lru_get_pintail() const { return pintail.size(); }
51 uint64_t lru_get_num_pinned() const { return num_pinned; }
53 void lru_set_midpoint(double f) { midpoint = fmin(1.0, fmax(0.0, f)); }
56 while (!top.empty()) {
57 lru_remove(top.front());
59 while (!bottom.empty()) {
60 lru_remove(bottom.front());
62 while (!pintail.empty()) {
63 lru_remove(pintail.front());
65 assert(num_pinned == 0);
68 // insert at top of lru
69 void lru_insert_top(LRUObject *o) {
72 top.push_front(&o->lru_link);
73 if (o->lru_pinned) num_pinned++;
77 // insert at mid point in lru
78 void lru_insert_mid(LRUObject *o) {
81 bottom.push_front(&o->lru_link);
82 if (o->lru_pinned) num_pinned++;
86 // insert at bottom of lru
87 void lru_insert_bot(LRUObject *o) {
90 bottom.push_back(&o->lru_link);
91 if (o->lru_pinned) num_pinned++;
96 LRUObject *lru_remove(LRUObject *o) {
97 if (!o->lru) return o;
98 auto list = o->lru_link.get_list();
99 assert(list == &top || list == &bottom || list == &pintail);
100 o->lru_link.remove_myself();
101 if (o->lru_pinned) num_pinned--;
107 // touch item -- move to head of lru
108 bool lru_touch(LRUObject *o) {
112 assert(o->lru == this);
113 auto list = o->lru_link.get_list();
114 assert(list == &top || list == &bottom || list == &pintail);
115 top.push_front(&o->lru_link);
121 // touch item -- move to midpoint (unless already higher)
122 bool lru_midtouch(LRUObject *o) {
126 assert(o->lru == this);
127 auto list = o->lru_link.get_list();
128 assert(list == &top || list == &bottom || list == &pintail);
129 if (list == &top) return false;
130 bottom.push_front(&o->lru_link);
136 // touch item -- move to bottom
137 bool lru_bottouch(LRUObject *o) {
141 assert(o->lru == this);
142 auto list = o->lru_link.get_list();
143 assert(list == &top || list == &bottom || list == &pintail);
144 bottom.push_back(&o->lru_link);
150 void lru_touch_entire_pintail() {
151 // promote entire pintail to the top lru
152 while (pintail.size() > 0) {
153 top.push_back(&pintail.front()->lru_link);
158 // expire -- expire a single item
159 LRUObject *lru_get_next_expire() {
160 // look through tail of bot
161 while (bottom.size()) {
162 LRUObject *p = bottom.back();
163 if (!p->lru_pinned) return p;
166 pintail.push_front(&p->lru_link);
172 LRUObject *p = top.back();
173 if (!p->lru_pinned) return p;
176 pintail.push_front(&p->lru_link);
184 LRUObject *lru_expire() {
185 LRUObject *p = lru_get_next_expire();
187 return lru_remove(p);
192 //generic_dout(10) << "lru: " << lru_get_size() << " items, " << top.size() << " top, " << bottom.size() << " bot, " << pintail.size() << " pintail" << dendl;
196 // adjust top/bot balance, as necessary
198 uint64_t toplen = top.size();
199 uint64_t topwant = (midpoint * (double)(lru_get_size() - num_pinned));
200 /* move items from below midpoint (bottom) to top: move midpoint forward */
201 for (uint64_t i = toplen; i < topwant; i++) {
202 top.push_back(&bottom.front()->lru_link);
204 /* or: move items from above midpoint (top) to bottom: move midpoint backwards */
205 for (uint64_t i = toplen; i > topwant; i--) {
206 bottom.push_front(&top.back()->lru_link);
213 friend class LRUObject;
215 typedef xlist<LRUObject *> LRUList;
216 LRUList top, bottom, pintail;
219 inline LRUObject::~LRUObject() {
221 lru->lru_remove(this);
225 inline void LRUObject::lru_pin() {
226 if (lru && !lru_pinned) {
232 inline void LRUObject::lru_unpin() {
233 if (lru && lru_pinned) {
236 // move from pintail -> bot
237 if (lru_link.get_list() == &lru->pintail) {
238 lru->lru_bottouch(this);