path: root/usr/src/stand/lib/fs/common/cache.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 *  Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
 *  Use is subject to license terms.
 *
 *  This is mostly new code.  Major revisions were made to allow multiple
 *  file systems to share a common cache.  While this consisted primarily
 *  of including a "devid_t" pointer in the hash functions, I also re-
 *  organized everything to eliminate much of the duplicated code that
 *  had existed previously.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

#include <sys/param.h>
#include <sys/vnode.h>
#include <sys/sysmacros.h>
#include <sys/filep.h>
#include <sys/salib.h>
#include <sys/promif.h>

#ifndef	ICACHE_SIZE
/*
 *  These should probably be defined in an architecture-specific header
 *  file.  The values below are analogous to those used in earlier versions
 *  of this module.
 */

#define	ICACHE_SIZE 350	    /* Max number of I-node in file cache	*/
#define	DCACHE_SIZE 1500    /* Max number of cached directories		*/
#define	BCACHE_SIZE 250	    /* Max number of cached disk blocks		*/
#endif

#define	Next 0		    /* Next pointer in Fwd/Bak link		*/
#define	Prev 1		    /* Previous pointer in Fwd/Back links	*/

#define	Frst 0		    /* Ptr to first element of a chain		*/
#define	Last 1		    /* Ptr to last element of a chain		*/

#define	Hash 2		    /* Offset of hash chain ptrs.		*/

typedef struct cache {	    /* Generic cache element:			*/
    struct cache *link[4];  /* .. Fwd/Bak links for hash chain & LRU	*/
    struct cache **chn;	    /* .. Hash chain link			*/
    int		   dev;	    /* .. Device file handle			*/
    void	 *data;	    /* .. Ptr to associated data		*/
    int		  size;	    /* .. Size of cached data			*/
} cache_t;

typedef struct head {	    /* Generic cache header:			*/
	cache_t	   *aged[2];	/* .. LRU list				*/
	int (*cmp)(cache_t *);	/* .. Ptr to comparison function	*/
	int	  size;		/* .. Size of "cache" objects		*/
	int	  maxblks;	/* .. Max number of cached elements	*/
	int	  count;	/* .. Current number of cached elements	*/
	int	  hits;		/* .. Total cache hits			*/
	int	  searches;	/* .. Total searches			*/
	int	  purges;	/* .. Total purges			*/
} head_t;

/* Constructor for cache headers:					*/
#define	cache_head(h, f, t, n) \
	{{(cache_t *)&h, (cache_t *)&h}, f, sizeof (t), n}

int read_opt;		/* Number of times cache was bypassed	*/
static int x_dev;	/* Target device ID saved here!		*/
static int x_len;	/* length of object			*/

#define	LOG2(x) \
	(((x) <= 16)  ?	 4 : /* Yeah, it's ugly.  But it works! */ \
	(((x) <= 32)  ?  5 : /* .. Binary log should be part of */ \
	(((x) <= 64)  ?  6 : /* .. the language!		*/ \
	(((x) <= 128) ?	 7 : 8))))

static cache_t *
get_cache(cache_t *cap, head_t *chp)
{
	/*
	 *  Search cache:
	 *
	 *  The caller pass a pointer to the first "cache" object in the current
	 *  hash chain ["cap"] and a pointer to the corresponding cache header
	 *  ["chp"].  This routine follows the cache chain until it finds an
	 *  entry that matches both the current device [as noted in "x_dev"]
	 *  and the cache-specific comparison ["chp->cmp"].
	 *
	 *  Returns the address of the matching cache object or null if there
	 *  is none.
	 */

	while (cap) {
		/*
		 * Check all entries on the cache chain.  We expect
		 * chains to be relatively short, so we use a simple
		 * linear search.
		 */
		if ((x_dev == cap->dev) && (*chp->cmp)(cap)) {
			/*
			 * Found the entry we're looking for! Move it
			 * to the front of the cache header's LRU list
			 * before returing its addres to the caller.
			 */
			cap->link[Next]->link[Prev] = cap->link[Prev];
			cap->link[Prev]->link[Next] = cap->link[Next];

			cap->link[Prev] = (cache_t *)chp->aged;
			cap->link[Next] = chp->aged[Frst];
			chp->aged[Frst]->link[Prev] = cap;
			chp->aged[Frst] = cap;
			chp->hits += 1;
			break;
		}

		cap = cap->link[Hash+Next];
	}

	chp->searches += 1;
	return (cap);
}

static cache_t *
reclaim_cache(head_t *chp, int dev)
{
	/*
	 * Reclaim a cache element:
	 *
	 * This routine is used to: [a] free the oldest element from
	 * the cache headed at "chp" and return the address of the
	 * corresponding "cache_t" struct (iff dev == -1), or [b] free all
	 * elements on the cache headed at "chp" that belong to the
	 * indicated "dev"ice.
	 */
	cache_t *cap, *cxp;
	cache_t *cpp = (cache_t *)chp;

	while ((cap = cpp->link[Prev]) != (cache_t *)chp) {
		/*
		 * We follow the cache's LRU chain from oldest to
		 * newest member.  This ensures that we remove only
		 * the oldest element when we're called with a
		 * negative "dev" argument.
		 */
		if ((dev == -1) || (dev == cap->dev)) {
			/*
			 * This is one of the (perhaps the only)
			 * elements we're supposed to free.  Remove it
			 * from both the LRU list and its associated
			 * hash chain.  Then free the data bound the
			 * the cache_t element and, if "dev" is
			 * not -1, the element itself!
			 */
			cap->link[Prev]->link[Next] = cap->link[Next];
			cap->link[Next]->link[Prev] = cap->link[Prev];

			if ((cxp = cap->link[Hash+Prev]) != 0)
				cxp->link[Hash+Next] = cap->link[Hash+Next];
			else
				*(cap->chn) = cap->link[Hash+Next];

			if ((cxp = cap->link[Hash+Next]) != 0)
				cxp->link[Hash+Prev] = cap->link[Hash+Prev];

			bkmem_free((caddr_t)cap->data, cap->size);
			if (dev == -1)
				return (cap);

			bkmem_free((caddr_t)cap, chp->size);
			chp->count -= 1;

		} else {
			/*
			 * Skip this element, it's not one of the
			 * ones we want to free up.
			 */
			cpp = cap;
		}
	};

	return (0);
}

static cache_t *
set_cache(cache_t **ccp, head_t *chp, int noreclaim)
{
	/*
	 *  Install a cache element:
	 *
	 *  The caller passes the address of cache descriptor ["chp"] and the
	 *  hash chain into which the new element is to be linked ["ccp"].  This
	 *  routine allocates a new cache_t structure (or, if the maximum number
	 *  of elements has already been allocated, reclaims the oldest element
	 *  from the cache), links it into the indicated hash chain, and returns
	 *  its address to the caller.
	 */
	cache_t *cap;

	if ((chp->count < chp->maxblks) &&
	    (cap = (cache_t *)bkmem_alloc(chp->size))) {
		/*
		 * We haven't reached the maximum cache size yet.
		 * Allocate a new "cache_t" struct to be added to the
		 * cache.
		 */
		chp->count += 1;

	} else {
		if (noreclaim)
			return (NULL);

		/*
		 * Cache is full.  Use the "reclaim_cache" routine to
		 * remove the oldest element from the cache.  This
		 * will become the cache_t struct associated with the
		 * new element.
		 */
		cap = reclaim_cache(chp, -1);
		chp->purges += 1;
	}

	bzero((char *)cap, chp->size);

	cap->chn = ccp;
	cap->link[Prev] = (cache_t *)chp;
	cap->link[Next] = chp->aged[Frst];
	cap->link[Prev]->link[Next] = cap->link[Next]->link[Prev] = cap;

	if ((cap->link[Hash+Next] = *ccp) != 0)
		(*ccp)->link[Hash+Prev] = cap;
	return (*ccp = cap);
}

/*
 *  The File Cache:
 *
 *  This cache (also known as the inode cache) is used to keep track of all
 *  files open on a given device.  The only special data required to locate
 *  a cache entry is the file reference number which is file-system dependent
 *  (for UNIX file systems, it's an inode number).
 */

typedef struct icache {		/* Inode cache element:		*/
	cache_t ic_hdr;		/* .. Standard header		*/
	int	ic_num;		/* .. I-node number		*/
} ic_t;

#define	IC_MAX_HDRS (1 << LOG2(ICACHE_SIZE/6))
#define	IC_HASH(d, i) (((d) + (i)) & (IC_MAX_HDRS - 1))

static int x_inode;

static int		    /* Cache search predicate:			    */
cmp_icache(cache_t *p)
{
	/* Just check the file number ("x_inode") ...	*/
	return (((ic_t *)p)->ic_num == x_inode);
}

static head_t	ic_head = cache_head(ic_head, cmp_icache, ic_t, ICACHE_SIZE);
static cache_t *ic_hash[IC_MAX_HDRS];

void *
get_icache(int dev, int inum)
{
	/*
	 *  Search File Cache:
	 *
	 *  This routine searches the file cache looking for the entry bound to
	 *  the given "dev"ice and file number ["inum"].  If said entry exists,
	 *  it returns the address of the associated file structure.  Otherwise
	 *  it returns null.
	 */
	cache_t *icp;

	x_dev = dev;
	x_inode = inum;
	icp = get_cache(ic_hash[IC_HASH(dev, inum)], &ic_head);

	return (icp ? (caddr_t)icp->data : 0);
}

void
set_icache(int dev, int inum, void *ip, int size)
{
	/*
	 *  Build a File Cache Entry:
	 *
	 * This routne installs the "size"-byte file structure at
	 * "*ip" in the inode cache where it may be retrieved by
	 * subsequent call to get_icache.
	 */
	ic_t *icp = (ic_t *)set_cache(&ic_hash[IC_HASH(dev, inum)],
								&ic_head, 0);
	icp->ic_num = inum;
	icp->ic_hdr.data = ip;
	icp->ic_hdr.dev = dev;
	icp->ic_hdr.size = size;
}

int
set_ricache(int dev, int inum, void *ip, int size)
{
	/*
	 * Reliably set the icache
	 *
	 * This routine is the same as set_icache except that it
	 * will return 1 if the entry could not be entered into the cache
	 * without a purge.
	 */
	ic_t *icp = (ic_t *)set_cache(&ic_hash[IC_HASH(dev, inum)],
					&ic_head, 1);

	if (icp == NULL)
		return (1);

	icp->ic_num = inum;
	icp->ic_hdr.data = ip;
	icp->ic_hdr.dev = dev;
	icp->ic_hdr.size = size;

	return (0);
}

/*
 *  The Directory Cache:
 *
 *  This cache is designed to speed directory searches.	 Each entry cor-
 *  responds to a directory entry that was used in a pathname resolution.
 *  The idea is that most files used by the boot wil be contained in a hand-
 *  full of directories, so we can speed searches if we know ahead of time
 *  just where these directories are.
 */

typedef struct dcache {		/* Directory cache objects:	*/
	cache_t dc_hdr;		/* .. Standard header		*/
	int	dc_inum;	/* .. File number		*/
	int	dc_pnum;	/* .. Parent diretory's file number */
} dc_t;

#define	DC_MAX_HDRS (1 << LOG2(DCACHE_SIZE/6))
#define	DC_HASH(d, n, l) (((d) + (n)[0] + (n)[(l)-1] + (l)) & (DC_MAX_HDRS-1))

static char *x_name;
static int x_pnum;

static int
cmp_dcache(cache_t *p) /* Cache Search predicate:	*/
{
	/* Check name, length, and parent's file number	*/
	return ((x_len == p->size) && (x_pnum == ((dc_t *)p)->dc_pnum) &&
	    (strcmp((char *)p->data, x_name) == 0));
}

static head_t	dc_head = cache_head(dc_head, cmp_dcache, dc_t, DCACHE_SIZE);
static cache_t *dc_hash[DC_MAX_HDRS];

int
get_dcache(int dev, char *name, int pnum)
{
	/*
	 *  Search Directory Cache:
	 *
	 *  This routine searches the directory cache for an entry
	 *  associated with directory number "pnum" from the given
	 *  file system that de-scribes a file of the given "name".
	 *  If we find such an entry, we return the corresponding file
	 *  number, 0 otherwise.
	 */
	dc_t *dcp;

	x_dev = dev;
	x_len = strlen(name)+1;
	x_pnum = pnum;
	x_name = name;
	dcp = (dc_t *)get_cache(dc_hash[DC_HASH(dev, name, x_len)], &dc_head);

	return (dcp ? dcp->dc_inum : 0);
}

void
set_dcache(int dev, char *name, int pnum, int inum)
{
	/*
	 *  Build Directory Cache Entry:
	 *
	 *  This routine creates directory cache entries to be retrieved later
	 *  via "get_dcache".  The cache key is composed of three parts: The
	 *  device specifier, the file name ("name"), and the file number of
	 *  the directory containing that name ("pnum").  The data portion of
	 *  the entry consists of the file number ("inum").
	 */

	int len = strlen(name)+1;
	dc_t *dcp =
	    (dc_t *)set_cache(&dc_hash[DC_HASH(dev, name, len)], &dc_head, 0);

	if (dcp->dc_hdr.data = (void *)bkmem_alloc(len)) {
		/*
		 * Allocate a buffer for the pathname component, and
		 * make this the "data" portion of the generalize
		 * "cache_t" struct. Also fill in the cache-specific
		 * fields (pnum, inum).
		 */
		dcp->dc_pnum = pnum;
		dcp->dc_inum = inum;
		dcp->dc_hdr.dev = dev;
		dcp->dc_hdr.size = len;
		bcopy(name, (char *)dcp->dc_hdr.data, len);

	} else {
		/*
		 * Not enough memory to make a copy of the name!
		 * There's probably not enough to do much else either!
		 */
		prom_panic("no memory for directory cache");
	}
}

int
set_rdcache(int dev, char *name, int pnum, int inum)
{
	/*
	 * Reliably set the dcache
	 *
	 * This routine is the same as set_dcache except that it
	 * return 1 if the entry could not be entered into
	 * the cache without a purge.
	 */
	int len = strlen(name) + 1;
	dc_t *dcp =
		(dc_t *)set_cache(&dc_hash[DC_HASH(dev, name, len)],
								&dc_head, 1);

	if (dcp == NULL)
		return (1);

	if ((dcp->dc_hdr.data = (void *)bkmem_alloc(len)) == NULL) {
		/*
		 * Not enough memory to make a copy of the name!
		 * There's probably not enough to do much else either!
		 */
		prom_panic("no memory for directory cache");
		/* NOTREACHED */
	}

	/*
	 * Allocate a buffer for the pathname component, and
	 * make this the "data" portion of the generalize
	 * "cache_t" struct. Also fill in the cache-specific
	 * fields (pnum, inum).
	 */
	dcp->dc_pnum = pnum;
	dcp->dc_inum = inum;
	dcp->dc_hdr.dev = dev;
	dcp->dc_hdr.size = len;
	bcopy(name, (char *)dcp->dc_hdr.data, len);

	return (0);
}

/*
 *  Disk Block Cache:
 */

typedef struct bcache {	    /* Disk block cache objects:		*/
	cache_t		bc_hdr;	/* .. Standard header			*/
	unsigned long	bc_blk;	/* .. The block number			*/
} bc_t;

#define	BC_MAX_HDRS (1 << LOG2(BCACHE_SIZE/6))
#define	BC_HASH(d, b, l) (((d) + (b) + ((l) >> 8)) & (BC_MAX_HDRS-1))

static unsigned long x_blkno;

static int
cmp_bcache(cache_t *p) /* Cache Search predicate:		*/
{
	/* Check block number, buffer size	*/
	return ((x_len == p->size) && (x_blkno == ((bc_t *)p)->bc_blk));
}

static head_t	bc_head = cache_head(bc_head, cmp_bcache, bc_t, BCACHE_SIZE);
static cache_t *bc_hash[BC_MAX_HDRS];

caddr_t
get_bcache(fileid_t *fp)
{
	/*
	 *  Search Disk Block Cache:
	 *
	 *  This should be getting pretty monotonous by now.  Aren't generalized
	 *  subroutines ("objects", if you prefer) great?
	 */
	cache_t *bcp;

	x_len = fp->fi_count;
	x_blkno = fp->fi_blocknum;
	x_dev = fp->fi_devp->di_dcookie;
	bcp = get_cache(bc_hash[BC_HASH(x_dev, x_blkno, x_len)], &bc_head);

	return (bcp ? (caddr_t)bcp->data : 0);
}

int
set_bcache(fileid_t *fp)
{
	/*
	 *  Insert Disk Block Cache Entry:
	 *
	 *  In this case, we actually read the requested block into a
	 *  dynamically allocated buffer before inserting it into the
	 *  cache.  If the read fails, we return a non-zero value.
	 *
	 *  The search keys for disk blocks are the block number and
	 *  buffer size.  The data associated with each entry is the
	 *  corresponding data buffer.
	 */
	bc_t *bcp;

	if (fp->fi_memp = bkmem_alloc(x_len = fp->fi_count)) {
		/*
		 *  We were able to succesffully allocate an input
		 *  buffer, now read the data into it.
		 */
		if (diskread(fp) != 0) {
			/*
			 * I/O error on read. Free the input buffer,
			 * print an error message, and bail out.
			 */
			bkmem_free(fp->fi_memp, x_len);
			printf("disk read error\n");
			return (-1);
		}

		x_blkno = fp->fi_blocknum;
		x_dev = fp->fi_devp->di_dcookie;
		bcp = (bc_t *)
			set_cache(&bc_hash[BC_HASH(x_dev, x_blkno, x_len)],
								&bc_head, 0);
		bcp->bc_blk = x_blkno;
		bcp->bc_hdr.dev = x_dev;
		bcp->bc_hdr.size = x_len;
		bcp->bc_hdr.data = (void *)fp->fi_memp;

	} else {
		/*
		 * We could be a bit more convervative here by
		 * calling "set_cache" before we try to allocate a
		 * buffer (thereby giving us a chance to re-use a
		 * previously allocated buffer) but the error recovery
		 * is a bit trickier, and if we're that short on memory
		 * we'll have trouble elsewhere anyway!
		 */
		prom_panic("can't read - no memory");
	}

	return (0);
}

void
release_cache(int dev)
{
	/*
	 *  Reclaim all cache entries:
	 *
	 *  This routine is called by the file-system's "closeall" method.  It
	 *  removes all cache entries associated with that file system from the
	 *  global cache and release any resources bound to said entrires.
	 */

	(void) reclaim_cache(&ic_head, dev);
	(void) reclaim_cache(&dc_head, dev);
	(void) reclaim_cache(&bc_head, dev);
}

void
print_cache_data()
{
	/*
	 *  Print some cacheing statistics ...
	 */
	static char	*tag[] = { "inode", "directory", "disk block", 0};
	static head_t	*hdp[] = { &ic_head, &dc_head, &bc_head, 0};

	int j;

	for (j = 0; tag[j]; j++) {
		/*
		 * Print statistics maintained in the header
		 * ("head_t" struct) of each of the above caches.
		 */
		head_t *hp = hdp[j];

		if (j)
			printf("\n");
		printf("%s cache:\n", tag[j]);
		printf("   max size %d\n", hp->maxblks);
		printf("   actual size %d\n", hp->count);
		printf("   total searches %d\n", hp->searches);
		printf("   cache hits %d\n", hp->hits);
		printf("   cache purges %d\n", hp->purges);
	}

	printf("\nread opts %d\n", read_opt);
}