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 
22 struct LruPolicyData {
23  void setPolicyNode (StoreEntry *, void *) const;
26  int count;
27  int nwalkers;
30  } type;
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 
50 void
51 LruPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
52 {
53  switch (type) {
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;
65  }
66 }
67 
68 typedef struct _LruNode LruNode;
69 
70 struct _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 
78 static int nr_lru_policies = 0;
79 
80 static 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 
94 static 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 (NULL == lru_node->node.data)
109  return;
110 
111  assert(lru_node->node.data == entry);
112 
113  node->data = NULL;
114 
115  dlinkDelete(&lru_node->node, &lru->list);
116 
117  lru_node_pool->freeOne(lru_node);
118 
119  lru->count -= 1;
120 }
121 
122 static void
123 lru_referenced(RemovalPolicy * policy, const StoreEntry * entry,
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 
139 typedef struct _LruWalkData LruWalkData;
140 
141 struct _LruWalkData {
143 };
144 
145 static const StoreEntry *
147 {
148  LruWalkData *lru_walk = (LruWalkData *)walker->_data;
149  LruNode *lru_node = lru_walk->current;
150 
151  if (!lru_node)
152  return NULL;
153 
154  lru_walk->current = (LruNode *) lru_node->node.next;
155 
156  return (StoreEntry *) lru_node->node.data;
157 }
158 
159 static 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 
171 static 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 
190 typedef struct _LruPurgeData LruPurgeData;
191 
195 };
196 
197 static 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 
206 try_again:
207  lru_node = lru_walker->current;
208 
209  if (!lru_node || walker->scanned >= walker->max_scan)
210  return NULL;
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 = NULL;
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, NULL);
234  return entry;
235 }
236 
237 static 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 
249 static RemovalPurgeWalker *
250 lru_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 
267 static void
268 lru_stats(RemovalPolicy * policy, StoreEntry * sentry)
269 {
270  LruPolicyData *lru = (LruPolicyData *)policy->_data;
271  LruNode *lru_node = (LruNode *) lru->list.head;
272 
273 again:
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 
287 static 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 
337  policy->Dereferenced = lru_referenced;
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 
RemovalPolicy * policy
void fatal(const char *message)
Definition: fatal.cc:28
Definition: parse.c:104
void(* Free)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:45
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
static const StoreEntry * lru_walkNext(RemovalPolicyWalker *walker)
RemovalPolicy * _policy
Definition: RemovalPolicy.h:68
MemObject * mem_obj
Definition: Store.h:219
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:830
RemovalPolicy * _policy
Definition: RemovalPolicy.h:57
static MemAllocator * lru_node_pool
enum LruPolicyData::heap_entry_type type
RemovalPurgeWalker *(* PurgeInit)(RemovalPolicy *policy, int max_scan)
Definition: RemovalPolicy.h:51
static void lru_walkDone(RemovalPolicyWalker *walker)
static RemovalPurgeWalker * lru_purgeInit(RemovalPolicy *policy, int max_scan)
static void lru_stats(RemovalPolicy *policy, StoreEntry *sentry)
void(* Referenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:48
const char * _type
Definition: RemovalPolicy.h:40
dlink_list list
static void lru_add(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
virtual void freeOne(void *)=0
dlink_node node
#define NULL
Definition: types.h:166
void setPolicyNode(StoreEntry *, void *) const
LruNode * current
static void lru_free(RemovalPolicy *policy)
static void lru_purgeDone(RemovalPurgeWalker *walker)
static void lru_referenced(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
#define safe_free(x)
Definition: xalloc.h:73
#define assert(EX)
Definition: assert.h:19
void(* Stats)(RemovalPolicy *policy, StoreEntry *entry)
Definition: RemovalPolicy.h:52
LruNode * current
void(* Remove)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:47
virtual void setChunkSize(size_t)
Definition: Pool.h:218
time_t squid_curtime
Definition: stub_libtime.cc:20
RemovalPolicyWalker *(* WalkInit)(RemovalPolicy *policy)
Definition: RemovalPolicy.h:50
void(* Dereferenced)(RemovalPolicy *policy, const StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:49
static int nr_lru_policies
static RemovalPolicyWalker * lru_walkInit(RemovalPolicy *policy)
virtual void * alloc()=0
void(* Add)(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
Definition: RemovalPolicy.h:46
#define memPoolCreate
Definition: Pool.h:325
static enum LruPolicyData::heap_entry_type repl_guessType(StoreEntry *entry, RemovalPolicyNode *node)
static StoreEntry * lru_purgeNext(RemovalPurgeWalker *walker)
REMOVALPOLICYCREATE createRemovalPolicy_lru
int locked() const
Definition: Store.h:144
RemovalPolicy * REMOVALPOLICYCREATE(wordlist *args)
Definition: RemovalPolicy.h:80
RemovalPolicyNode repl
Definition: MemObject.h:196
time_t lastref
Definition: Store.h:223
static void lru_remove(RemovalPolicy *policy, StoreEntry *entry, RemovalPolicyNode *node)
RemovalPolicyNode repl
Definition: Store.h:220

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors