src/repl/heap/store_repl_heap.cc

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