/* * Copyright (c) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, * 2002, 2003, 2004 * Ohio University. * * --- * * Starting with the release of tcptrace version 6 in 2001, tcptrace * is licensed under the GNU General Public License (GPL). We believe * that, among the available licenses, the GPL will do the best job of * allowing tcptrace to continue to be a valuable, freely-available * and well-maintained tool for the networking community. * * Previous versions of tcptrace were released under a license that * was much less restrictive with respect to how tcptrace could be * used in commercial products. Because of this, I am willing to * consider alternate license arrangements as allowed in Section 10 of * the GNU GPL. Before I would consider licensing tcptrace under an * alternate agreement with a particular individual or company, * however, I would have to be convinced that such an alternative * would be to the greater benefit of the networking community. * * --- * * This file is part of Tcptrace. * * Tcptrace was originally written and continues to be maintained by * Shawn Ostermann with the help of a group of devoted students and * users (see the file 'THANKS'). The work on tcptrace has been made * possible over the years through the generous support of NASA GRC, * the National Science Foundation, and Sun Microsystems. * * Tcptrace 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. * * Tcptrace 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 Tcptrace (in the file 'COPYING'); if not, write to the * Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, * MA 02111-1307 USA * * Author: Shawn Ostermann * School of Electrical Engineering and Computer Science * Ohio University * Athens, OH * ostermann@cs.ohiou.edu * http://www.tcptrace.org/ */ #include "tcptrace.h" static char const GCC_UNUSED copyright[] = "@(#)Copyright (c) 2004 -- Ohio University.\n"; static char const GCC_UNUSED rcsid[] = "@(#)$Header: /usr/local/cvs/tcptrace/gcache.c,v 5.7 2003/11/19 14:38:02 sdo Exp $"; /* * gcache.c - generalized cacheing routines */ #include #include "gcache.h" /* Let's use ANSI C rather than old BSD calls... */ #ifndef bzero #define bzero(ptr,nbytes) memset(ptr,0,nbytes) #endif #ifndef bcopy #define bcopy(from_ptr,to_ptr,nbytes) memcpy(to_ptr,from_ptr,nbytes) #endif static int ca_enabled; /* control block for a single cache */ enum cb_status { CB_INUSE=1, CB_FREE=2}; typedef enum cb_status cb_status; struct cacheblk { cb_status cb_status; /* INUSE or FREE */ char cb_name[CA_NAMELEN]; /* name of the cache */ u_short cb_maxent; /* maximum entries */ u_short cb_nument; /* number of entries */ u_short cb_hashsize; /* size of hash table */ u_int cb_maxlife; /* max life of an entry (secs) */ struct cacheentry *cb_cache; /* free nodes for the cache */ struct hashentry *cb_hash; /* the hash table */ tceix cb_freelist; /* list of free cacheentries */ /* statistics variables, mostly for debugging */ u_int cb_lookups; /* # lookups */ u_int cb_hits; /* # hits */ u_int cb_tos; /* # timed out entries */ u_int cb_fulls; /* # removed, full table */ }; /* a single node in the hash table */ struct hashentry { tceix he_ix; }; #define NULL_PHE ((struct hashentry *) 0) #define NULL_IX 0 /* a cached item in the hash list */ enum ce_status {CE_INUSE=11, CE_FREE=12}; typedef enum ce_status ce_status; struct cacheentry { ce_status ce_status; /* INUSE or FREE */ char *ce_keyptr; /* pointer to the key */ tcelen ce_keylen; /* length of the key */ char *ce_resptr; /* pointer to the result */ tcelen ce_reslen; /* length of the result */ thval ce_hash; /* value that was hashed in */ ttstamp ce_tsinsert; /* timestamp - time inserted */ ttstamp ce_tsaccess; /* timestamp - last access */ tceix ce_prev; /* next entry on list */ tceix ce_next; /* prev entry on list */ }; #define NULL_PCE ((struct cacheentry *) 0) /* locally global information */ static struct cacheblk catab[CA_NUMCACHES]; /* useful macros */ #define ISBADCID(cid) ((cid < 0) || (cid > CA_NUMCACHES) || \ (catab[cid].cb_status != CB_INUSE)) #define HASHTOIX(hash,pcb) ((hash) % (pcb->cb_hashsize)) /* debugging hooks */ static int docadebug = 0; static int docaerror = 1; #define CADEBUG if (docadebug) fprintf #define CAERROR if (docaerror) fprintf /* local routines defns */ static char *cagetmem(u_int); static void cadeleteold(struct cacheblk *); static void caclear(struct cacheblk *, tceix); static void cafreemem(void *, u_int); static tceix cagetfree(struct cacheblk *); static tceix cagetindex(struct cacheblk *, char *, tcelen, thval); static thval cahash(char *, tcelen); static int caisold(struct cacheblk *, struct cacheentry *); static void casetsize(struct cacheblk *, int); static void caunlink(struct cacheblk *, tceix); /*************************************************************************/ /** **/ /** GLOBAL ROUTINES **/ /** **/ /*************************************************************************/ /* * ==================================================================== * cainit - initialize the caching tables * ==================================================================== */ int cainit(void) { struct cacheblk *pcb; int cid; for (cid=0; cid < CA_NUMCACHES; ++cid) { pcb = &catab[cid]; bzero(pcb,sizeof(struct cacheblk)); pcb->cb_status = CB_FREE; } ca_enabled = TRUE; return(OK); } /* * ==================================================================== * cacreate - create a new cache * ==================================================================== */ int cacreate( char *name, int nentries, int lifetime) { int cid; tceix ix; struct cacheblk *pcb; struct cacheentry *pce; /* check config limits */ if (nentries >= CA_MAXENTRIES) { CAERROR(stderr,"cacreate(%s,%d,%d): SYSERR, nentries > max (%d)\n", name, nentries, lifetime, CA_MAXENTRIES); return(SYSERR); } for (cid=0; cid < CA_NUMCACHES; ++cid) { pcb = &catab[cid]; if (pcb->cb_status == CB_FREE) break; } if (cid == CA_NUMCACHES) { CAERROR(stderr,"cacreate(%s,%d,%d): SYSERR, no more caches\n", name, nentries, lifetime); return(SYSERR); } bzero(pcb, sizeof(struct cacheblk)); pcb->cb_status = CB_INUSE; #ifdef linux #ifdef strncpy /* stupid Linux (redhat?) bug in macro */ #undef strncpy #endif /* strncpy */ #endif /* linux */ strncpy(pcb->cb_name,name,CA_NAMELEN); pcb->cb_name[CA_NAMELEN-1] = '\00'; pcb->cb_maxent = nentries; casetsize(pcb,nentries); pcb->cb_maxlife = lifetime; /* allocate the cache entries */ /* (0 is reserved as a null pointer, so we allocate from 0 */ /* to maxent, rather than maxent-1) */ pcb->cb_cache = (struct cacheentry *) cagetmem((1+pcb->cb_maxent) * sizeof(struct cacheentry)); bzero(pcb->cb_cache, (1+pcb->cb_maxent) * sizeof(struct cacheentry)); /* put them all on the free list (only forward pointers) */ for (ix=1; ix <= pcb->cb_maxent; ++ix) { pce = &pcb->cb_cache[ix]; pce->ce_status = CE_FREE; pce->ce_next = ix+1; } pcb->cb_cache[pcb->cb_maxent].ce_next = NULL_IX; pcb->cb_freelist = 1; /* allocate the hash table */ pcb->cb_hash = (struct hashentry *) cagetmem(pcb->cb_hashsize * sizeof(struct hashentry)); for (ix=0; ix < pcb->cb_hashsize; ++ix) { pcb->cb_hash[ix].he_ix = NULL_IX; } CADEBUG(stderr,"cacreate(%s,%d,%d) returns cache %d\n", name, nentries, lifetime, cid); return(cid); } /* * ==================================================================== * cadestroy - destroy an existing cache * ==================================================================== */ int cadestroy( int cid) { struct cacheblk *pcb; if (ISBADCID(cid)) { CAERROR(stderr,"cadestroy(%d,...) cid is bad\n", cid); return(SYSERR); } pcb = &catab[cid]; /* free up all the entries */ (void) capurge(cid); /* free up the hash table */ cafreemem(pcb->cb_hash, pcb->cb_hashsize * sizeof(struct hashentry)); /* free up the cached blocks */ cafreemem(pcb->cb_cache, (1+pcb->cb_maxent) * sizeof(struct cacheentry)); /* zero out the table */ bzero(pcb,sizeof(struct cacheblk)); pcb->cb_status = CB_FREE; return(OK); } /* * ==================================================================== * cainsert - insert a new entry into an existing cache * ==================================================================== */ int cainsert( int cid, char *pkey, tcelen keylen, char *pres, tcelen reslen) { struct cacheblk *pcb; struct cacheentry *pce; struct hashentry *phe; thval hash; tceix ixnew; /* check argument validity */ if (ISBADCID(cid)) { CAERROR(stderr,"cainsert(%d,...) cid is bad\n", cid); return(SYSERR); } if ((keylen > CA_MAXKEY) || (reslen > CA_MAXRES)) { CAERROR(stderr,"cainsert: SYSERR, key or result too large\n"); return(SYSERR); } if (!ca_enabled) return(OK); pcb = &catab[cid]; hash = cahash(pkey,keylen); phe = &pcb->cb_hash[HASHTOIX(hash,pcb)]; if ((ixnew = cagetindex(pcb,pkey,keylen,hash)) != NULL_IX) { /* use the old one */ caclear(pcb,ixnew); pce = &pcb->cb_cache[ixnew]; CADEBUG(stderr,"cainsert(%d): reusing cache slot %d, nument:%d\n", cid, ixnew, pcb->cb_nument); } else { /* get a free cacheentry */ ixnew = cagetfree(pcb); pce = &pcb->cb_cache[ixnew]; /* ... and put it at the head of the list */ pce->ce_prev = 0; pce->ce_next = phe->he_ix; pcb->cb_cache[phe->he_ix].ce_prev = ixnew; phe->he_ix = ixnew; CADEBUG(stderr,"cainsert(%d): using new cache slot %d, nument:%d\n", cid, ixnew, pcb->cb_nument); } pce->ce_status = CE_INUSE; pce->ce_hash = hash; pce->ce_keyptr = cagetmem(keylen); pce->ce_keylen = keylen; bcopy(pkey,pce->ce_keyptr,(int)keylen); pce->ce_resptr = cagetmem(reslen); pce->ce_reslen = reslen; bcopy(pres,pce->ce_resptr,(int)reslen); time(&pce->ce_tsinsert); pce->ce_tsaccess = pce->ce_tsinsert; return(OK); } /* * ==================================================================== * calookup - find an entry in the cache given the key, return info * ==================================================================== */ int calookup( int cid, char *pkey, tcelen keylen, char *pres, tcelen *preslen) { struct cacheblk *pcb; struct cacheentry *pce; thval hash; tceix ix; if (ISBADCID(cid)) { CAERROR(stderr,"calookup(%d,...) cid is bad\n", cid); return(SYSERR); } if (!ca_enabled) return(SYSERR); pcb = &catab[cid]; hash = cahash(pkey,keylen); if ((ix = cagetindex(pcb,pkey,keylen,hash)) != NULL_IX) { pce = &pcb->cb_cache[ix]; if (pce->ce_reslen <= *preslen) { time(&pce->ce_tsaccess); bcopy(pce->ce_resptr,pres,(int)pce->ce_reslen); *preslen = pce->ce_reslen; return(OK); } } return(SYSERR); } /* * ==================================================================== * caremove - remove an entry from the cache if it exists * ==================================================================== */ int caremove( int cid, char *pkey, tcelen keylen) { struct cacheblk *pcb; unsigned hash; tceix ix; if (ISBADCID(cid)) { CAERROR(stderr,"caremove(%d,...) cid is bad\n", cid); return(SYSERR); } pcb = &catab[cid]; hash = cahash(pkey,keylen); if ((ix = cagetindex(pcb,pkey,keylen,hash)) != NULL_IX) { CADEBUG(stderr,"caremove(%d): killing entry in slot %d:\n", cid, ix); caunlink(pcb,ix); } return(OK); } /* * ==================================================================== * capurge - remove all entries in an existing cache * ==================================================================== */ int capurge( int cid) { struct cacheblk *pcb; struct cacheentry *pce; struct hashentry *phe; tceix ix; if (ISBADCID(cid)) { CAERROR(stderr,"capurge(%d,...) cid is bad\n", cid); return(SYSERR); } pcb = &catab[cid]; /* free all cached entries */ for (ix=1; ix <= pcb->cb_maxent; ++ix) { pce = &pcb->cb_cache[ix]; if (pce->ce_status == CE_INUSE) caunlink(pcb,ix); pce->ce_status = CE_FREE; } /* clear the hash table */ for (ix=0; ix < pcb->cb_hashsize; ++ix) { phe = &pcb->cb_hash[ix]; bzero(phe,sizeof(struct hashentry)); phe->he_ix = NULL_IX; } pcb->cb_nument = 0; return(OK); } /* * ==================================================================== * cadump - dump contents of the cache structures * ==================================================================== */ void cadump(void) { int cid; int purge; int zero; struct cacheblk *pcb; purge = zero = FALSE; fprintf(stderr,"\nmaxcaches: %d (caching %sabled)\n", CA_NUMCACHES, ca_enabled?"en":"DIS"); fprintf(stderr,"\ ix name maxent nument htsize life tos full finds hits hit%%\n"); fprintf(stderr,"\ == =============== ====== ====== ====== ==== ==== ==== ====== ====== ====\n"); for (cid=0; cid < CA_NUMCACHES; ++cid) { pcb = &catab[cid]; if (pcb->cb_status == CB_FREE) continue; if (purge) capurge(cid); if (zero) { pcb->cb_tos = 0; pcb->cb_fulls = 0; pcb->cb_lookups = 0; pcb->cb_hits = 0; } fprintf(stderr,"%2d %-15s %6d %6d %6d %4d %4d %4d %6d %6d %3d%%", cid, pcb->cb_name, pcb->cb_maxent, pcb->cb_nument, pcb->cb_hashsize, pcb->cb_maxlife, pcb->cb_tos, pcb->cb_fulls, pcb->cb_lookups, pcb->cb_hits, (pcb->cb_lookups)? ((100 * pcb->cb_hits) / pcb->cb_lookups):0); fprintf(stderr,"\n"); } } /*************************************************************************/ /** **/ /** LOCAL FUNCTIONS **/ /** **/ /*************************************************************************/ /* * ==================================================================== * cahash - return the hash value for a key * ==================================================================== */ static thval cahash( char *pkey, tcelen keylen) { int i; thval hval; hval = 0; for (i=0; i < keylen; ++i) hval += *pkey++; return(hval); } /* try to reduce fragmentation */ #define CAMEMSIZE(nb) ((unsigned) (((nb) + 31) & ~31)) /* * ==================================================================== * cagetmem - get memory for a cached entry * ==================================================================== */ static char * cagetmem( u_int nbytes) { char *ret; ret = malloc(CAMEMSIZE(nbytes)); if (!ret) { perror("cagetmem malloc"); exit(-1); } return(ret); } /* * ==================================================================== * cafreemem - free memory from a cached entry * ==================================================================== */ static void cafreemem( void *ptr, u_int nbytes) { free(ptr); } /* * ==================================================================== * cadeleteold - delete the "oldest" cached entry * ==================================================================== */ static void cadeleteold( struct cacheblk *pcb) { struct cacheentry *pce; unsigned oldtime; tceix oldix; tceix ix; /* check everyone against the first entry */ oldix = 1; pce = &pcb->cb_cache[oldix]; oldtime = pce->ce_tsaccess; for (ix=2; ix <= pcb->cb_maxent; ++ix) { pce = &pcb->cb_cache[ix]; if ((pce->ce_status == CE_INUSE) && (pce->ce_tsaccess < oldtime)) { oldix = ix; oldtime = pce->ce_tsaccess; } } /* nuke the oldest one */ pce = &pcb->cb_cache[oldix]; caunlink(pcb,oldix); return; } /* * ==================================================================== * caclear - clear out the given entry, set status to FREE * ==================================================================== */ static void caclear( struct cacheblk *pcb, tceix ix) { struct cacheentry *pce; pce = &pcb->cb_cache[ix]; if (pce->ce_keyptr) cafreemem(pce->ce_keyptr,pce->ce_keylen); if (pce->ce_resptr) cafreemem(pce->ce_resptr,pce->ce_reslen); bzero(pce,sizeof(struct cacheentry)); pce->ce_status = CE_FREE; } /* * ==================================================================== * caisold - return TRUE if the given entry is "too old" * ==================================================================== */ static int caisold( struct cacheblk *pcb, struct cacheentry *pce) { time_t now; if (pcb->cb_maxlife == 0) return(FALSE); time(&now); return ((now - pce->ce_tsaccess) > pcb->cb_maxlife); } /* * ==================================================================== * cagetindex - return the index of a matching entry, or SYSERR * ==================================================================== */ static tceix cagetindex( struct cacheblk *pcb, char *pkey, tcelen keylen, thval hashval) { struct cacheentry *pce; tceix ix; tceix nextix; ++pcb->cb_lookups; ix = pcb->cb_hash[HASHTOIX(hashval,pcb)].he_ix; while (ix != NULL_IX) { pce = &pcb->cb_cache[ix]; nextix = pce->ce_next; CADEBUG(stderr,"cagetindex[%d]: ", ix); if ((pce->ce_hash == hashval) && (pce->ce_keylen == keylen) && (memcmp((void *)pkey,(void *)pce->ce_keyptr,(int) keylen) == 0)) { /* this is a match */ ++pcb->cb_hits; if (caisold(pcb,pce)) { ++pcb->cb_tos; CADEBUG(stderr,"OLD\n"); caunlink(pcb,ix); return(NULL_IX); } else { CADEBUG(stderr,"YES\n"); return(ix); } } CADEBUG(stderr,"NO (%d!=%d, %d!=%d)\n", pce->ce_hash, hashval, pce->ce_keylen, keylen); ix = nextix; } return(NULL_IX); } /* * ==================================================================== * casetsize - set the hash table size * ==================================================================== */ static void casetsize( struct cacheblk *pcb, int nentries) { if (nentries <= 10) pcb->cb_hashsize = 13; else if (nentries <= 25) pcb->cb_hashsize = 29; else if (nentries <= 50) pcb->cb_hashsize = 53; else if (nentries <= 100) pcb->cb_hashsize = 101; else if (nentries <= 200) pcb->cb_hashsize = 213; else /* pcb->cb_hashsize = nentries * 1.25;*/ /* avoid the floating point */ pcb->cb_hashsize = (nentries * 5) >> 2; /* 5 >> 2 == 5 / 4 == 1.25 */ return; } /* * ==================================================================== * cagetfree - return the index of an unused pce. If there aren't any * left, delete an old one and return it. * ==================================================================== */ static tceix cagetfree( struct cacheblk *pcb) { struct cacheentry *pce; tceix ix; /* if the free list is empty, delete the oldest entry */ if (pcb->cb_freelist == NULL_IX) { CADEBUG(stderr,"cagetfree: cache full, deleting old entry, nument:%d\n", pcb->cb_nument); cadeleteold(pcb); ++pcb->cb_fulls; } /* remove the head of the list */ ix = pcb->cb_freelist; pce = &pcb->cb_cache[ix]; pcb->cb_freelist = pce->ce_next; ++pcb->cb_nument; CADEBUG(stderr,"cagetfree: returning slot %d\n", ix); return(ix); } /* * ==================================================================== * caunlink - remove a cached entry from a list (and erase it) * return it to the free list * ==================================================================== */ static void caunlink( struct cacheblk *pcb, tceix ix) { struct cacheentry *pce; struct hashentry *phe; thval hash; pce = &pcb->cb_cache[ix]; hash = pce->ce_hash; phe = &pcb->cb_hash[HASHTOIX(hash,pcb)]; if (pce->ce_prev == NULL_IX) phe->he_ix = pce->ce_next; else pcb->cb_cache[pce->ce_prev].ce_next = pce->ce_next; pcb->cb_cache[pce->ce_next].ce_prev = pce->ce_prev; caclear(pcb,ix); /* return it to the free list */ pce->ce_next = pcb->cb_freelist; pcb->cb_freelist = ix; --pcb->cb_nument; }