db.subproj/mpool.subproj/mpool.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  * Redistribution and use in source and binary forms, with or without
  27  * modification, are permitted provided that the following conditions
  28  * are met:
  29  * 1. Redistributions of source code must retain the above copyright
  30  *    notice, this list of conditions and the following disclaimer.
  31  * 2. Redistributions in binary form must reproduce the above copyright
  32  *    notice, this list of conditions and the following disclaimer in the
  33  *    documentation and/or other materials provided with the distribution.
  34  * 3. All advertising materials mentioning features or use of this software
  35  *    must display the following acknowledgement:
  36  *      This product includes software developed by the University of
  37  *      California, Berkeley and its contributors.
  38  * 4. Neither the name of the University nor the names of its contributors
  39  *    may be used to endorse or promote products derived from this software
  40  *    without specific prior written permission.
  41  *
  42  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  43  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  44  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  45  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  46  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  47  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  48  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  49  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  50  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  51  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  52  * SUCH DAMAGE.
  53  */
  54
  55
  56 #include <sys/param.h>
  57 #include <sys/stat.h>
  58
  59 #include <errno.h>
  60 #include <stdio.h>
  61 #include <stdlib.h>
  62 #include <string.h>
  63 #include <unistd.h>
  64
  65 #include <db.h>
  66 #define __MPOOLINTERFACE_PRIVATE
  67 #include "mpool.h"
  68
  69 static BKT *mpool_bkt __P((MPOOL *));
  70 static BKT *mpool_look __P((MPOOL *, pgno_t));
  71 static int  mpool_write __P((MPOOL *, BKT *));
  72 #ifdef DEBUG
  73 static void __mpoolerr __P((const char *fmt, ...));
  74 #endif
  75
  76 /*
  77  * MPOOL_OPEN -- initialize a memory pool.
  78  *
  79  * Parameters:
  80  *      key:            Shared buffer key.
  81  *      fd:             File descriptor.
  82  *      pagesize:       File page size.
  83  *      maxcache:       Max number of cached pages.
  84  *
  85  * Returns:
  86  *      MPOOL pointer, NULL on error.
  87  */
  88 MPOOL *
  89 mpool_open(key, fd, pagesize, maxcache)
  90         DBT *key;
  91         int fd;
  92         pgno_t pagesize, maxcache;
  93 {
  94         struct stat sb;
  95         MPOOL *mp;
  96         int entry;
  97
  98         if (fstat(fd, &sb))
  99                 return (NULL);
 100         /* XXX
 101          * We should only set st_size to 0 for pipes -- 4.4BSD has the fix so
 102          * that stat(2) returns true for ISSOCK on pipes.  Until then, this is
 103          * fairly close.
 104          */
 105         if (!S_ISREG(sb.st_mode)) {
 106                 errno = ESPIPE;
 107                 return (NULL);
 108         }
 109
 110         if ((mp = (MPOOL *)malloc(sizeof(MPOOL))) == NULL)
 111                 return (NULL);
 112         mp->free.cnext = mp->free.cprev = (BKT *)&mp->free;
 113         mp->lru.cnext = mp->lru.cprev = (BKT *)&mp->lru;
 114         for (entry = 0; entry < HASHSIZE; ++entry)
 115                 mp->hashtable[entry].hnext = mp->hashtable[entry].hprev =
 116                     mp->hashtable[entry].cnext = mp->hashtable[entry].cprev =
 117                     (BKT *)&mp->hashtable[entry];
 118         mp->curcache = 0;
 119         mp->maxcache = maxcache;
 120         mp->pagesize = pagesize;
 121         mp->npages = sb.st_size / pagesize;
 122         mp->fd = fd;
 123         mp->pgcookie = NULL;
 124         mp->pgin = mp->pgout = NULL;
 125
 126 #ifdef STATISTICS
 127         mp->cachehit = mp->cachemiss = mp->pagealloc = mp->pageflush =
 128             mp->pageget = mp->pagenew = mp->pageput = mp->pageread =
 129             mp->pagewrite = 0;
 130 #endif
 131         return (mp);
 132 }
 133
 134 /*
 135  * MPOOL_FILTER -- initialize input/output filters.
 136  *
 137  * Parameters:
 138  *      pgin:           Page in conversion routine.
 139  *      pgout:          Page out conversion routine.
 140  *      pgcookie:       Cookie for page in/out routines.
 141  */
 142 void
 143 mpool_filter(mp, pgin, pgout, pgcookie)
 144         MPOOL *mp;
 145         void (*pgin) __P((void *, pgno_t, void *));
 146         void (*pgout) __P((void *, pgno_t, void *));
 147         void *pgcookie;
 148 {
 149         mp->pgin = pgin;
 150         mp->pgout = pgout;
 151         mp->pgcookie = pgcookie;
 152 }
 153
 154 /*
 155  * MPOOL_NEW -- get a new page
 156  *
 157  * Parameters:
 158  *      mp:             mpool cookie
 159  *      pgnoadddr:      place to store new page number
 160  * Returns:
 161  *      RET_ERROR, RET_SUCCESS
 162  */
 163 void *
 164 mpool_new(mp, pgnoaddr)
 165         MPOOL *mp;
 166         pgno_t *pgnoaddr;
 167 {
 168         BKT *b;
 169         BKTHDR *hp;
 170
 171 #ifdef STATISTICS
 172         ++mp->pagenew;
 173 #endif
 174         /*
 175          * Get a BKT from the cache.  Assign a new page number, attach it to
 176          * the hash and lru chains and return.
 177          */
 178         if ((b = mpool_bkt(mp)) == NULL)
 179                 return (NULL);
 180         *pgnoaddr = b->pgno = mp->npages++;
 181         b->flags = MPOOL_PINNED;
 182         inshash(b, b->pgno);
 183         inschain(b, &mp->lru);
 184         return (b->page);
 185 }
 186
 187 /*
 188  * MPOOL_GET -- get a page from the pool
 189  *
 190  * Parameters:
 191  *      mp:     mpool cookie
 192  *      pgno:   page number
 193  *      flags:  not used
 194  *
 195  * Returns:
 196  *      RET_ERROR, RET_SUCCESS
 197  */
 198 void *
 199 mpool_get(mp, pgno, flags)
 200         MPOOL *mp;
 201         pgno_t pgno;
 202         u_int flags;            /* XXX not used? */
 203 {
 204         BKT *b;
 205         BKTHDR *hp;
 206         off_t off;
 207         int nr;
 208
 209         /*
 210          * If asking for a specific page that is already in the cache, find
 211          * it and return it.
 212          */
 213         if (b = mpool_look(mp, pgno)) {
 214 #ifdef STATISTICS
 215                 ++mp->pageget;
 216 #endif
 217 #ifdef DEBUG
 218                 if (b->flags & MPOOL_PINNED)
 219                         __mpoolerr("mpool_get: page %d already pinned",
 220                             b->pgno);
 221 #endif
 222                 rmchain(b);
 223                 inschain(b, &mp->lru);
 224                 b->flags |= MPOOL_PINNED;
 225                 return (b->page);
 226         }
 227
 228         /* Not allowed to retrieve a non-existent page. */
 229         if (pgno >= mp->npages) {
 230                 errno = EINVAL;
 231                 return (NULL);
 232         }
 233
 234         /* Get a page from the cache. */
 235         if ((b = mpool_bkt(mp)) == NULL)
 236                 return (NULL);
 237         b->pgno = pgno;
 238         b->flags = MPOOL_PINNED;
 239
 240 #ifdef STATISTICS
 241         ++mp->pageread;
 242 #endif
 243         /* Read in the contents. */
 244         off = mp->pagesize * pgno;
 245         if (lseek(mp->fd, off, SEEK_SET) != off)
 246                 return (NULL);
 247         if ((nr = read(mp->fd, b->page, mp->pagesize)) != mp->pagesize) {
 248                 if (nr >= 0)
 249                         errno = EFTYPE;
 250                 return (NULL);
 251         }
 252         if (mp->pgin)
 253                 (mp->pgin)(mp->pgcookie, b->pgno, b->page);
 254
 255         inshash(b, b->pgno);
 256         inschain(b, &mp->lru);
 257 #ifdef STATISTICS
 258         ++mp->pageget;
 259 #endif
 260         return (b->page);
 261 }
 262
 263 /*
 264  * MPOOL_PUT -- return a page to the pool
 265  *
 266  * Parameters:
 267  *      mp:     mpool cookie
 268  *      page:   page pointer
 269  *      pgno:   page number
 270  *
 271  * Returns:
 272  *      RET_ERROR, RET_SUCCESS
 273  */
 274 int
 275 mpool_put(mp, page, flags)
 276         MPOOL *mp;
 277         void *page;
 278         u_int flags;
 279 {
 280         BKT *baddr;
 281 #ifdef DEBUG
 282         BKT *b;
 283 #endif
 284
 285 #ifdef STATISTICS
 286         ++mp->pageput;
 287 #endif
 288         baddr = (BKT *)((char *)page - sizeof(BKT));
 289 #ifdef DEBUG
 290         if (!(baddr->flags & MPOOL_PINNED))
 291                 __mpoolerr("mpool_put: page %d not pinned", b->pgno);
 292         for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
 293                 if (b == (BKT *)&mp->lru)
 294                         __mpoolerr("mpool_put: %0x: bad address", baddr);
 295                 if (b == baddr)
 296                         break;
 297         }
 298 #endif
 299         baddr->flags &= ~MPOOL_PINNED;
 300         baddr->flags |= flags & MPOOL_DIRTY;
 301         return (RET_SUCCESS);
 302 }
 303
 304 /*
 305  * MPOOL_CLOSE -- close the buffer pool
 306  *
 307  * Parameters:
 308  *      mp:     mpool cookie
 309  *
 310  * Returns:
 311  *      RET_ERROR, RET_SUCCESS
 312  */
 313 int
 314 mpool_close(mp)
 315         MPOOL *mp;
 316 {
 317         BKT *b, *next;
 318
 319         /* Free up any space allocated to the lru pages. */
 320         for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = next) {
 321                 next = b->cprev;
 322                 free(b);
 323         }
 324         free(mp);
 325         return (RET_SUCCESS);
 326 }
 327
 328 /*
 329  * MPOOL_SYNC -- sync the file to disk.
 330  *
 331  * Parameters:
 332  *      mp:     mpool cookie
 333  *
 334  * Returns:
 335  *      RET_ERROR, RET_SUCCESS
 336  */
 337 int
 338 mpool_sync(mp)
 339         MPOOL *mp;
 340 {
 341         BKT *b;
 342
 343         for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
 344                 if (b->flags & MPOOL_DIRTY && mpool_write(mp, b) == RET_ERROR)
 345                         return (RET_ERROR);
 346         return (fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
 347 }
 348
 349 /*
 350  * MPOOL_BKT -- get/create a BKT from the cache
 351  *
 352  * Parameters:
 353  *      mp:     mpool cookie
 354  *
 355  * Returns:
 356  *      NULL on failure and a pointer to the BKT on success
 357  */
 358 static BKT *
 359 mpool_bkt(mp)
 360         MPOOL *mp;
 361 {
 362         BKT *b;
 363
 364         if (mp->curcache < mp->maxcache)
 365                 goto new;
 366
 367         /*
 368          * If the cache is maxxed out, search the lru list for a buffer we
 369          * can flush.  If we find one, write it if necessary and take it off
 370          * any lists.  If we don't find anything we grow the cache anyway.
 371          * The cache never shrinks.
 372          */
 373         for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
 374                 if (!(b->flags & MPOOL_PINNED)) {
 375                         if (b->flags & MPOOL_DIRTY &&
 376                             mpool_write(mp, b) == RET_ERROR)
 377                                 return (NULL);
 378                         rmhash(b);
 379                         rmchain(b);
 380 #ifdef STATISTICS
 381                         ++mp->pageflush;
 382 #endif
 383 #ifdef DEBUG
 384                         {
 385                                 void *spage;
 386                                 spage = b->page;
 387                                 memset(b, 0xff, sizeof(BKT) + mp->pagesize);
 388                                 b->page = spage;
 389                         }
 390 #endif
 391                         return (b);
 392                 }
 393
 394 new:    if ((b = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
 395                 return (NULL);
 396 #ifdef STATISTICS
 397         ++mp->pagealloc;
 398 #endif
 399 #ifdef DEBUG
 400         memset(b, 0xff, sizeof(BKT) + mp->pagesize);
 401 #endif
 402         b->page = (char *)b + sizeof(BKT);
 403         ++mp->curcache;
 404         return (b);
 405 }
 406
 407 /*
 408  * MPOOL_WRITE -- sync a page to disk
 409  *
 410  * Parameters:
 411  *      mp:     mpool cookie
 412  *
 413  * Returns:
 414  *      RET_ERROR, RET_SUCCESS
 415  */
 416 static int
 417 mpool_write(mp, b)
 418         MPOOL *mp;
 419         BKT *b;
 420 {
 421         off_t off;
 422
 423         if (mp->pgout)
 424                 (mp->pgout)(mp->pgcookie, b->pgno, b->page);
 425
 426 #ifdef STATISTICS
 427         ++mp->pagewrite;
 428 #endif
 429         off = mp->pagesize * b->pgno;
 430         if (lseek(mp->fd, off, SEEK_SET) != off)
 431                 return (RET_ERROR);
 432         if (write(mp->fd, b->page, mp->pagesize) != mp->pagesize)
 433                 return (RET_ERROR);
 434         b->flags &= ~MPOOL_DIRTY;
 435         return (RET_SUCCESS);
 436 }
 437
 438 /*
 439  * MPOOL_LOOK -- lookup a page
 440  *
 441  * Parameters:
 442  *      mp:     mpool cookie
 443  *      pgno:   page number
 444  *
 445  * Returns:
 446  *      NULL on failure and a pointer to the BKT on success
 447  */
 448 static BKT *
 449 mpool_look(mp, pgno)
 450         MPOOL *mp;
 451         pgno_t pgno;
 452 {
 453         register BKT *b;
 454         register BKTHDR *tb;
 455
 456         /* XXX
 457          * If find the buffer, put it first on the hash chain so can
 458          * find it again quickly.
 459          */
 460         tb = &mp->hashtable[HASHKEY(pgno)];
 461         for (b = tb->hnext; b != (BKT *)tb; b = b->hnext)
 462                 if (b->pgno == pgno) {
 463 #ifdef STATISTICS
 464                         ++mp->cachehit;
 465 #endif
 466                         return (b);
 467                 }
 468 #ifdef STATISTICS
 469         ++mp->cachemiss;
 470 #endif
 471         return (NULL);
 472 }
 473
 474 #ifdef STATISTICS
 475 /*
 476  * MPOOL_STAT -- cache statistics
 477  *
 478  * Parameters:
 479  *      mp:     mpool cookie
 480  */
 481 void
 482 mpool_stat(mp)
 483         MPOOL *mp;
 484 {
 485         BKT *b;
 486         int cnt;
 487         char *sep;
 488
 489         (void)fprintf(stderr, "%lu pages in the file\n", mp->npages);
 490         (void)fprintf(stderr,
 491             "page size %lu, cacheing %lu pages of %lu page max cache\n",
 492             mp->pagesize, mp->curcache, mp->maxcache);
 493         (void)fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n",
 494             mp->pageput, mp->pageget, mp->pagenew);
 495         (void)fprintf(stderr, "%lu page allocs, %lu page flushes\n",
 496             mp->pagealloc, mp->pageflush);
 497         if (mp->cachehit + mp->cachemiss)
 498                 (void)fprintf(stderr,
 499                     "%.0f%% cache hit rate (%lu hits, %lu misses)\n",
 500                     ((double)mp->cachehit / (mp->cachehit + mp->cachemiss))
 501                     * 100, mp->cachehit, mp->cachemiss);
 502         (void)fprintf(stderr, "%lu page reads, %lu page writes\n",
 503             mp->pageread, mp->pagewrite);
 504
 505         sep = "";
 506         cnt = 0;
 507         for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
 508                 (void)fprintf(stderr, "%s%d", sep, b->pgno);
 509                 if (b->flags & MPOOL_DIRTY)
 510                         (void)fprintf(stderr, "d");
 511                 if (b->flags & MPOOL_PINNED)
 512                         (void)fprintf(stderr, "P");
 513                 if (++cnt == 10) {
 514                         sep = "\n";
 515                         cnt = 0;
 516                 } else
 517                         sep = ", ";
 518
 519         }
 520         (void)fprintf(stderr, "\n");
 521 }
 522 #endif
 523
 524 #ifdef DEBUG
 525 #if __STDC__
 526 #include <stdarg.h>
 527 #else
 528 #include <varargs.h>
 529 #endif
 530
 531 static void
 532 #if __STDC__
 533 __mpoolerr(const char *fmt, ...)
 534 #else
 535 __mpoolerr(fmt, va_alist)
 536         char *fmt;
 537         va_dcl
 538 #endif
 539 {
 540         va_list ap;
 541 #if __STDC__
 542         va_start(ap, fmt);
 543 #else
 544         va_start(ap);
 545 #endif
 546         (void)vfprintf(stderr, fmt, ap);
 547         va_end(ap);
 548         (void)fprintf(stderr, "\n");
 549         abort();
 550         /* NOTREACHED */
 551 }
 552 #endif