store_repl_lru.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 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
15/* because LruNode use explicit memory alloc()/freeOne() calls.
16 * XXX: convert to MEMPROXY_CLASS() API
17 */
18#include "mem/Pool.h"
19
21
23 void setPolicyNode (StoreEntry *, void *) const;
26 int count;
31};
32
33/* Hack to avoid having to remember the RemovalPolicyNode location.
34 * Needed by the purge walker to clear the policy information
35 */
38{
39 if (node == &entry->repl)
41
42 if (entry->mem_obj && node == &entry->mem_obj->repl)
44
45 fatal("Heap Replacement: Unknown StoreEntry node type");
46
48}
49
50void
51LruPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
52{
53 switch (type) {
54
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;
65 }
66}
67
68typedef struct _LruNode LruNode;
69
70struct _LruNode {
71 /* Note: the dlink_node MUST be the first member of the LruNode
72 * structure. This member is later pointer typecasted to LruNode *.
73 */
75};
76
77static MemAllocator *lru_node_pool = nullptr;
78static int nr_lru_policies = 0;
79
80static void
82{
83 LruPolicyData *lru = (LruPolicyData *)policy->_data;
84 LruNode *lru_node;
85 assert(!node->data);
86 node->data = lru_node = (LruNode *)lru_node_pool->alloc();
87 dlinkAddTail(entry, &lru_node->node, &lru->list);
88 lru->count += 1;
89
90 if (!lru->type)
91 lru->type = repl_guessType(entry, node);
92}
93
94static void
96{
97 LruPolicyData *lru = (LruPolicyData *)policy->_data;
98 LruNode *lru_node = (LruNode *)node->data;
99
100 if (!lru_node)
101 return;
102
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 */
108 if (nullptr == lru_node->node.data)
109 return;
110
111 assert(lru_node->node.data == entry);
112
113 node->data = nullptr;
114
115 dlinkDelete(&lru_node->node, &lru->list);
116
117 lru_node_pool->freeOne(lru_node);
118
119 lru->count -= 1;
120}
121
122static void
125{
126 LruPolicyData *lru = (LruPolicyData *)policy->_data;
127 LruNode *lru_node = (LruNode *)node->data;
128
129 if (!lru_node)
130 return;
131
132 dlinkDelete(&lru_node->node, &lru->list);
133
134 dlinkAddTail((void *) entry, &lru_node->node, &lru->list);
135}
136
140
143};
144
145static const StoreEntry *
147{
148 LruWalkData *lru_walk = (LruWalkData *)walker->_data;
149 LruNode *lru_node = lru_walk->current;
150
151 if (!lru_node)
152 return nullptr;
153
154 lru_walk->current = (LruNode *) lru_node->node.next;
155
156 return (StoreEntry *) lru_node->node.data;
157}
158
159static void
161{
162 RemovalPolicy *policy = walker->_policy;
163 LruPolicyData *lru = (LruPolicyData *)policy->_data;
164 assert(strcmp(policy->_type, "lru") == 0);
165 assert(lru->nwalkers > 0);
166 lru->nwalkers -= 1;
167 safe_free(walker->_data);
168 delete walker;
169}
170
171static RemovalPolicyWalker *
173{
174 LruPolicyData *lru = (LruPolicyData *)policy->_data;
175 RemovalPolicyWalker *walker;
176 LruWalkData *lru_walk;
177 lru->nwalkers += 1;
178 walker = new RemovalPolicyWalker;
179 lru_walk = (LruWalkData *)xcalloc(1, sizeof(*lru_walk));
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;
185 return walker;
186}
187
191
195};
196
197static StoreEntry *
199{
200 LruPurgeData *lru_walker = (LruPurgeData *)walker->_data;
201 RemovalPolicy *policy = walker->_policy;
202 LruPolicyData *lru = (LruPolicyData *)policy->_data;
203 LruNode *lru_node;
204 StoreEntry *entry;
205
206try_again:
207 lru_node = lru_walker->current;
208
209 if (!lru_node || walker->scanned >= walker->max_scan)
210 return nullptr;
211
212 walker->scanned += 1;
213
214 lru_walker->current = (LruNode *) lru_node->node.next;
215
216 if (lru_walker->current == lru_walker->start) {
217 /* Last node found */
218 lru_walker->current = nullptr;
219 }
220
221 entry = (StoreEntry *) lru_node->node.data;
222 dlinkDelete(&lru_node->node, &lru->list);
223
224 if (entry->locked()) {
225 /* Shit, it is locked. we can't return this one */
226 ++ walker->locked;
227 dlinkAddTail(entry, &lru_node->node, &lru->list);
228 goto try_again;
229 }
230
231 lru_node_pool->freeOne(lru_node);
232 lru->count -= 1;
233 lru->setPolicyNode(entry, nullptr);
234 return entry;
235}
236
237static void
239{
240 RemovalPolicy *policy = walker->_policy;
241 LruPolicyData *lru = (LruPolicyData *)policy->_data;
242 assert(strcmp(policy->_type, "lru") == 0);
243 assert(lru->nwalkers > 0);
244 lru->nwalkers -= 1;
245 safe_free(walker->_data);
246 delete walker;
247}
248
249static RemovalPurgeWalker *
250lru_purgeInit(RemovalPolicy * policy, int max_scan)
251{
252 LruPolicyData *lru = (LruPolicyData *)policy->_data;
253 RemovalPurgeWalker *walker;
254 LruPurgeData *lru_walk;
255 lru->nwalkers += 1;
256 walker = new RemovalPurgeWalker;
257 lru_walk = (LruPurgeData *)xcalloc(1, sizeof(*lru_walk));
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;
264 return walker;
265}
266
267static void
269{
270 LruPolicyData *lru = (LruPolicyData *)policy->_data;
271 LruNode *lru_node = (LruNode *) lru->list.head;
272
273again:
274
275 if (lru_node) {
276 StoreEntry *entry = (StoreEntry *) lru_node->node.data;
277
278 if (entry->locked()) {
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));
284 }
285}
286
287static void
289{
290 LruPolicyData *lru = (LruPolicyData *)policy->_data;
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 */
296 safe_free(lru);
297 memset(policy, 0, sizeof(*policy));
298 delete policy;
299}
300
303{
304 RemovalPolicy *policy;
305 LruPolicyData *lru_data;
306 /* no arguments expected or understood */
307 assert(!args);
308 /* Initialize */
309
310 if (!lru_node_pool) {
311 /* Must be chunked */
312 lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode));
313 lru_node_pool->setChunkSize(512 * 1024);
314 }
315
316 /* Allocate the needed structures */
317 lru_data = (LruPolicyData *)xcalloc(1, sizeof(*lru_data));
318
319 policy = new RemovalPolicy;
320
321 /* Initialize the URL data */
322 lru_data->policy = policy;
323
324 /* Populate the policy structure */
325 policy->_type = "lru";
326
327 policy->_data = lru_data;
328
329 policy->Free = lru_free;
330
331 policy->Add = lru_add;
332
333 policy->Remove = lru_remove;
334
335 policy->Referenced = lru_referenced;
336
338
339 policy->WalkInit = lru_walkInit;
340
341 policy->PurgeInit = lru_purgeInit;
342
343 policy->Stats = lru_stats;
344
345 /* Increase policy usage count */
346 nr_lru_policies += 0;
347
348 return policy;
349}
350
time_t squid_curtime
Definition: stub_libtime.cc:20
RemovalPolicy * REMOVALPOLICYCREATE(wordlist *args)
Definition: RemovalPolicy.h:80
#define assert(EX)
Definition: assert.h:19
virtual void setChunkSize(size_t)
Definition: Pool.h:218
virtual void freeOne(void *)=0
virtual void * alloc()=0
RemovalPolicyNode repl
Definition: MemObject.h:196
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
#define memPoolCreate
Definition: Pool.h:325
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:828
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 MemAllocator * lru_node_pool
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
dlink_node node
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