Module Name: src
Committed By: joerg
Date: Wed Dec 11 01:24:08 UTC 2013
Modified Files:
src/distrib/sets/lists/comp: mi
src/include: Makefile
src/lib/libc/cdb: Makefile.inc
src/sys/lib/libkern: Makefile.libkern libkern.h
src/sys/sys: Makefile
src/tools/compat: Makefile cdbr.h
Added Files:
src/common/lib/libc/cdb: cdbr.c
src/common/lib/libc/stdlib: mi_vector_hash.c
src/sys/sys: cdbr.h
Removed Files:
src/include: cdbr.h
src/lib/libc/stdlib: mi_vector_hash.c
Log Message:
Allow kernel code to access constant databases by moving cdbr(3) and the
required mi_vector_hash(3) into src/common.
To generate a diff of this commit:
cvs rdiff -u -r0 -r1.1 src/common/lib/libc/cdb/cdbr.c
cvs rdiff -u -r0 -r1.1 src/common/lib/libc/stdlib/mi_vector_hash.c
cvs rdiff -u -r1.1869 -r1.1870 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.139 -r1.140 src/include/Makefile
cvs rdiff -u -r1.2 -r0 src/include/cdbr.h
cvs rdiff -u -r1.2 -r1.3 src/lib/libc/cdb/Makefile.inc
cvs rdiff -u -r1.4 -r0 src/lib/libc/stdlib/mi_vector_hash.c
cvs rdiff -u -r1.27 -r1.28 src/sys/lib/libkern/Makefile.libkern
cvs rdiff -u -r1.109 -r1.110 src/sys/lib/libkern/libkern.h
cvs rdiff -u -r1.144 -r1.145 src/sys/sys/Makefile
cvs rdiff -u -r0 -r1.1 src/sys/sys/cdbr.h
cvs rdiff -u -r1.69 -r1.70 src/tools/compat/Makefile
cvs rdiff -u -r1.1 -r1.2 src/tools/compat/cdbr.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/distrib/sets/lists/comp/mi
diff -u src/distrib/sets/lists/comp/mi:1.1869 src/distrib/sets/lists/comp/mi:1.1870
--- src/distrib/sets/lists/comp/mi:1.1869 Tue Dec 10 01:09:31 2013
+++ src/distrib/sets/lists/comp/mi Wed Dec 11 01:24:08 2013
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1869 2013/12/10 01:09:31 riz Exp $
+# $NetBSD: mi,v 1.1870 2013/12/11 01:24:08 joerg Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -3118,6 +3118,7 @@
./usr/include/sys/callback.h comp-c-include
./usr/include/sys/callout.h comp-c-include
./usr/include/sys/cc_microtime.h comp-obsolete obsolete
+./usr/include/sys/cdbr.h comp-c-include
./usr/include/sys/cdefs.h comp-c-include
./usr/include/sys/cdefs_aout.h comp-c-include
./usr/include/sys/cdefs_elf.h comp-c-include
Index: src/include/Makefile
diff -u src/include/Makefile:1.139 src/include/Makefile:1.140
--- src/include/Makefile:1.139 Sat Feb 11 23:31:24 2012
+++ src/include/Makefile Wed Dec 11 01:24:08 2013
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.139 2012/02/11 23:31:24 martin Exp $
+# $NetBSD: Makefile,v 1.140 2013/12/11 01:24:08 joerg Exp $
# @(#)Makefile 8.2 (Berkeley) 1/4/94
# Doing a make includes builds /usr/include
@@ -8,7 +8,7 @@ NOOBJ= # defined
# Missing: mp.h
INCS= a.out.h aio.h ar.h assert.h atomic.h \
- bitstring.h bm.h cdbr.h cdbw.h complex.h cpio.h ctype.h \
+ bitstring.h bm.h cdbw.h complex.h cpio.h ctype.h \
db.h dirent.h disktab.h dlfcn.h err.h errno.h fenv.h fmtmsg.h fnmatch.h \
fstab.h fts.h ftw.h getopt.h glob.h grp.h ifaddrs.h iconv.h \
inttypes.h iso646.h kvm.h langinfo.h libgen.h \
Index: src/lib/libc/cdb/Makefile.inc
diff -u src/lib/libc/cdb/Makefile.inc:1.2 src/lib/libc/cdb/Makefile.inc:1.3
--- src/lib/libc/cdb/Makefile.inc:1.2 Sat Mar 17 17:59:58 2012
+++ src/lib/libc/cdb/Makefile.inc Wed Dec 11 01:24:08 2013
@@ -1,8 +1,9 @@
-# $NetBSD: Makefile.inc,v 1.2 2012/03/17 17:59:58 christos Exp $
+# $NetBSD: Makefile.inc,v 1.3 2013/12/11 01:24:08 joerg Exp $
# Constant database reader/writer
.PATH: ${.CURDIR}/cdb
+.PATH: ${NETBSDSRCDIR}/common/lib/libc/cdb
SRCS+= cdbr.c cdbw.c
Index: src/sys/lib/libkern/Makefile.libkern
diff -u src/sys/lib/libkern/Makefile.libkern:1.27 src/sys/lib/libkern/Makefile.libkern:1.28
--- src/sys/lib/libkern/Makefile.libkern:1.27 Mon Dec 2 04:39:10 2013
+++ src/sys/lib/libkern/Makefile.libkern Wed Dec 11 01:24:08 2013
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.libkern,v 1.27 2013/12/02 04:39:10 lneto Exp $
+# $NetBSD: Makefile.libkern,v 1.28 2013/12/11 01:24:08 joerg Exp $
#
# Variable definitions for libkern.
@@ -98,6 +98,10 @@ SRCS+= heapsort.c ptree.c rb.c
# for crypto
SRCS+= explicit_memset.c consttime_memequal.c
+.PATH: ${NETBSDSRCDIR}/common/lib/libc/cdb
+SRCS+= cdbr.c
+SRCS+= mi_vector_hash.c
+
# Files to clean up
CLEANFILES+= lib${LIB}.o lib${LIB}.po
Index: src/sys/lib/libkern/libkern.h
diff -u src/sys/lib/libkern/libkern.h:1.109 src/sys/lib/libkern/libkern.h:1.110
--- src/sys/lib/libkern/libkern.h:1.109 Mon Dec 2 04:39:10 2013
+++ src/sys/lib/libkern/libkern.h Wed Dec 11 01:24:08 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: libkern.h,v 1.109 2013/12/02 04:39:10 lneto Exp $ */
+/* $NetBSD: libkern.h,v 1.110 2013/12/11 01:24:08 joerg Exp $ */
/*-
* Copyright (c) 1992, 1993
@@ -321,6 +321,8 @@ char *initstate(unsigned long, char *, s
char *setstate(char *);
#endif /* SMALL_RANDOM */
long random(void);
+void mi_vector_hash(const void * __restrict, size_t, uint32_t,
+ uint32_t[3]);
void mtprng_init32(struct mtprng_state *, uint32_t);
void mtprng_initarray(struct mtprng_state *, const uint32_t *, size_t);
uint32_t mtprng_rawrandom(struct mtprng_state *);
Index: src/sys/sys/Makefile
diff -u src/sys/sys/Makefile:1.144 src/sys/sys/Makefile:1.145
--- src/sys/sys/Makefile:1.144 Sun Oct 27 08:35:40 2013
+++ src/sys/sys/Makefile Wed Dec 11 01:24:08 2013
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.144 2013/10/27 08:35:40 mbalmer Exp $
+# $NetBSD: Makefile,v 1.145 2013/12/11 01:24:08 joerg Exp $
.include <bsd.sys.mk>
@@ -6,7 +6,7 @@ INCSDIR= /usr/include/sys
INCS= acct.h agpio.h aio.h ansi.h aout_mids.h ataio.h atomic.h audioio.h \
bitops.h bootblock.h bswap.h buf.h \
- callback.h callout.h cdefs.h cdefs_aout.h \
+ callback.h callout.h cdbr.h cdefs.h cdefs_aout.h \
cdefs_elf.h cdio.h chio.h clockctl.h condvar.h conf.h core.h \
cpufreq.h cpuio.h ctype_bits.h ctype_inline.h \
device.h device_if.h \
@@ -43,6 +43,7 @@ INCS= acct.h agpio.h aio.h ansi.h aout_m
wait.h wapbl.h wapbl_replay.h wdog.h xattr.h
INCSYMLINKS=\
+ sys/cdbr.h /usr/include/cdbr.h \
sys/exec_elf.h /usr/include/elf.h \
sys/fcntl.h /usr/include/fcntl.h \
sys/poll.h /usr/include/poll.h \
Index: src/tools/compat/Makefile
diff -u src/tools/compat/Makefile:1.69 src/tools/compat/Makefile:1.70
--- src/tools/compat/Makefile:1.69 Tue Aug 6 22:04:25 2013
+++ src/tools/compat/Makefile Wed Dec 11 01:24:08 2013
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.69 2013/08/06 22:04:25 apb Exp $
+# $NetBSD: Makefile,v 1.70 2013/12/11 01:24:08 joerg Exp $
HOSTLIB= nbcompat
@@ -48,6 +48,7 @@ CPPFLAGS+= -I. -I./include -I${.CURDIR}
${.CURDIR}/../../lib/libc/stdlib \
${.CURDIR}/../../lib/libc/string \
${.CURDIR}/../../lib/libutil \
+ ${.CURDIR}/../../common/lib/libc/cdb \
${.CURDIR}/../../common/lib/libc/string \
${.CURDIR}/../../common/lib/libc/hash/rmd160 \
${.CURDIR}/../../common/lib/libc/hash/sha1 \
Index: src/tools/compat/cdbr.h
diff -u src/tools/compat/cdbr.h:1.1 src/tools/compat/cdbr.h:1.2
--- src/tools/compat/cdbr.h:1.1 Mon Jun 4 19:06:45 2012
+++ src/tools/compat/cdbr.h Wed Dec 11 01:24:08 2013
@@ -1,5 +1,5 @@
-/* $NetBSD: cdbr.h,v 1.1 2012/06/04 19:06:45 joerg Exp $ */
+/* $NetBSD: cdbr.h,v 1.2 2013/12/11 01:24:08 joerg Exp $ */
/* We unconditionally use the NetBSD cdbr(3) in libnbcompat. */
#include "nbtool_config.h"
-#include "../../include/cdbr.h"
+#include "../../sys/sys/cdbr.h"
Added files:
Index: src/common/lib/libc/cdb/cdbr.c
diff -u /dev/null src/common/lib/libc/cdb/cdbr.c:1.1
--- /dev/null Wed Dec 11 01:24:09 2013
+++ src/common/lib/libc/cdb/cdbr.c Wed Dec 11 01:24:08 2013
@@ -0,0 +1,313 @@
+/* $NetBSD: cdbr.c,v 1.1 2013/12/11 01:24:08 joerg Exp $ */
+/*-
+ * Copyright (c) 2010 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Joerg Sonnenberger.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: cdbr.c,v 1.1 2013/12/11 01:24:08 joerg Exp $");
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+#include "namespace.h"
+#endif
+
+#if !HAVE_NBTOOL_CONFIG_H
+#include <sys/bitops.h>
+#endif
+#if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
+#include <sys/endian.h>
+#endif
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+#include <sys/cdbr.h>
+#include <sys/kmem.h>
+#include <sys/systm.h>
+#include <lib/libkern/libkern.h>
+#define SET_ERRNO(val)
+#define malloc(size) kmem_alloc(size, KM_SLEEP)
+#define free(ptr) kmem_free(ptr, sizeof(struct cdbr))
+#else
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <cdbr.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <inttypes.h>
+#include <limits.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#define SET_ERRNO(val) errno = (val)
+#endif
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+#ifdef __weak_alias
+__weak_alias(cdbr_close,_cdbr_close)
+__weak_alias(cdbr_find,_cdbr_find)
+__weak_alias(cdbr_get,_cdbr_get)
+__weak_alias(cdbr_open,_cdbr_open)
+__weak_alias(cdbr_open_mem,_cdbr_open_mem)
+#endif
+#endif
+
+#if HAVE_NBTOOL_CONFIG_H
+#define fast_divide32_prepare(d,m,s1,s2) (void)0
+#define fast_remainder32(v,d,m,s1,s2) (v%d)
+#endif
+
+struct cdbr {
+ void (*unmap)(void *, void *, size_t);
+ void *cookie;
+ uint8_t *mmap_base;
+ size_t mmap_size;
+
+ uint8_t *hash_base;
+ uint8_t *offset_base;
+ uint8_t *data_base;
+
+ uint32_t data_size;
+ uint32_t entries;
+ uint32_t entries_index;
+ uint32_t seed;
+
+ uint8_t offset_size;
+ uint8_t index_size;
+
+ uint32_t entries_m;
+ uint32_t entries_index_m;
+ uint8_t entries_s1, entries_s2;
+ uint8_t entries_index_s1, entries_index_s2;
+};
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+static void
+cdbr_unmap(void *cookie __unused, void *base, size_t size)
+{
+ munmap(base, size);
+}
+
+/* ARGSUSED */
+struct cdbr *
+cdbr_open(const char *path, int flags)
+{
+ void *base;
+ size_t size;
+ int fd;
+ struct cdbr *cdbr;
+ struct stat sb;
+
+ if ((fd = open(path, O_RDONLY)) == -1)
+ return NULL;
+ if (fstat(fd, &sb) == -1) {
+ close(fd);
+ return NULL;
+ }
+
+ if (sb.st_size >= SSIZE_MAX) {
+ close(fd);
+ SET_ERRNO(EINVAL);
+ return NULL;
+ }
+
+
+ size = (size_t)sb.st_size;
+ base = mmap(NULL, size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0);
+ close(fd);
+
+ if (base == MAP_FAILED)
+ return NULL;
+
+ cdbr = cdbr_open_mem(base, size, flags, cdbr_unmap, NULL);
+ if (cdbr == NULL)
+ munmap(base, size);
+ return cdbr;
+}
+#endif
+
+struct cdbr *
+cdbr_open_mem(void *base, size_t size, int flags,
+ void (*unmap)(void *, void *, size_t), void *cookie)
+{
+ struct cdbr *cdbr;
+ uint8_t *buf = base;
+ if (size < 40 || memcmp(buf, "NBCDB\n\0\001", 8)) {
+ SET_ERRNO(EINVAL);
+ return NULL;
+ }
+
+ cdbr = malloc(sizeof(*cdbr));
+ cdbr->unmap = unmap;
+ cdbr->cookie = cookie;
+
+ cdbr->data_size = le32dec(buf + 24);
+ cdbr->entries = le32dec(buf + 28);
+ cdbr->entries_index = le32dec(buf + 32);
+ cdbr->seed = le32dec(buf + 36);
+
+ if (cdbr->data_size < 0x100)
+ cdbr->offset_size = 1;
+ else if (cdbr->data_size < 0x10000)
+ cdbr->offset_size = 2;
+ else
+ cdbr->offset_size = 4;
+
+ if (cdbr->entries_index < 0x100)
+ cdbr->index_size = 1;
+ else if (cdbr->entries_index < 0x10000)
+ cdbr->index_size = 2;
+ else
+ cdbr->index_size = 4;
+
+ cdbr->mmap_base = base;
+ cdbr->mmap_size = size;
+
+ cdbr->hash_base = cdbr->mmap_base + 40;
+ cdbr->offset_base = cdbr->hash_base + cdbr->entries_index * cdbr->index_size;
+ if (cdbr->entries_index * cdbr->index_size % cdbr->offset_size)
+ cdbr->offset_base += cdbr->offset_size -
+ cdbr->entries_index * cdbr->index_size % cdbr->offset_size;
+ cdbr->data_base = cdbr->offset_base + (cdbr->entries + 1) * cdbr->offset_size;
+
+ if (cdbr->hash_base < cdbr->mmap_base ||
+ cdbr->offset_base < cdbr->mmap_base ||
+ cdbr->data_base < cdbr->mmap_base ||
+ cdbr->data_base + cdbr->data_size < cdbr->mmap_base ||
+ cdbr->data_base + cdbr->data_size >
+ cdbr->mmap_base + cdbr->mmap_size) {
+ SET_ERRNO(EINVAL);
+ free(cdbr);
+ return NULL;
+ }
+
+ if (cdbr->entries) {
+ fast_divide32_prepare(cdbr->entries, &cdbr->entries_m,
+ &cdbr->entries_s1, &cdbr->entries_s2);
+ }
+ if (cdbr->entries_index) {
+ fast_divide32_prepare(cdbr->entries_index,
+ &cdbr->entries_index_m,
+ &cdbr->entries_index_s1, &cdbr->entries_index_s2);
+ }
+
+ return cdbr;
+}
+
+static inline uint32_t
+get_uintX(const uint8_t *addr, uint32_t idx, int size)
+{
+ addr += idx * size;
+
+ if (size == 4)
+ return /* LINTED */le32toh(*(const uint32_t *)addr);
+ else if (size == 2)
+ return /* LINTED */le16toh(*(const uint16_t *)addr);
+ else
+ return *addr;
+}
+
+uint32_t
+cdbr_entries(struct cdbr *cdbr)
+{
+
+ return cdbr->entries;
+}
+
+int
+cdbr_get(struct cdbr *cdbr, uint32_t idx, const void **data, size_t *data_len)
+{
+ uint32_t start, end;
+
+ if (idx >= cdbr->entries) {
+ SET_ERRNO(EINVAL);
+ return -1;
+ }
+
+ start = get_uintX(cdbr->offset_base, idx, cdbr->offset_size);
+ end = get_uintX(cdbr->offset_base, idx + 1, cdbr->offset_size);
+
+ if (start > end) {
+ SET_ERRNO(EIO);
+ return -1;
+ }
+
+ if (end > cdbr->data_size) {
+ SET_ERRNO(EIO);
+ return -1;
+ }
+
+ *data = cdbr->data_base + start;
+ *data_len = end - start;
+
+ return 0;
+}
+
+int
+cdbr_find(struct cdbr *cdbr, const void *key, size_t key_len,
+ const void **data, size_t *data_len)
+{
+ uint32_t hashes[3], idx;
+
+ if (cdbr->entries_index == 0) {
+ SET_ERRNO(EINVAL);
+ return -1;
+ }
+
+ mi_vector_hash(key, key_len, cdbr->seed, hashes);
+
+ hashes[0] = fast_remainder32(hashes[0], cdbr->entries_index,
+ cdbr->entries_index_m, cdbr->entries_index_s1,
+ cdbr->entries_index_s2);
+ hashes[1] = fast_remainder32(hashes[1], cdbr->entries_index,
+ cdbr->entries_index_m, cdbr->entries_index_s1,
+ cdbr->entries_index_s2);
+ hashes[2] = fast_remainder32(hashes[2], cdbr->entries_index,
+ cdbr->entries_index_m, cdbr->entries_index_s1,
+ cdbr->entries_index_s2);
+
+ idx = get_uintX(cdbr->hash_base, hashes[0], cdbr->index_size);
+ idx += get_uintX(cdbr->hash_base, hashes[1], cdbr->index_size);
+ idx += get_uintX(cdbr->hash_base, hashes[2], cdbr->index_size);
+
+ return cdbr_get(cdbr, fast_remainder32(idx, cdbr->entries,
+ cdbr->entries_m, cdbr->entries_s1, cdbr->entries_s2), data,
+ data_len);
+}
+
+void
+cdbr_close(struct cdbr *cdbr)
+{
+ if (cdbr->unmap)
+ (*cdbr->unmap)(cdbr->cookie, cdbr->mmap_base, cdbr->mmap_size);
+ free(cdbr);
+}
Index: src/common/lib/libc/stdlib/mi_vector_hash.c
diff -u /dev/null src/common/lib/libc/stdlib/mi_vector_hash.c:1.1
--- /dev/null Wed Dec 11 01:24:09 2013
+++ src/common/lib/libc/stdlib/mi_vector_hash.c Wed Dec 11 01:24:08 2013
@@ -0,0 +1,182 @@
+/* $NetBSD: mi_vector_hash.c,v 1.1 2013/12/11 01:24:08 joerg Exp $ */
+/*-
+ * Copyright (c) 2009 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Joerg Sonnenberger.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * See http://burtleburtle.net/bob/hash/doobs.html for the full description
+ * and the original version of the code. This version differs by exposing
+ * the full internal state and avoiding byte operations in the inner loop
+ * if the key is aligned correctly.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: mi_vector_hash.c,v 1.1 2013/12/11 01:24:08 joerg Exp $");
+
+#if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
+#include <sys/endian.h>
+#endif
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+#include <sys/types.h>
+#include <sys/systm.h>
+#include <lib/libkern/libkern.h>
+#else
+#include "namespace.h"
+
+#include <stdint.h>
+#include <stdlib.h>
+#endif
+
+#define mix(a, b, c) do { \
+ a -= b; a -= c; a ^= (c >> 13); \
+ b -= c; b -= a; b ^= (a << 8); \
+ c -= a; c -= b; c ^= (b >> 13); \
+ a -= b; a -= c; a ^= (c >> 12); \
+ b -= c; b -= a; b ^= (a << 16); \
+ c -= a; c -= b; c ^= (b >> 5); \
+ a -= b; a -= c; a ^= (c >> 3); \
+ b -= c; b -= a; b ^= (a << 10); \
+ c -= a; c -= b; c ^= (b >> 15); \
+} while (/* CONSTCOND */0)
+
+#define FIXED_SEED 0x9e3779b9 /* Golden ratio, arbitrary constant */
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+#ifdef __weak_alias
+__weak_alias(mi_vector_hash, _mi_vector_hash)
+#endif
+#endif
+
+void
+mi_vector_hash(const void * __restrict key, size_t len, uint32_t seed,
+ uint32_t hashes[3])
+{
+ static const uint32_t mask[4] = {
+ 0x000000ff, 0x0000ffff, 0x00ffffff, 0xffffffff
+ };
+ uint32_t orig_len, a, b, c;
+ const uint8_t *k;
+
+ orig_len = (uint32_t)len;
+
+ a = b = FIXED_SEED;
+ c = seed;
+
+ if ((uintptr_t)key & 3) {
+ k = key;
+ while (len >= 12) {
+ a += le32dec(k);
+ b += le32dec(k + 4);
+ c += le32dec(k + 8);
+ mix(a, b, c);
+ k += 12;
+ len -= 12;
+ }
+ c += orig_len;
+
+ if (len > 8) {
+ switch (len) {
+ case 11:
+ c += (uint32_t)k[10] << 24;
+ /* FALLTHROUGH */
+ case 10:
+ c += (uint32_t)k[9] << 16;
+ /* FALLTHROUGH */
+ case 9:
+ c += (uint32_t)k[8] << 8;
+ /* FALLTHROUGH */
+ }
+ b += le32dec(k + 4);
+ a += le32dec(k);
+ } else if (len > 4) {
+ switch (len) {
+ case 8:
+ b += (uint32_t)k[7] << 24;
+ /* FALLTHROUGH */
+ case 7:
+ b += (uint32_t)k[6] << 16;
+ /* FALLTHROUGH */
+ case 6:
+ b += (uint32_t)k[5] << 8;
+ /* FALLTHROUGH */
+ case 5:
+ b += k[4];
+ /* FALLTHROUGH */
+ }
+ a += le32dec(k);
+ } else if (len) {
+ switch (len) {
+ case 4:
+ a += (uint32_t)k[3] << 24;
+ /* FALLTHROUGH */
+ case 3:
+ a += (uint32_t)k[2] << 16;
+ /* FALLTHROUGH */
+ case 2:
+ a += (uint32_t)k[1] << 8;
+ /* FALLTHROUGH */
+ case 1:
+ a += k[0];
+ /* FALLTHROUGH */
+ }
+ }
+ } else {
+ const uint32_t *key32 = key;
+ while (len >= 12) {
+ a += le32toh(key32[0]);
+ b += le32toh(key32[1]);
+ c += le32toh(key32[2]);
+ mix(a, b, c);
+ key32 += 3;
+ len -= 12;
+ }
+ c += orig_len;
+
+ if (len > 8) {
+ c += (le32toh(key32[2]) & mask[len - 9]) << 8;
+ b += le32toh(key32[1]);
+ a += le32toh(key32[0]);
+ } else if (len > 4) {
+ b += le32toh(key32[1]) & mask[len - 5];
+ a += le32toh(key32[0]);
+ } else if (len)
+ a += le32toh(key32[0]) & mask[len - 1];
+ }
+ mix(a, b, c);
+ hashes[0] = a;
+ hashes[1] = b;
+ hashes[2] = c;
+}
Index: src/sys/sys/cdbr.h
diff -u /dev/null src/sys/sys/cdbr.h:1.1
--- /dev/null Wed Dec 11 01:24:09 2013
+++ src/sys/sys/cdbr.h Wed Dec 11 01:24:08 2013
@@ -0,0 +1,64 @@
+/* $NetBSD: cdbr.h,v 1.1 2013/12/11 01:24:08 joerg Exp $ */
+/*-
+ * Copyright (c) 2010 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Joerg Sonnenberger.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef _CDBR_H
+#define _CDBR_H
+
+#include <sys/cdefs.h>
+#if defined(_KERNEL) || defined(_STANDALONE)
+#include <sys/types.h>
+#else
+#include <inttypes.h>
+#include <stddef.h>
+#endif
+
+#define CDBR_DEFAULT 0
+
+struct cdbr;
+
+__BEGIN_DECLS
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+struct cdbr *cdbr_open(const char *, int);
+#endif
+struct cdbr *cdbr_open_mem(void *, size_t, int,
+ void (*)(void *, void *, size_t), void *);
+uint32_t cdbr_entries(struct cdbr *);
+int cdbr_get(struct cdbr *, uint32_t, const void **, size_t *);
+int cdbr_find(struct cdbr *, const void *, size_t,
+ const void **, size_t *);
+void cdbr_close(struct cdbr *);
+
+__END_DECLS
+
+#endif /* _CDBR_H */
