OpenSolaris_b135/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);
}