src/repl/lru/store_repl_lru.cc

   1
   2 /*
   3  * DEBUG: none          LRU Removal Policy
   4  * AUTHOR: Henrik Nordstrom
   5  *
   6  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   7  * ----------------------------------------------------------
   8  *
   9  *  Squid is the result of efforts by numerous individuals from
  10  *  the Internet community; see the CONTRIBUTORS file for full
  11  *  details.   Many organizations have provided support for Squid's
  12  *  development; see the SPONSORS file for full details.  Squid is
  13  *  Copyrighted (C) 2001 by the Regents of the University of
  14  *  California; see the COPYRIGHT file for full details.  Squid
  15  *  incorporates software developed and/or copyrighted by other
  16  *  sources; see the CREDITS file for full details.
  17  *
  18  *  This program is free software; you can redistribute it and/or modify
  19  *  it under the terms of the GNU General Public License as published by
  20  *  the Free Software Foundation; either version 2 of the License, or
  21  *  (at your option) any later version.
  22  *
  23  *  This program is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  26  *  GNU General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU General Public License
  29  *  along with this program; if not, write to the Free Software
  30  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  31  *
  32  */
  33
  34 #include "squid.h"
  35 #include "Store.h"
  36 #include "MemObject.h"
  37 #include "SquidTime.h"
  38
  39 REMOVALPOLICYCREATE createRemovalPolicy_lru;
  40
  41 struct LruPolicyData {
  42     void setPolicyNode (StoreEntry *, void *) const;
  43     RemovalPolicy *policy;
  44     dlink_list list;
  45     int count;
  46     int nwalkers;
  47     enum heap_entry_type {
  48         TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
  49     } type;
  50 };
  51
  52 /* Hack to avoid having to remember the RemovalPolicyNode location.
  53  * Needed by the purge walker to clear the policy information
  54  */
  55 static enum LruPolicyData::heap_entry_type
  56 repl_guessType(StoreEntry * entry, RemovalPolicyNode * node)
  57 {
  58     if (node == &entry->repl)
  59         return LruPolicyData::TYPE_STORE_ENTRY;
  60
  61     if (entry->mem_obj && node == &entry->mem_obj->repl)
  62         return LruPolicyData::TYPE_STORE_MEM;
  63
  64     fatal("Heap Replacement: Unknown StoreEntry node type");
  65
  66     return LruPolicyData::TYPE_UNKNOWN;
  67 }
  68
  69 void
  70 LruPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
  71 {
  72     switch (type) {
  73
  74     case TYPE_STORE_ENTRY:
  75         entry->repl.data = value;
  76         break ;
  77
  78     case TYPE_STORE_MEM:
  79         entry->mem_obj->repl.data = value ;
  80         break ;
  81
  82     default:
  83         break;
  84     }
  85 }
  86
  87 typedef struct _LruNode LruNode;
  88
  89 struct _LruNode {
  90     /* Note: the dlink_node MUST be the first member of the LruNode
  91      * structure. This member is later pointer typecasted to LruNode *.
  92      */
  93     dlink_node node;
  94 };
  95
  96 static MemAllocator *lru_node_pool = NULL;
  97 static int nr_lru_policies = 0;
  98
  99 static void
 100 lru_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 101 {
 102     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 103     LruNode *lru_node;
 104     assert(!node->data);
 105     node->data = lru_node = (LruNode *)lru_node_pool->alloc();
 106     dlinkAddTail(entry, &lru_node->node, &lru->list);
 107     lru->count += 1;
 108
 109     if (!lru->type)
 110         lru->type = repl_guessType(entry, node);
 111 }
 112
 113 static void
 114 lru_remove(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
 115 {
 116     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 117     LruNode *lru_node = (LruNode *)node->data;
 118
 119     if (!lru_node)
 120         return;
 121
 122     /*
 123      * It seems to be possible for an entry to exist in the hash
 124      * but not be in the LRU list, so check for that case rather
 125      * than suffer a NULL pointer access.
 126      */
 127     if (NULL == lru_node->node.data)
 128         return;
 129
 130     assert(lru_node->node.data == entry);
 131
 132     node->data = NULL;
 133
 134     dlinkDelete(&lru_node->node, &lru->list);
 135
 136     lru_node_pool->freeOne(lru_node);
 137
 138     lru->count -= 1;
 139 }
 140
 141 static void
 142 lru_referenced(RemovalPolicy * policy, const StoreEntry * entry,
 143                RemovalPolicyNode * node)
 144 {
 145     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 146     LruNode *lru_node = (LruNode *)node->data;
 147
 148     if (!lru_node)
 149         return;
 150
 151     dlinkDelete(&lru_node->node, &lru->list);
 152
 153     dlinkAddTail((void *) entry, &lru_node->node, &lru->list);
 154 }
 155
 156 /** RemovalPolicyWalker **/
 157
 158 typedef struct _LruWalkData LruWalkData;
 159
 160 struct _LruWalkData {
 161     LruNode *current;
 162 };
 163
 164 static const StoreEntry *
 165 lru_walkNext(RemovalPolicyWalker * walker)
 166 {
 167     LruWalkData *lru_walk = (LruWalkData *)walker->_data;
 168     LruNode *lru_node = lru_walk->current;
 169
 170     if (!lru_node)
 171         return NULL;
 172
 173     lru_walk->current = (LruNode *) lru_node->node.next;
 174
 175     return (StoreEntry *) lru_node->node.data;
 176 }
 177
 178 static void
 179 lru_walkDone(RemovalPolicyWalker * walker)
 180 {
 181     RemovalPolicy *policy = walker->_policy;
 182     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 183     assert(strcmp(policy->_type, "lru") == 0);
 184     assert(lru->nwalkers > 0);
 185     lru->nwalkers -= 1;
 186     safe_free(walker->_data);
 187     delete walker;
 188 }
 189
 190 static RemovalPolicyWalker *
 191 lru_walkInit(RemovalPolicy * policy)
 192 {
 193     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 194     RemovalPolicyWalker *walker;
 195     LruWalkData *lru_walk;
 196     lru->nwalkers += 1;
 197     walker = new RemovalPolicyWalker;
 198     lru_walk = (LruWalkData *)xcalloc(1, sizeof(*lru_walk));
 199     walker->_policy = policy;
 200     walker->_data = lru_walk;
 201     walker->Next = lru_walkNext;
 202     walker->Done = lru_walkDone;
 203     lru_walk->current = (LruNode *) lru->list.head;
 204     return walker;
 205 }
 206
 207 /** RemovalPurgeWalker **/
 208
 209 typedef struct _LruPurgeData LruPurgeData;
 210
 211 struct _LruPurgeData {
 212     LruNode *current;
 213     LruNode *start;
 214 };
 215
 216 static StoreEntry *
 217 lru_purgeNext(RemovalPurgeWalker * walker)
 218 {
 219     LruPurgeData *lru_walker = (LruPurgeData *)walker->_data;
 220     RemovalPolicy *policy = walker->_policy;
 221     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 222     LruNode *lru_node;
 223     StoreEntry *entry;
 224
 225 try_again:
 226     lru_node = lru_walker->current;
 227
 228     if (!lru_node || walker->scanned >= walker->max_scan)
 229         return NULL;
 230
 231     walker->scanned += 1;
 232
 233     lru_walker->current = (LruNode *) lru_node->node.next;
 234
 235     if (lru_walker->current == lru_walker->start) {
 236         /* Last node found */
 237         lru_walker->current = NULL;
 238     }
 239
 240     entry = (StoreEntry *) lru_node->node.data;
 241     dlinkDelete(&lru_node->node, &lru->list);
 242
 243     if (entry->locked()) {
 244         /* Shit, it is locked. we can't return this one */
 245         ++ walker->locked;
 246         dlinkAddTail(entry, &lru_node->node, &lru->list);
 247         goto try_again;
 248     }
 249
 250     lru_node_pool->freeOne(lru_node);
 251     lru->count -= 1;
 252     lru->setPolicyNode(entry, NULL);
 253     return entry;
 254 }
 255
 256 static void
 257 lru_purgeDone(RemovalPurgeWalker * walker)
 258 {
 259     RemovalPolicy *policy = walker->_policy;
 260     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 261     assert(strcmp(policy->_type, "lru") == 0);
 262     assert(lru->nwalkers > 0);
 263     lru->nwalkers -= 1;
 264     safe_free(walker->_data);
 265     delete walker;
 266 }
 267
 268 static RemovalPurgeWalker *
 269 lru_purgeInit(RemovalPolicy * policy, int max_scan)
 270 {
 271     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 272     RemovalPurgeWalker *walker;
 273     LruPurgeData *lru_walk;
 274     lru->nwalkers += 1;
 275     walker = new RemovalPurgeWalker;
 276     lru_walk = (LruPurgeData *)xcalloc(1, sizeof(*lru_walk));
 277     walker->_policy = policy;
 278     walker->_data = lru_walk;
 279     walker->max_scan = max_scan;
 280     walker->Next = lru_purgeNext;
 281     walker->Done = lru_purgeDone;
 282     lru_walk->start = lru_walk->current = (LruNode *) lru->list.head;
 283     return walker;
 284 }
 285
 286 static void
 287 lru_stats(RemovalPolicy * policy, StoreEntry * sentry)
 288 {
 289     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 290     LruNode *lru_node = (LruNode *) lru->list.head;
 291
 292 again:
 293
 294     if (lru_node) {
 295         StoreEntry *entry = (StoreEntry *) lru_node->node.data;
 296
 297         if (entry->locked()) {
 298             lru_node = (LruNode *) lru_node->node.next;
 299             goto again;
 300         }
 301
 302         storeAppendPrintf(sentry, "LRU reference age: %.2f days\n", (double) (squid_curtime - entry->lastref) / (double) (24 * 60 * 60));
 303     }
 304 }
 305
 306 static void
 307 lru_free(RemovalPolicy * policy)
 308 {
 309     LruPolicyData *lru = (LruPolicyData *)policy->_data;
 310     /* Make some verification of the policy state */
 311     assert(strcmp(policy->_type, "lru") == 0);
 312     assert(lru->nwalkers);
 313     assert(lru->count);
 314     /* Ok, time to destroy this policy */
 315     safe_free(lru);
 316     memset(policy, 0, sizeof(*policy));
 317     delete policy;
 318 }
 319
 320 RemovalPolicy *
 321 createRemovalPolicy_lru(wordlist * args)
 322 {
 323     RemovalPolicy *policy;
 324     LruPolicyData *lru_data;
 325     /* no arguments expected or understood */
 326     assert(!args);
 327     /* Initialize */
 328
 329     if (!lru_node_pool) {
 330         /* Must be chunked */
 331         lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode));
 332         lru_node_pool->setChunkSize(512 * 1024);
 333     }
 334
 335     /* Allocate the needed structures */
 336     lru_data = (LruPolicyData *)xcalloc(1, sizeof(*lru_data));
 337
 338     policy = new RemovalPolicy;
 339
 340     /* Initialize the URL data */
 341     lru_data->policy = policy;
 342
 343     /* Populate the policy structure */
 344     policy->_type = "lru";
 345
 346     policy->_data = lru_data;
 347
 348     policy->Free = lru_free;
 349
 350     policy->Add = lru_add;
 351
 352     policy->Remove = lru_remove;
 353
 354     policy->Referenced = lru_referenced;
 355
 356     policy->Dereferenced = lru_referenced;
 357
 358     policy->WalkInit = lru_walkInit;
 359
 360     policy->PurgeInit = lru_purgeInit;
 361
 362     policy->Stats = lru_stats;
 363
 364     /* Increase policy usage count */
 365     nr_lru_policies += 0;
 366
 367     return policy;
 368 }