]>
Commit | Line | Data |
---|---|---|
6a566b9c | 1 | /* |
bbc27441 | 2 | * Copyright (C) 1996-2014 The Squid Software Foundation and contributors |
6a566b9c | 3 | * |
bbc27441 AJ |
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. | |
6a566b9c | 7 | */ |
8 | ||
bbc27441 AJ |
9 | /* DEBUG: section 20 Storage Manager Heap-based replacement */ |
10 | ||
6a566b9c | 11 | /* |
12 | * The code in this file is Copyrighted (C) 1999 by Hewlett Packard. | |
26ac0430 | 13 | * |
6a566b9c | 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 | ||
582c2af2 | 19 | #include "squid.h" |
6a566b9c | 20 | #include "heap.h" |
528b2c61 | 21 | #include "MemObject.h" |
985c86bc | 22 | #include "SquidTime.h" |
602d9612 A |
23 | #include "Store.h" |
24 | #include "store_heap_replacement.h" | |
6a566b9c | 25 | |
074d6a40 | 26 | #include <cmath> |
582c2af2 | 27 | |
6a566b9c | 28 | /* |
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). | |
26ac0430 | 36 | * |
6a566b9c | 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). | |
40 | * | |
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 | |
46 | * turnarounds) | |
47 | */ | |
f0debecb | 48 | heap_key |
b6a7f52c | 49 | HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age) |
6a566b9c | 50 | { |
e6ccf245 | 51 | StoreEntry *e = (StoreEntry *)entry; |
6a566b9c | 52 | heap_key key; |
53 | double tie; | |
62e76326 | 54 | |
6a566b9c | 55 | if (e->lastref <= 0) |
62e76326 | 56 | tie = 0.0; |
6a566b9c | 57 | else if (squid_curtime <= e->lastref) |
62e76326 | 58 | tie = 0.0; |
6a566b9c | 59 | else |
62e76326 | 60 | tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0); |
61 | ||
b6a7f52c | 62 | key = heap_age + (double) e->refcount - tie; |
62e76326 | 63 | |
e4049756 | 64 | debugs(81, 3, "HeapKeyGen_StoreEntry_LFUDA: " << e->getMD5Text() << |
65 | " refcnt=" << e->refcount << " lastref=" << e->lastref << | |
66 | " heap_age=" << heap_age << " tie=" << tie << " -> " << key); | |
62e76326 | 67 | |
cb868059 AR |
68 | if (e->mem_obj) |
69 | debugs(81, 3, "storeId=" << e->mem_obj->storeId()); | |
62e76326 | 70 | |
be1ed2a4 | 71 | return (double) key; |
6a566b9c | 72 | } |
73 | ||
6a566b9c | 74 | /* |
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 | |
80 | * in cache. | |
26ac0430 | 81 | * |
6a566b9c | 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). | |
85 | * | |
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 | |
91 | * turnarounds) | |
92 | */ | |
f0debecb | 93 | heap_key |
b6a7f52c | 94 | HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age) |
6a566b9c | 95 | { |
e6ccf245 | 96 | StoreEntry *e = (StoreEntry *)entry; |
6a566b9c | 97 | heap_key key; |
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; | |
b6a7f52c | 100 | key = heap_age + ((double) e->refcount / size) - tie; |
e4049756 | 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 << | |
104 | " -> " << key); | |
62e76326 | 105 | |
cb868059 AR |
106 | if (e->mem_obj) |
107 | debugs(81, 3, "storeId=" << e->mem_obj->storeId()); | |
62e76326 | 108 | |
6a566b9c | 109 | return key; |
110 | } | |
111 | ||
62e76326 | 112 | /* |
6a566b9c | 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... | |
118 | */ | |
f0debecb | 119 | heap_key |
b6a7f52c | 120 | HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age) |
6a566b9c | 121 | { |
e6ccf245 | 122 | StoreEntry *e = (StoreEntry *)entry; |
26ac0430 AJ |
123 | debugs(81, 3, "HeapKeyGen_StoreEntry_LRU: " << |
124 | e->getMD5Text() << " heap_age=" << heap_age << | |
125 | " lastref=" << (double) e->lastref ); | |
62e76326 | 126 | |
cb868059 AR |
127 | if (e->mem_obj) |
128 | debugs(81, 3, "storeId=" << e->mem_obj->storeId()); | |
62e76326 | 129 | |
6a566b9c | 130 | return (heap_key) e->lastref; |
131 | } |