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