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