8322 nl: misleading-indentation

[unleashed/tickless.git] / 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);
}