db/hash/hash_buf.c

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