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