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