Back to index

lightning-sunbird  0.9+nobinonly
hash_buf.c
Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993, 1994
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Margo Seltzer.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. ***REMOVED*** - see 
00017  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
00018  * 4. Neither the name of the University nor the names of its contributors
00019  *    may be used to endorse or promote products derived from this software
00020  *    without specific prior written permission.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00023  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00025  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00026  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00027  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00028  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00029  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00030  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00031  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00032  * SUCH DAMAGE.
00033  */
00034 
00035 #if defined(LIBC_SCCS) && !defined(lint)
00036 static char sccsid[] = "@(#)hash_buf.c    8.5 (Berkeley) 7/15/94";
00037 #endif /* LIBC_SCCS and not lint */
00038 
00039 #include "watcomfx.h"
00040 
00041 /*
00042  * PACKAGE: hash
00043  *
00044  * DESCRIPTION:
00045  *     Contains buffer management
00046  *
00047  * ROUTINES:
00048  * External
00049  *     __buf_init
00050  *     __get_buf
00051  *     __buf_free
00052  *     __reclaim_buf
00053  * Internal
00054  *     newbuf
00055  */
00056 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && !defined(XP_OS2_VACPP)
00057 #include <sys/param.h>
00058 #endif
00059 
00060 #include <errno.h>
00061 #include <stddef.h>
00062 #include <stdio.h>
00063 #include <stdlib.h>
00064 #include <string.h>
00065 
00066 #ifdef DEBUG
00067 #include <assert.h>
00068 #endif
00069 
00070 #include "mcom_db.h"
00071 #include "hash.h"
00072 #include "page.h"
00073 /* #include "extern.h" */
00074 
00075 static BUFHEAD *newbuf __P((HTAB *, uint32, BUFHEAD *));
00076 
00077 /* Unlink B from its place in the lru */
00078 #define BUF_REMOVE(B) { \
00079        (B)->prev->next = (B)->next; \
00080        (B)->next->prev = (B)->prev; \
00081 }
00082 
00083 /* Insert B after P */
00084 #define BUF_INSERT(B, P) { \
00085        (B)->next = (P)->next; \
00086        (B)->prev = (P); \
00087        (P)->next = (B); \
00088        (B)->next->prev = (B); \
00089 }
00090 
00091 #define       MRU    hashp->bufhead.next
00092 #define       LRU    hashp->bufhead.prev
00093 
00094 #define MRU_INSERT(B)       BUF_INSERT((B), &hashp->bufhead)
00095 #define LRU_INSERT(B)       BUF_INSERT((B), LRU)
00096 
00097 /*
00098  * We are looking for a buffer with address "addr".  If prev_bp is NULL, then
00099  * address is a bucket index.  If prev_bp is not NULL, then it points to the
00100  * page previous to an overflow page that we are trying to find.
00101  *
00102  * CAVEAT:  The buffer header accessed via prev_bp's ovfl field may no longer
00103  * be valid.  Therefore, you must always verify that its address matches the
00104  * address you are seeking.
00105  */
00106 extern BUFHEAD *
00107 __get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage)
00108 /* If prev_bp set, indicates a new overflow page. */
00109 {
00110        register BUFHEAD *bp;
00111        register uint32 is_disk_mask;
00112        register int is_disk, segment_ndx = 0;
00113        SEGMENT segp = 0;
00114 
00115        is_disk = 0;
00116        is_disk_mask = 0;
00117        if (prev_bp) {
00118               bp = prev_bp->ovfl;
00119               if (!bp || (bp->addr != addr))
00120                      bp = NULL;
00121               if (!newpage)
00122                      is_disk = BUF_DISK;
00123        } else {
00124               /* Grab buffer out of directory */
00125               segment_ndx = addr & (hashp->SGSIZE - 1);
00126 
00127               /* valid segment ensured by __call_hash() */
00128               segp = hashp->dir[addr >> hashp->SSHIFT];
00129 #ifdef DEBUG
00130               assert(segp != NULL);
00131 #endif  
00132 
00133               bp = PTROF(segp[segment_ndx]);
00134 
00135               is_disk_mask = ISDISK(segp[segment_ndx]);
00136               is_disk = is_disk_mask || !hashp->new_file;
00137        }
00138 
00139        if (!bp) {
00140               bp = newbuf(hashp, addr, prev_bp);
00141               if (!bp)
00142                      return(NULL);
00143               if(__get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
00144                 {
00145                      /* free bp and its page */
00146                      if(prev_bp)
00147                        {
00148                             /* if prev_bp is set then the new page that
00149                              * failed is hooked onto prev_bp as an overflow page.
00150                              * if we don't remove the pointer to the bad page
00151                              * we may try and access it later and we will die
00152                              * horribly because it will have already been
00153                              * free'd and overwritten with bogus data.
00154                              */
00155                             prev_bp->ovfl = NULL;
00156                        }
00157                      BUF_REMOVE(bp);
00158                      free(bp->page);
00159                      free(bp);
00160                      return (NULL);
00161                 }
00162 
00163               if (!prev_bp)               
00164                 {
00165 #if 0
00166                      /* 16 bit windows and mac can't handle the
00167                       * oring of the is disk flag.
00168                       */                  
00169                      segp[segment_ndx] =
00170                          (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask);
00171 #else   
00172                      /* set the is_disk thing inside the structure
00173                       */
00174                      bp->is_disk = is_disk_mask;
00175                      segp[segment_ndx] = bp;
00176 #endif
00177                 }
00178        } else {  
00179               BUF_REMOVE(bp);
00180               MRU_INSERT(bp);                 
00181        }
00182        return (bp);
00183 }
00184 
00185 /*
00186  * We need a buffer for this page. Either allocate one, or evict a resident
00187  * one (if we have as many buffers as we're allowed) and put this one in.
00188  *
00189  * If newbuf finds an error (returning NULL), it also sets errno.
00190  */
00191 static BUFHEAD *
00192 newbuf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp)
00193 {
00194        register BUFHEAD *bp;              /* The buffer we're going to use */
00195        register BUFHEAD *xbp;             /* Temp pointer */
00196        register BUFHEAD *next_xbp;
00197        SEGMENT segp;
00198        int segment_ndx;
00199        uint16 oaddr, *shortp;
00200 
00201        oaddr = 0;
00202        bp = LRU;
00203        /*
00204         * If LRU buffer is pinned, the buffer pool is too small. We need to
00205         * allocate more buffers.
00206         */
00207        if (hashp->nbufs || (bp->flags & BUF_PIN)) {
00208               /* Allocate a new one */
00209               if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL)
00210                      return (NULL);
00211 
00212               /* this memset is supposedly unnecessary but lets add
00213                * it anyways.
00214                */
00215               memset(bp, 0xff, sizeof(BUFHEAD));
00216 
00217               if ((bp->page = (char *)malloc((size_t)hashp->BSIZE)) == NULL) {
00218                      free(bp);
00219                      return (NULL);
00220               }
00221 
00222               /* this memset is supposedly unnecessary but lets add
00223                * it anyways.
00224                */
00225               memset(bp->page, 0xff, (size_t)hashp->BSIZE);
00226 
00227               if (hashp->nbufs)
00228                      hashp->nbufs--;
00229        } else {
00230               /* Kick someone out */
00231               BUF_REMOVE(bp);
00232               /*
00233                * If this is an overflow page with addr 0, it's already been
00234                * flushed back in an overflow chain and initialized.
00235                */
00236               if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
00237                      /*
00238                       * Set oaddr before __put_page so that you get it
00239                       * before bytes are swapped.
00240                       */
00241                      shortp = (uint16 *)bp->page;
00242                      if (shortp[0])
00243                        {
00244                             if(shortp[0] > (hashp->BSIZE / sizeof(uint16)))
00245                               {
00246                                    return(NULL);
00247                               }
00248                             oaddr = shortp[shortp[0] - 1];
00249                        }
00250                      if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
00251                          bp->addr, (int)IS_BUCKET(bp->flags), 0))
00252                             return (NULL);
00253                      /*
00254                       * Update the pointer to this page (i.e. invalidate it).
00255                       *
00256                       * If this is a new file (i.e. we created it at open
00257                       * time), make sure that we mark pages which have been
00258                       * written to disk so we retrieve them from disk later,
00259                       * rather than allocating new pages.
00260                       */
00261                      if (IS_BUCKET(bp->flags)) {
00262                             segment_ndx = bp->addr & (hashp->SGSIZE - 1);
00263                             segp = hashp->dir[bp->addr >> hashp->SSHIFT];
00264 #ifdef DEBUG
00265                             assert(segp != NULL);
00266 #endif
00267 
00268                             if (hashp->new_file &&
00269                                 ((bp->flags & BUF_MOD) ||
00270                                 ISDISK(segp[segment_ndx])))
00271                                    segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
00272                             else
00273                                    segp[segment_ndx] = NULL;
00274                      }
00275                      /*
00276                       * Since overflow pages can only be access by means of
00277                       * their bucket, free overflow pages associated with
00278                       * this bucket.
00279                       */
00280                      for (xbp = bp; xbp->ovfl;) {
00281                             next_xbp = xbp->ovfl;
00282                             xbp->ovfl = 0;
00283                             xbp = next_xbp;
00284 
00285                             /* leave pinned pages alone, we are still using
00286                              * them. */
00287                             if (xbp->flags & BUF_PIN) {
00288                                    continue;
00289                             }
00290 
00291                             /* Check that ovfl pointer is up date. */
00292                             if (IS_BUCKET(xbp->flags) ||
00293                                 (oaddr != xbp->addr))
00294                                    break;
00295 
00296                             shortp = (uint16 *)xbp->page;
00297                             if (shortp[0])
00298                               {
00299                                    /* LJM is the number of reported
00300                                     * pages way too much?
00301                                     */
00302                                    if(shortp[0] > hashp->BSIZE/sizeof(uint16))
00303                                           return NULL;
00304                                    /* set before __put_page */
00305                                    oaddr = shortp[shortp[0] - 1];
00306                               }
00307                             if ((xbp->flags & BUF_MOD) && __put_page(hashp,
00308                                 xbp->page, xbp->addr, 0, 0))
00309                                    return (NULL);
00310                             xbp->addr = 0;
00311                             xbp->flags = 0;
00312                             BUF_REMOVE(xbp);
00313                             LRU_INSERT(xbp);
00314                      }
00315               }
00316        }
00317 
00318        /* Now assign this buffer */
00319        bp->addr = addr;
00320 #ifdef DEBUG1
00321        (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
00322            bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
00323 #endif
00324        bp->ovfl = NULL;
00325        if (prev_bp) {
00326               /*
00327                * If prev_bp is set, this is an overflow page, hook it in to
00328                * the buffer overflow links.
00329                */
00330 #ifdef DEBUG1
00331               (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
00332                   prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
00333                   (bp ? bp->addr : 0));
00334 #endif
00335               prev_bp->ovfl = bp;
00336               bp->flags = 0;
00337        } else
00338               bp->flags = BUF_BUCKET;
00339        MRU_INSERT(bp);
00340        return (bp);
00341 }
00342 
00343 extern void __buf_init(HTAB *hashp, int32 nbytes)
00344 {
00345        BUFHEAD *bfp;
00346        int npages;
00347 
00348        bfp = &(hashp->bufhead);
00349        npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
00350        npages = PR_MAX(npages, MIN_BUFFERS);
00351 
00352        hashp->nbufs = npages;
00353        bfp->next = bfp;
00354        bfp->prev = bfp;
00355        /*
00356         * This space is calloc'd so these are already null.
00357         *
00358         * bfp->ovfl = NULL;
00359         * bfp->flags = 0;
00360         * bfp->page = NULL;
00361         * bfp->addr = 0;
00362         */
00363 }
00364 
00365 extern int
00366 __buf_free(HTAB *hashp, int do_free, int to_disk)
00367 {
00368        BUFHEAD *bp;
00369        int status = -1;
00370 
00371        /* Need to make sure that buffer manager has been initialized */
00372        if (!LRU)
00373               return (0);
00374        for (bp = LRU; bp != &hashp->bufhead;) {
00375               /* Check that the buffer is valid */
00376               if (bp->addr || IS_BUCKET(bp->flags)) {
00377                      if (to_disk && (bp->flags & BUF_MOD) &&
00378                          (status = __put_page(hashp, bp->page,
00379                          bp->addr, IS_BUCKET(bp->flags), 0))) {
00380                        
00381                             if (do_free) {
00382                                    if (bp->page)
00383                                           free(bp->page);
00384                                    BUF_REMOVE(bp);
00385                                    free(bp);
00386                             }
00387                             
00388                             return (status);
00389                      }
00390               }
00391               /* Check if we are freeing stuff */
00392               if (do_free) {
00393                      if (bp->page)
00394                             free(bp->page);
00395                      BUF_REMOVE(bp);
00396                      free(bp);
00397                      bp = LRU;
00398               } else
00399                      bp = bp->prev;
00400        }
00401        return (0);
00402 }
00403 
00404 extern void
00405 __reclaim_buf(HTAB *hashp, BUFHEAD *bp)
00406 {
00407        bp->ovfl = 0;
00408        bp->addr = 0;
00409        bp->flags = 0;
00410        BUF_REMOVE(bp);
00411        LRU_INSERT(bp);
00412 }