src/repl/heap/store_repl_heap.cc

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