src/repl/lru/store_repl_lru.cc

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