]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/CacheDigest.cc
2 * Copyright (C) 1996-2021 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 */
113 int on_xition_cnt
= 0;
115 if (!CBIT_TEST(mask
, hashed_keys
[0])) {
116 CBIT_SET(mask
, hashed_keys
[0]);
120 if (!CBIT_TEST(mask
, hashed_keys
[1])) {
121 CBIT_SET(mask
, hashed_keys
[1]);
125 if (!CBIT_TEST(mask
, hashed_keys
[2])) {
126 CBIT_SET(mask
, hashed_keys
[2]);
130 if (!CBIT_TEST(mask
, hashed_keys
[3])) {
131 CBIT_SET(mask
, hashed_keys
[3]);
135 statCounter
.cd
.on_xition_count
.count(on_xition_cnt
);
140 CacheDigest::remove(const cache_key
* key
)
144 /* we do not support deletions from the digest */
147 /* returns mask utilization parameters */
149 cacheDigestStats(const CacheDigest
* cd
, CacheDigestStats
* stats
)
152 int pos
= cd
->mask_size
* 8;
156 int cur_seq_type
= 1;
158 memset(stats
, 0, sizeof(*stats
));
161 const int is_on
= 0 != CBIT_TEST(cd
->mask
, pos
);
166 if (is_on
!= cur_seq_type
|| !pos
) {
167 seq_len_sum
+= cur_seq_len
;
169 cur_seq_type
= is_on
;
176 stats
->bit_count
= cd
->mask_size
* 8;
177 stats
->bit_on_count
= on_count
;
178 stats
->bseq_len_sum
= seq_len_sum
;
179 stats
->bseq_count
= seq_count
;
183 CacheDigest::usedMaskPercent() const
185 CacheDigestStats stats
;
186 cacheDigestStats(this, &stats
);
187 return xpercent(stats
.bit_on_count
, stats
.bit_count
);
191 cacheDigestGuessStatsUpdate(CacheDigestGuessStats
* stats
, int real_hit
, int guess_hit
)
199 ++stats
->falseMisses
;
209 cacheDigestGuessStatsReport(const CacheDigestGuessStats
* stats
, StoreEntry
* sentry
, const SBuf
&label
)
211 const int true_count
= stats
->trueHits
+ stats
->trueMisses
;
212 const int false_count
= stats
->falseHits
+ stats
->falseMisses
;
213 const int hit_count
= stats
->trueHits
+ stats
->falseHits
;
214 const int miss_count
= stats
->trueMisses
+ stats
->falseMisses
;
215 const int tot_count
= true_count
+ false_count
;
217 assert(!label
.isEmpty());
218 assert(tot_count
== hit_count
+ miss_count
); /* paranoid */
221 storeAppendPrintf(sentry
, "no guess stats for " SQUIDSBUFPH
" available\n", SQUIDSBUFPRINT(label
));
225 storeAppendPrintf(sentry
, "Digest guesses stats for " SQUIDSBUFPH
":\n", SQUIDSBUFPRINT(label
));
226 storeAppendPrintf(sentry
, "guess\t hit\t\t miss\t\t total\t\t\n");
227 storeAppendPrintf(sentry
, " \t #\t %%\t #\t %%\t #\t %%\t\n");
228 storeAppendPrintf(sentry
, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
229 stats
->trueHits
, xpercent(stats
->trueHits
, tot_count
),
230 stats
->trueMisses
, xpercent(stats
->trueMisses
, tot_count
),
231 true_count
, xpercent(true_count
, tot_count
));
232 storeAppendPrintf(sentry
, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
233 stats
->falseHits
, xpercent(stats
->falseHits
, tot_count
),
234 stats
->falseMisses
, xpercent(stats
->falseMisses
, tot_count
),
235 false_count
, xpercent(false_count
, tot_count
));
236 storeAppendPrintf(sentry
, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
237 hit_count
, xpercent(hit_count
, tot_count
),
238 miss_count
, xpercent(miss_count
, tot_count
),
239 tot_count
, xpercent(tot_count
, tot_count
));
240 storeAppendPrintf(sentry
, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n",
241 stats
->closeHits
, xpercentInt(stats
->closeHits
, stats
->falseHits
));
245 cacheDigestReport(CacheDigest
* cd
, const SBuf
&label
, StoreEntry
* e
)
247 CacheDigestStats stats
;
249 cacheDigestStats(cd
, &stats
);
250 storeAppendPrintf(e
, SQUIDSBUFPH
" digest: size: %d bytes\n",
251 SQUIDSBUFPRINT(label
), stats
.bit_count
/ 8
253 storeAppendPrintf(e
, "\t entries: count: %" PRIu64
" capacity: %" PRIu64
" util: %d%%\n",
256 xpercentInt(cd
->count
, cd
->capacity
)
258 storeAppendPrintf(e
, "\t deletion attempts: %" PRIu64
"\n",
261 storeAppendPrintf(e
, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
263 stats
.bit_on_count
, stats
.bit_count
,
264 xpercentInt(stats
.bit_on_count
, stats
.bit_count
)
266 storeAppendPrintf(e
, "\t bit-seq: count: %d avg.len: %.2f\n",
268 xdiv(stats
.bseq_len_sum
, stats
.bseq_count
)
273 CacheDigest::CalcMaskSize(uint64_t cap
, uint8_t bpe
)
275 uint64_t bitCount
= (cap
* bpe
) + 7;
276 assert(bitCount
< INT_MAX
); // do not 31-bit overflow later
277 return static_cast<uint32_t>(bitCount
/ 8);
281 cacheDigestHashKey(const CacheDigest
* cd
, const cache_key
* key
)
283 const uint32_t bit_count
= cd
->mask_size
* 8;
284 unsigned int tmp_keys
[4];
285 /* we must memcpy to ensure alignment */
286 memcpy(tmp_keys
, key
, sizeof(tmp_keys
));
287 hashed_keys
[0] = htonl(tmp_keys
[0]) % bit_count
;
288 hashed_keys
[1] = htonl(tmp_keys
[1]) % bit_count
;
289 hashed_keys
[2] = htonl(tmp_keys
[2]) % bit_count
;
290 hashed_keys
[3] = htonl(tmp_keys
[3]) % bit_count
;
291 debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key
) << " -(" <<
292 bit_count
<< ")-> " << hashed_keys
[0] << " " << hashed_keys
[1] <<
293 " " << hashed_keys
[2] << " " << hashed_keys
[3]);