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