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