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