src/repl/lru/store_repl_lru.cc

   1
   2 /*
   3  * $Id: store_repl_lru.cc,v 1.7 2001/02/07 18:56:56 hno Exp $
   4  *
   5  * DEBUG: section ?     LRU Removal policy
   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
  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 static 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 = CBDATA_ALLOC(RemovalPolicyWalker, NULL);
 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     return walker;
 173 }
 174
 175 /** RemovalPurgeWalker **/
 176
 177 typedef struct _LruPurgeData LruPurgeData;
 178 struct _LruPurgeData {
 179     LruNode *current;
 180     LruNode *start;
 181 };
 182
 183 static StoreEntry *
 184 lru_purgeNext(RemovalPurgeWalker * walker)
 185 {
 186     LruPurgeData *lru_walker = walker->_data;
 187     RemovalPolicy *policy = walker->_policy;
 188     LruPolicyData *lru = policy->_data;
 189     LruNode *lru_node;
 190     StoreEntry *entry;
 191   try_again:
 192     lru_node = lru_walker->current;
 193     if (!lru_node || walker->scanned >= walker->max_scan)
 194         return NULL;
 195     walker->scanned += 1;
 196     lru_walker->current = (LruNode *) lru_node->node.next;
 197     if (lru_walker->current == lru_walker->start) {
 198         /* Last node found */
 199         lru_walker->current = NULL;
 200     }
 201     entry = (StoreEntry *) lru_node->node.data;
 202     dlinkDelete(&lru_node->node, &lru->list);
 203     if (storeEntryLocked(entry)) {
 204         /* Shit, it is locked. we can't return this one */
 205         walker->locked++;
 206         dlinkAddTail(entry, &lru_node->node, &lru->list);
 207         goto try_again;
 208     }
 209     memPoolFree(lru_node_pool, lru_node);
 210     lru->count -= 1;
 211     SET_POLICY_NODE(entry, NULL);
 212     return entry;
 213 }
 214
 215 static void
 216 lru_purgeDone(RemovalPurgeWalker * walker)
 217 {
 218     RemovalPolicy *policy = walker->_policy;
 219     LruPolicyData *lru = policy->_data;
 220     assert(strcmp(policy->_type, "lru") == 0);
 221     assert(lru->nwalkers > 0);
 222     lru->nwalkers -= 1;
 223     safe_free(walker->_data);
 224     cbdataFree(walker);
 225 }
 226
 227 static RemovalPurgeWalker *
 228 lru_purgeInit(RemovalPolicy * policy, int max_scan)
 229 {
 230     LruPolicyData *lru = policy->_data;
 231     RemovalPurgeWalker *walker;
 232     LruPurgeData *lru_walk;
 233     lru->nwalkers += 1;
 234     walker = CBDATA_ALLOC(RemovalPurgeWalker, NULL);
 235     lru_walk = xcalloc(1, sizeof(*lru_walk));
 236     walker->_policy = policy;
 237     walker->_data = lru_walk;
 238     walker->max_scan = max_scan;
 239     walker->Next = lru_purgeNext;
 240     walker->Done = lru_purgeDone;
 241     lru_walk->start = lru_walk->current = (LruNode *) lru->list.head;
 242     return walker;
 243 }
 244
 245 static void
 246 lru_free(RemovalPolicy * policy)
 247 {
 248     LruPolicyData *lru = policy->_data;
 249     /* Make some verification of the policy state */
 250     assert(strcmp(policy->_type, "lru") == 0);
 251     assert(lru->nwalkers);
 252     assert(lru->count);
 253     /* Ok, time to destroy this policy */
 254     safe_free(policy->_data);
 255     memset(policy, 0, sizeof(*policy));
 256     cbdataFree(policy);
 257 }
 258
 259 RemovalPolicy *
 260 createRemovalPolicy_lru(wordlist * args)
 261 {
 262     RemovalPolicy *policy;
 263     LruPolicyData *lru_data;
 264     /* no arguments expected or understood */
 265     assert(!args);
 266     /* Initialize */
 267     if (!lru_node_pool)
 268         lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode));
 269     /* Allocate the needed structures */
 270     lru_data = xcalloc(1, sizeof(*lru_data));
 271     policy = CBDATA_ALLOC(RemovalPolicy, NULL);
 272     /* Initialize the URL data */
 273     lru_data->policy = policy;
 274     /* Populate the policy structure */
 275     policy->_type = "lru";
 276     policy->_data = lru_data;
 277     policy->Free = lru_free;
 278     policy->Add = lru_add;
 279     policy->Remove = lru_remove;
 280     policy->Referenced = lru_referenced;
 281     policy->Dereferenced = lru_referenced;
 282     policy->WalkInit = lru_walkInit;
 283     policy->PurgeInit = lru_purgeInit;
 284     /* Increase policy usage count */
 285     nr_lru_policies += 0;
 286     return policy;
 287 }