Lines Matching +full:page +full:- +full:offset
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
39 * Page manipulation for hashing package.
64 #include "un-namespace.h"
69 #include "page.h"
82 ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \
83 ((u_int16_t *)(P))[2] = hashp->BSIZE; \
87 * This is called AFTER we have verified that there is room on the page for
101 off = OFFSET(bp) - key->size; in putpair()
102 memmove(p + off, key->data, key->size); in putpair()
106 off -= val->size; in putpair()
107 memmove(p + off, val->data, val->size); in putpair()
110 /* Adjust page info. */ in putpair()
112 bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); in putpair()
119 * -1 error
127 bp = (u_int16_t *)bufp->page; in __delpair()
133 newoff = bp[ndx - 1]; in __delpair()
135 newoff = hashp->BSIZE; in __delpair()
136 pairlen = newoff - bp[ndx + 1]; in __delpair()
138 if (ndx != (n - 1)) { in __delpair()
139 /* Hard Case -- need to shuffle keys */ in __delpair()
141 char *src = bufp->page + (int)OFFSET(bp); in __delpair()
143 memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); in __delpair()
148 bp[i - 2] = bp[i]; in __delpair()
149 bp[i - 1] = bp[i + 1]; in __delpair()
151 bp[i - 2] = bp[i] + pairlen; in __delpair()
152 bp[i - 1] = bp[i + 1] + pairlen; in __delpair()
155 if (ndx == hashp->cndx) { in __delpair()
161 hashp->cndx -= 2; in __delpair()
164 /* Finally adjust the page data */ in __delpair()
165 bp[n] = OFFSET(bp) + pairlen; in __delpair()
166 bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); in __delpair()
167 bp[0] = n - 2; in __delpair()
168 hashp->NKEYS--; in __delpair()
170 bufp->flags |= BUF_MOD; in __delpair()
176 * -1 ==> Error
189 copyto = (u_int16_t)hashp->BSIZE; in __split_page()
190 off = (u_int16_t)hashp->BSIZE; in __split_page()
193 return (-1); in __split_page()
196 return (-1); in __split_page()
198 old_bufp->flags |= (BUF_MOD | BUF_PIN); in __split_page()
199 new_bufp->flags |= (BUF_MOD | BUF_PIN); in __split_page()
201 ino = (u_int16_t *)(op = old_bufp->page); in __split_page()
202 np = new_bufp->page; in __split_page()
210 old_bufp->flags &= ~BUF_PIN; in __split_page()
211 new_bufp->flags &= ~BUF_PIN; in __split_page()
216 key.size = off - ino[n]; in __split_page()
219 /* Don't switch page */ in __split_page()
220 diff = copyto - off; in __split_page()
224 off - ino[n + 1]); in __split_page()
225 ino[ndx] = copyto + ino[n] - ino[n + 1]; in __split_page()
231 /* Switch page */ in __split_page()
233 val.size = ino[n] - ino[n + 1]; in __split_page()
241 /* Now clean up the page */ in __split_page()
242 ino[0] -= moved; in __split_page()
243 FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3); in __split_page()
244 OFFSET(ino) = copyto; in __split_page()
252 old_bufp->flags &= ~BUF_PIN; in __split_page()
253 new_bufp->flags &= ~BUF_PIN; in __split_page()
258 * Called when we encounter an overflow or big key/data page during split
263 * The first page might be a page with regular key/data pairs in which case
265 * page or it might be a big key/data pair in which case we need to fix the
270 * -1 ==> failure
277 int copyto, /* First byte on page which contains key/data values. */ in ugly_split()
278 int moved) /* Number of pairs moved to new page. */ in ugly_split()
281 u_int16_t *ino; /* Page keys come off of */ in ugly_split()
282 u_int16_t *np; /* New page */ in ugly_split()
283 u_int16_t *op; /* Page keys go on to if they aren't moving */ in ugly_split()
292 ino = (u_int16_t *)old_bufp->page; in ugly_split()
293 np = (u_int16_t *)new_bufp->page; in ugly_split()
294 op = (u_int16_t *)old_bufp->page; in ugly_split()
298 n = ino[0] - 1; in ugly_split()
302 new_bufp, bufp, bufp->addr, obucket, &ret)) in ugly_split()
303 return (-1); in ugly_split()
306 return (-1); in ugly_split()
307 op = (u_int16_t *)old_bufp->page; in ugly_split()
310 return (-1); in ugly_split()
311 np = (u_int16_t *)new_bufp->page; in ugly_split()
315 cino = (char *)bufp->page; in ugly_split()
321 * Fix up the old page -- the extra 2 are the fields in ugly_split()
324 ino[0] -= (moved + 2); in ugly_split()
326 scopyto - sizeof(u_int16_t) * (ino[0] + 3); in ugly_split()
327 OFFSET(ino) = scopyto; in ugly_split()
331 return (-1); in ugly_split()
333 ino = (u_int16_t *)bufp->page; in ugly_split()
335 scopyto = hashp->BSIZE; in ugly_split()
343 off = hashp->BSIZE; in ugly_split()
347 key.size = off - ino[n]; in ugly_split()
349 val.size = ino[n] - ino[n + 1]; in ugly_split()
353 /* Keep on old page */ in ugly_split()
360 return (-1); in ugly_split()
361 op = (u_int16_t *)old_bufp->page; in ugly_split()
364 old_bufp->flags |= BUF_MOD; in ugly_split()
366 /* Move to new page */ in ugly_split()
373 return (-1); in ugly_split()
374 np = (u_int16_t *)new_bufp->page; in ugly_split()
377 new_bufp->flags |= BUF_MOD; in ugly_split()
387 * Add the given pair to the page
399 bp = (u_int16_t *)bufp->page; in __addel()
404 /* This is the last page of a big key/data pair in __addel()
405 and we need to add another page */ in __addel()
408 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); in __addel()
410 return (-1); in __addel()
411 bp = (u_int16_t *)bufp->page; in __addel()
416 /* Try to squeeze key on this page */ in __addel()
422 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); in __addel()
424 return (-1); in __addel()
425 bp = (u_int16_t *)bufp->page; in __addel()
430 putpair(bufp->page, key, val); in __addel()
435 return (-1); in __addel()
436 sop = (u_int16_t *)bufp->page; in __addel()
442 return (-1); in __addel()
445 bufp->flags |= BUF_MOD; in __addel()
450 hashp->NKEYS++; in __addel()
452 (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) in __addel()
470 sp = (u_int16_t *)bufp->page; in __add_ovflpage()
473 if (hashp->FFACTOR == DEF_FFACTOR) { in __add_ovflpage()
474 hashp->FFACTOR = sp[0] >> 1; in __add_ovflpage()
475 if (hashp->FFACTOR < MIN_FFACTOR) in __add_ovflpage()
476 hashp->FFACTOR = MIN_FFACTOR; in __add_ovflpage()
478 bufp->flags |= BUF_MOD; in __add_ovflpage()
481 tmp1 = bufp->addr; in __add_ovflpage()
482 tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; in __add_ovflpage()
484 if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) in __add_ovflpage()
486 bufp->ovfl->flags |= BUF_MOD; in __add_ovflpage()
488 (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", in __add_ovflpage()
489 tmp1, tmp2, bufp->ovfl->addr); in __add_ovflpage()
493 * Since a pair is allocated on a page only if there's room to add in __add_ovflpage()
494 * an overflow page, we know that the OVFL information will fit on in __add_ovflpage()
495 * the page. in __add_ovflpage()
497 sp[ndx + 4] = OFFSET(sp); in __add_ovflpage()
498 sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; in __add_ovflpage()
505 return (bufp->ovfl); in __add_ovflpage()
511 * -1 indicates FAILURE
517 int fd, page, size, rsize; in __get_page() local
520 fd = hashp->fp; in __get_page()
521 size = hashp->BSIZE; in __get_page()
523 if ((fd == -1) || !is_disk) { in __get_page()
528 page = BUCKET_TO_PAGE(bucket); in __get_page()
530 page = OADDR_TO_PAGE(bucket); in __get_page()
531 if ((rsize = pread(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) in __get_page()
532 return (-1); in __get_page()
535 bp[0] = 0; /* We hit the EOF, so initialize a new page */ in __get_page()
539 return (-1); in __get_page()
544 if (hashp->LORDER != BYTE_ORDER) { in __get_page()
548 max = hashp->BSIZE >> 2; /* divide by 4 */ in __get_page()
562 * Write page p to disk
566 * -1 ==>failure
571 int fd, page, size; in __put_page() local
575 size = hashp->BSIZE; in __put_page()
576 if ((hashp->fp == -1) && open_temp(hashp)) in __put_page()
577 return (-1); in __put_page()
578 fd = hashp->fp; in __put_page()
580 if (hashp->LORDER != BYTE_ORDER) { in __put_page()
585 max = hashp->BSIZE >> 2; /* divide by 4 */ in __put_page()
597 page = BUCKET_TO_PAGE(bucket); in __put_page()
599 page = OADDR_TO_PAGE(bucket); in __put_page()
600 if ((wsize = pwrite(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) in __put_page()
602 return (-1); in __put_page()
605 return (-1); in __put_page()
610 #define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1)
612 * Initialize a new bitmap page. Bitmap pages are left in memory
621 if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) in __ibitmap()
623 hashp->nmaps++; in __ibitmap()
624 clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; in __ibitmap()
628 hashp->BSIZE - clearbytes); in __ibitmap()
629 ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); in __ibitmap()
631 hashp->BITMAPS[ndx] = (u_int16_t)pnum; in __ibitmap()
632 hashp->mapp[ndx] = ip; in __ibitmap()
654 int max_free, offset, splitnum; in overflow_page() local
660 splitnum = hashp->OVFL_POINT; in overflow_page()
661 max_free = hashp->SPARES[splitnum]; in overflow_page()
663 free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); in overflow_page()
664 free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); in overflow_page()
667 first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); in overflow_page()
669 if (!(freep = (u_int32_t *)hashp->mapp[i]) && in overflow_page()
675 in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; in overflow_page()
678 bit = hashp->LAST_FREED & in overflow_page()
679 ((hashp->BSIZE << BYTE_SHIFT) - 1); in overflow_page()
691 /* No Free Page Found */ in overflow_page()
692 hashp->LAST_FREED = hashp->SPARES[splitnum]; in overflow_page()
693 hashp->SPARES[splitnum]++; in overflow_page()
694 offset = hashp->SPARES[splitnum] - in overflow_page()
695 (splitnum ? hashp->SPARES[splitnum - 1] : 0); in overflow_page()
697 #define OVMSG "HASH: Out of overflow pages. Increase page size\n" in overflow_page()
698 if (offset > SPLITMASK) { in overflow_page()
700 (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); in overflow_page()
704 hashp->OVFL_POINT = splitnum; in overflow_page()
705 hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; in overflow_page()
706 hashp->SPARES[splitnum-1]--; in overflow_page()
707 offset = 1; in overflow_page()
710 /* Check if we need to allocate a new bitmap page */ in overflow_page()
711 if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { in overflow_page()
714 (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); in overflow_page()
719 * This is tricky. The 1 indicates that you want the new page in overflow_page()
722 * the map page, the second is the overflow page we were in overflow_page()
730 (int)OADDR_OF(splitnum, offset), 1, free_page)) in overflow_page()
732 hashp->SPARES[splitnum]++; in overflow_page()
736 offset++; in overflow_page()
737 if (offset > SPLITMASK) { in overflow_page()
740 sizeof(OVMSG) - 1); in overflow_page()
744 hashp->OVFL_POINT = splitnum; in overflow_page()
745 hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; in overflow_page()
746 hashp->SPARES[splitnum-1]--; in overflow_page()
747 offset = 0; in overflow_page()
758 /* Calculate address of the new overflow page */ in overflow_page()
759 addr = OADDR_OF(splitnum, offset); in overflow_page()
761 (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", in overflow_page()
776 * it to convert it to a page number. in overflow_page()
778 bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); in overflow_page()
779 if (bit >= hashp->LAST_FREED) in overflow_page()
780 hashp->LAST_FREED = bit - 1; in overflow_page()
782 /* Calculate the split number for this page */ in overflow_page()
783 for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); in overflow_page()
784 offset = (i ? bit - hashp->SPARES[i - 1] : bit); in overflow_page()
785 if (offset >= SPLITMASK) { in overflow_page()
786 (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); in overflow_page()
790 addr = OADDR_OF(i, offset); in overflow_page()
792 (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", in overflow_page()
796 /* Allocate and return the overflow page */ in overflow_page()
801 * Mark this overflow page as free.
811 addr = obufp->addr; in __free_ovflpage()
817 (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; in __free_ovflpage()
818 if (bit_address < hashp->LAST_FREED) in __free_ovflpage()
819 hashp->LAST_FREED = bit_address; in __free_ovflpage()
820 free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); in __free_ovflpage()
821 free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); in __free_ovflpage()
823 if (!(freep = hashp->mapp[free_page])) in __free_ovflpage()
836 (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", in __free_ovflpage()
837 obufp->addr, free_bit, free_page); in __free_ovflpage()
845 * -1 failure
860 return (-1); in open_temp()
866 if ((hashp->fp = mkostemp(path, O_CLOEXEC)) != -1) in open_temp()
869 return (hashp->fp != -1 ? 0 : -1); in open_temp()
873 * We have to know that the key will fit, but the last entry on the page is
885 off = OFFSET(sp); in squeeze_key()
887 pageno = sp[n - 1]; in squeeze_key()
888 off -= key->size; in squeeze_key()
889 sp[n - 1] = off; in squeeze_key()
890 memmove(p + off, key->data, key->size); in squeeze_key()
891 off -= val->size; in squeeze_key()
893 memmove(p + off, val->data, val->size); in squeeze_key()
897 FREESPACE(sp) = free_space - PAIRSIZE(key, val); in squeeze_key()
898 OFFSET(sp) = off; in squeeze_key()
904 if (ndx >= hashp->nmaps) in fetch_bitmap()
906 if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) in fetch_bitmap()
909 (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { in fetch_bitmap()
910 free(hashp->mapp[ndx]); in fetch_bitmap()
913 return (hashp->mapp[ndx]); in fetch_bitmap()
925 bp = (short *)bufp->page; in print_chain()
928 oaddr = bp[bp[0] - 1]; in print_chain()
931 bp = (short *)bufp->page; in print_chain()