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