hash_page.c revision 190487
11573Srgrimes/*- 214287Spst * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Margo Seltzer. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3414287Spststatic char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692889Sobrien#include <sys/cdefs.h> 3792889Sobrien__FBSDID("$FreeBSD: head/lib/libc/db/hash/hash_page.c 190487 2009-03-28 06:12:39Z delphij $"); 381573Srgrimes 391573Srgrimes/* 401573Srgrimes * PACKAGE: hashing 411573Srgrimes * 421573Srgrimes * DESCRIPTION: 431573Srgrimes * Page manipulation for hashing package. 441573Srgrimes * 451573Srgrimes * ROUTINES: 461573Srgrimes * 471573Srgrimes * External 481573Srgrimes * __get_page 491573Srgrimes * __add_ovflpage 501573Srgrimes * Internal 511573Srgrimes * overflow_page 521573Srgrimes * open_temp 531573Srgrimes */ 541573Srgrimes 5571579Sdeischen#include "namespace.h" 56190485Sdelphij#include <sys/param.h> 571573Srgrimes 581573Srgrimes#include <errno.h> 591573Srgrimes#include <fcntl.h> 601573Srgrimes#include <signal.h> 611573Srgrimes#include <stdio.h> 621573Srgrimes#include <stdlib.h> 631573Srgrimes#include <string.h> 641573Srgrimes#include <unistd.h> 651573Srgrimes#ifdef DEBUG 661573Srgrimes#include <assert.h> 671573Srgrimes#endif 6871579Sdeischen#include "un-namespace.h" 691573Srgrimes 701573Srgrimes#include <db.h> 711573Srgrimes#include "hash.h" 721573Srgrimes#include "page.h" 731573Srgrimes#include "extern.h" 741573Srgrimes 75189291Sdelphijstatic u_int32_t *fetch_bitmap(HTAB *, int); 76189291Sdelphijstatic u_int32_t first_free(u_int32_t); 77189291Sdelphijstatic int open_temp(HTAB *); 78189291Sdelphijstatic u_int16_t overflow_page(HTAB *); 79189291Sdelphijstatic void putpair(char *, const DBT *, const DBT *); 80189291Sdelphijstatic void squeeze_key(u_int16_t *, const DBT *, const DBT *); 81189291Sdelphijstatic int ugly_split(HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int); 821573Srgrimes 831573Srgrimes#define PAGE_INIT(P) { \ 8414287Spst ((u_int16_t *)(P))[0] = 0; \ 8514287Spst ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \ 8614287Spst ((u_int16_t *)(P))[2] = hashp->BSIZE; \ 871573Srgrimes} 881573Srgrimes 891573Srgrimes/* 901573Srgrimes * This is called AFTER we have verified that there is room on the page for 911573Srgrimes * the pair (PAIRFITS has returned true) so we go right ahead and start moving 921573Srgrimes * stuff on. 931573Srgrimes */ 941573Srgrimesstatic void 95189291Sdelphijputpair(char *p, const DBT *key, const DBT *val) 961573Srgrimes{ 9792889Sobrien u_int16_t *bp, n, off; 981573Srgrimes 9914287Spst bp = (u_int16_t *)p; 1001573Srgrimes 1011573Srgrimes /* Enter the key first. */ 1021573Srgrimes n = bp[0]; 1031573Srgrimes 1041573Srgrimes off = OFFSET(bp) - key->size; 1051573Srgrimes memmove(p + off, key->data, key->size); 1061573Srgrimes bp[++n] = off; 1071573Srgrimes 1081573Srgrimes /* Now the data. */ 1091573Srgrimes off -= val->size; 1101573Srgrimes memmove(p + off, val->data, val->size); 1111573Srgrimes bp[++n] = off; 1121573Srgrimes 1131573Srgrimes /* Adjust page info. */ 1141573Srgrimes bp[0] = n; 11514287Spst bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); 1161573Srgrimes bp[n + 2] = off; 1171573Srgrimes} 1181573Srgrimes 1191573Srgrimes/* 1201573Srgrimes * Returns: 1211573Srgrimes * 0 OK 1221573Srgrimes * -1 error 1231573Srgrimes */ 124189291Sdelphijint 125189291Sdelphij__delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) 1261573Srgrimes{ 12792889Sobrien u_int16_t *bp, newoff; 12892889Sobrien int n; 12914287Spst u_int16_t pairlen; 1301573Srgrimes 13114287Spst bp = (u_int16_t *)bufp->page; 1321573Srgrimes n = bp[0]; 1331573Srgrimes 1341573Srgrimes if (bp[ndx + 1] < REAL_KEY) 1351573Srgrimes return (__big_delete(hashp, bufp)); 1361573Srgrimes if (ndx != 1) 1371573Srgrimes newoff = bp[ndx - 1]; 1381573Srgrimes else 1391573Srgrimes newoff = hashp->BSIZE; 1401573Srgrimes pairlen = newoff - bp[ndx + 1]; 1411573Srgrimes 1421573Srgrimes if (ndx != (n - 1)) { 1431573Srgrimes /* Hard Case -- need to shuffle keys */ 14492889Sobrien int i; 14592889Sobrien char *src = bufp->page + (int)OFFSET(bp); 14692889Sobrien char *dst = src + (int)pairlen; 1471573Srgrimes memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); 1481573Srgrimes 1491573Srgrimes /* Now adjust the pointers */ 1501573Srgrimes for (i = ndx + 2; i <= n; i += 2) { 1511573Srgrimes if (bp[i + 1] == OVFLPAGE) { 1521573Srgrimes bp[i - 2] = bp[i]; 1531573Srgrimes bp[i - 1] = bp[i + 1]; 1541573Srgrimes } else { 1551573Srgrimes bp[i - 2] = bp[i] + pairlen; 1561573Srgrimes bp[i - 1] = bp[i + 1] + pairlen; 1571573Srgrimes } 1581573Srgrimes } 1591573Srgrimes } 1601573Srgrimes /* Finally adjust the page data */ 1611573Srgrimes bp[n] = OFFSET(bp) + pairlen; 16214287Spst bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); 1631573Srgrimes bp[0] = n - 2; 1641573Srgrimes hashp->NKEYS--; 1651573Srgrimes 1661573Srgrimes bufp->flags |= BUF_MOD; 1671573Srgrimes return (0); 1681573Srgrimes} 1691573Srgrimes/* 1701573Srgrimes * Returns: 1711573Srgrimes * 0 ==> OK 1721573Srgrimes * -1 ==> Error 1731573Srgrimes */ 174189291Sdelphijint 175189291Sdelphij__split_page(HTAB *hashp, u_int32_t obucket, u_int32_t nbucket) 1761573Srgrimes{ 17792889Sobrien BUFHEAD *new_bufp, *old_bufp; 17892889Sobrien u_int16_t *ino; 17992889Sobrien char *np; 1801573Srgrimes DBT key, val; 1811573Srgrimes int n, ndx, retval; 18214287Spst u_int16_t copyto, diff, off, moved; 1831573Srgrimes char *op; 1841573Srgrimes 18514287Spst copyto = (u_int16_t)hashp->BSIZE; 18614287Spst off = (u_int16_t)hashp->BSIZE; 1871573Srgrimes old_bufp = __get_buf(hashp, obucket, NULL, 0); 1881573Srgrimes if (old_bufp == NULL) 1891573Srgrimes return (-1); 1901573Srgrimes new_bufp = __get_buf(hashp, nbucket, NULL, 0); 1911573Srgrimes if (new_bufp == NULL) 1921573Srgrimes return (-1); 1931573Srgrimes 1941573Srgrimes old_bufp->flags |= (BUF_MOD | BUF_PIN); 1951573Srgrimes new_bufp->flags |= (BUF_MOD | BUF_PIN); 1961573Srgrimes 19714287Spst ino = (u_int16_t *)(op = old_bufp->page); 1981573Srgrimes np = new_bufp->page; 1991573Srgrimes 2001573Srgrimes moved = 0; 2011573Srgrimes 2021573Srgrimes for (n = 1, ndx = 1; n < ino[0]; n += 2) { 2031573Srgrimes if (ino[n + 1] < REAL_KEY) { 2041573Srgrimes retval = ugly_split(hashp, obucket, old_bufp, new_bufp, 2051573Srgrimes (int)copyto, (int)moved); 2061573Srgrimes old_bufp->flags &= ~BUF_PIN; 2071573Srgrimes new_bufp->flags &= ~BUF_PIN; 2081573Srgrimes return (retval); 2091573Srgrimes 2101573Srgrimes } 2111573Srgrimes key.data = (u_char *)op + ino[n]; 2121573Srgrimes key.size = off - ino[n]; 2131573Srgrimes 2141573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 2151573Srgrimes /* Don't switch page */ 2161573Srgrimes diff = copyto - off; 2171573Srgrimes if (diff) { 2181573Srgrimes copyto = ino[n + 1] + diff; 2191573Srgrimes memmove(op + copyto, op + ino[n + 1], 2201573Srgrimes off - ino[n + 1]); 2211573Srgrimes ino[ndx] = copyto + ino[n] - ino[n + 1]; 2221573Srgrimes ino[ndx + 1] = copyto; 2231573Srgrimes } else 2241573Srgrimes copyto = ino[n + 1]; 2251573Srgrimes ndx += 2; 2261573Srgrimes } else { 2271573Srgrimes /* Switch page */ 2281573Srgrimes val.data = (u_char *)op + ino[n + 1]; 2291573Srgrimes val.size = ino[n] - ino[n + 1]; 2301573Srgrimes putpair(np, &key, &val); 2311573Srgrimes moved += 2; 2321573Srgrimes } 2331573Srgrimes 2341573Srgrimes off = ino[n + 1]; 2351573Srgrimes } 2361573Srgrimes 2371573Srgrimes /* Now clean up the page */ 2381573Srgrimes ino[0] -= moved; 23914287Spst FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3); 2401573Srgrimes OFFSET(ino) = copyto; 2411573Srgrimes 2421573Srgrimes#ifdef DEBUG3 2431573Srgrimes (void)fprintf(stderr, "split %d/%d\n", 24414287Spst ((u_int16_t *)np)[0] / 2, 24514287Spst ((u_int16_t *)op)[0] / 2); 2461573Srgrimes#endif 2471573Srgrimes /* unpin both pages */ 2481573Srgrimes old_bufp->flags &= ~BUF_PIN; 2491573Srgrimes new_bufp->flags &= ~BUF_PIN; 2501573Srgrimes return (0); 2511573Srgrimes} 2521573Srgrimes 2531573Srgrimes/* 2541573Srgrimes * Called when we encounter an overflow or big key/data page during split 2551573Srgrimes * handling. This is special cased since we have to begin checking whether 2561573Srgrimes * the key/data pairs fit on their respective pages and because we may need 2571573Srgrimes * overflow pages for both the old and new pages. 2581573Srgrimes * 2591573Srgrimes * The first page might be a page with regular key/data pairs in which case 2601573Srgrimes * we have a regular overflow condition and just need to go on to the next 2611573Srgrimes * page or it might be a big key/data pair in which case we need to fix the 2621573Srgrimes * big key/data pair. 2631573Srgrimes * 2641573Srgrimes * Returns: 2651573Srgrimes * 0 ==> success 2661573Srgrimes * -1 ==> failure 2671573Srgrimes */ 2681573Srgrimesstatic int 269189291Sdelphijugly_split(HTAB *hashp, 270189291Sdelphij u_int32_t obucket, /* Same as __split_page. */ 271189291Sdelphij BUFHEAD *old_bufp, 272189291Sdelphij BUFHEAD *new_bufp, 273189291Sdelphij int copyto, /* First byte on page which contains key/data values. */ 274189291Sdelphij int moved) /* Number of pairs moved to new page. */ 2751573Srgrimes{ 276189291Sdelphij BUFHEAD *bufp; /* Buffer header for ino */ 277189291Sdelphij u_int16_t *ino; /* Page keys come off of */ 278189291Sdelphij u_int16_t *np; /* New page */ 279189291Sdelphij u_int16_t *op; /* Page keys go on to if they aren't moving */ 2801573Srgrimes 2811573Srgrimes BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ 2821573Srgrimes DBT key, val; 2831573Srgrimes SPLIT_RETURN ret; 28414287Spst u_int16_t n, off, ov_addr, scopyto; 2851573Srgrimes char *cino; /* Character value of ino */ 2861573Srgrimes 2871573Srgrimes bufp = old_bufp; 28814287Spst ino = (u_int16_t *)old_bufp->page; 28914287Spst np = (u_int16_t *)new_bufp->page; 29014287Spst op = (u_int16_t *)old_bufp->page; 2911573Srgrimes last_bfp = NULL; 29214287Spst scopyto = (u_int16_t)copyto; /* ANSI */ 2931573Srgrimes 2941573Srgrimes n = ino[0] - 1; 2951573Srgrimes while (n < ino[0]) { 2961573Srgrimes if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { 2971573Srgrimes if (__big_split(hashp, old_bufp, 2981573Srgrimes new_bufp, bufp, bufp->addr, obucket, &ret)) 2991573Srgrimes return (-1); 3001573Srgrimes old_bufp = ret.oldp; 3011573Srgrimes if (!old_bufp) 3021573Srgrimes return (-1); 30314287Spst op = (u_int16_t *)old_bufp->page; 3041573Srgrimes new_bufp = ret.newp; 3051573Srgrimes if (!new_bufp) 3061573Srgrimes return (-1); 30714287Spst np = (u_int16_t *)new_bufp->page; 3081573Srgrimes bufp = ret.nextp; 3091573Srgrimes if (!bufp) 3101573Srgrimes return (0); 3111573Srgrimes cino = (char *)bufp->page; 31214287Spst ino = (u_int16_t *)cino; 3131573Srgrimes last_bfp = ret.nextp; 3141573Srgrimes } else if (ino[n + 1] == OVFLPAGE) { 3151573Srgrimes ov_addr = ino[n]; 3161573Srgrimes /* 3171573Srgrimes * Fix up the old page -- the extra 2 are the fields 3181573Srgrimes * which contained the overflow information. 3191573Srgrimes */ 3201573Srgrimes ino[0] -= (moved + 2); 3211573Srgrimes FREESPACE(ino) = 32214287Spst scopyto - sizeof(u_int16_t) * (ino[0] + 3); 3231573Srgrimes OFFSET(ino) = scopyto; 3241573Srgrimes 3251573Srgrimes bufp = __get_buf(hashp, ov_addr, bufp, 0); 3261573Srgrimes if (!bufp) 3271573Srgrimes return (-1); 3281573Srgrimes 32914287Spst ino = (u_int16_t *)bufp->page; 3301573Srgrimes n = 1; 3311573Srgrimes scopyto = hashp->BSIZE; 3321573Srgrimes moved = 0; 3331573Srgrimes 3341573Srgrimes if (last_bfp) 3351573Srgrimes __free_ovflpage(hashp, last_bfp); 3361573Srgrimes last_bfp = bufp; 3371573Srgrimes } 3381573Srgrimes /* Move regular sized pairs of there are any */ 3391573Srgrimes off = hashp->BSIZE; 3401573Srgrimes for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { 3411573Srgrimes cino = (char *)ino; 3421573Srgrimes key.data = (u_char *)cino + ino[n]; 3431573Srgrimes key.size = off - ino[n]; 3441573Srgrimes val.data = (u_char *)cino + ino[n + 1]; 3451573Srgrimes val.size = ino[n] - ino[n + 1]; 3461573Srgrimes off = ino[n + 1]; 3471573Srgrimes 3481573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 3491573Srgrimes /* Keep on old page */ 3501573Srgrimes if (PAIRFITS(op, (&key), (&val))) 3511573Srgrimes putpair((char *)op, &key, &val); 3521573Srgrimes else { 3531573Srgrimes old_bufp = 3541573Srgrimes __add_ovflpage(hashp, old_bufp); 3551573Srgrimes if (!old_bufp) 3561573Srgrimes return (-1); 35714287Spst op = (u_int16_t *)old_bufp->page; 3581573Srgrimes putpair((char *)op, &key, &val); 3591573Srgrimes } 3601573Srgrimes old_bufp->flags |= BUF_MOD; 3611573Srgrimes } else { 3621573Srgrimes /* Move to new page */ 3631573Srgrimes if (PAIRFITS(np, (&key), (&val))) 3641573Srgrimes putpair((char *)np, &key, &val); 3651573Srgrimes else { 3661573Srgrimes new_bufp = 3671573Srgrimes __add_ovflpage(hashp, new_bufp); 3681573Srgrimes if (!new_bufp) 3691573Srgrimes return (-1); 37014287Spst np = (u_int16_t *)new_bufp->page; 3711573Srgrimes putpair((char *)np, &key, &val); 3721573Srgrimes } 3731573Srgrimes new_bufp->flags |= BUF_MOD; 3741573Srgrimes } 3751573Srgrimes } 3761573Srgrimes } 3771573Srgrimes if (last_bfp) 3781573Srgrimes __free_ovflpage(hashp, last_bfp); 3791573Srgrimes return (0); 3801573Srgrimes} 3811573Srgrimes 3821573Srgrimes/* 3831573Srgrimes * Add the given pair to the page 3841573Srgrimes * 3851573Srgrimes * Returns: 3861573Srgrimes * 0 ==> OK 3871573Srgrimes * 1 ==> failure 3881573Srgrimes */ 389189291Sdelphijint 390189291Sdelphij__addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) 3911573Srgrimes{ 39292889Sobrien u_int16_t *bp, *sop; 3931573Srgrimes int do_expand; 3941573Srgrimes 39514287Spst bp = (u_int16_t *)bufp->page; 3961573Srgrimes do_expand = 0; 3971573Srgrimes while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) 3981573Srgrimes /* Exception case */ 3991573Srgrimes if (bp[2] == FULL_KEY_DATA && bp[0] == 2) 4001573Srgrimes /* This is the last page of a big key/data pair 4011573Srgrimes and we need to add another page */ 4021573Srgrimes break; 4031573Srgrimes else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { 4041573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4051573Srgrimes if (!bufp) 4061573Srgrimes return (-1); 40714287Spst bp = (u_int16_t *)bufp->page; 4081573Srgrimes } else 4091573Srgrimes /* Try to squeeze key on this page */ 4101573Srgrimes if (FREESPACE(bp) > PAIRSIZE(key, val)) { 4111573Srgrimes squeeze_key(bp, key, val); 4121573Srgrimes return (0); 4131573Srgrimes } else { 4141573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4151573Srgrimes if (!bufp) 4161573Srgrimes return (-1); 41714287Spst bp = (u_int16_t *)bufp->page; 4181573Srgrimes } 4191573Srgrimes 4201573Srgrimes if (PAIRFITS(bp, key, val)) 4211573Srgrimes putpair(bufp->page, key, val); 4221573Srgrimes else { 4231573Srgrimes do_expand = 1; 4241573Srgrimes bufp = __add_ovflpage(hashp, bufp); 4251573Srgrimes if (!bufp) 4261573Srgrimes return (-1); 42714287Spst sop = (u_int16_t *)bufp->page; 4281573Srgrimes 4291573Srgrimes if (PAIRFITS(sop, key, val)) 4301573Srgrimes putpair((char *)sop, key, val); 4311573Srgrimes else 4321573Srgrimes if (__big_insert(hashp, bufp, key, val)) 4331573Srgrimes return (-1); 4341573Srgrimes } 4351573Srgrimes bufp->flags |= BUF_MOD; 4361573Srgrimes /* 4371573Srgrimes * If the average number of keys per bucket exceeds the fill factor, 4381573Srgrimes * expand the table. 4391573Srgrimes */ 4401573Srgrimes hashp->NKEYS++; 4411573Srgrimes if (do_expand || 4421573Srgrimes (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) 4431573Srgrimes return (__expand_table(hashp)); 4441573Srgrimes return (0); 4451573Srgrimes} 4461573Srgrimes 4471573Srgrimes/* 4481573Srgrimes * 4491573Srgrimes * Returns: 4501573Srgrimes * pointer on success 4511573Srgrimes * NULL on error 4521573Srgrimes */ 453189291SdelphijBUFHEAD * 454189291Sdelphij__add_ovflpage(HTAB *hashp, BUFHEAD *bufp) 4551573Srgrimes{ 45692889Sobrien u_int16_t *sp; 45714287Spst u_int16_t ndx, ovfl_num; 4581573Srgrimes#ifdef DEBUG1 4591573Srgrimes int tmp1, tmp2; 4601573Srgrimes#endif 46114287Spst sp = (u_int16_t *)bufp->page; 4621573Srgrimes 4631573Srgrimes /* Check if we are dynamically determining the fill factor */ 4641573Srgrimes if (hashp->FFACTOR == DEF_FFACTOR) { 4651573Srgrimes hashp->FFACTOR = sp[0] >> 1; 4661573Srgrimes if (hashp->FFACTOR < MIN_FFACTOR) 4671573Srgrimes hashp->FFACTOR = MIN_FFACTOR; 4681573Srgrimes } 4691573Srgrimes bufp->flags |= BUF_MOD; 4701573Srgrimes ovfl_num = overflow_page(hashp); 4711573Srgrimes#ifdef DEBUG1 4721573Srgrimes tmp1 = bufp->addr; 4731573Srgrimes tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; 4741573Srgrimes#endif 4751573Srgrimes if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) 4761573Srgrimes return (NULL); 4771573Srgrimes bufp->ovfl->flags |= BUF_MOD; 4781573Srgrimes#ifdef DEBUG1 4791573Srgrimes (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", 4801573Srgrimes tmp1, tmp2, bufp->ovfl->addr); 4811573Srgrimes#endif 4821573Srgrimes ndx = sp[0]; 4831573Srgrimes /* 4841573Srgrimes * Since a pair is allocated on a page only if there's room to add 4851573Srgrimes * an overflow page, we know that the OVFL information will fit on 4861573Srgrimes * the page. 4871573Srgrimes */ 4881573Srgrimes sp[ndx + 4] = OFFSET(sp); 4891573Srgrimes sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; 4901573Srgrimes sp[ndx + 1] = ovfl_num; 4911573Srgrimes sp[ndx + 2] = OVFLPAGE; 4921573Srgrimes sp[0] = ndx + 2; 4931573Srgrimes#ifdef HASH_STATISTICS 4941573Srgrimes hash_overflows++; 4951573Srgrimes#endif 4961573Srgrimes return (bufp->ovfl); 4971573Srgrimes} 4981573Srgrimes 4991573Srgrimes/* 5001573Srgrimes * Returns: 5011573Srgrimes * 0 indicates SUCCESS 5021573Srgrimes * -1 indicates FAILURE 5031573Srgrimes */ 504189291Sdelphijint 505189291Sdelphij__get_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_disk, 506189291Sdelphij int is_bitmap) 5071573Srgrimes{ 50892889Sobrien int fd, page, size; 5091573Srgrimes int rsize; 51014287Spst u_int16_t *bp; 5111573Srgrimes 5121573Srgrimes fd = hashp->fp; 5131573Srgrimes size = hashp->BSIZE; 5141573Srgrimes 5151573Srgrimes if ((fd == -1) || !is_disk) { 5161573Srgrimes PAGE_INIT(p); 5171573Srgrimes return (0); 5181573Srgrimes } 5191573Srgrimes if (is_bucket) 5201573Srgrimes page = BUCKET_TO_PAGE(bucket); 5211573Srgrimes else 5221573Srgrimes page = OADDR_TO_PAGE(bucket); 523190486Sdelphij if ((rsize = pread(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 5241573Srgrimes return (-1); 52514287Spst bp = (u_int16_t *)p; 5261573Srgrimes if (!rsize) 5271573Srgrimes bp[0] = 0; /* We hit the EOF, so initialize a new page */ 5281573Srgrimes else 5291573Srgrimes if (rsize != size) { 5301573Srgrimes errno = EFTYPE; 5311573Srgrimes return (-1); 5321573Srgrimes } 5331573Srgrimes if (!is_bitmap && !bp[0]) { 5341573Srgrimes PAGE_INIT(p); 5351573Srgrimes } else 5361573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 53792889Sobrien int i, max; 5381573Srgrimes 5391573Srgrimes if (is_bitmap) { 5401573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5411573Srgrimes for (i = 0; i < max; i++) 54214287Spst M_32_SWAP(((int *)p)[i]); 5431573Srgrimes } else { 5441573Srgrimes M_16_SWAP(bp[0]); 5451573Srgrimes max = bp[0] + 2; 5461573Srgrimes for (i = 1; i <= max; i++) 5471573Srgrimes M_16_SWAP(bp[i]); 5481573Srgrimes } 5491573Srgrimes } 5501573Srgrimes return (0); 5511573Srgrimes} 5521573Srgrimes 5531573Srgrimes/* 5541573Srgrimes * Write page p to disk 5551573Srgrimes * 5561573Srgrimes * Returns: 5571573Srgrimes * 0 ==> OK 5581573Srgrimes * -1 ==>failure 5591573Srgrimes */ 560189291Sdelphijint 561189291Sdelphij__put_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_bitmap) 5621573Srgrimes{ 56392889Sobrien int fd, page, size; 5641573Srgrimes int wsize; 5651573Srgrimes 5661573Srgrimes size = hashp->BSIZE; 5671573Srgrimes if ((hashp->fp == -1) && open_temp(hashp)) 5681573Srgrimes return (-1); 5691573Srgrimes fd = hashp->fp; 5701573Srgrimes 5711573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 57292889Sobrien int i; 57392889Sobrien int max; 5741573Srgrimes 5751573Srgrimes if (is_bitmap) { 5761573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5771573Srgrimes for (i = 0; i < max; i++) 57814287Spst M_32_SWAP(((int *)p)[i]); 5791573Srgrimes } else { 58014287Spst max = ((u_int16_t *)p)[0] + 2; 5811573Srgrimes for (i = 0; i <= max; i++) 58214287Spst M_16_SWAP(((u_int16_t *)p)[i]); 5831573Srgrimes } 5841573Srgrimes } 5851573Srgrimes if (is_bucket) 5861573Srgrimes page = BUCKET_TO_PAGE(bucket); 5871573Srgrimes else 5881573Srgrimes page = OADDR_TO_PAGE(bucket); 589190486Sdelphij if ((wsize = pwrite(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 5901573Srgrimes /* Errno is set */ 5911573Srgrimes return (-1); 5921573Srgrimes if (wsize != size) { 5931573Srgrimes errno = EFTYPE; 5941573Srgrimes return (-1); 5951573Srgrimes } 5961573Srgrimes return (0); 5971573Srgrimes} 5981573Srgrimes 5991573Srgrimes#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) 6001573Srgrimes/* 6011573Srgrimes * Initialize a new bitmap page. Bitmap pages are left in memory 6021573Srgrimes * once they are read in. 6031573Srgrimes */ 604189291Sdelphijint 605189291Sdelphij__ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) 6061573Srgrimes{ 60714287Spst u_int32_t *ip; 6081573Srgrimes int clearbytes, clearints; 6091573Srgrimes 61014287Spst if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 6111573Srgrimes return (1); 6121573Srgrimes hashp->nmaps++; 6131573Srgrimes clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; 6141573Srgrimes clearbytes = clearints << INT_TO_BYTE; 6151573Srgrimes (void)memset((char *)ip, 0, clearbytes); 6161573Srgrimes (void)memset(((char *)ip) + clearbytes, 0xFF, 6171573Srgrimes hashp->BSIZE - clearbytes); 6181573Srgrimes ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); 6191573Srgrimes SETBIT(ip, 0); 62014287Spst hashp->BITMAPS[ndx] = (u_int16_t)pnum; 6211573Srgrimes hashp->mapp[ndx] = ip; 6221573Srgrimes return (0); 6231573Srgrimes} 6241573Srgrimes 62514287Spststatic u_int32_t 626189291Sdelphijfirst_free(u_int32_t map) 6271573Srgrimes{ 62892889Sobrien u_int32_t i, mask; 6291573Srgrimes 6301573Srgrimes mask = 0x1; 6311573Srgrimes for (i = 0; i < BITS_PER_MAP; i++) { 6321573Srgrimes if (!(mask & map)) 6331573Srgrimes return (i); 6341573Srgrimes mask = mask << 1; 6351573Srgrimes } 6361573Srgrimes return (i); 6371573Srgrimes} 6381573Srgrimes 63914287Spststatic u_int16_t 640189291Sdelphijoverflow_page(HTAB *hashp) 6411573Srgrimes{ 64292889Sobrien u_int32_t *freep; 64392889Sobrien int max_free, offset, splitnum; 64414287Spst u_int16_t addr; 6451573Srgrimes int bit, first_page, free_bit, free_page, i, in_use_bits, j; 6461573Srgrimes#ifdef DEBUG2 6471573Srgrimes int tmp1, tmp2; 6481573Srgrimes#endif 6491573Srgrimes splitnum = hashp->OVFL_POINT; 6501573Srgrimes max_free = hashp->SPARES[splitnum]; 6511573Srgrimes 6521573Srgrimes free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); 6531573Srgrimes free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); 6541573Srgrimes 6551573Srgrimes /* Look through all the free maps to find the first free block */ 6561573Srgrimes first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); 6571573Srgrimes for ( i = first_page; i <= free_page; i++ ) { 65814287Spst if (!(freep = (u_int32_t *)hashp->mapp[i]) && 6591573Srgrimes !(freep = fetch_bitmap(hashp, i))) 66014287Spst return (0); 6611573Srgrimes if (i == free_page) 6621573Srgrimes in_use_bits = free_bit; 6631573Srgrimes else 6641573Srgrimes in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; 6658870Srgrimes 6661573Srgrimes if (i == first_page) { 6671573Srgrimes bit = hashp->LAST_FREED & 6681573Srgrimes ((hashp->BSIZE << BYTE_SHIFT) - 1); 6691573Srgrimes j = bit / BITS_PER_MAP; 6701573Srgrimes bit = bit & ~(BITS_PER_MAP - 1); 6711573Srgrimes } else { 6721573Srgrimes bit = 0; 6731573Srgrimes j = 0; 6741573Srgrimes } 6751573Srgrimes for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) 6761573Srgrimes if (freep[j] != ALL_SET) 6771573Srgrimes goto found; 6781573Srgrimes } 6791573Srgrimes 6801573Srgrimes /* No Free Page Found */ 6811573Srgrimes hashp->LAST_FREED = hashp->SPARES[splitnum]; 6821573Srgrimes hashp->SPARES[splitnum]++; 6831573Srgrimes offset = hashp->SPARES[splitnum] - 6841573Srgrimes (splitnum ? hashp->SPARES[splitnum - 1] : 0); 6851573Srgrimes 6861573Srgrimes#define OVMSG "HASH: Out of overflow pages. Increase page size\n" 6871573Srgrimes if (offset > SPLITMASK) { 6881573Srgrimes if (++splitnum >= NCACHED) { 68956698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 690190487Sdelphij errno = EFBIG; 69114287Spst return (0); 6921573Srgrimes } 6931573Srgrimes hashp->OVFL_POINT = splitnum; 6941573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 6951573Srgrimes hashp->SPARES[splitnum-1]--; 6961573Srgrimes offset = 1; 6971573Srgrimes } 6981573Srgrimes 6991573Srgrimes /* Check if we need to allocate a new bitmap page */ 7001573Srgrimes if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { 7011573Srgrimes free_page++; 7021573Srgrimes if (free_page >= NCACHED) { 70356698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 704190487Sdelphij errno = EFBIG; 70514287Spst return (0); 7061573Srgrimes } 7071573Srgrimes /* 7081573Srgrimes * This is tricky. The 1 indicates that you want the new page 7091573Srgrimes * allocated with 1 clear bit. Actually, you are going to 7101573Srgrimes * allocate 2 pages from this map. The first is going to be 7111573Srgrimes * the map page, the second is the overflow page we were 7121573Srgrimes * looking for. The init_bitmap routine automatically, sets 7131573Srgrimes * the first bit of itself to indicate that the bitmap itself 7141573Srgrimes * is in use. We would explicitly set the second bit, but 7151573Srgrimes * don't have to if we tell init_bitmap not to leave it clear 7161573Srgrimes * in the first place. 7171573Srgrimes */ 71814287Spst if (__ibitmap(hashp, 71914287Spst (int)OADDR_OF(splitnum, offset), 1, free_page)) 72014287Spst return (0); 7211573Srgrimes hashp->SPARES[splitnum]++; 7221573Srgrimes#ifdef DEBUG2 7231573Srgrimes free_bit = 2; 7241573Srgrimes#endif 7251573Srgrimes offset++; 7261573Srgrimes if (offset > SPLITMASK) { 7271573Srgrimes if (++splitnum >= NCACHED) { 72856698Sjasone (void)_write(STDERR_FILENO, OVMSG, 7291573Srgrimes sizeof(OVMSG) - 1); 730190487Sdelphij errno = EFBIG; 73114287Spst return (0); 7321573Srgrimes } 7331573Srgrimes hashp->OVFL_POINT = splitnum; 7341573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7351573Srgrimes hashp->SPARES[splitnum-1]--; 7361573Srgrimes offset = 0; 7371573Srgrimes } 7381573Srgrimes } else { 7391573Srgrimes /* 7401573Srgrimes * Free_bit addresses the last used bit. Bump it to address 7411573Srgrimes * the first available bit. 7421573Srgrimes */ 7431573Srgrimes free_bit++; 7441573Srgrimes SETBIT(freep, free_bit); 7451573Srgrimes } 7461573Srgrimes 7471573Srgrimes /* Calculate address of the new overflow page */ 7481573Srgrimes addr = OADDR_OF(splitnum, offset); 7491573Srgrimes#ifdef DEBUG2 7501573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7511573Srgrimes addr, free_bit, free_page); 7521573Srgrimes#endif 7531573Srgrimes return (addr); 7541573Srgrimes 7551573Srgrimesfound: 7561573Srgrimes bit = bit + first_free(freep[j]); 7571573Srgrimes SETBIT(freep, bit); 7581573Srgrimes#ifdef DEBUG2 7591573Srgrimes tmp1 = bit; 7601573Srgrimes tmp2 = i; 7611573Srgrimes#endif 7621573Srgrimes /* 7631573Srgrimes * Bits are addressed starting with 0, but overflow pages are addressed 7641573Srgrimes * beginning at 1. Bit is a bit addressnumber, so we need to increment 7651573Srgrimes * it to convert it to a page number. 7661573Srgrimes */ 7671573Srgrimes bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); 7681573Srgrimes if (bit >= hashp->LAST_FREED) 7691573Srgrimes hashp->LAST_FREED = bit - 1; 7701573Srgrimes 7711573Srgrimes /* Calculate the split number for this page */ 7721573Srgrimes for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); 7731573Srgrimes offset = (i ? bit - hashp->SPARES[i - 1] : bit); 774190487Sdelphij if (offset >= SPLITMASK) { 775190487Sdelphij (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 776190487Sdelphij errno = EFBIG; 77714287Spst return (0); /* Out of overflow pages */ 778190487Sdelphij } 7791573Srgrimes addr = OADDR_OF(i, offset); 7801573Srgrimes#ifdef DEBUG2 7811573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7821573Srgrimes addr, tmp1, tmp2); 7831573Srgrimes#endif 7841573Srgrimes 7851573Srgrimes /* Allocate and return the overflow page */ 7861573Srgrimes return (addr); 7871573Srgrimes} 7881573Srgrimes 7891573Srgrimes/* 7901573Srgrimes * Mark this overflow page as free. 7911573Srgrimes */ 792189291Sdelphijvoid 793189291Sdelphij__free_ovflpage(HTAB *hashp, BUFHEAD *obufp) 7941573Srgrimes{ 79592889Sobrien u_int16_t addr; 79614287Spst u_int32_t *freep; 7971573Srgrimes int bit_address, free_page, free_bit; 79814287Spst u_int16_t ndx; 7991573Srgrimes 8001573Srgrimes addr = obufp->addr; 8011573Srgrimes#ifdef DEBUG1 8021573Srgrimes (void)fprintf(stderr, "Freeing %d\n", addr); 8031573Srgrimes#endif 80414287Spst ndx = (((u_int16_t)addr) >> SPLITSHIFT); 8051573Srgrimes bit_address = 8061573Srgrimes (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; 8071573Srgrimes if (bit_address < hashp->LAST_FREED) 8081573Srgrimes hashp->LAST_FREED = bit_address; 8091573Srgrimes free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); 8101573Srgrimes free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); 8111573Srgrimes 8121573Srgrimes if (!(freep = hashp->mapp[free_page])) 8131573Srgrimes freep = fetch_bitmap(hashp, free_page); 8141573Srgrimes#ifdef DEBUG 8151573Srgrimes /* 8161573Srgrimes * This had better never happen. It means we tried to read a bitmap 8171573Srgrimes * that has already had overflow pages allocated off it, and we 8181573Srgrimes * failed to read it from the file. 8191573Srgrimes */ 8201573Srgrimes if (!freep) 8211573Srgrimes assert(0); 8221573Srgrimes#endif 8231573Srgrimes CLRBIT(freep, free_bit); 8241573Srgrimes#ifdef DEBUG2 8251573Srgrimes (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", 8261573Srgrimes obufp->addr, free_bit, free_page); 8271573Srgrimes#endif 8281573Srgrimes __reclaim_buf(hashp, obufp); 8291573Srgrimes} 8301573Srgrimes 8311573Srgrimes/* 8321573Srgrimes * Returns: 8331573Srgrimes * 0 success 8341573Srgrimes * -1 failure 8351573Srgrimes */ 8361573Srgrimesstatic int 837189291Sdelphijopen_temp(HTAB *hashp) 8381573Srgrimes{ 8391573Srgrimes sigset_t set, oset; 840190485Sdelphij int len; 841190485Sdelphij char *envtmp = NULL; 842190485Sdelphij char path[MAXPATHLEN]; 8431573Srgrimes 844190485Sdelphij if (issetugid() == 0) 845190485Sdelphij envtmp = getenv("TMPDIR"); 846190485Sdelphij len = snprintf(path, 847190485Sdelphij sizeof(path), "%s/_hash.XXXXXX", envtmp ? envtmp : "/tmp"); 848190485Sdelphij if (len < 0 || len >= sizeof(path)) { 849190485Sdelphij errno = ENAMETOOLONG; 850190485Sdelphij return (-1); 851190485Sdelphij } 852190485Sdelphij 8531573Srgrimes /* Block signals; make sure file goes away at process exit. */ 8541573Srgrimes (void)sigfillset(&set); 85571579Sdeischen (void)_sigprocmask(SIG_BLOCK, &set, &oset); 856190485Sdelphij if ((hashp->fp = mkstemp(path)) != -1) { 857190485Sdelphij (void)unlink(path); 85856698Sjasone (void)_fcntl(hashp->fp, F_SETFD, 1); 8591573Srgrimes } 86071579Sdeischen (void)_sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); 8611573Srgrimes return (hashp->fp != -1 ? 0 : -1); 8621573Srgrimes} 8631573Srgrimes 8641573Srgrimes/* 8651573Srgrimes * We have to know that the key will fit, but the last entry on the page is 8661573Srgrimes * an overflow pair, so we need to shift things. 8671573Srgrimes */ 8681573Srgrimesstatic void 869189291Sdelphijsqueeze_key(u_int16_t *sp, const DBT *key, const DBT *val) 8701573Srgrimes{ 87192889Sobrien char *p; 87214287Spst u_int16_t free_space, n, off, pageno; 8731573Srgrimes 8741573Srgrimes p = (char *)sp; 8751573Srgrimes n = sp[0]; 8761573Srgrimes free_space = FREESPACE(sp); 8771573Srgrimes off = OFFSET(sp); 8781573Srgrimes 8791573Srgrimes pageno = sp[n - 1]; 8801573Srgrimes off -= key->size; 8811573Srgrimes sp[n - 1] = off; 8821573Srgrimes memmove(p + off, key->data, key->size); 8831573Srgrimes off -= val->size; 8841573Srgrimes sp[n] = off; 8851573Srgrimes memmove(p + off, val->data, val->size); 8861573Srgrimes sp[0] = n + 2; 8871573Srgrimes sp[n + 1] = pageno; 8881573Srgrimes sp[n + 2] = OVFLPAGE; 8891573Srgrimes FREESPACE(sp) = free_space - PAIRSIZE(key, val); 8901573Srgrimes OFFSET(sp) = off; 8911573Srgrimes} 8921573Srgrimes 89314287Spststatic u_int32_t * 894189291Sdelphijfetch_bitmap(HTAB *hashp, int ndx) 8951573Srgrimes{ 8961573Srgrimes if (ndx >= hashp->nmaps) 8971573Srgrimes return (NULL); 89814287Spst if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 8991573Srgrimes return (NULL); 9001573Srgrimes if (__get_page(hashp, 9011573Srgrimes (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { 9021573Srgrimes free(hashp->mapp[ndx]); 9031573Srgrimes return (NULL); 9041573Srgrimes } 9051573Srgrimes return (hashp->mapp[ndx]); 9061573Srgrimes} 9071573Srgrimes 9081573Srgrimes#ifdef DEBUG4 9091573Srgrimesint 910189291Sdelphijprint_chain(int addr) 9111573Srgrimes{ 9121573Srgrimes BUFHEAD *bufp; 9131573Srgrimes short *bp, oaddr; 9141573Srgrimes 9151573Srgrimes (void)fprintf(stderr, "%d ", addr); 9161573Srgrimes bufp = __get_buf(hashp, addr, NULL, 0); 9171573Srgrimes bp = (short *)bufp->page; 9181573Srgrimes while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || 9191573Srgrimes ((bp[0] > 2) && bp[2] < REAL_KEY))) { 9201573Srgrimes oaddr = bp[bp[0] - 1]; 9211573Srgrimes (void)fprintf(stderr, "%d ", (int)oaddr); 9221573Srgrimes bufp = __get_buf(hashp, (int)oaddr, bufp, 0); 9231573Srgrimes bp = (short *)bufp->page; 9241573Srgrimes } 9251573Srgrimes (void)fprintf(stderr, "\n"); 9261573Srgrimes} 9271573Srgrimes#endif 928