src/repl/heap/store_repl_heap.cc

   1
   2 /*
   3  * $Id: store_repl_heap.cc,v 1.11 2002/10/13 20:35:29 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
  49 REMOVALPOLICYCREATE createRemovalPolicy_heap;
  50
  51 static int nr_heap_policies = 0;
  52
  53 struct HeapPolicyData {
  54     void setPolicyNode (StoreEntry *, void *) const;
  55     RemovalPolicy *policy;
  56     heap *theHeap;
  57     heap_key_func *keyfunc;
  58     int count;
  59     int nwalkers;
  60     enum heap_entry_type {
  61         TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
  62     } type;
  63 };
  64
  65 /* Hack to avoid having to remember the RemovalPolicyNode location.
  66  * Needed by the purge walker.
  67  */
  68 static enum HeapPolicyData::heap_entry_type
  69 heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
  70 {
  71     if (node == &entry->repl)
  72         return HeapPolicyData::TYPE_STORE_ENTRY;
  73     if (entry->mem_obj && node == &entry->mem_obj->repl)
  74         return HeapPolicyData::TYPE_STORE_MEM;
  75     fatal("Heap Replacement: Unknown StoreEntry node type");
  76     return HeapPolicyData::TYPE_UNKNOWN;
  77 }
  78
  79 void
  80 HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
  81 {
  82     switch (type) {
  83       case TYPE_STORE_ENTRY: entry->repl.data = value; break ;
  84       case TYPE_STORE_MEM: entry->mem_obj->repl.data = value ; break ;
  85       default: break;
  86     }
  87 }
  88
  89 static void
  90 heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
  91 {
  92     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
  93     assert(!node->data);
  94     if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
  95         return;                 /* We won't manage these.. they messes things up */
  96     node->data = heap_insert(heap->theHeap, entry);
  97     heap->count += 1;
  98     if (!heap->type)
  99         heap->type = heap_guessType(entry, node);
 100     /* Add a little more variance to the aging factor */
 101     heap->theHeap->age += heap->theHeap->age / 100000000;
 102 }
 103
 104 static void
 105 heap_remove(RemovalPolicy * policy, StoreEntry * entry,
 106     RemovalPolicyNode * node)
 107 {
 108     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 109     heap_node *hnode = (heap_node *)node->data;
 110     if (!hnode)
 111         return;
 112     heap_delete(heap->theHeap, hnode);
 113     node->data = NULL;
 114     heap->count -= 1;
 115 }
 116
 117 static void
 118 heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 119     RemovalPolicyNode * node)
 120 {
 121     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 122     heap_node *hnode = (heap_node *)node->data;
 123     if (!hnode)
 124         return;
 125     heap_update(heap->theHeap, hnode, (StoreEntry *) entry);
 126 }
 127
 128 /** RemovalPolicyWalker **/
 129
 130 typedef struct _HeapWalkData HeapWalkData;
 131 struct _HeapWalkData {
 132     size_t current;
 133 };
 134
 135 static const StoreEntry *
 136 heap_walkNext(RemovalPolicyWalker * walker)
 137 {
 138     HeapWalkData *heap_walk = (HeapWalkData *)walker->_data;
 139     RemovalPolicy *policy = walker->_policy;
 140     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 141     StoreEntry *entry;
 142     if (heap_walk->current >= heap_nodes(heap->theHeap))
 143         return NULL;            /* done */
 144     entry = (StoreEntry *) heap_peep(heap->theHeap, heap_walk->current++);
 145     return entry;
 146 }
 147
 148 static void
 149 heap_walkDone(RemovalPolicyWalker * walker)
 150 {
 151     RemovalPolicy *policy = walker->_policy;
 152     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 153     assert(strcmp(policy->_type, "heap") == 0);
 154     assert(heap->nwalkers > 0);
 155     heap->nwalkers -= 1;
 156     safe_free(walker->_data);
 157     cbdataFree(walker);
 158 }
 159
 160 static RemovalPolicyWalker *
 161 heap_walkInit(RemovalPolicy * policy)
 162 {
 163     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 164     RemovalPolicyWalker *walker;
 165     HeapWalkData *heap_walk;
 166     heap->nwalkers += 1;
 167     walker = cbdataAlloc(RemovalPolicyWalker);
 168     heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk));
 169     heap_walk->current = 0;
 170     walker->_policy = policy;
 171     walker->_data = heap_walk;
 172     walker->Next = heap_walkNext;
 173     walker->Done = heap_walkDone;
 174     return walker;
 175 }
 176
 177 /** RemovalPurgeWalker **/
 178
 179 typedef struct _HeapPurgeData HeapPurgeData;
 180 struct _HeapPurgeData {
 181     link_list *locked_entries;
 182     heap_key min_age;
 183 };
 184
 185 static StoreEntry *
 186 heap_purgeNext(RemovalPurgeWalker * walker)
 187 {
 188     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 189     RemovalPolicy *policy = walker->_policy;
 190     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 191     StoreEntry *entry;
 192     heap_key age;
 193   try_again:
 194     if (!heap_nodes(heap->theHeap) > 0)
 195         return NULL;            /* done */
 196     age = heap_peepminkey(heap->theHeap);
 197     entry = (StoreEntry *)heap_extractmin(heap->theHeap);
 198     if (storeEntryLocked(entry)) {
 199         linklistPush(&heap_walker->locked_entries, entry);
 200         goto try_again;
 201     }
 202     heap_walker->min_age = age;
 203     heap->setPolicyNode(entry, NULL);
 204     return entry;
 205 }
 206
 207 static void
 208 heap_purgeDone(RemovalPurgeWalker * walker)
 209 {
 210     HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
 211     RemovalPolicy *policy = walker->_policy;
 212     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 213     StoreEntry *entry;
 214     assert(strcmp(policy->_type, "heap") == 0);
 215     assert(heap->nwalkers > 0);
 216     heap->nwalkers -= 1;
 217     if (heap_walker->min_age > 0) {
 218         heap->theHeap->age = heap_walker->min_age;
 219         debug(81, 3) ("heap_purgeDone: Heap age set to %f\n",
 220             (double) heap->theHeap->age);
 221     }
 222     /*
 223      * Reinsert the locked entries
 224      */
 225     while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) {
 226         heap_node *node = heap_insert(heap->theHeap, entry);
 227         heap->setPolicyNode(entry, node);
 228     }
 229     safe_free(walker->_data);
 230     cbdataFree(walker);
 231 }
 232
 233 static RemovalPurgeWalker *
 234 heap_purgeInit(RemovalPolicy * policy, int max_scan)
 235 {
 236     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 237     RemovalPurgeWalker *walker;
 238     HeapPurgeData *heap_walk;
 239     heap->nwalkers += 1;
 240     walker = cbdataAlloc(RemovalPurgeWalker);
 241     heap_walk = (HeapPurgeData *)xcalloc(1, sizeof(*heap_walk));
 242     heap_walk->min_age = 0.0;
 243     heap_walk->locked_entries = NULL;
 244     walker->_policy = policy;
 245     walker->_data = heap_walk;
 246     walker->max_scan = max_scan;
 247     walker->Next = heap_purgeNext;
 248     walker->Done = heap_purgeDone;
 249     return walker;
 250 }
 251
 252 static void
 253 heap_free(RemovalPolicy * policy)
 254 {
 255     HeapPolicyData *heap = (HeapPolicyData *)policy->_data;
 256     /* Make some verification of the policy state */
 257     assert(strcmp(policy->_type, "heap") == 0);
 258     assert(heap->nwalkers);
 259     assert(heap->count);
 260     /* Ok, time to destroy this policy */
 261     safe_free(policy->_data);
 262     memset(policy, 0, sizeof(*policy));
 263     cbdataFree(policy);
 264 }
 265
 266 RemovalPolicy *
 267 createRemovalPolicy_heap(wordlist * args)
 268 {
 269     RemovalPolicy *policy;
 270     HeapPolicyData *heap_data;
 271     const char *keytype;
 272     /* Allocate the needed structures */
 273     policy = cbdataAlloc(RemovalPolicy);
 274     heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
 275     /* Initialize the policy data */
 276     heap_data->policy = policy;
 277     if (args) {
 278         keytype = args->key;
 279         args = args->next;
 280     } else {
 281         debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
 282         keytype = "LRU";
 283     }
 284     if (!strcmp(keytype, "GDSF"))
 285         heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 286     else if (!strcmp(keytype, "LFUDA"))
 287         heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 288     else if (!strcmp(keytype, "LRU"))
 289         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 290     else {
 291         debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
 292             keytype);
 293         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 294     }
 295     /* No additional arguments expected */
 296     assert(!args);
 297     heap_data->theHeap = new_heap(1000, heap_data->keyfunc);
 298     heap_data->theHeap->age = 1.0;
 299     /* Populate the policy structure */
 300     policy->_type = "heap";
 301     policy->_data = heap_data;
 302     policy->Free = heap_free;
 303     policy->Add = heap_add;
 304     policy->Remove = heap_remove;
 305     policy->Referenced = NULL;
 306     policy->Dereferenced = heap_referenced;
 307     policy->WalkInit = heap_walkInit;
 308     policy->PurgeInit = heap_purgeInit;
 309     /* Increase policy usage count */
 310     nr_heap_policies += 0;
 311     return policy;
 312 }