src/repl/heap/store_repl_heap.cc

   1
   2 /*
   3  * $Id: store_repl_heap.cc,v 1.5 2001/02/07 18:56:56 hno Exp $
   4  *
   5  * DEBUG: section ?     HEAP based removal policies
   6  * AUTHOR: Henrik Nordstrom
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from
  12  *  the Internet community; see the CONTRIBUTORS file for full
  13  *  details.   Many organizations have provided support for Squid's
  14  *  development; see the SPONSORS file for full details.  Squid is
  15  *  Copyrighted (C) 2001 by the Regents of the University of
  16  *  California; see the COPYRIGHT file for full details.  Squid
  17  *  incorporates software developed and/or copyrighted by other
  18  *  sources; see the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37 #include "heap.h"
  38 #include "store_heap_replacement.h"
  39
  40 REMOVALPOLICYCREATE createRemovalPolicy_heap;
  41
  42 static int nr_heap_policies = 0;
  43
  44 typedef struct _HeapPolicyData HeapPolicyData;
  45 struct _HeapPolicyData {
  46     RemovalPolicy *policy;
  47     heap *heap;
  48     heap_key_func *keyfunc;
  49     int count;
  50     int nwalkers;
  51     enum heap_entry_type {
  52         TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
  53     } type;
  54 };
  55
  56 /* Hack to avoid having to remember the RemovalPolicyNode location.
  57  * Needed by the purge walker.
  58  */
  59 static enum heap_entry_type
  60 heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
  61 {
  62     if (node == &entry->repl)
  63         return TYPE_STORE_ENTRY;
  64     if (entry->mem_obj && node == &entry->mem_obj->repl)
  65         return TYPE_STORE_MEM;
  66     fatal("Heap Replacement: Unknown StoreEntry node type");
  67     return TYPE_UNKNOWN;
  68 }
  69 #define SET_POLICY_NODE(entry,value) \
  70     switch(heap->type) { \
  71     case TYPE_STORE_ENTRY: entry->repl.data = value; break ; \
  72     case TYPE_STORE_MEM: entry->mem_obj->repl.data = value ; break ; \
  73     default: break; \
  74     }
  75
  76 static void
  77 heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
  78 {
  79     HeapPolicyData *heap = policy->_data;
  80     assert(!node->data);
  81     if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
  82         return;                 /* We won't manage these.. they messes things up */
  83     node->data = heap_insert(heap->heap, entry);
  84     heap->count += 1;
  85     if (!heap->type)
  86         heap->type = heap_guessType(entry, node);
  87     /* Add a little more variance to the aging factor */
  88     heap->heap->age += heap->heap->age / 100000000;
  89 }
  90
  91 static void
  92 heap_remove(RemovalPolicy * policy, StoreEntry * entry,
  93     RemovalPolicyNode * node)
  94 {
  95     HeapPolicyData *heap = policy->_data;
  96     heap_node *hnode = node->data;
  97     if (!hnode)
  98         return;
  99     heap_delete(heap->heap, hnode);
 100     node->data = NULL;
 101     heap->count -= 1;
 102 }
 103
 104 static void
 105 heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 106     RemovalPolicyNode * node)
 107 {
 108     HeapPolicyData *heap = policy->_data;
 109     heap_node *hnode = node->data;
 110     if (!hnode)
 111         return;
 112     heap_update(heap->heap, hnode, (StoreEntry *) entry);
 113 }
 114
 115 /** RemovalPolicyWalker **/
 116
 117 typedef struct _HeapWalkData HeapWalkData;
 118 struct _HeapWalkData {
 119     int current;
 120 };
 121
 122 static const StoreEntry *
 123 heap_walkNext(RemovalPolicyWalker * walker)
 124 {
 125     HeapWalkData *heap_walk = walker->_data;
 126     RemovalPolicy *policy = walker->_policy;
 127     HeapPolicyData *heap = policy->_data;
 128     StoreEntry *entry;
 129     if (heap_walk->current >= heap_nodes(heap->heap))
 130         return NULL;            /* done */
 131     entry = (StoreEntry *) heap_peep(heap->heap, heap_walk->current++);
 132     return entry;
 133 }
 134
 135 static void
 136 heap_walkDone(RemovalPolicyWalker * walker)
 137 {
 138     RemovalPolicy *policy = walker->_policy;
 139     HeapPolicyData *heap = policy->_data;
 140     assert(strcmp(policy->_type, "heap") == 0);
 141     assert(heap->nwalkers > 0);
 142     heap->nwalkers -= 1;
 143     safe_free(walker->_data);
 144     cbdataFree(walker);
 145 }
 146
 147 static RemovalPolicyWalker *
 148 heap_walkInit(RemovalPolicy * policy)
 149 {
 150     HeapPolicyData *heap = policy->_data;
 151     RemovalPolicyWalker *walker;
 152     HeapWalkData *heap_walk;
 153     heap->nwalkers += 1;
 154     walker = CBDATA_ALLOC(RemovalPolicyWalker, NULL);
 155     heap_walk = xcalloc(1, sizeof(*heap_walk));
 156     heap_walk->current = 0;
 157     walker->_policy = policy;
 158     walker->_data = heap_walk;
 159     walker->Next = heap_walkNext;
 160     walker->Done = heap_walkDone;
 161     return walker;
 162 }
 163
 164 /** RemovalPurgeWalker **/
 165
 166 typedef struct _HeapPurgeData HeapPurgeData;
 167 struct _HeapPurgeData {
 168     link_list *locked_entries;
 169     heap_key min_age;
 170 };
 171
 172 static StoreEntry *
 173 heap_purgeNext(RemovalPurgeWalker * walker)
 174 {
 175     HeapPurgeData *heap_walker = walker->_data;
 176     RemovalPolicy *policy = walker->_policy;
 177     HeapPolicyData *heap = policy->_data;
 178     StoreEntry *entry;
 179     heap_key age;
 180   try_again:
 181     if (!heap_nodes(heap->heap) > 0)
 182         return NULL;            /* done */
 183     age = heap_peepminkey(heap->heap);
 184     entry = heap_extractmin(heap->heap);
 185     if (storeEntryLocked(entry)) {
 186         linklistPush(&heap_walker->locked_entries, entry);
 187         goto try_again;
 188     }
 189     heap_walker->min_age = age;
 190     SET_POLICY_NODE(entry, NULL);
 191     return entry;
 192 }
 193
 194 static void
 195 heap_purgeDone(RemovalPurgeWalker * walker)
 196 {
 197     HeapPurgeData *heap_walker = walker->_data;
 198     RemovalPolicy *policy = walker->_policy;
 199     HeapPolicyData *heap = policy->_data;
 200     StoreEntry *entry;
 201     assert(strcmp(policy->_type, "heap") == 0);
 202     assert(heap->nwalkers > 0);
 203     heap->nwalkers -= 1;
 204     if (heap_walker->min_age > 0) {
 205         heap->heap->age = heap_walker->min_age;
 206         debug(81, 3) ("heap_purgeDone: Heap age set to %f\n",
 207             (double) heap->heap->age);
 208     }
 209     /*
 210      * Reinsert the locked entries
 211      */
 212     while ((entry = linklistShift(&heap_walker->locked_entries))) {
 213         heap_node *node = heap_insert(heap->heap, entry);
 214         SET_POLICY_NODE(entry, node);
 215     }
 216     safe_free(walker->_data);
 217     cbdataFree(walker);
 218 }
 219
 220 static RemovalPurgeWalker *
 221 heap_purgeInit(RemovalPolicy * policy, int max_scan)
 222 {
 223     HeapPolicyData *heap = policy->_data;
 224     RemovalPurgeWalker *walker;
 225     HeapPurgeData *heap_walk;
 226     heap->nwalkers += 1;
 227     walker = CBDATA_ALLOC(RemovalPurgeWalker, NULL);
 228     heap_walk = xcalloc(1, sizeof(*heap_walk));
 229     heap_walk->min_age = 0.0;
 230     heap_walk->locked_entries = NULL;
 231     walker->_policy = policy;
 232     walker->_data = heap_walk;
 233     walker->max_scan = max_scan;
 234     walker->Next = heap_purgeNext;
 235     walker->Done = heap_purgeDone;
 236 #if HEAP_REPLACEMENT_DEBUG
 237     if (!verify_heap_property(heap->heap)) {
 238         debug(81, 1) ("Heap property violated!\n");
 239     }
 240 #endif
 241     return walker;
 242 }
 243
 244 static void
 245 heap_free(RemovalPolicy * policy)
 246 {
 247     HeapPolicyData *heap = policy->_data;
 248     /* Make some verification of the policy state */
 249     assert(strcmp(policy->_type, "heap") == 0);
 250     assert(heap->nwalkers);
 251     assert(heap->count);
 252     /* Ok, time to destroy this policy */
 253     safe_free(policy->_data);
 254     memset(policy, 0, sizeof(*policy));
 255     cbdataFree(policy);
 256 }
 257
 258 RemovalPolicy *
 259 createRemovalPolicy_heap(wordlist * args)
 260 {
 261     RemovalPolicy *policy;
 262     HeapPolicyData *heap_data;
 263     char *keytype;
 264     /* Allocate the needed structures */
 265     policy = CBDATA_ALLOC(RemovalPolicy, NULL);
 266     heap_data = xcalloc(1, sizeof(*heap_data));
 267     /* Initialize the policy data */
 268     heap_data->policy = policy;
 269     if (args) {
 270         keytype = args->key;
 271         args = args->next;
 272     } else {
 273         debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
 274         keytype = "LRU";
 275     }
 276     if (!strcmp(keytype, "GDSF"))
 277         heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 278     else if (!strcmp(keytype, "LFUDA"))
 279         heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 280     else if (!strcmp(keytype, "LRU"))
 281         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 282     else {
 283         debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
 284             keytype);
 285         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 286     }
 287     /* No additional arguments expected */
 288     assert(!args);
 289     heap_data->heap = new_heap(1000, heap_data->keyfunc);
 290     heap_data->heap->age = 1.0;
 291     /* Populate the policy structure */
 292     policy->_type = "heap";
 293     policy->_data = heap_data;
 294     policy->Free = heap_free;
 295     policy->Add = heap_add;
 296     policy->Remove = heap_remove;
 297     policy->Referenced = NULL;
 298     policy->Dereferenced = heap_referenced;
 299     policy->WalkInit = heap_walkInit;
 300     policy->PurgeInit = heap_purgeInit;
 301     /* Increase policy usage count */
 302     nr_heap_policies += 0;
 303     return policy;
 304 }