src/CacheDigest.cc

   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 */
  29 } CacheDigestStats;
  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
  62 CacheDigest::~CacheDigest()
  63 {
  64     xfree(mask);
  65 }
  66
  67 CacheDigest *
  68 CacheDigest::clone() const
  69 {
  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;
  76 }
  77
  78 void
  79 CacheDigest::clear()
  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]) &&
 103         CBIT_TEST(mask, hashed_keys[3]);
 104 }
 105
 106 void
 107 CacheDigest::add(const cache_key * key)
 108 {
 109     assert(key);
 110     /* hash */
 111     cacheDigestHashKey(this, key);
 112     /* turn on corresponding bits */
 113 #if CD_FAST_ADD
 114
 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]);
 119 #else
 120
 121     {
 122         int on_xition_cnt = 0;
 123
 124         if (!CBIT_TEST(mask, hashed_keys[0])) {
 125             CBIT_SET(mask, hashed_keys[0]);
 126             ++on_xition_cnt;
 127         }
 128
 129         if (!CBIT_TEST(mask, hashed_keys[1])) {
 130             CBIT_SET(mask, hashed_keys[1]);
 131             ++on_xition_cnt;
 132         }
 133
 134         if (!CBIT_TEST(mask, hashed_keys[2])) {
 135             CBIT_SET(mask, hashed_keys[2]);
 136             ++on_xition_cnt;
 137         }
 138
 139         if (!CBIT_TEST(mask, hashed_keys[3])) {
 140             CBIT_SET(mask, hashed_keys[3]);
 141             ++on_xition_cnt;
 142         }
 143
 144         statCounter.cd.on_xition_count.count(on_xition_cnt);
 145     }
 146 #endif
 147     ++count;
 148 }
 149
 150 void
 151 CacheDigest::remove(const cache_key * key)
 152 {
 153     assert(key);
 154     ++del_count;
 155     /* we do not support deletions from the digest */
 156 }
 157
 158 /* returns mask utilization parameters */
 159 static void
 160 cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats)
 161 {
 162     int on_count = 0;
 163     int pos = cd->mask_size * 8;
 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));
 170
 171     while (pos-- > 0) {
 172         const int is_on = 0 != CBIT_TEST(cd->mask, pos);
 173
 174         if (is_on)
 175             ++on_count;
 176
 177         if (is_on != cur_seq_type || !pos) {
 178             seq_len_sum += cur_seq_len;
 179             ++seq_count;
 180             cur_seq_type = is_on;
 181             cur_seq_len = 0;
 182         }
 183
 184         ++cur_seq_len;
 185     }
 186
 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;
 191 }
 192
 193 double
 194 CacheDigest::usedMaskPercent() const
 195 {
 196     CacheDigestStats stats;
 197     cacheDigestStats(this, &stats);
 198     return xpercent(stats.bit_on_count, stats.bit_count);
 199 }
 200
 201 void
 202 cacheDigestGuessStatsUpdate(CacheDigestGuessStats * stats, int real_hit, int guess_hit)
 203 {
 204     assert(stats);
 205
 206     if (real_hit) {
 207         if (guess_hit)
 208             ++stats->trueHits;
 209         else
 210             ++stats->falseMisses;
 211     } else {
 212         if (guess_hit)
 213             ++stats->falseHits;
 214         else
 215             ++stats->trueMisses;
 216     }
 217 }
 218
 219 void
 220 cacheDigestGuessStatsReport(const CacheDigestGuessStats * stats, StoreEntry * sentry, const SBuf &label)
 221 {
 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;
 227
 228     assert(!label.isEmpty());
 229     assert(tot_count == hit_count + miss_count);    /* paranoid */
 230
 231     if (!tot_count) {
 232         storeAppendPrintf(sentry, "no guess stats for " SQUIDSBUFPH " available\n", SQUIDSBUFPRINT(label));
 233         return;
 234     }
 235
 236     storeAppendPrintf(sentry, "Digest guesses stats for " SQUIDSBUFPH ":\n", SQUIDSBUFPRINT(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));
 253 }
 254
 255 void
 256 cacheDigestReport(CacheDigest * cd, const SBuf &label, StoreEntry * e)
 257 {
 258     CacheDigestStats stats;
 259     assert(cd && e);
 260     cacheDigestStats(cd, &stats);
 261     storeAppendPrintf(e, SQUIDSBUFPH " digest: size: %d bytes\n",
 262                       SQUIDSBUFPRINT(label), stats.bit_count / 8
 263                      );
 264     storeAppendPrintf(e, "\t entries: count: %" PRIu64 " capacity: %" PRIu64 " util: %d%%\n",
 265                       cd->count,
 266                       cd->capacity,
 267                       xpercentInt(cd->count, cd->capacity)
 268                      );
 269     storeAppendPrintf(e, "\t deletion attempts: %" PRIu64 "\n",
 270                       cd->del_count
 271                      );
 272     storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
 273                       cd->bits_per_entry,
 274                       stats.bit_on_count, stats.bit_count,
 275                       xpercentInt(stats.bit_on_count, stats.bit_count)
 276                      );
 277     storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
 278                       stats.bseq_count,
 279                       xdiv(stats.bseq_len_sum, stats.bseq_count)
 280                      );
 281 }
 282
 283 uint32_t
 284 CacheDigest::CalcMaskSize(uint64_t cap, uint8_t bpe)
 285 {
 286     uint64_t bitCount = (cap * bpe) + 7;
 287     assert(bitCount < INT_MAX); // do not 31-bit overflow later
 288     return static_cast<uint32_t>(bitCount / 8);
 289 }
 290
 291 static void
 292 cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
 293 {
 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]);
 305 }
 306
 307 #endif
 308