]>
Commit | Line | Data |
---|---|---|
6a566b9c | 1 | |
2 | /* | |
507d0a78 | 3 | * DEBUG: section 81 Store HEAP Removal Policies |
6a566b9c | 4 | * AUTHOR: Henrik Nordstrom |
5 | * | |
b6a7f52c | 6 | * Based on the ideas of the heap policy implemented by John Dilley of |
6095abfe | 7 | * Hewlett Packard. Rewritten from scratch when modularizing the removal |
8 | * policy implementation of Squid. | |
b6a7f52c | 9 | * |
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 | |
12 | * | |
26ac0430 | 13 | * |
2b6662ba | 14 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
6a566b9c | 15 | * ---------------------------------------------------------- |
16 | * | |
2b6662ba | 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. | |
6a566b9c | 25 | * |
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. | |
26ac0430 | 30 | * |
6a566b9c | 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. | |
26ac0430 | 35 | * |
6a566b9c | 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. | |
39 | * | |
40 | */ | |
41 | ||
582c2af2 | 42 | #include "squid.h" |
6a566b9c | 43 | #include "heap.h" |
602d9612 | 44 | #include "MemObject.h" |
41c97755 | 45 | #include "SquidList.h" |
e6ccf245 | 46 | #include "Store.h" |
602d9612 | 47 | #include "store_heap_replacement.h" |
d295d770 | 48 | #include "wordlist.h" |
6a566b9c | 49 | |
50 | REMOVALPOLICYCREATE createRemovalPolicy_heap; | |
51 | ||
52 | static int nr_heap_policies = 0; | |
53 | ||
26ac0430 | 54 | struct HeapPolicyData { |
e6ccf245 | 55 | void setPolicyNode (StoreEntry *, void *) const; |
6a566b9c | 56 | RemovalPolicy *policy; |
e6ccf245 | 57 | heap *theHeap; |
6a566b9c | 58 | heap_key_func *keyfunc; |
59 | int count; | |
60 | int nwalkers; | |
be1ed2a4 | 61 | enum heap_entry_type { |
62e76326 | 62 | TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM |
be1ed2a4 | 63 | } type; |
6a566b9c | 64 | }; |
65 | ||
66 | /* Hack to avoid having to remember the RemovalPolicyNode location. | |
67 | * Needed by the purge walker. | |
68 | */ | |
e6ccf245 | 69 | static enum HeapPolicyData::heap_entry_type |
6a566b9c | 70 | heap_guessType(StoreEntry * entry, RemovalPolicyNode * node) |
71 | { | |
72 | if (node == &entry->repl) | |
62e76326 | 73 | return HeapPolicyData::TYPE_STORE_ENTRY; |
74 | ||
6a566b9c | 75 | if (entry->mem_obj && node == &entry->mem_obj->repl) |
62e76326 | 76 | return HeapPolicyData::TYPE_STORE_MEM; |
77 | ||
6a566b9c | 78 | fatal("Heap Replacement: Unknown StoreEntry node type"); |
62e76326 | 79 | |
e6ccf245 | 80 | return HeapPolicyData::TYPE_UNKNOWN; |
6a566b9c | 81 | } |
e6ccf245 | 82 | |
83 | void | |
84 | HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const | |
85 | { | |
86 | switch (type) { | |
62e76326 | 87 | |
88 | case TYPE_STORE_ENTRY: | |
89 | entry->repl.data = value; | |
90 | break ; | |
91 | ||
92 | case TYPE_STORE_MEM: | |
93 | entry->mem_obj->repl.data = value ; | |
94 | break ; | |
95 | ||
96 | default: | |
97 | break; | |
6a566b9c | 98 | } |
e6ccf245 | 99 | } |
6a566b9c | 100 | |
101 | static void | |
102 | heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) | |
103 | { | |
eb898410 | 104 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 105 | assert(!node->data); |
62e76326 | 106 | |
6a566b9c | 107 | if (EBIT_TEST(entry->flags, ENTRY_SPECIAL)) |
62e76326 | 108 | return; /* We won't manage these.. they messes things up */ |
109 | ||
eb898410 | 110 | node->data = heap_insert(h->theHeap, entry); |
62e76326 | 111 | |
eb898410 | 112 | h->count += 1; |
62e76326 | 113 | |
eb898410 AJ |
114 | if (!h->type) |
115 | h->type = heap_guessType(entry, node); | |
62e76326 | 116 | |
6a566b9c | 117 | /* Add a little more variance to the aging factor */ |
eb898410 | 118 | h->theHeap->age += h->theHeap->age / 100000000; |
6a566b9c | 119 | } |
120 | ||
121 | static void | |
122 | heap_remove(RemovalPolicy * policy, StoreEntry * entry, | |
62e76326 | 123 | RemovalPolicyNode * node) |
6a566b9c | 124 | { |
eb898410 | 125 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
e6ccf245 | 126 | heap_node *hnode = (heap_node *)node->data; |
62e76326 | 127 | |
6a566b9c | 128 | if (!hnode) |
62e76326 | 129 | return; |
130 | ||
eb898410 | 131 | heap_delete(h->theHeap, hnode); |
62e76326 | 132 | |
6a566b9c | 133 | node->data = NULL; |
62e76326 | 134 | |
eb898410 | 135 | h->count -= 1; |
6a566b9c | 136 | } |
137 | ||
138 | static void | |
139 | heap_referenced(RemovalPolicy * policy, const StoreEntry * entry, | |
62e76326 | 140 | RemovalPolicyNode * node) |
6a566b9c | 141 | { |
eb898410 | 142 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
e6ccf245 | 143 | heap_node *hnode = (heap_node *)node->data; |
62e76326 | 144 | |
6a566b9c | 145 | if (!hnode) |
62e76326 | 146 | return; |
147 | ||
eb898410 | 148 | heap_update(h->theHeap, hnode, (StoreEntry *) entry); |
6a566b9c | 149 | } |
150 | ||
151 | /** RemovalPolicyWalker **/ | |
152 | ||
153 | typedef struct _HeapWalkData HeapWalkData; | |
62e76326 | 154 | |
26ac0430 | 155 | struct _HeapWalkData { |
e6ccf245 | 156 | size_t current; |
6a566b9c | 157 | }; |
158 | ||
2d72d4fd | 159 | static const StoreEntry * |
6a566b9c | 160 | heap_walkNext(RemovalPolicyWalker * walker) |
161 | { | |
e6ccf245 | 162 | HeapWalkData *heap_walk = (HeapWalkData *)walker->_data; |
6a566b9c | 163 | RemovalPolicy *policy = walker->_policy; |
eb898410 | 164 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 165 | StoreEntry *entry; |
62e76326 | 166 | |
eb898410 | 167 | if (heap_walk->current >= heap_nodes(h->theHeap)) |
62e76326 | 168 | return NULL; /* done */ |
169 | ||
eb898410 | 170 | entry = (StoreEntry *) heap_peep(h->theHeap, heap_walk->current++); |
62e76326 | 171 | |
6a566b9c | 172 | return entry; |
173 | } | |
174 | ||
175 | static void | |
176 | heap_walkDone(RemovalPolicyWalker * walker) | |
177 | { | |
178 | RemovalPolicy *policy = walker->_policy; | |
eb898410 | 179 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 180 | assert(strcmp(policy->_type, "heap") == 0); |
eb898410 AJ |
181 | assert(h->nwalkers > 0); |
182 | h->nwalkers -= 1; | |
6a566b9c | 183 | safe_free(walker->_data); |
aa839030 | 184 | delete walker; |
6a566b9c | 185 | } |
186 | ||
187 | static RemovalPolicyWalker * | |
188 | heap_walkInit(RemovalPolicy * policy) | |
189 | { | |
eb898410 | 190 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 191 | RemovalPolicyWalker *walker; |
192 | HeapWalkData *heap_walk; | |
eb898410 | 193 | h->nwalkers += 1; |
aa839030 | 194 | walker = new RemovalPolicyWalker; |
e6ccf245 | 195 | heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk)); |
6a566b9c | 196 | heap_walk->current = 0; |
197 | walker->_policy = policy; | |
198 | walker->_data = heap_walk; | |
199 | walker->Next = heap_walkNext; | |
200 | walker->Done = heap_walkDone; | |
6a566b9c | 201 | return walker; |
202 | } | |
203 | ||
204 | /** RemovalPurgeWalker **/ | |
205 | ||
206 | typedef struct _HeapPurgeData HeapPurgeData; | |
62e76326 | 207 | |
26ac0430 | 208 | struct _HeapPurgeData { |
6a566b9c | 209 | link_list *locked_entries; |
210 | heap_key min_age; | |
211 | }; | |
212 | ||
213 | static StoreEntry * | |
214 | heap_purgeNext(RemovalPurgeWalker * walker) | |
215 | { | |
e6ccf245 | 216 | HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data; |
6a566b9c | 217 | RemovalPolicy *policy = walker->_policy; |
eb898410 | 218 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 219 | StoreEntry *entry; |
220 | heap_key age; | |
62e76326 | 221 | |
222 | try_again: | |
223 | ||
eb898410 | 224 | if (!heap_nodes(h->theHeap) > 0) |
62e76326 | 225 | return NULL; /* done */ |
226 | ||
eb898410 | 227 | age = heap_peepminkey(h->theHeap); |
62e76326 | 228 | |
eb898410 | 229 | entry = (StoreEntry *)heap_extractmin(h->theHeap); |
62e76326 | 230 | |
3900307b | 231 | if (entry->locked()) { |
34266cde | 232 | |
3d0ac046 | 233 | entry->lock(); |
62e76326 | 234 | linklistPush(&heap_walker->locked_entries, entry); |
34266cde | 235 | |
62e76326 | 236 | goto try_again; |
6a566b9c | 237 | } |
62e76326 | 238 | |
6a566b9c | 239 | heap_walker->min_age = age; |
eb898410 | 240 | h->setPolicyNode(entry, NULL); |
6a566b9c | 241 | return entry; |
242 | } | |
243 | ||
244 | static void | |
245 | heap_purgeDone(RemovalPurgeWalker * walker) | |
246 | { | |
e6ccf245 | 247 | HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data; |
6a566b9c | 248 | RemovalPolicy *policy = walker->_policy; |
eb898410 | 249 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 250 | StoreEntry *entry; |
251 | assert(strcmp(policy->_type, "heap") == 0); | |
eb898410 AJ |
252 | assert(h->nwalkers > 0); |
253 | h->nwalkers -= 1; | |
62e76326 | 254 | |
6a566b9c | 255 | if (heap_walker->min_age > 0) { |
eb898410 AJ |
256 | h->theHeap->age = heap_walker->min_age; |
257 | debugs(81, 3, "Heap age set to " << h->theHeap->age); | |
6a566b9c | 258 | } |
62e76326 | 259 | |
6a566b9c | 260 | /* |
261 | * Reinsert the locked entries | |
262 | */ | |
e6ccf245 | 263 | while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) { |
eb898410 AJ |
264 | heap_node *node = heap_insert(h->theHeap, entry); |
265 | h->setPolicyNode(entry, node); | |
97b5e68f | 266 | entry->unlock(); |
6a566b9c | 267 | } |
62e76326 | 268 | |
6a566b9c | 269 | safe_free(walker->_data); |
aa839030 | 270 | delete walker; |
6a566b9c | 271 | } |
272 | ||
273 | static RemovalPurgeWalker * | |
274 | heap_purgeInit(RemovalPolicy * policy, int max_scan) | |
275 | { | |
eb898410 | 276 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 277 | RemovalPurgeWalker *walker; |
278 | HeapPurgeData *heap_walk; | |
eb898410 | 279 | h->nwalkers += 1; |
aa839030 | 280 | walker = new RemovalPurgeWalker; |
e6ccf245 | 281 | heap_walk = (HeapPurgeData *)xcalloc(1, sizeof(*heap_walk)); |
6a566b9c | 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; | |
6a566b9c | 289 | return walker; |
290 | } | |
291 | ||
292 | static void | |
293 | heap_free(RemovalPolicy * policy) | |
294 | { | |
eb898410 | 295 | HeapPolicyData *h = (HeapPolicyData *)policy->_data; |
6a566b9c | 296 | /* Make some verification of the policy state */ |
297 | assert(strcmp(policy->_type, "heap") == 0); | |
eb898410 AJ |
298 | assert(h->nwalkers); |
299 | assert(h->count); | |
6a566b9c | 300 | /* Ok, time to destroy this policy */ |
eb898410 | 301 | safe_free(h); |
6a566b9c | 302 | memset(policy, 0, sizeof(*policy)); |
aa839030 | 303 | delete policy; |
6a566b9c | 304 | } |
305 | ||
306 | RemovalPolicy * | |
307 | createRemovalPolicy_heap(wordlist * args) | |
308 | { | |
309 | RemovalPolicy *policy; | |
310 | HeapPolicyData *heap_data; | |
c193c972 | 311 | const char *keytype; |
6a566b9c | 312 | /* Allocate the needed structures */ |
aa839030 | 313 | policy = new RemovalPolicy; |
e6ccf245 | 314 | heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data)); |
6a566b9c | 315 | /* Initialize the policy data */ |
316 | heap_data->policy = policy; | |
62e76326 | 317 | |
6a566b9c | 318 | if (args) { |
62e76326 | 319 | keytype = args->key; |
320 | args = args->next; | |
6a566b9c | 321 | } else { |
e0236918 | 322 | debugs(81, DBG_IMPORTANT, "createRemovalPolicy_heap: No key type specified. Using LRU"); |
62e76326 | 323 | keytype = "LRU"; |
6a566b9c | 324 | } |
62e76326 | 325 | |
6a566b9c | 326 | if (!strcmp(keytype, "GDSF")) |
62e76326 | 327 | heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF; |
6a566b9c | 328 | else if (!strcmp(keytype, "LFUDA")) |
62e76326 | 329 | heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA; |
6a566b9c | 330 | else if (!strcmp(keytype, "LRU")) |
62e76326 | 331 | heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU; |
6a566b9c | 332 | else { |
fa84c01d | 333 | debugs(81, DBG_CRITICAL, "createRemovalPolicy_heap: Unknown key type \"" << keytype << "\". Using LRU"); |
62e76326 | 334 | heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU; |
6a566b9c | 335 | } |
62e76326 | 336 | |
6a566b9c | 337 | /* No additional arguments expected */ |
f6574e11 AJ |
338 | while (args) { |
339 | debugs(81, DBG_IMPORTANT, "WARNING: discarding unknown removal policy '" << args->key << "'"); | |
340 | args = args->next; | |
341 | } | |
62e76326 | 342 | |
e6ccf245 | 343 | heap_data->theHeap = new_heap(1000, heap_data->keyfunc); |
62e76326 | 344 | |
e6ccf245 | 345 | heap_data->theHeap->age = 1.0; |
62e76326 | 346 | |
6a566b9c | 347 | /* Populate the policy structure */ |
348 | policy->_type = "heap"; | |
62e76326 | 349 | |
6a566b9c | 350 | policy->_data = heap_data; |
62e76326 | 351 | |
6a566b9c | 352 | policy->Free = heap_free; |
62e76326 | 353 | |
6a566b9c | 354 | policy->Add = heap_add; |
62e76326 | 355 | |
6a566b9c | 356 | policy->Remove = heap_remove; |
62e76326 | 357 | |
6a566b9c | 358 | policy->Referenced = NULL; |
62e76326 | 359 | |
6a566b9c | 360 | policy->Dereferenced = heap_referenced; |
62e76326 | 361 | |
6a566b9c | 362 | policy->WalkInit = heap_walkInit; |
62e76326 | 363 | |
6a566b9c | 364 | policy->PurgeInit = heap_purgeInit; |
62e76326 | 365 | |
6a566b9c | 366 | /* Increase policy usage count */ |
367 | nr_heap_policies += 0; | |
62e76326 | 368 | |
6a566b9c | 369 | return policy; |
370 | } |