]>
Commit | Line | Data |
---|---|---|
bdbb6d04 | 1 | /* |
bbc27441 | 2 | * Copyright (C) 1996-2014 The Squid Software Foundation and contributors |
e25c139f | 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. | |
bdbb6d04 | 7 | */ |
8 | ||
bbc27441 AJ |
9 | /* DEBUG: section 70 Cache Digest */ |
10 | ||
582c2af2 FC |
11 | #include "squid.h" |
12 | #include "md5.h" | |
e4f1fdae | 13 | #include "StatCounters.h" |
e6ccf245 | 14 | #include "Store.h" |
fb548aaf | 15 | #include "store_key_md5.h" |
bdbb6d04 | 16 | |
c68e9c6b | 17 | #if USE_CACHE_DIGESTS |
18 | ||
b814e8d4 | 19 | #include "CacheDigest.h" |
ed6e9fb9 | 20 | #include "util.h" |
b814e8d4 | 21 | |
12784378 | 22 | /* local types */ |
62e76326 | 23 | |
26ac0430 | 24 | typedef struct { |
f53969cc SM |
25 | int bit_count; /* total number of bits */ |
26 | int bit_on_count; /* #bits turned on */ | |
27 | int bseq_len_sum; /* sum of all bit seq length */ | |
28 | int bseq_count; /* number of bit seqs */ | |
2fadd50d | 29 | } CacheDigestStats; |
12784378 | 30 | |
31 | /* local functions */ | |
13c31e72 | 32 | static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key); |
bdbb6d04 | 33 | |
34 | /* static array used by cacheDigestHashKey for optimization purposes */ | |
09aabd84 | 35 | static uint32_t hashed_keys[4]; |
bdbb6d04 | 36 | |
315127ff | 37 | static void |
4b4cd312 | 38 | cacheDigestInit(CacheDigest * cd, int capacity, int bpe) |
bdbb6d04 | 39 | { |
315127ff | 40 | const size_t mask_size = cacheDigestCalcMaskSize(capacity, bpe); |
41 | assert(cd); | |
42 | assert(capacity > 0 && bpe > 0); | |
43 | assert(mask_size > 0); | |
44 | cd->capacity = capacity; | |
45 | cd->bits_per_entry = bpe; | |
46 | cd->mask_size = mask_size; | |
e6ccf245 | 47 | cd->mask = (char *)xcalloc(cd->mask_size, 1); |
6edb5d4a | 48 | debugs(70, 2, "cacheDigestInit: capacity: " << cd->capacity << " entries, bpe: " << cd->bits_per_entry << "; size: " |
49 | << cd->mask_size << " bytes"); | |
56a1c446 | 50 | } |
51 | ||
56a1c446 | 52 | CacheDigest * |
315127ff | 53 | cacheDigestCreate(int capacity, int bpe) |
56a1c446 | 54 | { |
e6ccf245 | 55 | CacheDigest *cd = (CacheDigest *)memAllocate(MEM_CACHE_DIGEST); |
f53969cc | 56 | assert(SQUID_MD5_DIGEST_LENGTH == 16); /* our hash functions rely on 16 byte keys */ |
315127ff | 57 | cacheDigestInit(cd, capacity, bpe); |
bdbb6d04 | 58 | return cd; |
59 | } | |
60 | ||
315127ff | 61 | static void |
62 | cacheDigestClean(CacheDigest * cd) | |
63 | { | |
64 | assert(cd); | |
65 | xfree(cd->mask); | |
66 | cd->mask = NULL; | |
67 | } | |
68 | ||
bdbb6d04 | 69 | void |
1afe05c5 | 70 | cacheDigestDestroy(CacheDigest * cd) |
bdbb6d04 | 71 | { |
72 | assert(cd); | |
315127ff | 73 | cacheDigestClean(cd); |
db1cd23c | 74 | memFree(cd, MEM_CACHE_DIGEST); |
bdbb6d04 | 75 | } |
76 | ||
6d80b36f | 77 | CacheDigest * |
78 | cacheDigestClone(const CacheDigest * cd) | |
79 | { | |
80 | CacheDigest *clone; | |
81 | assert(cd); | |
315127ff | 82 | clone = cacheDigestCreate(cd->capacity, cd->bits_per_entry); |
c2186446 | 83 | clone->count = cd->count; |
315127ff | 84 | clone->del_count = cd->del_count; |
85 | assert(cd->mask_size == clone->mask_size); | |
41d00cd3 | 86 | memcpy(clone->mask, cd->mask, cd->mask_size); |
6d80b36f | 87 | return clone; |
88 | } | |
89 | ||
12784378 | 90 | void |
91 | cacheDigestClear(CacheDigest * cd) | |
92 | { | |
93 | assert(cd); | |
94 | cd->count = cd->del_count = 0; | |
95 | memset(cd->mask, 0, cd->mask_size); | |
96 | } | |
97 | ||
315127ff | 98 | /* changes mask size, resets bits to 0, preserves "cd" pointer */ |
304b267e | 99 | void |
100 | cacheDigestChangeCap(CacheDigest * cd, int new_cap) | |
101 | { | |
102 | assert(cd); | |
315127ff | 103 | cacheDigestClean(cd); |
104 | cacheDigestInit(cd, new_cap, cd->bits_per_entry); | |
304b267e | 105 | } |
106 | ||
bdbb6d04 | 107 | /* returns true if the key belongs to the digest */ |
108 | int | |
1afe05c5 | 109 | cacheDigestTest(const CacheDigest * cd, const cache_key * key) |
bdbb6d04 | 110 | { |
111 | assert(cd && key); | |
112 | /* hash */ | |
56a1c446 | 113 | cacheDigestHashKey(cd, key); |
bdbb6d04 | 114 | /* test corresponding bits */ |
1afe05c5 | 115 | return |
62e76326 | 116 | CBIT_TEST(cd->mask, hashed_keys[0]) && |
117 | CBIT_TEST(cd->mask, hashed_keys[1]) && | |
118 | CBIT_TEST(cd->mask, hashed_keys[2]) && | |
119 | CBIT_TEST(cd->mask, hashed_keys[3]); | |
bdbb6d04 | 120 | } |
121 | ||
c2186446 | 122 | void |
123 | cacheDigestAdd(CacheDigest * cd, const cache_key * key) | |
124 | { | |
125 | assert(cd && key); | |
126 | /* hash */ | |
56a1c446 | 127 | cacheDigestHashKey(cd, key); |
c2186446 | 128 | /* turn on corresponding bits */ |
c135694e | 129 | #if CD_FAST_ADD |
62e76326 | 130 | |
c2186446 | 131 | CBIT_SET(cd->mask, hashed_keys[0]); |
132 | CBIT_SET(cd->mask, hashed_keys[1]); | |
133 | CBIT_SET(cd->mask, hashed_keys[2]); | |
134 | CBIT_SET(cd->mask, hashed_keys[3]); | |
c135694e | 135 | #else |
62e76326 | 136 | |
c135694e | 137 | { |
62e76326 | 138 | int on_xition_cnt = 0; |
139 | ||
26ac0430 | 140 | if (!CBIT_TEST(cd->mask, hashed_keys[0])) { |
62e76326 | 141 | CBIT_SET(cd->mask, hashed_keys[0]); |
d7ae3534 | 142 | ++on_xition_cnt; |
62e76326 | 143 | } |
144 | ||
26ac0430 | 145 | if (!CBIT_TEST(cd->mask, hashed_keys[1])) { |
62e76326 | 146 | CBIT_SET(cd->mask, hashed_keys[1]); |
d7ae3534 | 147 | ++on_xition_cnt; |
62e76326 | 148 | } |
149 | ||
26ac0430 | 150 | if (!CBIT_TEST(cd->mask, hashed_keys[2])) { |
62e76326 | 151 | CBIT_SET(cd->mask, hashed_keys[2]); |
d7ae3534 | 152 | ++on_xition_cnt; |
62e76326 | 153 | } |
154 | ||
26ac0430 | 155 | if (!CBIT_TEST(cd->mask, hashed_keys[3])) { |
62e76326 | 156 | CBIT_SET(cd->mask, hashed_keys[3]); |
d7ae3534 | 157 | ++on_xition_cnt; |
62e76326 | 158 | } |
159 | ||
f30f7998 | 160 | statCounter.cd.on_xition_count.count(on_xition_cnt); |
c135694e | 161 | } |
162 | #endif | |
d7ae3534 | 163 | ++ cd->count; |
c2186446 | 164 | } |
165 | ||
bdbb6d04 | 166 | void |
1afe05c5 | 167 | cacheDigestDel(CacheDigest * cd, const cache_key * key) |
bdbb6d04 | 168 | { |
169 | assert(cd && key); | |
d7ae3534 | 170 | ++ cd->del_count; |
bdbb6d04 | 171 | /* we do not support deletions from the digest */ |
172 | } | |
173 | ||
c2186446 | 174 | /* returns mask utilization parameters */ |
12784378 | 175 | static void |
b644367b | 176 | cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats) |
c2186446 | 177 | { |
c2186446 | 178 | int on_count = 0; |
56a1c446 | 179 | int pos = cd->mask_size * 8; |
12784378 | 180 | int seq_len_sum = 0; |
181 | int seq_count = 0; | |
182 | int cur_seq_len = 0; | |
183 | int cur_seq_type = 1; | |
184 | assert(stats); | |
185 | memset(stats, 0, sizeof(*stats)); | |
62e76326 | 186 | |
c2186446 | 187 | while (pos-- > 0) { |
62e76326 | 188 | const int is_on = 0 != CBIT_TEST(cd->mask, pos); |
189 | ||
190 | if (is_on) | |
d7ae3534 | 191 | ++on_count; |
62e76326 | 192 | |
193 | if (is_on != cur_seq_type || !pos) { | |
194 | seq_len_sum += cur_seq_len; | |
d7ae3534 | 195 | ++seq_count; |
62e76326 | 196 | cur_seq_type = is_on; |
197 | cur_seq_len = 0; | |
198 | } | |
199 | ||
d7ae3534 | 200 | ++cur_seq_len; |
c2186446 | 201 | } |
62e76326 | 202 | |
56a1c446 | 203 | stats->bit_count = cd->mask_size * 8; |
12784378 | 204 | stats->bit_on_count = on_count; |
205 | stats->bseq_len_sum = seq_len_sum; | |
206 | stats->bseq_count = seq_count; | |
c2186446 | 207 | } |
bdbb6d04 | 208 | |
315127ff | 209 | int |
210 | cacheDigestBitUtil(const CacheDigest * cd) | |
211 | { | |
212 | CacheDigestStats stats; | |
213 | assert(cd); | |
214 | cacheDigestStats(cd, &stats); | |
215 | return xpercentInt(stats.bit_on_count, stats.bit_count); | |
216 | } | |
217 | ||
8638fc66 | 218 | void |
e8baef82 | 219 | cacheDigestGuessStatsUpdate(CacheDigestGuessStats * stats, int real_hit, int guess_hit) |
56a1c446 | 220 | { |
221 | assert(stats); | |
62e76326 | 222 | |
56a1c446 | 223 | if (real_hit) { |
62e76326 | 224 | if (guess_hit) |
e8baef82 | 225 | ++stats->trueHits; |
62e76326 | 226 | else |
e8baef82 | 227 | ++stats->falseMisses; |
56a1c446 | 228 | } else { |
62e76326 | 229 | if (guess_hit) |
e8baef82 | 230 | ++stats->falseHits; |
62e76326 | 231 | else |
e8baef82 | 232 | ++stats->trueMisses; |
56a1c446 | 233 | } |
234 | } | |
235 | ||
236 | void | |
e8baef82 | 237 | cacheDigestGuessStatsReport(const CacheDigestGuessStats * stats, StoreEntry * sentry, const char *label) |
56a1c446 | 238 | { |
e8baef82 FC |
239 | const int true_count = stats->trueHits + stats->trueMisses; |
240 | const int false_count = stats->falseHits + stats->falseMisses; | |
241 | const int hit_count = stats->trueHits + stats->falseHits; | |
242 | const int miss_count = stats->trueMisses + stats->falseMisses; | |
56a1c446 | 243 | const int tot_count = true_count + false_count; |
4b4cd312 | 244 | |
56a1c446 | 245 | assert(label); |
f53969cc | 246 | assert(tot_count == hit_count + miss_count); /* paranoid */ |
56a1c446 | 247 | |
e13ee7ad | 248 | if (!tot_count) { |
62e76326 | 249 | storeAppendPrintf(sentry, "no guess stats for %s available\n", label); |
250 | return; | |
e13ee7ad | 251 | } |
62e76326 | 252 | |
56a1c446 | 253 | storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label); |
254 | storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n"); | |
255 | storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n"); | |
56a1c446 | 256 | storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
e8baef82 FC |
257 | stats->trueHits, xpercent(stats->trueHits, tot_count), |
258 | stats->trueMisses, xpercent(stats->trueMisses, tot_count), | |
62e76326 | 259 | true_count, xpercent(true_count, tot_count)); |
56a1c446 | 260 | storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
e8baef82 FC |
261 | stats->falseHits, xpercent(stats->falseHits, tot_count), |
262 | stats->falseMisses, xpercent(stats->falseMisses, tot_count), | |
62e76326 | 263 | false_count, xpercent(false_count, tot_count)); |
56a1c446 | 264 | storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
62e76326 | 265 | hit_count, xpercent(hit_count, tot_count), |
266 | miss_count, xpercent(miss_count, tot_count), | |
267 | tot_count, xpercent(tot_count, tot_count)); | |
315127ff | 268 | storeAppendPrintf(sentry, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n", |
e8baef82 | 269 | stats->closeHits, xpercentInt(stats->closeHits, stats->falseHits)); |
56a1c446 | 270 | } |
271 | ||
272 | void | |
4b4cd312 | 273 | cacheDigestReport(CacheDigest * cd, const char *label, StoreEntry * e) |
8638fc66 | 274 | { |
12784378 | 275 | CacheDigestStats stats; |
8638fc66 | 276 | assert(cd && e); |
12784378 | 277 | cacheDigestStats(cd, &stats); |
278 | storeAppendPrintf(e, "%s digest: size: %d bytes\n", | |
62e76326 | 279 | label ? label : "", stats.bit_count / 8 |
280 | ); | |
8638fc66 | 281 | storeAppendPrintf(e, "\t entries: count: %d capacity: %d util: %d%%\n", |
62e76326 | 282 | cd->count, |
283 | cd->capacity, | |
284 | xpercentInt(cd->count, cd->capacity) | |
285 | ); | |
b644367b | 286 | storeAppendPrintf(e, "\t deletion attempts: %d\n", |
62e76326 | 287 | cd->del_count |
288 | ); | |
315127ff | 289 | storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n", |
62e76326 | 290 | cd->bits_per_entry, |
291 | stats.bit_on_count, stats.bit_count, | |
292 | xpercentInt(stats.bit_on_count, stats.bit_count) | |
293 | ); | |
b644367b | 294 | storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n", |
62e76326 | 295 | stats.bseq_count, |
296 | xdiv(stats.bseq_len_sum, stats.bseq_count) | |
297 | ); | |
8638fc66 | 298 | } |
299 | ||
315127ff | 300 | size_t |
301 | cacheDigestCalcMaskSize(int cap, int bpe) | |
304b267e | 302 | { |
315127ff | 303 | return (size_t) (cap * bpe + 7) / 8; |
304b267e | 304 | } |
305 | ||
e5834061 | 306 | static void |
5999b776 | 307 | cacheDigestHashKey(const CacheDigest * cd, const cache_key * key) |
e5834061 | 308 | { |
309 | const unsigned int bit_count = cd->mask_size * 8; | |
13c31e72 | 310 | unsigned int tmp_keys[4]; |
311 | /* we must memcpy to ensure alignment */ | |
41d00cd3 | 312 | memcpy(tmp_keys, key, sizeof(tmp_keys)); |
e5834061 | 313 | hashed_keys[0] = htonl(tmp_keys[0]) % bit_count; |
314 | hashed_keys[1] = htonl(tmp_keys[1]) % bit_count; | |
315 | hashed_keys[2] = htonl(tmp_keys[2]) % bit_count; | |
316 | hashed_keys[3] = htonl(tmp_keys[3]) % bit_count; | |
bf8fe701 | 317 | debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key) << " -(" << |
318 | bit_count << ")-> " << hashed_keys[0] << " " << hashed_keys[1] << | |
319 | " " << hashed_keys[2] << " " << hashed_keys[3]); | |
e5834061 | 320 | } |
c68e9c6b | 321 | |
322 | #endif | |
f53969cc | 323 |