]>
Commit | Line | Data |
---|---|---|
bdbb6d04 | 1 | /* |
5b74111a | 2 | * Copyright (C) 1996-2018 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 | |
afffcaab | 37 | void |
831e953c | 38 | CacheDigest::init(uint64_t newCapacity) |
bdbb6d04 | 39 | { |
afffcaab AJ |
40 | const auto newMaskSz = CacheDigest::CalcMaskSize(newCapacity, bits_per_entry); |
41 | assert(newCapacity > 0 && bits_per_entry > 0); | |
831e953c | 42 | assert(newMaskSz != 0); |
afffcaab AJ |
43 | capacity = newCapacity; |
44 | mask_size = newMaskSz; | |
45 | mask = static_cast<char *>(xcalloc(mask_size,1)); | |
46 | debugs(70, 2, "capacity: " << capacity << " entries, bpe: " << bits_per_entry << "; size: " | |
47 | << mask_size << " bytes"); | |
56a1c446 | 48 | } |
49 | ||
831e953c AJ |
50 | CacheDigest::CacheDigest(uint64_t aCapacity, uint8_t bpe) : |
51 | count(0), | |
52 | del_count(0), | |
53 | capacity(0), | |
895171b1 SM |
54 | mask(nullptr), |
55 | mask_size(0), | |
831e953c | 56 | bits_per_entry(bpe) |
56a1c446 | 57 | { |
f53969cc | 58 | assert(SQUID_MD5_DIGEST_LENGTH == 16); /* our hash functions rely on 16 byte keys */ |
7daad00c | 59 | updateCapacity(aCapacity); |
bdbb6d04 | 60 | } |
61 | ||
a901d0b4 | 62 | CacheDigest::~CacheDigest() |
315127ff | 63 | { |
a901d0b4 | 64 | xfree(mask); |
bdbb6d04 | 65 | } |
66 | ||
6d80b36f | 67 | CacheDigest * |
fab3d38b | 68 | CacheDigest::clone() const |
6d80b36f | 69 | { |
978eaffc AJ |
70 | CacheDigest *cl = new CacheDigest(capacity, bits_per_entry); |
71 | cl->count = count; | |
72 | cl->del_count = del_count; | |
73 | assert(mask_size == cl->mask_size); | |
74 | memcpy(cl->mask, mask, mask_size); | |
75 | return cl; | |
6d80b36f | 76 | } |
77 | ||
12784378 | 78 | void |
28faff32 | 79 | CacheDigest::clear() |
12784378 | 80 | { |
28faff32 AJ |
81 | count = del_count = 0; |
82 | memset(mask, 0, mask_size); | |
12784378 | 83 | } |
84 | ||
304b267e | 85 | void |
831e953c | 86 | CacheDigest::updateCapacity(uint64_t newCapacity) |
304b267e | 87 | { |
7daad00c | 88 | safe_free(mask); |
afffcaab | 89 | init(newCapacity); // will re-init mask and mask_size |
304b267e | 90 | } |
91 | ||
5bc5e81f | 92 | bool |
6fc4e508 | 93 | CacheDigest::contains(const cache_key * key) const |
bdbb6d04 | 94 | { |
5bc5e81f | 95 | assert(key); |
bdbb6d04 | 96 | /* hash */ |
5bc5e81f | 97 | cacheDigestHashKey(this, key); |
bdbb6d04 | 98 | /* test corresponding bits */ |
1afe05c5 | 99 | return |
5bc5e81f AJ |
100 | CBIT_TEST(mask, hashed_keys[0]) && |
101 | CBIT_TEST(mask, hashed_keys[1]) && | |
102 | CBIT_TEST(mask, hashed_keys[2]) && | |
103 | CBIT_TEST(mask, hashed_keys[3]); | |
bdbb6d04 | 104 | } |
105 | ||
c2186446 | 106 | void |
fbba122c | 107 | CacheDigest::add(const cache_key * key) |
c2186446 | 108 | { |
fbba122c | 109 | assert(key); |
c2186446 | 110 | /* hash */ |
fbba122c | 111 | cacheDigestHashKey(this, key); |
c2186446 | 112 | /* turn on corresponding bits */ |
c135694e | 113 | #if CD_FAST_ADD |
62e76326 | 114 | |
fbba122c AJ |
115 | CBIT_SET(mask, hashed_keys[0]); |
116 | CBIT_SET(mask, hashed_keys[1]); | |
117 | CBIT_SET(mask, hashed_keys[2]); | |
118 | CBIT_SET(mask, hashed_keys[3]); | |
c135694e | 119 | #else |
62e76326 | 120 | |
c135694e | 121 | { |
62e76326 | 122 | int on_xition_cnt = 0; |
123 | ||
fbba122c AJ |
124 | if (!CBIT_TEST(mask, hashed_keys[0])) { |
125 | CBIT_SET(mask, hashed_keys[0]); | |
d7ae3534 | 126 | ++on_xition_cnt; |
62e76326 | 127 | } |
128 | ||
fbba122c AJ |
129 | if (!CBIT_TEST(mask, hashed_keys[1])) { |
130 | CBIT_SET(mask, hashed_keys[1]); | |
d7ae3534 | 131 | ++on_xition_cnt; |
62e76326 | 132 | } |
133 | ||
fbba122c AJ |
134 | if (!CBIT_TEST(mask, hashed_keys[2])) { |
135 | CBIT_SET(mask, hashed_keys[2]); | |
d7ae3534 | 136 | ++on_xition_cnt; |
62e76326 | 137 | } |
138 | ||
fbba122c AJ |
139 | if (!CBIT_TEST(mask, hashed_keys[3])) { |
140 | CBIT_SET(mask, hashed_keys[3]); | |
d7ae3534 | 141 | ++on_xition_cnt; |
62e76326 | 142 | } |
143 | ||
f30f7998 | 144 | statCounter.cd.on_xition_count.count(on_xition_cnt); |
c135694e | 145 | } |
146 | #endif | |
fbba122c | 147 | ++count; |
c2186446 | 148 | } |
149 | ||
bdbb6d04 | 150 | void |
fbba122c | 151 | CacheDigest::remove(const cache_key * key) |
bdbb6d04 | 152 | { |
fbba122c AJ |
153 | assert(key); |
154 | ++del_count; | |
bdbb6d04 | 155 | /* we do not support deletions from the digest */ |
156 | } | |
157 | ||
c2186446 | 158 | /* returns mask utilization parameters */ |
12784378 | 159 | static void |
b644367b | 160 | cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats) |
c2186446 | 161 | { |
c2186446 | 162 | int on_count = 0; |
56a1c446 | 163 | int pos = cd->mask_size * 8; |
12784378 | 164 | int seq_len_sum = 0; |
165 | int seq_count = 0; | |
166 | int cur_seq_len = 0; | |
167 | int cur_seq_type = 1; | |
168 | assert(stats); | |
169 | memset(stats, 0, sizeof(*stats)); | |
62e76326 | 170 | |
c2186446 | 171 | while (pos-- > 0) { |
62e76326 | 172 | const int is_on = 0 != CBIT_TEST(cd->mask, pos); |
173 | ||
174 | if (is_on) | |
d7ae3534 | 175 | ++on_count; |
62e76326 | 176 | |
177 | if (is_on != cur_seq_type || !pos) { | |
178 | seq_len_sum += cur_seq_len; | |
d7ae3534 | 179 | ++seq_count; |
62e76326 | 180 | cur_seq_type = is_on; |
181 | cur_seq_len = 0; | |
182 | } | |
183 | ||
d7ae3534 | 184 | ++cur_seq_len; |
c2186446 | 185 | } |
62e76326 | 186 | |
56a1c446 | 187 | stats->bit_count = cd->mask_size * 8; |
12784378 | 188 | stats->bit_on_count = on_count; |
189 | stats->bseq_len_sum = seq_len_sum; | |
190 | stats->bseq_count = seq_count; | |
c2186446 | 191 | } |
bdbb6d04 | 192 | |
6fbd1d41 AJ |
193 | double |
194 | CacheDigest::usedMaskPercent() const | |
315127ff | 195 | { |
196 | CacheDigestStats stats; | |
6fbd1d41 AJ |
197 | cacheDigestStats(this, &stats); |
198 | return xpercent(stats.bit_on_count, stats.bit_count); | |
315127ff | 199 | } |
200 | ||
8638fc66 | 201 | void |
e8baef82 | 202 | cacheDigestGuessStatsUpdate(CacheDigestGuessStats * stats, int real_hit, int guess_hit) |
56a1c446 | 203 | { |
204 | assert(stats); | |
62e76326 | 205 | |
56a1c446 | 206 | if (real_hit) { |
62e76326 | 207 | if (guess_hit) |
e8baef82 | 208 | ++stats->trueHits; |
62e76326 | 209 | else |
e8baef82 | 210 | ++stats->falseMisses; |
56a1c446 | 211 | } else { |
62e76326 | 212 | if (guess_hit) |
e8baef82 | 213 | ++stats->falseHits; |
62e76326 | 214 | else |
e8baef82 | 215 | ++stats->trueMisses; |
56a1c446 | 216 | } |
217 | } | |
218 | ||
219 | void | |
e8baef82 | 220 | cacheDigestGuessStatsReport(const CacheDigestGuessStats * stats, StoreEntry * sentry, const char *label) |
56a1c446 | 221 | { |
e8baef82 FC |
222 | const int true_count = stats->trueHits + stats->trueMisses; |
223 | const int false_count = stats->falseHits + stats->falseMisses; | |
224 | const int hit_count = stats->trueHits + stats->falseHits; | |
225 | const int miss_count = stats->trueMisses + stats->falseMisses; | |
56a1c446 | 226 | const int tot_count = true_count + false_count; |
4b4cd312 | 227 | |
56a1c446 | 228 | assert(label); |
f53969cc | 229 | assert(tot_count == hit_count + miss_count); /* paranoid */ |
56a1c446 | 230 | |
e13ee7ad | 231 | if (!tot_count) { |
62e76326 | 232 | storeAppendPrintf(sentry, "no guess stats for %s available\n", label); |
233 | return; | |
e13ee7ad | 234 | } |
62e76326 | 235 | |
56a1c446 | 236 | storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label); |
237 | storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n"); | |
238 | storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n"); | |
56a1c446 | 239 | storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
e8baef82 FC |
240 | stats->trueHits, xpercent(stats->trueHits, tot_count), |
241 | stats->trueMisses, xpercent(stats->trueMisses, tot_count), | |
62e76326 | 242 | true_count, xpercent(true_count, tot_count)); |
56a1c446 | 243 | storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
e8baef82 FC |
244 | stats->falseHits, xpercent(stats->falseHits, tot_count), |
245 | stats->falseMisses, xpercent(stats->falseMisses, tot_count), | |
62e76326 | 246 | false_count, xpercent(false_count, tot_count)); |
56a1c446 | 247 | storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n", |
62e76326 | 248 | hit_count, xpercent(hit_count, tot_count), |
249 | miss_count, xpercent(miss_count, tot_count), | |
250 | tot_count, xpercent(tot_count, tot_count)); | |
315127ff | 251 | storeAppendPrintf(sentry, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n", |
e8baef82 | 252 | stats->closeHits, xpercentInt(stats->closeHits, stats->falseHits)); |
56a1c446 | 253 | } |
254 | ||
255 | void | |
4b4cd312 | 256 | cacheDigestReport(CacheDigest * cd, const char *label, StoreEntry * e) |
8638fc66 | 257 | { |
12784378 | 258 | CacheDigestStats stats; |
8638fc66 | 259 | assert(cd && e); |
12784378 | 260 | cacheDigestStats(cd, &stats); |
261 | storeAppendPrintf(e, "%s digest: size: %d bytes\n", | |
62e76326 | 262 | label ? label : "", stats.bit_count / 8 |
263 | ); | |
831e953c | 264 | storeAppendPrintf(e, "\t entries: count: %" PRIu64 " capacity: %" PRIu64 " util: %d%%\n", |
62e76326 | 265 | cd->count, |
266 | cd->capacity, | |
267 | xpercentInt(cd->count, cd->capacity) | |
268 | ); | |
831e953c | 269 | storeAppendPrintf(e, "\t deletion attempts: %" PRIu64 "\n", |
62e76326 | 270 | cd->del_count |
271 | ); | |
315127ff | 272 | storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n", |
62e76326 | 273 | cd->bits_per_entry, |
274 | stats.bit_on_count, stats.bit_count, | |
275 | xpercentInt(stats.bit_on_count, stats.bit_count) | |
276 | ); | |
b644367b | 277 | storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n", |
62e76326 | 278 | stats.bseq_count, |
279 | xdiv(stats.bseq_len_sum, stats.bseq_count) | |
280 | ); | |
8638fc66 | 281 | } |
282 | ||
831e953c AJ |
283 | uint32_t |
284 | CacheDigest::CalcMaskSize(uint64_t cap, uint8_t bpe) | |
304b267e | 285 | { |
831e953c | 286 | uint64_t bitCount = (cap * bpe) + 7; |
61beade2 | 287 | assert(bitCount < INT_MAX); // do not 31-bit overflow later |
831e953c | 288 | return static_cast<uint32_t>(bitCount / 8); |
304b267e | 289 | } |
290 | ||
e5834061 | 291 | static void |
5999b776 | 292 | cacheDigestHashKey(const CacheDigest * cd, const cache_key * key) |
e5834061 | 293 | { |
831e953c | 294 | const uint32_t bit_count = cd->mask_size * 8; |
13c31e72 | 295 | unsigned int tmp_keys[4]; |
296 | /* we must memcpy to ensure alignment */ | |
41d00cd3 | 297 | memcpy(tmp_keys, key, sizeof(tmp_keys)); |
e5834061 | 298 | hashed_keys[0] = htonl(tmp_keys[0]) % bit_count; |
299 | hashed_keys[1] = htonl(tmp_keys[1]) % bit_count; | |
300 | hashed_keys[2] = htonl(tmp_keys[2]) % bit_count; | |
301 | hashed_keys[3] = htonl(tmp_keys[3]) % bit_count; | |
bf8fe701 | 302 | debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key) << " -(" << |
303 | bit_count << ")-> " << hashed_keys[0] << " " << hashed_keys[1] << | |
304 | " " << hashed_keys[2] << " " << hashed_keys[3]); | |
e5834061 | 305 | } |
c68e9c6b | 306 | |
307 | #endif | |
f53969cc | 308 |