[unix-history] / usr / src / lib / libc / db / btree / lrucache.c

/*-
 * Copyright (c) 1990 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Mike Olson.
 *
 * %sccs.include.redist.c%
 */

#if defined(LIBC_SCCS) && !defined(lint)
char sccsid[] = "@(#)lrucache.c	5.3 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */

/*
 *  lrucache.c -- LRU cache for disk-based btree pages.
 *
 *	This file implements an LRU cache in user space for disk-based
 *	btrees.
 */
#include <sys/param.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "lrucache.h"

/*
 *  LRUINIT -- Initialize a new LRU cache.
 *
 *	There's a separate LRU cache for every open file descriptor on which
 *	the user wants caching.  The desired cache size and logical page
 *	size are passed in.  We try to avoid growing the cache beyond the
 *	limit specified by the user, but if we cannot satisfy a block request
 *	without growing the cache, we do so.
 *
 *	Note that the page size passed in is the logical page size for
 *	use with this file descriptor, and doesn't necessarily have anything
 *	to do with the underlying hardware page size.
 *
 *	Parameters:
 *		fd -- file descriptor for this cache
 *		cachesz -- number of buffers in cache (suggested)
 *		pagesz -- logical page size inside this file
 *		inproc -- routine to call when a buffer is read
 *		outproc -- routine to call when a buffer is written
 *
 *	Returns:
 *		Opaque pointer to the LRU cache on success, NULL on failure.
 *
 *	Side Effects:
 *		Allocates memory for the hash table and LRU cache.  Buffers
 *		are allocated on demand, later.
 */
LRU
lruinit(fd, cachesz, pagesz, opaque, inproc, outproc)
	int fd;
	int cachesz;
	int pagesz;
	char *opaque;
	int (*inproc)();
	int (*outproc)();
{
	register LRUCACHE *l;
	int nbytes;

	/* allocate the LRU cache struct */
	if ((l = (LRUCACHE *) malloc((unsigned) sizeof(LRUCACHE)))
	    == (LRUCACHE *) NULL)
		return ((LRU) NULL);

	/* allocate the hash table */
	nbytes = cachesz * sizeof(CACHE_ENT *);
	if ((l->lru_cache = (CACHE_ENT **) malloc((unsigned) nbytes))
	    == (CACHE_ENT **) NULL) {
		(void) free((char *) l);
		return ((LRU) NULL);
	}

	/* init memory */
	bzero((char *) (l->lru_cache), (size_t) nbytes);
	l->lru_fd = fd;
	l->lru_psize = pagesz;
	l->lru_csize = cachesz;
	l->lru_cursz = 0;
	l->lru_opaque = opaque;
	l->lru_head = l->lru_tail = (LRU_ENT *) NULL;
	l->lru_inproc = inproc;
	l->lru_outproc = outproc;

	return ((LRU) l);
}

/*
 *  LRUGET -- Get a buffer from an LRU cache.
 *
 *	If the buffer is not in the cache at present, this routine will
 *	instantiate it from the file.  This REQUIRES that the desired
 *	block actually be on disk; we don't do non-blocking reads, so
 *	if it's not actually out there, this routine won't return for
 *	a very long time.  In order to instantiate a new buffer, use
 *	lrugetnew().
 *
 *	Parameters:
 *		lru -- the LRU cache to use.
 *		pgno -- the logical block number to get.
 *		nread -- pointer to an int, in which the number of bytes
 *			 read is returned.
 *
 *	Returns:
 *		(char *) pointer to the buffer for the desired block.  The
 *		number of bytes actually read is returned in *nread.
 *
 *	Warnings:
 *		The requested buffer is locked down until the user does
 *		an explicit lrurelease() on it.
 */

char *
lruget(lru, pgno, nread)
	LRU lru;
	int pgno;
	int *nread;
{
	LRUCACHE *l = (LRUCACHE *) lru;
	CACHE_ENT *ce;
	LRU_ENT *lruent;
	char *buffer;
	long pos;

	/* is it already in the cache? */
	if ((ce = lruhashget(l, pgno)) != (CACHE_ENT *) NULL) {

		/* yes, move it to the head and return it */
		lruent = ce->c_lruent;
		lruent->l_flags &= ~F_FREE;
		lruhead(l, ce->c_lruent);
		*nread = l->lru_psize;
		return (ce->c_lruent->l_buffer);
	}

	/* not there, get a free page */
	if ((buffer = lrugetpg(l, pgno, nread, lruget)) == (char *) NULL)
		return ((char *) NULL);

	/* okay, got a buffer -- fill it */
	pos = (long) (l->lru_psize * pgno);
	if (lseek(l->lru_fd, pos, L_SET) != pos)
		return ((char *) NULL);

	*nread = read(l->lru_fd, buffer, l->lru_psize);

	if (l->lru_inproc)
		(*(l->lru_inproc))(buffer, l->lru_opaque);

	return (buffer);
}

/*
 *  LRUGETNEW -- Get a page for a new block in an LRU cache.
 *
 *	This routine allows users to instantiate pages for a file if they
 *	don't exist on disk yet.  It's used to make a file bigger.
 *
 *	Parameters:
 *		lru -- the LRU cache to use
 *		pgno -- the (new) logical page number to instantiate
 *		nread -- ptr to int to get number of bytes read (this is
 *			 guaranteed to be zero, since the page isn't on disk)
 *
 *	Returns:
 *		Pointer to a buffer for the associated page, or NULL on
 *		failure.
 *
 *	Warnings:
 *		The associated buffer is locked down until the user
 *		explicitly does an lrurelease() on it.
 */

char *
lrugetnew(lru, pgno, nread)
	LRU lru;
	int pgno;
	int *nread;
{
	LRUCACHE *l = (LRUCACHE *) lru;

	*nread = 0;
	return (lrugetpg(l, pgno, nread, lrugetnew));
}

/*
 *  LRUFLUSH -- flush an LRU page to disk.
 *
 *	This routine forces a page to disk.  Users should use lruwrite(),
 *	which simply marks a page dirty and does late writing.
 *
 *	Parameters:
 *		l -- LRU cache
 *		lruent -- the LRU cache entry whose page we should flush
 *
 *	Returns:
 *		Zero on success, -1 on failure.
 */

lruflush(l, lruent)
	LRUCACHE *l;
	LRU_ENT *lruent;
{
	long pos;

	if (l->lru_outproc)
		(*(l->lru_outproc))(lruent->l_buffer, l->lru_opaque);

	pos = (long) (l->lru_psize * lruent->l_pgno);
	if (lseek(l->lru_fd, pos, L_SET) != pos)
		return (-1);
	if (write(l->lru_fd, lruent->l_buffer, l->lru_psize) != l->lru_psize)
		return (-1);

	if (l->lru_inproc)
		(*(l->lru_inproc))(lruent->l_buffer, l->lru_opaque);

	lruent->l_flags &= ~F_DIRTY;
	return (0);
}

/*
 *  LRUWRITE -- Mark an LRU cache buffer dirty
 *
 *	This routine is how users should move their changes to disk.  The
 *	cache code marks the associated buffer dirty, and flushes it to
 *	disk if we need to reuse the buffer for some other page.
 *
 *	Parameters:
 *		lru -- LRU cache
 *		pgno -- page number to flush
 *
 *	Returns:
 *		Zero on success, -1 on failure.
 */

int
lruwrite(lru, pgno)
	LRU lru;
	int pgno;
{
	LRUCACHE *l = (LRUCACHE *) lru;
	CACHE_ENT *ce;

	if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
		return (-1);

	/* mark the entry dirty */
	ce->c_lruent->l_flags |= F_DIRTY;

	return (0);
}

/*
 *  LRUSYNC -- Flush all changes to disk
 *
 *	This routine allows users to force all changes to buffers currently
 *	in memory to disk.  This is expensive.
 *
 *	Parameters:
 *		lru -- LRU cache to flush
 *
 *	Returns:
 *		Zero on success, -1 on failure
 *
 *	Side Effects:
 *		After this call, all buffers are clean.
 */

int
lrusync(lru)
	LRU lru;
{
	LRUCACHE *l = (LRUCACHE *) lru;
	LRU_ENT *le;

	for (le = l->lru_head; le != (LRU_ENT *) NULL; le = le->l_next)
		if (le->l_flags & F_DIRTY)
			if (lruflush(l, le) < 0)
				return (-1);
	return (0);
}

/*
 *  LRURELEASE -- Release a buffer in the LRU cache for reuse
 *
 *	When the user does an lruget() or lrugetnew(), the buffer we return
 *	is locked down, to guarantee that it's not reused while the user
 *	still needs it.  Once a buffer is no longer needed, it should be
 *	released (via this routine) so that we can use it for other pages
 *	if necessary.
 *
 *	Parameters:
 *		lru -- LRU cache
 *		pgno -- page number of buffer to release
 *
 *	Returns:
 *		Zero on success, -1 on failure
 */

int
lrurelease(lru, pgno)
	LRU lru;
	int pgno;
{
	LRUCACHE *l = (LRUCACHE *) lru;
	CACHE_ENT *ce;

	if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
		return (-1);
	ce->c_lruent->l_flags |= F_FREE;
	return (0);
}

/*
 *  LRUFREE -- Free an entire LRU cache
 *
 *	This routine releases an LRU cache.  The cache should not be
 *	used again.
 *
 *	Parameters:
 *		lru -- LRU cache to free
 *
 *	Returns:
 *		None.
 *
 *	Side Effects:
 *		Frees a lot of memory.
 */

void
lrufree(lru)
	LRU lru;
{
	LRUCACHE *l = (LRUCACHE *) lru;
	LRU_ENT *le;
	LRU_ENT *sle;

	for (le = l->lru_head; le != (LRU_ENT *) NULL; ) {
		free((char *) (le->l_buffer));
		sle = le;
		le = le->l_next;
		free((char *) sle);
	}
	free ((char *) l);
}
Commit	Line	Data
6ca882b0 KB	1	/*-
	2	* Copyright (c) 1990 The Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* This code is derived from software contributed to Berkeley by
	6	* Mike Olson.
	7	*
	8	* %sccs.include.redist.c%
	9	*/
	10
	11	#if defined(LIBC_SCCS) && !defined(lint)
fb91cf55	12	char sccsid[] = "@(#)lrucache.c 5.3 (Berkeley) %G%";
6ca882b0 KB	13	#endif /* LIBC_SCCS and not lint */
	14
	15	/*
	16	* lrucache.c -- LRU cache for disk-based btree pages.
	17	*
	18	* This file implements an LRU cache in user space for disk-based
	19	* btrees.
	20	*/
	21	#include <sys/param.h>
fb91cf55 KB	22	#include <stdlib.h>
	23	#include <string.h>
	24	#include <unistd.h>
71e5ebb2	25	#include "lrucache.h"
6ca882b0 KB	26
	27	/*
	28	* LRUINIT -- Initialize a new LRU cache.
	29	*
	30	* There's a separate LRU cache for every open file descriptor on which
	31	* the user wants caching. The desired cache size and logical page
	32	* size are passed in. We try to avoid growing the cache beyond the
	33	* limit specified by the user, but if we cannot satisfy a block request
	34	* without growing the cache, we do so.
	35	*
	36	* Note that the page size passed in is the logical page size for
	37	* use with this file descriptor, and doesn't necessarily have anything
	38	* to do with the underlying hardware page size.
	39	*
	40	* Parameters:
	41	* fd -- file descriptor for this cache
	42	* cachesz -- number of buffers in cache (suggested)
	43	* pagesz -- logical page size inside this file
	44	* inproc -- routine to call when a buffer is read
	45	* outproc -- routine to call when a buffer is written
	46	*
	47	* Returns:
	48	* Opaque pointer to the LRU cache on success, NULL on failure.
	49	*
	50	* Side Effects:
	51	* Allocates memory for the hash table and LRU cache. Buffers
	52	* are allocated on demand, later.
	53	*/
	54	LRU
	55	lruinit(fd, cachesz, pagesz, opaque, inproc, outproc)
	56	int fd;
	57	int cachesz;
	58	int pagesz;
	59	char *opaque;
	60	int (*inproc)();
	61	int (*outproc)();
	62	{
	63	register LRUCACHE *l;
	64	int nbytes;
	65
	66	/* allocate the LRU cache struct */
	67	if ((l = (LRUCACHE *) malloc((unsigned) sizeof(LRUCACHE)))
	68	== (LRUCACHE *) NULL)
	69	return ((LRU) NULL);
	70
	71	/* allocate the hash table */
	72	nbytes = cachesz * sizeof(CACHE_ENT *);
	73	if ((l->lru_cache = (CACHE_ENT **) malloc((unsigned) nbytes))
	74	== (CACHE_ENT **) NULL) {
71e5ebb2	75	(void) free((char *) l);
6ca882b0 KB	76	return ((LRU) NULL);
	77	}
	78
	79	/* init memory */
71e5ebb2	80	bzero((char *) (l->lru_cache), (size_t) nbytes);
6ca882b0 KB	81	l->lru_fd = fd;
	82	l->lru_psize = pagesz;
	83	l->lru_csize = cachesz;
	84	l->lru_cursz = 0;
	85	l->lru_opaque = opaque;
	86	l->lru_head = l->lru_tail = (LRU_ENT *) NULL;
	87	l->lru_inproc = inproc;
	88	l->lru_outproc = outproc;
	89
	90	return ((LRU) l);
	91	}
	92
	93	/*
	94	* LRUGET -- Get a buffer from an LRU cache.
	95	*
	96	* If the buffer is not in the cache at present, this routine will
	97	* instantiate it from the file. This REQUIRES that the desired
	98	* block actually be on disk; we don't do non-blocking reads, so
	99	* if it's not actually out there, this routine won't return for
	100	* a very long time. In order to instantiate a new buffer, use
	101	* lrugetnew().
	102	*
	103	* Parameters:
	104	* lru -- the LRU cache to use.
	105	* pgno -- the logical block number to get.
	106	* nread -- pointer to an int, in which the number of bytes
	107	* read is returned.
	108	*
	109	* Returns:
	110	* (char *) pointer to the buffer for the desired block. The
	111	* number of bytes actually read is returned in *nread.
	112	*
	113	* Warnings:
	114	* The requested buffer is locked down until the user does
	115	* an explicit lrurelease() on it.
	116	*/
	117
	118	char *
	119	lruget(lru, pgno, nread)
	120	LRU lru;
	121	int pgno;
	122	int *nread;
	123	{
	124	LRUCACHE l = (LRUCACHE ) lru;
	125	CACHE_ENT *ce;
6ca882b0 KB	126	LRU_ENT *lruent;
	127	char *buffer;
	128	long pos;
	129
	130	/* is it already in the cache? */
	131	if ((ce = lruhashget(l, pgno)) != (CACHE_ENT *) NULL) {
	132
	133	/* yes, move it to the head and return it */
	134	lruent = ce->c_lruent;
	135	lruent->l_flags &= ~F_FREE;
	136	lruhead(l, ce->c_lruent);
	137	*nread = l->lru_psize;
	138	return (ce->c_lruent->l_buffer);
	139	}
	140
	141	/* not there, get a free page */
	142	if ((buffer = lrugetpg(l, pgno, nread, lruget)) == (char *) NULL)
	143	return ((char *) NULL);
	144
	145	/* okay, got a buffer -- fill it */
	146	pos = (long) (l->lru_psize * pgno);
	147	if (lseek(l->lru_fd, pos, L_SET) != pos)
	148	return ((char *) NULL);
	149
	150	*nread = read(l->lru_fd, buffer, l->lru_psize);
	151
	152	if (l->lru_inproc)
	153	(*(l->lru_inproc))(buffer, l->lru_opaque);
	154
	155	return (buffer);
	156	}
	157
	158	/*
	159	* LRUGETNEW -- Get a page for a new block in an LRU cache.
	160	*
	161	* This routine allows users to instantiate pages for a file if they
	162	* don't exist on disk yet. It's used to make a file bigger.
	163	*
	164	* Parameters:
	165	* lru -- the LRU cache to use
	166	* pgno -- the (new) logical page number to instantiate
	167	* nread -- ptr to int to get number of bytes read (this is
	168	* guaranteed to be zero, since the page isn't on disk)
	169	*
	170	* Returns:
	171	* Pointer to a buffer for the associated page, or NULL on
	172	* failure.
	173	*
	174	* Warnings:
	175	* The associated buffer is locked down until the user
	176	* explicitly does an lrurelease() on it.
	177	*/
	178
	179	char *
	180	lrugetnew(lru, pgno, nread)
	181	LRU lru;
	182	int pgno;
	183	int *nread;
	184	{
	185	LRUCACHE l = (LRUCACHE ) lru;
	186
	187	*nread = 0;
	188	return (lrugetpg(l, pgno, nread, lrugetnew));
	189	}
190
6ca882b0 KB	191	/*
	192	* LRUFLUSH -- flush an LRU page to disk.
	193	*
	194	* This routine forces a page to disk. Users should use lruwrite(),
	195	* which simply marks a page dirty and does late writing.
	196	*
	197	* Parameters:
	198	* l -- LRU cache
	199	* lruent -- the LRU cache entry whose page we should flush
	200	*
	201	* Returns:
	202	* Zero on success, -1 on failure.
	203	*/
	204
	205	lruflush(l, lruent)
	206	LRUCACHE *l;
	207	LRU_ENT *lruent;
	208	{
	209	long pos;
6ca882b0 KB	210
	211	if (l->lru_outproc)
	212	(*(l->lru_outproc))(lruent->l_buffer, l->lru_opaque);
	213
	214	pos = (long) (l->lru_psize * lruent->l_pgno);
	215	if (lseek(l->lru_fd, pos, L_SET) != pos)
	216	return (-1);
	217	if (write(l->lru_fd, lruent->l_buffer, l->lru_psize) != l->lru_psize)
	218	return (-1);
	219
	220	if (l->lru_inproc)
	221	(*(l->lru_inproc))(lruent->l_buffer, l->lru_opaque);
	222
	223	lruent->l_flags &= ~F_DIRTY;
	224	return (0);
	225	}
	226
6ca882b0 KB	227	/*
	228	* LRUWRITE -- Mark an LRU cache buffer dirty
	229	*
	230	* This routine is how users should move their changes to disk. The
	231	* cache code marks the associated buffer dirty, and flushes it to
	232	* disk if we need to reuse the buffer for some other page.
	233	*
	234	* Parameters:
	235	* lru -- LRU cache
	236	* pgno -- page number to flush
	237	*
	238	* Returns:
	239	* Zero on success, -1 on failure.
	240	*/
	241
	242	int
	243	lruwrite(lru, pgno)
	244	LRU lru;
	245	int pgno;
	246	{
	247	LRUCACHE l = (LRUCACHE ) lru;
6ca882b0 KB	248	CACHE_ENT *ce;
	249
	250	if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
	251	return (-1);
	252
	253	/* mark the entry dirty */
	254	ce->c_lruent->l_flags \|= F_DIRTY;
	255
	256	return (0);
	257	}
	258
	259	/*
	260	* LRUSYNC -- Flush all changes to disk
	261	*
	262	* This routine allows users to force all changes to buffers currently
	263	* in memory to disk. This is expensive.
	264	*
	265	* Parameters:
	266	* lru -- LRU cache to flush
	267	*
	268	* Returns:
	269	* Zero on success, -1 on failure
	270	*
	271	* Side Effects:
	272	* After this call, all buffers are clean.
	273	*/
	274
	275	int
	276	lrusync(lru)
	277	LRU lru;
	278	{
	279	LRUCACHE l = (LRUCACHE ) lru;
	280	LRU_ENT *le;
	281
	282	for (le = l->lru_head; le != (LRU_ENT *) NULL; le = le->l_next)
	283	if (le->l_flags & F_DIRTY)
	284	if (lruflush(l, le) < 0)
	285	return (-1);
	286	return (0);
	287	}
	288
6ca882b0 KB	289	/*
	290	* LRURELEASE -- Release a buffer in the LRU cache for reuse
	291	*
	292	* When the user does an lruget() or lrugetnew(), the buffer we return
	293	* is locked down, to guarantee that it's not reused while the user
	294	* still needs it. Once a buffer is no longer needed, it should be
	295	* released (via this routine) so that we can use it for other pages
	296	* if necessary.
	297	*
	298	* Parameters:
	299	* lru -- LRU cache
	300	* pgno -- page number of buffer to release
	301	*
	302	* Returns:
	303	* Zero on success, -1 on failure
	304	*/
	305
	306	int
	307	lrurelease(lru, pgno)
	308	LRU lru;
	309	int pgno;
	310	{
	311	LRUCACHE l = (LRUCACHE ) lru;
	312	CACHE_ENT *ce;
	313
	314	if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
	315	return (-1);
	316	ce->c_lruent->l_flags \|= F_FREE;
	317	return (0);
	318	}
	319
	320	/*
	321	* LRUFREE -- Free an entire LRU cache
	322	*
	323	* This routine releases an LRU cache. The cache should not be
	324	* used again.
	325	*
	326	* Parameters:
	327	* lru -- LRU cache to free
	328	*
	329	* Returns:
	330	* None.
	331	*
	332	* Side Effects:
	333	* Frees a lot of memory.
	334	*/
	335
	336	void
	337	lrufree(lru)
	338	LRU lru;
	339	{
	340	LRUCACHE l = (LRUCACHE ) lru;
	341	LRU_ENT *le;
	342	LRU_ENT *sle;
	343
	344	for (le = l->lru_head; le != (LRU_ENT *) NULL; ) {
71e5ebb2	345	free((char *) (le->l_buffer));
6ca882b0 KB	346	sle = le;
6ca882b0 KB	347	le = le->l_next;
71e5ebb2	348	free((char *) sle);
6ca882b0	349	}
71e5ebb2	350	free ((char *) l);
6ca882b0	351	}