db.subproj/hash.subproj/hash_buf.c

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