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