]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net> | |
7 | * | |
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. | |
12 | * | |
13 | */ | |
14 | ||
15 | ||
16 | ||
17 | #ifndef CEPH_LRU_H | |
18 | #define CEPH_LRU_H | |
19 | ||
181888fb | 20 | #include <math.h> |
7c673cae FG |
21 | #include <stdint.h> |
22 | ||
23 | #include "common/config.h" | |
181888fb | 24 | #include "xlist.h" |
7c673cae FG |
25 | |
26 | class LRUObject { | |
181888fb FG |
27 | public: |
28 | LRUObject() : lru(), lru_link(this), lru_pinned(false) { } | |
29 | ~LRUObject(); | |
7c673cae FG |
30 | |
31 | // pin/unpin item in cache | |
181888fb | 32 | void lru_pin(); |
7c673cae FG |
33 | void lru_unpin(); |
34 | bool lru_is_expireable() const { return !lru_pinned; } | |
35 | ||
36 | friend class LRU; | |
181888fb FG |
37 | private: |
38 | class LRU *lru; | |
39 | xlist<LRUObject *>::item lru_link; | |
40 | bool lru_pinned; | |
7c673cae FG |
41 | }; |
42 | ||
181888fb FG |
43 | class LRU { |
44 | public: | |
45 | LRU() : num_pinned(0), midpoint(0.6) {} | |
7c673cae | 46 | |
181888fb FG |
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; } | |
7c673cae | 52 | |
181888fb | 53 | void lru_set_midpoint(double f) { midpoint = fmin(1.0, fmax(0.0, f)); } |
7c673cae | 54 | |
181888fb FG |
55 | void lru_clear() { |
56 | while (!top.empty()) { | |
57 | lru_remove(top.front()); | |
7c673cae | 58 | } |
181888fb FG |
59 | while (!bottom.empty()) { |
60 | lru_remove(bottom.front()); | |
7c673cae | 61 | } |
181888fb FG |
62 | while (!pintail.empty()) { |
63 | lru_remove(pintail.front()); | |
7c673cae | 64 | } |
181888fb | 65 | assert(num_pinned == 0); |
7c673cae FG |
66 | } |
67 | ||
68 | // insert at top of lru | |
69 | void lru_insert_top(LRUObject *o) { | |
7c673cae FG |
70 | assert(!o->lru); |
71 | o->lru = this; | |
181888fb FG |
72 | top.push_front(&o->lru_link); |
73 | if (o->lru_pinned) num_pinned++; | |
74 | adjust(); | |
7c673cae FG |
75 | } |
76 | ||
77 | // insert at mid point in lru | |
78 | void lru_insert_mid(LRUObject *o) { | |
7c673cae FG |
79 | assert(!o->lru); |
80 | o->lru = this; | |
181888fb FG |
81 | bottom.push_front(&o->lru_link); |
82 | if (o->lru_pinned) num_pinned++; | |
83 | adjust(); | |
7c673cae FG |
84 | } |
85 | ||
86 | // insert at bottom of lru | |
87 | void lru_insert_bot(LRUObject *o) { | |
88 | assert(!o->lru); | |
89 | o->lru = this; | |
181888fb FG |
90 | bottom.push_back(&o->lru_link); |
91 | if (o->lru_pinned) num_pinned++; | |
92 | adjust(); | |
7c673cae FG |
93 | } |
94 | ||
7c673cae FG |
95 | // remove an item |
96 | LRUObject *lru_remove(LRUObject *o) { | |
7c673cae | 97 | if (!o->lru) return o; |
181888fb FG |
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--; | |
102 | o->lru = nullptr; | |
103 | adjust(); | |
7c673cae FG |
104 | return o; |
105 | } | |
106 | ||
107 | // touch item -- move to head of lru | |
108 | bool lru_touch(LRUObject *o) { | |
181888fb FG |
109 | if (!o->lru) { |
110 | lru_insert_top(o); | |
111 | } else { | |
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); | |
116 | adjust(); | |
117 | } | |
7c673cae FG |
118 | return true; |
119 | } | |
120 | ||
121 | // touch item -- move to midpoint (unless already higher) | |
122 | bool lru_midtouch(LRUObject *o) { | |
181888fb FG |
123 | if (!o->lru) { |
124 | lru_insert_mid(o); | |
125 | } else { | |
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); | |
131 | adjust(); | |
132 | } | |
7c673cae FG |
133 | return true; |
134 | } | |
135 | ||
136 | // touch item -- move to bottom | |
137 | bool lru_bottouch(LRUObject *o) { | |
181888fb FG |
138 | if (!o->lru) { |
139 | lru_insert_bot(o); | |
140 | } else { | |
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); | |
145 | adjust(); | |
146 | } | |
7c673cae FG |
147 | return true; |
148 | } | |
149 | ||
150 | void lru_touch_entire_pintail() { | |
151 | // promote entire pintail to the top lru | |
181888fb FG |
152 | while (pintail.size() > 0) { |
153 | top.push_back(&pintail.front()->lru_link); | |
154 | adjust(); | |
7c673cae FG |
155 | } |
156 | } | |
157 | ||
7c673cae FG |
158 | // expire -- expire a single item |
159 | LRUObject *lru_get_next_expire() { | |
b32b8144 | 160 | adjust(); |
7c673cae | 161 | // look through tail of bot |
181888fb FG |
162 | while (bottom.size()) { |
163 | LRUObject *p = bottom.back(); | |
7c673cae FG |
164 | if (!p->lru_pinned) return p; |
165 | ||
166 | // move to pintail | |
181888fb | 167 | pintail.push_front(&p->lru_link); |
7c673cae FG |
168 | } |
169 | ||
170 | // ok, try head then | |
181888fb FG |
171 | while (top.size()) { |
172 | LRUObject *p = top.back(); | |
7c673cae FG |
173 | if (!p->lru_pinned) return p; |
174 | ||
175 | // move to pintail | |
181888fb | 176 | pintail.push_front(&p->lru_link); |
7c673cae FG |
177 | } |
178 | ||
179 | // no luck! | |
180 | return NULL; | |
181 | } | |
182 | ||
183 | LRUObject *lru_expire() { | |
184 | LRUObject *p = lru_get_next_expire(); | |
185 | if (p) | |
186 | return lru_remove(p); | |
187 | return NULL; | |
188 | } | |
189 | ||
7c673cae | 190 | void lru_status() { |
181888fb | 191 | //generic_dout(10) << "lru: " << lru_get_size() << " items, " << top.size() << " top, " << bottom.size() << " bot, " << pintail.size() << " pintail" << dendl; |
7c673cae FG |
192 | } |
193 | ||
181888fb FG |
194 | protected: |
195 | // adjust top/bot balance, as necessary | |
196 | void adjust() { | |
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); | |
202 | } | |
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); | |
206 | } | |
207 | } | |
208 | ||
209 | uint64_t num_pinned; | |
210 | double midpoint; | |
211 | ||
212 | friend class LRUObject; | |
213 | private: | |
214 | typedef xlist<LRUObject *> LRUList; | |
215 | LRUList top, bottom, pintail; | |
7c673cae FG |
216 | }; |
217 | ||
181888fb FG |
218 | inline LRUObject::~LRUObject() { |
219 | if (lru) { | |
220 | lru->lru_remove(this); | |
221 | } | |
222 | } | |
7c673cae FG |
223 | |
224 | inline void LRUObject::lru_pin() { | |
225 | if (lru && !lru_pinned) { | |
181888fb | 226 | lru->num_pinned++; |
7c673cae FG |
227 | } |
228 | lru_pinned = true; | |
229 | } | |
230 | ||
231 | inline void LRUObject::lru_unpin() { | |
232 | if (lru && lru_pinned) { | |
181888fb | 233 | lru->num_pinned--; |
7c673cae FG |
234 | |
235 | // move from pintail -> bot | |
181888fb FG |
236 | if (lru_link.get_list() == &lru->pintail) { |
237 | lru->lru_bottouch(this); | |
7c673cae | 238 | } |
7c673cae FG |
239 | } |
240 | lru_pinned = false; | |
241 | } | |
242 | ||
243 | #endif |