src/repl/lru/store_repl_lru.cc

   1
   2 /*
   3  * $Id: store_repl_lru.cc,v 1.3 2000/10/06 05:13:04 wessels Exp $
   4  *
   5  * DEBUG: section ?     LRU Removal policy
   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
  38 REMOVALPOLICYCREATE createRemovalPolicy_lru;
  39
  40 typedef struct _LruPolicyData LruPolicyData;
  41 struct _LruPolicyData {
  42     RemovalPolicy *policy;
  43     dlink_list list;
  44     int count;
  45     int nwalkers;
  46     enum heap_entry_type {
  47         TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
  48     } type;
  49 };
  50
  51 /* Hack to avoid having to remember the RemovalPolicyNode location.
  52  * Needed by the purge walker to clear the policy information
  53  */
  54 static enum heap_entry_type
  55 repl_guessType(StoreEntry * entry, RemovalPolicyNode * node)
  56 {
  57     if (node == &entry->repl)
  58         return TYPE_STORE_ENTRY;
  59     if (entry->mem_obj && node == &entry->mem_obj->repl)
  60         return TYPE_STORE_MEM;
  61     fatal("Heap Replacement: Unknown StoreEntry node type");
  62     return TYPE_UNKNOWN;
  63 }
  64 #define SET_POLICY_NODE(entry,value) \
  65     switch(lru->type) { \
  66     case TYPE_STORE_ENTRY: entry->repl.data = value; break ; \
  67     case TYPE_STORE_MEM: entry->mem_obj->repl.data = value ; break ; \
  68     default: break; \
  69     }
  70
  71 typedef struct _LruNode LruNode;
  72 struct _LruNode {
  73     /* Note: the dlink_node MUST be the first member of the LruNode
  74      * structure. This member is later pointer typecasted to LruNode *.
  75      */
  76     dlink_node node;
  77 };
  78
  79 static MemPool *lru_node_pool = NULL;
  80 static int nr_lru_policies = 0;
  81
  82 static void
  83 lru_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
  84 {
  85     LruPolicyData *lru = policy->_data;
  86     LruNode *lru_node;
  87     assert(!node->data);
  88     node->data = lru_node = memPoolAlloc(lru_node_pool);
  89     dlinkAddTail(entry, &lru_node->node, &lru->list);
  90     lru->count += 1;
  91     if (!lru->type)
  92         lru->type = repl_guessType(entry, node);
  93 }
  94
  95 static void
  96 lru_remove(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
  97 {
  98     LruPolicyData *lru = policy->_data;
  99     LruNode *lru_node = node->data;
 100     if (!lru_node)
 101         return;
 102     /*
 103      * It seems to be possible for an entry to exist in the hash
 104      * but not be in the LRU list, so check for that case rather
 105      * than suffer a NULL pointer access.
 106      */
 107     if (NULL == lru_node->node.data)
 108         return;
 109     assert(lru_node->node.data == entry);
 110     node->data = NULL;
 111     dlinkDelete(&lru_node->node, &lru->list);
 112     memPoolFree(lru_node_pool, lru_node);
 113     lru->count -= 1;
 114 }
 115
 116 static void
 117 lru_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 118     RemovalPolicyNode * node)
 119 {
 120     LruPolicyData *lru = policy->_data;
 121     LruNode *lru_node = node->data;
 122     if (!lru_node)
 123         return;
 124     dlinkDelete(&lru_node->node, &lru->list);
 125     dlinkAddTail((void *) entry, &lru_node->node, &lru->list);
 126 }
 127
 128 /** RemovalPolicyWalker **/
 129
 130 typedef struct _LruWalkData LruWalkData;
 131 struct _LruWalkData {
 132     LruNode *current;
 133 };
 134
 135 const StoreEntry *
 136 lru_walkNext(RemovalPolicyWalker * walker)
 137 {
 138     LruWalkData *lru_walk = walker->_data;
 139     LruNode *lru_node = lru_walk->current;
 140     if (!lru_node)
 141         return NULL;
 142     lru_walk->current = (LruNode *) lru_node->node.next;
 143     return (StoreEntry *) lru_node->node.data;
 144 }
 145
 146 static void
 147 lru_walkDone(RemovalPolicyWalker * walker)
 148 {
 149     RemovalPolicy *policy = walker->_policy;
 150     LruPolicyData *lru = policy->_data;
 151     assert(strcmp(policy->_type, "lru") == 0);
 152     assert(lru->nwalkers > 0);
 153     lru->nwalkers -= 1;
 154     safe_free(walker->_data);
 155     cbdataFree(walker);
 156 }
 157
 158 static RemovalPolicyWalker *
 159 lru_walkInit(RemovalPolicy * policy)
 160 {
 161     LruPolicyData *lru = policy->_data;
 162     RemovalPolicyWalker *walker;
 163     LruWalkData *lru_walk;
 164     lru->nwalkers += 1;
 165     walker = xcalloc(1, sizeof(*walker));
 166     lru_walk = xcalloc(1, sizeof(*lru_walk));
 167     walker->_policy = policy;
 168     walker->_data = lru_walk;
 169     walker->Next = lru_walkNext;
 170     walker->Done = lru_walkDone;
 171     lru_walk->current = (LruNode *) lru->list.head;
 172     cbdataAdd(walker, cbdataXfree, 0);
 173     return walker;
 174 }
 175
 176 /** RemovalPurgeWalker **/
 177
 178 typedef struct _LruPurgeData LruPurgeData;
 179 struct _LruPurgeData {
 180     LruNode *current;
 181     LruNode *start;
 182 };
 183
 184 static StoreEntry *
 185 lru_purgeNext(RemovalPurgeWalker * walker)
 186 {
 187     LruPurgeData *lru_walker = walker->_data;
 188     RemovalPolicy *policy = walker->_policy;
 189     LruPolicyData *lru = policy->_data;
 190     LruNode *lru_node;
 191     StoreEntry *entry;
 192   try_again:
 193     lru_node = lru_walker->current;
 194     if (!lru_node || walker->scanned >= walker->max_scan)
 195         return NULL;
 196     walker->scanned += 1;
 197     lru_walker->current = (LruNode *) lru_node->node.next;
 198     if (lru_walker->current == lru_walker->start) {
 199         /* Last node found */
 200         lru_walker->current = NULL;
 201     }
 202     entry = (StoreEntry *) lru_node->node.data;
 203     dlinkDelete(&lru_node->node, &lru->list);
 204     if (storeEntryLocked(entry)) {
 205         /* Shit, it is locked. we can't return this one */
 206         walker->locked++;
 207         dlinkAddTail(entry, &lru_node->node, &lru->list);
 208         goto try_again;
 209     }
 210     memPoolFree(lru_node_pool, lru_node);
 211     lru->count -= 1;
 212     SET_POLICY_NODE(entry, NULL);
 213     return entry;
 214 }
 215
 216 static void
 217 lru_purgeDone(RemovalPurgeWalker * walker)
 218 {
 219     RemovalPolicy *policy = walker->_policy;
 220     LruPolicyData *lru = policy->_data;
 221     assert(strcmp(policy->_type, "lru") == 0);
 222     assert(lru->nwalkers > 0);
 223     lru->nwalkers -= 1;
 224     safe_free(walker->_data);
 225     cbdataFree(walker);
 226 }
 227
 228 static RemovalPurgeWalker *
 229 lru_purgeInit(RemovalPolicy * policy, int max_scan)
 230 {
 231     LruPolicyData *lru = policy->_data;
 232     RemovalPurgeWalker *walker;
 233     LruPurgeData *lru_walk;
 234     lru->nwalkers += 1;
 235     walker = xcalloc(1, sizeof(*walker));
 236     lru_walk = xcalloc(1, sizeof(*lru_walk));
 237     walker->_policy = policy;
 238     walker->_data = lru_walk;
 239     walker->max_scan = max_scan;
 240     walker->Next = lru_purgeNext;
 241     walker->Done = lru_purgeDone;
 242     lru_walk->start = lru_walk->current = (LruNode *) lru->list.head;
 243     cbdataAdd(walker, cbdataXfree, 0);
 244     return walker;
 245 }
 246
 247 static void
 248 lru_free(RemovalPolicy * policy)
 249 {
 250     LruPolicyData *lru = policy->_data;
 251     /* Make some verification of the policy state */
 252     assert(strcmp(policy->_type, "lru") == 0);
 253     assert(lru->nwalkers);
 254     assert(lru->count);
 255     /* Ok, time to destroy this policy */
 256     safe_free(policy->_data);
 257     memset(policy, 0, sizeof(*policy));
 258     cbdataFree(policy);
 259 }
 260
 261 RemovalPolicy *
 262 createRemovalPolicy_lru(wordlist * args)
 263 {
 264     RemovalPolicy *policy;
 265     LruPolicyData *lru_data;
 266     /* no arguments expected or understood */
 267     assert(!args);
 268     /* Initialize */
 269     if (!lru_node_pool)
 270         lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode));
 271     /* Allocate the needed structures */
 272     policy = xcalloc(1, sizeof(*policy));
 273     lru_data = xcalloc(1, sizeof(*lru_data));
 274     /* cbdata register the policy */
 275     cbdataAdd(policy, cbdataXfree, 0);
 276     /* Initialize the URL data */
 277     lru_data->policy = policy;
 278     /* Populate the policy structure */
 279     policy->_type = "lru";
 280     policy->_data = lru_data;
 281     policy->Free = lru_free;
 282     policy->Add = lru_add;
 283     policy->Remove = lru_remove;
 284     policy->Referenced = lru_referenced;
 285     policy->Dereferenced = lru_referenced;
 286     policy->WalkInit = lru_walkInit;
 287     policy->PurgeInit = lru_purgeInit;
 288     /* Increase policy usage count */
 289     nr_lru_policies += 0;
 290     return policy;
 291 }