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