cache.c

RADIUS协议的认证计费服务

/*
 * ASCEND: @(#)cache.c	1.0 (95/10/05 00:55:30)
 *
 *      Copyright (c) 1994 Ascend Communications, Inc.
 *      All rights reserved.
 *
 *	Permission to copy all or part of this material for any purpose is
 *	granted provided that the above copyright notice and this paragraph
 *	are duplicated in all copies.  THIS SOFTWARE IS PROVIDED ``AS IS''
 *	AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT
 *	LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 *	FOR A PARTICULAR PURPOSE.
 */

static char     rcsid[] = "$Id: cache.c,v 1.1.1.1 2001/08/10 20:49:27 bonze Exp $";

#include	<sys/types.h>
#include        <sys/param.h>
#include        <sys/socket.h>
#include        <sys/time.h>
#include        <sys/file.h>
#include        <sys/wait.h>
#include        <net/if.h>
#include        <netinet/in.h>

#include	<ctype.h>
#include	<string.h>
#include	<stdio.h>

#if defined(AUTOTEST)
#include	<unistd.h>
#endif	/* AUTOTEST */

#include	"radius.h"
#include	"cache.h"

static CONST HASHVAL * _hlist_search PROTO((HASHLIST ** list,
						CONST HASHKEY * key, int len));
static HASHLIST * _hlist_locate PROTO((HASHLIST ** list, CONST HASHKEY * key,
					int len));
static void _hlist_expire PROTO((HASHLIST ** list));
static int _key_expired PROTO((HASHLIST * elem));
static int _idle_expired PROTO((HASHLIST * elem));
static time_t _calc_expiration PROTO((time_t duration));

#if defined(AUTOTEST)
int             count[BUCKETS];	/* allocater storage for statistics */
#define	log_err	printf		/* debug output */
#else	/* AUTOTEST */
#define	log_err
#endif	/* AUTOTEST */

static CACHE   *cache = NULL;

/*
 * Initialise the given cache.  Return 0 if successful, -1 if problems arise.
 */

int
cache_init ()

{
	int             buckets = BUCKETS;
	int             i;

	if (cache != (CACHE *) NULL)	/* Already init'd */
	{
		return -1;
	}

	cache = (CACHE *) malloc (sizeof (*cache));
	if (cache == (CACHE *) NULL)
	{
		return -1;
	}

	cache->buckets = buckets;
	for (i = 0; i < buckets; i++)
	{
		cache->table[i] = (HASHLIST *) 0;

#if defined(AUTOTEST)
		count[i] = 0;
#endif

	}
	return 0;
} /* end of cache_init () */

/*
 * Search the cache for the indicated key.
 * 
 * Return a pointer to the associated value or (HASHVAL *)0 if the key is not
 * found
 */

CONST HASHVAL *
cache_search (key, len)

CONST HASHKEY  *key;
int             len;

{
	int             bucket;

	if (len > MAX_KEY_LEN)
	{
		return (CONST HASHVAL *) 0;
	}

	bucket = hash (key, len, cache->buckets);
	if (cache->table[bucket])
	{
		return _hlist_search (&cache->table[bucket], key, len);
	}
	else
	{
		return (CONST HASHVAL *) 0;
	}
} /* end of cache_search () */

/*
 * Insert the given info into the cache.
 * 
 * Checks for duplicate records.
 * 
 * Return TRUE if inserted, else FALSE.
 */

int
cache_insert (key, key_len, val, val_len, duration, idle)

CONST HASHKEY  *key;
int             key_len;
CONST HASHVAL  *val;
int             val_len;
time_t          duration;
time_t          idle;

{
	int             bucket;
	HASHLIST       *elem;
	CONST HASHVAL  *res;

	if ((key_len > MAX_KEY_LEN) || (val_len > MAX_VAL_LEN))
	{
		return FALSE;
	}

	bucket = hash (key, key_len, cache->buckets);
	res = _hlist_search (&cache->table[bucket], key, key_len);

	if (res && (res != ELEM_DELETED))
	{
		return FALSE;	/* already in table, delete first */
	}

	elem = (HASHLIST *) malloc (sizeof (*elem));
	if (!elem)
	{
		return FALSE;
	}
	else
	{
		elem->next = cache->table[bucket];
		memcpy (elem->key, key, (size_t) key_len);
		memcpy (elem->val, val, (size_t) val_len);
		elem->time = _calc_expiration (duration);
		if (idle)
		{
			elem->idle = _calc_expiration (idle);
			elem->idling = TRUE;
		}
		else
		{
			elem->idling = FALSE;
		}
		cache->table[bucket] = elem;

#if defined(AUTOTEST)
		count[bucket]++;
#endif

#if(0)
		printf ("cache_insert(key<%d><%s>, val<%d><%s>)\n",
			key_len, elem->key, val_len, elem->val);
#endif

		return TRUE;
	}
} /* end of cache_insert () */

/*
 * Delete the given info from the given cache.
 * 
 * Return TRUE if deleted, else FALSE.
 */

int
cache_delete (key, len)

CONST HASHKEY  *key;
int             len;

{
	int             bucket;
	int             result = FALSE;
	HASHLIST       *cur;
	HASHLIST       *prev = (HASHLIST *) 0;
	HASHLIST      **list;

	if (len > MAX_KEY_LEN)
	{
		return FALSE;
	}

	bucket = hash (key, len, cache->buckets);
	list = &cache->table[bucket];

	for (cur = *list; cur; prev = cur, cur = cur->next)
	{
		if (memcmp (key, cur->key, len) == 0)
		{
			if (prev)
			{
				prev->next = cur->next;
			}
			else
			{
				*list = cur->next;
			}
			free (cur);
			result = TRUE;
			break;
		}
	}
	return result;
} /* end of cache_delete () */

/*
 * Update the idle time for this entry
 * 
 * Return TRUE if elem has idling enabled, else FALSE.
 */

int
cache_idle_update (key, len, idle)

CONST HASHKEY  *key;
int             len;
time_t          idle;

{
	int             bucket;
	HASHLIST       *elem;

	if (len > MAX_KEY_LEN)
	{
		return FALSE;
	}

	bucket = hash (key, len, cache->buckets);
	elem = _hlist_locate (&cache->table[bucket], key, len);
	elem->idle = _calc_expiration (idle);
	return elem->idling;
} /* end of cache_idle_update () */

/*
 * Search the cache for expired keys and delete them.
 */

void
cache_expire ()

{
	int             ix;

	for (ix = 0; ix < cache->buckets; ix++)
	{
		_hlist_expire (&cache->table[ix]);
	}
} /* end of cache_expire () */

/*
 * Search the given hash list for the indicated key.
 * 
 * Return a pointer to the associated elem or (HASHLIST *)0 if the key is not
 * found.
 */

static HASHLIST *
_hlist_locate (list, key, len)

HASHLIST      **list;
CONST HASHKEY  *key;
int             len;

{
	HASHLIST       *cur;
	HASHLIST       *prev;
	HASHLIST       *retval = (HASHLIST *) 0;

	prev = (HASHLIST *) 0;
	for (cur = *list; cur; prev = cur, cur = cur->next)
	{
		if (memcmp (key, cur->key, len) == 0)
		{
			retval = cur;
			break;
		}
	}

	return retval;
} /* end of _hlist_locate () */

/*
 * Search the given hash list for the indicated key.
 * 
 * Return a pointer to the associated value or (HASHVAL *)0 if the key is not
 * found.
 * 
 * For efficiency, delete the search entry if it has expired and return
 * ELEM_DELETED.
 * 
 * Does NOT update the idle timer.
 */

static CONST HASHVAL *
_hlist_search (list, key, len)

HASHLIST      **list;
CONST HASHKEY  *key;
int             len;

{
	HASHLIST       *cur;
	HASHLIST       *prev;
	HASHVAL        *retval = (HASHVAL *) 0;

	prev = (HASHLIST *) 0;
	for (cur = *list; cur; prev = cur, cur = cur->next)
	{
		if (memcmp (key, cur->key, len) == 0)
		{
			retval = cur->val;
			break;
		}
	}
	if (retval)
	{
		if ((_key_expired (cur) == TRUE) ||
		    ((cur->idling == TRUE) && (_idle_expired (cur) == TRUE)))
		{
			/* delete it now */
			if (prev)
			{
				prev->next = cur->next;
			}
			else
			{
				*list = cur->next;
			}
			retval = ELEM_DELETED;
			free (cur);
		}
	}
	return (CONST HASHVAL *) retval;
} /* end of _hlist_search () */

/*
 * Search for and delete all expired keys
 */

static void
_hlist_expire (list)

HASHLIST      **list;

{
	HASHLIST       *cur;
	HASHLIST       *prev;

	prev = (HASHLIST *) 0;
	for (cur = *list; cur; prev = cur, cur = cur->next)
	{
		if (_key_expired (cur))
		{
			if (prev)
			{
				prev->next = cur->next;
			}
			else
			{
				*list = cur->next;
			}
			free (cur);
		}
	}
} /* end of _hlist_expire () */

/*
 * Return TRUE if the key has expired
 */

static int
_key_expired (elem)

HASHLIST       *elem;

{
	time_t          curtime;

	curtime = time ((time_t *) 0);
	if (curtime == -1)
	{
		log_err ("_key_expired(): time() err\n");
		return TRUE;
	}
	if (curtime > elem->time)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
} /* end of _key_expired () */

/*
 * Return TRUE if the idle timer has expired
 */

static int
_idle_expired (elem)

HASHLIST       *elem;

{
	time_t          curtime;

	curtime = time ((time_t *) 0);
	if (curtime == -1)
	{
		log_err ("_key_expired(): time() err\n");
		return TRUE;
	}
	if (curtime > elem->idle)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
} /* end of _idle_expired () */

/*
 * Calculate the time of expiration
 */

static          time_t
_calc_expiration (duration)

time_t          duration;

{
	time_t          curtime;

	curtime = time ((time_t *) 0);
	if (curtime == -1)
	{
		log_err ("_calc_expiration(): time() err\n");
		return duration;
	}
	curtime += duration;
	return curtime;
} /* end of _calc_expiration () */

/**********************************************************

	CRC-16 Byte Look-up Table <initial crc=0>

		P(x) = a001 = 1 + x^2 + x^15 + x^16

	This table was automatically generated by 'gencrc'

	-- Do _NOT_ modify this table manually ! --

	Table generated on Thu Oct  5 16:45:34 1995

**********************************************************/

unsigned short  crc_16_lookup[256] =
{
	0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241,
	0xc601, 0x06c0, 0x0780, 0xc741, 0x0500, 0xc5c1, 0xc481, 0x0440,
	0xcc01, 0x0cc0, 0x0d80, 0xcd41, 0x0f00, 0xcfc1, 0xce81, 0x0e40,
	0x0a00, 0xcac1, 0xcb81, 0x0b40, 0xc901, 0x09c0, 0x0880, 0xc841,
	0xd801, 0x18c0, 0x1980, 0xd941, 0x1b00, 0xdbc1, 0xda81, 0x1a40,
	0x1e00, 0xdec1, 0xdf81, 0x1f40, 0xdd01, 0x1dc0, 0x1c80, 0xdc41,
	0x1400, 0xd4c1, 0xd581, 0x1540, 0xd701, 0x17c0, 0x1680, 0xd641,
	0xd201, 0x12c0, 0x1380, 0xd341, 0x1100, 0xd1c1, 0xd081, 0x1040,
	0xf001, 0x30c0, 0x3180, 0xf141, 0x3300, 0xf3c1, 0xf281, 0x3240,
	0x3600, 0xf6c1, 0xf781, 0x3740, 0xf501, 0x35c0, 0x3480, 0xf441,
	0x3c00, 0xfcc1, 0xfd81, 0x3d40, 0xff01, 0x3fc0, 0x3e80, 0xfe41,
	0xfa01, 0x3ac0, 0x3b80, 0xfb41, 0x3900, 0xf9c1, 0xf881, 0x3840,
	0x2800, 0xe8c1, 0xe981, 0x2940, 0xeb01, 0x2bc0, 0x2a80, 0xea41,
	0xee01, 0x2ec0, 0x2f80, 0xef41, 0x2d00, 0xedc1, 0xec81, 0x2c40,
	0xe401, 0x24c0, 0x2580, 0xe541, 0x2700, 0xe7c1, 0xe681, 0x2640,
	0x2200, 0xe2c1, 0xe381, 0x2340, 0xe101, 0x21c0, 0x2080, 0xe041,
	0xa001, 0x60c0, 0x6180, 0xa141, 0x6300, 0xa3c1, 0xa281, 0x6240,
	0x6600, 0xa6c1, 0xa781, 0x6740, 0xa501, 0x65c0, 0x6480, 0xa441,
	0x6c00, 0xacc1, 0xad81, 0x6d40, 0xaf01, 0x6fc0, 0x6e80, 0xae41,
	0xaa01, 0x6ac0, 0x6b80, 0xab41, 0x6900, 0xa9c1, 0xa881, 0x6840,
	0x7800, 0xb8c1, 0xb981, 0x7940, 0xbb01, 0x7bc0, 0x7a80, 0xba41,
	0xbe01, 0x7ec0, 0x7f80, 0xbf41, 0x7d00, 0xbdc1, 0xbc81, 0x7c40,
	0xb401, 0x74c0, 0x7580, 0xb541, 0x7700, 0xb7c1, 0xb681, 0x7640,
	0x7200, 0xb2c1, 0xb381, 0x7340, 0xb101, 0x71c0, 0x7080, 0xb041,
	0x5000, 0x90c1, 0x9181, 0x5140, 0x9301, 0x53c0, 0x5280, 0x9241,
	0x9601, 0x56c0, 0x5780, 0x9741, 0x5500, 0x95c1, 0x9481, 0x5440,
	0x9c01, 0x5cc0, 0x5d80, 0x9d41, 0x5f00, 0x9fc1, 0x9e81, 0x5e40,
	0x5a00, 0x9ac1, 0x9b81, 0x5b40, 0x9901, 0x59c0, 0x5880, 0x9841,
	0x8801, 0x48c0, 0x4980, 0x8941, 0x4b00, 0x8bc1, 0x8a81, 0x4a40,
	0x4e00, 0x8ec1, 0x8f81, 0x4f40, 0x8d01, 0x4dc0, 0x4c80, 0x8c41,
	0x4400, 0x84c1, 0x8581, 0x4540, 0x8701, 0x47c0, 0x4680, 0x8641,
	0x8201, 0x42c0, 0x4380, 0x8341, 0x4100, 0x81c1, 0x8081, 0x4040
};

/*-----------------------------------------------------------------------
	unsigned short hash(key, len, buckets)

	Calculate the CRC-16 of a key, modulo MODULUS.

		uses the x^16 + x^15 + x^2 + 1 CRC-16 algorithm

	Return the 16 bit crc number for a key, mod BUCKETS.
	Uses a 256 entry table lookup.

		NOTE: 17 (_not_ 16) terms [x^16 ... x^0]

		X^16 + X^15 + X^2 + 1
			= 1 1000 0000 0000 0101
			= 18005
			  ^ implicit value (17th bit)

		Inverting the bit order yields
			= 1010 0000 0000 0001 1
			= a0011
			      ^ implicit value (17th  bit)
--------------------------------------------------------------------*/

u_short
hash (key, len, buckets)

CONST HASHKEY  *key;
int             len;
int             buckets;

{
	u_short         crc;
	u_short         n;
	int             i;

	crc = 0;
	for (i = len; i; i--)
	{
		n = *key++;
		n ^= crc;
		crc = crc_16_lookup[n & 0xff] ^ (crc >> 8);
	}
	return (unsigned int) crc % (unsigned int) buckets;
} /* end of hash () */

#if defined(AUTOTEST)

/**********************************************************************

			Test code

**********************************************************************/

int
main (argc, argv)

int             argc;
char          **argv;

{
	int             i;
	int             least;
	int             len;
	int             most;
	int             stat;
	FILE           *fd;
	HASHVAL        *val;
	char           *words;	/* typically, /usr/dict/words */
	char            buf[101];

	if (argc < 2)
	{
		words = "/usr/dict/words";
	}
	else
	{
		words = argv[1];
	}

	cache_init ();
	fd = fopen (words, "r");
	if (!fd)
	{
		printf ("Error opening '%s'\n", words);
		exit (-1);
	}

	while (fgets (buf, 100, fd) != (char *) 0)
	{
		len = strlen (buf);
		if (buf[len - 1] == '\n')
		{
			buf[len - 1] = '\0';
			len--;
		}
		len = MIN ((size_t) MAX_KEY_LEN, strlen (buf));
		buf[len + 1] = '\0';
		stat = cache_insert (buf, len + 1, buf, len + 1, 0);
		printf ("Insert key <%s>: %s\n",
			buf, (stat == TRUE) ? "GOOD" : "BAD");
	}

	least = most = 0;
	for (i = 0; i < BUCKETS; i++)
	{
		if (count[i] < least)
		{
			least = count[i];
		}
		else if (count[i] > most)
		{
			most = count[i];
		}
	}
	printf ("\n\nShortest List Len=%d, Longest List Len=%d\n\n",
		least, most);
	for (i = 0; i < BUCKETS; i++)
	{
		if ((i % 10) == 0)
		{
			printf ("\ncount[%4x]= ", i);
		}
		printf ("%4d ", count[i]);
	}
	printf ("\n\n");

	rewind (fd);
	while (fgets (buf, 100, fd) != (char *) 0)
	{
		char           *msg;

		len = strlen (buf);
		if (buf[len - 1] == '\n')
		{
			buf[len - 1] = '\0';
			len--;
		}
		len = MIN ((size_t) MAX_KEY_LEN, strlen (buf));
		buf[len + 1] = '\0';
		val = (HASHVAL *) cache_search (buf, len + 1);
		if (val && (val != ELEM_DELETED))
		{
			msg = "GOOD search";
		}
		else if (val == ELEM_DELETED)
		{
			msg = "DELETED before search";
		}
		else
		{
			msg = "BAD return from search";
		}
		if (val != ELEM_DELETED)
		{
			printf ("Search key <%s, %s>: %s\n", buf, val, msg);
		}
		else
		{
			printf ("Search key <%s>: %s\n", buf, msg);
		}
	}

	rewind (fd);
	while (fgets (buf, 100, fd) != (char *) 0)
	{
		len = strlen (buf);
		if (buf[len - 1] == '\n')
		{
			buf[len - 1] = '\0';
			len--;
		}
		len = MIN ((size_t) MAX_KEY_LEN, strlen (buf));
		buf[len + 1] = '\0';
		stat = cache_delete (buf, len + 1);
		printf ("Delete key <%s>: %s\n",
			buf, (stat == TRUE) ? "GOOD" : "BAD");
	}

	fclose (fd);
	return 0;
} /* end of main () */

#endif	/* AUTOTEST */