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