[thirdparty/squid.git] / src / CacheDigest.cc


/*
 * $Id: CacheDigest.cc,v 1.14 1998/04/18 06:54:08 rousskov Exp $
 *
 * DEBUG: section 70    Cache Digest
 * AUTHOR: Alex Rousskov
 *
 * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
 * --------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from the
 *  Internet community.  Development is led by Duane Wessels of the
 *  National Laboratory for Applied Network Research and funded by
 *  the National Science Foundation.
 *
 *  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., 675 Mass Ave, Cambridge, MA 02139, USA.
 *  
 */

#include "squid.h"

/* 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 size_t cacheDigestCalcMaskSize(int cap);

/* configuration params */
static const int BitsPerEntry = 4;

/* static array used by cacheDigestHashKey for optimization purposes */
static u_num32 hashed_keys[4];


CacheDigest *
cacheDigestCreate(int capacity)
{
    const size_t mask_size = cacheDigestCalcMaskSize(capacity);
    CacheDigest *cd = cacheDigestSizedCreate(mask_size, capacity);
    return cd;
}

/* use this method only if mask size is known a priory */
CacheDigest *
cacheDigestSizedCreate(size_t size, int capacity)
{
    CacheDigest *cd = memAllocate(MEM_CACHE_DIGEST);
    assert(MD5_DIGEST_CHARS == 16);	/* our hash functions rely on 16 byte keys */
    assert(capacity > 0);
    cd->capacity = capacity;
    cd->mask_size = size;
    cd->mask = xcalloc(cd->mask_size, 1);
    return cd;
}

void
cacheDigestDestroy(CacheDigest * cd)
{
    assert(cd);
    xfree(cd->mask);
    xfree(cd);
}

CacheDigest *
cacheDigestClone(const CacheDigest * cd)
{
    CacheDigest *clone;
    assert(cd);
    clone = cacheDigestCreate(cd->capacity);
    clone->count = cd->count;
    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);
}

void
cacheDigestChangeCap(CacheDigest * cd, int new_cap)
{
    assert(cd);
    /* have to clear because capacity changes hash functions */
    cacheDigestClear(cd);
    cd->capacity = new_cap;
    cd->mask_size = cacheDigestCalcMaskSize(new_cap);
    cd->mask = xrealloc(cd->mask, cd->mask_size);
}

/* 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++;
	}
#if SQUID_PEER_DIGEST
	statHistCount(&Counter.cd.on_xition_count, on_xition_cnt);
#endif
    }
#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 = 0 != 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;
}

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 */

    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));
}

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: on: %d capacity: %d util: %d%%\n",
	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)
	);
}

static size_t
cacheDigestCalcMaskSize(int cap)
{
    return (size_t) (cap * BitsPerEntry + 7) / 8;
}

static void
cacheDigestHashKey(const CacheDigest *cd, const cache_key *key)
{
    const int bit_count = cd->mask_size * 8;
    /* get four hashed values */
    memcpy(hashed_keys, key, sizeof(hashed_keys));
    /* wrap */
    hashed_keys[0] %= bit_count;
    hashed_keys[1] %= bit_count;
    hashed_keys[2] %= bit_count;
    hashed_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]);
}
Commit	Line	Data
bdbb6d04	1
bdbb6d04	2	/*
e998b523	3	* $Id: CacheDigest.cc,v 1.14 1998/04/18 06:54:08 rousskov Exp $
bdbb6d04	4	*
8638fc66	5	* DEBUG: section 70 Cache Digest
bdbb6d04	6	* AUTHOR: Alex Rousskov
	7	*
	8	* SQUID Internet Object Cache http://squid.nlanr.net/Squid/
	9	* --------------------------------------------------------
	10	*
	11	* Squid is the result of efforts by numerous individuals from the
	12	* Internet community. Development is led by Duane Wessels of the
	13	* National Laboratory for Applied Network Research and funded by
	14	* the National Science Foundation.
	15	*
	16	* This program is free software; you can redistribute it and/or modify
	17	* it under the terms of the GNU General Public License as published by
	18	* the Free Software Foundation; either version 2 of the License, or
	19	* (at your option) any later version.
	20	*
	21	* This program is distributed in the hope that it will be useful,
	22	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	23	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	24	* GNU General Public License for more details.
	25	*
	26	* You should have received a copy of the GNU General Public License
	27	* along with this program; if not, write to the Free Software
	28	* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
	29	*
	30	*/
	31
	32	#include "squid.h"
	33
12784378	34	/* local types */
12784378	35	typedef struct {
b644367b	36	int bit_count; /* total number of bits */
	37	int bit_on_count; /* #bits turned on */
	38	int bseq_len_sum; /* sum of all bit seq length */
	39	int bseq_count; /* number of bit seqs */
12784378	40	} CacheDigestStats;
	41
	42	/* local functions */
56a1c446	43	static void cacheDigestHashKey(const CacheDigest cd, const cache_key key);
304b267e	44	static size_t cacheDigestCalcMaskSize(int cap);
12784378	45
12784378	46	/* configuration params */
bdbb6d04	47	static const int BitsPerEntry = 4;
	48
	49	/* static array used by cacheDigestHashKey for optimization purposes */
	50	static u_num32 hashed_keys[4];
	51
bdbb6d04	52
	53	CacheDigest *
	54	cacheDigestCreate(int capacity)
	55	{
304b267e	56	const size_t mask_size = cacheDigestCalcMaskSize(capacity);
56a1c446	57	CacheDigest *cd = cacheDigestSizedCreate(mask_size, capacity);
	58	return cd;
	59	}
	60
	61	/* use this method only if mask size is known a priory */
	62	CacheDigest *
	63	cacheDigestSizedCreate(size_t size, int capacity)
	64	{
	65	CacheDigest *cd = memAllocate(MEM_CACHE_DIGEST);
1afe05c5	66	assert(MD5_DIGEST_CHARS == 16); /* our hash functions rely on 16 byte keys */
bdbb6d04	67	assert(capacity > 0);
bdbb6d04	68	cd->capacity = capacity;
56a1c446	69	cd->mask_size = size;
bdbb6d04	70	cd->mask = xcalloc(cd->mask_size, 1);
	71	return cd;
	72	}
	73
	74	void
1afe05c5	75	cacheDigestDestroy(CacheDigest * cd)
bdbb6d04	76	{
	77	assert(cd);
	78	xfree(cd->mask);
	79	xfree(cd);
	80	}
	81
6d80b36f	82	CacheDigest *
	83	cacheDigestClone(const CacheDigest * cd)
	84	{
	85	CacheDigest *clone;
	86	assert(cd);
	87	clone = cacheDigestCreate(cd->capacity);
c2186446	88	clone->count = cd->count;
6d80b36f	89	xmemcpy(clone->mask, cd->mask, cd->mask_size);
	90	return clone;
	91	}
	92
12784378	93	void
	94	cacheDigestClear(CacheDigest * cd)
	95	{
	96	assert(cd);
	97	cd->count = cd->del_count = 0;
	98	memset(cd->mask, 0, cd->mask_size);
	99	}
	100
304b267e	101	void
	102	cacheDigestChangeCap(CacheDigest * cd, int new_cap)
	103	{
	104	assert(cd);
	105	/* have to clear because capacity changes hash functions */
	106	cacheDigestClear(cd);
	107	cd->capacity = new_cap;
	108	cd->mask_size = cacheDigestCalcMaskSize(new_cap);
	109	cd->mask = xrealloc(cd->mask, cd->mask_size);
	110	}
	111
bdbb6d04	112	/* returns true if the key belongs to the digest */
bdbb6d04	113	int
1afe05c5	114	cacheDigestTest(const CacheDigest * cd, const cache_key * key)
bdbb6d04	115	{
	116	assert(cd && key);
	117	/* hash */
56a1c446	118	cacheDigestHashKey(cd, key);
bdbb6d04	119	/* test corresponding bits */
1afe05c5	120	return
bdbb6d04	121	CBIT_TEST(cd->mask, hashed_keys[0]) &&
	122	CBIT_TEST(cd->mask, hashed_keys[1]) &&
	123	CBIT_TEST(cd->mask, hashed_keys[2]) &&
	124	CBIT_TEST(cd->mask, hashed_keys[3]);
	125	}
	126
c2186446	127	void
	128	cacheDigestAdd(CacheDigest * cd, const cache_key * key)
	129	{
	130	assert(cd && key);
	131	/* hash */
56a1c446	132	cacheDigestHashKey(cd, key);
c2186446	133	/* turn on corresponding bits */
c135694e	134	#if CD_FAST_ADD
c2186446	135	CBIT_SET(cd->mask, hashed_keys[0]);
	136	CBIT_SET(cd->mask, hashed_keys[1]);
	137	CBIT_SET(cd->mask, hashed_keys[2]);
	138	CBIT_SET(cd->mask, hashed_keys[3]);
c135694e	139	#else
	140	{
	141	int on_xition_cnt = 0;
	142	if (!CBIT_TEST(cd->mask, hashed_keys[0])) {
	143	CBIT_SET(cd->mask, hashed_keys[0]);
	144	on_xition_cnt++;
	145	}
	146	if (!CBIT_TEST(cd->mask, hashed_keys[1])) {
	147	CBIT_SET(cd->mask, hashed_keys[1]);
	148	on_xition_cnt++;
	149	}
	150	if (!CBIT_TEST(cd->mask, hashed_keys[2])) {
	151	CBIT_SET(cd->mask, hashed_keys[2]);
	152	on_xition_cnt++;
	153	}
	154	if (!CBIT_TEST(cd->mask, hashed_keys[3])) {
	155	CBIT_SET(cd->mask, hashed_keys[3]);
	156	on_xition_cnt++;
	157	}
e998b523	158	#if SQUID_PEER_DIGEST
c135694e	159	statHistCount(&Counter.cd.on_xition_count, on_xition_cnt);
e998b523	160	#endif
c135694e	161	}
c135694e	162	#endif
c2186446	163	cd->count++;
	164	}
	165
bdbb6d04	166	void
1afe05c5	167	cacheDigestDel(CacheDigest * cd, const cache_key * key)
bdbb6d04	168	{
	169	assert(cd && key);
	170	cd->del_count++;
	171	/* we do not support deletions from the digest */
	172	}
	173
c2186446	174	/* returns mask utilization parameters */
12784378	175	static void
b644367b	176	cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats)
c2186446	177	{
c2186446	178	int on_count = 0;
56a1c446	179	int pos = cd->mask_size * 8;
12784378	180	int seq_len_sum = 0;
	181	int seq_count = 0;
	182	int cur_seq_len = 0;
	183	int cur_seq_type = 1;
	184	assert(stats);
	185	memset(stats, 0, sizeof(*stats));
c2186446	186	while (pos-- > 0) {
e998b523	187	const int is_on = 0 != CBIT_TEST(cd->mask, pos);
12784378	188	if (is_on)
c2186446	189	on_count++;
12784378	190	if (is_on != cur_seq_type \|\| !pos) {
	191	seq_len_sum += cur_seq_len;
	192	seq_count++;
e998b523	193	cur_seq_type = is_on;
12784378	194	cur_seq_len = 0;
	195	}
	196	cur_seq_len++;
c2186446	197	}
56a1c446	198	stats->bit_count = cd->mask_size * 8;
12784378	199	stats->bit_on_count = on_count;
	200	stats->bseq_len_sum = seq_len_sum;
	201	stats->bseq_count = seq_count;
c2186446	202	}
bdbb6d04	203
8638fc66	204	void
56a1c446	205	cacheDigestGuessStatsUpdate(cd_guess_stats *stats, int real_hit, int guess_hit)
	206	{
	207	assert(stats);
	208	if (real_hit) {
	209	if (guess_hit)
	210	stats->true_hits++;
	211	else
	212	stats->false_misses++;
	213	} else {
	214	if (guess_hit)
	215	stats->false_hits++;
	216	else
	217	stats->true_misses++;
	218	}
	219	}
	220
	221	void
	222	cacheDigestGuessStatsReport(const cd_guess_stats stats, StoreEntry sentry, const char *label)
	223	{
	224	const int true_count = stats->true_hits + stats->true_misses;
	225	const int false_count = stats->false_hits + stats->false_misses;
	226	const int hit_count = stats->true_hits + stats->false_hits;
	227	const int miss_count = stats->true_misses + stats->false_misses;
	228	const int tot_count = true_count + false_count;
	229
	230	assert(label);
	231	assert(tot_count == hit_count + miss_count); /* paranoid */
	232
	233	storeAppendPrintf(sentry, "Digest guesses stats for %s:\n", label);
	234	storeAppendPrintf(sentry, "guess\t hit\t\t miss\t\t total\t\t\n");
	235	storeAppendPrintf(sentry, " \t #\t %%\t #\t %%\t #\t %%\t\n");
	236
	237	storeAppendPrintf(sentry, "true\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	238	stats->true_hits, xpercent(stats->true_hits, tot_count),
	239	stats->true_misses, xpercent(stats->true_misses, tot_count),
	240	true_count, xpercent(true_count, tot_count));
	241	storeAppendPrintf(sentry, "false\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	242	stats->false_hits, xpercent(stats->false_hits, tot_count),
	243	stats->false_misses, xpercent(stats->false_misses, tot_count),
	244	false_count, xpercent(false_count, tot_count));
	245	storeAppendPrintf(sentry, "all\t %d\t %.2f\t %d\t %.2f\t %d\t %.2f\n",
	246	hit_count, xpercent(hit_count, tot_count),
	247	miss_count, xpercent(miss_count, tot_count),
	248	tot_count, xpercent(tot_count, tot_count));
	249	}
	250
	251	void
	252	cacheDigestReport(CacheDigest cd, const char label, StoreEntry * e)
8638fc66	253	{
12784378	254	CacheDigestStats stats;
8638fc66	255	assert(cd && e);
12784378	256	cacheDigestStats(cd, &stats);
12784378	257	storeAppendPrintf(e, "%s digest: size: %d bytes\n",
b644367b	258	label ? label : "", stats.bit_count / 8
b644367b	259	);
8638fc66	260	storeAppendPrintf(e, "\t entries: count: %d capacity: %d util: %d%%\n",
	261	cd->count,
	262	cd->capacity,
	263	xpercentInt(cd->count, cd->capacity)
b644367b	264	);
b644367b	265	storeAppendPrintf(e, "\t deletion attempts: %d\n",
8638fc66	266	cd->del_count
b644367b	267	);
b644367b	268	storeAppendPrintf(e, "\t bits: on: %d capacity: %d util: %d%%\n",
12784378	269	stats.bit_on_count, stats.bit_count,
12784378	270	xpercentInt(stats.bit_on_count, stats.bit_count)
b644367b	271	);
b644367b	272	storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
12784378	273	stats.bseq_count,
12784378	274	xdiv(stats.bseq_len_sum, stats.bseq_count)
b644367b	275	);
8638fc66	276	}
8638fc66	277
304b267e	278	static size_t
	279	cacheDigestCalcMaskSize(int cap)
	280	{
	281	return (size_t) (cap * BitsPerEntry + 7) / 8;
	282	}
	283
bdbb6d04	284	static void
56a1c446	285	cacheDigestHashKey(const CacheDigest cd, const cache_key key)
bdbb6d04	286	{
56a1c446	287	const int bit_count = cd->mask_size * 8;
bdbb6d04	288	/* get four hashed values */
	289	memcpy(hashed_keys, key, sizeof(hashed_keys));
	290	/* wrap */
	291	hashed_keys[0] %= bit_count;
	292	hashed_keys[1] %= bit_count;
	293	hashed_keys[2] %= bit_count;
	294	hashed_keys[3] %= bit_count;
56a1c446	295
	296	debug(70,9) ("cacheDigestHashKey: %s -(%d)-> %d %d %d %d\n",
	297	storeKeyText(key), bit_count, hashed_keys[0], hashed_keys[1], hashed_keys[2], hashed_keys[3]);
bdbb6d04	298	}