1 /* $OpenBSD: hash_page.c,v 1.21 2013/09/30 12:02:31 millert Exp $ */ 2 3 /*- 4 * Copyright (c) 1990, 1993, 1994 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Margo Seltzer. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. 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 /* 36 * PACKAGE: hashing 37 * 38 * DESCRIPTION: 39 * Page manipulation for hashing package. 40 * 41 * ROUTINES: 42 * 43 * External 44 * __get_page 45 * __add_ovflpage 46 * Internal 47 * overflow_page 48 * open_temp 49 */ 50 51 #include <errno.h> 52 #include <fcntl.h> 53 #include <limits.h> 54 #include <signal.h> 55 #include <stdio.h> 56 #include <stdlib.h> 57 #include <string.h> 58 #include <unistd.h> 59 #ifdef DEBUG 60 #include <assert.h> 61 #endif 62 63 #include <db.h> 64 #include "hash.h" 65 #include "page.h" 66 #include "extern.h" 67 68 static u_int32_t *fetch_bitmap(HTAB *, int); 69 static u_int32_t first_free(u_int32_t); 70 static int open_temp(HTAB *); 71 static u_int16_t overflow_page(HTAB *); 72 static void putpair(char *, const DBT *, const DBT *); 73 static void squeeze_key(u_int16_t *, const DBT *, const DBT *); 74 static int ugly_split(HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int); 75 76 #define PAGE_INIT(P) { \ 77 ((u_int16_t *)(P))[0] = 0; \ 78 ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \ 79 ((u_int16_t *)(P))[2] = hashp->BSIZE; \ 80 } 81 82 /* 83 * This is called AFTER we have verified that there is room on the page for 84 * the pair (PAIRFITS has returned true) so we go right ahead and start moving 85 * stuff on. 86 */ 87 static void 88 putpair(char *p, const DBT *key, const DBT *val) 89 { 90 u_int16_t *bp, n, off; 91 92 bp = (u_int16_t *)p; 93 94 /* Enter the key first. */ 95 n = bp[0]; 96 97 off = OFFSET(bp) - key->size; 98 memmove(p + off, key->data, key->size); 99 bp[++n] = off; 100 101 /* Now the data. */ 102 off -= val->size; 103 memmove(p + off, val->data, val->size); 104 bp[++n] = off; 105 106 /* Adjust page info. */ 107 bp[0] = n; 108 bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); 109 bp[n + 2] = off; 110 } 111 112 /* 113 * Returns: 114 * 0 OK 115 * -1 error 116 */ 117 int 118 __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) 119 { 120 u_int16_t *bp, newoff, pairlen; 121 int n; 122 123 bp = (u_int16_t *)bufp->page; 124 n = bp[0]; 125 126 if (bp[ndx + 1] < REAL_KEY) 127 return (__big_delete(hashp, bufp)); 128 if (ndx != 1) 129 newoff = bp[ndx - 1]; 130 else 131 newoff = hashp->BSIZE; 132 pairlen = newoff - bp[ndx + 1]; 133 134 if (ndx != (n - 1)) { 135 /* Hard Case -- need to shuffle keys */ 136 int i; 137 char *src = bufp->page + (int)OFFSET(bp); 138 char *dst = src + (int)pairlen; 139 memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); 140 141 /* Now adjust the pointers */ 142 for (i = ndx + 2; i <= n; i += 2) { 143 if (bp[i + 1] == OVFLPAGE) { 144 bp[i - 2] = bp[i]; 145 bp[i - 1] = bp[i + 1]; 146 } else { 147 bp[i - 2] = bp[i] + pairlen; 148 bp[i - 1] = bp[i + 1] + pairlen; 149 } 150 } 151 if (ndx == hashp->cndx) { 152 /* 153 * We just removed pair we were "pointing" to. 154 * By moving back the cndx we ensure subsequent 155 * hash_seq() calls won't skip over any entries. 156 */ 157 hashp->cndx -= 2; 158 } 159 } 160 /* Finally adjust the page data */ 161 bp[n] = OFFSET(bp) + pairlen; 162 bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); 163 bp[0] = n - 2; 164 hashp->NKEYS--; 165 166 bufp->flags |= BUF_MOD; 167 return (0); 168 } 169 /* 170 * Returns: 171 * 0 ==> OK 172 * -1 ==> Error 173 */ 174 int 175 __split_page(HTAB *hashp, u_int32_t obucket, u_int32_t nbucket) 176 { 177 BUFHEAD *new_bufp, *old_bufp; 178 u_int16_t *ino; 179 char *np; 180 DBT key, val; 181 int n, ndx, retval; 182 u_int16_t copyto, diff, off, moved; 183 char *op; 184 185 copyto = (u_int16_t)hashp->BSIZE; 186 off = (u_int16_t)hashp->BSIZE; 187 old_bufp = __get_buf(hashp, obucket, NULL, 0); 188 if (old_bufp == NULL) 189 return (-1); 190 new_bufp = __get_buf(hashp, nbucket, NULL, 0); 191 if (new_bufp == NULL) 192 return (-1); 193 194 old_bufp->flags |= (BUF_MOD | BUF_PIN); 195 new_bufp->flags |= (BUF_MOD | BUF_PIN); 196 197 ino = (u_int16_t *)(op = old_bufp->page); 198 np = new_bufp->page; 199 200 moved = 0; 201 202 for (n = 1, ndx = 1; n < ino[0]; n += 2) { 203 if (ino[n + 1] < REAL_KEY) { 204 retval = ugly_split(hashp, obucket, old_bufp, new_bufp, 205 (int)copyto, (int)moved); 206 old_bufp->flags &= ~BUF_PIN; 207 new_bufp->flags &= ~BUF_PIN; 208 return (retval); 209 210 } 211 key.data = (u_char *)op + ino[n]; 212 key.size = off - ino[n]; 213 214 if (__call_hash(hashp, key.data, key.size) == obucket) { 215 /* Don't switch page */ 216 diff = copyto - off; 217 if (diff) { 218 copyto = ino[n + 1] + diff; 219 memmove(op + copyto, op + ino[n + 1], 220 off - ino[n + 1]); 221 ino[ndx] = copyto + ino[n] - ino[n + 1]; 222 ino[ndx + 1] = copyto; 223 } else 224 copyto = ino[n + 1]; 225 ndx += 2; 226 } else { 227 /* Switch page */ 228 val.data = (u_char *)op + ino[n + 1]; 229 val.size = ino[n] - ino[n + 1]; 230 putpair(np, &key, &val); 231 moved += 2; 232 } 233 234 off = ino[n + 1]; 235 } 236 237 /* Now clean up the page */ 238 ino[0] -= moved; 239 FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3); 240 OFFSET(ino) = copyto; 241 242 #ifdef DEBUG3 243 (void)fprintf(stderr, "split %d/%d\n", 244 ((u_int16_t *)np)[0] / 2, 245 ((u_int16_t *)op)[0] / 2); 246 #endif 247 /* unpin both pages */ 248 old_bufp->flags &= ~BUF_PIN; 249 new_bufp->flags &= ~BUF_PIN; 250 return (0); 251 } 252 253 /* 254 * Called when we encounter an overflow or big key/data page during split 255 * handling. This is special cased since we have to begin checking whether 256 * the key/data pairs fit on their respective pages and because we may need 257 * overflow pages for both the old and new pages. 258 * 259 * The first page might be a page with regular key/data pairs in which case 260 * we have a regular overflow condition and just need to go on to the next 261 * page or it might be a big key/data pair in which case we need to fix the 262 * big key/data pair. 263 * 264 * Returns: 265 * 0 ==> success 266 * -1 ==> failure 267 */ 268 static int 269 ugly_split(HTAB *hashp, 270 u_int32_t obucket, /* Same as __split_page. */ 271 BUFHEAD *old_bufp, 272 BUFHEAD *new_bufp, 273 int copyto, /* First byte on page which contains key/data values. */ 274 int moved) /* Number of pairs moved to new page. */ 275 { 276 BUFHEAD *bufp; /* Buffer header for ino */ 277 u_int16_t *ino; /* Page keys come off of */ 278 u_int16_t *np; /* New page */ 279 u_int16_t *op; /* Page keys go on to if they aren't moving */ 280 281 BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ 282 DBT key, val; 283 SPLIT_RETURN ret; 284 u_int16_t n, off, ov_addr, scopyto; 285 char *cino; /* Character value of ino */ 286 287 bufp = old_bufp; 288 ino = (u_int16_t *)old_bufp->page; 289 np = (u_int16_t *)new_bufp->page; 290 op = (u_int16_t *)old_bufp->page; 291 last_bfp = NULL; 292 scopyto = (u_int16_t)copyto; /* ANSI */ 293 294 n = ino[0] - 1; 295 while (n < ino[0]) { 296 if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { 297 if (__big_split(hashp, old_bufp, 298 new_bufp, bufp, bufp->addr, obucket, &ret)) 299 return (-1); 300 old_bufp = ret.oldp; 301 if (!old_bufp) 302 return (-1); 303 op = (u_int16_t *)old_bufp->page; 304 new_bufp = ret.newp; 305 if (!new_bufp) 306 return (-1); 307 np = (u_int16_t *)new_bufp->page; 308 bufp = ret.nextp; 309 if (!bufp) 310 return (0); 311 cino = (char *)bufp->page; 312 ino = (u_int16_t *)cino; 313 last_bfp = ret.nextp; 314 } else if (ino[n + 1] == OVFLPAGE) { 315 ov_addr = ino[n]; 316 /* 317 * Fix up the old page -- the extra 2 are the fields 318 * which contained the overflow information. 319 */ 320 ino[0] -= (moved + 2); 321 FREESPACE(ino) = 322 scopyto - sizeof(u_int16_t) * (ino[0] + 3); 323 OFFSET(ino) = scopyto; 324 325 bufp = __get_buf(hashp, ov_addr, bufp, 0); 326 if (!bufp) 327 return (-1); 328 329 ino = (u_int16_t *)bufp->page; 330 n = 1; 331 scopyto = hashp->BSIZE; 332 moved = 0; 333 334 if (last_bfp) 335 __free_ovflpage(hashp, last_bfp); 336 last_bfp = bufp; 337 } 338 /* Move regular sized pairs of there are any */ 339 off = hashp->BSIZE; 340 for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { 341 cino = (char *)ino; 342 key.data = (u_char *)cino + ino[n]; 343 key.size = off - ino[n]; 344 val.data = (u_char *)cino + ino[n + 1]; 345 val.size = ino[n] - ino[n + 1]; 346 off = ino[n + 1]; 347 348 if (__call_hash(hashp, key.data, key.size) == obucket) { 349 /* Keep on old page */ 350 if (PAIRFITS(op, (&key), (&val))) 351 putpair((char *)op, &key, &val); 352 else { 353 old_bufp = 354 __add_ovflpage(hashp, old_bufp); 355 if (!old_bufp) 356 return (-1); 357 op = (u_int16_t *)old_bufp->page; 358 putpair((char *)op, &key, &val); 359 } 360 old_bufp->flags |= BUF_MOD; 361 } else { 362 /* Move to new page */ 363 if (PAIRFITS(np, (&key), (&val))) 364 putpair((char *)np, &key, &val); 365 else { 366 new_bufp = 367 __add_ovflpage(hashp, new_bufp); 368 if (!new_bufp) 369 return (-1); 370 np = (u_int16_t *)new_bufp->page; 371 putpair((char *)np, &key, &val); 372 } 373 new_bufp->flags |= BUF_MOD; 374 } 375 } 376 } 377 if (last_bfp) 378 __free_ovflpage(hashp, last_bfp); 379 return (0); 380 } 381 382 /* 383 * Add the given pair to the page 384 * 385 * Returns: 386 * 0 ==> OK 387 * 1 ==> failure 388 */ 389 int 390 __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) 391 { 392 u_int16_t *bp, *sop; 393 int do_expand; 394 395 bp = (u_int16_t *)bufp->page; 396 do_expand = 0; 397 while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) 398 /* Exception case */ 399 if (bp[2] == FULL_KEY_DATA && bp[0] == 2) 400 /* This is the last page of a big key/data pair 401 and we need to add another page */ 402 break; 403 else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { 404 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 405 if (!bufp) 406 return (-1); 407 bp = (u_int16_t *)bufp->page; 408 } else if (bp[bp[0]] != OVFLPAGE) { 409 /* Short key/data pairs, no more pages */ 410 break; 411 } else { 412 /* Try to squeeze key on this page */ 413 if (bp[2] >= REAL_KEY && 414 FREESPACE(bp) >= PAIRSIZE(key, val)) { 415 squeeze_key(bp, key, val); 416 goto stats; 417 } else { 418 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 419 if (!bufp) 420 return (-1); 421 bp = (u_int16_t *)bufp->page; 422 } 423 } 424 425 if (PAIRFITS(bp, key, val)) 426 putpair(bufp->page, key, val); 427 else { 428 do_expand = 1; 429 bufp = __add_ovflpage(hashp, bufp); 430 if (!bufp) 431 return (-1); 432 sop = (u_int16_t *)bufp->page; 433 434 if (PAIRFITS(sop, key, val)) 435 putpair((char *)sop, key, val); 436 else 437 if (__big_insert(hashp, bufp, key, val)) 438 return (-1); 439 } 440 stats: 441 bufp->flags |= BUF_MOD; 442 /* 443 * If the average number of keys per bucket exceeds the fill factor, 444 * expand the table. 445 */ 446 hashp->NKEYS++; 447 if (do_expand || 448 (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) 449 return (__expand_table(hashp)); 450 return (0); 451 } 452 453 /* 454 * 455 * Returns: 456 * pointer on success 457 * NULL on error 458 */ 459 BUFHEAD * 460 __add_ovflpage(HTAB *hashp, BUFHEAD *bufp) 461 { 462 u_int16_t *sp, ndx, ovfl_num; 463 #ifdef DEBUG1 464 int tmp1, tmp2; 465 #endif 466 sp = (u_int16_t *)bufp->page; 467 468 /* Check if we are dynamically determining the fill factor */ 469 if (hashp->FFACTOR == DEF_FFACTOR) { 470 hashp->FFACTOR = sp[0] >> 1; 471 if (hashp->FFACTOR < MIN_FFACTOR) 472 hashp->FFACTOR = MIN_FFACTOR; 473 } 474 bufp->flags |= BUF_MOD; 475 ovfl_num = overflow_page(hashp); 476 #ifdef DEBUG1 477 tmp1 = bufp->addr; 478 tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; 479 #endif 480 if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) 481 return (NULL); 482 bufp->ovfl->flags |= BUF_MOD; 483 #ifdef DEBUG1 484 (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", 485 tmp1, tmp2, bufp->ovfl->addr); 486 #endif 487 ndx = sp[0]; 488 /* 489 * Since a pair is allocated on a page only if there's room to add 490 * an overflow page, we know that the OVFL information will fit on 491 * the page. 492 */ 493 sp[ndx + 4] = OFFSET(sp); 494 sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; 495 sp[ndx + 1] = ovfl_num; 496 sp[ndx + 2] = OVFLPAGE; 497 sp[0] = ndx + 2; 498 #ifdef HASH_STATISTICS 499 hash_overflows++; 500 #endif 501 return (bufp->ovfl); 502 } 503 504 /* 505 * Returns: 506 * 0 indicates SUCCESS 507 * -1 indicates FAILURE 508 */ 509 int 510 __get_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_disk, 511 int is_bitmap) 512 { 513 int fd, page, size, rsize; 514 u_int16_t *bp; 515 516 fd = hashp->fp; 517 size = hashp->BSIZE; 518 519 if ((fd == -1) || !is_disk) { 520 PAGE_INIT(p); 521 return (0); 522 } 523 if (is_bucket) 524 page = BUCKET_TO_PAGE(bucket); 525 else 526 page = OADDR_TO_PAGE(bucket); 527 if ((rsize = pread(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 528 return (-1); 529 bp = (u_int16_t *)p; 530 if (!rsize) 531 bp[0] = 0; /* We hit the EOF, so initialize a new page */ 532 else 533 if (rsize != size) { 534 errno = EFTYPE; 535 return (-1); 536 } 537 if (!is_bitmap && !bp[0]) { 538 PAGE_INIT(p); 539 } else 540 if (hashp->LORDER != BYTE_ORDER) { 541 int i, max; 542 543 if (is_bitmap) { 544 max = hashp->BSIZE >> 2; /* divide by 4 */ 545 for (i = 0; i < max; i++) 546 M_32_SWAP(((int *)p)[i]); 547 } else { 548 M_16_SWAP(bp[0]); 549 max = bp[0] + 2; 550 for (i = 1; i <= max; i++) 551 M_16_SWAP(bp[i]); 552 } 553 } 554 return (0); 555 } 556 557 /* 558 * Write page p to disk 559 * 560 * Returns: 561 * 0 ==> OK 562 * -1 ==>failure 563 */ 564 int 565 __put_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_bitmap) 566 { 567 int fd, page, size, wsize; 568 569 size = hashp->BSIZE; 570 if ((hashp->fp == -1) && open_temp(hashp)) 571 return (-1); 572 fd = hashp->fp; 573 574 if (hashp->LORDER != BYTE_ORDER) { 575 int i, max; 576 577 if (is_bitmap) { 578 max = hashp->BSIZE >> 2; /* divide by 4 */ 579 for (i = 0; i < max; i++) 580 M_32_SWAP(((int *)p)[i]); 581 } else { 582 max = ((u_int16_t *)p)[0] + 2; 583 for (i = 0; i <= max; i++) 584 M_16_SWAP(((u_int16_t *)p)[i]); 585 } 586 } 587 if (is_bucket) 588 page = BUCKET_TO_PAGE(bucket); 589 else 590 page = OADDR_TO_PAGE(bucket); 591 if ((wsize = pwrite(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 592 /* Errno is set */ 593 return (-1); 594 if (wsize != size) { 595 errno = EFTYPE; 596 return (-1); 597 } 598 return (0); 599 } 600 601 #define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) 602 /* 603 * Initialize a new bitmap page. Bitmap pages are left in memory 604 * once they are read in. 605 */ 606 int 607 __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) 608 { 609 u_int32_t *ip; 610 int clearbytes, clearints; 611 612 if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 613 return (1); 614 hashp->nmaps++; 615 clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; 616 clearbytes = clearints << INT_TO_BYTE; 617 (void)memset((char *)ip, 0, clearbytes); 618 (void)memset(((char *)ip) + clearbytes, 0xFF, 619 hashp->BSIZE - clearbytes); 620 ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); 621 SETBIT(ip, 0); 622 hashp->BITMAPS[ndx] = (u_int16_t)pnum; 623 hashp->mapp[ndx] = ip; 624 return (0); 625 } 626 627 static u_int32_t 628 first_free(u_int32_t map) 629 { 630 u_int32_t i, mask; 631 632 mask = 0x1; 633 for (i = 0; i < BITS_PER_MAP; i++) { 634 if (!(mask & map)) 635 return (i); 636 mask = mask << 1; 637 } 638 return (i); 639 } 640 641 static u_int16_t 642 overflow_page(HTAB *hashp) 643 { 644 u_int32_t *freep; 645 int max_free, offset, splitnum; 646 u_int16_t addr; 647 int bit, first_page, free_bit, free_page, i, in_use_bits, j; 648 #ifdef DEBUG2 649 int tmp1, tmp2; 650 #endif 651 splitnum = hashp->OVFL_POINT; 652 max_free = hashp->SPARES[splitnum]; 653 654 free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); 655 free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); 656 657 /* Look through all the free maps to find the first free block */ 658 first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); 659 for ( i = first_page; i <= free_page; i++ ) { 660 if (!(freep = (u_int32_t *)hashp->mapp[i]) && 661 !(freep = fetch_bitmap(hashp, i))) 662 return (0); 663 if (i == free_page) 664 in_use_bits = free_bit; 665 else 666 in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; 667 668 if (i == first_page) { 669 bit = hashp->LAST_FREED & 670 ((hashp->BSIZE << BYTE_SHIFT) - 1); 671 j = bit / BITS_PER_MAP; 672 bit = bit & ~(BITS_PER_MAP - 1); 673 } else { 674 bit = 0; 675 j = 0; 676 } 677 for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) 678 if (freep[j] != ALL_SET) 679 goto found; 680 } 681 682 /* No Free Page Found */ 683 hashp->LAST_FREED = hashp->SPARES[splitnum]; 684 hashp->SPARES[splitnum]++; 685 offset = hashp->SPARES[splitnum] - 686 (splitnum ? hashp->SPARES[splitnum - 1] : 0); 687 688 #define OVMSG "HASH: Out of overflow pages. Increase page size\n" 689 if (offset > SPLITMASK) { 690 if (++splitnum >= NCACHED) { 691 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 692 errno = EFBIG; 693 return (0); 694 } 695 hashp->OVFL_POINT = splitnum; 696 hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 697 hashp->SPARES[splitnum-1]--; 698 offset = 1; 699 } 700 701 /* Check if we need to allocate a new bitmap page */ 702 if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { 703 free_page++; 704 if (free_page >= NCACHED) { 705 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 706 errno = EFBIG; 707 return (0); 708 } 709 /* 710 * This is tricky. The 1 indicates that you want the new page 711 * allocated with 1 clear bit. Actually, you are going to 712 * allocate 2 pages from this map. The first is going to be 713 * the map page, the second is the overflow page we were 714 * looking for. The init_bitmap routine automatically, sets 715 * the first bit of itself to indicate that the bitmap itself 716 * is in use. We would explicitly set the second bit, but 717 * don't have to if we tell init_bitmap not to leave it clear 718 * in the first place. 719 */ 720 if (__ibitmap(hashp, 721 (int)OADDR_OF(splitnum, offset), 1, free_page)) 722 return (0); 723 hashp->SPARES[splitnum]++; 724 #ifdef DEBUG2 725 free_bit = 2; 726 #endif 727 offset++; 728 if (offset > SPLITMASK) { 729 if (++splitnum >= NCACHED) { 730 (void)write(STDERR_FILENO, OVMSG, 731 sizeof(OVMSG) - 1); 732 errno = EFBIG; 733 return (0); 734 } 735 hashp->OVFL_POINT = splitnum; 736 hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 737 hashp->SPARES[splitnum-1]--; 738 offset = 0; 739 } 740 } else { 741 /* 742 * Free_bit addresses the last used bit. Bump it to address 743 * the first available bit. 744 */ 745 free_bit++; 746 SETBIT(freep, free_bit); 747 } 748 749 /* Calculate address of the new overflow page */ 750 addr = OADDR_OF(splitnum, offset); 751 #ifdef DEBUG2 752 (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 753 addr, free_bit, free_page); 754 #endif 755 return (addr); 756 757 found: 758 bit = bit + first_free(freep[j]); 759 SETBIT(freep, bit); 760 #ifdef DEBUG2 761 tmp1 = bit; 762 tmp2 = i; 763 #endif 764 /* 765 * Bits are addressed starting with 0, but overflow pages are addressed 766 * beginning at 1. Bit is a bit addressnumber, so we need to increment 767 * it to convert it to a page number. 768 */ 769 bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); 770 if (bit >= hashp->LAST_FREED) 771 hashp->LAST_FREED = bit - 1; 772 773 /* Calculate the split number for this page */ 774 for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); 775 offset = (i ? bit - hashp->SPARES[i - 1] : bit); 776 if (offset >= SPLITMASK) { 777 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 778 errno = EFBIG; 779 return (0); /* Out of overflow pages */ 780 } 781 addr = OADDR_OF(i, offset); 782 #ifdef DEBUG2 783 (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 784 addr, tmp1, tmp2); 785 #endif 786 787 /* Allocate and return the overflow page */ 788 return (addr); 789 } 790 791 /* 792 * Mark this overflow page as free. 793 */ 794 void 795 __free_ovflpage(HTAB *hashp, BUFHEAD *obufp) 796 { 797 u_int16_t addr; 798 u_int32_t *freep; 799 int bit_address, free_page, free_bit; 800 u_int16_t ndx; 801 802 addr = obufp->addr; 803 #ifdef DEBUG1 804 (void)fprintf(stderr, "Freeing %d\n", addr); 805 #endif 806 ndx = (((u_int16_t)addr) >> SPLITSHIFT); 807 bit_address = 808 (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; 809 if (bit_address < hashp->LAST_FREED) 810 hashp->LAST_FREED = bit_address; 811 free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); 812 free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); 813 814 if (!(freep = hashp->mapp[free_page])) 815 freep = fetch_bitmap(hashp, free_page); 816 #ifdef DEBUG 817 /* 818 * This had better never happen. It means we tried to read a bitmap 819 * that has already had overflow pages allocated off it, and we 820 * failed to read it from the file. 821 */ 822 if (!freep) 823 assert(0); 824 #endif 825 CLRBIT(freep, free_bit); 826 #ifdef DEBUG2 827 (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", 828 obufp->addr, free_bit, free_page); 829 #endif 830 __reclaim_buf(hashp, obufp); 831 } 832 833 /* 834 * Returns: 835 * 0 success 836 * -1 failure 837 */ 838 static int 839 open_temp(HTAB *hashp) 840 { 841 sigset_t set, oset; 842 int len; 843 char *envtmp = NULL; 844 char path[PATH_MAX]; 845 846 if (issetugid() == 0) 847 envtmp = getenv("TMPDIR"); 848 len = snprintf(path, 849 sizeof(path), "%s/_hash.XXXXXX", envtmp ? envtmp : "/tmp"); 850 if (len < 0 || len >= sizeof(path)) { 851 errno = ENAMETOOLONG; 852 return (-1); 853 } 854 855 /* Block signals; make sure file goes away at process exit. */ 856 (void)sigfillset(&set); 857 (void)sigprocmask(SIG_BLOCK, &set, &oset); 858 if ((hashp->fp = mkstemp(path)) != -1) { 859 (void)unlink(path); 860 (void)fcntl(hashp->fp, F_SETFD, FD_CLOEXEC); 861 } 862 (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); 863 return (hashp->fp != -1 ? 0 : -1); 864 } 865 866 /* 867 * We have to know that the key will fit, but the last entry on the page is 868 * an overflow pair, so we need to shift things. 869 */ 870 static void 871 squeeze_key(u_int16_t *sp, const DBT *key, const DBT *val) 872 { 873 char *p; 874 u_int16_t free_space, n, off, pageno; 875 876 p = (char *)sp; 877 n = sp[0]; 878 free_space = FREESPACE(sp); 879 off = OFFSET(sp); 880 881 pageno = sp[n - 1]; 882 off -= key->size; 883 sp[n - 1] = off; 884 memmove(p + off, key->data, key->size); 885 off -= val->size; 886 sp[n] = off; 887 memmove(p + off, val->data, val->size); 888 sp[0] = n + 2; 889 sp[n + 1] = pageno; 890 sp[n + 2] = OVFLPAGE; 891 FREESPACE(sp) = free_space - PAIRSIZE(key, val); 892 OFFSET(sp) = off; 893 } 894 895 static u_int32_t * 896 fetch_bitmap(HTAB *hashp, int ndx) 897 { 898 if (ndx >= hashp->nmaps) 899 return (NULL); 900 if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 901 return (NULL); 902 if (__get_page(hashp, 903 (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { 904 free(hashp->mapp[ndx]); 905 return (NULL); 906 } 907 return (hashp->mapp[ndx]); 908 } 909 910 #ifdef DEBUG4 911 int 912 print_chain(int addr) 913 { 914 BUFHEAD *bufp; 915 short *bp, oaddr; 916 917 (void)fprintf(stderr, "%d ", addr); 918 bufp = __get_buf(hashp, addr, NULL, 0); 919 bp = (short *)bufp->page; 920 while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || 921 ((bp[0] > 2) && bp[2] < REAL_KEY))) { 922 oaddr = bp[bp[0] - 1]; 923 (void)fprintf(stderr, "%d ", (int)oaddr); 924 bufp = __get_buf(hashp, (int)oaddr, bufp, 0); 925 bp = (short *)bufp->page; 926 } 927 (void)fprintf(stderr, "\n"); 928 } 929 #endif 930