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