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