1 /*- 2 * Copyright (c) 1990, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Margo Seltzer. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)hash_buf.c 8.1 (Berkeley) 06/04/93"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 /* 16 * PACKAGE: hash 17 * 18 * DESCRIPTION: 19 * Contains buffer management 20 * 21 * ROUTINES: 22 * External 23 * __buf_init 24 * __get_buf 25 * __buf_free 26 * __reclaim_buf 27 * Internal 28 * newbuf 29 */ 30 31 #include <sys/param.h> 32 33 #include <errno.h> 34 #include <stdio.h> 35 #include <stdlib.h> 36 #ifdef DEBUG 37 #include <assert.h> 38 #endif 39 40 #include <db.h> 41 #include "hash.h" 42 #include "page.h" 43 #include "extern.h" 44 45 static BUFHEAD *newbuf __P((HTAB *, u_int, BUFHEAD *)); 46 47 /* Unlink B from its place in the lru */ 48 #define BUF_REMOVE(B) { \ 49 (B)->prev->next = (B)->next; \ 50 (B)->next->prev = (B)->prev; \ 51 } 52 53 /* Insert B after P */ 54 #define BUF_INSERT(B, P) { \ 55 (B)->next = (P)->next; \ 56 (B)->prev = (P); \ 57 (P)->next = (B); \ 58 (B)->next->prev = (B); \ 59 } 60 61 #define MRU hashp->bufhead.next 62 #define LRU hashp->bufhead.prev 63 64 #define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead) 65 #define LRU_INSERT(B) BUF_INSERT((B), LRU) 66 67 /* 68 * We are looking for a buffer with address "addr". If prev_bp is NULL, then 69 * address is a bucket index. If prev_bp is not NULL, then it points to the 70 * page previous to an overflow page that we are trying to find. 71 * 72 * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer 73 * be valid. Therefore, you must always verify that its address matches the 74 * address you are seeking. 75 */ 76 extern BUFHEAD * 77 __get_buf(hashp, addr, prev_bp, newpage) 78 HTAB *hashp; 79 u_int addr; 80 BUFHEAD *prev_bp; 81 int newpage; /* If prev_bp set, indicates a new overflow page. */ 82 { 83 register BUFHEAD *bp; 84 register u_int is_disk_mask; 85 register int is_disk, segment_ndx; 86 SEGMENT segp; 87 88 is_disk = 0; 89 is_disk_mask = 0; 90 if (prev_bp) { 91 bp = prev_bp->ovfl; 92 if (!bp || (bp->addr != addr)) 93 bp = NULL; 94 if (!newpage) 95 is_disk = BUF_DISK; 96 } else { 97 /* Grab buffer out of directory */ 98 segment_ndx = addr & (hashp->SGSIZE - 1); 99 100 /* valid segment ensured by __call_hash() */ 101 segp = hashp->dir[addr >> hashp->SSHIFT]; 102 #ifdef DEBUG 103 assert(segp != NULL); 104 #endif 105 bp = PTROF(segp[segment_ndx]); 106 is_disk_mask = ISDISK(segp[segment_ndx]); 107 is_disk = is_disk_mask || !hashp->new_file; 108 } 109 110 if (!bp) { 111 bp = newbuf(hashp, addr, prev_bp); 112 if (!bp || 113 __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0)) 114 return (NULL); 115 if (!prev_bp) 116 segp[segment_ndx] = 117 (BUFHEAD *)((u_int)bp | is_disk_mask); 118 } else { 119 BUF_REMOVE(bp); 120 MRU_INSERT(bp); 121 } 122 return (bp); 123 } 124 125 /* 126 * We need a buffer for this page. Either allocate one, or evict a resident 127 * one (if we have as many buffers as we're allowed) and put this one in. 128 * 129 * If newbuf finds an error (returning NULL), it also sets errno. 130 */ 131 static BUFHEAD * 132 newbuf(hashp, addr, prev_bp) 133 HTAB *hashp; 134 u_int addr; 135 BUFHEAD *prev_bp; 136 { 137 register BUFHEAD *bp; /* The buffer we're going to use */ 138 register BUFHEAD *xbp; /* Temp pointer */ 139 register BUFHEAD *next_xbp; 140 SEGMENT segp; 141 int segment_ndx; 142 u_short oaddr, *shortp; 143 144 oaddr = 0; 145 bp = LRU; 146 /* 147 * If LRU buffer is pinned, the buffer pool is too small. We need to 148 * allocate more buffers. 149 */ 150 if (hashp->nbufs || (bp->flags & BUF_PIN)) { 151 /* Allocate a new one */ 152 bp = malloc(sizeof(struct _bufhead)); 153 if (!bp || !(bp->page = malloc(hashp->BSIZE))) 154 return (NULL); 155 if (hashp->nbufs) 156 hashp->nbufs--; 157 } else { 158 /* Kick someone out */ 159 BUF_REMOVE(bp); 160 /* 161 * If this is an overflow page with addr 0, it's already been 162 * flushed back in an overflow chain and initialized. 163 */ 164 if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) { 165 /* 166 * Set oaddr before __put_page so that you get it 167 * before bytes are swapped. 168 */ 169 shortp = (u_short *)bp->page; 170 if (shortp[0]) 171 oaddr = shortp[shortp[0] - 1]; 172 if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page, 173 bp->addr, (int)IS_BUCKET(bp->flags), 0)) 174 return (NULL); 175 /* 176 * Update the pointer to this page (i.e. invalidate it). 177 * 178 * If this is a new file (i.e. we created it at open 179 * time), make sure that we mark pages which have been 180 * written to disk so we retrieve them from disk later, 181 * rather than allocating new pages. 182 */ 183 if (IS_BUCKET(bp->flags)) { 184 segment_ndx = bp->addr & (hashp->SGSIZE - 1); 185 segp = hashp->dir[bp->addr >> hashp->SSHIFT]; 186 #ifdef DEBUG 187 assert(segp != NULL); 188 #endif 189 190 if (hashp->new_file && 191 ((bp->flags & BUF_MOD) || 192 ISDISK(segp[segment_ndx]))) 193 segp[segment_ndx] = (BUFHEAD *)BUF_DISK; 194 else 195 segp[segment_ndx] = NULL; 196 } 197 /* 198 * Since overflow pages can only be access by means of 199 * their bucket, free overflow pages associated with 200 * this bucket. 201 */ 202 for (xbp = bp; xbp->ovfl;) { 203 next_xbp = xbp->ovfl; 204 xbp->ovfl = 0; 205 xbp = next_xbp; 206 207 /* Check that ovfl pointer is up date. */ 208 if (IS_BUCKET(xbp->flags) || 209 (oaddr != xbp->addr)) 210 break; 211 212 shortp = (u_short *)xbp->page; 213 if (shortp[0]) 214 /* set before __put_page */ 215 oaddr = shortp[shortp[0] - 1]; 216 if ((xbp->flags & BUF_MOD) && __put_page(hashp, 217 xbp->page, xbp->addr, 0, 0)) 218 return (NULL); 219 xbp->addr = 0; 220 xbp->flags = 0; 221 BUF_REMOVE(xbp); 222 LRU_INSERT(xbp); 223 } 224 } 225 } 226 227 /* Now assign this buffer */ 228 bp->addr = addr; 229 #ifdef DEBUG1 230 (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", 231 bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); 232 #endif 233 bp->ovfl = NULL; 234 if (prev_bp) { 235 /* 236 * If prev_bp is set, this is an overflow page, hook it in to 237 * the buffer overflow links. 238 */ 239 #ifdef DEBUG1 240 (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n", 241 prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0), 242 (bp ? bp->addr : 0)); 243 #endif 244 prev_bp->ovfl = bp; 245 bp->flags = 0; 246 } else 247 bp->flags = BUF_BUCKET; 248 MRU_INSERT(bp); 249 return (bp); 250 } 251 252 extern void 253 __buf_init(hashp, nbytes) 254 HTAB *hashp; 255 int nbytes; 256 { 257 BUFHEAD *bfp; 258 int npages; 259 260 bfp = &(hashp->bufhead); 261 npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT; 262 npages = MAX(npages, MIN_BUFFERS); 263 264 hashp->nbufs = npages; 265 bfp->next = bfp; 266 bfp->prev = bfp; 267 /* 268 * This space is calloc'd so these are already null. 269 * 270 * bfp->ovfl = NULL; 271 * bfp->flags = 0; 272 * bfp->page = NULL; 273 * bfp->addr = 0; 274 */ 275 } 276 277 extern int 278 __buf_free(hashp, do_free, to_disk) 279 HTAB *hashp; 280 int do_free, to_disk; 281 { 282 BUFHEAD *bp; 283 284 /* Need to make sure that buffer manager has been initialized */ 285 if (!LRU) 286 return (0); 287 for (bp = LRU; bp != &hashp->bufhead;) { 288 /* Check that the buffer is valid */ 289 if (bp->addr || IS_BUCKET(bp->flags)) { 290 if (to_disk && (bp->flags & BUF_MOD) && 291 __put_page(hashp, bp->page, 292 bp->addr, IS_BUCKET(bp->flags), 0)) 293 return (-1); 294 } 295 /* Check if we are freeing stuff */ 296 if (do_free) { 297 if (bp->page) 298 free(bp->page); 299 BUF_REMOVE(bp); 300 free(bp); 301 bp = LRU; 302 } else 303 bp = bp->prev; 304 } 305 return (0); 306 } 307 308 extern void 309 __reclaim_buf(hashp, bp) 310 HTAB *hashp; 311 BUFHEAD *bp; 312 { 313 bp->ovfl = 0; 314 bp->addr = 0; 315 bp->flags = 0; 316 BUF_REMOVE(bp); 317 LRU_INSERT(bp); 318 } 319