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