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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors