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

/*
 * Copyright (C) 1996-2025 The Squid Software Foundation and contributors
 *
 * Squid software is distributed under GPLv2+ license and includes
 * contributions from numerous individuals and organizations.
 * Please see the COPYING and CONTRIBUTORS files for details.
 */

/* DEBUG: section 70    Cache Digest */

#include "squid.h"
#include "md5.h"
#include "StatCounters.h"
#include "Store.h"
#include "store_key_md5.h"

#if USE_CACHE_DIGESTS

#include "CacheDigest.h"
#include "util.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 array used by cacheDigestHashKey for optimization purposes */
static uint32_t hashed_keys[4];

void
CacheDigest::init(uint64_t newCapacity)
{
    const auto newMaskSz = CacheDigest::CalcMaskSize(newCapacity, bits_per_entry);
    assert(newCapacity > 0 && bits_per_entry > 0);
    assert(newMaskSz != 0);
    capacity = newCapacity;
    mask_size = newMaskSz;
    mask = static_cast<char *>(xcalloc(mask_size,1));
    debugs(70, 2, "capacity: " << capacity << " entries, bpe: " << bits_per_entry << "; size: "
           << mask_size << " bytes");
}

CacheDigest::CacheDigest(uint64_t aCapacity, uint8_t bpe) :
    count(0),
    del_count(0),
    capacity(0),
    mask(nullptr),
    mask_size(0),
    bits_per_entry(bpe)
{
    assert(SQUID_MD5_DIGEST_LENGTH == 16);  /* our hash functions rely on 16 byte keys */
    updateCapacity(aCapacity);
}

CacheDigest::~CacheDigest()
{
    xfree(mask);
}

CacheDigest *
CacheDigest::clone() const
{
    CacheDigest *cl = new CacheDigest(capacity, bits_per_entry);
    cl->count = count;
    cl->del_count = del_count;
    assert(mask_size == cl->mask_size);
    memcpy(cl->mask, mask, mask_size);
    return cl;
}

void
CacheDigest::clear()
{
    count = del_count = 0;
    memset(mask, 0, mask_size);
}

void
CacheDigest::updateCapacity(uint64_t newCapacity)
{
    safe_free(mask);
    init(newCapacity); // will re-init mask and mask_size
}

bool
CacheDigest::contains(const cache_key * key) const
{
    assert(key);
    /* hash */
    cacheDigestHashKey(this, key);
    /* test corresponding bits */
    return
        CBIT_TEST(mask, hashed_keys[0]) &&
        CBIT_TEST(mask, hashed_keys[1]) &&
        CBIT_TEST(mask, hashed_keys[2]) &&
        CBIT_TEST(mask, hashed_keys[3]);
}

void
CacheDigest::add(const cache_key * key)
{
    assert(key);
    /* hash */
    cacheDigestHashKey(this, key);
    /* turn on corresponding bits */
    int on_xition_cnt = 0;

    if (!CBIT_TEST(mask, hashed_keys[0])) {
        CBIT_SET(mask, hashed_keys[0]);
        ++on_xition_cnt;
    }

    if (!CBIT_TEST(mask, hashed_keys[1])) {
        CBIT_SET(mask, hashed_keys[1]);
        ++on_xition_cnt;
    }

    if (!CBIT_TEST(mask, hashed_keys[2])) {
        CBIT_SET(mask, hashed_keys[2]);
        ++on_xition_cnt;
    }

    if (!CBIT_TEST(mask, hashed_keys[3])) {
        CBIT_SET(mask, hashed_keys[3]);
        ++on_xition_cnt;
    }

    statCounter.cd.on_xition_count.count(on_xition_cnt);
    ++count;
}

void
CacheDigest::remove(const cache_key * key)
{
    assert(key);
    ++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;
}

double
CacheDigest::usedMaskPercent() const
{
    CacheDigestStats stats;
    cacheDigestStats(this, &stats);
    return xpercent(stats.bit_on_count, stats.bit_count);
}

void
cacheDigestGuessStatsUpdate(CacheDigestGuessStats * stats, int real_hit, int guess_hit)
{
    assert(stats);

    if (real_hit) {
        if (guess_hit)
            ++stats->trueHits;
        else
            ++stats->falseMisses;
    } else {
        if (guess_hit)
            ++stats->falseHits;
        else
            ++stats->trueMisses;
    }
}

void
cacheDigestGuessStatsReport(const CacheDigestGuessStats * stats, StoreEntry * sentry, const SBuf &label)
{
    const int true_count = stats->trueHits + stats->trueMisses;
    const int false_count = stats->falseHits + stats->falseMisses;
    const int hit_count = stats->trueHits + stats->falseHits;
    const int miss_count = stats->trueMisses + stats->falseMisses;
    const int tot_count = true_count + false_count;

    assert(!label.isEmpty());
    assert(tot_count == hit_count + miss_count);    /* paranoid */

    if (!tot_count) {
        storeAppendPrintf(sentry, "no guess stats for " SQUIDSBUFPH " available\n", SQUIDSBUFPRINT(label));
        return;
    }

    storeAppendPrintf(sentry, "Digest guesses stats for " SQUIDSBUFPH ":\n", SQUIDSBUFPRINT(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->trueHits, xpercent(stats->trueHits, tot_count),
                      stats->trueMisses, xpercent(stats->trueMisses, 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->falseHits, xpercent(stats->falseHits, tot_count),
                      stats->falseMisses, xpercent(stats->falseMisses, 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 SBuf &label, StoreEntry * e)
{
    CacheDigestStats stats;
    assert(cd && e);
    cacheDigestStats(cd, &stats);
    storeAppendPrintf(e, SQUIDSBUFPH " digest: size: %d bytes\n",
                      SQUIDSBUFPRINT(label), stats.bit_count / 8
                     );
    storeAppendPrintf(e, "\t entries: count: %" PRIu64 " capacity: %" PRIu64 " util: %d%%\n",
                      cd->count,
                      cd->capacity,
                      xpercentInt(cd->count, cd->capacity)
                     );
    storeAppendPrintf(e, "\t deletion attempts: %" PRIu64 "\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)
                     );
}

uint32_t
CacheDigest::CalcMaskSize(uint64_t cap, uint8_t bpe)
{
    uint64_t bitCount = (cap * bpe) + 7;
    assert(bitCount < INT_MAX); // do not 31-bit overflow later
    return static_cast<uint32_t>(bitCount / 8);
}

static void
cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
{
    const uint32_t bit_count = cd->mask_size * 8;
    unsigned int tmp_keys[4];
    /* we must memcpy to ensure alignment */
    memcpy(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;
    debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key) << " -(" <<
           bit_count << ")-> " << hashed_keys[0] << " " << hashed_keys[1] <<
           " " << hashed_keys[2] << " " << hashed_keys[3]);
}

#endif
Commit	Line	Data
	1	/*
	2	* Copyright (C) 1996-2025 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	int on_xition_cnt = 0;
	114
	115	if (!CBIT_TEST(mask, hashed_keys[0])) {
	116	CBIT_SET(mask, hashed_keys[0]);
	117	++on_xition_cnt;
	118	}
	119
	120	if (!CBIT_TEST(mask, hashed_keys[1])) {
	121	CBIT_SET(mask, hashed_keys[1]);
	122	++on_xition_cnt;
	123	}
	124
	125	if (!CBIT_TEST(mask, hashed_keys[2])) {
	126	CBIT_SET(mask, hashed_keys[2]);
	127	++on_xition_cnt;
	128	}
	129
	130	if (!CBIT_TEST(mask, hashed_keys[3])) {
	131	CBIT_SET(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
	140	CacheDigest::remove(const cache_key * key)
	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
	149	cacheDigestStats(const CacheDigest * cd, CacheDigestStats * stats)
	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
	183	CacheDigest::usedMaskPercent() const
	184	{
	185	CacheDigestStats stats;
	186	cacheDigestStats(this, &stats);
	187	return xpercent(stats.bit_on_count, stats.bit_count);
	188	}
	189
	190	void
	191	cacheDigestGuessStatsUpdate(CacheDigestGuessStats * stats, int real_hit, int guess_hit)
	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
	209	cacheDigestGuessStatsReport(const CacheDigestGuessStats * stats, StoreEntry * sentry, const SBuf &label)
	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	}
	241
	242	void
	243	cacheDigestReport(CacheDigest * cd, const SBuf &label, StoreEntry * e)
	244	{
	245	CacheDigestStats stats;
	246	assert(cd && e);
	247	cacheDigestStats(cd, &stats);
	248	storeAppendPrintf(e, SQUIDSBUFPH " digest: size: %d bytes\n",
	249	SQUIDSBUFPRINT(label), stats.bit_count / 8
	250	);
	251	storeAppendPrintf(e, "\t entries: count: %" PRIu64 " capacity: %" PRIu64 " util: %d%%\n",
	252	cd->count,
	253	cd->capacity,
	254	xpercentInt(cd->count, cd->capacity)
	255	);
	256	storeAppendPrintf(e, "\t deletion attempts: %" PRIu64 "\n",
	257	cd->del_count
	258	);
	259	storeAppendPrintf(e, "\t bits: per entry: %d on: %d capacity: %d util: %d%%\n",
	260	cd->bits_per_entry,
	261	stats.bit_on_count, stats.bit_count,
	262	xpercentInt(stats.bit_on_count, stats.bit_count)
	263	);
	264	storeAppendPrintf(e, "\t bit-seq: count: %d avg.len: %.2f\n",
	265	stats.bseq_count,
	266	xdiv(stats.bseq_len_sum, stats.bseq_count)
	267	);
	268	}
	269
	270	uint32_t
	271	CacheDigest::CalcMaskSize(uint64_t cap, uint8_t bpe)
	272	{
	273	uint64_t bitCount = (cap * bpe) + 7;
	274	assert(bitCount < INT_MAX); // do not 31-bit overflow later
	275	return static_cast<uint32_t>(bitCount / 8);
	276	}
	277
	278	static void
	279	cacheDigestHashKey(const CacheDigest * cd, const cache_key * key)
	280	{
	281	const uint32_t bit_count = cd->mask_size * 8;
	282	unsigned int tmp_keys[4];
	283	/* we must memcpy to ensure alignment */
	284	memcpy(tmp_keys, key, sizeof(tmp_keys));
	285	hashed_keys[0] = htonl(tmp_keys[0]) % bit_count;
	286	hashed_keys[1] = htonl(tmp_keys[1]) % bit_count;
	287	hashed_keys[2] = htonl(tmp_keys[2]) % bit_count;
	288	hashed_keys[3] = htonl(tmp_keys[3]) % bit_count;
	289	debugs(70, 9, "cacheDigestHashKey: " << storeKeyText(key) << " -(" <<
	290	bit_count << ")-> " << hashed_keys[0] << " " << hashed_keys[1] <<
	291	" " << hashed_keys[2] << " " << hashed_keys[3]);
	292	}
	293
	294	#endif
	295