Module Name: src
Committed By: bouyer
Date: Sun Nov 22 14:15:14 UTC 2015
Modified Files:
src/lib/libc/db/hash [netbsd-7]: hash.c hash.h hash_bigkey.c
hash_page.c
Log Message:
Pull up following revision(s) (requested by christos in ticket #1046):
lib/libc/db/hash/hash_page.c: revision 1.27
lib/libc/db/hash/hash_page.c: revision 1.28
lib/libc/db/hash/hash.h: revision 1.16
lib/libc/db/hash/hash.c: revision 1.36
lib/libc/db/hash/hash.c: revision 1.37
lib/libc/db/hash/hash.c: revision 1.38
lib/libc/db/hash/hash_bigkey.c: revision 1.25
Account for the -1 hack to fit 0x10000 in a short in hash_page.c
Introduce a HASH_BSIZE macro to return the blocksize; in the 64K case this
returns 0xffff to avoid overflow. This is used where sizes are stored.
If MAX_BSIZE == hashp->BSIZE (65536) then it does not fit in a short, and
we end up storing 0... This means that every entry needs a page. We store
MAX_BSIZE - 1 here, but it would be better to always store (avail - 1) here
so that we don't waste a byte and be consistent.
PR/50441: Manuel Bouyer: hash seq enumeration skips keys on big data.
XXX: pullup-7
To generate a diff of this commit:
cvs rdiff -u -r1.33.4.1 -r1.33.4.2 src/lib/libc/db/hash/hash.c
cvs rdiff -u -r1.15 -r1.15.40.1 src/lib/libc/db/hash/hash.h
cvs rdiff -u -r1.24 -r1.24.10.1 src/lib/libc/db/hash/hash_bigkey.c
cvs rdiff -u -r1.26 -r1.26.4.1 src/lib/libc/db/hash/hash_page.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/lib/libc/db/hash/hash.c
diff -u src/lib/libc/db/hash/hash.c:1.33.4.1 src/lib/libc/db/hash/hash.c:1.33.4.2
--- src/lib/libc/db/hash/hash.c:1.33.4.1 Thu Aug 6 21:50:36 2015
+++ src/lib/libc/db/hash/hash.c Sun Nov 22 14:15:14 2015
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.c,v 1.33.4.1 2015/08/06 21:50:36 snj Exp $ */
+/* $NetBSD: hash.c,v 1.33.4.2 2015/11/22 14:15:14 bouyer Exp $ */
/*-
* Copyright (c) 1990, 1993, 1994
@@ -37,7 +37,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: hash.c,v 1.33.4.1 2015/08/06 21:50:36 snj Exp $");
+__RCSID("$NetBSD: hash.c,v 1.33.4.2 2015/11/22 14:15:14 bouyer Exp $");
#include "namespace.h"
#include <sys/param.h>
@@ -585,7 +585,7 @@ hash_access(HTAB *hashp, ACTION action,
hash_accesses++;
#endif
- off = hashp->BSIZE;
+ off = HASH_BSIZE(hashp);
size = key->size;
kp = (char *)key->data;
rbufp = __get_buf(hashp, __call_hash(hashp, kp, (int)size), NULL, 0);
@@ -617,7 +617,7 @@ hash_access(HTAB *hashp, ACTION action,
bp = (uint16_t *)(void *)rbufp->page;
n = *bp++;
ndx = 1;
- off = hashp->BSIZE;
+ off = HASH_BSIZE(hashp);
} else if (bp[1] < REAL_KEY) {
if ((ndx =
__find_bigpair(hashp, rbufp, ndx, kp, (int)size)) > 0)
@@ -640,7 +640,7 @@ hash_access(HTAB *hashp, ACTION action,
bp = (uint16_t *)(void *)rbufp->page;
n = *bp++;
ndx = 1;
- off = hashp->BSIZE;
+ off = HASH_BSIZE(hashp);
} else {
save_bufp->flags &= ~BUF_PIN;
return (ERROR);
@@ -770,7 +770,7 @@ next_bucket:
hashp->cndx = 1;
}
} else {
- bp = (uint16_t *)(void *)hashp->cpage->page;
+ bp = (uint16_t *)(void *)bufp->page;
if (flag == R_NEXT || flag == 0) {
if (hashp->cndx > bp[0]) {
hashp->cpage = NULL;
@@ -802,15 +802,16 @@ next_bucket:
if (bp[ndx + 1] < REAL_KEY) {
if (__big_keydata(hashp, bufp, key, data, 1))
return (ERROR);
+ hashp->cndx = 1;
} else {
if (hashp->cpage == NULL)
return (ERROR);
key->data = (uint8_t *)hashp->cpage->page + bp[ndx];
- key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
+ key->size = (ndx > 1 ? bp[ndx - 1] : HASH_BSIZE(hashp)) - bp[ndx];
data->data = (uint8_t *)hashp->cpage->page + bp[ndx + 1];
data->size = bp[ndx] - bp[ndx + 1];
+ hashp->cndx += 2;
}
- hashp->cndx += 2;
return (SUCCESS);
}
Index: src/lib/libc/db/hash/hash.h
diff -u src/lib/libc/db/hash/hash.h:1.15 src/lib/libc/db/hash/hash.h:1.15.40.1
--- src/lib/libc/db/hash/hash.h:1.15 Tue Aug 26 21:18:38 2008
+++ src/lib/libc/db/hash/hash.h Sun Nov 22 14:15:14 2015
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.h,v 1.15 2008/08/26 21:18:38 joerg Exp $ */
+/* $NetBSD: hash.h,v 1.15.40.1 2015/11/22 14:15:14 bouyer Exp $ */
/*-
* Copyright (c) 1990, 1993, 1994
@@ -123,6 +123,11 @@ typedef struct htab { /* Memory reside
* Constants
*/
#define MAX_BSIZE 65536 /* 2^16 */
+/*
+ * Make it fit in uint16_t; a better way would be to store size - 1, but
+ * then we'd need to bump the version.
+ */
+#define HASH_BSIZE(hp) ((hp)->BSIZE == MAX_BSIZE ? MAX_BSIZE - 1 : (hp)->BSIZE)
#define MIN_BUFFERS 6
#define MINHDRSIZE 512
#define DEF_BUFSIZE 65536 /* 64 K */
Index: src/lib/libc/db/hash/hash_bigkey.c
diff -u src/lib/libc/db/hash/hash_bigkey.c:1.24 src/lib/libc/db/hash/hash_bigkey.c:1.24.10.1
--- src/lib/libc/db/hash/hash_bigkey.c:1.24 Tue Mar 13 21:13:32 2012
+++ src/lib/libc/db/hash/hash_bigkey.c Sun Nov 22 14:15:14 2015
@@ -1,4 +1,4 @@
-/* $NetBSD: hash_bigkey.c,v 1.24 2012/03/13 21:13:32 christos Exp $ */
+/* $NetBSD: hash_bigkey.c,v 1.24.10.1 2015/11/22 14:15:14 bouyer Exp $ */
/*-
* Copyright (c) 1990, 1993, 1994
@@ -37,7 +37,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: hash_bigkey.c,v 1.24 2012/03/13 21:13:32 christos Exp $");
+__RCSID("$NetBSD: hash_bigkey.c,v 1.24.10.1 2015/11/22 14:15:14 bouyer Exp $");
/*
* PACKAGE: hash
@@ -274,10 +274,10 @@ __big_delete(HTAB *hashp, BUFHEAD *bufp)
bufp->ovfl = NULL;
n -= 2;
bp[0] = n;
- temp = hashp->BSIZE - PAGE_META(n);
+ temp = HASH_BSIZE(hashp) - PAGE_META(n);
_DBFIT(temp, uint16_t);
FREESPACE(bp) = (uint16_t)temp;
- OFFSET(bp) = hashp->BSIZE;
+ OFFSET(bp) = HASH_BSIZE(hashp);
bufp->flags |= BUF_MOD;
if (rbufp)
@@ -309,9 +309,9 @@ __find_bigpair(HTAB *hashp, BUFHEAD *buf
ksize = size;
kkey = key;
- for (bytes = hashp->BSIZE - bp[ndx];
+ for (bytes = HASH_BSIZE(hashp) - bp[ndx];
bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
- bytes = hashp->BSIZE - bp[ndx]) {
+ bytes = HASH_BSIZE(hashp) - bp[ndx]) {
if (memcmp(p + bp[ndx], kkey, (size_t)bytes))
return (-2);
kkey += bytes;
@@ -479,7 +479,7 @@ collect_data(HTAB *hashp, BUFHEAD *bufp,
p = bufp->page;
bp = (uint16_t *)(void *)p;
- mylen = hashp->BSIZE - bp[1];
+ mylen = HASH_BSIZE(hashp) - bp[1];
save_addr = bufp->addr;
if (bp[2] == FULL_KEY_DATA) { /* End of Data */
@@ -546,7 +546,7 @@ collect_key(HTAB *hashp, BUFHEAD *bufp,
p = bufp->page;
bp = (uint16_t *)(void *)p;
- mylen = hashp->BSIZE - bp[1];
+ mylen = HASH_BSIZE(hashp) - bp[1];
save_addr = bufp->addr;
totlen = len + mylen;
Index: src/lib/libc/db/hash/hash_page.c
diff -u src/lib/libc/db/hash/hash_page.c:1.26 src/lib/libc/db/hash/hash_page.c:1.26.4.1
--- src/lib/libc/db/hash/hash_page.c:1.26 Sun Dec 1 00:22:48 2013
+++ src/lib/libc/db/hash/hash_page.c Sun Nov 22 14:15:14 2015
@@ -1,4 +1,4 @@
-/* $NetBSD: hash_page.c,v 1.26 2013/12/01 00:22:48 christos Exp $ */
+/* $NetBSD: hash_page.c,v 1.26.4.1 2015/11/22 14:15:14 bouyer Exp $ */
/*-
* Copyright (c) 1990, 1993, 1994
@@ -37,7 +37,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: hash_page.c,v 1.26 2013/12/01 00:22:48 christos Exp $");
+__RCSID("$NetBSD: hash_page.c,v 1.26.4.1 2015/11/22 14:15:14 bouyer Exp $");
/*
* PACKAGE: hashing
@@ -83,9 +83,9 @@ static int ugly_split(HTAB *, uint32_t,
#define PAGE_INIT(P) { \
((uint16_t *)(void *)(P))[0] = 0; \
temp = 3 * sizeof(uint16_t); \
- _DIAGASSERT((size_t)hashp->BSIZE >= temp); \
- ((uint16_t *)(void *)(P))[1] = (uint16_t)(hashp->BSIZE - temp); \
- ((uint16_t *)(void *)(P))[2] = hashp->BSIZE; \
+ _DIAGASSERT((size_t)HASH_BSIZE(hashp) >= temp); \
+ ((uint16_t *)(void *)(P))[1] = (uint16_t)(HASH_BSIZE(hashp) - temp); \
+ ((uint16_t *)(void *)(P))[2] = HASH_BSIZE(hashp); \
}
/*
@@ -145,7 +145,7 @@ __delpair(HTAB *hashp, BUFHEAD *bufp, in
if (ndx != 1)
newoff = bp[ndx - 1];
else
- newoff = hashp->BSIZE;
+ newoff = HASH_BSIZE(hashp);
pairlen = newoff - bp[ndx + 1];
if (ndx != (n - 1)) {
@@ -194,8 +194,8 @@ __split_page(HTAB *hashp, uint32_t obuck
char *op;
size_t temp;
- copyto = (uint16_t)hashp->BSIZE;
- off = (uint16_t)hashp->BSIZE;
+ copyto = HASH_BSIZE(hashp);
+ off = HASH_BSIZE(hashp);
old_bufp = __get_buf(hashp, obucket, NULL, 0);
if (old_bufp == NULL)
return (-1);
@@ -346,7 +346,7 @@ ugly_split(
ino = (uint16_t *)(void *)bufp->page;
n = 1;
- scopyto = hashp->BSIZE;
+ scopyto = HASH_BSIZE(hashp);
moved = 0;
if (last_bfp)
@@ -354,7 +354,7 @@ ugly_split(
last_bfp = bufp;
}
/* Move regular sized pairs of there are any */
- off = hashp->BSIZE;
+ off = HASH_BSIZE(hashp);
for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
cino = (char *)(void *)ino;
key.data = (uint8_t *)cino + ino[n];
@@ -541,7 +541,7 @@ __get_page(HTAB *hashp, char *p, uint32_
size_t temp;
fd = hashp->fp;
- size = hashp->BSIZE;
+ size = HASH_BSIZE(hashp);
if ((fd == -1) || !is_disk) {
PAGE_INIT(p);
@@ -594,7 +594,7 @@ __put_page(HTAB *hashp, char *p, uint32_
int fd, page, size;
ssize_t wsize;
- size = hashp->BSIZE;
+ size = HASH_BSIZE(hashp);
if ((hashp->fp == -1) && (hashp->fp = __dbtemp("_hash", NULL)) == -1)
return (-1);
fd = hashp->fp;
