SEO

Greetings,

Two diffs for libc/db/hash/hash.c. I noticed a problem where
creating a hash database, populating it with some key/data pairs
and then removing each entry sequentially would cause a core
dump.

The test program uses db->seq() (hash_seq) to iterate through the
entries and calling db->del() to remove entry. The problem seems
to be how hash_seq increments hashp->cndx before returning,
essentially anticipating a subsequent call with flag == R_NEXT.
The test program gets in a condition where hashp->cndx ends up
pointing past the last key/data pair due to the fact it is
deleting entries as it interates through the keys. hashp->cndx
ends up being > bp[0]. Since hash_seq() doesn't have any
sanity checks in place for hashp->cndx value it returns bogus
values for key and data, hence the crash.

The change I made is to increment hashp->cndx at the beginning of
the call to hash_seq(), if flag == R_NEXT, rather than prepare it
for a subsequent call before returning.

Also, hashp->cndx is decremented (adjusted) during deletion of
the key/data pair if hashp->cndx is pointing to the entry being
deleted. The side-effect of not doing this is entries are
skipped due to the way __delpair "shuffles" keys.


The diffs are based on OPENBSD_4_2. I believe the head of cvs
has the same version of hash.c file.

The first diff has nothing to do with the above problem. It is
a sequence point evaluation fix. There may be more of these in
the code, but I've not dug around for them (yet). It also adds
curly braces for a long-ish for() loop.

The second diff, which is based on the first diff, fixes the bug
described above.

After applying these patches, I was able to run 'make regress'
successfully.



--- /usr/src/lib/libc/db/hash/hash.c Tue Aug 1 03:11:31 2006
+++ hash/hash.c Sat Apr 5 23:10:46 2008
@@ -582,7 +582,9 @@ hash_access(HTAB *hashp, ACTION action, DBT *key, DBT

/* Pin the bucket chain */
rbufp->flags |= BUF_PIN;
- for (bp = (u_int16_t *)rbufp->page, n = *bp++, ndx = 1; ndx < n
+ bp = (u_int16_t *)rbufp->page;
+ n = *bp++;
+ for (ndx = 1; ndx < n {
if (bp[1] >= REAL_KEY) {
/* Real key/data pair */
if (size == off - *bp &&
@@ -632,6 +634,7 @@ hash_access(HTAB *hashp, ACTION action, DBT *key, DBT
return (ERROR);
}
}
+ }

/* Not found */
switch (action) {



--- /usr/src/lib/libc/db/hash/hash.c Tue Aug 1 03:11:31 2006
+++ hash/hash.c Sun Apr 6 00:27:30 2008
@@ -676,6 +679,14 @@ found:
case HASH_DELETE:
if (__delpair(hashp, rbufp, ndx))
return (ERROR);
+ if (ndx == hashp->cndx) {
+ /*
+ * We just removed pair we were "pointing" to.
+ * By moving back the cndx we ensure subsequent
+ * hash_seq() calls won't skip over any entries.
+ */
+ hashp->cndx -= 2;
+ }
break;
default:
abort();
@@ -705,7 +716,7 @@ hash_seq(const DB *dbp, DBT *key, DBT *data, u_int32_t
hashp->cndx = 1;
hashp->cpage = NULL;
}
-
+ next_bucket:
for (bp = NULL; !bp || !bp[0]; ) {
if (!(bufp = hashp->cpage)) {
for (bucket = hashp->cbucket;
@@ -724,8 +735,18 @@ hash_seq(const DB *dbp, DBT *key, DBT *data, u_int32_t
hashp->cbucket = -1;
return (ABNORMAL);
}
- } else
+ } else {
bp = (u_int16_t *)hashp->cpage->page;
+ if (flag == R_NEXT) {
+ hashp->cndx += 2;
+ if (hashp->cndx > bp[0]) {
+ hashp->cpage = NULL;
+ hashp->cbucket++;
+ hashp->cndx = 1;
+ goto next_bucket;
+ }
+ }
+ }

#ifdef DEBUG
assert(bp);
@@ -755,13 +776,6 @@ hash_seq(const DB *dbp, DBT *key, DBT *data, u_int32_t
key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
data->size = bp[ndx] - bp[ndx + 1];
- ndx += 2;
- if (ndx > bp[0]) {
- hashp->cpage = NULL;
- hashp->cbucket++;
- hashp->cndx = 1;
- } else
- hashp->cndx = ndx;
}
return (SUCCESS);
}



Below is the test code that causes the crash. It assumes you
have /usr/src/lib/libc/db/hash/hash.h checked out as it relies
on the definition of HTAB for debug printf()s.

I've run a slightly modified version on Linux (Red Hat Enterprise
Linux ES release 3 and Slackware 10.2.0 -- only two available to
me) and the test program runs as expected; no crashes there, key
and data pairs stored, retrieved and purged successfully.

The program puts 10 entries in the hash database. Dumps the
stored data to stdout, walking through the db using hash_seq().
Next it attempts to purge the stored data walking through the
db entries using hash_seq(). Finally attempts to dump the data,
again, to stdout, the db should have no records at this point.


$ cat hashtest.c
#include <sys/types.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <db.h>
/* Required for the DBGXX macro below */
#include "/usr/src/lib/libc/db/hash/hash.h"

extern char const *__progname;

#define DBFILE "hashtest.db"


void
dump_db(DB *db)
{
char pkey[128], pval[128];
int i, r;
DBT dbk, dbv;
printf("Retrieving stored data...\n");
i = 0;
r = db->seq(db, &dbk, &dbv, R_FIRST);
while (0 == r) {
int n;
bzero(pkey, sizeof(pkey));
bzero(pval, sizeof(pval));
n = dbk.size > sizeof(pkey) ? (sizeof(pkey)-1) : dbk.size;
memcpy(pkey, dbk.data, n);
n = dbv.size > sizeof(pval) ? (sizeof(pval)-1) : dbv.size;
memcpy(pval, dbv.data, n);
printf("#%d> key:%s -> value:%s\n", ++i, pkey, pval);
r = db->seq(db, &dbk, &dbv, R_NEXT);
}
}

#define DBGXX(db) do { \
HTAB *h = (HTAB*)(db)->internal; \
printf("DBG:%s:%d> hashp:%p cndx:%d cpage:%p\n", \
__func__, __LINE__, h, h ? h->cndx : -1, \
h ? h->cpage : NULL); \
} while (0)

int main(int argc, char *argv[])
{
char pkey[128], pval[128];
int i, r;
DB *db;
DBT dbk, dbv;
HASHINFO hashinfo;

bzero(&hashinfo, sizeof(hashinfo));
db = dbopen(DBFILE, (O_CREAT|O_RDWR|O_EXLOCK), 0644, DB_HASH,
&hashinfo);
if (db == NULL)
err(errno, "failed to open %s", DBFILE);
bzero(&dbk, sizeof(dbk));
bzero(&dbv, sizeof(dbv));
printf("Storing data...\n");
for (i = 0; i < 10; ++i) {
snprintf(pkey, sizeof(pkey), "Key #%d", (i+1));
snprintf(pval, sizeof(pval), "Value for key #%d", (i+1));
dbk.data = pkey;
dbk.size = strlen(pkey);
dbv.data = pval;
dbv.size = strlen(pval);
if (0 != db->put(db, &dbk, &dbv, 0)) {
warn("failed to entr %s -> %s", pkey, pval);
goto done;
}
}
dump_db(db);
//goto done;
i = 0;
printf("Purging stored data ...\n");
DBGXX(db);
r = db->seq(db, &dbk, &dbv, R_FIRST);
while (0 == r) {
int n;
bzero(pkey, sizeof(pkey));
bzero(pval, sizeof(pval));
n = dbk.size > sizeof(pkey) ? (sizeof(pkey)-1) : dbk.size;
memcpy(pkey, dbk.data, n);
n = dbv.size > sizeof(pval) ? (sizeof(pval)-1) : dbv.size;
memcpy(pval, dbv.data, n);
printf("#%2d> key:%s -> value:%s\n", ++i, pkey, pval);
DBGXX(db);
if (0 != db->del(db, &dbk, 0))
warn("failed to delete entry");
r = db->seq(db, &dbk, &dbv, R_NEXT);
DBGXX(db);
}
dump_db(db);
done:
db->close(db);
return 0;
}