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. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by the University of
  16  *      California, Berkeley and its contributors.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #if defined(LIBC_SCCS) && !defined(lint)
  35 static char sccsid[] = "@(#)mpool.c     8.5 (Berkeley) 7/26/94";
  36 #endif /* LIBC_SCCS and not lint */
  37
  38 #include <sys/param.h>
  39 #include <sys/queue.h>
  40 #include <sys/stat.h>
  41
  42 #include <errno.h>
  43 #include <stdio.h>
  44 #include <stdlib.h>
  45 #include <string.h>
  46 #include <unistd.h>
  47
  48 #include <db.h>
  49
  50 #define __MPOOLINTERFACE_PRIVATE
  51 #include <mpool.h>
  52
  53 #ifdef _LIBC
  54 /* In the GNU C library we must not pollute the namespace because libdb is
  55    needed by libnss_db.  */
  56 #define mpool_open __mpool_open
  57 #define mpool_filter __mpool_filter
  58 #define mpool_new __mpool_new
  59 #define mpool_get __mpool_get
  60 #define mpool_put __mpool_put
  61 #define mpool_sync __mpool_sync
  62 #define mpool_close __mpool_close
  63 #endif
  64
  65 static BKT *mpool_bkt __P((MPOOL *));
  66 static BKT *mpool_look __P((MPOOL *, pgno_t));
  67 static int  mpool_write __P((MPOOL *, BKT *));
  68
  69 /*
  70  * mpool_open --
  71  *      Initialize a memory pool.
  72  */
  73 MPOOL *
  74 mpool_open(key, fd, pagesize, maxcache)
  75         void *key;
  76         int fd;
  77         pgno_t pagesize, maxcache;
  78 {
  79         struct stat sb;
  80         MPOOL *mp;
  81         int entry;
  82
  83         /*
  84          * Get information about the file.
  85          *
  86          * XXX
  87          * We don't currently handle pipes, although we should.
  88          */
  89         if (fstat(fd, &sb))
  90                 return (NULL);
  91         if (!S_ISREG(sb.st_mode)) {
  92                 errno = ESPIPE;
  93                 return (NULL);
  94         }
  95
  96         /* Allocate and initialize the MPOOL cookie. */
  97         if ((mp = (MPOOL *)calloc(1, sizeof(MPOOL))) == NULL)
  98                 return (NULL);
  99         CIRCLEQ_INIT(&mp->lqh);
 100         for (entry = 0; entry < HASHSIZE; ++entry)
 101                 CIRCLEQ_INIT(&mp->hqh[entry]);
 102         mp->maxcache = maxcache;
 103         mp->npages = sb.st_size / pagesize;
 104         mp->pagesize = pagesize;
 105         mp->fd = fd;
 106         return (mp);
 107 }
 108
 109 /*
 110  * mpool_filter --
 111  *      Initialize input/output filters.
 112  */
 113 void
 114 mpool_filter(mp, pgin, pgout, pgcookie)
 115         MPOOL *mp;
 116         void (*pgin) __P((void *, pgno_t, void *));
 117         void (*pgout) __P((void *, pgno_t, void *));
 118         void *pgcookie;
 119 {
 120         mp->pgin = pgin;
 121         mp->pgout = pgout;
 122         mp->pgcookie = pgcookie;
 123 }
 124
 125 /*
 126  * mpool_new --
 127  *      Get a new page of memory.
 128  */
 129 void *
 130 mpool_new(mp, pgnoaddr)
 131         MPOOL *mp;
 132         pgno_t *pgnoaddr;
 133 {
 134         struct _hqh *head;
 135         BKT *bp;
 136
 137         if (mp->npages == MAX_PAGE_NUMBER) {
 138                 (void)fprintf(stderr, "mpool_new: page allocation overflow.\n");
 139                 abort();
 140         }
 141 #ifdef STATISTICS
 142         ++mp->pagenew;
 143 #endif
 144         /*
 145          * Get a BKT from the cache.  Assign a new page number, attach
 146          * it to the head of the hash chain, the tail of the lru chain,
 147          * and return.
 148          */
 149         if ((bp = mpool_bkt(mp)) == NULL)
 150                 return (NULL);
 151         *pgnoaddr = bp->pgno = mp->npages++;
 152         bp->flags = MPOOL_PINNED;
 153
 154         head = &mp->hqh[HASHKEY(bp->pgno)];
 155         CIRCLEQ_INSERT_HEAD(head, bp, hq);
 156         CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q);
 157         return (bp->page);
 158 }
 159
 160 /*
 161  * mpool_get
 162  *      Get a page.
 163  */
 164 void *
 165 mpool_get(mp, pgno, flags)
 166         MPOOL *mp;
 167         pgno_t pgno;
 168         u_int flags;                            /* XXX not used? */
 169 {
 170         struct _hqh *head;
 171         BKT *bp;
 172         off_t off;
 173         int nr;
 174
 175         /* Check for attempt to retrieve a non-existent page. */
 176         if (pgno >= mp->npages) {
 177                 errno = EINVAL;
 178                 return (NULL);
 179         }
 180
 181 #ifdef STATISTICS
 182         ++mp->pageget;
 183 #endif
 184
 185         /* Check for a page that is cached. */
 186         if ((bp = mpool_look(mp, pgno)) != NULL) {
 187 #ifdef DEBUG
 188                 if (bp->flags & MPOOL_PINNED) {
 189                         (void)fprintf(stderr,
 190                             "mpool_get: page %d already pinned\n", bp->pgno);
 191                         abort();
 192                 }
 193 #endif
 194                 /*
 195                  * Move the page to the head of the hash chain and the tail
 196                  * of the lru chain.
 197                  */
 198                 head = &mp->hqh[HASHKEY(bp->pgno)];
 199                 CIRCLEQ_REMOVE(head, bp, hq);
 200                 CIRCLEQ_INSERT_HEAD(head, bp, hq);
 201                 CIRCLEQ_REMOVE(&mp->lqh, bp, q);
 202                 CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q);
 203
 204                 /* Return a pinned page. */
 205                 bp->flags |= MPOOL_PINNED;
 206                 return (bp->page);
 207         }
 208
 209         /* Get a page from the cache. */
 210         if ((bp = mpool_bkt(mp)) == NULL)
 211                 return (NULL);
 212
 213         /* Read in the contents. */
 214 #ifdef STATISTICS
 215         ++mp->pageread;
 216 #endif
 217         off = mp->pagesize * pgno;
 218         if (lseek(mp->fd, off, SEEK_SET) != off)
 219                 return (NULL);
 220         if ((u_long) (nr = read(mp->fd, bp->page, mp->pagesize))
 221             != mp->pagesize) {
 222                 if (nr >= 0)
 223                         errno = EFTYPE;
 224                 return (NULL);
 225         }
 226
 227         /* Set the page number, pin the page. */
 228         bp->pgno = pgno;
 229         bp->flags = MPOOL_PINNED;
 230
 231         /*
 232          * Add the page to the head of the hash chain and the tail
 233          * of the lru chain.
 234          */
 235         head = &mp->hqh[HASHKEY(bp->pgno)];
 236         CIRCLEQ_INSERT_HEAD(head, bp, hq);
 237         CIRCLEQ_INSERT_TAIL(&mp->lqh, bp, q);
 238
 239         /* Run through the user's filter. */
 240         if (mp->pgin != NULL)
 241                 (mp->pgin)(mp->pgcookie, bp->pgno, bp->page);
 242
 243         return (bp->page);
 244 }
 245
 246 /*
 247  * mpool_put
 248  *      Return a page.
 249  */
 250 int
 251 mpool_put(mp, page, flags)
 252         MPOOL *mp;
 253         void *page;
 254         u_int flags;
 255 {
 256         BKT *bp;
 257
 258 #ifdef STATISTICS
 259         ++mp->pageput;
 260 #endif
 261         bp = (BKT *)((char *)page - sizeof(BKT));
 262 #ifdef DEBUG
 263         if (!(bp->flags & MPOOL_PINNED)) {
 264                 (void)fprintf(stderr,
 265                     "mpool_put: page %d not pinned\n", bp->pgno);
 266                 abort();
 267         }
 268 #endif
 269         bp->flags &= ~MPOOL_PINNED;
 270         bp->flags |= flags & MPOOL_DIRTY;
 271         return (RET_SUCCESS);
 272 }
 273
 274 /*
 275  * mpool_close
 276  *      Close the buffer pool.
 277  */
 278 int
 279 mpool_close(mp)
 280         MPOOL *mp;
 281 {
 282         BKT *bp;
 283
 284         /* Free up any space allocated to the lru pages. */
 285         while ((bp = mp->lqh.cqh_first) != (void *)&mp->lqh) {
 286                 CIRCLEQ_REMOVE(&mp->lqh, mp->lqh.cqh_first, q);
 287                 free(bp);
 288         }
 289
 290         /* Free the MPOOL cookie. */
 291         free(mp);
 292         return (RET_SUCCESS);
 293 }
 294
 295 /*
 296  * mpool_sync
 297  *      Sync the pool to disk.
 298  */
 299 int
 300 mpool_sync(mp)
 301         MPOOL *mp;
 302 {
 303         BKT *bp;
 304
 305         /* Walk the lru chain, flushing any dirty pages to disk. */
 306         for (bp = mp->lqh.cqh_first;
 307             bp != (void *)&mp->lqh; bp = bp->q.cqe_next)
 308                 if (bp->flags & MPOOL_DIRTY &&
 309                     mpool_write(mp, bp) == RET_ERROR)
 310                         return (RET_ERROR);
 311
 312         /* Sync the file descriptor. */
 313         return (fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
 314 }
 315
 316 #ifdef _LIBC
 317 #undef mpool_open
 318 #undef mpool_filter
 319 #undef mpool_new
 320 #undef mpool_get
 321 #undef mpool_put
 322 #undef mpool_close
 323 #undef mpool_sync
 324 weak_alias (__mpool_open, mpool_open)
 325 weak_alias (__mpool_filter, mpool_filter)
 326 weak_alias (__mpool_new, mpool_new)
 327 weak_alias (__mpool_get, mpool_get)
 328 weak_alias (__mpool_put, mpool_put)
 329 weak_alias (__mpool_close, mpool_close)
 330 weak_alias (__mpool_sync, mpool_sync)
 331 #endif
 332
 333 /*
 334  * mpool_bkt
 335  *      Get a page from the cache (or create one).
 336  */
 337 static BKT *
 338 mpool_bkt(mp)
 339         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         for (bp = mp->lqh.cqh_first;
 355             bp != (void *)&mp->lqh; bp = bp->q.cqe_next)
 356                 if (!(bp->flags & MPOOL_PINNED)) {
 357                         /* Flush if dirty. */
 358                         if (bp->flags & MPOOL_DIRTY &&
 359                             mpool_write(mp, bp) == RET_ERROR)
 360                                 return (NULL);
 361 #ifdef STATISTICS
 362                         ++mp->pageflush;
 363 #endif
 364                         /* Remove from the hash and lru queues. */
 365                         head = &mp->hqh[HASHKEY(bp->pgno)];
 366                         CIRCLEQ_REMOVE(head, bp, hq);
 367                         CIRCLEQ_REMOVE(&mp->lqh, bp, q);
 368 #ifdef DEBUG
 369                         { void *spage;
 370                                 spage = bp->page;
 371                                 memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
 372                                 bp->page = spage;
 373                         }
 374 #endif
 375                         return (bp);
 376                 }
 377
 378 new:    if ((bp = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
 379                 return (NULL);
 380 #ifdef STATISTICS
 381         ++mp->pagealloc;
 382 #endif
 383 #if defined(DEBUG) || defined(PURIFY)
 384         memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
 385 #endif
 386         bp->page = (char *)bp + sizeof(BKT);
 387         ++mp->curcache;
 388         return (bp);
 389 }
 390
 391 /*
 392  * mpool_write
 393  *      Write a page to disk.
 394  */
 395 static int
 396 mpool_write(mp, bp)
 397         MPOOL *mp;
 398         BKT *bp;
 399 {
 400         off_t off;
 401
 402 #ifdef STATISTICS
 403         ++mp->pagewrite;
 404 #endif
 405
 406         /* Run through the user's filter. */
 407         if (mp->pgout)
 408                 (mp->pgout)(mp->pgcookie, bp->pgno, bp->page);
 409
 410         off = mp->pagesize * bp->pgno;
 411         if (lseek(mp->fd, off, SEEK_SET) != off)
 412                 return (RET_ERROR);
 413         if ((u_long) write(mp->fd, bp->page, mp->pagesize) != mp->pagesize)
 414                 return (RET_ERROR);
 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(mp, pgno)
 426         MPOOL *mp;
 427         pgno_t pgno;
 428 {
 429         struct _hqh *head;
 430         BKT *bp;
 431
 432         head = &mp->hqh[HASHKEY(pgno)];
 433         for (bp = head->cqh_first; bp != (void *)head; bp = bp->hq.cqe_next)
 434                 if (bp->pgno == pgno) {
 435 #ifdef STATISTICS
 436                         ++mp->cachehit;
 437 #endif
 438                         return (bp);
 439                 }
 440 #ifdef STATISTICS
 441         ++mp->cachemiss;
 442 #endif
 443         return (NULL);
 444 }
 445
 446 #ifdef STATISTICS
 447 /*
 448  * mpool_stat
 449  *      Print out cache statistics.
 450  */
 451 void
 452 mpool_stat(mp)
 453         MPOOL *mp;
 454 {
 455         BKT *bp;
 456         int cnt;
 457         char *sep;
 458
 459         (void)fprintf(stderr, "%lu pages in the file\n", mp->npages);
 460         (void)fprintf(stderr,
 461             "page size %lu, cacheing %lu pages of %lu page max cache\n",
 462             mp->pagesize, mp->curcache, mp->maxcache);
 463         (void)fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n",
 464             mp->pageput, mp->pageget, mp->pagenew);
 465         (void)fprintf(stderr, "%lu page allocs, %lu page flushes\n",
 466             mp->pagealloc, mp->pageflush);
 467         if (mp->cachehit + mp->cachemiss)
 468                 (void)fprintf(stderr,
 469                     "%.0f%% cache hit rate (%lu hits, %lu misses)\n",
 470                     ((double)mp->cachehit / (mp->cachehit + mp->cachemiss))
 471                     * 100, mp->cachehit, mp->cachemiss);
 472         (void)fprintf(stderr, "%lu page reads, %lu page writes\n",
 473             mp->pageread, mp->pagewrite);
 474
 475         sep = "";
 476         cnt = 0;
 477         for (bp = mp->lqh.cqh_first;
 478             bp != (void *)&mp->lqh; bp = bp->q.cqe_next) {
 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