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