3 * DEBUG: none LRU Removal Policy
4 * AUTHOR: Henrik Nordstrom
6 * SQUID Web Proxy Cache http://www.squid-cache.org/
7 * ----------------------------------------------------------
9 * Squid is the result of efforts by numerous individuals from
10 * the Internet community; see the CONTRIBUTORS file for full
11 * details. Many organizations have provided support for Squid's
12 * development; see the SPONSORS file for full details. Squid is
13 * Copyrighted (C) 2001 by the Regents of the University of
14 * California; see the COPYRIGHT file for full details. Squid
15 * incorporates software developed and/or copyrighted by other
16 * sources; see the CREDITS file for full details.
18 * This program is free software; you can redistribute it and/or modify
19 * it under the terms of the GNU General Public License as published by
20 * the Free Software Foundation; either version 2 of the License, or
21 * (at your option) any later version.
23 * This program is distributed in the hope that it will be useful,
24 * but WITHOUT ANY WARRANTY; without even the implied warranty of
25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 * GNU General Public License for more details.
28 * You should have received a copy of the GNU General Public License
29 * along with this program; if not, write to the Free Software
30 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
36 #include "MemObject.h"
37 #include "SquidTime.h"
39 REMOVALPOLICYCREATE createRemovalPolicy_lru
;
41 struct LruPolicyData
{
42 void setPolicyNode (StoreEntry
*, void *) const;
43 RemovalPolicy
*policy
;
47 enum heap_entry_type
{
48 TYPE_UNKNOWN
= 0, TYPE_STORE_ENTRY
, TYPE_STORE_MEM
52 /* Hack to avoid having to remember the RemovalPolicyNode location.
53 * Needed by the purge walker to clear the policy information
55 static enum LruPolicyData::heap_entry_type
56 repl_guessType(StoreEntry
* entry
, RemovalPolicyNode
* node
)
58 if (node
== &entry
->repl
)
59 return LruPolicyData::TYPE_STORE_ENTRY
;
61 if (entry
->mem_obj
&& node
== &entry
->mem_obj
->repl
)
62 return LruPolicyData::TYPE_STORE_MEM
;
64 fatal("Heap Replacement: Unknown StoreEntry node type");
66 return LruPolicyData::TYPE_UNKNOWN
;
70 LruPolicyData::setPolicyNode (StoreEntry
*entry
, void *value
) const
74 case TYPE_STORE_ENTRY
:
75 entry
->repl
.data
= value
;
79 entry
->mem_obj
->repl
.data
= value
;
87 typedef struct _LruNode LruNode
;
90 /* Note: the dlink_node MUST be the first member of the LruNode
91 * structure. This member is later pointer typecasted to LruNode *.
96 static MemAllocator
*lru_node_pool
= NULL
;
97 static int nr_lru_policies
= 0;
100 lru_add(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
102 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
105 node
->data
= lru_node
= (LruNode
*)lru_node_pool
->alloc();
106 dlinkAddTail(entry
, &lru_node
->node
, &lru
->list
);
110 lru
->type
= repl_guessType(entry
, node
);
114 lru_remove(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
116 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
117 LruNode
*lru_node
= (LruNode
*)node
->data
;
123 * It seems to be possible for an entry to exist in the hash
124 * but not be in the LRU list, so check for that case rather
125 * than suffer a NULL pointer access.
127 if (NULL
== lru_node
->node
.data
)
130 assert(lru_node
->node
.data
== entry
);
134 dlinkDelete(&lru_node
->node
, &lru
->list
);
136 lru_node_pool
->freeOne(lru_node
);
142 lru_referenced(RemovalPolicy
* policy
, const StoreEntry
* entry
,
143 RemovalPolicyNode
* node
)
145 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
146 LruNode
*lru_node
= (LruNode
*)node
->data
;
151 dlinkDelete(&lru_node
->node
, &lru
->list
);
153 dlinkAddTail((void *) entry
, &lru_node
->node
, &lru
->list
);
156 /** RemovalPolicyWalker **/
158 typedef struct _LruWalkData LruWalkData
;
160 struct _LruWalkData
{
164 static const StoreEntry
*
165 lru_walkNext(RemovalPolicyWalker
* walker
)
167 LruWalkData
*lru_walk
= (LruWalkData
*)walker
->_data
;
168 LruNode
*lru_node
= lru_walk
->current
;
173 lru_walk
->current
= (LruNode
*) lru_node
->node
.next
;
175 return (StoreEntry
*) lru_node
->node
.data
;
179 lru_walkDone(RemovalPolicyWalker
* walker
)
181 RemovalPolicy
*policy
= walker
->_policy
;
182 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
183 assert(strcmp(policy
->_type
, "lru") == 0);
184 assert(lru
->nwalkers
> 0);
186 safe_free(walker
->_data
);
190 static RemovalPolicyWalker
*
191 lru_walkInit(RemovalPolicy
* policy
)
193 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
194 RemovalPolicyWalker
*walker
;
195 LruWalkData
*lru_walk
;
197 walker
= new RemovalPolicyWalker
;
198 lru_walk
= (LruWalkData
*)xcalloc(1, sizeof(*lru_walk
));
199 walker
->_policy
= policy
;
200 walker
->_data
= lru_walk
;
201 walker
->Next
= lru_walkNext
;
202 walker
->Done
= lru_walkDone
;
203 lru_walk
->current
= (LruNode
*) lru
->list
.head
;
207 /** RemovalPurgeWalker **/
209 typedef struct _LruPurgeData LruPurgeData
;
211 struct _LruPurgeData
{
217 lru_purgeNext(RemovalPurgeWalker
* walker
)
219 LruPurgeData
*lru_walker
= (LruPurgeData
*)walker
->_data
;
220 RemovalPolicy
*policy
= walker
->_policy
;
221 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
226 lru_node
= lru_walker
->current
;
228 if (!lru_node
|| walker
->scanned
>= walker
->max_scan
)
231 walker
->scanned
+= 1;
233 lru_walker
->current
= (LruNode
*) lru_node
->node
.next
;
235 if (lru_walker
->current
== lru_walker
->start
) {
236 /* Last node found */
237 lru_walker
->current
= NULL
;
240 entry
= (StoreEntry
*) lru_node
->node
.data
;
241 dlinkDelete(&lru_node
->node
, &lru
->list
);
243 if (entry
->locked()) {
244 /* Shit, it is locked. we can't return this one */
246 dlinkAddTail(entry
, &lru_node
->node
, &lru
->list
);
250 lru_node_pool
->freeOne(lru_node
);
252 lru
->setPolicyNode(entry
, NULL
);
257 lru_purgeDone(RemovalPurgeWalker
* walker
)
259 RemovalPolicy
*policy
= walker
->_policy
;
260 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
261 assert(strcmp(policy
->_type
, "lru") == 0);
262 assert(lru
->nwalkers
> 0);
264 safe_free(walker
->_data
);
268 static RemovalPurgeWalker
*
269 lru_purgeInit(RemovalPolicy
* policy
, int max_scan
)
271 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
272 RemovalPurgeWalker
*walker
;
273 LruPurgeData
*lru_walk
;
275 walker
= new RemovalPurgeWalker
;
276 lru_walk
= (LruPurgeData
*)xcalloc(1, sizeof(*lru_walk
));
277 walker
->_policy
= policy
;
278 walker
->_data
= lru_walk
;
279 walker
->max_scan
= max_scan
;
280 walker
->Next
= lru_purgeNext
;
281 walker
->Done
= lru_purgeDone
;
282 lru_walk
->start
= lru_walk
->current
= (LruNode
*) lru
->list
.head
;
287 lru_stats(RemovalPolicy
* policy
, StoreEntry
* sentry
)
289 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
290 LruNode
*lru_node
= (LruNode
*) lru
->list
.head
;
295 StoreEntry
*entry
= (StoreEntry
*) lru_node
->node
.data
;
297 if (entry
->locked()) {
298 lru_node
= (LruNode
*) lru_node
->node
.next
;
302 storeAppendPrintf(sentry
, "LRU reference age: %.2f days\n", (double) (squid_curtime
- entry
->lastref
) / (double) (24 * 60 * 60));
307 lru_free(RemovalPolicy
* policy
)
309 LruPolicyData
*lru
= (LruPolicyData
*)policy
->_data
;
310 /* Make some verification of the policy state */
311 assert(strcmp(policy
->_type
, "lru") == 0);
312 assert(lru
->nwalkers
);
314 /* Ok, time to destroy this policy */
316 memset(policy
, 0, sizeof(*policy
));
321 createRemovalPolicy_lru(wordlist
* args
)
323 RemovalPolicy
*policy
;
324 LruPolicyData
*lru_data
;
325 /* no arguments expected or understood */
329 if (!lru_node_pool
) {
330 /* Must be chunked */
331 lru_node_pool
= memPoolCreate("LRU policy node", sizeof(LruNode
));
332 lru_node_pool
->setChunkSize(512 * 1024);
335 /* Allocate the needed structures */
336 lru_data
= (LruPolicyData
*)xcalloc(1, sizeof(*lru_data
));
338 policy
= new RemovalPolicy
;
340 /* Initialize the URL data */
341 lru_data
->policy
= policy
;
343 /* Populate the policy structure */
344 policy
->_type
= "lru";
346 policy
->_data
= lru_data
;
348 policy
->Free
= lru_free
;
350 policy
->Add
= lru_add
;
352 policy
->Remove
= lru_remove
;
354 policy
->Referenced
= lru_referenced
;
356 policy
->Dereferenced
= lru_referenced
;
358 policy
->WalkInit
= lru_walkInit
;
360 policy
->PurgeInit
= lru_purgeInit
;
362 policy
->Stats
= lru_stats
;
364 /* Increase policy usage count */
365 nr_lru_policies
+= 0;