store_repl_lru.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2023 The Squid Software Foundation and contributors
3 *
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.
7 */
8
9/* DEBUG: none LRU Removal Policy */
10
11#include "squid.h"
12#include "MemObject.h"
13#include "Store.h"
14
16
18 void setPolicyNode (StoreEntry *, void *) const;
21 int count;
26};
27
28/* Hack to avoid having to remember the RemovalPolicyNode location.
29 * Needed by the purge walker to clear the policy information
30 */
33{
34 if (node == &entry->repl)
36
37 if (entry->mem_obj && node == &entry->mem_obj->repl)
39
40 fatal("Heap Replacement: Unknown StoreEntry node type");
41
43}
44
45void
46LruPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
47{
48 switch (type) {
49
51 entry->repl.data = value;
52 break ;
53
54 case TYPE_STORE_MEM:
55 entry->mem_obj->repl.data = value ;
56 break ;
57
58 default:
59 break;
60 }
61}
62
64{
66
67public:
68 /* Note: the dlink_node MUST be the first member of the LruNode
69 * structure. This member is later pointer typecasted to LruNode *.
70 */
72};
73
74static int nr_lru_policies = 0;
75
76static void
78{
79 LruPolicyData *lru = (LruPolicyData *)policy->_data;
80 LruNode *lru_node;
81 assert(!node->data);
82 node->data = lru_node = new LruNode;
83 dlinkAddTail(entry, &lru_node->node, &lru->list);
84 lru->count += 1;
85
86 if (!lru->type)
87 lru->type = repl_guessType(entry, node);
88}
89
90static void
92{
93 LruPolicyData *lru = (LruPolicyData *)policy->_data;
94 LruNode *lru_node = (LruNode *)node->data;
95
96 if (!lru_node)
97 return;
98
99 /*
100 * It seems to be possible for an entry to exist in the hash
101 * but not be in the LRU list, so check for that case rather
102 * than suffer a NULL pointer access.
103 */
104 if (nullptr == lru_node->node.data)
105 return;
106
107 assert(lru_node->node.data == entry);
108
109 node->data = nullptr;
110
111 dlinkDelete(&lru_node->node, &lru->list);
112
113 delete lru_node;
114
115 lru->count -= 1;
116}
117
118static void
121{
122 LruPolicyData *lru = (LruPolicyData *)policy->_data;
123 LruNode *lru_node = (LruNode *)node->data;
124
125 if (!lru_node)
126 return;
127
128 dlinkDelete(&lru_node->node, &lru->list);
129
130 dlinkAddTail((void *) entry, &lru_node->node, &lru->list);
131}
132
136
139};
140
141static const StoreEntry *
143{
144 LruWalkData *lru_walk = (LruWalkData *)walker->_data;
145 LruNode *lru_node = lru_walk->current;
146
147 if (!lru_node)
148 return nullptr;
149
150 lru_walk->current = (LruNode *) lru_node->node.next;
151
152 return (StoreEntry *) lru_node->node.data;
153}
154
155static void
157{
158 RemovalPolicy *policy = walker->_policy;
159 LruPolicyData *lru = (LruPolicyData *)policy->_data;
160 assert(strcmp(policy->_type, "lru") == 0);
161 assert(lru->nwalkers > 0);
162 lru->nwalkers -= 1;
163 safe_free(walker->_data);
164 delete walker;
165}
166
167static RemovalPolicyWalker *
169{
170 LruPolicyData *lru = (LruPolicyData *)policy->_data;
171 RemovalPolicyWalker *walker;
172 LruWalkData *lru_walk;
173 lru->nwalkers += 1;
174 walker = new RemovalPolicyWalker;
175 lru_walk = (LruWalkData *)xcalloc(1, sizeof(*lru_walk));
176 walker->_policy = policy;
177 walker->_data = lru_walk;
178 walker->Next = lru_walkNext;
179 walker->Done = lru_walkDone;
180 lru_walk->current = (LruNode *) lru->list.head;
181 return walker;
182}
183
187
191};
192
193static StoreEntry *
195{
196 LruPurgeData *lru_walker = (LruPurgeData *)walker->_data;
197 RemovalPolicy *policy = walker->_policy;
198 LruPolicyData *lru = (LruPolicyData *)policy->_data;
199 LruNode *lru_node;
200 StoreEntry *entry;
201
202try_again:
203 lru_node = lru_walker->current;
204
205 if (!lru_node || walker->scanned >= walker->max_scan)
206 return nullptr;
207
208 walker->scanned += 1;
209
210 lru_walker->current = (LruNode *) lru_node->node.next;
211
212 if (lru_walker->current == lru_walker->start) {
213 /* Last node found */
214 lru_walker->current = nullptr;
215 }
216
217 entry = (StoreEntry *) lru_node->node.data;
218 dlinkDelete(&lru_node->node, &lru->list);
219
220 if (entry->locked()) {
221 /* Shit, it is locked. we can't return this one */
222 ++ walker->locked;
223 dlinkAddTail(entry, &lru_node->node, &lru->list);
224 goto try_again;
225 }
226
227 delete lru_node;
228 lru->count -= 1;
229 lru->setPolicyNode(entry, nullptr);
230 return entry;
231}
232
233static void
235{
236 RemovalPolicy *policy = walker->_policy;
237 LruPolicyData *lru = (LruPolicyData *)policy->_data;
238 assert(strcmp(policy->_type, "lru") == 0);
239 assert(lru->nwalkers > 0);
240 lru->nwalkers -= 1;
241 safe_free(walker->_data);
242 delete walker;
243}
244
245static RemovalPurgeWalker *
246lru_purgeInit(RemovalPolicy * policy, int max_scan)
247{
248 LruPolicyData *lru = (LruPolicyData *)policy->_data;
249 RemovalPurgeWalker *walker;
250 LruPurgeData *lru_walk;
251 lru->nwalkers += 1;
252 walker = new RemovalPurgeWalker;
253 lru_walk = (LruPurgeData *)xcalloc(1, sizeof(*lru_walk));
254 walker->_policy = policy;
255 walker->_data = lru_walk;
256 walker->max_scan = max_scan;
257 walker->Next = lru_purgeNext;
258 walker->Done = lru_purgeDone;
259 lru_walk->start = lru_walk->current = (LruNode *) lru->list.head;
260 return walker;
261}
262
263static void
265{
266 LruPolicyData *lru = (LruPolicyData *)policy->_data;
267 LruNode *lru_node = (LruNode *) lru->list.head;
268
269again:
270
271 if (lru_node) {
272 StoreEntry *entry = (StoreEntry *) lru_node->node.data;
273
274 if (entry->locked()) {
275 lru_node = (LruNode *) lru_node->node.next;
276 goto again;
277 }
278
279 storeAppendPrintf(sentry, "LRU reference age: %.2f days\n", (double) (squid_curtime - entry->lastref) / (double) (24 * 60 * 60));
280 }
281}
282
283static void
285{
286 LruPolicyData *lru = (LruPolicyData *)policy->_data;
287 /* Make some verification of the policy state */
288 assert(strcmp(policy->_type, "lru") == 0);
289 assert(lru->nwalkers);
290 assert(lru->count);
291 /* Ok, time to destroy this policy */
292 safe_free(lru);
293 memset(policy, 0, sizeof(*policy));
294 delete policy;
295}
296
299{
300 RemovalPolicy *policy;
301 LruPolicyData *lru_data;
302 /* no arguments expected or understood */
303 assert(!args);
304
305 /* Allocate the needed structures */
306 lru_data = (LruPolicyData *)xcalloc(1, sizeof(*lru_data));
307
308 policy = new RemovalPolicy;
309
310 /* Initialize the URL data */
311 lru_data->policy = policy;
312
313 /* Populate the policy structure */
314 policy->_type = "lru";
315
316 policy->_data = lru_data;
317
318 policy->Free = lru_free;
319
320 policy->Add = lru_add;
321
322 policy->Remove = lru_remove;
323
324 policy->Referenced = lru_referenced;
325
327
328 policy->WalkInit = lru_walkInit;
329
330 policy->PurgeInit = lru_purgeInit;
331
332 policy->Stats = lru_stats;
333
334 /* Increase policy usage count */
335 nr_lru_policies += 0;
336
337 return policy;
338}
339
time_t squid_curtime
Definition: stub_libtime.cc:20
RemovalPolicy * REMOVALPOLICYCREATE(wordlist *args)
Definition: RemovalPolicy.h:80
#define assert(EX)
Definition: assert.h:17
dlink_node node
MEMPROXY_CLASS(LruNode)
RemovalPolicyNode repl
Definition: MemObject.h:220
RemovalPolicy * _policy
Definition: RemovalPolicy.h:60
const char * _type
Definition: RemovalPolicy.h:43
void(* Free)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:45
void(* Referenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:48
void(* Add)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:46
void(* Stats)(RemovalPolicy *policy, StoreEntry *entry)
Definition: RemovalPolicy.h:52
RemovalPurgeWalker *(* PurgeInit)(RemovalPolicy *policy, int max_scan)
Definition: RemovalPolicy.h:51
void(* Dereferenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:49
void(* Remove)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:47
RemovalPolicyWalker *(* WalkInit)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:50
RemovalPolicy * _policy
Definition: RemovalPolicy.h:71
int locked() const
Definition: Store.h:146
RemovalPolicyNode repl
Definition: Store.h:222
MemObject * mem_obj
Definition: Store.h:221
time_t lastref
Definition: Store.h:225
void fatal(const char *message)
Definition: fatal.cc:28
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:841
static void lru_free(RemovalPolicy *policy)
static void lru_referenced(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
static void lru_remove(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
static RemovalPurgeWalker * lru_purgeInit(RemovalPolicy *policy, int max_scan)
static StoreEntry * lru_purgeNext(RemovalPurgeWalker *walker)
static const StoreEntry * lru_walkNext(RemovalPolicyWalker *walker)
static void lru_walkDone(RemovalPolicyWalker *walker)
REMOVALPOLICYCREATE createRemovalPolicy_lru
static enum LruPolicyData::heap_entry_type repl_guessType(StoreEntry *entry, RemovalPolicyNode *node)
static RemovalPolicyWalker * lru_walkInit(RemovalPolicy *policy)
static void lru_purgeDone(RemovalPurgeWalker *walker)
static int nr_lru_policies
static void lru_add(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
static void lru_stats(RemovalPolicy *policy, StoreEntry *sentry)
dlink_list list
RemovalPolicy * policy
void setPolicyNode(StoreEntry *, void *) const
enum LruPolicyData::heap_entry_type type
LruNode * current
LruNode * current
Definition: parse.c:104
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
#define safe_free(x)
Definition: xalloc.h:73

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors