lib/libc/db/mpool/mpool.c

   1 /*-
   2  * Copyright (c) 1990, 1993, 1994
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 4. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 #if defined(LIBC_SCCS) && !defined(lint)
  31 static char sccsid[] = "@(#)mpool.c     8.7 (Berkeley) 11/2/95";
  32 #endif /* LIBC_SCCS and not lint */
  33 #include <sys/cdefs.h>
  34 __FBSDID("$FreeBSD$");
  35
  36 #include "namespace.h"
  37 #include <sys/param.h>
  38 #include <sys/queue.h>
  39 #include <sys/stat.h>
  40
  41 #include <errno.h>
  42 #include <stdio.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include <unistd.h>
  46 #include "un-namespace.h"
  47
  48 #include <db.h>
  49
  50 #define __MPOOLINTERFACE_PRIVATE
  51 #include <mpool.h>
  52
  53 static BKT *mpool_bkt(MPOOL *);
  54 static BKT *mpool_look(MPOOL *, pgno_t);
  55 static int  mpool_write(MPOOL *, BKT *);
  56
  57 /*
  58  * mpool_open --
  59  *      Initialize a memory pool.
  60  */
  61 /* ARGSUSED */
  62 MPOOL *
  63 mpool_open(void *key, int fd, pgno_t pagesize, pgno_t maxcache)
  64 {
  65         struct stat sb;
  66         MPOOL *mp;
  67         int entry;
  68
  69         /*
  70          * Get information about the file.
  71          *
  72          * XXX
  73          * We don't currently handle pipes, although we should.
  74          */
  75         if (_fstat(fd, &sb))
  76                 return (NULL);
  77         if (!S_ISREG(sb.st_mode)) {
  78                 errno = ESPIPE;
  79                 return (NULL);
  80         }
  81
  82         /* Allocate and initialize the MPOOL cookie. */
  83         if ((mp = (MPOOL *)calloc(1, sizeof(MPOOL))) == NULL)
  84                 return (NULL);
  85         TAILQ_INIT(&mp->lqh);
  86         for (entry = 0; entry < HASHSIZE; ++entry)
  87                 TAILQ_INIT(&mp->hqh[entry]);
  88         mp->maxcache = maxcache;
  89         mp->npages = sb.st_size / pagesize;
  90         mp->pagesize = pagesize;
  91         mp->fd = fd;
  92         return (mp);
  93 }
  94
  95 /*
  96  * mpool_filter --
  97  *      Initialize input/output filters.
  98  */
  99 void
 100 mpool_filter(MPOOL *mp, void (*pgin) (void *, pgno_t, void *),
 101     void (*pgout) (void *, pgno_t, void *), void *pgcookie)
 102 {
 103         mp->pgin = pgin;
 104         mp->pgout = pgout;
 105         mp->pgcookie = pgcookie;
 106 }
 107
 108 /*
 109  * mpool_new --
 110  *      Get a new page of memory.
 111  */
 112 void *
 113 mpool_new(MPOOL *mp, pgno_t *pgnoaddr, u_int flags)
 114 {
 115         struct _hqh *head;
 116         BKT *bp;
 117
 118         if (mp->npages == MAX_PAGE_NUMBER) {
 119                 (void)fprintf(stderr, "mpool_new: page allocation overflow.\n");
 120                 abort();
 121         }
 122 #ifdef STATISTICS
 123         ++mp->pagenew;
 124 #endif
 125         /*
 126          * Get a BKT from the cache.  Assign a new page number, attach
 127          * it to the head of the hash chain, the tail of the lru chain,
 128          * and return.
 129          */
 130         if ((bp = mpool_bkt(mp)) == NULL)
 131                 return (NULL);
 132         if (flags == MPOOL_PAGE_REQUEST) {
 133                 mp->npages++;
 134                 bp->pgno = *pgnoaddr;
 135         } else
 136                 bp->pgno = *pgnoaddr = mp->npages++;
 137
 138         bp->flags = MPOOL_PINNED | MPOOL_INUSE;
 139
 140         head = &mp->hqh[HASHKEY(bp->pgno)];
 141         TAILQ_INSERT_HEAD(head, bp, hq);
 142         TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
 143         return (bp->page);
 144 }
 145
 146 int
 147 mpool_delete(MPOOL *mp, void *page)
 148 {
 149         struct _hqh *head;
 150         BKT *bp;
 151
 152         bp = (BKT *)((char *)page - sizeof(BKT));
 153
 154 #ifdef DEBUG
 155         if (!(bp->flags & MPOOL_PINNED)) {
 156                 (void)fprintf(stderr,
 157                     "mpool_delete: page %d not pinned\n", bp->pgno);
 158                 abort();
 159         }
 160 #endif
 161
 162         /* Remove from the hash and lru queues. */
 163         head = &mp->hqh[HASHKEY(bp->pgno)];
 164         TAILQ_REMOVE(head, bp, hq);
 165         TAILQ_REMOVE(&mp->lqh, bp, q);
 166
 167         free(bp);
 168         mp->curcache--;
 169         return (RET_SUCCESS);
 170 }
 171
 172 /*
 173  * mpool_get
 174  *      Get a page.
 175  */
 176 /* ARGSUSED */
 177 void *
 178 mpool_get(MPOOL *mp, pgno_t pgno,
 179     u_int flags)                /* XXX not used? */
 180 {
 181         struct _hqh *head;
 182         BKT *bp;
 183         off_t off;
 184         int nr;
 185
 186 #ifdef STATISTICS
 187         ++mp->pageget;
 188 #endif
 189
 190         /* Check for a page that is cached. */
 191         if ((bp = mpool_look(mp, pgno)) != NULL) {
 192 #ifdef DEBUG
 193                 if (!(flags & MPOOL_IGNOREPIN) && bp->flags & MPOOL_PINNED) {
 194                         (void)fprintf(stderr,
 195                             "mpool_get: page %d already pinned\n", bp->pgno);
 196                         abort();
 197                 }
 198 #endif
 199                 /*
 200                  * Move the page to the head of the hash chain and the tail
 201                  * of the lru chain.
 202                  */
 203                 head = &mp->hqh[HASHKEY(bp->pgno)];
 204                 TAILQ_REMOVE(head, bp, hq);
 205                 TAILQ_INSERT_HEAD(head, bp, hq);
 206                 TAILQ_REMOVE(&mp->lqh, bp, q);
 207                 TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
 208
 209                 /* Return a pinned page. */
 210                 bp->flags |= MPOOL_PINNED;
 211                 return (bp->page);
 212         }
 213
 214         /* Get a page from the cache. */
 215         if ((bp = mpool_bkt(mp)) == NULL)
 216                 return (NULL);
 217
 218         /* Read in the contents. */
 219         off = mp->pagesize * pgno;
 220         if ((nr = pread(mp->fd, bp->page, mp->pagesize, off)) != (ssize_t)mp->pagesize) {
 221                 switch (nr) {
 222                 case -1:
 223                         /* errno is set for us by pread(). */
 224                         free(bp);
 225                         mp->curcache--;
 226                         return (NULL);
 227                 case 0:
 228                         /*
 229                          * A zero-length read means you need to create a
 230                          * new page.
 231                          */
 232                         memset(bp->page, 0, mp->pagesize);
 233                         break;
 234                 default:
 235                         /* A partial read is definitely bad. */
 236                         free(bp);
 237                         mp->curcache--;
 238                         errno = EINVAL;
 239                         return (NULL);
 240                 }
 241         }
 242 #ifdef STATISTICS
 243         ++mp->pageread;
 244 #endif
 245
 246         /* Set the page number, pin the page. */
 247         bp->pgno = pgno;
 248         if (!(flags & MPOOL_IGNOREPIN))
 249                 bp->flags = MPOOL_PINNED;
 250         bp->flags |= MPOOL_INUSE;
 251
 252         /*
 253          * Add the page to the head of the hash chain and the tail
 254          * of the lru chain.
 255          */
 256         head = &mp->hqh[HASHKEY(bp->pgno)];
 257         TAILQ_INSERT_HEAD(head, bp, hq);
 258         TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
 259
 260         /* Run through the user's filter. */
 261         if (mp->pgin != NULL)
 262                 (mp->pgin)(mp->pgcookie, bp->pgno, bp->page);
 263
 264         return (bp->page);
 265 }
 266
 267 /*
 268  * mpool_put
 269  *      Return a page.
 270  */
 271 /* ARGSUSED */
 272 int
 273 mpool_put(MPOOL *mp, void *page, u_int flags)
 274 {
 275         BKT *bp;
 276
 277 #ifdef STATISTICS
 278         ++mp->pageput;
 279 #endif
 280         bp = (BKT *)((char *)page - sizeof(BKT));
 281 #ifdef DEBUG
 282         if (!(bp->flags & MPOOL_PINNED)) {
 283                 (void)fprintf(stderr,
 284                     "mpool_put: page %d not pinned\n", bp->pgno);
 285                 abort();
 286         }
 287 #endif
 288         bp->flags &= ~MPOOL_PINNED;
 289         if (flags & MPOOL_DIRTY)
 290                 bp->flags |= flags & MPOOL_DIRTY;
 291         return (RET_SUCCESS);
 292 }
 293
 294 /*
 295  * mpool_close
 296  *      Close the buffer pool.
 297  */
 298 int
 299 mpool_close(MPOOL *mp)
 300 {
 301         BKT *bp;
 302
 303         /* Free up any space allocated to the lru pages. */
 304         while (!TAILQ_EMPTY(&mp->lqh)) {
 305                 bp = TAILQ_FIRST(&mp->lqh);
 306                 TAILQ_REMOVE(&mp->lqh, bp, q);
 307                 free(bp);
 308         }
 309
 310         /* Free the MPOOL cookie. */
 311         free(mp);
 312         return (RET_SUCCESS);
 313 }
 314
 315 /*
 316  * mpool_sync
 317  *      Sync the pool to disk.
 318  */
 319 int
 320 mpool_sync(MPOOL *mp)
 321 {
 322         BKT *bp;
 323
 324         /* Walk the lru chain, flushing any dirty pages to disk. */
 325         TAILQ_FOREACH(bp, &mp->lqh, q)
 326                 if (bp->flags & MPOOL_DIRTY &&
 327                     mpool_write(mp, bp) == RET_ERROR)
 328                         return (RET_ERROR);
 329
 330         /* Sync the file descriptor. */
 331         return (_fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
 332 }
 333
 334 /*
 335  * mpool_bkt
 336  *      Get a page from the cache (or create one).
 337  */
 338 static BKT *
 339 mpool_bkt(MPOOL *mp)
 340 {
 341         struct _hqh *head;
 342         BKT *bp;
 343
 344         /* If under the max cached, always create a new page. */
 345         if (mp->curcache < mp->maxcache)
 346                 goto new;
 347
 348         /*
 349          * If the cache is max'd out, walk the lru list for a buffer we
 350          * can flush.  If we find one, write it (if necessary) and take it
 351          * off any lists.  If we don't find anything we grow the cache anyway.
 352          * The cache never shrinks.
 353          */
 354         TAILQ_FOREACH(bp, &mp->lqh, q)
 355                 if (!(bp->flags & MPOOL_PINNED)) {
 356                         /* Flush if dirty. */
 357                         if (bp->flags & MPOOL_DIRTY &&
 358                             mpool_write(mp, bp) == RET_ERROR)
 359                                 return (NULL);
 360 #ifdef STATISTICS
 361                         ++mp->pageflush;
 362 #endif
 363                         /* Remove from the hash and lru queues. */
 364                         head = &mp->hqh[HASHKEY(bp->pgno)];
 365                         TAILQ_REMOVE(head, bp, hq);
 366                         TAILQ_REMOVE(&mp->lqh, bp, q);
 367 #ifdef DEBUG
 368                         { void *spage;
 369                                 spage = bp->page;
 370                                 memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
 371                                 bp->page = spage;
 372                         }
 373 #endif
 374                         bp->flags = 0;
 375                         return (bp);
 376                 }
 377
 378 new:    if ((bp = (BKT *)calloc(1, sizeof(BKT) + mp->pagesize)) == NULL)
 379                 return (NULL);
 380 #ifdef STATISTICS
 381         ++mp->pagealloc;
 382 #endif
 383         bp->page = (char *)bp + sizeof(BKT);
 384         bp->flags = 0;
 385         ++mp->curcache;
 386         return (bp);
 387 }
 388
 389 /*
 390  * mpool_write
 391  *      Write a page to disk.
 392  */
 393 static int
 394 mpool_write(MPOOL *mp, BKT *bp)
 395 {
 396         off_t off;
 397
 398 #ifdef STATISTICS
 399         ++mp->pagewrite;
 400 #endif
 401
 402         /* Run through the user's filter. */
 403         if (mp->pgout)
 404                 (mp->pgout)(mp->pgcookie, bp->pgno, bp->page);
 405
 406         off = mp->pagesize * bp->pgno;
 407         if (pwrite(mp->fd, bp->page, mp->pagesize, off) != (ssize_t)mp->pagesize)
 408                 return (RET_ERROR);
 409
 410         /*
 411          * Re-run through the input filter since this page may soon be
 412          * accessed via the cache, and whatever the user's output filter
 413          * did may screw things up if we don't let the input filter
 414          * restore the in-core copy.
 415          */
 416         if (mp->pgin)
 417                 (mp->pgin)(mp->pgcookie, bp->pgno, bp->page);
 418
 419         bp->flags &= ~MPOOL_DIRTY;
 420         return (RET_SUCCESS);
 421 }
 422
 423 /*
 424  * mpool_look
 425  *      Lookup a page in the cache.
 426  */
 427 static BKT *
 428 mpool_look(MPOOL *mp, pgno_t pgno)
 429 {
 430         struct _hqh *head;
 431         BKT *bp;
 432
 433         head = &mp->hqh[HASHKEY(pgno)];
 434         TAILQ_FOREACH(bp, head, hq)
 435                 if ((bp->pgno == pgno) &&
 436                         ((bp->flags & MPOOL_INUSE) == MPOOL_INUSE)) {
 437 #ifdef STATISTICS
 438                         ++mp->cachehit;
 439 #endif
 440                         return (bp);
 441                 }
 442 #ifdef STATISTICS
 443         ++mp->cachemiss;
 444 #endif
 445         return (NULL);
 446 }
 447
 448 #ifdef STATISTICS
 449 /*
 450  * mpool_stat
 451  *      Print out cache statistics.
 452  */
 453 void
 454 mpool_stat(MPOOL *mp)
 455 {
 456         BKT *bp;
 457         int cnt;
 458         char *sep;
 459
 460         (void)fprintf(stderr, "%lu pages in the file\n", mp->npages);
 461         (void)fprintf(stderr,
 462             "page size %lu, cacheing %lu pages of %lu page max cache\n",
 463             mp->pagesize, mp->curcache, mp->maxcache);
 464         (void)fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n",
 465             mp->pageput, mp->pageget, mp->pagenew);
 466         (void)fprintf(stderr, "%lu page allocs, %lu page flushes\n",
 467             mp->pagealloc, mp->pageflush);
 468         if (mp->cachehit + mp->cachemiss)
 469                 (void)fprintf(stderr,
 470                     "%.0f%% cache hit rate (%lu hits, %lu misses)\n",
 471                     ((double)mp->cachehit / (mp->cachehit + mp->cachemiss))
 472                     * 100, mp->cachehit, mp->cachemiss);
 473         (void)fprintf(stderr, "%lu page reads, %lu page writes\n",
 474             mp->pageread, mp->pagewrite);
 475
 476         sep = "";
 477         cnt = 0;
 478         TAILQ_FOREACH(bp, &mp->lqh, q) {
 479                 (void)fprintf(stderr, "%s%d", sep, bp->pgno);
 480                 if (bp->flags & MPOOL_DIRTY)
 481                         (void)fprintf(stderr, "d");
 482                 if (bp->flags & MPOOL_PINNED)
 483                         (void)fprintf(stderr, "P");
 484                 if (++cnt == 10) {
 485                         sep = "\n";
 486                         cnt = 0;
 487                 } else
 488                         sep = ", ";
 489
 490         }
 491         (void)fprintf(stderr, "\n");
 492 }
 493 #endif