db/hash/hash_buf.c

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