]>
Commit | Line | Data |
---|---|---|
6a566b9c | 1 | |
2 | /* | |
507d0a78 | 3 | * DEBUG: none LRU Removal Policy |
6a566b9c | 4 | * AUTHOR: Henrik Nordstrom |
5 | * | |
2b6662ba | 6 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
6a566b9c | 7 | * ---------------------------------------------------------- |
8 | * | |
2b6662ba | 9 | * Squid is the result of efforts by numerous individuals from |
10 | * the Internet community; see the CONTRIBUTORS file for full | |
11 | * details. Many organizations have provided support for Squid's | |
12 | * development; see the SPONSORS file for full details. Squid is | |
13 | * Copyrighted (C) 2001 by the Regents of the University of | |
14 | * California; see the COPYRIGHT file for full details. Squid | |
15 | * incorporates software developed and/or copyrighted by other | |
16 | * sources; see the CREDITS file for full details. | |
6a566b9c | 17 | * |
18 | * This program is free software; you can redistribute it and/or modify | |
19 | * it under the terms of the GNU General Public License as published by | |
20 | * the Free Software Foundation; either version 2 of the License, or | |
21 | * (at your option) any later version. | |
26ac0430 | 22 | * |
6a566b9c | 23 | * This program is distributed in the hope that it will be useful, |
24 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
25 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
26 | * GNU General Public License for more details. | |
26ac0430 | 27 | * |
6a566b9c | 28 | * You should have received a copy of the GNU General Public License |
29 | * along with this program; if not, write to the Free Software | |
30 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | |
31 | * | |
32 | */ | |
33 | ||
582c2af2 | 34 | #include "squid.h" |
528b2c61 | 35 | #include "MemObject.h" |
985c86bc | 36 | #include "SquidTime.h" |
602d9612 | 37 | #include "Store.h" |
6a566b9c | 38 | |
39 | REMOVALPOLICYCREATE createRemovalPolicy_lru; | |
40 | ||
26ac0430 | 41 | struct LruPolicyData { |
e6ccf245 | 42 | void setPolicyNode (StoreEntry *, void *) const; |
6a566b9c | 43 | RemovalPolicy *policy; |
44 | dlink_list list; | |
45 | int count; | |
46 | int nwalkers; | |
9f913cf1 | 47 | enum heap_entry_type { |
62e76326 | 48 | TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM |
9f913cf1 | 49 | } type; |
6a566b9c | 50 | }; |
51 | ||
52 | /* Hack to avoid having to remember the RemovalPolicyNode location. | |
53 | * Needed by the purge walker to clear the policy information | |
54 | */ | |
e6ccf245 | 55 | static enum LruPolicyData::heap_entry_type |
6a566b9c | 56 | repl_guessType(StoreEntry * entry, RemovalPolicyNode * node) |
57 | { | |
58 | if (node == &entry->repl) | |
62e76326 | 59 | return LruPolicyData::TYPE_STORE_ENTRY; |
60 | ||
6a566b9c | 61 | if (entry->mem_obj && node == &entry->mem_obj->repl) |
62e76326 | 62 | return LruPolicyData::TYPE_STORE_MEM; |
63 | ||
6a566b9c | 64 | fatal("Heap Replacement: Unknown StoreEntry node type"); |
62e76326 | 65 | |
e6ccf245 | 66 | return LruPolicyData::TYPE_UNKNOWN; |
6a566b9c | 67 | } |
e6ccf245 | 68 | |
69 | void | |
70 | LruPolicyData::setPolicyNode (StoreEntry *entry, void *value) const | |
71 | { | |
72 | switch (type) { | |
62e76326 | 73 | |
74 | case TYPE_STORE_ENTRY: | |
75 | entry->repl.data = value; | |
76 | break ; | |
77 | ||
78 | case TYPE_STORE_MEM: | |
79 | entry->mem_obj->repl.data = value ; | |
80 | break ; | |
81 | ||
82 | default: | |
83 | break; | |
6a566b9c | 84 | } |
e6ccf245 | 85 | } |
6a566b9c | 86 | |
87 | typedef struct _LruNode LruNode; | |
62e76326 | 88 | |
26ac0430 | 89 | struct _LruNode { |
6a566b9c | 90 | /* Note: the dlink_node MUST be the first member of the LruNode |
91 | * structure. This member is later pointer typecasted to LruNode *. | |
92 | */ | |
93 | dlink_node node; | |
94 | }; | |
95 | ||
04eb0689 | 96 | static MemAllocator *lru_node_pool = NULL; |
6a566b9c | 97 | static int nr_lru_policies = 0; |
98 | ||
99 | static void | |
100 | lru_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) | |
101 | { | |
e6ccf245 | 102 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
6a566b9c | 103 | LruNode *lru_node; |
104 | assert(!node->data); | |
b001e822 | 105 | node->data = lru_node = (LruNode *)lru_node_pool->alloc(); |
6a566b9c | 106 | dlinkAddTail(entry, &lru_node->node, &lru->list); |
107 | lru->count += 1; | |
62e76326 | 108 | |
6a566b9c | 109 | if (!lru->type) |
62e76326 | 110 | lru->type = repl_guessType(entry, node); |
6a566b9c | 111 | } |
112 | ||
113 | static void | |
114 | lru_remove(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) | |
115 | { | |
e6ccf245 | 116 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
117 | LruNode *lru_node = (LruNode *)node->data; | |
62e76326 | 118 | |
6a566b9c | 119 | if (!lru_node) |
62e76326 | 120 | return; |
121 | ||
75240ca9 | 122 | /* |
123 | * It seems to be possible for an entry to exist in the hash | |
124 | * but not be in the LRU list, so check for that case rather | |
125 | * than suffer a NULL pointer access. | |
126 | */ | |
127 | if (NULL == lru_node->node.data) | |
62e76326 | 128 | return; |
129 | ||
6a566b9c | 130 | assert(lru_node->node.data == entry); |
62e76326 | 131 | |
6a566b9c | 132 | node->data = NULL; |
62e76326 | 133 | |
6a566b9c | 134 | dlinkDelete(&lru_node->node, &lru->list); |
62e76326 | 135 | |
dc47f531 | 136 | lru_node_pool->freeOne(lru_node); |
62e76326 | 137 | |
6a566b9c | 138 | lru->count -= 1; |
139 | } | |
140 | ||
141 | static void | |
142 | lru_referenced(RemovalPolicy * policy, const StoreEntry * entry, | |
62e76326 | 143 | RemovalPolicyNode * node) |
6a566b9c | 144 | { |
e6ccf245 | 145 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
146 | LruNode *lru_node = (LruNode *)node->data; | |
62e76326 | 147 | |
6a566b9c | 148 | if (!lru_node) |
62e76326 | 149 | return; |
150 | ||
6a566b9c | 151 | dlinkDelete(&lru_node->node, &lru->list); |
62e76326 | 152 | |
6a566b9c | 153 | dlinkAddTail((void *) entry, &lru_node->node, &lru->list); |
154 | } | |
155 | ||
156 | /** RemovalPolicyWalker **/ | |
157 | ||
158 | typedef struct _LruWalkData LruWalkData; | |
62e76326 | 159 | |
26ac0430 | 160 | struct _LruWalkData { |
6a566b9c | 161 | LruNode *current; |
162 | }; | |
163 | ||
2d72d4fd | 164 | static const StoreEntry * |
6a566b9c | 165 | lru_walkNext(RemovalPolicyWalker * walker) |
166 | { | |
e6ccf245 | 167 | LruWalkData *lru_walk = (LruWalkData *)walker->_data; |
6a566b9c | 168 | LruNode *lru_node = lru_walk->current; |
62e76326 | 169 | |
6a566b9c | 170 | if (!lru_node) |
62e76326 | 171 | return NULL; |
172 | ||
6a566b9c | 173 | lru_walk->current = (LruNode *) lru_node->node.next; |
62e76326 | 174 | |
6a566b9c | 175 | return (StoreEntry *) lru_node->node.data; |
176 | } | |
177 | ||
178 | static void | |
179 | lru_walkDone(RemovalPolicyWalker * walker) | |
180 | { | |
181 | RemovalPolicy *policy = walker->_policy; | |
e6ccf245 | 182 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
6a566b9c | 183 | assert(strcmp(policy->_type, "lru") == 0); |
184 | assert(lru->nwalkers > 0); | |
185 | lru->nwalkers -= 1; | |
186 | safe_free(walker->_data); | |
aa839030 | 187 | delete walker; |
6a566b9c | 188 | } |
189 | ||
190 | static RemovalPolicyWalker * | |
191 | lru_walkInit(RemovalPolicy * policy) | |
192 | { | |
e6ccf245 | 193 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
6a566b9c | 194 | RemovalPolicyWalker *walker; |
195 | LruWalkData *lru_walk; | |
196 | lru->nwalkers += 1; | |
aa839030 | 197 | walker = new RemovalPolicyWalker; |
e6ccf245 | 198 | lru_walk = (LruWalkData *)xcalloc(1, sizeof(*lru_walk)); |
6a566b9c | 199 | walker->_policy = policy; |
200 | walker->_data = lru_walk; | |
201 | walker->Next = lru_walkNext; | |
202 | walker->Done = lru_walkDone; | |
203 | lru_walk->current = (LruNode *) lru->list.head; | |
6a566b9c | 204 | return walker; |
205 | } | |
206 | ||
207 | /** RemovalPurgeWalker **/ | |
208 | ||
209 | typedef struct _LruPurgeData LruPurgeData; | |
62e76326 | 210 | |
26ac0430 | 211 | struct _LruPurgeData { |
6a566b9c | 212 | LruNode *current; |
213 | LruNode *start; | |
214 | }; | |
215 | ||
216 | static StoreEntry * | |
217 | lru_purgeNext(RemovalPurgeWalker * walker) | |
218 | { | |
e6ccf245 | 219 | LruPurgeData *lru_walker = (LruPurgeData *)walker->_data; |
6a566b9c | 220 | RemovalPolicy *policy = walker->_policy; |
e6ccf245 | 221 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
6a566b9c | 222 | LruNode *lru_node; |
223 | StoreEntry *entry; | |
62e76326 | 224 | |
225 | try_again: | |
6a566b9c | 226 | lru_node = lru_walker->current; |
62e76326 | 227 | |
6a566b9c | 228 | if (!lru_node || walker->scanned >= walker->max_scan) |
62e76326 | 229 | return NULL; |
230 | ||
6a566b9c | 231 | walker->scanned += 1; |
62e76326 | 232 | |
6a566b9c | 233 | lru_walker->current = (LruNode *) lru_node->node.next; |
62e76326 | 234 | |
6a566b9c | 235 | if (lru_walker->current == lru_walker->start) { |
62e76326 | 236 | /* Last node found */ |
237 | lru_walker->current = NULL; | |
6a566b9c | 238 | } |
62e76326 | 239 | |
6a566b9c | 240 | entry = (StoreEntry *) lru_node->node.data; |
241 | dlinkDelete(&lru_node->node, &lru->list); | |
62e76326 | 242 | |
3900307b | 243 | if (entry->locked()) { |
62e76326 | 244 | /* Shit, it is locked. we can't return this one */ |
d7ae3534 | 245 | ++ walker->locked; |
62e76326 | 246 | dlinkAddTail(entry, &lru_node->node, &lru->list); |
247 | goto try_again; | |
6a566b9c | 248 | } |
62e76326 | 249 | |
dc47f531 | 250 | lru_node_pool->freeOne(lru_node); |
6a566b9c | 251 | lru->count -= 1; |
e6ccf245 | 252 | lru->setPolicyNode(entry, NULL); |
6a566b9c | 253 | return entry; |
254 | } | |
255 | ||
256 | static void | |
257 | lru_purgeDone(RemovalPurgeWalker * walker) | |
258 | { | |
259 | RemovalPolicy *policy = walker->_policy; | |
e6ccf245 | 260 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
6a566b9c | 261 | assert(strcmp(policy->_type, "lru") == 0); |
262 | assert(lru->nwalkers > 0); | |
263 | lru->nwalkers -= 1; | |
264 | safe_free(walker->_data); | |
aa839030 | 265 | delete walker; |
6a566b9c | 266 | } |
267 | ||
268 | static RemovalPurgeWalker * | |
269 | lru_purgeInit(RemovalPolicy * policy, int max_scan) | |
270 | { | |
e6ccf245 | 271 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
6a566b9c | 272 | RemovalPurgeWalker *walker; |
273 | LruPurgeData *lru_walk; | |
274 | lru->nwalkers += 1; | |
aa839030 | 275 | walker = new RemovalPurgeWalker; |
e6ccf245 | 276 | lru_walk = (LruPurgeData *)xcalloc(1, sizeof(*lru_walk)); |
6a566b9c | 277 | walker->_policy = policy; |
278 | walker->_data = lru_walk; | |
279 | walker->max_scan = max_scan; | |
280 | walker->Next = lru_purgeNext; | |
281 | walker->Done = lru_purgeDone; | |
282 | lru_walk->start = lru_walk->current = (LruNode *) lru->list.head; | |
6a566b9c | 283 | return walker; |
284 | } | |
285 | ||
8a3e7d9e | 286 | static void |
287 | lru_stats(RemovalPolicy * policy, StoreEntry * sentry) | |
288 | { | |
e6ccf245 | 289 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
b671cc68 | 290 | LruNode *lru_node = (LruNode *) lru->list.head; |
8a3e7d9e | 291 | |
62e76326 | 292 | again: |
293 | ||
8a3e7d9e | 294 | if (lru_node) { |
62e76326 | 295 | StoreEntry *entry = (StoreEntry *) lru_node->node.data; |
296 | ||
3900307b | 297 | if (entry->locked()) { |
62e76326 | 298 | lru_node = (LruNode *) lru_node->node.next; |
299 | goto again; | |
300 | } | |
301 | ||
302 | storeAppendPrintf(sentry, "LRU reference age: %.2f days\n", (double) (squid_curtime - entry->lastref) / (double) (24 * 60 * 60)); | |
8a3e7d9e | 303 | } |
304 | } | |
305 | ||
6a566b9c | 306 | static void |
307 | lru_free(RemovalPolicy * policy) | |
308 | { | |
e6ccf245 | 309 | LruPolicyData *lru = (LruPolicyData *)policy->_data; |
6a566b9c | 310 | /* Make some verification of the policy state */ |
311 | assert(strcmp(policy->_type, "lru") == 0); | |
312 | assert(lru->nwalkers); | |
313 | assert(lru->count); | |
314 | /* Ok, time to destroy this policy */ | |
e4a67a80 | 315 | safe_free(lru); |
6a566b9c | 316 | memset(policy, 0, sizeof(*policy)); |
aa839030 | 317 | delete policy; |
6a566b9c | 318 | } |
319 | ||
320 | RemovalPolicy * | |
9f913cf1 | 321 | createRemovalPolicy_lru(wordlist * args) |
6a566b9c | 322 | { |
323 | RemovalPolicy *policy; | |
324 | LruPolicyData *lru_data; | |
325 | /* no arguments expected or understood */ | |
326 | assert(!args); | |
327 | /* Initialize */ | |
62e76326 | 328 | |
d96ceb8e | 329 | if (!lru_node_pool) { |
b001e822 | 330 | /* Must be chunked */ |
04eb0689 | 331 | lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode)); |
b001e822 | 332 | lru_node_pool->setChunkSize(512 * 1024); |
d96ceb8e | 333 | } |
62e76326 | 334 | |
6a566b9c | 335 | /* Allocate the needed structures */ |
e6ccf245 | 336 | lru_data = (LruPolicyData *)xcalloc(1, sizeof(*lru_data)); |
62e76326 | 337 | |
aa839030 | 338 | policy = new RemovalPolicy; |
62e76326 | 339 | |
6a566b9c | 340 | /* Initialize the URL data */ |
341 | lru_data->policy = policy; | |
62e76326 | 342 | |
6a566b9c | 343 | /* Populate the policy structure */ |
344 | policy->_type = "lru"; | |
62e76326 | 345 | |
6a566b9c | 346 | policy->_data = lru_data; |
62e76326 | 347 | |
6a566b9c | 348 | policy->Free = lru_free; |
62e76326 | 349 | |
6a566b9c | 350 | policy->Add = lru_add; |
62e76326 | 351 | |
6a566b9c | 352 | policy->Remove = lru_remove; |
62e76326 | 353 | |
6a566b9c | 354 | policy->Referenced = lru_referenced; |
62e76326 | 355 | |
6a566b9c | 356 | policy->Dereferenced = lru_referenced; |
62e76326 | 357 | |
6a566b9c | 358 | policy->WalkInit = lru_walkInit; |
62e76326 | 359 | |
6a566b9c | 360 | policy->PurgeInit = lru_purgeInit; |
62e76326 | 361 | |
8a3e7d9e | 362 | policy->Stats = lru_stats; |
62e76326 | 363 | |
6a566b9c | 364 | /* Increase policy usage count */ |
365 | nr_lru_policies += 0; | |
62e76326 | 366 | |
6a566b9c | 367 | return policy; |
368 | } |