lib/libc/db/hash/buf.c

   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  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if defined(LIBC_SCCS) && !defined(lint)
  38 static char sccsid[] = "@(#)buf.c       5.7 (Berkeley) 3/12/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 /******************************************************************************
  42
  43 PACKAGE: hash
  44
  45 DESCRIPTION:
  46         Contains buffer management
  47
  48 ROUTINES:
  49     External
  50         __buf_init
  51         __get_buf
  52         __buf_free
  53         __reclaim_buf
  54     Internal
  55         newbuf
  56
  57 ******************************************************************************/
  58 #include <sys/param.h>
  59 #include <assert.h>
  60 #include <errno.h>
  61 #include <stdio.h>
  62 #include <stdlib.h>
  63 #include "hash.h"
  64
  65 /* Externals */
  66 extern HTAB     *hashp;
  67
  68 /* My internals */
  69 static BUFHEAD *newbuf();
  70
  71 /* Unlink B from its place in the lru */
  72 #define BUF_REMOVE(B)                   \
  73 {                                       \
  74     B->prev->next = B->next;            \
  75     B->next->prev = B->prev;            \
  76 }
  77
  78 /* Insert B after P */
  79 #define BUF_INSERT(B,P)                 \
  80 {                                       \
  81     B->next = P->next;                  \
  82     B->prev = P;                        \
  83     P->next = B;                        \
  84     B->next->prev = B;                  \
  85 }
  86
  87 #define MRU     hashp->bufhead.next
  88 #define LRU     hashp->bufhead.prev
  89
  90 #define MRU_INSERT(B)   BUF_INSERT(B,(&hashp->bufhead))
  91 #define LRU_INSERT(B)   BUF_INSERT(B,LRU)
  92
  93 /*
  94     We are looking for a buffer with address "addr".
  95     If prev_bp is NULL, then address is a bucket index.
  96     If prev_bp is not NULL, then it points to the page previous
  97         to an overflow page that we are trying to find.
  98
  99     CAVEAT:  The buffer header accessed via prev_bp's ovfl field
 100     may no longer be valid.  Therefore, you must always verify that
 101     its address matches the address you are seeking.
 102 */
 103 extern BUFHEAD *
 104 __get_buf ( addr, prev_bp, newpage )
 105 u_int   addr;
 106 BUFHEAD *prev_bp;
 107 int     newpage;                /* If prev_bp is set, indicates that this is
 108                                         a new overflow page */
 109 {
 110     register int        segment_ndx;
 111     register    BUFHEAD *bp;
 112     register    unsigned        is_disk = 0;
 113     register    unsigned        is_disk_mask = 0;
 114     SEGMENT     segp;
 115
 116     if ( prev_bp ) {
 117         bp = prev_bp->ovfl;
 118         if ( !bp || (bp->addr != addr) ) bp = NULL;
 119         if ( !newpage ) is_disk = BUF_DISK;
 120     }
 121     else {
 122         /* Grab buffer out of directory */
 123         segment_ndx = addr & ( hashp->SGSIZE - 1 );
 124
 125         /*
 126          * valid segment ensured by __call_hash()
 127          */
 128         segp = hashp->dir[addr >> hashp->SSHIFT];
 129 #ifdef DEBUG
 130         assert(segp != NULL);
 131 #endif
 132         bp = PTROF(segp[segment_ndx]);
 133         is_disk_mask = ISDISK(segp[segment_ndx]);
 134         is_disk = is_disk_mask || !hashp->new_file;
 135     }
 136
 137     if ( !bp ) {
 138         bp = newbuf ( addr, prev_bp );
 139         if ( !bp || __get_page ( bp->page, addr, !prev_bp, is_disk, 0 )) {
 140             return(NULL);
 141         }
 142         if ( !prev_bp ) {
 143             segp[segment_ndx] = (BUFHEAD *)((unsigned)bp | is_disk_mask );
 144         }
 145     } else {
 146         BUF_REMOVE ( bp );
 147         MRU_INSERT ( bp );
 148     }
 149     return(bp);
 150 }
 151
 152 /*
 153     We need a buffer for this page. Either allocate one, or
 154     evict a resident one (if we have as many buffers as we're
 155     allowed) and put this one in.
 156
 157     If newbuf finds an error (returning NULL), it also sets errno
 158 */
 159 static BUFHEAD *
 160 newbuf ( addr, prev_bp )
 161 u_int   addr;
 162 BUFHEAD *prev_bp;
 163 {
 164     register    BUFHEAD *bp;    /* The buffer we're going to use */
 165     register    BUFHEAD *xbp;   /* Temp pointer */
 166     register    BUFHEAD *next_xbp;
 167     int segment_ndx;
 168     u_short     *shortp;
 169     u_short     oaddr;
 170     SEGMENT     segp;
 171
 172     oaddr = 0;
 173     bp = LRU;
 174     /*
 175         If LRU buffer is pinned, the buffer pool is too small.
 176         We need to allocate more buffers
 177     */
 178     if ( hashp->nbufs || (bp->flags & BUF_PIN) ) {
 179         /* Allocate a new one */
 180         bp = (BUFHEAD *)malloc ( sizeof (struct _bufhead) );
 181         if ( !bp || !(bp->page = (char *)malloc ( hashp->BSIZE )) ) {
 182             return (NULL);
 183         }
 184         hashp->nbufs--;
 185     } else {
 186         /* Kick someone out */
 187         BUF_REMOVE( bp );
 188         /*
 189             If this is an overflow page with addr 0, it's already
 190             been flushed back in an overflow chain and initialized
 191         */
 192         if ( (bp->addr != 0) || (bp->flags & BUF_BUCKET) ) {
 193             /*
 194                 Set oaddr before __put_page so that you get it
 195                 before bytes are swapped
 196             */
 197             shortp = (u_short *)bp->page;
 198             if ( shortp[0] ) {
 199                 oaddr = shortp[shortp[0]-1];
 200             }
 201             if ( (bp->flags & BUF_MOD) &&
 202                  __put_page(bp->page, bp->addr, (int)IS_BUCKET(bp->flags), 0) ) {
 203                 return(NULL);
 204             }
 205             /*
 206                 Update the pointer to this page (i.e. invalidate it).
 207
 208                 If this is a new file (i.e. we created it at open time),
 209                 make sure that we mark pages which have been written to
 210                 disk so we retrieve them from disk later, rather than
 211                 allocating new pages.
 212             */
 213
 214             if ( IS_BUCKET(bp->flags)) {
 215                 segment_ndx = bp->addr & ( hashp->SGSIZE - 1 );
 216
 217                 segp = hashp->dir[bp->addr >> hashp->SSHIFT];
 218
 219                 assert(segp != NULL);
 220
 221                 if ( hashp->new_file &&
 222                      ((bp->flags & BUF_MOD) || ISDISK(segp[segment_ndx])) ) {
 223                     segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
 224                 } else segp[segment_ndx] = NULL;
 225             }
 226
 227             /*
 228                 Since overflow pages can only be access by means of
 229                 their bucket, free overflow pages associated with this
 230                 bucket.
 231             */
 232             for ( xbp = bp; xbp->ovfl; ) {
 233
 234                 next_xbp = xbp->ovfl;
 235                 xbp->ovfl = 0;
 236                 xbp = next_xbp;
 237
 238                 /* Check that ovfl pointer is up date */
 239                 if ( IS_BUCKET(xbp->flags) || (oaddr != xbp->addr) ) break;
 240
 241                 shortp = (u_short *)xbp->page;
 242                 if ( shortp[0] ) {
 243                     oaddr = shortp[shortp[0]-1];  /* set before __put_page */
 244                 }
 245                 if ( (xbp->flags & BUF_MOD) &&
 246                     __put_page ( xbp->page, xbp->addr, 0, 0 ) ) {
 247                     return(NULL);
 248                 }
 249                 xbp->addr = 0;
 250                 xbp->flags = 0;
 251                 BUF_REMOVE ( xbp );
 252                 LRU_INSERT ( xbp );
 253             }
 254         }
 255     }
 256
 257     /* Now assign this buffer */
 258     bp->addr = addr;
 259 #ifdef DEBUG1
 260     fprintf ( stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", bp->addr,
 261                 (bp->ovfl?bp->ovfl->addr:0),  0);
 262 #endif
 263     bp->ovfl = NULL;
 264     if ( prev_bp ) {
 265         /*
 266             If prev_bp is set, this is an overflow page, hook it in to the
 267             buffer overflow links
 268         */
 269 #ifdef DEBUG1
 270         fprintf ( stderr, "NEWBUF2: %d->ovfl was %d is now %d\n", prev_bp->addr,
 271                     (prev_bp->ovfl?bp->ovfl->addr:0),
 272                     (bp?bp->addr: 0));
 273 #endif
 274         prev_bp->ovfl = bp;
 275         bp->flags = 0;
 276     } else bp->flags = BUF_BUCKET;
 277     MRU_INSERT ( bp );
 278     return ( bp );
 279 }
 280
 281 extern void
 282 __buf_init ( nbytes )
 283 int     nbytes;
 284 {
 285     int npages;
 286     BUFHEAD     *bfp = &(hashp->bufhead);
 287
 288     npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
 289     npages = MAX ( npages, MIN_BUFFERS );
 290
 291     hashp->nbufs = npages;
 292     bfp->next = bfp;
 293     bfp->prev = bfp;
 294     /*
 295         This space is calloc'd so these are already null
 296
 297         bfp->ovfl = NULL;
 298         bfp->flags = 0;
 299         bfp->page = NULL;
 300         bfp->addr = 0;
 301     */
 302 }
 303
 304 extern int
 305 __buf_free ( do_free, to_disk )
 306 int     do_free;
 307 int     to_disk;
 308 {
 309     BUFHEAD     *bp;
 310
 311     /* Need to make sure that buffer manager has been initialized */
 312     if ( !LRU ) {
 313         return(0);
 314     }
 315
 316     for ( bp = LRU; bp != &hashp->bufhead; ) {
 317         /* Check that the buffer is valid */
 318         if ( bp->addr || IS_BUCKET(bp->flags) ) {
 319             if ( to_disk && (bp->flags & BUF_MOD) &&
 320                  __put_page (bp->page, bp->addr, IS_BUCKET(bp->flags), 0 )) {
 321                 return (-1);
 322             }
 323         }
 324
 325         /* Check if we are freeing stuff */
 326         if ( do_free ) {
 327             if ( bp->page ) free ( bp->page );
 328             BUF_REMOVE(bp);
 329             (void)free ( bp );
 330             bp = LRU;
 331         } else bp = bp->prev;
 332     }
 333
 334     return(0);
 335 }
 336
 337 extern void
 338 __reclaim_buf ( bp )
 339 BUFHEAD *bp;
 340 {
 341     bp->ovfl = 0;
 342     bp->addr = 0;
 343     bp->flags = 0;
 344     BUF_REMOVE ( bp );
 345     LRU_INSERT ( bp );
 346 }