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