src/repl/heap/store_repl_heap.cc

   1
   2 /*
   3  * $Id: store_repl_heap.cc,v 1.25 2007/04/30 16:56:19 wessels Exp $
   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 "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     delete 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 = new 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 (entry->locked()) {
 236
 237         entry->lock();
 238         linklistPush(&heap_walker->locked_entries, entry);
 239
 240         goto try_again;
 241     }
 242
 243     heap_walker->min_age = age;
 244     heap->setPolicyNode(entry, NULL);
 245     return entry;
 246 }
 247
 248 static void
 249 heap_purgeDone(RemovalPurgeWalker * walker)
 250 {
 251     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 252     RemovalPolicy *policy = walker->_policy;
 253     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 254     StoreEntry *entry;
 255     assert(strcmp(policy->_type, "heap") == 0);
 256     assert(heap->nwalkers > 0);
 257     heap->nwalkers -= 1;
 258
 259     if (heap_walker->min_age > 0) {
 260         heap->theHeap->age = heap_walker->min_age;
 261         debugs(81, 3, "heap_purgeDone: Heap age set to " << heap->theHeap->age  );
 262     }
 263
 264     /*
 265      * Reinsert the locked entries
 266      */
 267     while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) {
 268         heap_node *node = heap_insert(heap->theHeap, entry);
 269         heap->setPolicyNode(entry, node);
 270         entry->unlock();
 271     }
 272
 273     safe_free(walker->_data);
 274     delete walker;
 275 }
 276
 277 static RemovalPurgeWalker *
 278 heap_purgeInit(RemovalPolicy * policy, int max_scan)
 279 {
 280     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 281     RemovalPurgeWalker *walker;
 282     HeapPurgeData *heap_walk;
 283     heap->nwalkers += 1;
 284     walker = new RemovalPurgeWalker;
 285     heap_walk = (HeapPurgeData *)xcalloc(1, sizeof(*heap_walk));
 286     heap_walk->min_age = 0.0;
 287     heap_walk->locked_entries = NULL;
 288     walker->_policy = policy;
 289     walker->_data = heap_walk;
 290     walker->max_scan = max_scan;
 291     walker->Next = heap_purgeNext;
 292     walker->Done = heap_purgeDone;
 293     return walker;
 294 }
 295
 296 static void
 297 heap_free(RemovalPolicy * policy)
 298 {
 299     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 300     /* Make some verification of the policy state */
 301     assert(strcmp(policy->_type, "heap") == 0);
 302     assert(heap->nwalkers);
 303     assert(heap->count);
 304     /* Ok, time to destroy this policy */
 305     safe_free(heap);
 306     memset(policy, 0, sizeof(*policy));
 307     delete policy;
 308 }
 309
 310 RemovalPolicy *
 311 createRemovalPolicy_heap(wordlist * args)
 312 {
 313     RemovalPolicy *policy;
 314     HeapPolicyData *heap_data;
 315     const char *keytype;
 316     /* Allocate the needed structures */
 317     policy = new RemovalPolicy;
 318     heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
 319     /* Initialize the policy data */
 320     heap_data->policy = policy;
 321
 322     if (args) {
 323         keytype = args->key;
 324         args = args->next;
 325     } else {
 326         debugs(81, 1, "createRemovalPolicy_heap: No key type specified. Using LRU");
 327         keytype = "LRU";
 328     }
 329
 330     if (!strcmp(keytype, "GDSF"))
 331         heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 332     else if (!strcmp(keytype, "LFUDA"))
 333         heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 334     else if (!strcmp(keytype, "LRU"))
 335         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 336     else {
 337         debugs(81, 0, "createRemovalPolicy_heap: Unknown key type \"" << keytype << "\". Using LRU");
 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 }