bump the hash version to 2; (allocate overflow pages beyond EOF)

SCCS-vsn: lib/libc/db/hash/hash.c 5.17
SCCS-vsn: lib/libc/db/hash/hash.h 5.6
SCCS-vsn: lib/libc/db/hash/hash_page.c 5.16

diff --git a/usr/src/lib/libc/db/hash/hash.c b/usr/src/lib/libc/db/hash/hash.c
index 248d379..bdaf435 100644 (file)
--- a/usr/src/lib/libc/db/hash/hash.c
+++ b/usr/src/lib/libc/db/hash/hash.c
@@ -9,7 +9,7 @@
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)

-static char sccsid[] = "@(#)hash.c     5.16 (Berkeley) %G%";
+static char sccsid[] = "@(#)hash.c     5.17 (Berkeley) %G%";

 #endif /* LIBC_SCCS and not lint */
 
 #include <sys/param.h>
 #endif /* LIBC_SCCS and not lint */
 
 #include <sys/param.h>


@@ -123,7 +123,7 @@ hash_open(file, flags, mode, info)
                /* Verify file type, versions and hash function */
                if (hashp->MAGIC != HASHMAGIC)
                        RETURN_ERROR(EFTYPE, error1);
                /* Verify file type, versions and hash function */
                if (hashp->MAGIC != HASHMAGIC)
                        RETURN_ERROR(EFTYPE, error1);

-               if (hashp->VERSION != VERSION_NO)
+               if (hashp->VERSION != HASHVERSION)

                        RETURN_ERROR(EFTYPE, error1);
                if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)
                        RETURN_ERROR(EFTYPE, error1);
                        RETURN_ERROR(EFTYPE, error1);
                if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)
                        RETURN_ERROR(EFTYPE, error1);


@@ -142,7 +142,7 @@ hash_open(file, flags, mode, info)
                         */
                        return (NULL);
                /* Read in bitmaps */
                         */
                        return (NULL);
                /* Read in bitmaps */

-               bpages = (hashp->SPARES[__log2(hashp->MAX_BUCKET)] +
+               bpages = (hashp->SPARES[hashp->OVFL_POINT] +

                    (hashp->BSIZE << BYTE_SHIFT) - 1) >>
                    (hashp->BSHIFT + BYTE_SHIFT);
 
                    (hashp->BSIZE << BYTE_SHIFT) - 1) >>
                    (hashp->BSHIFT + BYTE_SHIFT);
 


@@ -176,7 +176,7 @@ hash_open(file, flags, mode, info)
 
 #ifdef DEBUG
        (void)fprintf(stderr,
 
 #ifdef DEBUG
        (void)fprintf(stderr,

-"%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
+"%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",

            "init_htab:",
            "TABLE POINTER   ", hashp,
            "BUCKET SIZE     ", hashp->BSIZE,
            "init_htab:",
            "TABLE POINTER   ", hashp,
            "BUCKET SIZE     ", hashp->BSIZE,


@@ -186,6 +186,8 @@ hash_open(file, flags, mode, info)
            "SEGMENT SHIFT   ", hashp->SSHIFT,
            "FILL FACTOR     ", hashp->FFACTOR,
            "MAX BUCKET      ", hashp->MAX_BUCKET,
            "SEGMENT SHIFT   ", hashp->SSHIFT,
            "FILL FACTOR     ", hashp->FFACTOR,
            "MAX BUCKET      ", hashp->MAX_BUCKET,

+           "OVFL POINT      ", hashp->OVFL_POINT,
+           "LAST FREED      ", hashp->LAST_FREED,

            "HIGH MASK       ", hashp->HIGH_MASK,
            "LOW  MASK       ", hashp->LOW_MASK,
            "NSEGS           ", hashp->nsegs,
            "HIGH MASK       ", hashp->HIGH_MASK,
            "LOW  MASK       ", hashp->LOW_MASK,
            "NSEGS           ", hashp->nsegs,


@@ -227,6 +229,7 @@ init_hash(info)
        int nelem;
 
        nelem = 1;
        int nelem;
 
        nelem = 1;

+       hashp->NKEYS = 0;

        hashp->LORDER = BYTE_ORDER;
        hashp->BSIZE = DEF_BUCKET_SIZE;
        hashp->BSHIFT = DEF_BUCKET_SHIFT;
        hashp->LORDER = BYTE_ORDER;
        hashp->BSIZE = DEF_BUCKET_SIZE;
        hashp->BSHIFT = DEF_BUCKET_SHIFT;


@@ -236,6 +239,7 @@ init_hash(info)
        hashp->FFACTOR = DEF_FFACTOR;
        hashp->hash = default_hash;
        bzero(hashp->SPARES, sizeof(hashp->SPARES));
        hashp->FFACTOR = DEF_FFACTOR;
        hashp->hash = default_hash;
        bzero(hashp->SPARES, sizeof(hashp->SPARES));

+       bzero (hashp->BITMAPS, sizeof (hashp->BITMAPS));

 
        if (info) {
                if (info->bsize) {
 
        if (info) {
                if (info->bsize) {


@@ -294,6 +298,9 @@ init_htab(nelem)
 
        hashp->SPARES[l2] = l2 + 1;
        hashp->SPARES[l2 + 1] = l2 + 1;
 
        hashp->SPARES[l2] = l2 + 1;
        hashp->SPARES[l2 + 1] = l2 + 1;

+       hashp->OVFL_POINT = l2;
+       hashp->LAST_FREED = 2;
+

        /* First bitmap page is at: splitpoint l2 page offset 1 */
        if (__init_bitmap(OADDR_OF(l2, 1), l2 + 1, 0))
                return (-1);
        /* First bitmap page is at: splitpoint l2 page offset 1 */
        if (__init_bitmap(OADDR_OF(l2, 1), l2 + 1, 0))
                return (-1);


@@ -407,7 +414,7 @@ flush_meta()
        if (!hashp->save_file)
                return (0);
        hashp->MAGIC = HASHMAGIC;
        if (!hashp->save_file)
                return (0);
        hashp->MAGIC = HASHMAGIC;

-       hashp->VERSION = VERSION_NO;
+       hashp->VERSION = HASHVERSION;

        hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
 
        fp = hashp->fp;
        hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
 
        fp = hashp->fp;


@@ -745,8 +752,11 @@ __expand_table()
         * split bucket to the next bucket.
         */
        spare_ndx = __log2(hashp->MAX_BUCKET);
         * split bucket to the next bucket.
         */
        spare_ndx = __log2(hashp->MAX_BUCKET);

-       if (spare_ndx != (__log2(hashp->MAX_BUCKET - 1)))
-               hashp->SPARES[spare_ndx] = hashp->SPARES[spare_ndx - 1];
+       if ( spare_ndx > hashp->OVFL_POINT ) {
+               hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
+               hashp->OVFL_POINT = spare_ndx;
+       }
+

        if (new_bucket > hashp->HIGH_MASK) {
                /* Starting a new doubling */
                hashp->LOW_MASK = hashp->HIGH_MASK;
        if (new_bucket > hashp->HIGH_MASK) {
                /* Starting a new doubling */
                hashp->LOW_MASK = hashp->HIGH_MASK;


@@ -841,6 +851,8 @@ swap_header_copy(srcp, destp)
        BLSWAP_COPY(srcp->dsize, destp->dsize);
        BLSWAP_COPY(srcp->ssize, destp->ssize);
        BLSWAP_COPY(srcp->sshift, destp->sshift);
        BLSWAP_COPY(srcp->dsize, destp->dsize);
        BLSWAP_COPY(srcp->ssize, destp->ssize);
        BLSWAP_COPY(srcp->sshift, destp->sshift);

+       BLSWAP_COPY(srcp->ovfl_point, destp->ovfl_point);
+       BLSWAP_COPY(srcp->last_freed, destp->last_freed);

        BLSWAP_COPY(srcp->max_bucket, destp->max_bucket);
        BLSWAP_COPY(srcp->high_mask, destp->high_mask);
        BLSWAP_COPY(srcp->low_mask, destp->low_mask);
        BLSWAP_COPY(srcp->max_bucket, destp->max_bucket);
        BLSWAP_COPY(srcp->high_mask, destp->high_mask);
        BLSWAP_COPY(srcp->low_mask, destp->low_mask);


@@ -870,6 +882,8 @@ swap_header()
        BLSWAP(hdrp->dsize);
        BLSWAP(hdrp->ssize);
        BLSWAP(hdrp->sshift);
        BLSWAP(hdrp->dsize);
        BLSWAP(hdrp->ssize);
        BLSWAP(hdrp->sshift);

+       BLSWAP(hdrp->ovfl_point);
+       BLSWAP(hdrp->last_freed);

        BLSWAP(hdrp->max_bucket);
        BLSWAP(hdrp->high_mask);
        BLSWAP(hdrp->low_mask);
        BLSWAP(hdrp->max_bucket);
        BLSWAP(hdrp->high_mask);
        BLSWAP(hdrp->low_mask);

diff --git a/usr/src/lib/libc/db/hash/hash.h b/usr/src/lib/libc/db/hash/hash.h
index cbcb460..1e69842 100644 (file)
--- a/usr/src/lib/libc/db/hash/hash.h
+++ b/usr/src/lib/libc/db/hash/hash.h
@@ -7,7 +7,7 @@
  *
  * %sccs.include.redist.c%
  *
  *
  * %sccs.include.redist.c%
  *

- *     @(#)hash.h      5.5 (Berkeley) %G%
+ *     @(#)hash.h      5.6 (Berkeley) %G%

  */
 
 /* Operations */
  */
 
 /* Operations */


@@ -45,6 +45,8 @@ typedef struct hashhdr {      /* Disk resident portion */
        int     dsize;          /* Directory Size */
        int     ssize;          /* Segment Size */
        int     sshift;         /* Segment shift */
        int     dsize;          /* Directory Size */
        int     ssize;          /* Segment Size */
        int     sshift;         /* Segment shift */

+       int     ovfl_point;     /* Where overflow pages are being allocated */
+       int     last_freed;     /* Last overflow page freed */

        int     max_bucket;     /* ID of Maximum bucket in use */
        int     high_mask;      /* Mask to modulo into entire table */
        int     low_mask;       /* Mask to modulo into lower half of table */
        int     max_bucket;     /* ID of Maximum bucket in use */
        int     high_mask;      /* Mask to modulo into entire table */
        int     low_mask;       /* Mask to modulo into lower half of table */


@@ -96,7 +98,6 @@ typedef struct htab {         /* Memory resident data structure */
 #define SPLTMAX                        8
 #define CHARKEY                        "%$sniglet^&"
 #define NUMKEY                 1038583
 #define SPLTMAX                        8
 #define CHARKEY                        "%$sniglet^&"
 #define NUMKEY                 1038583

-#define VERSION_NO             3

 #define BYTE_SHIFT             3
 #define INT_TO_BYTE            2
 #define INT_BYTE_SHIFT         5
 #define BYTE_SHIFT             3
 #define INT_TO_BYTE            2
 #define INT_BYTE_SHIFT         5


@@ -239,6 +240,8 @@ typedef struct htab {               /* Memory resident data structure */
 #define SGSIZE         hdr.ssize
 #define SSHIFT         hdr.sshift
 #define LORDER         hdr.lorder
 #define SGSIZE         hdr.ssize
 #define SSHIFT         hdr.sshift
 #define LORDER         hdr.lorder

+#define OVFL_POINT     hdr.ovfl_point
+#define        LAST_FREED      hdr.last_freed

 #define MAX_BUCKET     hdr.max_bucket
 #define FFACTOR                hdr.ffactor
 #define HIGH_MASK      hdr.high_mask
 #define MAX_BUCKET     hdr.max_bucket
 #define FFACTOR                hdr.ffactor
 #define HIGH_MASK      hdr.high_mask

diff --git a/usr/src/lib/libc/db/hash/hash_page.c b/usr/src/lib/libc/db/hash/hash_page.c
index 31abcdc..dda09ca 100644 (file)
--- a/usr/src/lib/libc/db/hash/hash_page.c
+++ b/usr/src/lib/libc/db/hash/hash_page.c
@@ -9,7 +9,7 @@
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)

-static char sccsid[] = "@(#)hash_page.c        5.15 (Berkeley) %G%";
+static char sccsid[] = "@(#)hash_page.c        5.16 (Berkeley) %G%";

 #endif /* LIBC_SCCS and not lint */
 
 /*
 #endif /* LIBC_SCCS and not lint */
 
 /*


@@ -618,18 +618,19 @@ overflow_page()
        register u_long *freep;
        register int max_free, offset, splitnum;
        u_short addr;
        register u_long *freep;
        register int max_free, offset, splitnum;
        u_short addr;

-       int bit, free_bit, free_page, i, in_use_bits, j;
+       int bit, first_page, free_bit, free_page, i, in_use_bits, j;

 #ifdef DEBUG2
        int tmp1, tmp2;
 #endif
 #ifdef DEBUG2
        int tmp1, tmp2;
 #endif

-       splitnum = __log2(hashp->MAX_BUCKET);
+       splitnum = hashp->OVFL_POINT;

        max_free = hashp->SPARES[splitnum];
 
        free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
        free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
 
        /* Look through all the free maps to find the first free block */
        max_free = hashp->SPARES[splitnum];
 
        free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
        free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
 
        /* Look through all the free maps to find the first free block */

-       for (i = 0; i <= free_page; i++) {
+       first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
+       for ( i = first_page; i <= free_page; i++ ) {

                if (!(freep = (u_long *)hashp->mapp[i]) &&
                    !(freep = fetch_bitmap(i)))
                        return (NULL);
                if (!(freep = (u_long *)hashp->mapp[i]) &&
                    !(freep = fetch_bitmap(i)))
                        return (NULL);


@@ -637,22 +638,42 @@ overflow_page()
                        in_use_bits = free_bit;
                else
                        in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
                        in_use_bits = free_bit;
                else
                        in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;

-
-               for (j = 0, bit = 0; bit <= in_use_bits;
-                   j++, bit += BITS_PER_MAP)
+               
+               if (i == first_page) {
+                       bit = hashp->LAST_FREED &
+                           ((hashp->BSIZE << BYTE_SHIFT) - 1);
+                       j = bit / BITS_PER_MAP;
+                       bit = bit & ~(BITS_PER_MAP - 1);
+               } else {
+                       bit = 0;
+                       j = 0;
+               }
+               for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)

                        if (freep[j] != ALL_SET)
                                goto found;
        }
 
        /* No Free Page Found */
                        if (freep[j] != ALL_SET)
                                goto found;
        }
 
        /* No Free Page Found */

+       hashp->LAST_FREED = hashp->SPARES[splitnum];

        hashp->SPARES[splitnum]++;
        offset = hashp->SPARES[splitnum] -
            (splitnum ? hashp->SPARES[splitnum - 1] : 0);
 
        hashp->SPARES[splitnum]++;
        offset = hashp->SPARES[splitnum] -
            (splitnum ? hashp->SPARES[splitnum - 1] : 0);
 

+#define        OVMSG   "HASH: Out of overflow pages.  Increase page size\n"
+       if (offset > SPLITMASK) {
+               if (++splitnum >= NCACHED) {
+                       (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
+                       return (NULL);
+               }
+               hashp->OVFL_POINT = splitnum;
+               hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
+               hashp->SPARES[splitnum-1]--;
+               offset = 0;
+       }
+

        /* Check if we need to allocate a new bitmap page */
        if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
                free_page++;
        /* Check if we need to allocate a new bitmap page */
        if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
                free_page++;

-#define        OVMSG   "hash: out of overflow pages; increase page size\n"

                if (free_page >= NCACHED) {
                        (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
                        return (NULL);
                if (free_page >= NCACHED) {
                        (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
                        return (NULL);


@@ -676,6 +697,17 @@ overflow_page()
                free_bit = 2;
 #endif
                offset++;
                free_bit = 2;
 #endif
                offset++;

+               if (offset > SPLITMASK) {
+                       if (++splitnum >= NCACHED) {
+                               (void)write(STDERR_FILENO, OVMSG,
+                                   sizeof(OVMSG) - 1);
+                               return (NULL);
+                       }
+                       hashp->OVFL_POINT = splitnum;
+                       hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
+                       hashp->SPARES[splitnum-1]--;
+                       offset = 0;
+               }

        } else {
                /*
                 * Free_bit addresses the last used bit.  Bump it to address
        } else {
                /*
                 * Free_bit addresses the last used bit.  Bump it to address


@@ -686,10 +718,6 @@ overflow_page()
        }
 
        /* Calculate address of the new overflow page */
        }
 
        /* Calculate address of the new overflow page */

-       if (offset > SPLITMASK) {
-               (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
-               return (NULL);
-       }

        addr = OADDR_OF(splitnum, offset);
 #ifdef DEBUG2
        (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
        addr = OADDR_OF(splitnum, offset);
 #ifdef DEBUG2
        (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",


@@ -710,6 +738,8 @@ found:
         * it to convert it to a page number.
         */
        bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
         * it to convert it to a page number.
         */
        bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));

+       if (bit >= hashp->LAST_FREED)
+               hashp->LAST_FREED = bit - 1;

 
        /* Calculate the split number for this page */
        for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
 
        /* Calculate the split number for this page */
        for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);


@@ -745,6 +775,8 @@ __free_ovflpage(obufp)
        ndx = (((u_short)addr) >> SPLITSHIFT);
        bit_address =
            (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
        ndx = (((u_short)addr) >> SPLITSHIFT);
        bit_address =
            (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;

+        if (bit_address < hashp->LAST_FREED)
+               hashp->LAST_FREED = bit_address;

        free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
        free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
 
        free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
        free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);