store_digest.c

-

/*
 * $Id: store_digest.c,v 1.34 1998/12/05 00:54:44 wessels Exp $
 *
 * DEBUG: section 71    Store Digest Manager
 * 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.  Squid is Copyrighted (C) 1998 by
 *  Duane Wessels and the University of California San Diego.  Please
 *  see the COPYRIGHT file for full details.  Squid incorporates
 *  software developed and/or copyrighted by other sources.  Please 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.
 *
 */


/*
 * TODO: We probably do not track all the cases when
 *       storeDigestNoteStoreReady() must be called; this may prevent
 *       storeDigestRebuild/write schedule to be activated
 */

#include "squid.h"

#if USE_CACHE_DIGESTS

/*
 * local types
 */

typedef struct {
    StoreDigestCBlock cblock;
    int rebuild_lock;		/* bucket number */
    StoreEntry *rewrite_lock;	/* store entry with the digest */
    int rebuild_offset;
    int rewrite_offset;
    int rebuild_count;
    int rewrite_count;
} StoreDigestState;

typedef struct {
    int del_count;		/* #store entries deleted from store_digest */
    int del_lost_count;		/* #store entries not found in store_digest on delete */
    int add_count;		/* #store entries accepted to store_digest */
    int add_coll_count;		/* #accepted entries that collided with existing ones */
    int rej_count;		/* #store entries not accepted to store_digest */
    int rej_coll_count;		/* #not accepted entries that collided with existing ones */
} StoreDigestStats;

/*
 * local constants (many of these are good candidates for SquidConfig
 */

/* #bits per entry in store digest */
static const int StoreDigestBitsPerEntry = 5;
/* how often we want to rebuild the digest, in seconds */
static const time_t StoreDigestRebuildPeriod = 60 * 60;
/* how often we want to rewrite the digest after rebuild, in seconds */
static const int StoreDigestRewritePeriod = 60 * 60;
/* how many bytes to swap out at a time */
static const int StoreDigestSwapOutChunkSize = SM_PAGE_SIZE;
/* portion (0,1] of a hash table to be rescanned at a time */
static const double StoreDigestRebuildChunkPercent = 0.10;

/* local vars */
static StoreDigestState sd_state;
static StoreDigestStats sd_stats;

/* local prototypes */
static void storeDigestRebuildStart(void *datanotused);
static void storeDigestRebuildResume(void);
static void storeDigestRebuildFinish(void);
static void storeDigestRebuildStep(void *datanotused);
static void storeDigestRewriteStart(void *);
static void storeDigestRewriteResume(void);
static void storeDigestRewriteFinish(StoreEntry * e);
static EVH storeDigestSwapOutStep;
static void storeDigestCBlockSwapOut(StoreEntry * e);
static int storeDigestCalcCap(void);
static int storeDigestResize(void);
static void storeDigestAdd(const StoreEntry *);

#endif /* USE_CACHE_DIGESTS */

/*
 * PUBLIC FUNCTIONS
 */

void
storeDigestInit(void)
{
#if USE_CACHE_DIGESTS
    const int cap = storeDigestCalcCap();
    store_digest = cacheDigestCreate(cap, StoreDigestBitsPerEntry);
    debug(71, 1) ("Local cache digest enabled; rebuild/rewrite every %d/%d sec\n",
	StoreDigestRebuildPeriod, StoreDigestRewritePeriod);
    memset(&sd_state, 0, sizeof(sd_state));
    cachemgrRegister("store_digest", "Store Digest",
	storeDigestReport, 0, 1);
#else
    store_digest = NULL;
    debug(71, 3) ("Local cache digest is 'off'\n");
#endif
}

/* called when store_rebuild completes */
void
storeDigestNoteStoreReady(void)
{
#if USE_CACHE_DIGESTS
    storeDigestRebuildStart(NULL);
    storeDigestRewriteStart(NULL);
#endif
}

void
storeDigestDel(const StoreEntry * entry)
{
#if USE_CACHE_DIGESTS
    assert(entry && store_digest);
    debug(71, 6) ("storeDigestDel: checking entry, key: %s\n",
	storeKeyText(entry->key));
    if (!EBIT_TEST(entry->flags, KEY_PRIVATE)) {
	if (!cacheDigestTest(store_digest, entry->key)) {
	    sd_stats.del_lost_count++;
	    debug(71, 6) ("storeDigestDel: lost entry, key: %s url: %s\n",
		storeKeyText(entry->key), storeUrl(entry));
	} else {
	    sd_stats.del_count++;
	    cacheDigestDel(store_digest, entry->key);
	    debug(71, 6) ("storeDigestDel: deled entry, key: %s\n",
		storeKeyText(entry->key));
	}
    }
#endif
}

void
storeDigestReport(StoreEntry * e)
{
#if USE_CACHE_DIGESTS
    if (store_digest) {
	cacheDigestReport(store_digest, "store", e);
	storeAppendPrintf(e, "\t added: %d rejected: %d ( %.2f %%) del-ed: %d\n",
	    sd_stats.add_count,
	    sd_stats.rej_count,
	    xpercent(sd_stats.rej_count, sd_stats.rej_count + sd_stats.add_count),
	    sd_stats.del_count);
	storeAppendPrintf(e, "\t collisions: on add: %.2f %% on rej: %.2f %%\n",
	    xpercent(sd_stats.add_coll_count, sd_stats.add_count),
	    xpercent(sd_stats.rej_coll_count, sd_stats.rej_count));
    } else {
	storeAppendPrintf(e, "store digest: disabled.\n");
    }
#endif
}

/*
 * LOCAL FUNCTIONS
 */

#if USE_CACHE_DIGESTS

/* should we digest this entry? used by storeDigestAdd() */
static int
storeDigestAddable(const StoreEntry * e)
{
    /* add some stats! XXX */

    debug(71, 6) ("storeDigestAddable: checking entry, key: %s\n",
	storeKeyText(e->key));

    /* check various entry flags (mimics storeCheckCachable XXX) */
    if (!EBIT_TEST(e->flags, ENTRY_CACHABLE)) {
	debug(71, 6) ("storeDigestAddable: NO: not cachable\n");
	return 0;
    }
    if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
	debug(71, 6) ("storeDigestAddable: NO: private key\n");
	return 0;
    }
    if (EBIT_TEST(e->flags, ENTRY_NEGCACHED)) {
	debug(71, 6) ("storeDigestAddable: NO: negative cached\n");
	return 0;
    }
    if (EBIT_TEST(e->flags, RELEASE_REQUEST)) {
	debug(71, 6) ("storeDigestAddable: NO: release requested\n");
	return 0;
    }
    if (e->store_status == STORE_OK && EBIT_TEST(e->flags, ENTRY_BAD_LENGTH)) {
	debug(71, 6) ("storeDigestAddable: NO: wrong content-length\n");
	return 0;
    }
    /* do not digest huge objects */
    if (e->swap_file_sz > Config.Store.maxObjectSize) {
	debug(71, 6) ("storeDigestAddable: NO: too big\n");
	return 0;
    }
    /* still here? check staleness */
    /* Note: We should use the time of the next rebuild, not (cur_time+period) */
    if (refreshCheckDigest(e, StoreDigestRebuildPeriod)) {
	debug(71, 6) ("storeDigestAdd: entry expires within %d secs, ignoring\n",
	    StoreDigestRebuildPeriod);
	return 0;
    }
    /* idea: how about also skipping very fresh (thus, potentially unstable) 
     * entries? Should be configurable through cd_refresh_pattern, of course */

    return 1;
}

static void
storeDigestAdd(const StoreEntry * entry)
{
    assert(entry && store_digest);

    if (storeDigestAddable(entry)) {
	sd_stats.add_count++;
	if (cacheDigestTest(store_digest, entry->key))
	    sd_stats.add_coll_count++;
	cacheDigestAdd(store_digest, entry->key);
	debug(71, 6) ("storeDigestAdd: added entry, key: %s\n",
	    storeKeyText(entry->key));
    } else {
	sd_stats.rej_count++;
	if (cacheDigestTest(store_digest, entry->key))