src/repl/lru/store_repl_lru.cc

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