]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/repl/heap/store_heap_replacement.cc
7fcc662a335edc39ddf319194338aa781022e510
2 * Copyright (C) 1996-2016 The Squid Software Foundation and contributors
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.
9 /* DEBUG: section 20 Storage Manager Heap-based replacement */
12 * The code in this file is Copyrighted (C) 1999 by Hewlett Packard.
15 * For a description of these cache replacement policies see --
16 * http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
21 #include "MemObject.h"
22 #include "SquidTime.h"
24 #include "store_heap_replacement.h"
29 * Key generation function to implement the LFU-DA policy (Least
30 * Frequently Used with Dynamic Aging). Similar to classical LFU
31 * but with aging to handle turnover of the popular document set.
32 * Maximizes byte hit rate by keeping more currently popular objects
33 * in cache regardless of size. Achieves lower hit rate than GDS
34 * because there are more large objects in cache (so less room for
35 * smaller popular objects).
37 * This version implements a tie-breaker based upon recency
38 * (e->lastref): for objects that have the same reference count
39 * the most recent object wins (gets a higher key value).
41 * Note: this does not properly handle when the aging factor
42 * gets so huge that the added value is outside of the
43 * precision of double. However, Squid has to stay up
44 * for quite a extended period of time (number of requests)
45 * for this to become a problem. (estimation is 10^8 cache
49 HeapKeyGen_StoreEntry_LFUDA(void *entry
, double heap_age
)
51 StoreEntry
*e
= (StoreEntry
*)entry
;
57 else if (squid_curtime
<= e
->lastref
)
60 tie
= 1.0 - exp((double) (e
->lastref
- squid_curtime
) / 86400.0);
62 key
= heap_age
+ (double) e
->refcount
- tie
;
64 debugs(81, 3, "HeapKeyGen_StoreEntry_LFUDA: " << e
->getMD5Text() <<
65 " refcnt=" << e
->refcount
<< " lastref=" << e
->lastref
<<
66 " heap_age=" << heap_age
<< " tie=" << tie
<< " -> " << key
);
69 debugs(81, 3, "storeId=" << e
->mem_obj
->storeId());
75 * Key generation function to implement the GDS-Frequency policy.
76 * Similar to Greedy Dual-Size Hits policy, but adds aging of
77 * documents to prevent pollution. Maximizes object hit rate by
78 * keeping more small, popular objects in cache. Achieves lower
79 * byte hit rate than LFUDA because there are fewer large objects
82 * This version implements a tie-breaker based upon recency
83 * (e->lastref): for objects that have the same reference count
84 * the most recent object wins (gets a higher key value).
86 * Note: this does not properly handle when the aging factor
87 * gets so huge that the added value is outside of the
88 * precision of double. However, Squid has to stay up
89 * for quite a extended period of time (number of requests)
90 * for this to become a problem. (estimation is 10^8 cache
94 HeapKeyGen_StoreEntry_GDSF(void *entry
, double heap_age
)
96 StoreEntry
*e
= (StoreEntry
*)entry
;
98 double size
= e
->swap_file_sz
? (double) e
->swap_file_sz
: 1.0;
99 double tie
= (e
->lastref
> 1) ? (1.0 / e
->lastref
) : 1.0;
100 key
= heap_age
+ ((double) e
->refcount
/ size
) - tie
;
101 debugs(81, 3, "HeapKeyGen_StoreEntry_GDSF: " << e
->getMD5Text() <<
102 " size=" << size
<< " refcnt=" << e
->refcount
<< " lastref=" <<
103 e
->lastref
<< " heap_age=" << heap_age
<< " tie=" << tie
<<
107 debugs(81, 3, "storeId=" << e
->mem_obj
->storeId());
113 * Key generation function to implement the LRU policy. Normally
114 * one would not do this with a heap -- use the linked list instead.
115 * For testing and performance characterization it was useful.
116 * Don't use it unless you are trying to compare performance among
117 * heap-based replacement policies...
120 HeapKeyGen_StoreEntry_LRU(void *entry
, double heap_age
)
122 StoreEntry
*e
= (StoreEntry
*)entry
;
123 debugs(81, 3, "HeapKeyGen_StoreEntry_LRU: " <<
124 e
->getMD5Text() << " heap_age=" << heap_age
<<
125 " lastref=" << (double) e
->lastref
);
128 debugs(81, 3, "storeId=" << e
->mem_obj
->storeId());
130 return (heap_key
) e
->lastref
;