src/CacheDigest.cc

   1
   2 /*
   3  * $Id$
   4  *
   5  * DEBUG: section 70    Cache Digest
   6  * AUTHOR: Alex Rousskov
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from
  12  *  the Internet community; see the CONTRIBUTORS file for full
  13  *  details.   Many organizations have provided support for Squid's
  14  *  development; see the SPONSORS file for full details.  Squid is
  15  *  Copyrighted (C) 2001 by the Regents of the University of
  16  *  California; see the COPYRIGHT file for full details.  Squid
  17  *  incorporates software developed and/or copyrighted by other
  18  *  sources; see the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37 #include "md5.h"
  38 #include "protos.h"
  39 #include "StatCounters.h"
  40 #include "Store.h"
  41
  42 #if USE_CACHE_DIGESTS
  43
  44 /* local types */
  45
  46 typedef struct {
  47     int bit_count;              /* total number of bits */
  48     int bit_on_count;           /* #bits turned on */
  49     int bseq_len_sum;           /* sum of all bit seq length */
  50     int bseq_count;             /* number of bit seqs */
  51 } CacheDigestStats;
  52
  53 /* local functions */
  54 static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key);
  55
  56 /* static array used by cacheDigestHashKey for optimization purposes */
  57 static uint32_t hashed_keys[4];
  58
  59 static void
  60 cacheDigestInit(CacheDigest * cd, int capacity, int bpe)
  61 {
  62     const size_t mask_size = cacheDigestCalcMaskSize(capacity, bpe);
  63     assert(cd);
  64     assert(capacity > 0 && bpe > 0);
  65     assert(mask_size > 0);
  66     cd->capacity = capacity;
  67     cd->bits_per_entry = bpe;
  68     cd->mask_size = mask_size;
  69     cd->mask = (char *)xcalloc(cd->mask_size, 1);
  70     debugs(70, 2, "cacheDigestInit: capacity: " << cd->capacity << " entries, bpe: " << cd->bits_per_entry << "; size: "
  71            << cd->mask_size << " bytes");
  72 }
  73
  74 CacheDigest *
  75 cacheDigestCreate(int capacity, int bpe)
  76 {
  77     CacheDigest *cd = (CacheDigest *)memAllocate(MEM_CACHE_DIGEST);
  78     assert(SQUID_MD5_DIGEST_LENGTH == 16);      /* our hash functions rely on 16 byte keys */
  79     cacheDigestInit(cd, capacity, bpe);
  80     return cd;
  81 }
  82
  83 static void
  84 cacheDigestClean(CacheDigest * cd)
  85 {
  86     assert(cd);
  87     xfree(cd->mask);
  88     cd->mask = NULL;
  89 }
  90
  91 void
  92 cacheDigestDestroy(CacheDigest * cd)
  93 {
  94     assert(cd);
  95     cacheDigestClean(cd);
  96     memFree(cd, MEM_CACHE_DIGEST);
  97 }
  98
  99 CacheDigest *
 100 cacheDigestClone(const CacheDigest * cd)
 101 {
 102     CacheDigest *clone;
 103     assert(cd);
 104     clone = cacheDigestCreate(cd->capacity, cd->bits_per_entry);
 105     clone->count = cd->count;
 106     clone->del_count = cd->del_count;
 107     assert(cd->mask_size == clone->mask_size);
 108     memcpy(clone->mask, cd->mask, cd->mask_size);
 109     return clone;
 110 }
 111
 112 void
 113 cacheDigestClear(CacheDigest * cd)
 114 {
 115     assert(cd);
 116     cd->count = cd->del_count = 0;
 117     memset(cd->mask, 0, cd->mask_size);
 118 }
 119
 120 /* changes mask size, resets bits to 0, preserves "cd" pointer */
 121 void
 122 cacheDigestChangeCap(CacheDigest * cd, int new_cap)
 123 {
 124     assert(cd);
 125     cacheDigestClean(cd);
 126     cacheDigestInit(cd, new_cap, cd->bits_per_entry);
 127 }
 128
 129 /* returns true if the key belongs to the digest */
 130 int
 131 cacheDigestTest(const CacheDigest * cd, const cache_key * key)
 132 {
 133     assert(cd && key);
 134     /* hash */
 135     cacheDigestHashKey(cd, key);
 136     /* test corresponding bits */
 137     return
 138         CBIT_TEST(cd->mask, hashed_keys[0]) &&
 139         CBIT_TEST(cd->mask, hashed_keys[1]) &&
 140         CBIT_TEST(cd->mask, hashed_keys[2]) &&
 141         CBIT_TEST(cd->mask, hashed_keys[3]);
 142 }
 143
 144 void
 145 cacheDigestAdd(CacheDigest * cd, const cache_key * key)
 146 {
 147     assert(cd && key);
 148     /* hash */
 149     cacheDigestHashKey(cd, key);
 150     /* turn on corresponding bits */
 151 #if CD_FAST_ADD
 152
 153     CBIT_SET(cd->mask, hashed_keys[0]);
 154     CBIT_SET(cd->mask, hashed_keys[1]);
 155     CBIT_SET(cd->mask, hashed_keys[2]);
 156     CBIT_SET(cd->mask, hashed_keys[3]);
 157 #else
 158
 159     {
 160         int on_xition_cnt = 0;
 161
 162         if (!CBIT_TEST(cd->mask, hashed_keys[0])) {
 163             CBIT_SET(cd->mask, hashed_keys[0]);
 164             ++on_xition_cnt;
 165         }
 166
 167         if (!CBIT_TEST(cd->mask, hashed_keys[1])) {
 168             CBIT_SET(cd->mask, hashed_keys[1]);
 169             ++on_xition_cnt;
 170         }
 171
 172         if (!CBIT_TEST(cd->mask, hashed_keys[2])) {
 173             CBIT_SET(cd->mask, hashed_keys[2]);
 174             ++on_xition_cnt;
 175         }
 176
 177         if (!CBIT_TEST(cd->mask, hashed_keys[3])) {
 178             CBIT_SET(cd->mask, hashed_keys[3]);
 179             ++on_xition_cnt;
 180         }
 181
 182         statCounter.cd.on_xition_count.count(on_xition_cnt);
 183     }
 184 #endif
 185     ++ cd->count;
 186 }
 187
 188 void
 189 cacheDigestDel(CacheDigest * cd, const cache_key * key)
 190 {
 191     assert(cd && key);
 192     ++ cd->del_count;
 193     /* we do not support deletions from the digest */
 194 }
 195
 196 /* returns mask utilization parameters */
 197 static void
 198 cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats)
 199 {
 200     int on_count = 0;
 201     int pos = cd->mask_size * 8;
 202     int seq_len_sum = 0;
 203     int seq_count = 0;
 204     int cur_seq_len = 0;
 205     int cur_seq_type = 1;
 206     assert(stats);
 207     memset(stats, 0, sizeof(*stats));
 208
 209     while (pos-- > 0) {
 210         const int is_on = 0 != CBIT_TEST(cd->mask, pos);
 211
 212         if (is_on)
 213             ++on_count;
 214
 215         if (is_on != cur_seq_type || !pos) {
 216             seq_len_sum += cur_seq_len;
 217             ++seq_count;
 218             cur_seq_type = is_on;
 219             cur_seq_len = 0;
 220         }
 221
 222         ++cur_seq_len;
 223     }
 224
 225     stats->bit_count = cd->mask_size * 8;
 226     stats->bit_on_count = on_count;
 227     stats->bseq_len_sum = seq_len_sum;
 228     stats->bseq_count = seq_count;
 229 }
 230
 231 int
 232 cacheDigestBitUtil(const CacheDigest * cd)
 233 {
 234     CacheDigestStats stats;
 235     assert(cd);
 236     cacheDigestStats(cd, &stats);
 237     return xpercentInt(stats.bit_on_count, stats.bit_count);
 238 }
 239
 240 void
 241 cacheDigestGuessStatsUpdate(CacheDigestGuessStats * stats, int real_hit, int guess_hit)
 242 {
 243     assert(stats);
 244
 245     if (real_hit) {
 246         if (guess_hit)
 247             ++stats->trueHits;
 248         else
 249             ++stats->falseMisses;
 250     } else {
 251         if (guess_hit)
 252             ++stats->falseHits;
 253         else
 254             ++stats->trueMisses;
 255     }
 256 }
 257
 258 void
 259 cacheDigestGuessStatsReport(const CacheDigestGuessStats * stats, StoreEntry * sentry, const char *label)
 260 {
 261     const int true_count = stats->trueHits + stats->trueMisses;
 262     const int false_count = stats->falseHits + stats->falseMisses;
 263     const int hit_count = stats->trueHits + stats->falseHits;
 264     const int miss_count = stats->trueMisses + stats->falseMisses;
 265     const int tot_count = true_count + false_count;
 266
 267     assert(label);
 268     assert(tot_count == hit_count + miss_count);        /* paranoid */
 269
 270     if (!tot_count) {
 271         storeAppendPrintf(sentry, "no guess stats for %s available\n", label);
 272         return;
 273     }
 274
 275     storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label);
 276     storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n");
 277     storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n");
 278     storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
 279                       stats->trueHits, xpercent(stats->trueHits, tot_count),
 280                       stats->trueMisses, xpercent(stats->trueMisses, tot_count),
 281                       true_count, xpercent(true_count, tot_count));
 282     storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
 283                       stats->falseHits, xpercent(stats->falseHits, tot_count),
 284                       stats->falseMisses, xpercent(stats->falseMisses, tot_count),
 285                       false_count, xpercent(false_count, tot_count));
 286     storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
 287                       hit_count, xpercent(hit_count, tot_count),
 288                       miss_count, xpercent(miss_count, tot_count),
 289                       tot_count, xpercent(tot_count, tot_count));
 290     storeAppendPrintf(sentry, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n",
 291                       stats->closeHits, xpercentInt(stats->closeHits, stats->falseHits));
 292 }
 293
 294 void
 295 cacheDigestReport(CacheDigest * cd, const char *label, StoreEntry * e)
 296 {
 297     CacheDigestStats stats;
 298     assert(cd && e);
 299     cacheDigestStats(cd, &stats);
 300     storeAppendPrintf(e, "%s digest: size: %d bytes\n",
 301                       label ? label : "", stats.bit_count / 8
 302                      );
 303     storeAppendPrintf(e, "\t entries: count: %d capacity: %d util: %d%%\n",
 304                       cd->count,
 305                       cd->capacity,
 306                       xpercentInt(cd->count, cd->capacity)
 307                      );
 308     storeAppendPrintf(e, "\t deletion attempts: %d\n",
 309                       cd->del_count
 310                      );
 311     storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
 312                       cd->bits_per_entry,
 313                       stats.bit_on_count, stats.bit_count,
 314                       xpercentInt(stats.bit_on_count, stats.bit_count)
 315                      );
 316     storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
 317                       stats.bseq_count,
 318                       xdiv(stats.bseq_len_sum, stats.bseq_count)
 319                      );
 320 }
 321
 322 size_t
 323 cacheDigestCalcMaskSize(int cap, int bpe)
 324 {
 325     return (size_t) (cap * bpe + 7) / 8;
 326 }
 327
 328 static void
 329 cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
 330 {
 331     const unsigned int bit_count = cd->mask_size * 8;
 332     unsigned int tmp_keys[4];
 333     /* we must memcpy to ensure alignment */
 334     memcpy(tmp_keys, key, sizeof(tmp_keys));
 335     hashed_keys[0] = htonl(tmp_keys[0]) % bit_count;
 336     hashed_keys[1] = htonl(tmp_keys[1]) % bit_count;
 337     hashed_keys[2] = htonl(tmp_keys[2]) % bit_count;
 338     hashed_keys[3] = htonl(tmp_keys[3]) % bit_count;
 339     debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key) << " -(" <<
 340            bit_count << ")-> " << hashed_keys[0] << " " << hashed_keys[1] <<
 341            " " << hashed_keys[2] << " " << hashed_keys[3]);
 342 }
 343
 344 #endif