src/repl/lru/store_repl_lru.cc

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