test_cache_digest.c

-

/*
 * $Id: test_cache_digest.c,v 1.23 1998/07/22 20:38:01 wessels Exp $
 *
 * 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.
 *
 */

/*
 * Test-suite for playing with cache digests
 */

#include "squid.h"

typedef struct {
    int query_count;
    int true_hit_count;
    int true_miss_count;
    int false_hit_count;
    int false_miss_count;
} CacheQueryStats;

typedef struct _Cache Cache;
struct _Cache {
    const char *name;
    hash_table *hash;
    CacheDigest *digest;
    Cache *peer;
    CacheQueryStats qstats;
    int count;			/* #currently cached entries */
    int req_count;		/* #requests to this cache */
    int bad_add_count;		/* #duplicate adds */
    int bad_del_count;		/* #dels with no prior add */
};


typedef struct _CacheEntry {
    const cache_key *key;
    struct _CacheEntry *next;
    unsigned char key_arr[MD5_DIGEST_CHARS];
    /* storeSwapLogData s; */
} CacheEntry;

/* parsed access log entry */
typedef struct {
    cache_key key[MD5_DIGEST_CHARS];
    time_t timestamp;
    short int use_icp;		/* true/false */
} RawAccessLogEntry;

typedef enum {
    frError = -2, frMore = -1, frEof = 0, frOk = 1
} fr_result;
typedef struct _FileIterator FileIterator;
typedef fr_result(*FI_READER) (FileIterator * fi);

struct _FileIterator {
    const char *fname;
    FILE *file;
    time_t inner_time;		/* timestamp of the current entry */
    time_t time_offset;		/* to adjust time set by reader */
    int line_count;		/* number of lines scanned */
    int bad_line_count;		/* number of parsing errors */
    int time_warp_count;	/* number of out-of-order entries in the file */
    FI_READER reader;		/* reads next entry and updates inner_time */
    void *entry;		/* buffer for the current entry, freed with xfree() */
};

/* globals */
static time_t cur_time = -1;	/* timestamp of the current log entry */

/* copied from url.c */
const char *RequestMethodStr[] =
{
    "NONE",
    "GET",
    "POST",
    "PUT",
    "HEAD",
    "CONNECT",
    "TRACE",
    "PURGE"
};
/* copied from url.c */
static method_t
methodStrToId(const char *s)
{
    if (strcasecmp(s, "GET") == 0) {
	return METHOD_GET;
    } else if (strcasecmp(s, "POST") == 0) {
	return METHOD_POST;
    } else if (strcasecmp(s, "PUT") == 0) {
	return METHOD_PUT;
    } else if (strcasecmp(s, "HEAD") == 0) {
	return METHOD_HEAD;
    } else if (strcasecmp(s, "CONNECT") == 0) {
	return METHOD_CONNECT;
    } else if (strcasecmp(s, "TRACE") == 0) {
	return METHOD_TRACE;
    } else if (strcasecmp(s, "PURGE") == 0) {
	return METHOD_PURGE;
    }
    return METHOD_NONE;
}

/* FileIterator */

static void fileIteratorAdvance(FileIterator * fi);

static FileIterator *
fileIteratorCreate(const char *fname, FI_READER reader)
{
    FileIterator *fi = xcalloc(1, sizeof(FileIterator));
    assert(fname && reader);
    fi->fname = fname;
    fi->reader = reader;
    fi->file = fopen(fname, "r");
    if (!fi->file) {
	fprintf(stderr, "cannot open %s: %s\n", fname, strerror(errno));
	return NULL;
    } else
	fprintf(stderr, "opened %s\n", fname);
    fileIteratorAdvance(fi);
    return fi;
}

static void
fileIteratorDestroy(FileIterator * fi)
{
    assert(fi);
    if (fi->file) {
	fclose(fi->file);
	fprintf(stderr, "closed %s\n", fi->fname);
    }
    xfree(fi->entry);
    xfree(fi);
}

static void
fileIteratorSetCurTime(FileIterator * fi, time_t ct)
{
    assert(fi);
    assert(fi->inner_time > 0);
    fi->time_offset = ct - fi->inner_time;
}

static void
fileIteratorAdvance(FileIterator * fi)
{
    int res;
    assert(fi);
    do {
	const time_t last_time = fi->inner_time;
	fi->inner_time = -1;
	res = fi->reader(fi);
	fi->line_count++;
	if (fi->inner_time < 0)
	    fi->inner_time = last_time;
	else
	    fi->inner_time += fi->time_offset;
	if (res == frError)
	    fi->bad_line_count++;
	else if (res == frEof) {
	    fprintf(stderr, "exhausted %s (%d entries) at %s",
		fi->fname, fi->line_count, ctime(&fi->inner_time));
	    fi->inner_time = -1;
	} else if (fi->inner_time < last_time) {
	    assert(last_time >= 0);
	    fi->time_warp_count++;
	    fi->inner_time = last_time;
	}
	/* report progress */
	if (!(fi->line_count % 50000))
	    fprintf(stderr, "%s scanned %d K entries (%d bad) at %s",
		fi->fname, fi->line_count / 1000, fi->bad_line_count,
		ctime(&fi->inner_time));
    } while (res < 0);
}

/* CacheEntry */

static CacheEntry *
cacheEntryCreate(const storeSwapLogData * s)
{
    CacheEntry *e = xcalloc(1, sizeof(CacheEntry));
    assert(s);
    /* e->s = *s; */
    xmemcpy(e->key_arr, s->key, MD5_DIGEST_CHARS);
    e->key = &e->key_arr[0];
    return e;
}

static void
cacheEntryDestroy(CacheEntry * e)
{
    assert(e);
    xfree(e);
}


/* Cache */

static Cache *
cacheCreate(const char *name)
{
    Cache *c;
    assert(name && strlen(name));
    c = xcalloc(1, sizeof(Cache));
    c->name = name;
    c->hash = hash_create(storeKeyHashCmp, 2e6, storeKeyHashHash);
    return c;
}

static void
cacheDestroy(Cache * cache)
{
    CacheEntry *e = NULL;
    hash_table *hash;
    assert(cache);
    hash = cache->hash;
    /* destroy hash table contents */
    hash_first(hash);
    while (e = hash_next(hash)) {
	hash_remove_link(hash, (hash_link *) e);
	cacheEntryDestroy(e);
    }
    /* destroy the hash table itself */
    hashFreeMemory(hash);
    if (cache->digest)
	cacheDigestDestroy(cache->digest);
    xfree(cache);
}

/* re-digests currently hashed entries */
static void
cacheResetDigest(Cache * cache)
{
    CacheEntry *e = NULL;
    hash_table *hash;
    struct timeval t_start, t_end;

    assert(cache);
    fprintf(stderr, "%s: init-ing digest with %d entries\n", cache->name, cache->count);
    if (cache->digest)
	cacheDigestDestroy(cache->digest);
    hash = cache->hash;
    cache->digest = cacheDigestCreate(cache->count + 1, 6);
    if (!cache->count)
	return;
    gettimeofday(&t_start, NULL);
    hash_first(hash);
    while (e = hash_next(hash)) {
	cacheDigestAdd(cache->digest, e->key);
    }
    gettimeofday(&t_end, NULL);
    assert(cache->digest->count == cache->count);
    fprintf(stderr, "%s: init-ed  digest with %d entries\n",
	cache->name, cache->digest->count);
    fprintf(stderr, "%s: init took: %f sec, %f sec/M\n",
	cache->name,
	tvSubDsec(t_start, t_end),
	(double) 1e6 * tvSubDsec(t_start, t_end) / cache->count);
    /* check how long it takes to traverse the hash */
    gettimeofday(&t_start, NULL);
    for (e = hash_first(hash); e; e = hash_next(hash)) {
    }
    gettimeofday(&t_end, NULL);
    fprintf(stderr, "%s: hash scan took: %f sec, %f sec/M\n",
	cache->name,
	tvSubDsec(t_start, t_end),