CacheDigest.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
3 *
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.
7 */
8
9/* DEBUG: section 70 Cache Digest */
10
11#include "squid.h"
12#include "md5.h"
13#include "StatCounters.h"
14#include "Store.h"
15#include "store_key_md5.h"
16
17#if USE_CACHE_DIGESTS
18
19#include "CacheDigest.h"
20#include "util.h"
21
22/* local types */
23
24typedef struct {
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 */
30
31/* local functions */
32static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key);
33
34/* static array used by cacheDigestHashKey for optimization purposes */
35static uint32_t hashed_keys[4];
36
37void
38CacheDigest::init(uint64_t newCapacity)
39{
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");
48}
49
50CacheDigest::CacheDigest(uint64_t aCapacity, uint8_t bpe) :
51 count(0),
52 del_count(0),
53 capacity(0),
54 mask(nullptr),
55 mask_size(0),
56 bits_per_entry(bpe)
57{
58 assert(SQUID_MD5_DIGEST_LENGTH == 16); /* our hash functions rely on 16 byte keys */
59 updateCapacity(aCapacity);
60}
61
63{
64 xfree(mask);
65}
66
69{
71 cl->count = count;
72 cl->del_count = del_count;
74 memcpy(cl->mask, mask, mask_size);
75 return cl;
76}
77
78void
80{
81 count = del_count = 0;
82 memset(mask, 0, mask_size);
83}
84
85void
86CacheDigest::updateCapacity(uint64_t newCapacity)
87{
89 init(newCapacity); // will re-init mask and mask_size
90}
91
92bool
94{
95 assert(key);
96 /* hash */
97 cacheDigestHashKey(this, key);
98 /* test corresponding bits */
99 return
104}
105
106void
108{
109 assert(key);
110 /* hash */
111 cacheDigestHashKey(this, key);
112 /* turn on corresponding bits */
113 int on_xition_cnt = 0;
114
115 if (!CBIT_TEST(mask, hashed_keys[0])) {
117 ++on_xition_cnt;
118 }
119
120 if (!CBIT_TEST(mask, hashed_keys[1])) {
122 ++on_xition_cnt;
123 }
124
125 if (!CBIT_TEST(mask, hashed_keys[2])) {
127 ++on_xition_cnt;
128 }
129
130 if (!CBIT_TEST(mask, hashed_keys[3])) {
132 ++on_xition_cnt;
133 }
134
135 statCounter.cd.on_xition_count.count(on_xition_cnt);
136 ++count;
137}
138
139void
141{
142 assert(key);
143 ++del_count;
144 /* we do not support deletions from the digest */
145}
146
147/* returns mask utilization parameters */
148static void
150{
151 int on_count = 0;
152 int pos = cd->mask_size * 8;
153 int seq_len_sum = 0;
154 int seq_count = 0;
155 int cur_seq_len = 0;
156 int cur_seq_type = 1;
157 assert(stats);
158 memset(stats, 0, sizeof(*stats));
159
160 while (pos-- > 0) {
161 const int is_on = 0 != CBIT_TEST(cd->mask, pos);
162
163 if (is_on)
164 ++on_count;
165
166 if (is_on != cur_seq_type || !pos) {
167 seq_len_sum += cur_seq_len;
168 ++seq_count;
169 cur_seq_type = is_on;
170 cur_seq_len = 0;
171 }
172
173 ++cur_seq_len;
174 }
175
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;
180}
181
182double
184{
186 cacheDigestStats(this, &stats);
187 return xpercent(stats.bit_on_count, stats.bit_count);
188}
189
190void
192{
193 assert(stats);
194
195 if (real_hit) {
196 if (guess_hit)
197 ++stats->trueHits;
198 else
199 ++stats->falseMisses;
200 } else {
201 if (guess_hit)
202 ++stats->falseHits;
203 else
204 ++stats->trueMisses;
205 }
206}
207
208void
210{
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;
216
217 assert(!label.isEmpty());
218 assert(tot_count == hit_count + miss_count); /* paranoid */
219
220 if (!tot_count) {
221 storeAppendPrintf(sentry, "no guess stats for " SQUIDSBUFPH " available\n", SQUIDSBUFPRINT(label));
222 return;
223 }
224
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));
242}
243
244void
246{
248 assert(cd && e);
250 storeAppendPrintf(e, SQUIDSBUFPH " digest: size: %d bytes\n",
251 SQUIDSBUFPRINT(label), stats.bit_count / 8
252 );
253 storeAppendPrintf(e, "\t entries: count: %" PRIu64 " capacity: %" PRIu64 " util: %d%%\n",
254 cd->count,
255 cd->capacity,
256 xpercentInt(cd->count, cd->capacity)
257 );
258 storeAppendPrintf(e, "\t deletion attempts: %" PRIu64 "\n",
259 cd->del_count
260 );
261 storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
262 cd->bits_per_entry,
263 stats.bit_on_count, stats.bit_count,
264 xpercentInt(stats.bit_on_count, stats.bit_count)
265 );
266 storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
267 stats.bseq_count,
268 xdiv(stats.bseq_len_sum, stats.bseq_count)
269 );
270}
271
272uint32_t
273CacheDigest::CalcMaskSize(uint64_t cap, uint8_t bpe)
274{
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);
278}
279
280static void
282{
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]);
294}
295
296#endif
297
void cacheDigestGuessStatsReport(const CacheDigestGuessStats *stats, StoreEntry *sentry, const SBuf &label)
Definition: CacheDigest.cc:209
void cacheDigestGuessStatsUpdate(CacheDigestGuessStats *stats, int real_hit, int guess_hit)
Definition: CacheDigest.cc:191
static uint32_t hashed_keys[4]
Definition: CacheDigest.cc:35
static void cacheDigestStats(const CacheDigest *cd, CacheDigestStats *stats)
Definition: CacheDigest.cc:149
void cacheDigestReport(CacheDigest *cd, const SBuf &label, StoreEntry *e)
Definition: CacheDigest.cc:245
static void cacheDigestHashKey(const CacheDigest *cd, const cache_key *key)
Definition: CacheDigest.cc:281
#define SQUIDSBUFPH
Definition: SBuf.h:31
#define SQUIDSBUFPRINT(s)
Definition: SBuf.h:32
StatCounters statCounter
Definition: StatCounters.cc:12
#define assert(EX)
Definition: assert.h:19
void updateCapacity(uint64_t newCapacity)
changes mask size to fit newCapacity, resets bits to 0
Definition: CacheDigest.cc:86
char * mask
Definition: CacheDigest.h:58
double usedMaskPercent() const
percentage of mask bits which are used
Definition: CacheDigest.cc:183
static uint32_t CalcMaskSize(uint64_t cap, uint8_t bpe)
Definition: CacheDigest.cc:273
uint64_t del_count
Definition: CacheDigest.h:56
CacheDigest(uint64_t capacity, uint8_t bpe)
Definition: CacheDigest.cc:50
uint64_t count
Definition: CacheDigest.h:55
uint32_t mask_size
Definition: CacheDigest.h:59
void init(uint64_t newCapacity)
Definition: CacheDigest.cc:38
void add(const cache_key *key)
Definition: CacheDigest.cc:107
CacheDigest * clone() const
produce a new identical copy of the digest object
Definition: CacheDigest.cc:68
uint64_t capacity
Definition: CacheDigest.h:57
int8_t bits_per_entry
Definition: CacheDigest.h:60
bool contains(const cache_key *key) const
Definition: CacheDigest.cc:93
void clear()
reset the digest mask and counters
Definition: CacheDigest.cc:79
void remove(const cache_key *key)
Definition: CacheDigest.cc:140
Definition: SBuf.h:94
bool isEmpty() const
Definition: SBuf.h:431
struct StatCounters::@134 cd
StatHist on_xition_count
Definition: StatCounters.h:111
void count(double val)
Definition: StatHist.cc:55
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:196
#define CBIT_SET(mask, bit)
Definition: defines.h:74
#define CBIT_TEST(mask, bit)
Definition: defines.h:76
#define SQUID_MD5_DIGEST_LENGTH
Definition: md5.h:66
class Ping::pingStats_ stats
#define xfree
unsigned char cache_key
Store key.
Definition: forward.h:29
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:828
const char * storeKeyText(const cache_key *key)
#define INT_MAX
Definition: types.h:76
#define PRIu64
Definition: types.h:120
SQUIDCEXTERN int xpercentInt(double part, double whole)
Definition: util.c:46
SQUIDCEXTERN double xpercent(double part, double whole)
Definition: util.c:40
SQUIDCEXTERN double xdiv(double nom, double denom)
Definition: util.c:53
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
#define safe_free(x)
Definition: xalloc.h:73

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors