src/repl/lru/store_repl_lru.cc

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