3 * $Id: store_repl_lru.cc,v 1.6 2001/01/12 00:37:36 wessels Exp $
5 * DEBUG: section ? LRU Removal policy
6 * AUTHOR: Henrik Nordstrom
8 * SQUID Web Proxy Cache http://www.squid-cache.org/
9 * ----------------------------------------------------------
11 * Squid is the result of efforts by numerous individuals from
12 * the Internet community; see the CONTRIBUTORS file for full
13 * details. Many organizations have provided support for Squid's
14 * development; see the SPONSORS file for full details. Squid is
15 * Copyrighted (C) 2001 by the Regents of the University of
16 * California; see the COPYRIGHT file for full details. Squid
17 * incorporates software developed and/or copyrighted by other
18 * sources; see the CREDITS file for full details.
20 * This program is free software; you can redistribute it and/or modify
21 * it under the terms of the GNU General Public License as published by
22 * the Free Software Foundation; either version 2 of the License, or
23 * (at your option) any later version.
25 * This program is distributed in the hope that it will be useful,
26 * but WITHOUT ANY WARRANTY; without even the implied warranty of
27 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 * GNU General Public License for more details.
30 * You should have received a copy of the GNU General Public License
31 * along with this program; if not, write to the Free Software
32 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
38 REMOVALPOLICYCREATE createRemovalPolicy_lru
;
40 typedef struct _LruPolicyData LruPolicyData
;
41 struct _LruPolicyData
{
42 RemovalPolicy
*policy
;
46 enum heap_entry_type
{
47 TYPE_UNKNOWN
= 0, TYPE_STORE_ENTRY
, TYPE_STORE_MEM
51 /* Hack to avoid having to remember the RemovalPolicyNode location.
52 * Needed by the purge walker to clear the policy information
54 static enum heap_entry_type
55 repl_guessType(StoreEntry
* entry
, RemovalPolicyNode
* node
)
57 if (node
== &entry
->repl
)
58 return TYPE_STORE_ENTRY
;
59 if (entry
->mem_obj
&& node
== &entry
->mem_obj
->repl
)
60 return TYPE_STORE_MEM
;
61 fatal("Heap Replacement: Unknown StoreEntry node type");
64 #define SET_POLICY_NODE(entry,value) \
66 case TYPE_STORE_ENTRY: entry->repl.data = value; break ; \
67 case TYPE_STORE_MEM: entry->mem_obj->repl.data = value ; break ; \
71 typedef struct _LruNode LruNode
;
73 /* Note: the dlink_node MUST be the first member of the LruNode
74 * structure. This member is later pointer typecasted to LruNode *.
79 static MemPool
*lru_node_pool
= NULL
;
80 static int nr_lru_policies
= 0;
83 lru_add(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
85 LruPolicyData
*lru
= policy
->_data
;
88 node
->data
= lru_node
= memPoolAlloc(lru_node_pool
);
89 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
= policy
->_data
;
99 LruNode
*lru_node
= node
->data
;
103 * It seems to be possible for an entry to exist in the hash
104 * but not be in the LRU list, so check for that case rather
105 * than suffer a NULL pointer access.
107 if (NULL
== lru_node
->node
.data
)
109 assert(lru_node
->node
.data
== entry
);
111 dlinkDelete(&lru_node
->node
, &lru
->list
);
112 memPoolFree(lru_node_pool
, lru_node
);
117 lru_referenced(RemovalPolicy
* policy
, const StoreEntry
* entry
,
118 RemovalPolicyNode
* node
)
120 LruPolicyData
*lru
= policy
->_data
;
121 LruNode
*lru_node
= node
->data
;
124 dlinkDelete(&lru_node
->node
, &lru
->list
);
125 dlinkAddTail((void *) entry
, &lru_node
->node
, &lru
->list
);
128 /** RemovalPolicyWalker **/
130 typedef struct _LruWalkData LruWalkData
;
131 struct _LruWalkData
{
136 lru_walkNext(RemovalPolicyWalker
* walker
)
138 LruWalkData
*lru_walk
= walker
->_data
;
139 LruNode
*lru_node
= lru_walk
->current
;
142 lru_walk
->current
= (LruNode
*) lru_node
->node
.next
;
143 return (StoreEntry
*) lru_node
->node
.data
;
147 lru_walkDone(RemovalPolicyWalker
* walker
)
149 RemovalPolicy
*policy
= walker
->_policy
;
150 LruPolicyData
*lru
= policy
->_data
;
151 assert(strcmp(policy
->_type
, "lru") == 0);
152 assert(lru
->nwalkers
> 0);
154 safe_free(walker
->_data
);
158 static RemovalPolicyWalker
*
159 lru_walkInit(RemovalPolicy
* policy
)
161 LruPolicyData
*lru
= policy
->_data
;
162 RemovalPolicyWalker
*walker
;
163 LruWalkData
*lru_walk
;
165 walker
= CBDATA_ALLOC(RemovalPolicyWalker
, NULL
);
166 lru_walk
= xcalloc(1, sizeof(*lru_walk
));
167 walker
->_policy
= policy
;
168 walker
->_data
= lru_walk
;
169 walker
->Next
= lru_walkNext
;
170 walker
->Done
= lru_walkDone
;
171 lru_walk
->current
= (LruNode
*) lru
->list
.head
;
175 /** RemovalPurgeWalker **/
177 typedef struct _LruPurgeData LruPurgeData
;
178 struct _LruPurgeData
{
184 lru_purgeNext(RemovalPurgeWalker
* walker
)
186 LruPurgeData
*lru_walker
= walker
->_data
;
187 RemovalPolicy
*policy
= walker
->_policy
;
188 LruPolicyData
*lru
= policy
->_data
;
192 lru_node
= lru_walker
->current
;
193 if (!lru_node
|| walker
->scanned
>= walker
->max_scan
)
195 walker
->scanned
+= 1;
196 lru_walker
->current
= (LruNode
*) lru_node
->node
.next
;
197 if (lru_walker
->current
== lru_walker
->start
) {
198 /* Last node found */
199 lru_walker
->current
= NULL
;
201 entry
= (StoreEntry
*) lru_node
->node
.data
;
202 dlinkDelete(&lru_node
->node
, &lru
->list
);
203 if (storeEntryLocked(entry
)) {
204 /* Shit, it is locked. we can't return this one */
206 dlinkAddTail(entry
, &lru_node
->node
, &lru
->list
);
209 memPoolFree(lru_node_pool
, lru_node
);
211 SET_POLICY_NODE(entry
, NULL
);
216 lru_purgeDone(RemovalPurgeWalker
* walker
)
218 RemovalPolicy
*policy
= walker
->_policy
;
219 LruPolicyData
*lru
= policy
->_data
;
220 assert(strcmp(policy
->_type
, "lru") == 0);
221 assert(lru
->nwalkers
> 0);
223 safe_free(walker
->_data
);
227 static RemovalPurgeWalker
*
228 lru_purgeInit(RemovalPolicy
* policy
, int max_scan
)
230 LruPolicyData
*lru
= policy
->_data
;
231 RemovalPurgeWalker
*walker
;
232 LruPurgeData
*lru_walk
;
234 walker
= CBDATA_ALLOC(RemovalPurgeWalker
, NULL
);
235 lru_walk
= xcalloc(1, sizeof(*lru_walk
));
236 walker
->_policy
= policy
;
237 walker
->_data
= lru_walk
;
238 walker
->max_scan
= max_scan
;
239 walker
->Next
= lru_purgeNext
;
240 walker
->Done
= lru_purgeDone
;
241 lru_walk
->start
= lru_walk
->current
= (LruNode
*) lru
->list
.head
;
246 lru_free(RemovalPolicy
* policy
)
248 LruPolicyData
*lru
= policy
->_data
;
249 /* Make some verification of the policy state */
250 assert(strcmp(policy
->_type
, "lru") == 0);
251 assert(lru
->nwalkers
);
253 /* Ok, time to destroy this policy */
254 safe_free(policy
->_data
);
255 memset(policy
, 0, sizeof(*policy
));
260 createRemovalPolicy_lru(wordlist
* args
)
262 RemovalPolicy
*policy
;
263 LruPolicyData
*lru_data
;
264 /* no arguments expected or understood */
268 lru_node_pool
= memPoolCreate("LRU policy node", sizeof(LruNode
));
269 /* Allocate the needed structures */
270 lru_data
= xcalloc(1, sizeof(*lru_data
));
271 policy
= CBDATA_ALLOC(RemovalPolicy
, NULL
);
272 /* Initialize the URL data */
273 lru_data
->policy
= policy
;
274 /* Populate the policy structure */
275 policy
->_type
= "lru";
276 policy
->_data
= lru_data
;
277 policy
->Free
= lru_free
;
278 policy
->Add
= lru_add
;
279 policy
->Remove
= lru_remove
;
280 policy
->Referenced
= lru_referenced
;
281 policy
->Dereferenced
= lru_referenced
;
282 policy
->WalkInit
= lru_walkInit
;
283 policy
->PurgeInit
= lru_purgeInit
;
284 /* Increase policy usage count */
285 nr_lru_policies
+= 0;