Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 58badfca4f
Fetching contributors…

Cannot retrieve contributors at this time

325 lines (298 sloc) 9.678 kb
/*
* $Id: CacheDigest.c,v 1.36.6.1 2008/01/02 15:49:30 hno Exp $
*
* DEBUG: section 70 Cache Digest
* AUTHOR: Alex Rousskov
*
* SQUID Web Proxy Cache http://www.squid-cache.org/
* ----------------------------------------------------------
*
* Squid is the result of efforts by numerous individuals from
* the Internet community; see the CONTRIBUTORS file for full
* details. Many organizations have provided support for Squid's
* development; see the SPONSORS file for full details. Squid is
* Copyrighted (C) 2001 by the Regents of the University of
* California; see the COPYRIGHT file for full details. Squid
* incorporates software developed and/or copyrighted by other
* sources; see the CREDITS file for full details.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
*
*/
#include "squid.h"
#if USE_CACHE_DIGESTS
/* local types */
typedef struct {
int bit_count; /* total number of bits */
int bit_on_count; /* #bits turned on */
int bseq_len_sum; /* sum of all bit seq length */
int bseq_count; /* number of bit seqs */
} CacheDigestStats;
/* local functions */
static void cacheDigestHashKey(const CacheDigest * cd, const cache_key * key);
/* static array used by cacheDigestHashKey for optimization purposes */
static u_num32 hashed_keys[4];
static void
cacheDigestInit(CacheDigest * cd, int capacity, int bpe)
{
const size_t mask_size = cacheDigestCalcMaskSize(capacity, bpe);
assert(cd);
assert(capacity > 0 && bpe > 0);
assert(mask_size > 0);
cd->capacity = capacity;
cd->bits_per_entry = bpe;
cd->mask_size = mask_size;
cd->mask = xcalloc(cd->mask_size, 1);
debug(70, 2) ("cacheDigestInit: capacity: %d entries, bpe: %d; size: %d bytes\n",
cd->capacity, cd->bits_per_entry, cd->mask_size);
}
CacheDigest *
cacheDigestCreate(int capacity, int bpe)
{
CacheDigest *cd = memAllocate(MEM_CACHE_DIGEST);
assert(SQUID_MD5_DIGEST_LENGTH == 16); /* our hash functions rely on 16 byte keys */
cacheDigestInit(cd, capacity, bpe);
return cd;
}
static void
cacheDigestClean(CacheDigest * cd)
{
assert(cd);
safe_free(cd->mask);
}
void
cacheDigestDestroy(CacheDigest * cd)
{
assert(cd);
cacheDigestClean(cd);
memFree(cd, MEM_CACHE_DIGEST);
}
CacheDigest *
cacheDigestClone(const CacheDigest * cd)
{
CacheDigest *clone;
assert(cd);
clone = cacheDigestCreate(cd->capacity, cd->bits_per_entry);
clone->count = cd->count;
clone->del_count = cd->del_count;
assert(cd->mask_size == clone->mask_size);
xmemcpy(clone->mask, cd->mask, cd->mask_size);
return clone;
}
void
cacheDigestClear(CacheDigest * cd)
{
assert(cd);
cd->count = cd->del_count = 0;
memset(cd->mask, 0, cd->mask_size);
}
/* changes mask size, resets bits to 0, preserves "cd" pointer */
void
cacheDigestChangeCap(CacheDigest * cd, int new_cap)
{
assert(cd);
cacheDigestClean(cd);
cacheDigestInit(cd, new_cap, cd->bits_per_entry);
}
/* returns true if the key belongs to the digest */
int
cacheDigestTest(const CacheDigest * cd, const cache_key * key)
{
assert(cd && key);
/* hash */
cacheDigestHashKey(cd, key);
/* test corresponding bits */
return
CBIT_TEST(cd->mask, hashed_keys[0]) &&
CBIT_TEST(cd->mask, hashed_keys[1]) &&
CBIT_TEST(cd->mask, hashed_keys[2]) &&
CBIT_TEST(cd->mask, hashed_keys[3]);
}
void
cacheDigestAdd(CacheDigest * cd, const cache_key * key)
{
assert(cd && key);
/* hash */
cacheDigestHashKey(cd, key);
/* turn on corresponding bits */
#if CD_FAST_ADD
CBIT_SET(cd->mask, hashed_keys[0]);
CBIT_SET(cd->mask, hashed_keys[1]);
CBIT_SET(cd->mask, hashed_keys[2]);
CBIT_SET(cd->mask, hashed_keys[3]);
#else
{
int on_xition_cnt = 0;
if (!CBIT_TEST(cd->mask, hashed_keys[0])) {
CBIT_SET(cd->mask, hashed_keys[0]);
on_xition_cnt++;
}
if (!CBIT_TEST(cd->mask, hashed_keys[1])) {
CBIT_SET(cd->mask, hashed_keys[1]);
on_xition_cnt++;
}
if (!CBIT_TEST(cd->mask, hashed_keys[2])) {
CBIT_SET(cd->mask, hashed_keys[2]);
on_xition_cnt++;
}
if (!CBIT_TEST(cd->mask, hashed_keys[3])) {
CBIT_SET(cd->mask, hashed_keys[3]);
on_xition_cnt++;
}
statHistCount(&statCounter.cd.on_xition_count, on_xition_cnt);
}
#endif
cd->count++;
}
void
cacheDigestDel(CacheDigest * cd, const cache_key * key)
{
assert(cd && key);
cd->del_count++;
/* we do not support deletions from the digest */
}
/* returns mask utilization parameters */
static void
cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats)
{
int on_count = 0;
int pos = cd->mask_size * 8;
int seq_len_sum = 0;
int seq_count = 0;
int cur_seq_len = 0;
int cur_seq_type = 1;
assert(stats);
memset(stats, 0, sizeof(*stats));
while (pos-- > 0) {
const int is_on = CBIT_TEST(cd->mask, pos);
if (is_on)
on_count++;
if (is_on != cur_seq_type || !pos) {
seq_len_sum += cur_seq_len;
seq_count++;
cur_seq_type = is_on;
cur_seq_len = 0;
}
cur_seq_len++;
}
stats->bit_count = cd->mask_size * 8;
stats->bit_on_count = on_count;
stats->bseq_len_sum = seq_len_sum;
stats->bseq_count = seq_count;
}
int
cacheDigestBitUtil(const CacheDigest * cd)
{
CacheDigestStats stats;
assert(cd);
cacheDigestStats(cd, &stats);
return xpercentInt(stats.bit_on_count, stats.bit_count);
}
void
cacheDigestGuessStatsUpdate(cd_guess_stats * stats, int real_hit, int guess_hit)
{
assert(stats);
if (real_hit) {
if (guess_hit)
stats->true_hits++;
else
stats->false_misses++;
} else {
if (guess_hit)
stats->false_hits++;
else
stats->true_misses++;
}
}
void
cacheDigestGuessStatsReport(const cd_guess_stats * stats, StoreEntry * sentry, const char *label)
{
const int true_count = stats->true_hits + stats->true_misses;
const int false_count = stats->false_hits + stats->false_misses;
const int hit_count = stats->true_hits + stats->false_hits;
const int miss_count = stats->true_misses + stats->false_misses;
const int tot_count = true_count + false_count;
assert(label);
assert(tot_count == hit_count + miss_count); /* paranoid */
if (!tot_count) {
storeAppendPrintf(sentry, "no guess stats for %s available\n", label);
return;
}
storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label);
storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n");
storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n");
storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
stats->true_hits, xpercent(stats->true_hits, tot_count),
stats->true_misses, xpercent(stats->true_misses, tot_count),
true_count, xpercent(true_count, tot_count));
storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
stats->false_hits, xpercent(stats->false_hits, tot_count),
stats->false_misses, xpercent(stats->false_misses, tot_count),
false_count, xpercent(false_count, tot_count));
storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
hit_count, xpercent(hit_count, tot_count),
miss_count, xpercent(miss_count, tot_count),
tot_count, xpercent(tot_count, tot_count));
storeAppendPrintf(sentry, "\tclose_hits: %d ( %d%%) /* cd said hit, doc was in the peer cache, but we got a miss */\n",
stats->close_hits, xpercentInt(stats->close_hits, stats->false_hits));
}
void
cacheDigestReport(CacheDigest * cd, const char *label, StoreEntry * e)
{
CacheDigestStats stats;
assert(cd && e);
cacheDigestStats(cd, &stats);
storeAppendPrintf(e, "%s digest: size: %d bytes\n",
label ? label : "", stats.bit_count / 8
);
storeAppendPrintf(e, "\t entries: count: %d capacity: %d util: %d%%\n",
cd->count,
cd->capacity,
xpercentInt(cd->count, cd->capacity)
);
storeAppendPrintf(e, "\t deletion attempts: %d\n",
cd->del_count
);
storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
cd->bits_per_entry,
stats.bit_on_count, stats.bit_count,
xpercentInt(stats.bit_on_count, stats.bit_count)
);
storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
stats.bseq_count,
xdiv(stats.bseq_len_sum, stats.bseq_count)
);
}
size_t
cacheDigestCalcMaskSize(int cap, int bpe)
{
return (size_t) (cap * bpe + 7) / 8;
}
static void
cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
{
const unsigned int bit_count = cd->mask_size * 8;
unsigned int tmp_keys[4];
/* we must memcpy to ensure alignment */
xmemcpy(tmp_keys, key, sizeof(tmp_keys));
hashed_keys[0] = htonl(tmp_keys[0]) % bit_count;
hashed_keys[1] = htonl(tmp_keys[1]) % bit_count;
hashed_keys[2] = htonl(tmp_keys[2]) % bit_count;
hashed_keys[3] = htonl(tmp_keys[3]) % bit_count;
debug(70, 9) ("cacheDigestHashKey: %s -(%d)-> %d %d %d %d\n",
storeKeyText(key), bit_count,
hashed_keys[0], hashed_keys[1], hashed_keys[2], hashed_keys[3]);
}
#endif
Jump to Line
Something went wrong with that request. Please try again.