src/repl/heap/store_repl_heap.cc

   1
   2 /*
   3  * $Id$
   4  *
   5  * DEBUG: section 81    Store HEAP Removal Policies
   6  * AUTHOR: Henrik Nordstrom
   7  *
   8  * Based on the ideas of the heap policy implemented by John Dilley of
   9  * Hewlett Packard. Rewritten from scratch when modularizing the removal
  10  * policy implementation of Squid.
  11  *
  12  * For details on the original heap policy work and the thinking behind see
  13  * http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
  14  *
  15  *
  16  * SQUID Web Proxy Cache          http://www.squid-cache.org/
  17  * ----------------------------------------------------------
  18  *
  19  *  Squid is the result of efforts by numerous individuals from
  20  *  the Internet community; see the CONTRIBUTORS file for full
  21  *  details.   Many organizations have provided support for Squid's
  22  *  development; see the SPONSORS file for full details.  Squid is
  23  *  Copyrighted (C) 2001 by the Regents of the University of
  24  *  California; see the COPYRIGHT file for full details.  Squid
  25  *  incorporates software developed and/or copyrighted by other
  26  *  sources; see the CREDITS file for full details.
  27  *
  28  *  This program is free software; you can redistribute it and/or modify
  29  *  it under the terms of the GNU General Public License as published by
  30  *  the Free Software Foundation; either version 2 of the License, or
  31  *  (at your option) any later version.
  32  *
  33  *  This program is distributed in the hope that it will be useful,
  34  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  35  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  36  *  GNU General Public License for more details.
  37  *
  38  *  You should have received a copy of the GNU General Public License
  39  *  along with this program; if not, write to the Free Software
  40  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  41  *
  42  */
  43
  44 #include "squid.h"
  45 #include "heap.h"
  46 #include "protos.h"
  47 #include "store_heap_replacement.h"
  48 #include "Store.h"
  49 #include "MemObject.h"
  50 #include "wordlist.h"
  51
  52 REMOVALPOLICYCREATE createRemovalPolicy_heap;
  53
  54 static int nr_heap_policies = 0;
  55
  56 struct HeapPolicyData {
  57     void setPolicyNode (StoreEntry *, void *) const;
  58     RemovalPolicy *policy;
  59     heap *theHeap;
  60     heap_key_func *keyfunc;
  61     int count;
  62     int nwalkers;
  63     enum heap_entry_type {
  64         TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
  65     } type;
  66 };
  67
  68 /* Hack to avoid having to remember the RemovalPolicyNode location.
  69  * Needed by the purge walker.
  70  */
  71 static enum HeapPolicyData::heap_entry_type
  72 heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
  73 {
  74     if (node == &entry->repl)
  75         return HeapPolicyData::TYPE_STORE_ENTRY;
  76
  77     if (entry->mem_obj && node == &entry->mem_obj->repl)
  78         return HeapPolicyData::TYPE_STORE_MEM;
  79
  80     fatal("Heap Replacement: Unknown StoreEntry node type");
  81
  82     return HeapPolicyData::TYPE_UNKNOWN;
  83 }
  84
  85 void
  86 HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
  87 {
  88     switch (type) {
  89
  90     case TYPE_STORE_ENTRY:
  91         entry->repl.data = value;
  92         break ;
  93
  94     case TYPE_STORE_MEM:
  95         entry->mem_obj->repl.data = value ;
  96         break ;
  97
  98     default:
  99         break;
 100     }
 101 }
 102
 103 static void
 104 heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 105 {
 106     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 107     assert(!node->data);
 108
 109     if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
 110         return;                 /* We won't manage these.. they messes things up */
 111
 112     node->data = heap_insert(heap->theHeap, entry);
 113
 114     heap->count += 1;
 115
 116     if (!heap->type)
 117         heap->type = heap_guessType(entry, node);
 118
 119     /* Add a little more variance to the aging factor */
 120     heap->theHeap->age += heap->theHeap->age / 100000000;
 121 }
 122
 123 static void
 124 heap_remove(RemovalPolicy * policy, StoreEntry * entry,
 125             RemovalPolicyNode * node)
 126 {
 127     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 128     heap_node *hnode = (heap_node *)node->data;
 129
 130     if (!hnode)
 131         return;
 132
 133     heap_delete(heap->theHeap, hnode);
 134
 135     node->data = NULL;
 136
 137     heap->count -= 1;
 138 }
 139
 140 static void
 141 heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 142                 RemovalPolicyNode * node)
 143 {
 144     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 145     heap_node *hnode = (heap_node *)node->data;
 146
 147     if (!hnode)
 148         return;
 149
 150     heap_update(heap->theHeap, hnode, (StoreEntry *) entry);
 151 }
 152
 153 /** RemovalPolicyWalker **/
 154
 155 typedef struct _HeapWalkData HeapWalkData;
 156
 157 struct _HeapWalkData {
 158     size_t current;
 159 };
 160
 161 static const StoreEntry *
 162 heap_walkNext(RemovalPolicyWalker * walker)
 163 {
 164     HeapWalkData *heap_walk = (HeapWalkData *)walker->_data;
 165     RemovalPolicy *policy = walker->_policy;
 166     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 167     StoreEntry *entry;
 168
 169     if (heap_walk->current >= heap_nodes(heap->theHeap))
 170         return NULL;            /* done */
 171
 172     entry = (StoreEntry *) heap_peep(heap->theHeap, heap_walk->current++);
 173
 174     return entry;
 175 }
 176
 177 static void
 178 heap_walkDone(RemovalPolicyWalker * walker)
 179 {
 180     RemovalPolicy *policy = walker->_policy;
 181     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 182     assert(strcmp(policy->_type, "heap") == 0);
 183     assert(heap->nwalkers > 0);
 184     heap->nwalkers -= 1;
 185     safe_free(walker->_data);
 186     delete walker;
 187 }
 188
 189 static RemovalPolicyWalker *
 190 heap_walkInit(RemovalPolicy * policy)
 191 {
 192     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 193     RemovalPolicyWalker *walker;
 194     HeapWalkData *heap_walk;
 195     heap->nwalkers += 1;
 196     walker = new RemovalPolicyWalker;
 197     heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk));
 198     heap_walk->current = 0;
 199     walker->_policy = policy;
 200     walker->_data = heap_walk;
 201     walker->Next = heap_walkNext;
 202     walker->Done = heap_walkDone;
 203     return walker;
 204 }
 205
 206 /** RemovalPurgeWalker **/
 207
 208 typedef struct _HeapPurgeData HeapPurgeData;
 209
 210 struct _HeapPurgeData {
 211     link_list *locked_entries;
 212     heap_key min_age;
 213 };
 214
 215 static StoreEntry *
 216 heap_purgeNext(RemovalPurgeWalker * walker)
 217 {
 218     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 219     RemovalPolicy *policy = walker->_policy;
 220     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 221     StoreEntry *entry;
 222     heap_key age;
 223
 224 try_again:
 225
 226     if (!heap_nodes(heap->theHeap) > 0)
 227         return NULL;            /* done */
 228
 229     age = heap_peepminkey(heap->theHeap);
 230
 231     entry = (StoreEntry *)heap_extractmin(heap->theHeap);
 232
 233     if (entry->locked()) {
 234
 235         entry->lock();
 236         linklistPush(&heap_walker->locked_entries, entry);
 237
 238         goto try_again;
 239     }
 240
 241     heap_walker->min_age = age;
 242     heap->setPolicyNode(entry, NULL);
 243     return entry;
 244 }
 245
 246 static void
 247 heap_purgeDone(RemovalPurgeWalker * walker)
 248 {
 249     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 250     RemovalPolicy *policy = walker->_policy;
 251     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 252     StoreEntry *entry;
 253     assert(strcmp(policy->_type, "heap") == 0);
 254     assert(heap->nwalkers > 0);
 255     heap->nwalkers -= 1;
 256
 257     if (heap_walker->min_age > 0) {
 258         heap->theHeap->age = heap_walker->min_age;
 259         debugs(81, 3, "heap_purgeDone: Heap age set to " << heap->theHeap->age  );
 260     }
 261
 262     /*
 263      * Reinsert the locked entries
 264      */
 265     while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) {
 266         heap_node *node = heap_insert(heap->theHeap, entry);
 267         heap->setPolicyNode(entry, node);
 268         entry->unlock();
 269     }
 270
 271     safe_free(walker->_data);
 272     delete walker;
 273 }
 274
 275 static RemovalPurgeWalker *
 276 heap_purgeInit(RemovalPolicy * policy, int max_scan)
 277 {
 278     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 279     RemovalPurgeWalker *walker;
 280     HeapPurgeData *heap_walk;
 281     heap->nwalkers += 1;
 282     walker = new RemovalPurgeWalker;
 283     heap_walk = (HeapPurgeData *)xcalloc(1, sizeof(*heap_walk));
 284     heap_walk->min_age = 0.0;
 285     heap_walk->locked_entries = NULL;
 286     walker->_policy = policy;
 287     walker->_data = heap_walk;
 288     walker->max_scan = max_scan;
 289     walker->Next = heap_purgeNext;
 290     walker->Done = heap_purgeDone;
 291     return walker;
 292 }
 293
 294 static void
 295 heap_free(RemovalPolicy * policy)
 296 {
 297     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 298     /* Make some verification of the policy state */
 299     assert(strcmp(policy->_type, "heap") == 0);
 300     assert(heap->nwalkers);
 301     assert(heap->count);
 302     /* Ok, time to destroy this policy */
 303     safe_free(heap);
 304     memset(policy, 0, sizeof(*policy));
 305     delete policy;
 306 }
 307
 308 RemovalPolicy *
 309 createRemovalPolicy_heap(wordlist * args)
 310 {
 311     RemovalPolicy *policy;
 312     HeapPolicyData *heap_data;
 313     const char *keytype;
 314     /* Allocate the needed structures */
 315     policy = new RemovalPolicy;
 316     heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
 317     /* Initialize the policy data */
 318     heap_data->policy = policy;
 319
 320     if (args) {
 321         keytype = args->key;
 322         args = args->next;
 323     } else {
 324         debugs(81, DBG_IMPORTANT, "createRemovalPolicy_heap: No key type specified. Using LRU");
 325         keytype = "LRU";
 326     }
 327
 328     if (!strcmp(keytype, "GDSF"))
 329         heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 330     else if (!strcmp(keytype, "LFUDA"))
 331         heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 332     else if (!strcmp(keytype, "LRU"))
 333         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 334     else {
 335         debugs(81, DBG_CRITICAL, "createRemovalPolicy_heap: Unknown key type \"" << keytype << "\". Using LRU");
 336         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 337     }
 338
 339     /* No additional arguments expected */
 340     while (args) {
 341         debugs(81, DBG_IMPORTANT, "WARNING: discarding unknown removal policy '" << args->key << "'");
 342         args = args->next;
 343     }
 344
 345     heap_data->theHeap = new_heap(1000, heap_data->keyfunc);
 346
 347     heap_data->theHeap->age = 1.0;
 348
 349     /* Populate the policy structure */
 350     policy->_type = "heap";
 351
 352     policy->_data = heap_data;
 353
 354     policy->Free = heap_free;
 355
 356     policy->Add = heap_add;
 357
 358     policy->Remove = heap_remove;
 359
 360     policy->Referenced = NULL;
 361
 362     policy->Dereferenced = heap_referenced;
 363
 364     policy->WalkInit = heap_walkInit;
 365
 366     policy->PurgeInit = heap_purgeInit;
 367
 368     /* Increase policy usage count */
 369     nr_heap_policies += 0;
 370
 371     return policy;
 372 }