cmd/keyserv/keyserv_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 1997 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

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

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <thread.h>
#include <synch.h>
#include <stdlib.h>
#include <syslog.h>
#include <rpc/des_crypt.h>

#include "keyserv_cache.h"

struct cachekey {
    struct cachekey_header  *ch;
    keylen_t        keylen;
    algtype_t       algtype;
    mutex_t         mp;
    struct cachekey     *next;
};

static struct cachekey      *cache = 0;
static mutex_t          cache_lock = DEFAULTMUTEX;
static cond_t           cache_cv = DEFAULTCV;
static u_long           cache_refcnt = 0;

struct skck {
    des_block   common[3];
    des_block   verifier;   /* Checksum */
    struct dhkey    secret;
};

struct cachekey_disklist {
    uid_t               uid;
    struct cachekey_disklist    *prev;      /* LRU order */
    struct cachekey_disklist    *next;
    struct cachekey_disklist    *prevhash;  /* Hash chain */
    struct cachekey_disklist    *nexthash;
    struct dhkey            public;
    /*
     * Storage for encrypted skck structure here. The length will be
     * 8 * ( ( ( sizeof(struct skck) - 1 + secret.length ) - 1 ) / 8 + 1 )
     */
};

/* Length of skck structure for given key length (in bits) */
#define SKCK_LEN(keylen)    ALIGN8(sizeof (struct skck) + KEYLEN(keylen))
/* Length of a cachekey_disklist record for given key length (in bits) */
#define CACHEKEY_RECLEN(keylen) ALIGN8(sizeof (struct cachekey_disklist) - 1 + \
                    KEYLEN(keylen) + SKCK_LEN(keylen))
#define NUMHASHBUCKETS  253
#define CHUNK_NUMREC    64

#define CACHEKEY_HEADER_VERSION 0

struct cachekey_header {        /* First in each key cache file */
    u_int       version;    /* version number of interface */
    u_int       headerlength;   /* size of this header */
    keylen_t    keylen;     /* in bits */
    algtype_t   algtype;    /* algorithm type */
    size_t      reclength;  /* cache file record size in bytes */
    int     fd;     /* file descriptor */
    caddr_t     address;    /* mmap()ed here */
    size_t      length;     /* bytes mapped */
    size_t      maxsize;    /* don't grow beyond this */
    u_int       inuse_count;
    struct cachekey_disklist    *inuse; /* LRU order */
    struct cachekey_disklist    *inuse_end;
    u_int               free_count;
    struct cachekey_disklist    *free;
    struct cachekey_disklist    *bucket[NUMHASHBUCKETS];
    struct cachekey_disklist    array[1];   /* Start of array */
};


static struct cachekey_header   *create_cache_file_ch(keylen_t keylen,
                            algtype_t algtype,
                            int sizespec);

static struct cachekey_header   *remap_cache_file_ch(struct cachekey_header *ch,
                        u_int newrecs);

static struct cachekey_header   *cache_insert_ch(struct cachekey_header *ch,
                        uid_t uid, deskeyarray common,
                        des_block key,
                        keybuf3 *public,
                        keybuf3 *secret);

static struct cachekey3_list    *cache_retrieve_ch(struct cachekey_header *ch,
                        uid_t uid,
                        keybuf3 *public,
                        des_block key);

static int          cache_remove_ch(struct cachekey_header *ch,
                        uid_t uid,
                        keybuf3 *public);

static struct cachekey      *get_cache_header(keylen_t keylen,
                            algtype_t algtype);

static void         release_cache_header(struct cachekey *);

static int          cache_remap_addresses_ch(
                    struct cachekey_header *);

static struct cachekey_disklist *find_cache_item(struct cachekey_header **,
                        uid_t, struct dhkey *);

static struct dhkey     *keybuf3_2_dhkey(keybuf3 *);

static u_int            hashval(uid_t);

static void         list_remove(struct cachekey_disklist *,
                        struct cachekey_disklist **,
                        struct cachekey_disklist **,
                        u_int *);

static void         list_remove_hash(struct cachekey_disklist *,
                        struct cachekey_disklist **,
                        struct cachekey_disklist **,
                        u_int *);

static void         list_insert(struct cachekey_disklist *,
                        struct cachekey_disklist **,
                        struct cachekey_disklist **,
                        u_int *);

static void         list_insert_hash(struct cachekey_disklist *,
                        struct cachekey_disklist **,
                        struct cachekey_disklist **,
                        u_int *);

static struct cachekey3_list *  copy_cl_item(struct cachekey_header *ch,
                        struct cachekey_disklist *cd,
                        des_block key);

extern int          hex2bin(u_char *, u_char *, int);
extern int          bin2hex(u_char *, u_char *, int);

/*
 * The folowing set of macros implement address validity checking. A valid
 * address is defined to be either 0, or to fall on a record boundary. In
 * the latter case, the the difference between the address and the start of
 * the record array is divisible by the record length.
 */
#define FILEOFFSET(ckh)         ((u_long)(ckh) - \
                    (u_long)((ckh)->address))
#define ADJUSTEDADDR(addr, ckh)     ((u_long)(addr) + FILEOFFSET(ckh))
#define ARRAYOFFSET(addr, ckh)      (ADJUSTEDADDR(addr, ckh) - \
                    (u_long)&((ckh)->array[0]))
#define INVALID_ADDRESS(addr, ckh)  ((addr == 0) ? 0 : \
            (ARRAYOFFSET(addr, ckh) % (ckh)->reclength) != 0)

/* Add offset to old address */
#define MOVE_ADDR(old, offset)  ((old) == 0) ? 0 : \
                (void *)((u_long)(old) + (offset))

/* Number of records in use or on free list */
#define NUMRECS(ck_header)  ((ck_header)->inuse_count + \
                (ck_header)->free_count)

/* Max number of records the mapped file could hold */
#define MAPRECS(ck_header)  (((ck_header)->length - \
                sizeof (struct cachekey_header)) / \
                (ck_header)->reclength)
/* Max number of records the file will hold if extended to the maxsize */
#define MAXRECS(ck_header)  (((ck_header)->maxsize - \
                sizeof (struct cachekey_header)) / \
                (ck_header)->reclength)


struct cachekey_header *
create_cache_file_ch(keylen_t keylen, algtype_t algtype, int sizespec)
{
    char                filename[MAXPATHLEN];
    struct cachekey_header      *ch;
    int             fd, newfile = 0, i, checkvalid = 1;
    struct stat         statbuf;
    size_t              reclength, length;
    struct cachekey_header      *oldbase = 0;
    struct cachekey_disklist    *cd;
    size_t maxsize;

    /* Construct cache file name */
    if (snprintf(filename, sizeof (filename), "/var/nis/.keyserv_%d-%d",
            keylen, algtype) > sizeof (filename)) {
        syslog(LOG_WARNING,
        "error constructing file name for mech %d-%d", keylen, algtype);
        return (0);
    }

    /* Open/create the file */
    if ((fd = open(filename, O_RDWR|O_CREAT, 0600)) < 0) {
        syslog(LOG_WARNING, "cache file open error for mech %d-%d: %m",
            keylen, algtype);
        return (0);
    }

    /* We want exclusive use of the file */
    if (lockf(fd, F_LOCK, 0) < 0) {
        syslog(LOG_WARNING, "cache file lock error for mech %d-%d: %m",
            keylen, algtype);
        close(fd);
        return (0);
    }

    /* Zero size means a new file */
    if (fstat(fd, &statbuf) < 0) {
        syslog(LOG_WARNING, "cache file fstat error for mech %d-%d: %m",
            keylen, algtype);
        close(fd);
        return (0);
    }

    reclength = CACHEKEY_RECLEN(keylen);
    if (sizespec < 0) {
        /* specifies the number of records in file */
        maxsize = ALIGN8(sizeof (struct cachekey_header)) +
            -sizespec*reclength;
    } else {
        /* specifies size of file in MB */
        maxsize = sizespec*1024*1024;
    }
    length    = ALIGN8(sizeof (struct cachekey_header)) +
            reclength*CHUNK_NUMREC;
    if (length > maxsize) {
        /*
         * First record resides partly in the header, so the length
         * cannot be allowed to be less than header plus one record.
         */
        if (maxsize > ALIGN8(sizeof (struct cachekey_header)+reclength))
            length = maxsize;
        else {
            length  = ALIGN8(sizeof (struct cachekey_header)+
                    reclength);
            maxsize = length;
        }
    }

    if (statbuf.st_size == 0) {
        /* Extend the file if we just created it */
        if (ftruncate(fd, length) < 0) {
            syslog(LOG_WARNING,
                "cache file ftruncate error for mech %d-%d: %m",
                keylen, algtype);
            close(fd);
            return (0);
        }
        newfile = 1;
    } else {
        /*
         * Temporarily mmap the header, to sanity check and obtain
         * the address where it was mapped the last time.
         */
        if ((ch = (void *)mmap(0, sizeof (struct cachekey_header),
                PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) ==
            MAP_FAILED) {
            syslog(LOG_WARNING,
                "cache file mmap1 error for mech %d-%d: %m",
                keylen, algtype);
            close(fd);
            return (0);
        }
        if (ch->version != CACHEKEY_HEADER_VERSION ||
            ch->headerlength != sizeof (struct cachekey_header) ||
            ch->keylen != keylen ||
            ch->algtype != algtype ||
            ch->reclength != reclength ||
            ch->length < sizeof (struct cachekey_header) ||
            ch->maxsize < ch->length ||
            INVALID_ADDRESS(ch->inuse, ch) ||
            INVALID_ADDRESS(ch->free, ch)) {
            syslog(LOG_WARNING,
            "cache file consistency error for mech %d-%d",
                keylen, algtype);
            munmap((caddr_t)ch, sizeof (struct cachekey_header));
            close(fd);
            return (0);
        }
        oldbase = (void *)ch->address;
        length  = ch->length;
        if (munmap((caddr_t)ch, sizeof (struct cachekey_header)) < 0) {
            syslog(LOG_WARNING,
                "cache file munmap error for mech %d-%d: %m",
                keylen, algtype);
            close(fd);
            return (0);
        }
    }

    /* Map the file */
    if ((ch = (void *)mmap((caddr_t)oldbase, length,
        PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) == MAP_FAILED) {
        syslog(LOG_WARNING,
            "cache file mmap2 error for mech %d-%d: %m",
                keylen, algtype);
        close(fd);
        return (0);
    }

    ch->fd      = fd;
    ch->maxsize = maxsize;

    if (newfile) {
        ch->version     = CACHEKEY_HEADER_VERSION;
        ch->headerlength    = sizeof (struct cachekey_header);
        ch->keylen      = keylen;
        ch->algtype     = algtype;
        ch->reclength       = reclength;
        ch->length      = length;
        ch->address     = (caddr_t)ch;
        ch->inuse_count     = 0;
        ch->inuse       = 0;
        ch->inuse_end       = 0;
        ch->free        = 0;
        ch->free_count      = 0;
        for (i = 0; i < NUMHASHBUCKETS; i++) {
            ch->bucket[i] = 0;
        }

        cd = &(ch->array[0]);
        for (i = 0; i < MAPRECS(ch);
            i++, cd = MOVE_ADDR(cd, ch->reclength)) {
            cd->uid     = (uid_t)-1;
            cd->prev    = MOVE_ADDR(cd, -(ch->reclength));
            cd->next    = MOVE_ADDR(cd, +(ch->reclength));
            cd->prevhash    = 0;
            cd->nexthash    = 0;
        }
        /*
         * Last record next pointer, and first record prev pointer,
         * are both NULL.
         */
        cd      = MOVE_ADDR(cd, -(ch->reclength));
        cd->next    = 0;
        cd      = &(ch->array[0]);
        cd->prev    = 0;

        ch->free_count  = MAPRECS(ch);
        ch->free    = &(ch->array[0]);

        (void) msync((caddr_t)ch, ch->length, MS_SYNC);

    } else if (ch->length > maxsize) {
        /* File should shrink */
        if ((ch = remap_cache_file_ch(ch, MAXRECS(ch))) == 0) {
            return (0);
        }
        checkvalid = 0;
    }

    /*
     * cache_remap_addresses() also checks address consistency, so call
     * it even if the remap is a no-op. However, if we've called
     * remap_cache_file_ch(), it will have invoked cache_remap_addresses()
     * already, so we don't have to do that again.
     */
    if (checkvalid &&
        cache_remap_addresses_ch(ch) == 0) {
        syslog(LOG_WARNING, "cache file invalid for mech %d-%d",
            keylen, algtype);
        (void) munmap((caddr_t)ch, ch->length);
        close(fd);
        return (0);
    }

    (void) msync((caddr_t)ch, ch->length, MS_SYNC);

    return (ch);
}


static int
cache_remap_addresses_ch(struct cachekey_header *ch)
{
    int             i;
    u_long              offset;
    struct cachekey_disklist    *cd;

    offset = (u_long)ch - (u_long)ch->address;

    if (INVALID_ADDRESS(ch->inuse, ch) ||
        INVALID_ADDRESS(ch->inuse_end, ch) ||
        INVALID_ADDRESS(ch->free, ch)) {
        return (0);
    }

    ch->inuse   = MOVE_ADDR(ch->inuse, offset);
    ch->inuse_end   = MOVE_ADDR(ch->inuse_end, offset);
    ch->free    = MOVE_ADDR(ch->free, offset);

    cd = &(ch->array[0]);
    for (i = 0; i < NUMRECS(ch); i++) {
        if (INVALID_ADDRESS(cd->prev, ch) ||
            INVALID_ADDRESS(cd->next, ch) ||
            INVALID_ADDRESS(cd->prevhash, ch) ||
            INVALID_ADDRESS(cd->nexthash, ch)) {
            return (0);
        }
        cd->prev    = MOVE_ADDR(cd->prev, offset);
        cd->next    = MOVE_ADDR(cd->next, offset);
        cd->prevhash    = MOVE_ADDR(cd->prevhash, offset);
        cd->nexthash    = MOVE_ADDR(cd->nexthash, offset);
        cd = MOVE_ADDR(cd, ch->reclength);
    }

    for (i = 0; i < NUMHASHBUCKETS; i++) {
        if (INVALID_ADDRESS(ch->bucket[i], ch)) {
            return (0);
        }
        ch->bucket[i] = MOVE_ADDR(ch->bucket[i], offset);
    }

    /*
     * To prevent disaster if this function is invoked again, we
     * update ch->address, so that offset will be zero if we do
     * get called once more, and the mapped file hasn't moved.
     */
    ch->address = (caddr_t)ch;

    return (1);
}


/*
 * Remap cache file with space for 'newrecs' records. The mmap:ed address
 * may have to move; the new address is returned.
 */
static struct cachekey_header *
remap_cache_file_ch(struct cachekey_header *ch, u_int newrecs)
{
    size_t              newsize, oldsize;
    u_int               currecs;
    int             i, fd;
    struct cachekey_header      *newch;
    caddr_t             oldaddr;
    struct cachekey_disklist    *cd = 0;

    if (ch == 0)
        return (0);


    /*
     * Since the first record partly resides in the cachekey_header,
     * newrecs cannot be less than 1.
     */
    if (newrecs < 1)
        newrecs = 1;

    newsize = ALIGN8(sizeof (struct cachekey_header)) +
            (ch->reclength)*newrecs;
    currecs = NUMRECS(ch);

    if (newsize > ch->maxsize) {
        /* Would exceed maximum allowed */
        newsize = ch->maxsize;
    }

    /* Save stuff we need while the file is unmapped */
    oldsize = ch->length;
    oldaddr = (caddr_t)ch;
    fd  = ch->fd;

    if (newsize > ch->length) {
        /* Extending the file */
        cd = &(ch->array[0]);
    } else if (newsize == ch->length) {
        /* Already OK */
        return (ch);
    } else {
        size_t              tmpsize;
        struct cachekey_disklist    *fcd;
        /*
         * Shrink the file by removing records from the end.
         * First, we have to make sure the file contains valid
         * addresses.
         */
        if (cache_remap_addresses_ch(ch) == 0) {
            syslog(LOG_WARNING, "cache file invalid for mech %d-%d",
            ch->keylen, ch->algtype);
            close(ch->fd);
            munmap((caddr_t)ch, ch->length);
            return (0);
        }
        fcd = MOVE_ADDR(&(ch->array[0]),
                ch->reclength*(MAPRECS(ch)-1));
        tmpsize = (u_long)fcd - (u_long)ch + ch->reclength;
        while (tmpsize > newsize && fcd > &(ch->array[0])) {
            if (fcd->uid == (uid_t)-1) {
                list_remove(fcd, &(ch->free), 0,
                    &(ch->free_count));
            } else {
                list_remove_hash(fcd,
                    &(ch->bucket[hashval(fcd->uid)]), 0, 0);
                list_remove(fcd, &(ch->inuse), &(ch->inuse_end),
                        &(ch->inuse_count));
            }
            tmpsize -= ch->reclength;
            fcd = MOVE_ADDR(fcd, -(ch->reclength));
        }
        ch->length = newsize;
        (void) msync((caddr_t)ch, ch->length, MS_SYNC);
    }

    /* Unmap the file */
    if (munmap((caddr_t)oldaddr, oldsize) < 0) {
        return (0);
    }
    ch = 0;

    /* Truncate/extend it */
    if (ftruncate(fd, newsize) < 0) {
        return (0);
    }

    /* Map it again */
    if ((newch = (void *)mmap(oldaddr, newsize,
            PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) ==
    MAP_FAILED) {
        return (0);
    }

    /* Update with new values */
    newch->length   = newsize;

    if (cache_remap_addresses_ch(newch) == 0) {
        syslog(LOG_WARNING, "cache file invalid for mech %d-%d",
            newch->keylen, newch->algtype);
        newch->length = oldsize;
        close(newch->fd);
        munmap((caddr_t)newch, newsize);
        return (0);
    }

    /* If extending the file, add new records to the free list */
    if (cd != 0) {
        cd = MOVE_ADDR(&(newch->array[0]), currecs*newch->reclength);
        for (i = currecs; i < MAPRECS(newch); i++) {
            cd->uid     = (uid_t)-1;
            list_insert(cd, &(newch->free), 0,
                    &(newch->free_count));
            cd      = MOVE_ADDR(cd, newch->reclength);
        }
    }

    (void) msync(newch->address, newch->length, MS_SYNC);

    return (newch);
}


#ifdef DEBUG
void
print_cache_ch(struct cachekey_header *ch)
{
    int             i, inuse, inuse_err, free, free_err;
    int             pb;
    struct cachekey_disklist    *cd;

    printf(
"\nkeylen = %d, algtype = %d, version = %d, headerlen = %d, reclen = %d\n",
        ch->keylen, ch->algtype, ch->version, ch->headerlength,
        ch->reclength);
    printf("fd = %d, address = 0x%x, mapped length = %d, maxsize = %d\n",
        ch->fd, ch->address, ch->length, ch->maxsize);
    printf("inuse = %d, free = %d\n", ch->inuse_count, ch->free_count);

    printf("Active hash buckets:\n");

    for (i = 0, inuse = 0, inuse_err = 0; i < NUMHASHBUCKETS; i++) {
        cd = ch->bucket[i];
        pb = -1;
        if (cd != 0) {
            pb = 0;
            printf("\t%d: ", i);
        }
        while (cd != 0) {
            pb++;
            printf("%d ", cd->uid);
            if (cd->uid != (uid_t)-1) {
                inuse++;
            } else {
                inuse_err++;
            }
            cd = cd->nexthash;
        }
        if (pb >= 0)
            printf(" (%d)\n", pb);
    }

    printf("\ncounted hash inuse = %d, errors = %d\n", inuse, inuse_err);

    cd = ch->inuse;
    inuse = inuse_err = 0;
    while (cd != 0) {
        if (cd->uid != (uid_t)-1) {
            inuse++;
        } else {
            inuse_err++;
        }
        cd = cd->next;
    }
    printf("counted LRU  inuse = %d, errors = %d\n", inuse, inuse_err);

    cd = ch->free;
    free = free_err = 0;
    while (cd != 0) {
        if (cd->uid == (uid_t)-1) {
            free++;
        } else {
            free_err++;
            fprintf(stderr, "free = %d, err = %d, cd->uid = %d\n",
                free, free_err, cd->uid);
        }
        cd = cd->next;
    }
    printf("counted      free = %d, errors = %d\n", free, free_err);
}

void
print_cache(keylen_t keylen, algtype_t algtype)
{
    struct cachekey *c;

    if ((c = get_cache_header(keylen, algtype)) == 0)
        return;

    if (c->ch == 0) {
        release_cache_header(c);
        return;
    }

    print_cache_ch(c->ch);

    release_cache_header(c);
}
#endif


static u_int
hashval(uid_t uid)
{
    return (uid % NUMHASHBUCKETS);
}


static void
list_remove(
    struct cachekey_disklist *item,
    struct cachekey_disklist **head,
    struct cachekey_disklist **tail,
    u_int *count)
{
    if (item == NULL) return;

    /* Handle previous item, if any */
    if (item->prev == 0)
        *head = item->next;
    else
        item->prev->next = item->next;

    /* Take care of the next item, if any */
    if (item->next != 0)
        item->next->prev = item->prev;

    /* Handle tail pointer, if supplied */
    if (tail != 0 && *tail == item)
        *tail = item->prev;

    item->prev = item->next = 0;
    if (count != 0)
        (*count)--;
}


static void
list_remove_hash(
    struct cachekey_disklist *item,
    struct cachekey_disklist **head,
    struct cachekey_disklist **tail,
    u_int *count)
{
    if (item == NULL) return;

    /* Handle previous item, if any */
    if (item->prevhash == 0)
        *head = item->nexthash;
    else
        item->prevhash->nexthash = item->nexthash;

    /* Take care of the next item, if any */
    if (item->nexthash != 0)
        item->nexthash->prevhash = item->prevhash;

    /* Handle tail pointer, if supplied */
    if (tail != 0 && *tail == item)
        *tail = item->prevhash;

    item->prevhash = item->nexthash = 0;
    if (count != 0)
        (*count)--;
}


static void
list_insert(
    struct cachekey_disklist *item,
    struct cachekey_disklist **head,
    struct cachekey_disklist **tail,
    u_int *count)
{
    if (item == NULL) return;

    /* Insert at tail, if supplied */
    if (tail != 0) {
        item->prev = *tail;
        if (item->prev != 0)
            item->prev->next = item;
        item->next  = 0;
        *tail       = item;
        if (*head == 0)
            *head   = item;
    } else {
        item->next = *head;
        if (item->next != 0)
            item->next->prev = item;
        item->prev  = 0;
        *head       = item;
    }
    if (count != 0)
        (*count)++;
}

static void
list_insert_hash(
    struct cachekey_disklist *item,
    struct cachekey_disklist **head,
    struct cachekey_disklist **tail,
    u_int *count)
{
    if (item == NULL) return;

    /* Insert at tail, if supplied */
    if (tail != 0) {
        item->prevhash = *tail;
        if (item->prevhash != 0)
            item->prevhash->nexthash = item;
        item->nexthash  = 0;
        *tail       = item;
        if (*head == 0)
            *head   = item;
    } else {
        item->nexthash  = *head;
        if (item->nexthash != 0)
            item->nexthash->prevhash = item;
        item->prevhash  = 0;
        *head       = item;
    }
    if (count != 0)
        (*count)++;
}


/*
 * Find the cache item specified by the header, uid, and public key. If
 * no such uid/public item exists, return a pointer to an empty record.
 * In either case, the item returned has been removed from any and all
 * lists.
 */
static struct cachekey_disklist *
find_cache_item(struct cachekey_header **ch, uid_t uid, struct dhkey *public)
{
    u_int               hash;
    struct cachekey_disklist    *cd;

    hash = hashval(uid);

    if ((ch == NULL) || ((*ch) == NULL)) {
        return (0);
    }
    for (cd = (*ch)->bucket[hash]; cd != 0; cd = cd->nexthash) {
        if (uid == cd->uid &&
            public->length == cd->public.length &&
            memcmp(public->key, cd->public.key,
                cd->public.length) == 0) {
            list_remove_hash(cd, &((*ch)->bucket[hash]), 0, 0);
            list_remove(cd, &((*ch)->inuse), &((*ch)->inuse_end),
                    &((*ch)->inuse_count));
            return (cd);
        }
    }

    if ((cd = (*ch)->free) != 0) {
        list_remove(cd, &((*ch)->free), 0, &((*ch)->free_count));
        return (cd);
    }

    /* Try to extend the file by CHUNK_NUMREC records */
    if (((*ch) = remap_cache_file_ch(*ch, NUMRECS(*ch)+CHUNK_NUMREC)) == 0)
        return (0);

    /* If the extend worked, there should now be at least one free record */
    if ((cd = (*ch)->free) != 0) {
        list_remove(cd, &((*ch)->free), 0, &((*ch)->free_count));
        return (cd);
    }

    /* Sacrifice the LRU item, if there is one */
    if ((cd = (*ch)->inuse) == 0)
        return (0);

    /* Extract from hash list */
    list_remove_hash(cd, &((*ch)->bucket[hashval(cd->uid)]), 0, 0);
    /* Extract from LRU list */
    list_remove(cd, &((*ch)->inuse), &((*ch)->inuse_end),
            &((*ch)->inuse_count));

    return (cd);
}


static struct cachekey_header *
cache_insert_ch(
    struct cachekey_header *ch,
    uid_t uid,
    deskeyarray common,
    des_block key,
    keybuf3 *public,
    keybuf3 *secret)
{
    struct cachekey_disklist    *cd;
    struct cachekey_header      *newch;
    int             i, err;
    struct skck         *skck;
    des_block           ivec;
    struct dhkey            *pk;
    struct dhkey            *sk;


    if (ch == 0 || uid == (uid_t)-1) {
        return (0);
    }

    if (common.deskeyarray_len > sizeof (skck->common)/sizeof (des_block) ||
        (pk = keybuf3_2_dhkey(public)) == 0 ||
        (sk = keybuf3_2_dhkey(secret)) == 0) {
        return (0);
    }

    newch = ch;
    if ((cd = find_cache_item(&newch, uid, pk)) == 0) {
        free(pk);
        free(sk);
        return (newch);
    }

    /*
     * The item may have been free, or may have been the LRU sacrificial
     * lamb, so reset all fields.
     */
    cd->uid = uid;
    memcpy(&(cd->public), pk, DHKEYSIZE(pk));

    skck = MOVE_ADDR(&(cd->public), DHKEYSIZE(pk));
    for (i = 0; i < common.deskeyarray_len; i++) {
        skck->common[i] = common.deskeyarray_val[i];
    }
    skck->verifier = key;
    memcpy(&(skck->secret), sk, DHKEYSIZE(sk));
    free(pk);
    free(sk);
    memcpy(ivec.c, key.c, sizeof (key.c));
    err = cbc_crypt(key.c, (char *)skck, SKCK_LEN(newch->keylen),
            DES_ENCRYPT|DES_HW, ivec.c);
    if (DES_FAILED(err)) {
        /* Re-insert on free list */
        list_insert(cd, &(newch->free), 0, &(newch->free_count));
        return (newch);
    }

    /* Re-insert on hash list */
    list_insert_hash(cd, &(newch->bucket[hashval(cd->uid)]), 0, 0);
    /* Insert at end of LRU list */
    list_insert(cd, &(newch->inuse), &(newch->inuse_end),
            &(newch->inuse_count));

    (void) msync((caddr_t)newch, newch->length, MS_SYNC);

    return (newch);
}


static struct cachekey3_list *
copy_cl_item(struct cachekey_header *ch, struct cachekey_disklist *cd,
        des_block key) {

    struct cachekey3_list       *cl;
    struct skck         *skck, *skck_cd;
    int             i, err;
    des_block           ivec;

    /* Allocate the cachekey3_list structure */
    if ((cl = malloc(CACHEKEY3_LIST_SIZE(ch->keylen))) == 0) {
        return (0);
    }

    /* Allocate skck structure for decryption */
    if ((skck = malloc(SKCK_LEN(ch->keylen))) == 0) {
        free(cl);
        return (0);
    }

    /* Decrypt and check verifier */
    skck_cd = MOVE_ADDR(&(cd->public), DHKEYSIZE(&(cd->public)));
    memcpy(skck, skck_cd, SKCK_LEN(ch->keylen));
    memcpy(ivec.c, key.c, sizeof (ivec.c));
    err = cbc_crypt(key.c, (char *)skck, SKCK_LEN(ch->keylen),
            DES_DECRYPT|DES_HW, ivec.c);
    if (DES_FAILED(err)) {
        free(cl);
        free(skck);
        return (0);
    }
    if (memcmp(key.c, skck->verifier.c, sizeof (skck->verifier.c)) != 0) {
        free(cl);
        free(skck);
        return (0);
    }

    /* Everything OK; copy values */
    cl->public      = MOVE_ADDR(cl, sizeof (struct cachekey3_list));
    cl->public->keybuf3_val = MOVE_ADDR(cl->public, sizeof (keybuf3));
    cl->secret      = MOVE_ADDR(cl->public->keybuf3_val,
                    ALIGN4(2*KEYLEN(ch->keylen)+1));
    cl->secret->keybuf3_val = MOVE_ADDR(cl->secret, sizeof (keybuf3));
    cl->deskey.deskeyarray_val =
                MOVE_ADDR(cl->secret->keybuf3_val,
                    ALIGN4(2*KEYLEN(ch->keylen)+1));
    bin2hex(cd->public.key, (u_char *)cl->public->keybuf3_val,
        cd->public.length);
    cl->public->keybuf3_len = cd->public.length*2+1;

    bin2hex(skck->secret.key, (u_char *)cl->secret->keybuf3_val,
        skck->secret.length);
    cl->secret->keybuf3_len = skck->secret.length*2+1;
    cl->deskey.deskeyarray_len = sizeof (skck->common)/sizeof (des_block);
    for (i = 0; i < cl->deskey.deskeyarray_len; i++) {
        cl->deskey.deskeyarray_val[i] = skck->common[i];
    }

    cl->refcnt = 0;
    cl->next   = 0;

    free(skck);

    return (cl);

}


static struct cachekey3_list *
cache_retrieve_ch(struct cachekey_header *ch, uid_t uid, keybuf3 *public,
        des_block key) {

    struct cachekey_disklist    *cd;
    struct cachekey3_list       *cl = 0, **cltmp = &cl;
    u_int               hash;
    struct dhkey            *pk = 0;

    if (uid == (uid_t)-1 ||
        (public != 0 && (pk = keybuf3_2_dhkey(public)) == 0)) {
        return (0);
    }

    hash = hashval(uid);

    for (cd = ch->bucket[hash]; cd != 0; cd = cd->nexthash) {
        if (uid == cd->uid) {
            /* Match on public key as well ? */
            if (pk != 0) {
                if (memcmp(cd->public.key, pk->key,
                        cd->public.length) != 0) {
                    /* Keep looking... */
                    continue;
                }
                cl = copy_cl_item(ch, cd, key);
                /* Match on public key => nothing more to do */
                break;
            }
            *cltmp = copy_cl_item(ch, cd, key);
            if (*cltmp == 0) {
                /* Return what we've got */
                break;
            }
            cltmp = &((*cltmp)->next);
            /* On to the next item */
        }
    }

    if (pk != 0)
        free(pk);

    return (cl);
}


/*
 * Remove specified item. 'public' == 0 => remove all items for uid.
 * Return number of items removed.
 */
static int
cache_remove_ch(struct cachekey_header *ch, uid_t uid, keybuf3 *public) {

    struct cachekey_disklist    *cd, *cdtmp;
    u_int               hash;
    int             match = 0;
    struct dhkey            *pk = 0;

    if (uid == (uid_t)-1 ||
        (public != 0 && (pk = keybuf3_2_dhkey(public)) == 0)) {
        return (0);
    }

    hash = hashval(uid);

    for (cd = ch->bucket[hash]; cd != 0; ) {
        if (uid == cd->uid) {
            /* Match on public key as well ? */
            if (pk != 0) {
                if (memcmp(cd->public.key, pk->key,
                        cd->public.length) != 0) {
                    /* Keep looking... */
                    continue;
                }
                match++;
                list_remove_hash(cd, &(ch->bucket[hash]), 0, 0);
                list_remove(cd, &(ch->inuse), &(ch->inuse_end),
                        &(ch->inuse_count));
                cd->uid = (uid_t)-1;
                list_insert(cd, &(ch->free), 0,
                        &(ch->free_count));
                /* Match on public key => nothing more to do */
                break;
            }
            match++;
            /*
             * XXX: Assume that the order of the hash list remains
             * the same after removal of an item. If this isn't
             * true, we really should start over from the start
             * of the hash bucket.
             */
            cdtmp = cd->nexthash;
            list_remove_hash(cd, &(ch->bucket[hash]), 0, 0);
            list_remove(cd, &(ch->inuse), &(ch->inuse_end),
                    &(ch->inuse_count));
            cd->uid = (uid_t)-1;
            list_insert(cd, &(ch->free), 0,
                    &(ch->free_count));
            /* On to the next item */
            cd = cdtmp;
        } else {
            cd = cd->nexthash;
        }
    }

    free(pk);
    return (match);
}


#define INCCACHEREFCNT  mutex_lock(&cache_lock); \
            cache_refcnt++; \
            mutex_unlock(&cache_lock)

#if !defined(lint) && !defined(__lint)
#define DECCACHEREFCNT  mutex_lock(&cache_lock); \
            if (cache_refcnt > 0) \
                if (cache_refcnt-- == 0) (void) cond_broadcast(&cache_cv); \
            mutex_unlock(&cache_lock)
#else
#define DECCACHEREFCNT  mutex_lock(&cache_lock); \
            if (cache_refcnt-- == 0) (void) cond_broadcast(&cache_cv); \
            mutex_unlock(&cache_lock)
#endif

/*
 * Return the cachekey structure for the specified keylen and algtype.
 * When returned, the lock in the structure has been activated. It's the
 * responsibility of the caller to unlock it by calling release_cache_header().
 */
static struct cachekey *
get_cache_header(keylen_t keylen, algtype_t algtype) {

    struct cachekey     *c;

    INCCACHEREFCNT;

    for (c = cache; c != 0; c = c->next) {
        if (c->keylen == keylen && c->algtype == algtype) {
            mutex_lock(&c->mp);
            return (c);
        }
    }

    /* Spin until there are no cache readers */
    mutex_lock(&cache_lock);
#if !defined(lint) && !defined(__lint)
    if (cache_refcnt > 0)
#endif
        cache_refcnt--;
    while (cache_refcnt != 0) {
        (void) cond_wait(&cache_cv, &cache_lock);
    }

    if ((c = malloc(sizeof (struct cachekey))) != 0) {
        c->ch       = 0;
        c->keylen   = keylen;
        c->algtype  = algtype;
        mutex_init(&c->mp, 0, 0);
        c->next     = cache;
        cache       = c;
        mutex_lock(&c->mp);
        cache_refcnt++;
        mutex_unlock(&cache_lock);
        return (c);
    }

    mutex_unlock(&cache_lock);
    return (0);
}


static void
release_cache_header(struct cachekey *ck) {

    struct cachekey *c;

    if (ck == 0)
        return;

    for (c = cache; c != 0; c = c->next) {
        if (c == ck) {
            mutex_unlock(&c->mp);
            DECCACHEREFCNT;
            break;
        }
    }
}


int
create_cache_file(keylen_t keylen, algtype_t algtype, int sizespec)
{
    struct cachekey *c;
    int     ret;

    if ((c = get_cache_header(keylen, algtype)) == 0)
        return (0);

    if (c->ch != 0) {
        /* Already created and opened */
        release_cache_header(c);
        return (1);
    }

    ret = (c->ch = create_cache_file_ch(keylen, algtype, sizespec)) != 0;
    release_cache_header(c);

    return (ret);
}


int
cache_insert(
    keylen_t keylen,
    algtype_t algtype,
    uid_t uid,
    deskeyarray common,
    des_block key,
    keybuf3 *public,
    keybuf3 *secret)
{
    struct cachekey *c;
    int     ret;

    if ((c = get_cache_header(keylen, algtype)) == 0)
        return (0);

    if (c->ch == 0) {
        release_cache_header(c);
        return (0);
    }

    ret = (c->ch =
        cache_insert_ch(c->ch, uid, common, key, public, secret)) != 0;

    release_cache_header(c);

    return (ret);
}


struct cachekey3_list *
cache_retrieve(
    keylen_t keylen,
    algtype_t algtype,
    uid_t uid,
    keybuf3 *public,
    des_block key)
{
    struct cachekey     *c;
    struct cachekey3_list   *cl;

    if ((c = get_cache_header(keylen, algtype)) == 0)
        return (0);

    if (c->ch == 0) {
        release_cache_header(c);
        return (0);
    }

    cl = cache_retrieve_ch(c->ch, uid, public, key);

    release_cache_header(c);

    return (cl);
}

int
cache_remove(keylen_t keylen, algtype_t algtype, uid_t uid, keybuf3 *public)
{
    struct cachekey *c;
    int     ret;

    if ((c = get_cache_header(keylen, algtype)) == 0)
        return (0);

    if (c->ch == 0) {
        release_cache_header(c);
        return (0);
    }

    ret = cache_remove_ch(c->ch, uid, public);

    release_cache_header(c);

    return (ret);
}


static struct dhkey *
keybuf3_2_dhkey(keybuf3 *hexkey)
{
    struct dhkey    *binkey;

    /* hexkey->keybuf3_len*4 is the key length in bits */
    if ((binkey = malloc(DHKEYALLOC(hexkey->keybuf3_len*4))) == 0)
        return (0);

    /* Set to zero to keep dbx and Purify access checking happy */
    memset(binkey, 0, DHKEYALLOC(hexkey->keybuf3_len*4));

    binkey->length = hexkey->keybuf3_len/2;
    hex2bin((u_char *)hexkey->keybuf3_val, binkey->key,
        (int)binkey->length);

    return (binkey);
}