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