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 static char sccsid[] = "@(#)lrutils.c 5.2 (Berkeley) 02/22/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <stdlib.h> 16 #include <string.h> 17 #include "lrucache.h" 18 19 /* 20 * LRUGETPG -- Get a free page from the LRU cache. 21 * 22 * This routine grows the cache if necessary, finds an unused page if 23 * it can, and handles flushing dirty buffers to disk. 24 * 25 * One of the parameters to this routine (f) is the routine that called 26 * us. If we have to grow the cache, we call this routine recursively 27 * in order to fill the buffer. The reason for this is that we have 28 * two interfaces that call lrugetpg(). Lruget() fills a page from disk, 29 * and lrugetnew() just allocates a new (empty) page. 30 * 31 * Parameters: 32 * l -- LRU cache to use. 33 * pgno -- page number for which we want a buffer 34 * nread -- pointer to an int to get number of bytes read 35 * f -- who called us 36 * 37 * Returns: 38 * (char *) pointer to buffer to use, or NULL on failure. 39 * 40 * Warnings: 41 * The buffer returned is locked down until the user does an 42 * explicit lrurelease() on it. 43 */ 44 45 char * 46 lrugetpg(l, pgno, nread, f) 47 LRUCACHE *l; 48 int pgno; 49 int *nread; 50 char *(*f)(); 51 { 52 CACHE_ENT *ce; 53 LRU_ENT *lruent; 54 char *buffer; 55 56 /* if we're allowed to grow the cache, do so */ 57 if (l->lru_cursz < l->lru_csize) { 58 59 /* get a buffer */ 60 if ((buffer = (char *) malloc((unsigned) l->lru_psize)) 61 == (char *) NULL) 62 return ((char *) NULL); 63 64 /* get and LRU list entry */ 65 if ((lruent = (LRU_ENT *) malloc((unsigned) sizeof(LRU_ENT))) 66 == (LRU_ENT *) NULL) 67 return ((char *) NULL); 68 lruent->l_buffer = buffer; 69 lruent->l_pgno = pgno; 70 lruent->l_flags = NULL; 71 72 /* manage spaghetti */ 73 lruent->l_prev = (LRU_ENT *) NULL; 74 lruent->l_next = l->lru_head; 75 if (l->lru_head != (LRU_ENT *) NULL) 76 l->lru_head->l_prev = lruent; 77 l->lru_head = lruent; 78 if (l->lru_tail == (LRU_ENT *) NULL) 79 l->lru_tail = lruent; 80 81 /* add it to the hash table */ 82 ce = lruhashput(l, pgno, lruent); 83 l->lru_cursz++; 84 } else { 85 lruent = l->lru_tail; 86 87 /* find the oldest unused buffer */ 88 while (lruent != (LRU_ENT *) NULL 89 && !(lruent->l_flags & F_FREE)) 90 lruent = lruent->l_prev; 91 92 /* if no free buffer was found, we have to grow the cache */ 93 if (lruent == (LRU_ENT *) NULL) { 94 if (lrugrow(l) < 0) 95 return ((char *) NULL); 96 return ((*f)((LRU) l, pgno, nread)); 97 } 98 99 /* okay, found a free buffer -- update hash table and list */ 100 ce = lruhashget(l, lruent->l_pgno); 101 if (lruhashdel(l, lruent->l_pgno) < 0) 102 return ((char *) NULL); 103 104 /* flush the old page to disk, if necessary */ 105 if (lruent->l_flags & F_DIRTY) 106 if (lruflush(l, lruent) < 0) 107 return ((char *) NULL); 108 109 /* update stats, hash table, and list */ 110 lruent->l_pgno = pgno; 111 lruhead(l, lruent); 112 ce = lruhashput(l, pgno, lruent); 113 buffer = lruent->l_buffer; 114 } 115 #ifdef lint 116 ce = ce; 117 #endif /* lint */ 118 119 /* lock this page down */ 120 lruent->l_flags &= ~F_FREE; 121 122 return (buffer); 123 } 124 125 /* 126 * LRUHEAD -- Move an LRU list entry to the head of the list. 127 * 128 * The head of the list is where the most recently used item goes. 129 * 130 * Parameters: 131 * l -- LRU cache 132 * lruent -- entry to move to the head of the list 133 * 134 * Returns: 135 * None 136 * 137 * Side Effects: 138 * Updates the cache's head and tail pointers as required. 139 */ 140 141 void 142 lruhead(l, lruent) 143 LRUCACHE *l; 144 LRU_ENT *lruent; 145 { 146 LRU_ENT *next; 147 LRU_ENT *prev; 148 149 if (l->lru_head == lruent) 150 return; 151 152 next = lruent->l_next; 153 prev = lruent->l_prev; 154 lruent->l_prev = (LRU_ENT *) NULL; 155 lruent->l_next = l->lru_head; 156 l->lru_head->l_prev = lruent; 157 l->lru_head = lruent; 158 159 prev->l_next = next; 160 if (next != (LRU_ENT *) NULL) 161 next->l_prev = prev; 162 163 if (l->lru_tail == lruent) 164 l->lru_tail = prev; 165 } 166 167 /* 168 * LRUGROW -- Grow the LRU cache 169 * 170 * This routine is called only if we can't satisfy a user's get() request 171 * using an existing buffer. We need to rebuild the hash table so that 172 * subsequent lookups work correctly, since the cache size is used to 173 * compute hash keys. 174 * 175 * Parameters: 176 * l -- LRU cache to grow 177 * 178 * Returns: 179 * Zero on success, -1 on failure 180 */ 181 182 int 183 lrugrow(l) 184 LRUCACHE *l; 185 { 186 int oldsz, newsz; 187 CACHE_ENT **new; 188 CACHE_ENT *ce, *nce; 189 int h; 190 int i; 191 192 oldsz = l->lru_csize; 193 newsz = l->lru_csize + 1; 194 195 /* get a new hash table */ 196 if ((new = (CACHE_ENT **) malloc((unsigned)newsz * sizeof(CACHE_ENT *))) 197 == (CACHE_ENT **) NULL) 198 return (-1); 199 200 /* build the new hash table */ 201 bzero((char *) new, (size_t) (newsz * sizeof(CACHE_ENT *))); 202 for (i = oldsz; --i >= 0; ) { 203 for (ce = l->lru_cache[i]; ce != (CACHE_ENT *) NULL; ) { 204 nce = ce->c_chain; 205 h = ce->c_pgno % newsz; 206 ce->c_chain = new[h]; 207 new[h] = ce; 208 ce = nce; 209 } 210 } 211 212 /* get rid of the old hash table, and update the cache */ 213 free ((char *) (l->lru_cache)); 214 l->lru_cache = new; 215 l->lru_csize = newsz; 216 217 return (0); 218 } 219