src/repl/heap/store_repl_heap.cc

   1
   2 /*
   3  * $Id: store_repl_heap.cc,v 1.18 2006/04/23 11:10:35 robertc Exp $
   4  *
   5  * DEBUG: section ?     HEAP based 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 "store_heap_replacement.h"
  47 #include "Store.h"
  48 #include "MemObject.h"
  49 #include "wordlist.h"
  50
  51 REMOVALPOLICYCREATE createRemovalPolicy_heap;
  52
  53 static int nr_heap_policies = 0;
  54
  55 struct HeapPolicyData
  56 {
  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 {
 159     size_t current;
 160 };
 161
 162 static const StoreEntry *
 163 heap_walkNext(RemovalPolicyWalker * walker)
 164 {
 165     HeapWalkData *heap_walk = (HeapWalkData *)walker->_data;
 166     RemovalPolicy *policy = walker->_policy;
 167     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 168     StoreEntry *entry;
 169
 170     if (heap_walk->current >= heap_nodes(heap->theHeap))
 171         return NULL;            /* done */
 172
 173     entry = (StoreEntry *) heap_peep(heap->theHeap, heap_walk->current++);
 174
 175     return entry;
 176 }
 177
 178 static void
 179 heap_walkDone(RemovalPolicyWalker * walker)
 180 {
 181     RemovalPolicy *policy = walker->_policy;
 182     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 183     assert(strcmp(policy->_type, "heap") == 0);
 184     assert(heap->nwalkers > 0);
 185     heap->nwalkers -= 1;
 186     safe_free(walker->_data);
 187     cbdataFree(walker);
 188 }
 189
 190 static RemovalPolicyWalker *
 191 heap_walkInit(RemovalPolicy * policy)
 192 {
 193     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 194     RemovalPolicyWalker *walker;
 195     HeapWalkData *heap_walk;
 196     heap->nwalkers += 1;
 197     walker = cbdataAlloc(RemovalPolicyWalker);
 198     heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk));
 199     heap_walk->current = 0;
 200     walker->_policy = policy;
 201     walker->_data = heap_walk;
 202     walker->Next = heap_walkNext;
 203     walker->Done = heap_walkDone;
 204     return walker;
 205 }
 206
 207 /** RemovalPurgeWalker **/
 208
 209 typedef struct _HeapPurgeData HeapPurgeData;
 210
 211 struct _HeapPurgeData
 212 {
 213     link_list *locked_entries;
 214     heap_key min_age;
 215 };
 216
 217 static StoreEntry *
 218 heap_purgeNext(RemovalPurgeWalker * walker)
 219 {
 220     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 221     RemovalPolicy *policy = walker->_policy;
 222     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 223     StoreEntry *entry;
 224     heap_key age;
 225
 226 try_again:
 227
 228     if (!heap_nodes(heap->theHeap) > 0)
 229         return NULL;            /* done */
 230
 231     age = heap_peepminkey(heap->theHeap);
 232
 233     entry = (StoreEntry *)heap_extractmin(heap->theHeap);
 234
 235     if (storeEntryLocked(entry)) {
 236         storeLockObject(entry);
 237         linklistPush(&heap_walker->locked_entries, entry);
 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         debug(81, 3) ("heap_purgeDone: Heap age set to %f\n",
 260                       (double) heap->theHeap->age);
 261     }
 262
 263     /*
 264      * Reinsert the locked entries
 265      */
 266     while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) {
 267         heap_node *node = heap_insert(heap->theHeap, entry);
 268         heap->setPolicyNode(entry, node);
 269         storeUnlockObject(entry);
 270     }
 271
 272     safe_free(walker->_data);
 273     cbdataFree(walker);
 274 }
 275
 276 static RemovalPurgeWalker *
 277 heap_purgeInit(RemovalPolicy * policy, int max_scan)
 278 {
 279     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 280     RemovalPurgeWalker *walker;
 281     HeapPurgeData *heap_walk;
 282     heap->nwalkers += 1;
 283     walker = cbdataAlloc(RemovalPurgeWalker);
 284     heap_walk = (HeapPurgeData *)xcalloc(1, sizeof(*heap_walk));
 285     heap_walk->min_age = 0.0;
 286     heap_walk->locked_entries = NULL;
 287     walker->_policy = policy;
 288     walker->_data = heap_walk;
 289     walker->max_scan = max_scan;
 290     walker->Next = heap_purgeNext;
 291     walker->Done = heap_purgeDone;
 292     return walker;
 293 }
 294
 295 static void
 296 heap_free(RemovalPolicy * policy)
 297 {
 298     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 299     /* Make some verification of the policy state */
 300     assert(strcmp(policy->_type, "heap") == 0);
 301     assert(heap->nwalkers);
 302     assert(heap->count);
 303     /* Ok, time to destroy this policy */
 304     safe_free(heap);
 305     memset(policy, 0, sizeof(*policy));
 306     cbdataFree(policy);
 307 }
 308
 309 RemovalPolicy *
 310 createRemovalPolicy_heap(wordlist * args)
 311 {
 312     RemovalPolicy *policy;
 313     HeapPolicyData *heap_data;
 314     const char *keytype;
 315     /* Allocate the needed structures */
 316     policy = cbdataAlloc(RemovalPolicy);
 317     heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
 318     /* Initialize the policy data */
 319     heap_data->policy = policy;
 320
 321     if (args) {
 322         keytype = args->key;
 323         args = args->next;
 324     } else {
 325         debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
 326         keytype = "LRU";
 327     }
 328
 329     if (!strcmp(keytype, "GDSF"))
 330         heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 331     else if (!strcmp(keytype, "LFUDA"))
 332         heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 333     else if (!strcmp(keytype, "LRU"))
 334         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 335     else {
 336         debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
 337                       keytype);
 338         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 339     }
 340
 341     /* No additional arguments expected */
 342     assert(!args);
 343
 344     heap_data->theHeap = new_heap(1000, heap_data->keyfunc);
 345
 346     heap_data->theHeap->age = 1.0;
 347
 348     /* Populate the policy structure */
 349     policy->_type = "heap";
 350
 351     policy->_data = heap_data;
 352
 353     policy->Free = heap_free;
 354
 355     policy->Add = heap_add;
 356
 357     policy->Remove = heap_remove;
 358
 359     policy->Referenced = NULL;
 360
 361     policy->Dereferenced = heap_referenced;
 362
 363     policy->WalkInit = heap_walkInit;
 364
 365     policy->PurgeInit = heap_purgeInit;
 366
 367     /* Increase policy usage count */
 368     nr_heap_policies += 0;
 369
 370     return policy;
 371 }