]>
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 | ||
20 | #include <stdint.h> | |
21 | ||
22 | #include "common/config.h" | |
23 | ||
24 | ||
25 | ||
26 | class LRUObject { | |
27 | private: | |
28 | LRUObject *lru_next, *lru_prev; | |
29 | bool lru_pinned; | |
30 | class LRU *lru; | |
31 | class LRUList *lru_list; | |
32 | ||
33 | public: | |
34 | LRUObject() { | |
35 | lru_next = lru_prev = NULL; | |
36 | lru_list = 0; | |
37 | lru_pinned = false; | |
38 | lru = 0; | |
39 | } | |
40 | ||
41 | // pin/unpin item in cache | |
42 | void lru_pin(); | |
43 | void lru_unpin(); | |
44 | bool lru_is_expireable() const { return !lru_pinned; } | |
45 | ||
46 | friend class LRU; | |
47 | friend class LRUList; | |
48 | }; | |
49 | ||
50 | ||
51 | class LRUList { | |
52 | private: | |
53 | LRUObject *head, *tail; | |
54 | uint32_t len; | |
55 | ||
56 | public: | |
57 | LRUList() { | |
58 | head = tail = 0; | |
59 | len = 0; | |
60 | } | |
61 | ||
31f18b77 | 62 | uint32_t get_length() const { return len; } |
7c673cae FG |
63 | |
64 | LRUObject *get_head() { | |
65 | return head; | |
66 | } | |
67 | LRUObject *get_tail() { | |
68 | return tail; | |
69 | } | |
70 | ||
71 | void clear() { | |
72 | while (len > 0) { | |
73 | remove(get_head()); | |
74 | } | |
75 | } | |
76 | ||
77 | void insert_head(LRUObject *o) { | |
78 | o->lru_next = head; | |
79 | o->lru_prev = NULL; | |
80 | if (head) { | |
81 | head->lru_prev = o; | |
82 | } else { | |
83 | tail = o; | |
84 | } | |
85 | head = o; | |
86 | o->lru_list = this; | |
87 | len++; | |
88 | } | |
89 | void insert_tail(LRUObject *o) { | |
90 | o->lru_next = NULL; | |
91 | o->lru_prev = tail; | |
92 | if (tail) { | |
93 | tail->lru_next = o; | |
94 | } else { | |
95 | head = o; | |
96 | } | |
97 | tail = o; | |
98 | o->lru_list = this; | |
99 | len++; | |
100 | } | |
101 | ||
102 | void remove(LRUObject *o) { | |
103 | assert(o->lru_list == this); | |
104 | if (o->lru_next) | |
105 | o->lru_next->lru_prev = o->lru_prev; | |
106 | else | |
107 | tail = o->lru_prev; | |
108 | if (o->lru_prev) | |
109 | o->lru_prev->lru_next = o->lru_next; | |
110 | else | |
111 | head = o->lru_next; | |
112 | o->lru_next = o->lru_prev = NULL; | |
113 | o->lru_list = 0; | |
114 | assert(len>0); | |
115 | len--; | |
116 | } | |
117 | ||
118 | }; | |
119 | ||
120 | ||
121 | class LRU { | |
122 | protected: | |
123 | LRUList lru_top, lru_bot, lru_pintail; | |
124 | uint32_t lru_num, lru_num_pinned; | |
125 | uint32_t lru_max; // max items | |
126 | double lru_midpoint; | |
127 | ||
128 | friend class LRUObject; | |
129 | //friend class MDCache; // hack | |
130 | ||
131 | public: | |
132 | LRU(int max = 0) { | |
133 | lru_num = 0; | |
134 | lru_num_pinned = 0; | |
135 | lru_midpoint = .6; | |
136 | lru_max = max; | |
137 | } | |
138 | ||
31f18b77 FG |
139 | uint32_t lru_get_size() const { return lru_num; } |
140 | uint32_t lru_get_top() const { return lru_top.get_length(); } | |
141 | uint32_t lru_get_bot() const{ return lru_bot.get_length(); } | |
142 | uint32_t lru_get_pintail() const { return lru_pintail.get_length(); } | |
143 | uint32_t lru_get_max() const { return lru_max; } | |
144 | uint32_t lru_get_num_pinned() const { return lru_num_pinned; } | |
7c673cae FG |
145 | |
146 | void lru_set_max(uint32_t m) { lru_max = m; } | |
147 | void lru_set_midpoint(float f) { lru_midpoint = f; } | |
148 | ||
149 | void lru_clear() { | |
150 | lru_top.clear(); | |
151 | lru_bot.clear(); | |
152 | lru_pintail.clear(); | |
153 | lru_num = 0; | |
154 | } | |
155 | ||
156 | // insert at top of lru | |
157 | void lru_insert_top(LRUObject *o) { | |
158 | //assert(!o->lru_in_lru); | |
159 | //o->lru_in_lru = true; | |
160 | assert(!o->lru); | |
161 | o->lru = this; | |
162 | lru_top.insert_head( o ); | |
163 | lru_num++; | |
164 | if (o->lru_pinned) lru_num_pinned++; | |
165 | lru_adjust(); | |
166 | } | |
167 | ||
168 | // insert at mid point in lru | |
169 | void lru_insert_mid(LRUObject *o) { | |
170 | //assert(!o->lru_in_lru); | |
171 | //o->lru_in_lru = true; | |
172 | assert(!o->lru); | |
173 | o->lru = this; | |
174 | lru_bot.insert_head(o); | |
175 | lru_num++; | |
176 | if (o->lru_pinned) lru_num_pinned++; | |
177 | } | |
178 | ||
179 | // insert at bottom of lru | |
180 | void lru_insert_bot(LRUObject *o) { | |
181 | assert(!o->lru); | |
182 | o->lru = this; | |
183 | lru_bot.insert_tail(o); | |
184 | lru_num++; | |
185 | if (o->lru_pinned) lru_num_pinned++; | |
186 | } | |
187 | ||
188 | /* | |
189 | // insert at bottom of lru | |
190 | void lru_insert_pintail(LRUObject *o) { | |
191 | assert(!o->lru); | |
192 | o->lru = this; | |
193 | ||
194 | assert(o->lru_pinned); | |
195 | ||
196 | lru_pintail.insert_head(o); | |
197 | lru_num++; | |
198 | lru_num_pinned += o->lru_pinned; | |
199 | } | |
200 | */ | |
201 | ||
202 | ||
203 | ||
204 | ||
205 | // adjust top/bot balance, as necessary | |
206 | void lru_adjust() { | |
207 | if (!lru_max) return; | |
208 | ||
209 | unsigned toplen = lru_top.get_length(); | |
210 | unsigned topwant = (unsigned)(lru_midpoint * ((double)lru_max - lru_num_pinned)); | |
211 | while (toplen > 0 && | |
212 | toplen > topwant) { | |
213 | // remove from tail of top, stick at head of bot | |
214 | // FIXME: this could be way more efficient by moving a whole chain of items. | |
215 | ||
216 | LRUObject *o = lru_top.get_tail(); | |
217 | lru_top.remove(o); | |
218 | lru_bot.insert_head(o); | |
219 | toplen--; | |
220 | } | |
221 | } | |
222 | ||
223 | ||
224 | // remove an item | |
225 | LRUObject *lru_remove(LRUObject *o) { | |
226 | // not in list | |
227 | //assert(o->lru_in_lru); | |
228 | //if (!o->lru_in_lru) return o; // might have expired and been removed that way. | |
229 | if (!o->lru) return o; | |
230 | ||
231 | assert((o->lru_list == &lru_pintail) || | |
232 | (o->lru_list == &lru_top) || | |
233 | (o->lru_list == &lru_bot)); | |
234 | o->lru_list->remove(o); | |
235 | ||
236 | lru_num--; | |
237 | if (o->lru_pinned) lru_num_pinned--; | |
238 | o->lru = 0; | |
239 | return o; | |
240 | } | |
241 | ||
242 | // touch item -- move to head of lru | |
243 | bool lru_touch(LRUObject *o) { | |
244 | lru_remove(o); | |
245 | lru_insert_top(o); | |
246 | return true; | |
247 | } | |
248 | ||
249 | // touch item -- move to midpoint (unless already higher) | |
250 | bool lru_midtouch(LRUObject *o) { | |
251 | if (o->lru_list == &lru_top) return false; | |
252 | ||
253 | lru_remove(o); | |
254 | lru_insert_mid(o); | |
255 | return true; | |
256 | } | |
257 | ||
258 | // touch item -- move to bottom | |
259 | bool lru_bottouch(LRUObject *o) { | |
260 | lru_remove(o); | |
261 | lru_insert_bot(o); | |
262 | return true; | |
263 | } | |
264 | ||
265 | void lru_touch_entire_pintail() { | |
266 | // promote entire pintail to the top lru | |
267 | while (lru_pintail.get_length() > 0) { | |
268 | LRUObject *o = lru_pintail.get_head(); | |
269 | lru_pintail.remove(o); | |
270 | lru_top.insert_tail(o); | |
271 | } | |
272 | } | |
273 | ||
274 | ||
275 | // expire -- expire a single item | |
276 | LRUObject *lru_get_next_expire() { | |
277 | LRUObject *p; | |
278 | ||
279 | // look through tail of bot | |
280 | while (lru_bot.get_length()) { | |
281 | p = lru_bot.get_tail(); | |
282 | if (!p->lru_pinned) return p; | |
283 | ||
284 | // move to pintail | |
285 | lru_bot.remove(p); | |
286 | lru_pintail.insert_head(p); | |
287 | } | |
288 | ||
289 | // ok, try head then | |
290 | while (lru_top.get_length()) { | |
291 | p = lru_top.get_tail(); | |
292 | if (!p->lru_pinned) return p; | |
293 | ||
294 | // move to pintail | |
295 | lru_top.remove(p); | |
296 | lru_pintail.insert_head(p); | |
297 | } | |
298 | ||
299 | // no luck! | |
300 | return NULL; | |
301 | } | |
302 | ||
303 | LRUObject *lru_expire() { | |
304 | LRUObject *p = lru_get_next_expire(); | |
305 | if (p) | |
306 | return lru_remove(p); | |
307 | return NULL; | |
308 | } | |
309 | ||
310 | ||
311 | void lru_status() { | |
312 | //generic_dout(10) << "lru: " << lru_num << " items, " << lru_top.get_length() << " top, " << lru_bot.get_length() << " bot, " << lru_pintail.get_length() << " pintail" << dendl; | |
313 | } | |
314 | ||
315 | }; | |
316 | ||
317 | ||
318 | inline void LRUObject::lru_pin() { | |
319 | if (lru && !lru_pinned) { | |
320 | lru->lru_num_pinned++; | |
321 | lru->lru_adjust(); | |
322 | } | |
323 | lru_pinned = true; | |
324 | } | |
325 | ||
326 | inline void LRUObject::lru_unpin() { | |
327 | if (lru && lru_pinned) { | |
328 | lru->lru_num_pinned--; | |
329 | ||
330 | // move from pintail -> bot | |
331 | if (lru_list == &lru->lru_pintail) { | |
332 | lru->lru_pintail.remove(this); | |
333 | lru->lru_bot.insert_tail(this); | |
334 | } | |
335 | lru->lru_adjust(); | |
336 | } | |
337 | lru_pinned = false; | |
338 | } | |
339 | ||
340 | #endif |