src/repl/heap/store_repl_heap.cc

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