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