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