gcache.c

/*
 * 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 <sys/types.h>
#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;
}