* Copyright (c) 1990 The Regents of the University of California.
* This code is derived from software contributed to Berkeley by
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 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
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)lrutils.c 5.2 (Berkeley) 2/22/91";
#endif /* LIBC_SCCS and not lint */
* LRUGETPG -- Get a free page from the LRU cache.
* This routine grows the cache if necessary, finds an unused page if
* it can, and handles flushing dirty buffers to disk.
* One of the parameters to this routine (f) is the routine that called
* us. If we have to grow the cache, we call this routine recursively
* in order to fill the buffer. The reason for this is that we have
* two interfaces that call lrugetpg(). Lruget() fills a page from disk,
* and lrugetnew() just allocates a new (empty) page.
* pgno -- page number for which we want a buffer
* nread -- pointer to an int to get number of bytes read
* (char *) pointer to buffer to use, or NULL on failure.
* The buffer returned is locked down until the user does an
* explicit lrurelease() on it.
lrugetpg(l
, pgno
, nread
, f
)
/* if we're allowed to grow the cache, do so */
if (l
->lru_cursz
< l
->lru_csize
) {
if ((buffer
= (char *) malloc((unsigned) l
->lru_psize
))
/* get and LRU list entry */
if ((lruent
= (LRU_ENT
*) malloc((unsigned) sizeof(LRU_ENT
)))
lruent
->l_buffer
= buffer
;
lruent
->l_prev
= (LRU_ENT
*) NULL
;
lruent
->l_next
= l
->lru_head
;
if (l
->lru_head
!= (LRU_ENT
*) NULL
)
l
->lru_head
->l_prev
= lruent
;
if (l
->lru_tail
== (LRU_ENT
*) NULL
)
/* add it to the hash table */
ce
= lruhashput(l
, pgno
, lruent
);
/* find the oldest unused buffer */
while (lruent
!= (LRU_ENT
*) NULL
&& !(lruent
->l_flags
& F_FREE
))
/* if no free buffer was found, we have to grow the cache */
if (lruent
== (LRU_ENT
*) NULL
) {
return ((*f
)((LRU
) l
, pgno
, nread
));
/* okay, found a free buffer -- update hash table and list */
ce
= lruhashget(l
, lruent
->l_pgno
);
if (lruhashdel(l
, lruent
->l_pgno
) < 0)
/* flush the old page to disk, if necessary */
if (lruent
->l_flags
& F_DIRTY
)
if (lruflush(l
, lruent
) < 0)
/* update stats, hash table, and list */
ce
= lruhashput(l
, pgno
, lruent
);
buffer
= lruent
->l_buffer
;
/* lock this page down */
lruent
->l_flags
&= ~F_FREE
;
* LRUHEAD -- Move an LRU list entry to the head of the list.
* The head of the list is where the most recently used item goes.
* lruent -- entry to move to the head of the list
* Updates the cache's head and tail pointers as required.
if (l
->lru_head
== lruent
)
lruent
->l_prev
= (LRU_ENT
*) NULL
;
lruent
->l_next
= l
->lru_head
;
l
->lru_head
->l_prev
= lruent
;
if (next
!= (LRU_ENT
*) NULL
)
if (l
->lru_tail
== lruent
)
* LRUGROW -- Grow the LRU cache
* This routine is called only if we can't satisfy a user's get() request
* using an existing buffer. We need to rebuild the hash table so that
* subsequent lookups work correctly, since the cache size is used to
* Zero on success, -1 on failure
newsz
= l
->lru_csize
+ 1;
/* get a new hash table */
if ((new = (CACHE_ENT
**) malloc((unsigned)newsz
* sizeof(CACHE_ENT
*)))
/* build the new hash table */
bzero((char *) new, (size_t) (newsz
* sizeof(CACHE_ENT
*)));
for (i
= oldsz
; --i
>= 0; ) {
for (ce
= l
->lru_cache
[i
]; ce
!= (CACHE_ENT
*) NULL
; ) {
/* get rid of the old hash table, and update the cache */
free ((char *) (l
->lru_cache
));