src/repl/heap/store_heap_replacement.cc

   1 /*
   2  * Copyright (C) 1996-2025 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: section 20    Storage Manager Heap-based replacement */
  10
  11 /*
  12  * The code in this file is Copyrighted (C) 1999 by Hewlett Packard.
  13  *
  14  *
  15  * For a description of these cache replacement policies see --
  16  *  http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
  17  */
  18
  19 #include "squid.h"
  20 #include "heap.h"
  21 #include "MemObject.h"
  22 #include "Store.h"
  23 #include "store_heap_replacement.h"
  24
  25 #include <cmath>
  26
  27 /*
  28  * Key generation function to implement the LFU-DA policy (Least
  29  * Frequently Used with Dynamic Aging).  Similar to classical LFU
  30  * but with aging to handle turnover of the popular document set.
  31  * Maximizes byte hit rate by keeping more currently popular objects
  32  * in cache regardless of size.  Achieves lower hit rate than GDS
  33  * because there are more large objects in cache (so less room for
  34  * smaller popular objects).
  35  *
  36  * This version implements a tie-breaker based upon recency
  37  * (e->lastref): for objects that have the same reference count
  38  * the most recent object wins (gets a higher key value).
  39  *
  40  * Note: this does not properly handle when the aging factor
  41  * gets so huge that the added value is outside of the
  42  * precision of double. However, Squid has to stay up
  43  * for quite a extended period of time (number of requests)
  44  * for this to become a problem. (estimation is 10^8 cache
  45  * turnarounds)
  46  */
  47 heap_key
  48 HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
  49 {
  50     StoreEntry *e = (StoreEntry *)entry;
  51     heap_key key;
  52     double tie;
  53
  54     if (e->lastref <= 0)
  55         tie = 0.0;
  56     else if (squid_curtime <= e->lastref)
  57         tie = 0.0;
  58     else
  59         tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0);
  60
  61     key = heap_age + (double) e->refcount - tie;
  62
  63     debugs(81, 3, "HeapKeyGen_StoreEntry_LFUDA: " << e->getMD5Text() <<
  64            " refcnt=" << e->refcount << " lastref=" << e->lastref <<
  65            " heap_age=" << heap_age << " tie=" << tie << " -> " << key);
  66
  67     if (e->mem_obj)
  68         debugs(81, 3, "storeId=" << e->mem_obj->storeId());
  69
  70     return (double) key;
  71 }
  72
  73 /*
  74  * Key generation function to implement the GDS-Frequency policy.
  75  * Similar to Greedy Dual-Size Hits policy, but adds aging of
  76  * documents to prevent pollution.  Maximizes object hit rate by
  77  * keeping more small, popular objects in cache.  Achieves lower
  78  * byte hit rate than LFUDA because there are fewer large objects
  79  * in cache.
  80  *
  81  * This version implements a tie-breaker based upon recency
  82  * (e->lastref): for objects that have the same reference count
  83  * the most recent object wins (gets a higher key value).
  84  *
  85  * Note: this does not properly handle when the aging factor
  86  * gets so huge that the added value is outside of the
  87  * precision of double. However, Squid has to stay up
  88  * for quite a extended period of time (number of requests)
  89  * for this to become a problem. (estimation is 10^8 cache
  90  * turnarounds)
  91  */
  92 heap_key
  93 HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
  94 {
  95     StoreEntry *e = (StoreEntry *)entry;
  96     heap_key key;
  97     double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0;
  98     double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0;
  99     key = heap_age + ((double) e->refcount / size) - tie;
 100     debugs(81, 3, "HeapKeyGen_StoreEntry_GDSF: " << e->getMD5Text() <<
 101            " size=" << size << " refcnt=" << e->refcount << " lastref=" <<
 102            e->lastref << " heap_age=" << heap_age << " tie=" << tie <<
 103            " -> " << key);
 104
 105     if (e->mem_obj)
 106         debugs(81, 3, "storeId=" << e->mem_obj->storeId());
 107
 108     return key;
 109 }
 110
 111 /*
 112  * Key generation function to implement the LRU policy.  Normally
 113  * one would not do this with a heap -- use the linked list instead.
 114  * For testing and performance characterization it was useful.
 115  * Don't use it unless you are trying to compare performance among
 116  * heap-based replacement policies...
 117  */
 118 heap_key
 119 HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
 120 {
 121     StoreEntry *e = (StoreEntry *)entry;
 122     debugs(81, 3, "HeapKeyGen_StoreEntry_LRU: " <<
 123            e->getMD5Text() << " heap_age=" << heap_age <<
 124            " lastref=" << (double) e->lastref  );
 125
 126     if (e->mem_obj)
 127         debugs(81, 3, "storeId=" << e->mem_obj->storeId());
 128
 129     return (heap_key) e->lastref;
 130 }
 131