The Tor Browser / file comparison
comparison: security/nss/lib/dbm/src/hash_buf.c
security/nss/lib/dbm/src/hash_buf.c
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:40ebc604176d |
|---|---|
| 1 /*- | |
| 2 * Copyright (c) 1990, 1993, 1994 | |
| 3 * The Regents of the University of California. All rights reserved. | |
| 4 * | |
| 5 * This code is derived from software contributed to Berkeley by | |
| 6 * Margo Seltzer. | |
| 7 * | |
| 8 * Redistribution and use in source and binary forms, with or without | |
| 9 * modification, are permitted provided that the following conditions | |
| 10 * are met: | |
| 11 * 1. Redistributions of source code must retain the above copyright | |
| 12 * notice, this list of conditions and the following disclaimer. | |
| 13 * 2. Redistributions in binary form must reproduce the above copyright | |
| 14 * notice, this list of conditions and the following disclaimer in the | |
| 15 * documentation and/or other materials provided with the distribution. | |
| 16 * 3. ***REMOVED*** - see | |
| 17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change | |
| 18 * 4. Neither the name of the University nor the names of its contributors | |
| 19 * may be used to endorse or promote products derived from this software | |
| 20 * without specific prior written permission. | |
| 21 * | |
| 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
| 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
| 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
| 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
| 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
| 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
| 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
| 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
| 32 * SUCH DAMAGE. | |
| 33 */ | |
| 34 | |
| 35 #if defined(LIBC_SCCS) && !defined(lint) | |
| 36 static char sccsid[] = "@(#)hash_buf.c 8.5 (Berkeley) 7/15/94"; | |
| 37 #endif /* LIBC_SCCS and not lint */ | |
| 38 | |
| 39 /* | |
| 40 * PACKAGE: hash | |
| 41 * | |
| 42 * DESCRIPTION: | |
| 43 * Contains buffer management | |
| 44 * | |
| 45 * ROUTINES: | |
| 46 * External | |
| 47 * __buf_init | |
| 48 * __get_buf | |
| 49 * __buf_free | |
| 50 * __reclaim_buf | |
| 51 * Internal | |
| 52 * newbuf | |
| 53 */ | |
| 54 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) | |
| 55 #include <sys/param.h> | |
| 56 #endif | |
| 57 | |
| 58 #include <errno.h> | |
| 59 #include <stddef.h> | |
| 60 #include <stdio.h> | |
| 61 #include <stdlib.h> | |
| 62 #include <string.h> | |
| 63 | |
| 64 #ifdef DEBUG | |
| 65 #include <assert.h> | |
| 66 #endif | |
| 67 | |
| 68 #include "mcom_db.h" | |
| 69 #include "hash.h" | |
| 70 #include "page.h" | |
| 71 /* #include "extern.h" */ | |
| 72 | |
| 73 static BUFHEAD *newbuf __P((HTAB *, uint32, BUFHEAD *)); | |
| 74 | |
| 75 /* Unlink B from its place in the lru */ | |
| 76 #define BUF_REMOVE(B) { \ | |
| 77 (B)->prev->next = (B)->next; \ | |
| 78 (B)->next->prev = (B)->prev; \ | |
| 79 } | |
| 80 | |
| 81 /* Insert B after P */ | |
| 82 #define BUF_INSERT(B, P) { \ | |
| 83 (B)->next = (P)->next; \ | |
| 84 (B)->prev = (P); \ | |
| 85 (P)->next = (B); \ | |
| 86 (B)->next->prev = (B); \ | |
| 87 } | |
| 88 | |
| 89 #define MRU hashp->bufhead.next | |
| 90 #define LRU hashp->bufhead.prev | |
| 91 | |
| 92 #define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead) | |
| 93 #define LRU_INSERT(B) BUF_INSERT((B), LRU) | |
| 94 | |
| 95 /* | |
| 96 * We are looking for a buffer with address "addr". If prev_bp is NULL, then | |
| 97 * address is a bucket index. If prev_bp is not NULL, then it points to the | |
| 98 * page previous to an overflow page that we are trying to find. | |
| 99 * | |
| 100 * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer | |
| 101 * be valid. Therefore, you must always verify that its address matches the | |
| 102 * address you are seeking. | |
| 103 */ | |
| 104 extern BUFHEAD * | |
| 105 __get_buf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp, int newpage) | |
| 106 /* If prev_bp set, indicates a new overflow page. */ | |
| 107 { | |
| 108 register BUFHEAD *bp; | |
| 109 register uint32 is_disk_mask; | |
| 110 register int is_disk, segment_ndx = 0; | |
| 111 SEGMENT segp = 0; | |
| 112 | |
| 113 is_disk = 0; | |
| 114 is_disk_mask = 0; | |
| 115 if (prev_bp) { | |
| 116 bp = prev_bp->ovfl; | |
| 117 if (!bp || (bp->addr != addr)) | |
| 118 bp = NULL; | |
| 119 if (!newpage) | |
| 120 is_disk = BUF_DISK; | |
| 121 } else { | |
| 122 /* Grab buffer out of directory */ | |
| 123 segment_ndx = addr & (hashp->SGSIZE - 1); | |
| 124 | |
| 125 /* valid segment ensured by __call_hash() */ | |
| 126 segp = hashp->dir[addr >> hashp->SSHIFT]; | |
| 127 #ifdef DEBUG | |
| 128 assert(segp != NULL); | |
| 129 #endif | |
| 130 | |
| 131 bp = PTROF(segp[segment_ndx]); | |
| 132 | |
| 133 is_disk_mask = ISDISK(segp[segment_ndx]); | |
| 134 is_disk = is_disk_mask || !hashp->new_file; | |
| 135 } | |
| 136 | |
| 137 if (!bp) { | |
| 138 bp = newbuf(hashp, addr, prev_bp); | |
| 139 if (!bp) | |
| 140 return(NULL); | |
| 141 if(__get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0)) | |
| 142 { | |
| 143 /* free bp and its page */ | |
| 144 if(prev_bp) | |
| 145 { | |
| 146 /* if prev_bp is set then the new page that | |
| 147 * failed is hooked onto prev_bp as an overflow page. | |
| 148 * if we don't remove the pointer to the bad page | |
| 149 * we may try and access it later and we will die | |
| 150 * horribly because it will have already been | |
| 151 * free'd and overwritten with bogus data. | |
| 152 */ | |
| 153 prev_bp->ovfl = NULL; | |
| 154 } | |
| 155 BUF_REMOVE(bp); | |
| 156 free(bp->page); | |
| 157 free(bp); | |
| 158 return (NULL); | |
| 159 } | |
| 160 | |
| 161 if (!prev_bp) | |
| 162 { | |
| 163 #if 0 | |
| 164 /* 16 bit windows and mac can't handle the | |
| 165 * oring of the is disk flag. | |
| 166 */ | |
| 167 segp[segment_ndx] = | |
| 168 (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask); | |
| 169 #else | |
| 170 /* set the is_disk thing inside the structure | |
| 171 */ | |
| 172 bp->is_disk = is_disk_mask; | |
| 173 segp[segment_ndx] = bp; | |
| 174 #endif | |
| 175 } | |
| 176 } else { | |
| 177 BUF_REMOVE(bp); | |
| 178 MRU_INSERT(bp); | |
| 179 } | |
| 180 return (bp); | |
| 181 } | |
| 182 | |
| 183 /* | |
| 184 * We need a buffer for this page. Either allocate one, or evict a resident | |
| 185 * one (if we have as many buffers as we're allowed) and put this one in. | |
| 186 * | |
| 187 * If newbuf finds an error (returning NULL), it also sets errno. | |
| 188 */ | |
| 189 static BUFHEAD * | |
| 190 newbuf(HTAB *hashp, uint32 addr, BUFHEAD *prev_bp) | |
| 191 { | |
| 192 register BUFHEAD *bp; /* The buffer we're going to use */ | |
| 193 register BUFHEAD *xbp; /* Temp pointer */ | |
| 194 register BUFHEAD *next_xbp; | |
| 195 SEGMENT segp; | |
| 196 int segment_ndx; | |
| 197 uint16 oaddr, *shortp; | |
| 198 | |
| 199 oaddr = 0; | |
| 200 bp = LRU; | |
| 201 /* | |
| 202 * If LRU buffer is pinned, the buffer pool is too small. We need to | |
| 203 * allocate more buffers. | |
| 204 */ | |
| 205 if (hashp->nbufs || (bp->flags & BUF_PIN)) { | |
| 206 /* Allocate a new one */ | |
| 207 if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL) | |
| 208 return (NULL); | |
| 209 | |
| 210 /* this memset is supposedly unnecessary but lets add | |
| 211 * it anyways. | |
| 212 */ | |
| 213 memset(bp, 0xff, sizeof(BUFHEAD)); | |
| 214 | |
| 215 if ((bp->page = (char *)malloc((size_t)hashp->BSIZE)) == NULL) { | |
| 216 free(bp); | |
| 217 return (NULL); | |
| 218 } | |
| 219 | |
| 220 /* this memset is supposedly unnecessary but lets add | |
| 221 * it anyways. | |
| 222 */ | |
| 223 memset(bp->page, 0xff, (size_t)hashp->BSIZE); | |
| 224 | |
| 225 if (hashp->nbufs) | |
| 226 hashp->nbufs--; | |
| 227 } else { | |
| 228 /* Kick someone out */ | |
| 229 BUF_REMOVE(bp); | |
| 230 /* | |
| 231 * If this is an overflow page with addr 0, it's already been | |
| 232 * flushed back in an overflow chain and initialized. | |
| 233 */ | |
| 234 if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) { | |
| 235 /* | |
| 236 * Set oaddr before __put_page so that you get it | |
| 237 * before bytes are swapped. | |
| 238 */ | |
| 239 shortp = (uint16 *)bp->page; | |
| 240 if (shortp[0]) | |
| 241 { | |
| 242 if(shortp[0] > (hashp->BSIZE / sizeof(uint16))) | |
| 243 { | |
| 244 return(NULL); | |
| 245 } | |
| 246 oaddr = shortp[shortp[0] - 1]; | |
| 247 } | |
| 248 if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page, | |
| 249 bp->addr, (int)IS_BUCKET(bp->flags), 0)) | |
| 250 return (NULL); | |
| 251 /* | |
| 252 * Update the pointer to this page (i.e. invalidate it). | |
| 253 * | |
| 254 * If this is a new file (i.e. we created it at open | |
| 255 * time), make sure that we mark pages which have been | |
| 256 * written to disk so we retrieve them from disk later, | |
| 257 * rather than allocating new pages. | |
| 258 */ | |
| 259 if (IS_BUCKET(bp->flags)) { | |
| 260 segment_ndx = bp->addr & (hashp->SGSIZE - 1); | |
| 261 segp = hashp->dir[bp->addr >> hashp->SSHIFT]; | |
| 262 #ifdef DEBUG | |
| 263 assert(segp != NULL); | |
| 264 #endif | |
| 265 | |
| 266 if (hashp->new_file && | |
| 267 ((bp->flags & BUF_MOD) || | |
| 268 ISDISK(segp[segment_ndx]))) | |
| 269 segp[segment_ndx] = (BUFHEAD *)BUF_DISK; | |
| 270 else | |
| 271 segp[segment_ndx] = NULL; | |
| 272 } | |
| 273 /* | |
| 274 * Since overflow pages can only be access by means of | |
| 275 * their bucket, free overflow pages associated with | |
| 276 * this bucket. | |
| 277 */ | |
| 278 for (xbp = bp; xbp->ovfl;) { | |
| 279 next_xbp = xbp->ovfl; | |
| 280 xbp->ovfl = 0; | |
| 281 xbp = next_xbp; | |
| 282 | |
| 283 /* leave pinned pages alone, we are still using | |
| 284 * them. */ | |
| 285 if (xbp->flags & BUF_PIN) { | |
| 286 continue; | |
| 287 } | |
| 288 | |
| 289 /* Check that ovfl pointer is up date. */ | |
| 290 if (IS_BUCKET(xbp->flags) || | |
| 291 (oaddr != xbp->addr)) | |
| 292 break; | |
| 293 | |
| 294 shortp = (uint16 *)xbp->page; | |
| 295 if (shortp[0]) | |
| 296 { | |
| 297 /* LJM is the number of reported | |
| 298 * pages way too much? | |
| 299 */ | |
| 300 if(shortp[0] > hashp->BSIZE/sizeof(uint16)) | |
| 301 return NULL; | |
| 302 /* set before __put_page */ | |
| 303 oaddr = shortp[shortp[0] - 1]; | |
| 304 } | |
| 305 if ((xbp->flags & BUF_MOD) && __put_page(hashp, | |
| 306 xbp->page, xbp->addr, 0, 0)) | |
| 307 return (NULL); | |
| 308 xbp->addr = 0; | |
| 309 xbp->flags = 0; | |
| 310 BUF_REMOVE(xbp); | |
| 311 LRU_INSERT(xbp); | |
| 312 } | |
| 313 } | |
| 314 } | |
| 315 | |
| 316 /* Now assign this buffer */ | |
| 317 bp->addr = addr; | |
| 318 #ifdef DEBUG1 | |
| 319 (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", | |
| 320 bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); | |
| 321 #endif | |
| 322 bp->ovfl = NULL; | |
| 323 if (prev_bp) { | |
| 324 /* | |
| 325 * If prev_bp is set, this is an overflow page, hook it in to | |
| 326 * the buffer overflow links. | |
| 327 */ | |
| 328 #ifdef DEBUG1 | |
| 329 (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n", | |
| 330 prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0), | |
| 331 (bp ? bp->addr : 0)); | |
| 332 #endif | |
| 333 prev_bp->ovfl = bp; | |
| 334 bp->flags = 0; | |
| 335 } else | |
| 336 bp->flags = BUF_BUCKET; | |
| 337 MRU_INSERT(bp); | |
| 338 return (bp); | |
| 339 } | |
| 340 | |
| 341 extern void __buf_init(HTAB *hashp, int32 nbytes) | |
| 342 { | |
| 343 BUFHEAD *bfp; | |
| 344 int npages; | |
| 345 | |
| 346 bfp = &(hashp->bufhead); | |
| 347 npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT; | |
| 348 npages = PR_MAX(npages, MIN_BUFFERS); | |
| 349 | |
| 350 hashp->nbufs = npages; | |
| 351 bfp->next = bfp; | |
| 352 bfp->prev = bfp; | |
| 353 /* | |
| 354 * This space is calloc'd so these are already null. | |
| 355 * | |
| 356 * bfp->ovfl = NULL; | |
| 357 * bfp->flags = 0; | |
| 358 * bfp->page = NULL; | |
| 359 * bfp->addr = 0; | |
| 360 */ | |
| 361 } | |
| 362 | |
| 363 extern int | |
| 364 __buf_free(HTAB *hashp, int do_free, int to_disk) | |
| 365 { | |
| 366 BUFHEAD *bp; | |
| 367 int status = -1; | |
| 368 | |
| 369 /* Need to make sure that buffer manager has been initialized */ | |
| 370 if (!LRU) | |
| 371 return (0); | |
| 372 for (bp = LRU; bp != &hashp->bufhead;) { | |
| 373 /* Check that the buffer is valid */ | |
| 374 if (bp->addr || IS_BUCKET(bp->flags)) { | |
| 375 if (to_disk && (bp->flags & BUF_MOD) && | |
| 376 (status = __put_page(hashp, bp->page, | |
| 377 bp->addr, IS_BUCKET(bp->flags), 0))) { | |
| 378 | |
| 379 if (do_free) { | |
| 380 if (bp->page) | |
| 381 free(bp->page); | |
| 382 BUF_REMOVE(bp); | |
| 383 free(bp); | |
| 384 } | |
| 385 | |
| 386 return (status); | |
| 387 } | |
| 388 } | |
| 389 /* Check if we are freeing stuff */ | |
| 390 if (do_free) { | |
| 391 if (bp->page) | |
| 392 free(bp->page); | |
| 393 BUF_REMOVE(bp); | |
| 394 free(bp); | |
| 395 bp = LRU; | |
| 396 } else | |
| 397 bp = bp->prev; | |
| 398 } | |
| 399 return (0); | |
| 400 } | |
| 401 | |
| 402 extern void | |
| 403 __reclaim_buf(HTAB *hashp, BUFHEAD *bp) | |
| 404 { | |
| 405 bp->ovfl = 0; | |
| 406 bp->addr = 0; | |
| 407 bp->flags = 0; | |
| 408 BUF_REMOVE(bp); | |
| 409 LRU_INSERT(bp); | |
| 410 } |
