3 * DEBUG: section 81 Store HEAP Removal Policies
4 * AUTHOR: Henrik Nordstrom
6 * Based on the ideas of the heap policy implemented by John Dilley of
7 * Hewlett Packard. Rewritten from scratch when modularizing the removal
8 * policy implementation of Squid.
10 * For details on the original heap policy work and the thinking behind see
11 * http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
14 * SQUID Web Proxy Cache http://www.squid-cache.org/
15 * ----------------------------------------------------------
17 * Squid is the result of efforts by numerous individuals from
18 * the Internet community; see the CONTRIBUTORS file for full
19 * details. Many organizations have provided support for Squid's
20 * development; see the SPONSORS file for full details. Squid is
21 * Copyrighted (C) 2001 by the Regents of the University of
22 * California; see the COPYRIGHT file for full details. Squid
23 * incorporates software developed and/or copyrighted by other
24 * sources; see the CREDITS file for full details.
26 * This program is free software; you can redistribute it and/or modify
27 * it under the terms of the GNU General Public License as published by
28 * the Free Software Foundation; either version 2 of the License, or
29 * (at your option) any later version.
31 * This program is distributed in the hope that it will be useful,
32 * but WITHOUT ANY WARRANTY; without even the implied warranty of
33 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
34 * GNU General Public License for more details.
36 * You should have received a copy of the GNU General Public License
37 * along with this program; if not, write to the Free Software
38 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
44 #include "store_heap_replacement.h"
45 #include "SquidList.h"
47 #include "MemObject.h"
50 REMOVALPOLICYCREATE createRemovalPolicy_heap
;
52 static int nr_heap_policies
= 0;
54 struct HeapPolicyData
{
55 void setPolicyNode (StoreEntry
*, void *) const;
56 RemovalPolicy
*policy
;
58 heap_key_func
*keyfunc
;
61 enum heap_entry_type
{
62 TYPE_UNKNOWN
= 0, TYPE_STORE_ENTRY
, TYPE_STORE_MEM
66 /* Hack to avoid having to remember the RemovalPolicyNode location.
67 * Needed by the purge walker.
69 static enum HeapPolicyData::heap_entry_type
70 heap_guessType(StoreEntry
* entry
, RemovalPolicyNode
* node
)
72 if (node
== &entry
->repl
)
73 return HeapPolicyData::TYPE_STORE_ENTRY
;
75 if (entry
->mem_obj
&& node
== &entry
->mem_obj
->repl
)
76 return HeapPolicyData::TYPE_STORE_MEM
;
78 fatal("Heap Replacement: Unknown StoreEntry node type");
80 return HeapPolicyData::TYPE_UNKNOWN
;
84 HeapPolicyData::setPolicyNode (StoreEntry
*entry
, void *value
) const
88 case TYPE_STORE_ENTRY
:
89 entry
->repl
.data
= value
;
93 entry
->mem_obj
->repl
.data
= value
;
102 heap_add(RemovalPolicy
* policy
, StoreEntry
* entry
, RemovalPolicyNode
* node
)
104 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
107 if (EBIT_TEST(entry
->flags
, ENTRY_SPECIAL
))
108 return; /* We won't manage these.. they messes things up */
110 node
->data
= heap_insert(heap
->theHeap
, entry
);
115 heap
->type
= heap_guessType(entry
, node
);
117 /* Add a little more variance to the aging factor */
118 heap
->theHeap
->age
+= heap
->theHeap
->age
/ 100000000;
122 heap_remove(RemovalPolicy
* policy
, StoreEntry
* entry
,
123 RemovalPolicyNode
* node
)
125 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
126 heap_node
*hnode
= (heap_node
*)node
->data
;
131 heap_delete(heap
->theHeap
, hnode
);
139 heap_referenced(RemovalPolicy
* policy
, const StoreEntry
* entry
,
140 RemovalPolicyNode
* node
)
142 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
143 heap_node
*hnode
= (heap_node
*)node
->data
;
148 heap_update(heap
->theHeap
, hnode
, (StoreEntry
*) entry
);
151 /** RemovalPolicyWalker **/
153 typedef struct _HeapWalkData HeapWalkData
;
155 struct _HeapWalkData
{
159 static const StoreEntry
*
160 heap_walkNext(RemovalPolicyWalker
* walker
)
162 HeapWalkData
*heap_walk
= (HeapWalkData
*)walker
->_data
;
163 RemovalPolicy
*policy
= walker
->_policy
;
164 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
167 if (heap_walk
->current
>= heap_nodes(heap
->theHeap
))
168 return NULL
; /* done */
170 entry
= (StoreEntry
*) heap_peep(heap
->theHeap
, heap_walk
->current
++);
176 heap_walkDone(RemovalPolicyWalker
* walker
)
178 RemovalPolicy
*policy
= walker
->_policy
;
179 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
180 assert(strcmp(policy
->_type
, "heap") == 0);
181 assert(heap
->nwalkers
> 0);
183 safe_free(walker
->_data
);
187 static RemovalPolicyWalker
*
188 heap_walkInit(RemovalPolicy
* policy
)
190 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
191 RemovalPolicyWalker
*walker
;
192 HeapWalkData
*heap_walk
;
194 walker
= new RemovalPolicyWalker
;
195 heap_walk
= (HeapWalkData
*)xcalloc(1, sizeof(*heap_walk
));
196 heap_walk
->current
= 0;
197 walker
->_policy
= policy
;
198 walker
->_data
= heap_walk
;
199 walker
->Next
= heap_walkNext
;
200 walker
->Done
= heap_walkDone
;
204 /** RemovalPurgeWalker **/
206 typedef struct _HeapPurgeData HeapPurgeData
;
208 struct _HeapPurgeData
{
209 link_list
*locked_entries
;
214 heap_purgeNext(RemovalPurgeWalker
* walker
)
216 HeapPurgeData
*heap_walker
= (HeapPurgeData
*)walker
->_data
;
217 RemovalPolicy
*policy
= walker
->_policy
;
218 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
224 if (!heap_nodes(heap
->theHeap
) > 0)
225 return NULL
; /* done */
227 age
= heap_peepminkey(heap
->theHeap
);
229 entry
= (StoreEntry
*)heap_extractmin(heap
->theHeap
);
231 if (entry
->locked()) {
234 linklistPush(&heap_walker
->locked_entries
, entry
);
239 heap_walker
->min_age
= age
;
240 heap
->setPolicyNode(entry
, NULL
);
245 heap_purgeDone(RemovalPurgeWalker
* walker
)
247 HeapPurgeData
*heap_walker
= (HeapPurgeData
*)walker
->_data
;
248 RemovalPolicy
*policy
= walker
->_policy
;
249 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
251 assert(strcmp(policy
->_type
, "heap") == 0);
252 assert(heap
->nwalkers
> 0);
255 if (heap_walker
->min_age
> 0) {
256 heap
->theHeap
->age
= heap_walker
->min_age
;
257 debugs(81, 3, "heap_purgeDone: Heap age set to " << heap
->theHeap
->age
);
261 * Reinsert the locked entries
263 while ((entry
= (StoreEntry
*)linklistShift(&heap_walker
->locked_entries
))) {
264 heap_node
*node
= heap_insert(heap
->theHeap
, entry
);
265 heap
->setPolicyNode(entry
, node
);
269 safe_free(walker
->_data
);
273 static RemovalPurgeWalker
*
274 heap_purgeInit(RemovalPolicy
* policy
, int max_scan
)
276 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
277 RemovalPurgeWalker
*walker
;
278 HeapPurgeData
*heap_walk
;
280 walker
= new RemovalPurgeWalker
;
281 heap_walk
= (HeapPurgeData
*)xcalloc(1, sizeof(*heap_walk
));
282 heap_walk
->min_age
= 0.0;
283 heap_walk
->locked_entries
= NULL
;
284 walker
->_policy
= policy
;
285 walker
->_data
= heap_walk
;
286 walker
->max_scan
= max_scan
;
287 walker
->Next
= heap_purgeNext
;
288 walker
->Done
= heap_purgeDone
;
293 heap_free(RemovalPolicy
* policy
)
295 HeapPolicyData
*heap
= (HeapPolicyData
*)policy
->_data
;
296 /* Make some verification of the policy state */
297 assert(strcmp(policy
->_type
, "heap") == 0);
298 assert(heap
->nwalkers
);
300 /* Ok, time to destroy this policy */
302 memset(policy
, 0, sizeof(*policy
));
307 createRemovalPolicy_heap(wordlist
* args
)
309 RemovalPolicy
*policy
;
310 HeapPolicyData
*heap_data
;
312 /* Allocate the needed structures */
313 policy
= new RemovalPolicy
;
314 heap_data
= (HeapPolicyData
*)xcalloc(1, sizeof(*heap_data
));
315 /* Initialize the policy data */
316 heap_data
->policy
= policy
;
322 debugs(81, DBG_IMPORTANT
, "createRemovalPolicy_heap: No key type specified. Using LRU");
326 if (!strcmp(keytype
, "GDSF"))
327 heap_data
->keyfunc
= HeapKeyGen_StoreEntry_GDSF
;
328 else if (!strcmp(keytype
, "LFUDA"))
329 heap_data
->keyfunc
= HeapKeyGen_StoreEntry_LFUDA
;
330 else if (!strcmp(keytype
, "LRU"))
331 heap_data
->keyfunc
= HeapKeyGen_StoreEntry_LRU
;
333 debugs(81, DBG_CRITICAL
, "createRemovalPolicy_heap: Unknown key type \"" << keytype
<< "\". Using LRU");
334 heap_data
->keyfunc
= HeapKeyGen_StoreEntry_LRU
;
337 /* No additional arguments expected */
339 debugs(81, DBG_IMPORTANT
, "WARNING: discarding unknown removal policy '" << args
->key
<< "'");
343 heap_data
->theHeap
= new_heap(1000, heap_data
->keyfunc
);
345 heap_data
->theHeap
->age
= 1.0;
347 /* Populate the policy structure */
348 policy
->_type
= "heap";
350 policy
->_data
= heap_data
;
352 policy
->Free
= heap_free
;
354 policy
->Add
= heap_add
;
356 policy
->Remove
= heap_remove
;
358 policy
->Referenced
= NULL
;
360 policy
->Dereferenced
= heap_referenced
;
362 policy
->WalkInit
= heap_walkInit
;
364 policy
->PurgeInit
= heap_purgeInit
;
366 /* Increase policy usage count */
367 nr_heap_policies
+= 0;