src/repl/heap/store_repl_heap.cc

   1
   2 /*
   3  * $Id: store_repl_heap.cc,v 1.2 2000/11/03 16:39:42 wessels Exp $
   4  *
   5  * DEBUG: section ?     HEAP based removal policies
   6  * AUTHOR: Henrik Nordstrom
   7  *
   8  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from the
  12  *  Internet community.  Development is led by Duane Wessels of the
  13  *  National Laboratory for Applied Network Research and funded by the
  14  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  15  *  Duane Wessels and the University of California San Diego.  Please
  16  *  see the COPYRIGHT file for full details.  Squid incorporates
  17  *  software developed and/or copyrighted by other sources.  Please see
  18  *  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 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 = xcalloc(1, sizeof(*walker));
 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     cbdataAdd(walker, cbdataXfree, 0);
 162     return walker;
 163 }
 164
 165 /** RemovalPurgeWalker **/
 166
 167 typedef struct _HeapPurgeData HeapPurgeData;
 168 struct _HeapPurgeData {
 169     link_list *locked_entries;
 170     heap_key min_age;
 171 };
 172
 173 static StoreEntry *
 174 heap_purgeNext(RemovalPurgeWalker * walker)
 175 {
 176     HeapPurgeData *heap_walker = walker->_data;
 177     RemovalPolicy *policy = walker->_policy;
 178     HeapPolicyData *heap = policy->_data;
 179     StoreEntry *entry;
 180     heap_key age;
 181   try_again:
 182     if (!heap_nodes(heap->heap) > 0)
 183         return NULL;            /* done */
 184     age = heap_peepminkey(heap->heap);
 185     entry = heap_extractmin(heap->heap);
 186     if (storeEntryLocked(entry)) {
 187         linklistPush(&heap_walker->locked_entries, entry);
 188         goto try_again;
 189     }
 190     heap_walker->min_age = age;
 191     SET_POLICY_NODE(entry, NULL);
 192     return entry;
 193 }
 194
 195 static void
 196 heap_purgeDone(RemovalPurgeWalker * walker)
 197 {
 198     HeapPurgeData *heap_walker = walker->_data;
 199     RemovalPolicy *policy = walker->_policy;
 200     HeapPolicyData *heap = policy->_data;
 201     StoreEntry *entry;
 202     assert(strcmp(policy->_type, "heap") == 0);
 203     assert(heap->nwalkers > 0);
 204     heap->nwalkers -= 1;
 205     if (heap_walker->min_age > 0) {
 206         heap->heap->age = heap_walker->min_age;
 207         debug(81, 3) ("heap_purgeDone: Heap age set to %f\n",
 208             (double) heap->heap->age);
 209     }
 210     /*
 211      * Reinsert the locked entries
 212      */
 213     while ((entry = linklistShift(&heap_walker->locked_entries))) {
 214         heap_node *node = heap_insert(heap->heap, entry);
 215         SET_POLICY_NODE(entry, node);
 216     }
 217     safe_free(walker->_data);
 218     cbdataFree(walker);
 219 }
 220
 221 static RemovalPurgeWalker *
 222 heap_purgeInit(RemovalPolicy * policy, int max_scan)
 223 {
 224     HeapPolicyData *heap = policy->_data;
 225     RemovalPurgeWalker *walker;
 226     HeapPurgeData *heap_walk;
 227     heap->nwalkers += 1;
 228     walker = xcalloc(1, sizeof(*walker));
 229     heap_walk = xcalloc(1, sizeof(*heap_walk));
 230     heap_walk->min_age = 0.0;
 231     heap_walk->locked_entries = NULL;
 232     walker->_policy = policy;
 233     walker->_data = heap_walk;
 234     walker->max_scan = max_scan;
 235     walker->Next = heap_purgeNext;
 236     walker->Done = heap_purgeDone;
 237     cbdataAdd(walker, cbdataXfree, 0);
 238 #if HEAP_REPLACEMENT_DEBUG
 239     if (!verify_heap_property(heap->heap)) {
 240         debug(81, 1) ("Heap property violated!\n");
 241     }
 242 #endif
 243     return walker;
 244 }
 245
 246 static void
 247 heap_free(RemovalPolicy * policy)
 248 {
 249     HeapPolicyData *heap = policy->_data;
 250     /* Make some verification of the policy state */
 251     assert(strcmp(policy->_type, "heap") == 0);
 252     assert(heap->nwalkers);
 253     assert(heap->count);
 254     /* Ok, time to destroy this policy */
 255     safe_free(policy->_data);
 256     memset(policy, 0, sizeof(*policy));
 257     cbdataFree(policy);
 258 }
 259
 260 RemovalPolicy *
 261 createRemovalPolicy_heap(wordlist * args)
 262 {
 263     RemovalPolicy *policy;
 264     HeapPolicyData *heap_data;
 265     char *keytype;
 266     /* Allocate the needed structures */
 267     policy = xcalloc(1, sizeof(*policy));
 268     heap_data = xcalloc(1, sizeof(*heap_data));
 269     /* cbdata register the policy */
 270     cbdataAdd(policy, cbdataXfree, 0);
 271     /* Initialize the policy data */
 272     heap_data->policy = policy;
 273     if (args) {
 274         keytype = args->key;
 275         args = args->next;
 276     } else {
 277         debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
 278         keytype = "LRU";
 279     }
 280     if (!strcmp(keytype, "GDSF"))
 281         heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
 282     else if (!strcmp(keytype, "LFUDA"))
 283         heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
 284     else if (!strcmp(keytype, "LRU"))
 285         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 286     else {
 287         debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
 288             keytype);
 289         heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
 290     }
 291     /* No additional arguments expected */
 292     assert(!args);
 293     heap_data->heap = new_heap(1000, heap_data->keyfunc);
 294     heap_data->heap->age = 1.0;
 295     /* Populate the policy structure */
 296     policy->_type = "heap";
 297     policy->_data = heap_data;
 298     policy->Free = heap_free;
 299     policy->Add = heap_add;
 300     policy->Remove = heap_remove;
 301     policy->Referenced = NULL;
 302     policy->Dereferenced = heap_referenced;
 303     policy->WalkInit = heap_walkInit;
 304     policy->PurgeInit = heap_purgeInit;
 305     /* Increase policy usage count */
 306     nr_heap_policies += 0;
 307     return policy;
 308 }