cde/programs/dtinfo/DtMmdb/btree_berkeley/mpool.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: mpool.c /main/4 1996/10/04 09:47:13 drk $ */
  24 /*-
  25  * Copyright (c) 1990, 1993
  26  *      The Regents of the University of California.  All rights reserved.
  27  *
  28  * Redistribution and use in source and binary forms, with or without
  29  * modification, are permitted provided that the following conditions
  30  * are met:
  31  * 1. Redistributions of source code must retain the above copyright
  32  *    notice, this list of conditions and the following disclaimer.
  33  * 2. Redistributions in binary form must reproduce the above copyright
  34  *    notice, this list of conditions and the following disclaimer in the
  35  *    documentation and/or other materials provided with the distribution.
  36  * 3. All advertising materials mentioning features or use of this software
  37  *    must display the following acknowledgement:
  38  *      This product includes software developed by the University of
  39  *      California, Berkeley and its contributors.
  40  * 4. Neither the name of the University nor the names of its contributors
  41  *    may be used to endorse or promote products derived from this software
  42  *    without specific prior written permission.
  43  *
  44  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  45  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  46  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  47  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  48  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  49  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  50  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  51  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  52  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  53  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  54  * SUCH DAMAGE.
  55  */
  56
  57 #if defined(LIBC_SCCS) && !defined(lint)
  58 static char sccsid[] = "@(#)mpool.c     8.1 (Berkeley) 6/6/93";
  59 #endif /* LIBC_SCCS and not lint */
  60
  61 #include <sys/param.h>
  62 #include <sys/stat.h>
  63
  64 #include <errno.h>
  65 #include <stdio.h>
  66 #include <stdlib.h>
  67 #include <string.h>
  68 #include <unistd.h>
  69
  70 #include <db.h>
  71 #define __MPOOLINTERFACE_PRIVATE
  72 #include "mpool.h"
  73
  74 static BKT *mpool_bkt __P((MPOOL *));
  75 static BKT *mpool_look __P((MPOOL *, pgno_t));
  76 static int  mpool_write __P((MPOOL *, BKT *));
  77 #ifdef DEBUG
  78 static void __mpoolerr __P((const char *fmt, ...));
  79 #endif
  80
  81 /*
  82  * MPOOL_OPEN -- initialize a memory pool.
  83  *
  84  * Parameters:
  85  *      key:            Shared buffer key.
  86  *      fd:             File descriptor.
  87  *      pagesize:       File page size.
  88  *      maxcache:       Max number of cached pages.
  89  *
  90  * Returns:
  91  *      MPOOL pointer, NULL on error.
  92  */
  93 MPOOL *
  94 mpool_open(key, fd, pagesize, maxcache)
  95         DBT *key;
  96         int fd;
  97         pgno_t pagesize, maxcache;
  98 {
  99         struct stat sb;
 100         MPOOL *mp;
 101         int entry;
 102
 103         if (fstat(fd, &sb))
 104                 return (NULL);
 105         /* XXX
 106          * We should only set st_size to 0 for pipes -- 4.4BSD has the fix so
 107          * that stat(2) returns true for ISSOCK on pipes.  Until then, this is
 108          * fairly close.
 109          */
 110         if (!S_ISREG(sb.st_mode)) {
 111                 errno = ESPIPE;
 112                 return (NULL);
 113         }
 114
 115         if ((mp = malloc(sizeof(MPOOL))) == NULL)
 116                 return (NULL);
 117         mp->free.cnext = mp->free.cprev = (BKT *)&mp->free;
 118         mp->lru.cnext = mp->lru.cprev = (BKT *)&mp->lru;
 119         for (entry = 0; entry < HASHSIZE; ++entry)
 120                 mp->hashtable[entry].hnext = mp->hashtable[entry].hprev =
 121                     mp->hashtable[entry].cnext = mp->hashtable[entry].cprev =
 122                     (BKT *)&mp->hashtable[entry];
 123         mp->curcache = 0;
 124         mp->maxcache = maxcache;
 125         mp->pagesize = pagesize;
 126         mp->npages = sb.st_size / pagesize;
 127         mp->fd = fd;
 128         mp->pgcookie = NULL;
 129         mp->pgin = mp->pgout = NULL;
 130
 131 #ifdef STATISTICS
 132         mp->cachehit = mp->cachemiss = mp->pagealloc = mp->pageflush =
 133             mp->pageget = mp->pagenew = mp->pageput = mp->pageread =
 134             mp->pagewrite = 0;
 135 #endif
 136         return (mp);
 137 }
 138
 139 /*
 140  * MPOOL_FILTER -- initialize input/output filters.
 141  *
 142  * Parameters:
 143  *      pgin:           Page in conversion routine.
 144  *      pgout:          Page out conversion routine.
 145  *      pgcookie:       Cookie for page in/out routines.
 146  */
 147 void
 148 mpool_filter(mp, pgin, pgout, pgcookie)
 149         MPOOL *mp;
 150         void (*pgin) __P((void *, pgno_t, void *));
 151         void (*pgout) __P((void *, pgno_t, void *));
 152         void *pgcookie;
 153 {
 154         mp->pgin = pgin;
 155         mp->pgout = pgout;
 156         mp->pgcookie = pgcookie;
 157 }
 158
 159 /*
 160  * MPOOL_NEW -- get a new page
 161  *
 162  * Parameters:
 163  *      mp:             mpool cookie
 164  *      pgnoadddr:      place to store new page number
 165  * Returns:
 166  *      RET_ERROR, RET_SUCCESS
 167  */
 168 void *
 169 mpool_new(mp, pgnoaddr)
 170         MPOOL *mp;
 171         pgno_t *pgnoaddr;
 172 {
 173         BKT *b;
 174         BKTHDR *hp;
 175
 176 #ifdef STATISTICS
 177         ++mp->pagenew;
 178 #endif
 179         /*
 180          * Get a BKT from the cache.  Assign a new page number, attach it to
 181          * the hash and lru chains and return.
 182          */
 183         if ((b = mpool_bkt(mp)) == NULL)
 184                 return (NULL);
 185         *pgnoaddr = b->pgno = mp->npages++;
 186         b->flags = MPOOL_PINNED;
 187         inshash(b, b->pgno);
 188         inschain(b, &mp->lru);
 189         return (b->page);
 190 }
 191
 192 /*
 193  * MPOOL_GET -- get a page from the pool
 194  *
 195  * Parameters:
 196  *      mp:     mpool cookie
 197  *      pgno:   page number
 198  *      flags:  not used
 199  *
 200  * Returns:
 201  *      RET_ERROR, RET_SUCCESS
 202  */
 203 void *
 204 mpool_get(mp, pgno, flags)
 205         MPOOL *mp;
 206         pgno_t pgno;
 207         u_int flags;            /* XXX not used? */
 208 {
 209         BKT *b;
 210         BKTHDR *hp;
 211         off_t off;
 212         int nr;
 213
 214         /*
 215          * If asking for a specific page that is already in the cache, find
 216          * it and return it.
 217          */
 218         if (b = mpool_look(mp, pgno)) {
 219 #ifdef STATISTICS
 220                 ++mp->pageget;
 221 #endif
 222 #ifdef DEBUG
 223                 if (b->flags & MPOOL_PINNED)
 224                         __mpoolerr("mpool_get: page %d already pinned",
 225                             b->pgno);
 226 #endif
 227                 rmchain(b);
 228                 inschain(b, &mp->lru);
 229                 b->flags |= MPOOL_PINNED;
 230                 return (b->page);
 231         }
 232
 233         /* Not allowed to retrieve a non-existent page. */
 234         if (pgno >= mp->npages) {
 235                 errno = EINVAL;
 236                 return (NULL);
 237         }
 238
 239         /* Get a page from the cache. */
 240         if ((b = mpool_bkt(mp)) == NULL)
 241                 return (NULL);
 242         b->pgno = pgno;
 243         b->flags = MPOOL_PINNED;
 244
 245 #ifdef STATISTICS
 246         ++mp->pageread;
 247 #endif
 248         /* Read in the contents. */
 249         off = mp->pagesize * pgno;
 250         if (lseek(mp->fd, off, SEEK_SET) != off)
 251                 return (NULL);
 252         if ((nr = read(mp->fd, b->page, mp->pagesize)) != mp->pagesize) {
 253                 if (nr >= 0)
 254                         errno = EFTYPE;
 255                 return (NULL);
 256         }
 257         if (mp->pgin)
 258                 (mp->pgin)(mp->pgcookie, b->pgno, b->page);
 259
 260         inshash(b, b->pgno);
 261         inschain(b, &mp->lru);
 262 #ifdef STATISTICS
 263         ++mp->pageget;
 264 #endif
 265         return (b->page);
 266 }
 267
 268 /*
 269  * MPOOL_PUT -- return a page to the pool
 270  *
 271  * Parameters:
 272  *      mp:     mpool cookie
 273  *      page:   page pointer
 274  *      pgno:   page number
 275  *
 276  * Returns:
 277  *      RET_ERROR, RET_SUCCESS
 278  */
 279 int
 280 mpool_put(mp, page, flags)
 281         MPOOL *mp;
 282         void *page;
 283         u_int flags;
 284 {
 285         BKT *baddr;
 286 #ifdef DEBUG
 287         BKT *b;
 288 #endif
 289
 290 #ifdef STATISTICS
 291         ++mp->pageput;
 292 #endif
 293         baddr = (BKT *)((char *)page - sizeof(BKT));
 294 #ifdef DEBUG
 295         if (!(baddr->flags & MPOOL_PINNED))
 296                 __mpoolerr("mpool_put: page %d not pinned", b->pgno);
 297         for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
 298                 if (b == (BKT *)&mp->lru)
 299                         __mpoolerr("mpool_put: %0x: bad address", baddr);
 300                 if (b == baddr)
 301                         break;
 302         }
 303 #endif
 304         baddr->flags &= ~MPOOL_PINNED;
 305         baddr->flags |= flags & MPOOL_DIRTY;
 306         return (RET_SUCCESS);
 307 }
 308
 309 /*
 310  * MPOOL_CLOSE -- close the buffer pool
 311  *
 312  * Parameters:
 313  *      mp:     mpool cookie
 314  *
 315  * Returns:
 316  *      RET_ERROR, RET_SUCCESS
 317  */
 318 int
 319 mpool_close(mp)
 320         MPOOL *mp;
 321 {
 322         BKT *b, *next;
 323
 324         /* Free up any space allocated to the lru pages. */
 325         for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = next) {
 326                 next = b->cprev;
 327                 free(b);
 328         }
 329         free(mp);
 330         return (RET_SUCCESS);
 331 }
 332
 333 /*
 334  * MPOOL_SYNC -- sync the file to disk.
 335  *
 336  * Parameters:
 337  *      mp:     mpool cookie
 338  *
 339  * Returns:
 340  *      RET_ERROR, RET_SUCCESS
 341  */
 342 int
 343 mpool_sync(mp)
 344         MPOOL *mp;
 345 {
 346         BKT *b;
 347
 348         for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
 349                 if (b->flags & MPOOL_DIRTY && mpool_write(mp, b) == RET_ERROR)
 350                         return (RET_ERROR);
 351         return (fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
 352 }
 353
 354 /*
 355  * MPOOL_BKT -- get/create a BKT from the cache
 356  *
 357  * Parameters:
 358  *      mp:     mpool cookie
 359  *
 360  * Returns:
 361  *      NULL on failure and a pointer to the BKT on success
 362  */
 363 static BKT *
 364 mpool_bkt(mp)
 365         MPOOL *mp;
 366 {
 367         BKT *b;
 368
 369         if (mp->curcache < mp->maxcache)
 370                 goto new;
 371
 372         /*
 373          * If the cache is maxxed out, search the lru list for a buffer we
 374          * can flush.  If we find one, write it if necessary and take it off
 375          * any lists.  If we don't find anything we grow the cache anyway.
 376          * The cache never shrinks.
 377          */
 378         for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev)
 379                 if (!(b->flags & MPOOL_PINNED)) {
 380                         if (b->flags & MPOOL_DIRTY &&
 381                             mpool_write(mp, b) == RET_ERROR)
 382                                 return (NULL);
 383                         rmhash(b);
 384                         rmchain(b);
 385 #ifdef STATISTICS
 386                         ++mp->pageflush;
 387 #endif
 388 #ifdef DEBUG
 389                         {
 390                                 void *spage;
 391                                 spage = b->page;
 392                                 memset(b, 0xff, sizeof(BKT) + mp->pagesize);
 393                                 b->page = spage;
 394                         }
 395 #endif
 396                         return (b);
 397                 }
 398
 399 new:    if ((b = malloc(sizeof(BKT) + mp->pagesize)) == NULL)
 400                 return (NULL);
 401 #ifdef STATISTICS
 402         ++mp->pagealloc;
 403 #endif
 404 /*
 405 #ifdef DEBUG
 406 */
 407         memset(b, 0xff, sizeof(BKT) + mp->pagesize);
 408 /*
 409 #endif
 410 */
 411         b->page = (char *)b + sizeof(BKT);
 412
 413         ++mp->curcache;
 414         return (b);
 415 }
 416
 417 /*
 418  * MPOOL_WRITE -- sync a page to disk
 419  *
 420  * Parameters:
 421  *      mp:     mpool cookie
 422  *
 423  * Returns:
 424  *      RET_ERROR, RET_SUCCESS
 425  */
 426 static int
 427 mpool_write(mp, b)
 428         MPOOL *mp;
 429         BKT *b;
 430 {
 431         off_t off;
 432
 433         if (mp->pgout)
 434                 (mp->pgout)(mp->pgcookie, b->pgno, b->page);
 435
 436 #ifdef STATISTICS
 437         ++mp->pagewrite;
 438 #endif
 439         off = mp->pagesize * b->pgno;
 440         if (lseek(mp->fd, off, SEEK_SET) != off)
 441                 return (RET_ERROR);
 442         if (write(mp->fd, b->page, mp->pagesize) != mp->pagesize)
 443                 return (RET_ERROR);
 444         b->flags &= ~MPOOL_DIRTY;
 445         return (RET_SUCCESS);
 446 }
 447
 448 /*
 449  * MPOOL_LOOK -- lookup a page
 450  *
 451  * Parameters:
 452  *      mp:     mpool cookie
 453  *      pgno:   page number
 454  *
 455  * Returns:
 456  *      NULL on failure and a pointer to the BKT on success
 457  */
 458 static BKT *
 459 mpool_look(mp, pgno)
 460         MPOOL *mp;
 461         pgno_t pgno;
 462 {
 463         register BKT *b;
 464         register BKTHDR *tb;
 465
 466         /* XXX
 467          * If find the buffer, put it first on the hash chain so can
 468          * find it again quickly.
 469          */
 470         tb = &mp->hashtable[HASHKEY(pgno)];
 471         for (b = tb->hnext; b != (BKT *)tb; b = b->hnext)
 472                 if (b->pgno == pgno) {
 473 #ifdef STATISTICS
 474                         ++mp->cachehit;
 475 #endif
 476                         return (b);
 477                 }
 478 #ifdef STATISTICS
 479         ++mp->cachemiss;
 480 #endif
 481         return (NULL);
 482 }
 483
 484 #ifdef STATISTICS
 485 /*
 486  * MPOOL_STAT -- cache statistics
 487  *
 488  * Parameters:
 489  *      mp:     mpool cookie
 490  */
 491 void
 492 mpool_stat(mp)
 493         MPOOL *mp;
 494 {
 495         BKT *b;
 496         int cnt;
 497         char *sep;
 498
 499         (void)fprintf(stderr, "%lu pages in the file\n", mp->npages);
 500         (void)fprintf(stderr,
 501             "page size %lu, cacheing %lu pages of %lu page max cache\n",
 502             mp->pagesize, mp->curcache, mp->maxcache);
 503         (void)fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n",
 504             mp->pageput, mp->pageget, mp->pagenew);
 505         (void)fprintf(stderr, "%lu page allocs, %lu page flushes\n",
 506             mp->pagealloc, mp->pageflush);
 507         if (mp->cachehit + mp->cachemiss)
 508                 (void)fprintf(stderr,
 509                     "%.0f%% cache hit rate (%lu hits, %lu misses)\n",
 510                     ((double)mp->cachehit / (mp->cachehit + mp->cachemiss))
 511                     * 100, mp->cachehit, mp->cachemiss);
 512         (void)fprintf(stderr, "%lu page reads, %lu page writes\n",
 513             mp->pageread, mp->pagewrite);
 514
 515         sep = "";
 516         cnt = 0;
 517         for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) {
 518                 (void)fprintf(stderr, "%s%ld", sep, b->pgno);
 519                 if (b->flags & MPOOL_DIRTY)
 520                         (void)fprintf(stderr, "d");
 521                 if (b->flags & MPOOL_PINNED)
 522                         (void)fprintf(stderr, "P");
 523                 if (++cnt == 10) {
 524                         sep = "\n";
 525                         cnt = 0;
 526                 } else
 527                         sep = ", ";
 528
 529         }
 530         (void)fprintf(stderr, "\n");
 531 }
 532 #endif
 533
 534 #ifdef DEBUG
 535 #if __STDC__
 536 #include <stdarg.h>
 537 #else
 538 #include <varargs.h>
 539 #endif
 540
 541 static void
 542 #if __STDC__
 543 __mpoolerr(const char *fmt, ...)
 544 #else
 545 __mpoolerr(fmt, va_alist)
 546         char *fmt;
 547         va_dcl
 548 #endif
 549 {
 550         va_list ap;
 551 #if __STDC__
 552         va_start(ap, fmt);
 553 #else
 554         va_start(ap);
 555 #endif
 556         (void)vfprintf(stderr, fmt, ap);
 557         va_end(ap);
 558         (void)fprintf(stderr, "\n");
 559         abort();
 560         /* NOTREACHED */
 561 }
 562 #endif