src/repl/heap/store_repl_heap.cc

   1
   2 /*
   3  * $Id: store_repl_heap.cc,v 1.16 2004/12/20 14:52:32 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
  50 REMOVALPOLICYCREATE createRemovalPolicy_heap;
  51
  52 static int nr_heap_policies = 0;
  53
  54 struct HeapPolicyData
  55 {
  56     void setPolicyNode (StoreEntry *, void *) const;
  57     RemovalPolicy *policy;
  58     heap *theHeap;
  59     heap_key_func *keyfunc;
  60     int count;
  61     int nwalkers;
  62     enum heap_entry_type {
  63         TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
  64     } type;
  65 };
  66
  67 /* Hack to avoid having to remember the RemovalPolicyNode location.
  68  * Needed by the purge walker.
  69  */
  70 static enum HeapPolicyData::heap_entry_type
  71 heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
  72 {
  73     if (node == &entry->repl)
  74         return HeapPolicyData::TYPE_STORE_ENTRY;
  75
  76     if (entry->mem_obj && node == &entry->mem_obj->repl)
  77         return HeapPolicyData::TYPE_STORE_MEM;
  78
  79     fatal("Heap Replacement: Unknown StoreEntry node type");
  80
  81     return HeapPolicyData::TYPE_UNKNOWN;
  82 }
  83
  84 void
  85 HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
  86 {
  87     switch (type) {
  88
  89     case TYPE_STORE_ENTRY:
  90         entry->repl.data = value;
  91         break ;
  92
  93     case TYPE_STORE_MEM:
  94         entry->mem_obj->repl.data = value ;
  95         break ;
  96
  97     default:
  98         break;
  99     }
 100 }
 101
 102 static void
 103 heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 104 {
 105     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 106     assert(!node->data);
 107
 108     if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
 109         return;                 /* We won't manage these.. they messes things up */
 110
 111     node->data = heap_insert(heap->theHeap, entry);
 112
 113     heap->count += 1;
 114
 115     if (!heap->type)
 116         heap->type = heap_guessType(entry, node);
 117
 118     /* Add a little more variance to the aging factor */
 119     heap->theHeap->age += heap->theHeap->age / 100000000;
 120 }
 121
 122 static void
 123 heap_remove(RemovalPolicy * policy, StoreEntry * entry,
 124             RemovalPolicyNode * node)
 125 {
 126     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 127     heap_node *hnode = (heap_node *)node->data;
 128
 129     if (!hnode)
 130         return;
 131
 132     heap_delete(heap->theHeap, hnode);
 133
 134     node->data = NULL;
 135
 136     heap->count -= 1;
 137 }
 138
 139 static void
 140 heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 141                 RemovalPolicyNode * node)
 142 {
 143     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 144     heap_node *hnode = (heap_node *)node->data;
 145
 146     if (!hnode)
 147         return;
 148
 149     heap_update(heap->theHeap, hnode, (StoreEntry *) entry);
 150 }
 151
 152 /** RemovalPolicyWalker **/
 153
 154 typedef struct _HeapWalkData HeapWalkData;
 155
 156 struct _HeapWalkData
 157 {
 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     cbdataFree(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 = cbdataAlloc(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 {
 212     link_list *locked_entries;
 213     heap_key min_age;
 214 };
 215
 216 static StoreEntry *
 217 heap_purgeNext(RemovalPurgeWalker * walker)
 218 {
 219     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 220     RemovalPolicy *policy = walker->_policy;
 221     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 222     StoreEntry *entry;
 223     heap_key age;
 224
 225 try_again:
 226
 227     if (!heap_nodes(heap->theHeap) > 0)
 228         return NULL;            /* done */
 229
 230     age = heap_peepminkey(heap->theHeap);
 231
 232     entry = (StoreEntry *)heap_extractmin(heap->theHeap);
 233
 234     if (storeEntryLocked(entry)) {
 235         storeLockObject(entry);
 236         linklistPush(&heap_walker->locked_entries, entry);
 237         goto try_again;
 238     }
 239
 240     heap_walker->min_age = age;
 241     heap->setPolicyNode(entry, NULL);
 242     return entry;
 243 }
 244
 245 static void
 246 heap_purgeDone(RemovalPurgeWalker * walker)
 247 {
 248     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 249     RemovalPolicy *policy = walker->_policy;
 250     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 251     StoreEntry *entry;
 252     assert(strcmp(policy->_type, "heap") == 0);
 253     assert(heap->nwalkers > 0);
 254     heap->nwalkers -= 1;
 255
 256     if (heap_walker->min_age > 0) {
 257         heap->theHeap->age = heap_walker->min_age;
 258         debug(81, 3) ("heap_purgeDone: Heap age set to %f\n",
 259                       (double) 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         storeUnlockObject(entry);
 269     }
 270
 271     safe_free(walker->_data);
 272     cbdataFree(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 = cbdataAlloc(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     cbdataFree(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 = cbdataAlloc(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         debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
 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         debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
 336                       keytype);
 337         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 338     }
 339
 340     /* No additional arguments expected */
 341     assert(!args);
 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 }