CacheDigest.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2021 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 
24 typedef 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 */
32 static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key);
33 
34 /* static array used by cacheDigestHashKey for optimization purposes */
35 static uint32_t hashed_keys[4];
36 
37 void
38 CacheDigest::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 
50 CacheDigest::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;
73  assert(mask_size == cl->mask_size);
74  memcpy(cl->mask, mask, mask_size);
75  return cl;
76 }
77 
78 void
80 {
81  count = del_count = 0;
82  memset(mask, 0, mask_size);
83 }
84 
85 void
86 CacheDigest::updateCapacity(uint64_t newCapacity)
87 {
88  safe_free(mask);
89  init(newCapacity); // will re-init mask and mask_size
90 }
91 
92 bool
93 CacheDigest::contains(const cache_key * key) const
94 {
95  assert(key);
96  /* hash */
97  cacheDigestHashKey(this, key);
98  /* test corresponding bits */
99  return
100  CBIT_TEST(mask, hashed_keys[0]) &&
101  CBIT_TEST(mask, hashed_keys[1]) &&
102  CBIT_TEST(mask, hashed_keys[2]) &&
104 }
105 
106 void
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 
139 void
141 {
142  assert(key);
143  ++del_count;
144  /* we do not support deletions from the digest */
145 }
146 
147 /* returns mask utilization parameters */
148 static 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 
182 double
184 {
186  cacheDigestStats(this, &stats);
187  return xpercent(stats.bit_on_count, stats.bit_count);
188 }
189 
190 void
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 
208 void
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 
244 void
246 {
248  assert(cd && e);
249  cacheDigestStats(cd, &stats);
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 
272 uint32_t
273 CacheDigest::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 
280 static void
281 cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
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 
SQUIDCEXTERN double xpercent(double part, double whole)
Definition: util.c:54
double usedMaskPercent() const
percentage of mask bits which are used
Definition: CacheDigest.cc:183
class Ping::pingStats_ stats
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:72
unsigned char cache_key
Store key.
Definition: forward.h:29
uint64_t capacity
Definition: CacheDigest.h:57
bool isEmpty() const
Definition: SBuf.h:424
void clear()
reset the digest mask and counters
Definition: CacheDigest.cc:79
int8_t bits_per_entry
Definition: CacheDigest.h:60
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:872
Definition: SBuf.h:87
#define PRIu64
Definition: types.h:120
void updateCapacity(uint64_t newCapacity)
changes mask size to fit newCapacity, resets bits to 0
Definition: CacheDigest.cc:86
void cacheDigestGuessStatsReport(const CacheDigestGuessStats *stats, StoreEntry *sentry, const SBuf &label)
Definition: CacheDigest.cc:209
StatHist on_xition_count
Definition: StatCounters.h:111
CacheDigest * clone() const
produce a new identical copy of the digest object
Definition: CacheDigest.cc:68
void remove(const cache_key *key)
Definition: CacheDigest.cc:140
static uint32_t hashed_keys[4]
Definition: CacheDigest.cc:35
#define SQUID_MD5_DIGEST_LENGTH
Definition: md5.h:66
void cacheDigestReport(CacheDigest *cd, const SBuf &label, StoreEntry *e)
Definition: CacheDigest.cc:245
#define SQUIDSBUFPRINT(s)
Definition: SBuf.h:32
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
#define INT_MAX
Definition: types.h:76
#define safe_free(x)
Definition: xalloc.h:73
void count(double val)
Definition: StatHist.cc:57
#define assert(EX)
Definition: assert.h:19
static uint32_t CalcMaskSize(uint64_t cap, uint8_t bpe)
Definition: CacheDigest.cc:273
#define CBIT_TEST(mask, bit)
Definition: defines.h:76
char * mask
Definition: CacheDigest.h:58
void cacheDigestGuessStatsUpdate(CacheDigestGuessStats *stats, int real_hit, int guess_hit)
Definition: CacheDigest.cc:191
uint64_t del_count
Definition: CacheDigest.h:56
#define xfree
static void cacheDigestHashKey(const CacheDigest *cd, const cache_key *key)
Definition: CacheDigest.cc:281
CacheDigest(uint64_t capacity, uint8_t bpe)
Definition: CacheDigest.cc:50
void add(const cache_key *key)
Definition: CacheDigest.cc:107
bool contains(const cache_key *key) const
Definition: CacheDigest.cc:93
const char * storeKeyText(const cache_key *key)
void init(uint64_t newCapacity)
Definition: CacheDigest.cc:38
SQUIDCEXTERN double xdiv(double nom, double denom)
Definition: util.c:72
#define CBIT_SET(mask, bit)
Definition: defines.h:74
uint32_t mask_size
Definition: CacheDigest.h:59
static void cacheDigestStats(const CacheDigest *cd, CacheDigestStats *stats)
Definition: CacheDigest.cc:149
uint64_t count
Definition: CacheDigest.h:55
SQUIDCEXTERN int xpercentInt(double part, double whole)
Definition: util.c:60
#define SQUIDSBUFPH
Definition: SBuf.h:31
struct StatCounters::@134 cd
StatCounters statCounter
Definition: StatCounters.cc:12

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors