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