]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/CacheDigest.cc
2 * Copyright (C) 1996-2017 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 70 Cache Digest */
13 #include "StatCounters.h"
15 #include "store_key_md5.h"
19 #include "CacheDigest.h"
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 */
32 static void cacheDigestHashKey(const CacheDigest
* cd
, const cache_key
* key
);
34 /* static array used by cacheDigestHashKey for optimization purposes */
35 static uint32_t hashed_keys
[4];
38 CacheDigest::init(uint64_t newCapacity
)
40 const auto newMaskSz
= CacheDigest::CalcMaskSize(newCapacity
, bits_per_entry
);
41 assert(newCapacity
> 0 && bits_per_entry
> 0);
42 assert(newMaskSz
!= 0);
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");
50 CacheDigest::CacheDigest(uint64_t aCapacity
, uint8_t bpe
) :
58 assert(SQUID_MD5_DIGEST_LENGTH
== 16); /* our hash functions rely on 16 byte keys */
59 updateCapacity(aCapacity
);
62 CacheDigest::~CacheDigest()
68 CacheDigest::clone() const
70 CacheDigest
*cl
= new CacheDigest(capacity
, bits_per_entry
);
72 cl
->del_count
= del_count
;
73 assert(mask_size
== cl
->mask_size
);
74 memcpy(cl
->mask
, mask
, mask_size
);
81 count
= del_count
= 0;
82 memset(mask
, 0, mask_size
);
86 CacheDigest::updateCapacity(uint64_t newCapacity
)
89 init(newCapacity
); // will re-init mask and mask_size
93 CacheDigest::contains(const cache_key
* key
) const
97 cacheDigestHashKey(this, key
);
98 /* test corresponding bits */
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]);
107 CacheDigest::add(const cache_key
* key
)
111 cacheDigestHashKey(this, key
);
112 /* turn on corresponding bits */
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]);
122 int on_xition_cnt
= 0;
124 if (!CBIT_TEST(mask
, hashed_keys
[0])) {
125 CBIT_SET(mask
, hashed_keys
[0]);
129 if (!CBIT_TEST(mask
, hashed_keys
[1])) {
130 CBIT_SET(mask
, hashed_keys
[1]);
134 if (!CBIT_TEST(mask
, hashed_keys
[2])) {
135 CBIT_SET(mask
, hashed_keys
[2]);
139 if (!CBIT_TEST(mask
, hashed_keys
[3])) {
140 CBIT_SET(mask
, hashed_keys
[3]);
144 statCounter
.cd
.on_xition_count
.count(on_xition_cnt
);
151 CacheDigest::remove(const cache_key
* key
)
155 /* we do not support deletions from the digest */
158 /* returns mask utilization parameters */
160 cacheDigestStats(const CacheDigest
* cd
, CacheDigestStats
* stats
)
163 int pos
= cd
->mask_size
* 8;
167 int cur_seq_type
= 1;
169 memset(stats
, 0, sizeof(*stats
));
172 const int is_on
= 0 != CBIT_TEST(cd
->mask
, pos
);
177 if (is_on
!= cur_seq_type
|| !pos
) {
178 seq_len_sum
+= cur_seq_len
;
180 cur_seq_type
= is_on
;
187 stats
->bit_count
= cd
->mask_size
* 8;
188 stats
->bit_on_count
= on_count
;
189 stats
->bseq_len_sum
= seq_len_sum
;
190 stats
->bseq_count
= seq_count
;
194 CacheDigest::usedMaskPercent() const
196 CacheDigestStats stats
;
197 cacheDigestStats(this, &stats
);
198 return xpercent(stats
.bit_on_count
, stats
.bit_count
);
202 cacheDigestGuessStatsUpdate(CacheDigestGuessStats
* stats
, int real_hit
, int guess_hit
)
210 ++stats
->falseMisses
;
220 cacheDigestGuessStatsReport(const CacheDigestGuessStats
* stats
, StoreEntry
* sentry
, const char *label
)
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
;
226 const int tot_count
= true_count
+ false_count
;
229 assert(tot_count
== hit_count
+ miss_count
); /* paranoid */
232 storeAppendPrintf(sentry
, "no guess stats for %s available\n", label
);
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");
239 storeAppendPrintf(sentry
, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
240 stats
->trueHits
, xpercent(stats
->trueHits
, tot_count
),
241 stats
->trueMisses
, xpercent(stats
->trueMisses
, tot_count
),
242 true_count
, xpercent(true_count
, tot_count
));
243 storeAppendPrintf(sentry
, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
244 stats
->falseHits
, xpercent(stats
->falseHits
, tot_count
),
245 stats
->falseMisses
, xpercent(stats
->falseMisses
, tot_count
),
246 false_count
, xpercent(false_count
, tot_count
));
247 storeAppendPrintf(sentry
, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
248 hit_count
, xpercent(hit_count
, tot_count
),
249 miss_count
, xpercent(miss_count
, tot_count
),
250 tot_count
, xpercent(tot_count
, tot_count
));
251 storeAppendPrintf(sentry
, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n",
252 stats
->closeHits
, xpercentInt(stats
->closeHits
, stats
->falseHits
));
256 cacheDigestReport(CacheDigest
* cd
, const char *label
, StoreEntry
* e
)
258 CacheDigestStats stats
;
260 cacheDigestStats(cd
, &stats
);
261 storeAppendPrintf(e
, "%s digest: size: %d bytes\n",
262 label
? label
: "", stats
.bit_count
/ 8
264 storeAppendPrintf(e
, "\t entries: count: %" PRIu64
" capacity: %" PRIu64
" util: %d%%\n",
267 xpercentInt(cd
->count
, cd
->capacity
)
269 storeAppendPrintf(e
, "\t deletion attempts: %" PRIu64
"\n",
272 storeAppendPrintf(e
, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
274 stats
.bit_on_count
, stats
.bit_count
,
275 xpercentInt(stats
.bit_on_count
, stats
.bit_count
)
277 storeAppendPrintf(e
, "\t bit-seq: count: %d avg.len: %.2f\n",
279 xdiv(stats
.bseq_len_sum
, stats
.bseq_count
)
284 CacheDigest::CalcMaskSize(uint64_t cap
, uint8_t bpe
)
286 uint64_t bitCount
= (cap
* bpe
) + 7;
287 assert(bitCount
< INT_MAX
); // dont 31-bit overflow later
288 return static_cast<uint32_t>(bitCount
/ 8);
292 cacheDigestHashKey(const CacheDigest
* cd
, const cache_key
* key
)
294 const uint32_t bit_count
= cd
->mask_size
* 8;
295 unsigned int tmp_keys
[4];
296 /* we must memcpy to ensure alignment */
297 memcpy(tmp_keys
, key
, sizeof(tmp_keys
));
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
;
302 debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key
) << " -(" <<
303 bit_count
<< ")-> " << hashed_keys
[0] << " " << hashed_keys
[1] <<
304 " " << hashed_keys
[2] << " " << hashed_keys
[3]);