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