]>
Commit | Line | Data |
---|---|---|
bdbb6d04 | 1 | |
2 | /* | |
262a0e14 | 3 | * $Id$ |
bdbb6d04 | 4 | * |
8638fc66 | 5 | * DEBUG: section 70 Cache Digest |
bdbb6d04 | 6 | * AUTHOR: Alex Rousskov |
7 | * | |
2b6662ba | 8 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 9 | * ---------------------------------------------------------- |
bdbb6d04 | 10 | * |
2b6662ba | 11 | * Squid is the result of efforts by numerous individuals from |
12 | * the Internet community; see the CONTRIBUTORS file for full | |
13 | * details. Many organizations have provided support for Squid's | |
14 | * development; see the SPONSORS file for full details. Squid is | |
15 | * Copyrighted (C) 2001 by the Regents of the University of | |
16 | * California; see the COPYRIGHT file for full details. Squid | |
17 | * incorporates software developed and/or copyrighted by other | |
18 | * sources; see the CREDITS file for full details. | |
bdbb6d04 | 19 | * |
20 | * This program is free software; you can redistribute it and/or modify | |
21 | * it under the terms of the GNU General Public License as published by | |
22 | * the Free Software Foundation; either version 2 of the License, or | |
23 | * (at your option) any later version. | |
26ac0430 | 24 | * |
bdbb6d04 | 25 | * This program is distributed in the hope that it will be useful, |
26 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
27 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
28 | * GNU General Public License for more details. | |
26ac0430 | 29 | * |
bdbb6d04 | 30 | * You should have received a copy of the GNU General Public License |
31 | * along with this program; if not, write to the Free Software | |
cbdec147 | 32 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 33 | * |
bdbb6d04 | 34 | */ |
35 | ||
36 | #include "squid.h" | |
e6ccf245 | 37 | #include "Store.h" |
bdbb6d04 | 38 | |
c68e9c6b | 39 | #if USE_CACHE_DIGESTS |
40 | ||
12784378 | 41 | /* local types */ |
62e76326 | 42 | |
26ac0430 | 43 | typedef struct { |
b644367b | 44 | int bit_count; /* total number of bits */ |
45 | int bit_on_count; /* #bits turned on */ | |
46 | int bseq_len_sum; /* sum of all bit seq length */ | |
47 | int bseq_count; /* number of bit seqs */ | |
2fadd50d | 48 | } CacheDigestStats; |
12784378 | 49 | |
50 | /* local functions */ | |
13c31e72 | 51 | static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key); |
bdbb6d04 | 52 | |
53 | /* static array used by cacheDigestHashKey for optimization purposes */ | |
a9245686 | 54 | static u_int32_t hashed_keys[4]; |
bdbb6d04 | 55 | |
315127ff | 56 | static void |
4b4cd312 | 57 | cacheDigestInit(CacheDigest * cd, int capacity, int bpe) |
bdbb6d04 | 58 | { |
315127ff | 59 | const size_t mask_size = cacheDigestCalcMaskSize(capacity, bpe); |
60 | assert(cd); | |
61 | assert(capacity > 0 && bpe > 0); | |
62 | assert(mask_size > 0); | |
63 | cd->capacity = capacity; | |
64 | cd->bits_per_entry = bpe; | |
65 | cd->mask_size = mask_size; | |
e6ccf245 | 66 | cd->mask = (char *)xcalloc(cd->mask_size, 1); |
6edb5d4a | 67 | debugs(70, 2, "cacheDigestInit: capacity: " << cd->capacity << " entries, bpe: " << cd->bits_per_entry << "; size: " |
68 | << cd->mask_size << " bytes"); | |
56a1c446 | 69 | } |
70 | ||
56a1c446 | 71 | CacheDigest * |
315127ff | 72 | cacheDigestCreate(int capacity, int bpe) |
56a1c446 | 73 | { |
e6ccf245 | 74 | CacheDigest *cd = (CacheDigest *)memAllocate(MEM_CACHE_DIGEST); |
c3031d67 | 75 | assert(SQUID_MD5_DIGEST_LENGTH == 16); /* our hash functions rely on 16 byte keys */ |
315127ff | 76 | cacheDigestInit(cd, capacity, bpe); |
bdbb6d04 | 77 | return cd; |
78 | } | |
79 | ||
315127ff | 80 | static void |
81 | cacheDigestClean(CacheDigest * cd) | |
82 | { | |
83 | assert(cd); | |
84 | xfree(cd->mask); | |
85 | cd->mask = NULL; | |
86 | } | |
87 | ||
bdbb6d04 | 88 | void |
1afe05c5 | 89 | cacheDigestDestroy(CacheDigest * cd) |
bdbb6d04 | 90 | { |
91 | assert(cd); | |
315127ff | 92 | cacheDigestClean(cd); |
db1cd23c | 93 | memFree(cd, MEM_CACHE_DIGEST); |
bdbb6d04 | 94 | } |
95 | ||
6d80b36f | 96 | CacheDigest * |
97 | cacheDigestClone(const CacheDigest * cd) | |
98 | { | |
99 | CacheDigest *clone; | |
100 | assert(cd); | |
315127ff | 101 | clone = cacheDigestCreate(cd->capacity, cd->bits_per_entry); |
c2186446 | 102 | clone->count = cd->count; |
315127ff | 103 | clone->del_count = cd->del_count; |
104 | assert(cd->mask_size == clone->mask_size); | |
6d80b36f | 105 | xmemcpy(clone->mask, cd->mask, cd->mask_size); |
106 | return clone; | |
107 | } | |
108 | ||
12784378 | 109 | void |
110 | cacheDigestClear(CacheDigest * cd) | |
111 | { | |
112 | assert(cd); | |
113 | cd->count = cd->del_count = 0; | |
114 | memset(cd->mask, 0, cd->mask_size); | |
115 | } | |
116 | ||
315127ff | 117 | /* changes mask size, resets bits to 0, preserves "cd" pointer */ |
304b267e | 118 | void |
119 | cacheDigestChangeCap(CacheDigest * cd, int new_cap) | |
120 | { | |
121 | assert(cd); | |
315127ff | 122 | cacheDigestClean(cd); |
123 | cacheDigestInit(cd, new_cap, cd->bits_per_entry); | |
304b267e | 124 | } |
125 | ||
bdbb6d04 | 126 | /* returns true if the key belongs to the digest */ |
127 | int | |
1afe05c5 | 128 | cacheDigestTest(const CacheDigest * cd, const cache_key * key) |
bdbb6d04 | 129 | { |
130 | assert(cd && key); | |
131 | /* hash */ | |
56a1c446 | 132 | cacheDigestHashKey(cd, key); |
bdbb6d04 | 133 | /* test corresponding bits */ |
1afe05c5 | 134 | return |
62e76326 | 135 | CBIT_TEST(cd->mask, hashed_keys[0]) && |
136 | CBIT_TEST(cd->mask, hashed_keys[1]) && | |
137 | CBIT_TEST(cd->mask, hashed_keys[2]) && | |
138 | CBIT_TEST(cd->mask, hashed_keys[3]); | |
bdbb6d04 | 139 | } |
140 | ||
c2186446 | 141 | void |
142 | cacheDigestAdd(CacheDigest * cd, const cache_key * key) | |
143 | { | |
144 | assert(cd && key); | |
145 | /* hash */ | |
56a1c446 | 146 | cacheDigestHashKey(cd, key); |
c2186446 | 147 | /* turn on corresponding bits */ |
c135694e | 148 | #if CD_FAST_ADD |
62e76326 | 149 | |
c2186446 | 150 | CBIT_SET(cd->mask, hashed_keys[0]); |
151 | CBIT_SET(cd->mask, hashed_keys[1]); | |
152 | CBIT_SET(cd->mask, hashed_keys[2]); | |
153 | CBIT_SET(cd->mask, hashed_keys[3]); | |
c135694e | 154 | #else |
62e76326 | 155 | |
c135694e | 156 | { |
62e76326 | 157 | int on_xition_cnt = 0; |
158 | ||
26ac0430 | 159 | if (!CBIT_TEST(cd->mask, hashed_keys[0])) { |
62e76326 | 160 | CBIT_SET(cd->mask, hashed_keys[0]); |
161 | on_xition_cnt++; | |
162 | } | |
163 | ||
26ac0430 | 164 | if (!CBIT_TEST(cd->mask, hashed_keys[1])) { |
62e76326 | 165 | CBIT_SET(cd->mask, hashed_keys[1]); |
166 | on_xition_cnt++; | |
167 | } | |
168 | ||
26ac0430 | 169 | if (!CBIT_TEST(cd->mask, hashed_keys[2])) { |
62e76326 | 170 | CBIT_SET(cd->mask, hashed_keys[2]); |
171 | on_xition_cnt++; | |
172 | } | |
173 | ||
26ac0430 | 174 | if (!CBIT_TEST(cd->mask, hashed_keys[3])) { |
62e76326 | 175 | CBIT_SET(cd->mask, hashed_keys[3]); |
176 | on_xition_cnt++; | |
177 | } | |
178 | ||
179 | statHistCount(&statCounter.cd.on_xition_count, on_xition_cnt); | |
c135694e | 180 | } |
181 | #endif | |
c2186446 | 182 | cd->count++; |
183 | } | |
184 | ||
bdbb6d04 | 185 | void |
1afe05c5 | 186 | cacheDigestDel(CacheDigest * cd, const cache_key * key) |
bdbb6d04 | 187 | { |
188 | assert(cd && key); | |
189 | cd->del_count++; | |
190 | /* we do not support deletions from the digest */ | |
191 | } | |
192 | ||
c2186446 | 193 | /* returns mask utilization parameters */ |
12784378 | 194 | static void |
b644367b | 195 | cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats) |
c2186446 | 196 | { |
c2186446 | 197 | int on_count = 0; |
56a1c446 | 198 | int pos = cd->mask_size * 8; |
12784378 | 199 | int seq_len_sum = 0; |
200 | int seq_count = 0; | |
201 | int cur_seq_len = 0; | |
202 | int cur_seq_type = 1; | |
203 | assert(stats); | |
204 | memset(stats, 0, sizeof(*stats)); | |
62e76326 | 205 | |
c2186446 | 206 | while (pos-- > 0) { |
62e76326 | 207 | const int is_on = 0 != CBIT_TEST(cd->mask, pos); |
208 | ||
209 | if (is_on) | |
210 | on_count++; | |
211 | ||
212 | if (is_on != cur_seq_type || !pos) { | |
213 | seq_len_sum += cur_seq_len; | |
214 | seq_count++; | |
215 | cur_seq_type = is_on; | |
216 | cur_seq_len = 0; | |
217 | } | |
218 | ||
219 | cur_seq_len++; | |
c2186446 | 220 | } |
62e76326 | 221 | |
56a1c446 | 222 | stats->bit_count = cd->mask_size * 8; |
12784378 | 223 | stats->bit_on_count = on_count; |
224 | stats->bseq_len_sum = seq_len_sum; | |
225 | stats->bseq_count = seq_count; | |
c2186446 | 226 | } |
bdbb6d04 | 227 | |
315127ff | 228 | int |
229 | cacheDigestBitUtil(const CacheDigest * cd) | |
230 | { | |
231 | CacheDigestStats stats; | |
232 | assert(cd); | |
233 | cacheDigestStats(cd, &stats); | |
234 | return xpercentInt(stats.bit_on_count, stats.bit_count); | |
235 | } | |
236 | ||
8638fc66 | 237 | void |
4b4cd312 | 238 | cacheDigestGuessStatsUpdate(cd_guess_stats * stats, int real_hit, int guess_hit) |
56a1c446 | 239 | { |
240 | assert(stats); | |
62e76326 | 241 | |
56a1c446 | 242 | if (real_hit) { |
62e76326 | 243 | if (guess_hit) |
244 | stats->true_hits++; | |
245 | else | |
246 | stats->false_misses++; | |
56a1c446 | 247 | } else { |
62e76326 | 248 | if (guess_hit) |
249 | stats->false_hits++; | |
250 | else | |
251 | stats->true_misses++; | |
56a1c446 | 252 | } |
253 | } | |
254 | ||
255 | void | |
4b4cd312 | 256 | cacheDigestGuessStatsReport(const cd_guess_stats * stats, StoreEntry * sentry, const char *label) |
56a1c446 | 257 | { |
258 | const int true_count = stats->true_hits + stats->true_misses; | |
259 | const int false_count = stats->false_hits + stats->false_misses; | |
260 | const int hit_count = stats->true_hits + stats->false_hits; | |
261 | const int miss_count = stats->true_misses + stats->false_misses; | |
262 | const int tot_count = true_count + false_count; | |
4b4cd312 | 263 | |
56a1c446 | 264 | assert(label); |
4b4cd312 | 265 | assert(tot_count == hit_count + miss_count); /* paranoid */ |
56a1c446 | 266 | |
e13ee7ad | 267 | if (!tot_count) { |
62e76326 | 268 | storeAppendPrintf(sentry, "no guess stats for %s available\n", label); |
269 | return; | |
e13ee7ad | 270 | } |
62e76326 | 271 | |
56a1c446 | 272 | storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label); |
273 | storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n"); | |
274 | storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n"); | |
56a1c446 | 275 | storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
62e76326 | 276 | stats->true_hits, xpercent(stats->true_hits, tot_count), |
277 | stats->true_misses, xpercent(stats->true_misses, tot_count), | |
278 | true_count, xpercent(true_count, tot_count)); | |
56a1c446 | 279 | storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
62e76326 | 280 | stats->false_hits, xpercent(stats->false_hits, tot_count), |
281 | stats->false_misses, xpercent(stats->false_misses, tot_count), | |
282 | false_count, xpercent(false_count, tot_count)); | |
56a1c446 | 283 | storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
62e76326 | 284 | hit_count, xpercent(hit_count, tot_count), |
285 | miss_count, xpercent(miss_count, tot_count), | |
286 | tot_count, xpercent(tot_count, tot_count)); | |
315127ff | 287 | storeAppendPrintf(sentry, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n", |
62e76326 | 288 | stats->close_hits, xpercentInt(stats->close_hits, stats->false_hits)); |
56a1c446 | 289 | } |
290 | ||
291 | void | |
4b4cd312 | 292 | cacheDigestReport(CacheDigest * cd, const char *label, StoreEntry * e) |
8638fc66 | 293 | { |
12784378 | 294 | CacheDigestStats stats; |
8638fc66 | 295 | assert(cd && e); |
12784378 | 296 | cacheDigestStats(cd, &stats); |
297 | storeAppendPrintf(e, "%s digest: size: %d bytes\n", | |
62e76326 | 298 | label ? label : "", stats.bit_count / 8 |
299 | ); | |
8638fc66 | 300 | storeAppendPrintf(e, "\t entries: count: %d capacity: %d util: %d%%\n", |
62e76326 | 301 | cd->count, |
302 | cd->capacity, | |
303 | xpercentInt(cd->count, cd->capacity) | |
304 | ); | |
b644367b | 305 | storeAppendPrintf(e, "\t deletion attempts: %d\n", |
62e76326 | 306 | cd->del_count |
307 | ); | |
315127ff | 308 | storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n", |
62e76326 | 309 | cd->bits_per_entry, |
310 | stats.bit_on_count, stats.bit_count, | |
311 | xpercentInt(stats.bit_on_count, stats.bit_count) | |
312 | ); | |
b644367b | 313 | storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n", |
62e76326 | 314 | stats.bseq_count, |
315 | xdiv(stats.bseq_len_sum, stats.bseq_count) | |
316 | ); | |
8638fc66 | 317 | } |
318 | ||
315127ff | 319 | size_t |
320 | cacheDigestCalcMaskSize(int cap, int bpe) | |
304b267e | 321 | { |
315127ff | 322 | return (size_t) (cap * bpe + 7) / 8; |
304b267e | 323 | } |
324 | ||
e5834061 | 325 | static void |
5999b776 | 326 | cacheDigestHashKey(const CacheDigest * cd, const cache_key * key) |
e5834061 | 327 | { |
328 | const unsigned int bit_count = cd->mask_size * 8; | |
13c31e72 | 329 | unsigned int tmp_keys[4]; |
330 | /* we must memcpy to ensure alignment */ | |
331 | xmemcpy(tmp_keys, key, sizeof(tmp_keys)); | |
e5834061 | 332 | hashed_keys[0] = htonl(tmp_keys[0]) % bit_count; |
333 | hashed_keys[1] = htonl(tmp_keys[1]) % bit_count; | |
334 | hashed_keys[2] = htonl(tmp_keys[2]) % bit_count; | |
335 | hashed_keys[3] = htonl(tmp_keys[3]) % bit_count; | |
bf8fe701 | 336 | debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key) << " -(" << |
337 | bit_count << ")-> " << hashed_keys[0] << " " << hashed_keys[1] << | |
338 | " " << hashed_keys[2] << " " << hashed_keys[3]); | |
e5834061 | 339 | } |
c68e9c6b | 340 | |
341 | #endif |