2 * Copyright (C) 1996-2023 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"
15 REMOVALPOLICYCREATE createRemovalPolicy_lru
;
17 struct LruPolicyData
{
18 void setPolicyNode (StoreEntry
*, void *) const;
19 RemovalPolicy
*policy
;
23 enum heap_entry_type
{
24 TYPE_UNKNOWN
= 0, TYPE_STORE_ENTRY
, TYPE_STORE_MEM
28 /* Hack to avoid having to remember the RemovalPolicyNode location.
29 * Needed by the purge walker to clear the policy information
31 static enum LruPolicyData::heap_entry_type
32 repl_guessType(StoreEntry
* entry
, RemovalPolicyNode
* node
)
34 if (node
== &entry
->repl
)
35 return LruPolicyData::TYPE_STORE_ENTRY
;
37 if (entry
->mem_obj
&& node
== &entry
->mem_obj
->repl
)
38 return LruPolicyData::TYPE_STORE_MEM
;
40 fatal("Heap Replacement: Unknown StoreEntry node type");
42 return LruPolicyData::TYPE_UNKNOWN
;
46 LruPolicyData::setPolicyNode (StoreEntry
*entry
, void *value
) const
50 case TYPE_STORE_ENTRY
:
51 entry
->repl
.data
= value
;
55 entry
->mem_obj
->repl
.data
= value
;
65 MEMPROXY_CLASS(LruNode
);
68 /* Note: the dlink_node MUST be the first member of the LruNode
69 * structure. This member is later pointer typecasted to LruNode *.
74 static int nr_lru_policies
= 0;
77 lru_add(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
79 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
82 node
->data
= lru_node
= new LruNode
;
83 dlinkAddTail(entry
, &lru_node
->node
, &lru
->list
);
87 lru
->type
= repl_guessType(entry
, node
);
91 lru_remove(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
93 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
94 LruNode
*lru_node
= (LruNode
*)node
->data
;
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.
104 if (nullptr == lru_node
->node
.data
)
107 assert(lru_node
->node
.data
== entry
);
109 node
->data
= nullptr;
111 dlinkDelete(&lru_node
->node
, &lru
->list
);
119 lru_referenced(RemovalPolicy
* policy
, const StoreEntry
* entry
,
120 RemovalPolicyNode
* node
)
122 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
123 LruNode
*lru_node
= (LruNode
*)node
->data
;
128 dlinkDelete(&lru_node
->node
, &lru
->list
);
130 dlinkAddTail((void *) entry
, &lru_node
->node
, &lru
->list
);
133 /** RemovalPolicyWalker **/
135 typedef struct _LruWalkData LruWalkData
;
137 struct _LruWalkData
{
141 static const StoreEntry
*
142 lru_walkNext(RemovalPolicyWalker
* walker
)
144 LruWalkData
*lru_walk
= (LruWalkData
*)walker
->_data
;
145 LruNode
*lru_node
= lru_walk
->current
;
150 lru_walk
->current
= (LruNode
*) lru_node
->node
.next
;
152 return (StoreEntry
*) lru_node
->node
.data
;
156 lru_walkDone(RemovalPolicyWalker
* walker
)
158 RemovalPolicy
*policy
= walker
->_policy
;
159 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
160 assert(strcmp(policy
->_type
, "lru") == 0);
161 assert(lru
->nwalkers
> 0);
163 safe_free(walker
->_data
);
167 static RemovalPolicyWalker
*
168 lru_walkInit(RemovalPolicy
* policy
)
170 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
171 RemovalPolicyWalker
*walker
;
172 LruWalkData
*lru_walk
;
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
;
184 /** RemovalPurgeWalker **/
186 typedef struct _LruPurgeData LruPurgeData
;
188 struct _LruPurgeData
{
194 lru_purgeNext(RemovalPurgeWalker
* walker
)
196 LruPurgeData
*lru_walker
= (LruPurgeData
*)walker
->_data
;
197 RemovalPolicy
*policy
= walker
->_policy
;
198 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
203 lru_node
= lru_walker
->current
;
205 if (!lru_node
|| walker
->scanned
>= walker
->max_scan
)
208 walker
->scanned
+= 1;
210 lru_walker
->current
= (LruNode
*) lru_node
->node
.next
;
212 if (lru_walker
->current
== lru_walker
->start
) {
213 /* Last node found */
214 lru_walker
->current
= nullptr;
217 entry
= (StoreEntry
*) lru_node
->node
.data
;
218 dlinkDelete(&lru_node
->node
, &lru
->list
);
220 if (entry
->locked()) {
221 /* Shit, it is locked. we can't return this one */
223 dlinkAddTail(entry
, &lru_node
->node
, &lru
->list
);
229 lru
->setPolicyNode(entry
, nullptr);
234 lru_purgeDone(RemovalPurgeWalker
* walker
)
236 RemovalPolicy
*policy
= walker
->_policy
;
237 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
238 assert(strcmp(policy
->_type
, "lru") == 0);
239 assert(lru
->nwalkers
> 0);
241 safe_free(walker
->_data
);
245 static RemovalPurgeWalker
*
246 lru_purgeInit(RemovalPolicy
* policy
, int max_scan
)
248 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
249 RemovalPurgeWalker
*walker
;
250 LruPurgeData
*lru_walk
;
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
;
264 lru_stats(RemovalPolicy
* policy
, StoreEntry
* sentry
)
266 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
267 LruNode
*lru_node
= (LruNode
*) lru
->list
.head
;
272 StoreEntry
*entry
= (StoreEntry
*) lru_node
->node
.data
;
274 if (entry
->locked()) {
275 lru_node
= (LruNode
*) lru_node
->node
.next
;
279 storeAppendPrintf(sentry
, "LRU reference age: %.2f days\n", (double) (squid_curtime
- entry
->lastref
) / (double) (24 * 60 * 60));
284 lru_free(RemovalPolicy
* policy
)
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
);
291 /* Ok, time to destroy this policy */
293 memset(policy
, 0, sizeof(*policy
));
298 createRemovalPolicy_lru(wordlist
* args
)
300 RemovalPolicy
*policy
;
301 LruPolicyData
*lru_data
;
302 /* no arguments expected or understood */
305 /* Allocate the needed structures */
306 lru_data
= (LruPolicyData
*)xcalloc(1, sizeof(*lru_data
));
308 policy
= new RemovalPolicy
;
310 /* Initialize the URL data */
311 lru_data
->policy
= policy
;
313 /* Populate the policy structure */
314 policy
->_type
= "lru";
316 policy
->_data
= lru_data
;
318 policy
->Free
= lru_free
;
320 policy
->Add
= lru_add
;
322 policy
->Remove
= lru_remove
;
324 policy
->Referenced
= lru_referenced
;
326 policy
->Dereferenced
= lru_referenced
;
328 policy
->WalkInit
= lru_walkInit
;
330 policy
->PurgeInit
= lru_purgeInit
;
332 policy
->Stats
= lru_stats
;
334 /* Increase policy usage count */
335 nr_lru_policies
+= 0;