1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/dbm/src/hash_buf.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,410 @@
1.4 +/*-
1.5 + * Copyright (c) 1990, 1993, 1994
1.6 + * The Regents of the University of California. All rights reserved.
1.7 + *
1.8 + * This code is derived from software contributed to Berkeley by
1.9 + * Margo Seltzer.
1.10 + *
1.11 + * Redistribution and use in source and binary forms, with or without
1.12 + * modification, are permitted provided that the following conditions
1.13 + * are met:
1.14 + * 1. Redistributions of source code must retain the above copyright
1.15 + * notice, this list of conditions and the following disclaimer.
1.16 + * 2. Redistributions in binary form must reproduce the above copyright
1.17 + * notice, this list of conditions and the following disclaimer in the
1.18 + * documentation and/or other materials provided with the distribution.
1.19 + * 3. ***REMOVED*** - see
1.20 + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
1.21 + * 4. Neither the name of the University nor the names of its contributors
1.22 + * may be used to endorse or promote products derived from this software
1.23 + * without specific prior written permission.
1.24 + *
1.25 + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1.26 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.27 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.28 + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
1.29 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.30 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.31 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.32 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.33 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.34 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.35 + * SUCH DAMAGE.
1.36 + */
1.37 +
1.38 +#if defined(LIBC_SCCS) && !defined(lint)
1.39 +static char sccsid[] = "@(#)hash_buf.c 8.5 (Berkeley) 7/15/94";
1.40 +#endif /* LIBC_SCCS and not lint */
1.41 +
1.42 +/*
1.43 + * PACKAGE: hash
1.44 + *
1.45 + * DESCRIPTION:
1.46 + * Contains buffer management
1.47 + *
1.48 + * ROUTINES:
1.49 + * External
1.50 + * __buf_init
1.51 + * __get_buf
1.52 + * __buf_free
1.53 + * __reclaim_buf
1.54 + * Internal
1.55 + * newbuf
1.56 + */
1.57 +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1.58 +#include <sys/param.h>
1.59 +#endif
1.60 +
1.61 +#include <errno.h>
1.62 +#include <stddef.h>
1.63 +#include <stdio.h>
1.64 +#include <stdlib.h>
1.65 +#include <string.h>
1.66 +
1.67 +#ifdef DEBUG
1.68 +#include <assert.h>
1.69 +#endif
1.70 +
1.71 +#include "mcom_db.h"
1.72 +#include "hash.h"
1.73 +#include "page.h"
1.74 +/* #include "extern.h" */
1.75 +
1.76 +static BUFHEAD *newbuf __P((HTAB *, uint32, BUFHEAD *));
1.77 +
1.78 +/* Unlink B from its place in the lru */
1.79 +#define BUF_REMOVE(B) { \
1.80 + (B)->prev->next = (B)->next; \
1.81 + (B)->next->prev = (B)->prev; \
1.82 +}
1.83 +
1.84 +/* Insert B after P */
1.85 +#define BUF_INSERT(B, P) { \
1.86 + (B)->next = (P)->next; \
1.87 + (B)->prev = (P); \
1.88 + (P)->next = (B); \
1.89 + (B)->next->prev = (B); \
1.90 +}
1.91 +
1.92 +#define MRU hashp->bufhead.next
1.93 +#define LRU hashp->bufhead.prev
1.94 +
1.95 +#define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead)
1.96 +#define LRU_INSERT(B) BUF_INSERT((B), LRU)
1.97 +
1.98 +/*
1.99 + * We are looking for a buffer with address "addr". If prev_bp is NULL, then
1.100 + * address is a bucket index. If prev_bp is not NULL, then it points to the
1.101 + * page previous to an overflow page that we are trying to find.
1.102 + *
1.103 + * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer
1.104 + * be valid. Therefore, you must always verify that its address matches the
1.105 + * address you are seeking.
1.106 + */
1.107 +extern BUFHEAD *
1.108 +__get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage)
1.109 +/* If prev_bp set, indicates a new overflow page. */
1.110 +{
1.111 + register BUFHEAD *bp;
1.112 + register uint32 is_disk_mask;
1.113 + register int is_disk, segment_ndx = 0;
1.114 + SEGMENT segp = 0;
1.115 +
1.116 + is_disk = 0;
1.117 + is_disk_mask = 0;
1.118 + if (prev_bp) {
1.119 + bp = prev_bp->ovfl;
1.120 + if (!bp || (bp->addr != addr))
1.121 + bp = NULL;
1.122 + if (!newpage)
1.123 + is_disk = BUF_DISK;
1.124 + } else {
1.125 + /* Grab buffer out of directory */
1.126 + segment_ndx = addr & (hashp->SGSIZE - 1);
1.127 +
1.128 + /* valid segment ensured by __call_hash() */
1.129 + segp = hashp->dir[addr >> hashp->SSHIFT];
1.130 +#ifdef DEBUG
1.131 + assert(segp != NULL);
1.132 +#endif
1.133 +
1.134 + bp = PTROF(segp[segment_ndx]);
1.135 +
1.136 + is_disk_mask = ISDISK(segp[segment_ndx]);
1.137 + is_disk = is_disk_mask || !hashp->new_file;
1.138 + }
1.139 +
1.140 + if (!bp) {
1.141 + bp = newbuf(hashp, addr, prev_bp);
1.142 + if (!bp)
1.143 + return(NULL);
1.144 + if(__get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
1.145 + {
1.146 + /* free bp and its page */
1.147 + if(prev_bp)
1.148 + {
1.149 + /* if prev_bp is set then the new page that
1.150 + * failed is hooked onto prev_bp as an overflow page.
1.151 + * if we don't remove the pointer to the bad page
1.152 + * we may try and access it later and we will die
1.153 + * horribly because it will have already been
1.154 + * free'd and overwritten with bogus data.
1.155 + */
1.156 + prev_bp->ovfl = NULL;
1.157 + }
1.158 + BUF_REMOVE(bp);
1.159 + free(bp->page);
1.160 + free(bp);
1.161 + return (NULL);
1.162 + }
1.163 +
1.164 + if (!prev_bp)
1.165 + {
1.166 +#if 0
1.167 + /* 16 bit windows and mac can't handle the
1.168 + * oring of the is disk flag.
1.169 + */
1.170 + segp[segment_ndx] =
1.171 + (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask);
1.172 +#else
1.173 + /* set the is_disk thing inside the structure
1.174 + */
1.175 + bp->is_disk = is_disk_mask;
1.176 + segp[segment_ndx] = bp;
1.177 +#endif
1.178 + }
1.179 + } else {
1.180 + BUF_REMOVE(bp);
1.181 + MRU_INSERT(bp);
1.182 + }
1.183 + return (bp);
1.184 +}
1.185 +
1.186 +/*
1.187 + * We need a buffer for this page. Either allocate one, or evict a resident
1.188 + * one (if we have as many buffers as we're allowed) and put this one in.
1.189 + *
1.190 + * If newbuf finds an error (returning NULL), it also sets errno.
1.191 + */
1.192 +static BUFHEAD *
1.193 +newbuf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp)
1.194 +{
1.195 + register BUFHEAD *bp; /* The buffer we're going to use */
1.196 + register BUFHEAD *xbp; /* Temp pointer */
1.197 + register BUFHEAD *next_xbp;
1.198 + SEGMENT segp;
1.199 + int segment_ndx;
1.200 + uint16 oaddr, *shortp;
1.201 +
1.202 + oaddr = 0;
1.203 + bp = LRU;
1.204 + /*
1.205 + * If LRU buffer is pinned, the buffer pool is too small. We need to
1.206 + * allocate more buffers.
1.207 + */
1.208 + if (hashp->nbufs || (bp->flags & BUF_PIN)) {
1.209 + /* Allocate a new one */
1.210 + if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL)
1.211 + return (NULL);
1.212 +
1.213 + /* this memset is supposedly unnecessary but lets add
1.214 + * it anyways.
1.215 + */
1.216 + memset(bp, 0xff, sizeof(BUFHEAD));
1.217 +
1.218 + if ((bp->page = (char *)malloc((size_t)hashp->BSIZE)) == NULL) {
1.219 + free(bp);
1.220 + return (NULL);
1.221 + }
1.222 +
1.223 + /* this memset is supposedly unnecessary but lets add
1.224 + * it anyways.
1.225 + */
1.226 + memset(bp->page, 0xff, (size_t)hashp->BSIZE);
1.227 +
1.228 + if (hashp->nbufs)
1.229 + hashp->nbufs--;
1.230 + } else {
1.231 + /* Kick someone out */
1.232 + BUF_REMOVE(bp);
1.233 + /*
1.234 + * If this is an overflow page with addr 0, it's already been
1.235 + * flushed back in an overflow chain and initialized.
1.236 + */
1.237 + if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
1.238 + /*
1.239 + * Set oaddr before __put_page so that you get it
1.240 + * before bytes are swapped.
1.241 + */
1.242 + shortp = (uint16 *)bp->page;
1.243 + if (shortp[0])
1.244 + {
1.245 + if(shortp[0] > (hashp->BSIZE / sizeof(uint16)))
1.246 + {
1.247 + return(NULL);
1.248 + }
1.249 + oaddr = shortp[shortp[0] - 1];
1.250 + }
1.251 + if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
1.252 + bp->addr, (int)IS_BUCKET(bp->flags), 0))
1.253 + return (NULL);
1.254 + /*
1.255 + * Update the pointer to this page (i.e. invalidate it).
1.256 + *
1.257 + * If this is a new file (i.e. we created it at open
1.258 + * time), make sure that we mark pages which have been
1.259 + * written to disk so we retrieve them from disk later,
1.260 + * rather than allocating new pages.
1.261 + */
1.262 + if (IS_BUCKET(bp->flags)) {
1.263 + segment_ndx = bp->addr & (hashp->SGSIZE - 1);
1.264 + segp = hashp->dir[bp->addr >> hashp->SSHIFT];
1.265 +#ifdef DEBUG
1.266 + assert(segp != NULL);
1.267 +#endif
1.268 +
1.269 + if (hashp->new_file &&
1.270 + ((bp->flags & BUF_MOD) ||
1.271 + ISDISK(segp[segment_ndx])))
1.272 + segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
1.273 + else
1.274 + segp[segment_ndx] = NULL;
1.275 + }
1.276 + /*
1.277 + * Since overflow pages can only be access by means of
1.278 + * their bucket, free overflow pages associated with
1.279 + * this bucket.
1.280 + */
1.281 + for (xbp = bp; xbp->ovfl;) {
1.282 + next_xbp = xbp->ovfl;
1.283 + xbp->ovfl = 0;
1.284 + xbp = next_xbp;
1.285 +
1.286 + /* leave pinned pages alone, we are still using
1.287 + * them. */
1.288 + if (xbp->flags & BUF_PIN) {
1.289 + continue;
1.290 + }
1.291 +
1.292 + /* Check that ovfl pointer is up date. */
1.293 + if (IS_BUCKET(xbp->flags) ||
1.294 + (oaddr != xbp->addr))
1.295 + break;
1.296 +
1.297 + shortp = (uint16 *)xbp->page;
1.298 + if (shortp[0])
1.299 + {
1.300 + /* LJM is the number of reported
1.301 + * pages way too much?
1.302 + */
1.303 + if(shortp[0] > hashp->BSIZE/sizeof(uint16))
1.304 + return NULL;
1.305 + /* set before __put_page */
1.306 + oaddr = shortp[shortp[0] - 1];
1.307 + }
1.308 + if ((xbp->flags & BUF_MOD) && __put_page(hashp,
1.309 + xbp->page, xbp->addr, 0, 0))
1.310 + return (NULL);
1.311 + xbp->addr = 0;
1.312 + xbp->flags = 0;
1.313 + BUF_REMOVE(xbp);
1.314 + LRU_INSERT(xbp);
1.315 + }
1.316 + }
1.317 + }
1.318 +
1.319 + /* Now assign this buffer */
1.320 + bp->addr = addr;
1.321 +#ifdef DEBUG1
1.322 + (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
1.323 + bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
1.324 +#endif
1.325 + bp->ovfl = NULL;
1.326 + if (prev_bp) {
1.327 + /*
1.328 + * If prev_bp is set, this is an overflow page, hook it in to
1.329 + * the buffer overflow links.
1.330 + */
1.331 +#ifdef DEBUG1
1.332 + (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
1.333 + prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
1.334 + (bp ? bp->addr : 0));
1.335 +#endif
1.336 + prev_bp->ovfl = bp;
1.337 + bp->flags = 0;
1.338 + } else
1.339 + bp->flags = BUF_BUCKET;
1.340 + MRU_INSERT(bp);
1.341 + return (bp);
1.342 +}
1.343 +
1.344 +extern void __buf_init(HTAB *hashp, int32 nbytes)
1.345 +{
1.346 + BUFHEAD *bfp;
1.347 + int npages;
1.348 +
1.349 + bfp = &(hashp->bufhead);
1.350 + npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
1.351 + npages = PR_MAX(npages, MIN_BUFFERS);
1.352 +
1.353 + hashp->nbufs = npages;
1.354 + bfp->next = bfp;
1.355 + bfp->prev = bfp;
1.356 + /*
1.357 + * This space is calloc'd so these are already null.
1.358 + *
1.359 + * bfp->ovfl = NULL;
1.360 + * bfp->flags = 0;
1.361 + * bfp->page = NULL;
1.362 + * bfp->addr = 0;
1.363 + */
1.364 +}
1.365 +
1.366 +extern int
1.367 +__buf_free(HTAB *hashp, int do_free, int to_disk)
1.368 +{
1.369 + BUFHEAD *bp;
1.370 + int status = -1;
1.371 +
1.372 + /* Need to make sure that buffer manager has been initialized */
1.373 + if (!LRU)
1.374 + return (0);
1.375 + for (bp = LRU; bp != &hashp->bufhead;) {
1.376 + /* Check that the buffer is valid */
1.377 + if (bp->addr || IS_BUCKET(bp->flags)) {
1.378 + if (to_disk && (bp->flags & BUF_MOD) &&
1.379 + (status = __put_page(hashp, bp->page,
1.380 + bp->addr, IS_BUCKET(bp->flags), 0))) {
1.381 +
1.382 + if (do_free) {
1.383 + if (bp->page)
1.384 + free(bp->page);
1.385 + BUF_REMOVE(bp);
1.386 + free(bp);
1.387 + }
1.388 +
1.389 + return (status);
1.390 + }
1.391 + }
1.392 + /* Check if we are freeing stuff */
1.393 + if (do_free) {
1.394 + if (bp->page)
1.395 + free(bp->page);
1.396 + BUF_REMOVE(bp);
1.397 + free(bp);
1.398 + bp = LRU;
1.399 + } else
1.400 + bp = bp->prev;
1.401 + }
1.402 + return (0);
1.403 +}
1.404 +
1.405 +extern void
1.406 +__reclaim_buf(HTAB *hashp, BUFHEAD *bp)
1.407 +{
1.408 + bp->ovfl = 0;
1.409 + bp->addr = 0;
1.410 + bp->flags = 0;
1.411 + BUF_REMOVE(bp);
1.412 + LRU_INSERT(bp);
1.413 +}
