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