2 * Copyright (C) 1996-2016 The Squid Software Foundation and contributors
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.
9 /* DEBUG: none LRU Removal Policy */
12 #include "MemObject.h"
13 #include "SquidTime.h"
16 /* because LruNode use explicit memory alloc()/freeOne() calls.
17 * XXX: convert to MEMPROXY_CLASS() API
21 REMOVALPOLICYCREATE createRemovalPolicy_lru
;
23 struct LruPolicyData
{
24 void setPolicyNode (StoreEntry
*, void *) const;
25 RemovalPolicy
*policy
;
29 enum heap_entry_type
{
30 TYPE_UNKNOWN
= 0, TYPE_STORE_ENTRY
, TYPE_STORE_MEM
34 /* Hack to avoid having to remember the RemovalPolicyNode location.
35 * Needed by the purge walker to clear the policy information
37 static enum LruPolicyData::heap_entry_type
38 repl_guessType(StoreEntry
* entry
, RemovalPolicyNode
* node
)
40 if (node
== &entry
->repl
)
41 return LruPolicyData::TYPE_STORE_ENTRY
;
43 if (entry
->mem_obj
&& node
== &entry
->mem_obj
->repl
)
44 return LruPolicyData::TYPE_STORE_MEM
;
46 fatal("Heap Replacement: Unknown StoreEntry node type");
48 return LruPolicyData::TYPE_UNKNOWN
;
52 LruPolicyData::setPolicyNode (StoreEntry
*entry
, void *value
) const
56 case TYPE_STORE_ENTRY
:
57 entry
->repl
.data
= value
;
61 entry
->mem_obj
->repl
.data
= value
;
69 typedef struct _LruNode LruNode
;
72 /* Note: the dlink_node MUST be the first member of the LruNode
73 * structure. This member is later pointer typecasted to LruNode *.
78 static MemAllocator
*lru_node_pool
= NULL
;
79 static int nr_lru_policies
= 0;
82 lru_add(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
84 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
87 node
->data
= lru_node
= (LruNode
*)lru_node_pool
->alloc();
88 dlinkAddTail(entry
, &lru_node
->node
, &lru
->list
);
92 lru
->type
= repl_guessType(entry
, node
);
96 lru_remove(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
98 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
99 LruNode
*lru_node
= (LruNode
*)node
->data
;
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.
109 if (NULL
== lru_node
->node
.data
)
112 assert(lru_node
->node
.data
== entry
);
116 dlinkDelete(&lru_node
->node
, &lru
->list
);
118 lru_node_pool
->freeOne(lru_node
);
124 lru_referenced(RemovalPolicy
* policy
, const StoreEntry
* entry
,
125 RemovalPolicyNode
* node
)
127 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
128 LruNode
*lru_node
= (LruNode
*)node
->data
;
133 dlinkDelete(&lru_node
->node
, &lru
->list
);
135 dlinkAddTail((void *) entry
, &lru_node
->node
, &lru
->list
);
138 /** RemovalPolicyWalker **/
140 typedef struct _LruWalkData LruWalkData
;
142 struct _LruWalkData
{
146 static const StoreEntry
*
147 lru_walkNext(RemovalPolicyWalker
* walker
)
149 LruWalkData
*lru_walk
= (LruWalkData
*)walker
->_data
;
150 LruNode
*lru_node
= lru_walk
->current
;
155 lru_walk
->current
= (LruNode
*) lru_node
->node
.next
;
157 return (StoreEntry
*) lru_node
->node
.data
;
161 lru_walkDone(RemovalPolicyWalker
* walker
)
163 RemovalPolicy
*policy
= walker
->_policy
;
164 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
165 assert(strcmp(policy
->_type
, "lru") == 0);
166 assert(lru
->nwalkers
> 0);
168 safe_free(walker
->_data
);
172 static RemovalPolicyWalker
*
173 lru_walkInit(RemovalPolicy
* policy
)
175 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
176 RemovalPolicyWalker
*walker
;
177 LruWalkData
*lru_walk
;
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
;
189 /** RemovalPurgeWalker **/
191 typedef struct _LruPurgeData LruPurgeData
;
193 struct _LruPurgeData
{
199 lru_purgeNext(RemovalPurgeWalker
* walker
)
201 LruPurgeData
*lru_walker
= (LruPurgeData
*)walker
->_data
;
202 RemovalPolicy
*policy
= walker
->_policy
;
203 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
208 lru_node
= lru_walker
->current
;
210 if (!lru_node
|| walker
->scanned
>= walker
->max_scan
)
213 walker
->scanned
+= 1;
215 lru_walker
->current
= (LruNode
*) lru_node
->node
.next
;
217 if (lru_walker
->current
== lru_walker
->start
) {
218 /* Last node found */
219 lru_walker
->current
= NULL
;
222 entry
= (StoreEntry
*) lru_node
->node
.data
;
223 dlinkDelete(&lru_node
->node
, &lru
->list
);
225 if (entry
->locked()) {
226 /* Shit, it is locked. we can't return this one */
228 dlinkAddTail(entry
, &lru_node
->node
, &lru
->list
);
232 lru_node_pool
->freeOne(lru_node
);
234 lru
->setPolicyNode(entry
, NULL
);
239 lru_purgeDone(RemovalPurgeWalker
* walker
)
241 RemovalPolicy
*policy
= walker
->_policy
;
242 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
243 assert(strcmp(policy
->_type
, "lru") == 0);
244 assert(lru
->nwalkers
> 0);
246 safe_free(walker
->_data
);
250 static RemovalPurgeWalker
*
251 lru_purgeInit(RemovalPolicy
* policy
, int max_scan
)
253 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
254 RemovalPurgeWalker
*walker
;
255 LruPurgeData
*lru_walk
;
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
;
269 lru_stats(RemovalPolicy
* policy
, StoreEntry
* sentry
)
271 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
272 LruNode
*lru_node
= (LruNode
*) lru
->list
.head
;
277 StoreEntry
*entry
= (StoreEntry
*) lru_node
->node
.data
;
279 if (entry
->locked()) {
280 lru_node
= (LruNode
*) lru_node
->node
.next
;
284 storeAppendPrintf(sentry
, "LRU reference age: %.2f days\n", (double) (squid_curtime
- entry
->lastref
) / (double) (24 * 60 * 60));
289 lru_free(RemovalPolicy
* policy
)
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
);
296 /* Ok, time to destroy this policy */
298 memset(policy
, 0, sizeof(*policy
));
303 createRemovalPolicy_lru(wordlist
* args
)
305 RemovalPolicy
*policy
;
306 LruPolicyData
*lru_data
;
307 /* no arguments expected or understood */
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);
317 /* Allocate the needed structures */
318 lru_data
= (LruPolicyData
*)xcalloc(1, sizeof(*lru_data
));
320 policy
= new RemovalPolicy
;
322 /* Initialize the URL data */
323 lru_data
->policy
= policy
;
325 /* Populate the policy structure */
326 policy
->_type
= "lru";
328 policy
->_data
= lru_data
;
330 policy
->Free
= lru_free
;
332 policy
->Add
= lru_add
;
334 policy
->Remove
= lru_remove
;
336 policy
->Referenced
= lru_referenced
;
338 policy
->Dereferenced
= lru_referenced
;
340 policy
->WalkInit
= lru_walkInit
;
342 policy
->PurgeInit
= lru_purgeInit
;
344 policy
->Stats
= lru_stats
;
346 /* Increase policy usage count */
347 nr_lru_policies
+= 0;