initial import of NetBSD tree

1 files changed, 540 insertions, 0 deletions

diff --git a/lib/libc/db/mpool/mpool.c b/lib/libc/db/mpool/mpool.c
new file mode 100644
index 00000000000..6417c29d453
--- /dev/null
+++ b/lib/libc/db/mpool/mpool.c
@@ -0,0 +1,540 @@
+/*	$NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $	*/
+
+/*-
+ * Copyright (c) 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+#if 0
+static char sccsid[] = "@(#)mpool.c	8.2 (Berkeley) 2/21/94";
+#else
+static char rcsid[] = "$NetBSD: mpool.c,v 1.5 1995/02/27 13:24:05 cgd Exp $";
+#endif
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/param.h>
+#include <sys/stat.h>
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include <db.h>
+#define	__MPOOLINTERFACE_PRIVATE
+#include "mpool.h"
+
+static BKT *mpool_bkt __P((MPOOL *));
+static BKT *mpool_look __P((MPOOL *, pgno_t));
+static int  mpool_write __P((MPOOL *, BKT *));
+#ifdef DEBUG
+static void __mpoolerr __P((const char *fmt, ...));
+#endif
+
+/*
+ * MPOOL_OPEN -- initialize a memory pool.
+ *
+ * Parameters:
+ *	key:		Shared buffer key.
+ *	fd:		File descriptor.
+ *	pagesize:	File page size.
+ *	maxcache:	Max number of cached pages.
+ *
+ * Returns:
+ *	MPOOL pointer, NULL on error.
+ */
+MPOOL *
+mpool_open(key, fd, pagesize, maxcache)
+	DBT *key;
+	int fd;
+	pgno_t pagesize, maxcache;
+{
+	struct stat sb;
+	MPOOL *mp;
+	int entry;
+
+	if (fstat(fd, &sb))
+		return (NULL);
+	/* XXX
+	 * We should only set st_size to 0 for pipes -- 4.4BSD has the fix so
+	 * that stat(2) returns true for ISSOCK on pipes.  Until then, this is
+	 * fairly close.
+	 */
+	if (!S_ISREG(sb.st_mode)) {
+		errno = ESPIPE;
+		return (NULL);
+	}
+
+	if ((mp = (MPOOL *)malloc(sizeof(MPOOL))) == NULL)
+		return (NULL);
+	mp->free.cnext = mp->free.cprev = (BKT *)&mp->free;
+	mp->lru.cnext = mp->lru.cprev = (BKT *)&mp->lru;
+	for (entry = 0; entry < HASHSIZE; ++entry)
+		mp->hashtable[entry].hnext = mp->hashtable[entry].hprev = 
+		    mp->hashtable[entry].cnext = mp->hashtable[entry].cprev =
+		    (BKT *)&mp->hashtable[entry];
+	mp->curcache = 0;
+	mp->maxcache = maxcache;
+	mp->pagesize = pagesize;
+	mp->npages = sb.st_size / pagesize;
+	mp->fd = fd;
+	mp->pgcookie = NULL;
+	mp->pgin = mp->pgout = NULL;
+
+#ifdef STATISTICS
+	mp->cachehit = mp->cachemiss = mp->pagealloc = mp->pageflush = 
+	    mp->pageget = mp->pagenew = mp->pageput = mp->pageread = 
+	    mp->pagewrite = 0;
+#endif
+	return (mp);
+}
+
+/*
+ * MPOOL_FILTER -- initialize input/output filters.
+ *
+ * Parameters:
+ *	pgin:		Page in conversion routine.
+ *	pgout:		Page out conversion routine.
+ *	pgcookie:	Cookie for page in/out routines.
+ */
+void
+mpool_filter(mp, pgin, pgout, pgcookie)
+	MPOOL *mp;
+	void (*pgin) __P((void *, pgno_t, void *));
+	void (*pgout) __P((void *, pgno_t, void *));
+	void *pgcookie;
+{
+	mp->pgin = pgin;
+	mp->pgout = pgout;
+	mp->pgcookie = pgcookie;
+}
+	
+/*
+ * MPOOL_NEW -- get a new page
+ *
+ * Parameters:
+ *	mp:		mpool cookie
+ *	pgnoadddr:	place to store new page number
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+void *
+mpool_new(mp, pgnoaddr)
+	MPOOL *mp;
+	pgno_t *pgnoaddr;
+{
+	BKT *b;
+	BKTHDR *hp;
+
+#ifdef STATISTICS
+	++mp->pagenew;
+#endif
+	/*
+	 * Get a BKT from the cache.  Assign a new page number, attach it to
+	 * the hash and lru chains and return.
+	 */
+	if ((b = mpool_bkt(mp)) == NULL)
+		return (NULL);
+	*pgnoaddr = b->pgno = mp->npages++;
+	b->flags = MPOOL_PINNED;
+	inshash(b, b->pgno);
+	inschain(b, &mp->lru);
+	return (b->page);
+}
+
+/*
+ * MPOOL_GET -- get a page from the pool
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ *	pgno:	page number
+ *	flags:	not used
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+void *
+mpool_get(mp, pgno, flags)
+	MPOOL *mp;
+	pgno_t pgno;
+	u_int flags;		/* XXX not used? */
+{
+	BKT *b;
+	BKTHDR *hp;
+	off_t off;
+	int nr;
+
+	/*
+	 * If asking for a specific page that is already in the cache, find
+	 * it and return it.
+	 */
+	if (b = mpool_look(mp, pgno)) {
+#ifdef STATISTICS
+		++mp->pageget;
+#endif
+#ifdef DEBUG
+		if (b->flags & MPOOL_PINNED)
+			__mpoolerr("mpool_get: page %d already pinned",
+			    b->pgno);
+#endif
+		rmchain(b);
+		inschain(b, &mp->lru);
+		b->flags |= MPOOL_PINNED;
+		return (b->page);
+	}
+
+	/* Not allowed to retrieve a non-existent page. */
+	if (pgno >= mp->npages) {
+		errno = EINVAL;
+		return (NULL);
+	}
+
+	/* Get a page from the cache. */
+	if ((b = mpool_bkt(mp)) == NULL)
+		return (NULL);
+	b->pgno = pgno;
+	b->flags = MPOOL_PINNED;
+
+#ifdef STATISTICS
+	++mp->pageread;
+#endif
+	/* Read in the contents. */
+	off = mp->pagesize * pgno;
+	if (lseek(mp->fd, off, SEEK_SET) != off)
+		return (NULL);
+	if ((nr = read(mp->fd, b->page, mp->pagesize)) != mp->pagesize) {
+		if (nr >= 0)
+			errno = EFTYPE;
+		return (NULL);
+	}
+	if (mp->pgin)
+		(mp->pgin)(mp->pgcookie, b->pgno, b->page);
+
+	inshash(b, b->pgno);
+	inschain(b, &mp->lru);
+#ifdef STATISTICS
+	++mp->pageget;
+#endif
+	return (b->page);
+}
+
+/*
+ * MPOOL_PUT -- return a page to the pool
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ *	page:	page pointer
+ *	pgno:	page number
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+mpool_put(mp, page, flags)
+	MPOOL *mp;
+	void *page;
+	u_int flags;
+{
+	BKT *baddr;
+#ifdef DEBUG
+	BKT *b;
+#endif
+
+#ifdef STATISTICS
+	++mp->pageput;
+#endif
+	baddr = (BKT *)((char *)page - sizeof(BKT));
+#ifdef DEBUG
+	if (!(baddr->flags & MPOOL_PINNED))
+		__mpoolerr("mpool_put: page %d not pinned", b->pgno);
+	for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
+		if (b == (BKT *)&mp->lru)
+			__mpoolerr("mpool_put: %0x: bad address", baddr);
+		if (b == baddr)
+			break;
+	}
+#endif
+	baddr->flags &= ~MPOOL_PINNED;
+	baddr->flags |= flags & MPOOL_DIRTY;
+	return (RET_SUCCESS);
+}
+
+/*
+ * MPOOL_CLOSE -- close the buffer pool
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+mpool_close(mp)
+	MPOOL *mp;
+{
+	BKT *b, *next;
+
+	/* Free up any space allocated to the lru pages. */
+	for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = next) {
+		next = b->cprev;
+		free(b);
+	}
+	free(mp);
+	return (RET_SUCCESS);
+}
+
+/*
+ * MPOOL_SYNC -- sync the file to disk.
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+int
+mpool_sync(mp)
+	MPOOL *mp;
+{
+	BKT *b;
+
+	for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
+		if (b->flags & MPOOL_DIRTY && mpool_write(mp, b) == RET_ERROR)
+			return (RET_ERROR);
+	return (fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
+}
+
+/*
+ * MPOOL_BKT -- get/create a BKT from the cache
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ *
+ * Returns:
+ *	NULL on failure and a pointer to the BKT on success	
+ */
+static BKT *
+mpool_bkt(mp)
+	MPOOL *mp;
+{
+	BKT *b;
+
+	if (mp->curcache < mp->maxcache)
+		goto new;
+
+	/*
+	 * If the cache is maxxed out, search the lru list for a buffer we
+	 * can flush.  If we find one, write it if necessary and take it off
+	 * any lists.  If we don't find anything we grow the cache anyway.
+	 * The cache never shrinks.
+	 */
+	for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
+		if (!(b->flags & MPOOL_PINNED)) {
+			if (b->flags & MPOOL_DIRTY &&
+			    mpool_write(mp, b) == RET_ERROR)
+				return (NULL);
+			rmhash(b);
+			rmchain(b);
+#ifdef STATISTICS
+			++mp->pageflush;
+#endif
+#ifdef DEBUG
+			{
+				void *spage;
+				spage = b->page;
+				memset(b, 0xff, sizeof(BKT) + mp->pagesize);
+				b->page = spage;
+			}
+#endif
+			return (b);
+		}
+
+new:	if ((b = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
+		return (NULL);
+#ifdef STATISTICS
+	++mp->pagealloc;
+#endif
+#ifdef DEBUG
+	memset(b, 0xff, sizeof(BKT) + mp->pagesize);
+#endif
+	b->page = (char *)b + sizeof(BKT);
+	++mp->curcache;
+	return (b);
+}
+
+/*
+ * MPOOL_WRITE -- sync a page to disk
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ *
+ * Returns:
+ *	RET_ERROR, RET_SUCCESS
+ */
+static int
+mpool_write(mp, b)
+	MPOOL *mp;
+	BKT *b;
+{
+	off_t off;
+
+	if (mp->pgout)
+		(mp->pgout)(mp->pgcookie, b->pgno, b->page);
+
+#ifdef STATISTICS
+	++mp->pagewrite;
+#endif
+	off = mp->pagesize * b->pgno;
+	if (lseek(mp->fd, off, SEEK_SET) != off)
+		return (RET_ERROR);
+	if (write(mp->fd, b->page, mp->pagesize) != mp->pagesize)
+		return (RET_ERROR);
+	b->flags &= ~MPOOL_DIRTY;
+	return (RET_SUCCESS);
+}
+
+/*
+ * MPOOL_LOOK -- lookup a page
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ *	pgno:	page number
+ *
+ * Returns:
+ *	NULL on failure and a pointer to the BKT on success
+ */
+static BKT *
+mpool_look(mp, pgno)
+	MPOOL *mp;
+	pgno_t pgno;
+{
+	register BKT *b;
+	register BKTHDR *tb;
+
+	/* XXX
+	 * If find the buffer, put it first on the hash chain so can
+	 * find it again quickly.
+	 */
+	tb = &mp->hashtable[HASHKEY(pgno)];
+	for (b = tb->hnext; b != (BKT *)tb; b = b->hnext)
+		if (b->pgno == pgno) {
+#ifdef STATISTICS
+			++mp->cachehit;
+#endif
+			return (b);
+		}
+#ifdef STATISTICS
+	++mp->cachemiss;
+#endif
+	return (NULL);
+}
+
+#ifdef STATISTICS
+/*
+ * MPOOL_STAT -- cache statistics
+ *
+ * Parameters:
+ *	mp:	mpool cookie
+ */
+void
+mpool_stat(mp)
+	MPOOL *mp;
+{
+	BKT *b;
+	int cnt;
+	char *sep;
+
+	(void)fprintf(stderr, "%lu pages in the file\n", mp->npages);
+	(void)fprintf(stderr,
+	    "page size %lu, cacheing %lu pages of %lu page max cache\n",
+	    mp->pagesize, mp->curcache, mp->maxcache);
+	(void)fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n",
+	    mp->pageput, mp->pageget, mp->pagenew);
+	(void)fprintf(stderr, "%lu page allocs, %lu page flushes\n",
+	    mp->pagealloc, mp->pageflush);
+	if (mp->cachehit + mp->cachemiss)
+		(void)fprintf(stderr,
+		    "%.0f%% cache hit rate (%lu hits, %lu misses)\n", 
+		    ((double)mp->cachehit / (mp->cachehit + mp->cachemiss))
+		    * 100, mp->cachehit, mp->cachemiss);
+	(void)fprintf(stderr, "%lu page reads, %lu page writes\n",
+	    mp->pageread, mp->pagewrite);
+
+	sep = "";
+	cnt = 0;
+	for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
+		(void)fprintf(stderr, "%s%d", sep, b->pgno);
+		if (b->flags & MPOOL_DIRTY)
+			(void)fprintf(stderr, "d");
+		if (b->flags & MPOOL_PINNED)
+			(void)fprintf(stderr, "P");
+		if (++cnt == 10) {
+			sep = "\n";
+			cnt = 0;
+		} else
+			sep = ", ";
+			
+	}
+	(void)fprintf(stderr, "\n");
+}
+#endif
+
+#ifdef DEBUG
+#if __STDC__
+#include <stdarg.h>
+#else
+#include <varargs.h>
+#endif
+
+static void
+#if __STDC__
+__mpoolerr(const char *fmt, ...)
+#else
+__mpoolerr(fmt, va_alist)
+	char *fmt;
+	va_dcl
+#endif
+{
+	va_list ap;
+#if __STDC__
+	va_start(ap, fmt);
+#else
+	va_start(ap);
+#endif
+	(void)vfprintf(stderr, fmt, ap);
+	va_end(ap);
+	(void)fprintf(stderr, "\n");
+	abort();
+	/* NOTREACHED */
+}
+#endif