lib/libc/db/hash/hash_page.c

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