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.2 (Berkeley) 02/21/94"; 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 if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL) 153 return (NULL); 154 if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) { 155 free(bp); 156 return (NULL); 157 } 158 if (hashp->nbufs) 159 hashp->nbufs--; 160 } else { 161 /* Kick someone out */ 162 BUF_REMOVE(bp); 163 /* 164 * If this is an overflow page with addr 0, it's already been 165 * flushed back in an overflow chain and initialized. 166 */ 167 if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) { 168 /* 169 * Set oaddr before __put_page so that you get it 170 * before bytes are swapped. 171 */ 172 shortp = (u_short *)bp->page; 173 if (shortp[0]) 174 oaddr = shortp[shortp[0] - 1]; 175 if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page, 176 bp->addr, (int)IS_BUCKET(bp->flags), 0)) 177 return (NULL); 178 /* 179 * Update the pointer to this page (i.e. invalidate it). 180 * 181 * If this is a new file (i.e. we created it at open 182 * time), make sure that we mark pages which have been 183 * written to disk so we retrieve them from disk later, 184 * rather than allocating new pages. 185 */ 186 if (IS_BUCKET(bp->flags)) { 187 segment_ndx = bp->addr & (hashp->SGSIZE - 1); 188 segp = hashp->dir[bp->addr >> hashp->SSHIFT]; 189 #ifdef DEBUG 190 assert(segp != NULL); 191 #endif 192 193 if (hashp->new_file && 194 ((bp->flags & BUF_MOD) || 195 ISDISK(segp[segment_ndx]))) 196 segp[segment_ndx] = (BUFHEAD *)BUF_DISK; 197 else 198 segp[segment_ndx] = NULL; 199 } 200 /* 201 * Since overflow pages can only be access by means of 202 * their bucket, free overflow pages associated with 203 * this bucket. 204 */ 205 for (xbp = bp; xbp->ovfl;) { 206 next_xbp = xbp->ovfl; 207 xbp->ovfl = 0; 208 xbp = next_xbp; 209 210 /* Check that ovfl pointer is up date. */ 211 if (IS_BUCKET(xbp->flags) || 212 (oaddr != xbp->addr)) 213 break; 214 215 shortp = (u_short *)xbp->page; 216 if (shortp[0]) 217 /* set before __put_page */ 218 oaddr = shortp[shortp[0] - 1]; 219 if ((xbp->flags & BUF_MOD) && __put_page(hashp, 220 xbp->page, xbp->addr, 0, 0)) 221 return (NULL); 222 xbp->addr = 0; 223 xbp->flags = 0; 224 BUF_REMOVE(xbp); 225 LRU_INSERT(xbp); 226 } 227 } 228 } 229 230 /* Now assign this buffer */ 231 bp->addr = addr; 232 #ifdef DEBUG1 233 (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", 234 bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); 235 #endif 236 bp->ovfl = NULL; 237 if (prev_bp) { 238 /* 239 * If prev_bp is set, this is an overflow page, hook it in to 240 * the buffer overflow links. 241 */ 242 #ifdef DEBUG1 243 (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n", 244 prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0), 245 (bp ? bp->addr : 0)); 246 #endif 247 prev_bp->ovfl = bp; 248 bp->flags = 0; 249 } else 250 bp->flags = BUF_BUCKET; 251 MRU_INSERT(bp); 252 return (bp); 253 } 254 255 extern void 256 __buf_init(hashp, nbytes) 257 HTAB *hashp; 258 int nbytes; 259 { 260 BUFHEAD *bfp; 261 int npages; 262 263 bfp = &(hashp->bufhead); 264 npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT; 265 npages = MAX(npages, MIN_BUFFERS); 266 267 hashp->nbufs = npages; 268 bfp->next = bfp; 269 bfp->prev = bfp; 270 /* 271 * This space is calloc'd so these are already null. 272 * 273 * bfp->ovfl = NULL; 274 * bfp->flags = 0; 275 * bfp->page = NULL; 276 * bfp->addr = 0; 277 */ 278 } 279 280 extern int 281 __buf_free(hashp, do_free, to_disk) 282 HTAB *hashp; 283 int do_free, to_disk; 284 { 285 BUFHEAD *bp; 286 287 /* Need to make sure that buffer manager has been initialized */ 288 if (!LRU) 289 return (0); 290 for (bp = LRU; bp != &hashp->bufhead;) { 291 /* Check that the buffer is valid */ 292 if (bp->addr || IS_BUCKET(bp->flags)) { 293 if (to_disk && (bp->flags & BUF_MOD) && 294 __put_page(hashp, bp->page, 295 bp->addr, IS_BUCKET(bp->flags), 0)) 296 return (-1); 297 } 298 /* Check if we are freeing stuff */ 299 if (do_free) { 300 if (bp->page) 301 free(bp->page); 302 BUF_REMOVE(bp); 303 free(bp); 304 bp = LRU; 305 } else 306 bp = bp->prev; 307 } 308 return (0); 309 } 310 311 extern void 312 __reclaim_buf(hashp, bp) 313 HTAB *hashp; 314 BUFHEAD *bp; 315 { 316 bp->ovfl = 0; 317 bp->addr = 0; 318 bp->flags = 0; 319 BUF_REMOVE(bp); 320 LRU_INSERT(bp); 321 } 322