diff options
| author | joerg <joerg@NetBSD.org> | 2013-12-11 01:24:08 +0000 |
|---|---|---|
| committer | joerg <joerg@NetBSD.org> | 2013-12-11 01:24:08 +0000 |
| commit | 8a05e9a38d7cbb7726fc62dc486cee1896bb5173 (patch) | |
| tree | 90560bb06ba1978751f965d7585e4754764621aa | |
| parent | 82b90e35a45c68a97cac0e7d83a6905c2e29c8b7 (diff) | |
Allow kernel code to access constant databases by moving cdbr(3) and the
required mi_vector_hash(3) into src/common.
| -rw-r--r-- | common/lib/libc/cdb/cdbr.c | 313 | ||||
| -rw-r--r-- | common/lib/libc/stdlib/mi_vector_hash.c (renamed from lib/libc/stdlib/mi_vector_hash.c) | 17 | ||||
| -rw-r--r-- | distrib/sets/lists/comp/mi | 3 | ||||
| -rw-r--r-- | include/Makefile | 4 | ||||
| -rw-r--r-- | lib/libc/cdb/Makefile.inc | 3 | ||||
| -rw-r--r-- | sys/lib/libkern/Makefile.libkern | 6 | ||||
| -rw-r--r-- | sys/lib/libkern/libkern.h | 4 | ||||
| -rw-r--r-- | sys/sys/Makefile | 5 | ||||
| -rw-r--r-- | sys/sys/cdbr.h (renamed from include/cdbr.h) | 8 | ||||
| -rw-r--r-- | tools/compat/Makefile | 3 | ||||
| -rw-r--r-- | tools/compat/cdbr.h | 4 |
11 files changed, 354 insertions, 16 deletions
diff --git a/common/lib/libc/cdb/cdbr.c b/common/lib/libc/cdb/cdbr.c new file mode 100644 index 00000000000..9dcdbd0e3ef --- /dev/null +++ b/common/lib/libc/cdb/cdbr.c @@ -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); +} diff --git a/lib/libc/stdlib/mi_vector_hash.c b/common/lib/libc/stdlib/mi_vector_hash.c index 0cd75f206d3..7c26df27127 100644 --- a/lib/libc/stdlib/mi_vector_hash.c +++ b/common/lib/libc/stdlib/mi_vector_hash.c @@ -1,4 +1,4 @@ -/* $NetBSD: mi_vector_hash.c,v 1.4 2011/10/21 23:45:56 joerg Exp $ */ +/* $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. @@ -43,15 +43,22 @@ #endif #include <sys/cdefs.h> -__RCSID("$NetBSD: mi_vector_hash.c,v 1.4 2011/10/21 23:45:56 joerg Exp $"); - -#include "namespace.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); \ @@ -67,9 +74,11 @@ __RCSID("$NetBSD: mi_vector_hash.c,v 1.4 2011/10/21 23:45:56 joerg Exp $"); #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, diff --git a/distrib/sets/lists/comp/mi b/distrib/sets/lists/comp/mi index 5b4b83541a8..c2776193cb5 100644 --- a/distrib/sets/lists/comp/mi +++ b/distrib/sets/lists/comp/mi @@ -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 diff --git a/include/Makefile b/include/Makefile index 54dbafef1bc..0f94a2feefa 100644 --- a/include/Makefile +++ b/include/Makefile @@ -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 \ diff --git a/lib/libc/cdb/Makefile.inc b/lib/libc/cdb/Makefile.inc index 3b8a2f74840..c08c22e0086 100644 --- a/lib/libc/cdb/Makefile.inc +++ b/lib/libc/cdb/Makefile.inc @@ -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 diff --git a/sys/lib/libkern/Makefile.libkern b/sys/lib/libkern/Makefile.libkern index b3cad74bac8..16f4a39b783 100644 --- a/sys/lib/libkern/Makefile.libkern +++ b/sys/lib/libkern/Makefile.libkern @@ -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 diff --git a/sys/lib/libkern/libkern.h b/sys/lib/libkern/libkern.h index 02d6799b933..0162675562d 100644 --- a/sys/lib/libkern/libkern.h +++ b/sys/lib/libkern/libkern.h @@ -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 *, size_t); 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 *); diff --git a/sys/sys/Makefile b/sys/sys/Makefile index 0ba4aed7df7..afcd259ddf0 100644 --- a/sys/sys/Makefile +++ b/sys/sys/Makefile @@ -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_mids.h ataio.h atomic.h audioio.h \ 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 \ diff --git a/include/cdbr.h b/sys/sys/cdbr.h index b0f602d77e2..f0120a25893 100644 --- a/include/cdbr.h +++ b/sys/sys/cdbr.h @@ -1,4 +1,4 @@ -/* $NetBSD: cdbr.h,v 1.2 2013/12/05 21:17:23 joerg Exp $ */ +/* $NetBSD: cdbr.h,v 1.1 2013/12/11 01:24:08 joerg Exp $ */ /*- * Copyright (c) 2010 The NetBSD Foundation, Inc. * All rights reserved. @@ -35,8 +35,12 @@ #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 @@ -44,7 +48,9 @@ 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 *); diff --git a/tools/compat/Makefile b/tools/compat/Makefile index 182cbdda6d4..c88a12cbd3f 100644 --- a/tools/compat/Makefile +++ b/tools/compat/Makefile @@ -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} -I${.CURDIR}/sys \ ${.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 \ diff --git a/tools/compat/cdbr.h b/tools/compat/cdbr.h index bdf5cd6c8bb..4f09c9e869f 100644 --- a/tools/compat/cdbr.h +++ b/tools/compat/cdbr.h @@ -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" |
