]>
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 | 27 | public: |
f67539c2 TL |
28 | LRUObject() : lru_link(this) {} |
29 | virtual ~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 | 37 | private: |
f67539c2 | 38 | class LRU *lru{}; |
181888fb | 39 | xlist<LRUObject *>::item lru_link; |
f67539c2 | 40 | bool lru_pinned = false; |
7c673cae FG |
41 | }; |
42 | ||
181888fb FG |
43 | class LRU { |
44 | public: | |
181888fb FG |
45 | uint64_t lru_get_size() const { return lru_get_top()+lru_get_bot()+lru_get_pintail(); } |
46 | uint64_t lru_get_top() const { return top.size(); } | |
47 | uint64_t lru_get_bot() const{ return bottom.size(); } | |
48 | uint64_t lru_get_pintail() const { return pintail.size(); } | |
49 | uint64_t lru_get_num_pinned() const { return num_pinned; } | |
7c673cae | 50 | |
181888fb | 51 | void lru_set_midpoint(double f) { midpoint = fmin(1.0, fmax(0.0, f)); } |
7c673cae | 52 | |
181888fb FG |
53 | void lru_clear() { |
54 | while (!top.empty()) { | |
55 | lru_remove(top.front()); | |
7c673cae | 56 | } |
181888fb FG |
57 | while (!bottom.empty()) { |
58 | lru_remove(bottom.front()); | |
7c673cae | 59 | } |
181888fb FG |
60 | while (!pintail.empty()) { |
61 | lru_remove(pintail.front()); | |
7c673cae | 62 | } |
11fdf7f2 | 63 | ceph_assert(num_pinned == 0); |
7c673cae FG |
64 | } |
65 | ||
66 | // insert at top of lru | |
67 | void lru_insert_top(LRUObject *o) { | |
11fdf7f2 | 68 | ceph_assert(!o->lru); |
7c673cae | 69 | o->lru = this; |
181888fb FG |
70 | top.push_front(&o->lru_link); |
71 | if (o->lru_pinned) num_pinned++; | |
72 | adjust(); | |
7c673cae FG |
73 | } |
74 | ||
75 | // insert at mid point in lru | |
76 | void lru_insert_mid(LRUObject *o) { | |
11fdf7f2 | 77 | ceph_assert(!o->lru); |
7c673cae | 78 | o->lru = this; |
181888fb FG |
79 | bottom.push_front(&o->lru_link); |
80 | if (o->lru_pinned) num_pinned++; | |
81 | adjust(); | |
7c673cae FG |
82 | } |
83 | ||
84 | // insert at bottom of lru | |
85 | void lru_insert_bot(LRUObject *o) { | |
11fdf7f2 | 86 | ceph_assert(!o->lru); |
7c673cae | 87 | o->lru = this; |
181888fb FG |
88 | bottom.push_back(&o->lru_link); |
89 | if (o->lru_pinned) num_pinned++; | |
90 | adjust(); | |
7c673cae FG |
91 | } |
92 | ||
7c673cae FG |
93 | // remove an item |
94 | LRUObject *lru_remove(LRUObject *o) { | |
7c673cae | 95 | if (!o->lru) return o; |
181888fb | 96 | auto list = o->lru_link.get_list(); |
11fdf7f2 | 97 | ceph_assert(list == &top || list == &bottom || list == &pintail); |
181888fb FG |
98 | o->lru_link.remove_myself(); |
99 | if (o->lru_pinned) num_pinned--; | |
100 | o->lru = nullptr; | |
101 | adjust(); | |
7c673cae FG |
102 | return o; |
103 | } | |
104 | ||
105 | // touch item -- move to head of lru | |
106 | bool lru_touch(LRUObject *o) { | |
181888fb FG |
107 | if (!o->lru) { |
108 | lru_insert_top(o); | |
109 | } else { | |
11fdf7f2 | 110 | ceph_assert(o->lru == this); |
181888fb | 111 | auto list = o->lru_link.get_list(); |
11fdf7f2 | 112 | ceph_assert(list == &top || list == &bottom || list == &pintail); |
181888fb FG |
113 | top.push_front(&o->lru_link); |
114 | adjust(); | |
115 | } | |
7c673cae FG |
116 | return true; |
117 | } | |
118 | ||
119 | // touch item -- move to midpoint (unless already higher) | |
120 | bool lru_midtouch(LRUObject *o) { | |
181888fb FG |
121 | if (!o->lru) { |
122 | lru_insert_mid(o); | |
123 | } else { | |
11fdf7f2 | 124 | ceph_assert(o->lru == this); |
181888fb | 125 | auto list = o->lru_link.get_list(); |
11fdf7f2 | 126 | ceph_assert(list == &top || list == &bottom || list == &pintail); |
181888fb FG |
127 | if (list == &top) return false; |
128 | bottom.push_front(&o->lru_link); | |
129 | adjust(); | |
130 | } | |
7c673cae FG |
131 | return true; |
132 | } | |
133 | ||
134 | // touch item -- move to bottom | |
135 | bool lru_bottouch(LRUObject *o) { | |
181888fb FG |
136 | if (!o->lru) { |
137 | lru_insert_bot(o); | |
138 | } else { | |
11fdf7f2 | 139 | ceph_assert(o->lru == this); |
181888fb | 140 | auto list = o->lru_link.get_list(); |
11fdf7f2 | 141 | ceph_assert(list == &top || list == &bottom || list == &pintail); |
181888fb FG |
142 | bottom.push_back(&o->lru_link); |
143 | adjust(); | |
144 | } | |
7c673cae FG |
145 | return true; |
146 | } | |
147 | ||
148 | void lru_touch_entire_pintail() { | |
149 | // promote entire pintail to the top lru | |
181888fb FG |
150 | while (pintail.size() > 0) { |
151 | top.push_back(&pintail.front()->lru_link); | |
152 | adjust(); | |
7c673cae FG |
153 | } |
154 | } | |
155 | ||
7c673cae FG |
156 | // expire -- expire a single item |
157 | LRUObject *lru_get_next_expire() { | |
b32b8144 | 158 | adjust(); |
7c673cae | 159 | // look through tail of bot |
181888fb FG |
160 | while (bottom.size()) { |
161 | LRUObject *p = bottom.back(); | |
7c673cae FG |
162 | if (!p->lru_pinned) return p; |
163 | ||
164 | // move to pintail | |
181888fb | 165 | pintail.push_front(&p->lru_link); |
7c673cae FG |
166 | } |
167 | ||
168 | // ok, try head then | |
181888fb FG |
169 | while (top.size()) { |
170 | LRUObject *p = top.back(); | |
7c673cae FG |
171 | if (!p->lru_pinned) return p; |
172 | ||
173 | // move to pintail | |
181888fb | 174 | pintail.push_front(&p->lru_link); |
7c673cae FG |
175 | } |
176 | ||
177 | // no luck! | |
178 | return NULL; | |
179 | } | |
180 | ||
181 | LRUObject *lru_expire() { | |
182 | LRUObject *p = lru_get_next_expire(); | |
183 | if (p) | |
184 | return lru_remove(p); | |
185 | return NULL; | |
186 | } | |
187 | ||
7c673cae | 188 | void lru_status() { |
181888fb | 189 | //generic_dout(10) << "lru: " << lru_get_size() << " items, " << top.size() << " top, " << bottom.size() << " bot, " << pintail.size() << " pintail" << dendl; |
7c673cae FG |
190 | } |
191 | ||
181888fb FG |
192 | protected: |
193 | // adjust top/bot balance, as necessary | |
194 | void adjust() { | |
195 | uint64_t toplen = top.size(); | |
196 | uint64_t topwant = (midpoint * (double)(lru_get_size() - num_pinned)); | |
197 | /* move items from below midpoint (bottom) to top: move midpoint forward */ | |
198 | for (uint64_t i = toplen; i < topwant; i++) { | |
199 | top.push_back(&bottom.front()->lru_link); | |
200 | } | |
201 | /* or: move items from above midpoint (top) to bottom: move midpoint backwards */ | |
202 | for (uint64_t i = toplen; i > topwant; i--) { | |
203 | bottom.push_front(&top.back()->lru_link); | |
204 | } | |
205 | } | |
206 | ||
f67539c2 TL |
207 | uint64_t num_pinned = 0; |
208 | double midpoint = 0.6; | |
181888fb FG |
209 | |
210 | friend class LRUObject; | |
211 | private: | |
f67539c2 | 212 | using LRUList = xlist<LRUObject*>; |
181888fb | 213 | LRUList top, bottom, pintail; |
7c673cae FG |
214 | }; |
215 | ||
181888fb FG |
216 | inline LRUObject::~LRUObject() { |
217 | if (lru) { | |
218 | lru->lru_remove(this); | |
219 | } | |
220 | } | |
7c673cae FG |
221 | |
222 | inline void LRUObject::lru_pin() { | |
223 | if (lru && !lru_pinned) { | |
181888fb | 224 | lru->num_pinned++; |
7c673cae FG |
225 | } |
226 | lru_pinned = true; | |
227 | } | |
228 | ||
229 | inline void LRUObject::lru_unpin() { | |
230 | if (lru && lru_pinned) { | |
181888fb | 231 | lru->num_pinned--; |
7c673cae FG |
232 | |
233 | // move from pintail -> bot | |
181888fb FG |
234 | if (lru_link.get_list() == &lru->pintail) { |
235 | lru->lru_bottouch(this); | |
7c673cae | 236 | } |
7c673cae FG |
237 | } |
238 | lru_pinned = false; | |
239 | } | |
240 | ||
241 | #endif |