]>
git.proxmox.com Git - ceph.git/blob - ceph/src/include/lru.h
c52cb567bf158509044c924e90d500d8ad15edb5
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() {
161 // look through tail of bot
162 while (bottom
.size()) {
163 LRUObject
*p
= bottom
.back();
164 if (!p
->lru_pinned
) return p
;
167 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
);
183 LRUObject
*lru_expire() {
184 LRUObject
*p
= lru_get_next_expire();
186 return lru_remove(p
);
191 //generic_dout(10) << "lru: " << lru_get_size() << " items, " << top.size() << " top, " << bottom.size() << " bot, " << pintail.size() << " pintail" << dendl;
195 // adjust top/bot balance, as necessary
197 uint64_t toplen
= top
.size();
198 uint64_t topwant
= (midpoint
* (double)(lru_get_size() - num_pinned
));
199 /* move items from below midpoint (bottom) to top: move midpoint forward */
200 for (uint64_t i
= toplen
; i
< topwant
; i
++) {
201 top
.push_back(&bottom
.front()->lru_link
);
203 /* or: move items from above midpoint (top) to bottom: move midpoint backwards */
204 for (uint64_t i
= toplen
; i
> topwant
; i
--) {
205 bottom
.push_front(&top
.back()->lru_link
);
212 friend class LRUObject
;
214 typedef xlist
<LRUObject
*> LRUList
;
215 LRUList top
, bottom
, pintail
;
218 inline LRUObject::~LRUObject() {
220 lru
->lru_remove(this);
224 inline void LRUObject::lru_pin() {
225 if (lru
&& !lru_pinned
) {
231 inline void LRUObject::lru_unpin() {
232 if (lru
&& lru_pinned
) {
235 // move from pintail -> bot
236 if (lru_link
.get_list() == &lru
->pintail
) {
237 lru
->lru_bottouch(this);