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 */