src/repl/lru/store_repl_lru.cc

   1
   2 /*
   3  * $Id: store_repl_lru.cc,v 1.22 2007/04/25 11:30:19 adrian Exp $
   4  *
   5  * DEBUG: none          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 #include "Store.h"
  38 #include "MemObject.h"
  39 #include "SquidTime.h"
  40
  41 REMOVALPOLICYCREATE createRemovalPolicy_lru;
  42
  43 struct LruPolicyData
  44 {
  45     void setPolicyNode (StoreEntry *, void *) const;
  46     RemovalPolicy *policy;
  47     dlink_list list;
  48     int count;
  49     int nwalkers;
  50     enum heap_entry_type {
  51         TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
  52     } type;
  53 };
  54
  55 /* Hack to avoid having to remember the RemovalPolicyNode location.
  56  * Needed by the purge walker to clear the policy information
  57  */
  58 static enum LruPolicyData::heap_entry_type
  59 repl_guessType(StoreEntry * entry, RemovalPolicyNode * node)
  60 {
  61     if (node == &entry->repl)
  62         return LruPolicyData::TYPE_STORE_ENTRY;
  63
  64     if (entry->mem_obj && node == &entry->mem_obj->repl)
  65         return LruPolicyData::TYPE_STORE_MEM;
  66
  67     fatal("Heap Replacement: Unknown StoreEntry node type");
  68
  69     return LruPolicyData::TYPE_UNKNOWN;
  70 }
  71
  72 void
  73 LruPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
  74 {
  75     switch (type) {
  76
  77     case TYPE_STORE_ENTRY:
  78         entry->repl.data = value;
  79         break ;
  80
  81     case TYPE_STORE_MEM:
  82         entry->mem_obj->repl.data = value ;
  83         break ;
  84
  85     default:
  86         break;
  87     }
  88 }
  89
  90 typedef struct _LruNode LruNode;
  91
  92 struct _LruNode
  93 {
  94     /* Note: the dlink_node MUST be the first member of the LruNode
  95      * structure. This member is later pointer typecasted to LruNode *.
  96      */
  97     dlink_node node;
  98 };
  99
 100 static MemAllocator *lru_node_pool = NULL;
 101 static int nr_lru_policies = 0;
 102
 103 static void
 104 lru_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 105 {
 106     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 107     LruNode *lru_node;
 108     assert(!node->data);
 109     node->data = lru_node = (LruNode *)lru_node_pool->alloc();
 110     dlinkAddTail(entry, &lru_node->node, &lru->list);
 111     lru->count += 1;
 112
 113     if (!lru->type)
 114         lru->type = repl_guessType(entry, node);
 115 }
 116
 117 static void
 118 lru_remove(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 119 {
 120     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 121     LruNode *lru_node = (LruNode *)node->data;
 122
 123     if (!lru_node)
 124         return;
 125
 126     /*
 127      * It seems to be possible for an entry to exist in the hash
 128      * but not be in the LRU list, so check for that case rather
 129      * than suffer a NULL pointer access.
 130      */
 131     if (NULL == lru_node->node.data)
 132         return;
 133
 134     assert(lru_node->node.data == entry);
 135
 136     node->data = NULL;
 137
 138     dlinkDelete(&lru_node->node, &lru->list);
 139
 140     lru_node_pool->free(lru_node);
 141
 142     lru->count -= 1;
 143 }
 144
 145 static void
 146 lru_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 147                RemovalPolicyNode * node)
 148 {
 149     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 150     LruNode *lru_node = (LruNode *)node->data;
 151
 152     if (!lru_node)
 153         return;
 154
 155     dlinkDelete(&lru_node->node, &lru->list);
 156
 157     dlinkAddTail((void *) entry, &lru_node->node, &lru->list);
 158 }
 159
 160 /** RemovalPolicyWalker **/
 161
 162 typedef struct _LruWalkData LruWalkData;
 163
 164 struct _LruWalkData
 165 {
 166     LruNode *current;
 167 };
 168
 169 static const StoreEntry *
 170 lru_walkNext(RemovalPolicyWalker * walker)
 171 {
 172     LruWalkData *lru_walk = (LruWalkData *)walker->_data;
 173     LruNode *lru_node = lru_walk->current;
 174
 175     if (!lru_node)
 176         return NULL;
 177
 178     lru_walk->current = (LruNode *) lru_node->node.next;
 179
 180     return (StoreEntry *) lru_node->node.data;
 181 }
 182
 183 static void
 184 lru_walkDone(RemovalPolicyWalker * walker)
 185 {
 186     RemovalPolicy *policy = walker->_policy;
 187     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 188     assert(strcmp(policy->_type, "lru") == 0);
 189     assert(lru->nwalkers > 0);
 190     lru->nwalkers -= 1;
 191     safe_free(walker->_data);
 192     delete walker;
 193 }
 194
 195 static RemovalPolicyWalker *
 196 lru_walkInit(RemovalPolicy * policy)
 197 {
 198     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 199     RemovalPolicyWalker *walker;
 200     LruWalkData *lru_walk;
 201     lru->nwalkers += 1;
 202     walker = new RemovalPolicyWalker;
 203     lru_walk = (LruWalkData *)xcalloc(1, sizeof(*lru_walk));
 204     walker->_policy = policy;
 205     walker->_data = lru_walk;
 206     walker->Next = lru_walkNext;
 207     walker->Done = lru_walkDone;
 208     lru_walk->current = (LruNode *) lru->list.head;
 209     return walker;
 210 }
 211
 212 /** RemovalPurgeWalker **/
 213
 214 typedef struct _LruPurgeData LruPurgeData;
 215
 216 struct _LruPurgeData
 217 {
 218     LruNode *current;
 219     LruNode *start;
 220 };
 221
 222 static StoreEntry *
 223 lru_purgeNext(RemovalPurgeWalker * walker)
 224 {
 225     LruPurgeData *lru_walker = (LruPurgeData *)walker->_data;
 226     RemovalPolicy *policy = walker->_policy;
 227     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 228     LruNode *lru_node;
 229     StoreEntry *entry;
 230
 231 try_again:
 232     lru_node = lru_walker->current;
 233
 234     if (!lru_node || walker->scanned >= walker->max_scan)
 235         return NULL;
 236
 237     walker->scanned += 1;
 238
 239     lru_walker->current = (LruNode *) lru_node->node.next;
 240
 241     if (lru_walker->current == lru_walker->start) {
 242         /* Last node found */
 243         lru_walker->current = NULL;
 244     }
 245
 246     entry = (StoreEntry *) lru_node->node.data;
 247     dlinkDelete(&lru_node->node, &lru->list);
 248
 249     if (entry->locked()) {
 250         /* Shit, it is locked. we can't return this one */
 251         walker->locked++;
 252         dlinkAddTail(entry, &lru_node->node, &lru->list);
 253         goto try_again;
 254     }
 255
 256     lru_node_pool->free(lru_node);
 257     lru->count -= 1;
 258     lru->setPolicyNode(entry, NULL);
 259     return entry;
 260 }
 261
 262 static void
 263 lru_purgeDone(RemovalPurgeWalker * walker)
 264 {
 265     RemovalPolicy *policy = walker->_policy;
 266     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 267     assert(strcmp(policy->_type, "lru") == 0);
 268     assert(lru->nwalkers > 0);
 269     lru->nwalkers -= 1;
 270     safe_free(walker->_data);
 271     delete walker;
 272 }
 273
 274 static RemovalPurgeWalker *
 275 lru_purgeInit(RemovalPolicy * policy, int max_scan)
 276 {
 277     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 278     RemovalPurgeWalker *walker;
 279     LruPurgeData *lru_walk;
 280     lru->nwalkers += 1;
 281     walker = new RemovalPurgeWalker;
 282     lru_walk = (LruPurgeData *)xcalloc(1, sizeof(*lru_walk));
 283     walker->_policy = policy;
 284     walker->_data = lru_walk;
 285     walker->max_scan = max_scan;
 286     walker->Next = lru_purgeNext;
 287     walker->Done = lru_purgeDone;
 288     lru_walk->start = lru_walk->current = (LruNode *) lru->list.head;
 289     return walker;
 290 }
 291
 292 static void
 293 lru_stats(RemovalPolicy * policy, StoreEntry * sentry)
 294 {
 295     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 296     LruNode *lru_node = (LruNode *) lru->list.head;
 297
 298 again:
 299
 300     if (lru_node) {
 301         StoreEntry *entry = (StoreEntry *) lru_node->node.data;
 302
 303         if (entry->locked()) {
 304             lru_node = (LruNode *) lru_node->node.next;
 305             goto again;
 306         }
 307
 308         storeAppendPrintf(sentry, "LRU reference age: %.2f days\n", (double) (squid_curtime - entry->lastref) / (double) (24 * 60 * 60));
 309     }
 310 }
 311
 312 static void
 313 lru_free(RemovalPolicy * policy)
 314 {
 315     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 316     /* Make some verification of the policy state */
 317     assert(strcmp(policy->_type, "lru") == 0);
 318     assert(lru->nwalkers);
 319     assert(lru->count);
 320     /* Ok, time to destroy this policy */
 321     safe_free(lru);
 322     memset(policy, 0, sizeof(*policy));
 323     delete policy;
 324 }
 325
 326 RemovalPolicy *
 327 createRemovalPolicy_lru(wordlist * args)
 328 {
 329     RemovalPolicy *policy;
 330     LruPolicyData *lru_data;
 331     /* no arguments expected or understood */
 332     assert(!args);
 333     /* Initialize */
 334
 335     if (!lru_node_pool) {
 336         /* Must be chunked */
 337         lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode));
 338         lru_node_pool->setChunkSize(512 * 1024);
 339     }
 340
 341     /* Allocate the needed structures */
 342     lru_data = (LruPolicyData *)xcalloc(1, sizeof(*lru_data));
 343
 344     policy = new RemovalPolicy;
 345
 346     /* Initialize the URL data */
 347     lru_data->policy = policy;
 348
 349     /* Populate the policy structure */
 350     policy->_type = "lru";
 351
 352     policy->_data = lru_data;
 353
 354     policy->Free = lru_free;
 355
 356     policy->Add = lru_add;
 357
 358     policy->Remove = lru_remove;
 359
 360     policy->Referenced = lru_referenced;
 361
 362     policy->Dereferenced = lru_referenced;
 363
 364     policy->WalkInit = lru_walkInit;
 365
 366     policy->PurgeInit = lru_purgeInit;
 367
 368     policy->Stats = lru_stats;
 369
 370     /* Increase policy usage count */
 371     nr_lru_policies += 0;
 372
 373     return policy;
 374 }