Home | History | Annotate | Line # | Download | only in cdb 
      1 /*	$NetBSD: cdbr.c,v 1.2 2017/01/10 23:06:06 christos Exp $	*/
      2 /*-
      3  * Copyright (c) 2010 The NetBSD Foundation, Inc.
      4  * All rights reserved.
      5  *
      6  * This code is derived from software contributed to The NetBSD Foundation
      7  * by Joerg Sonnenberger.
      8  *
      9  * Redistribution and use in source and binary forms, with or without
     10  * modification, are permitted provided that the following conditions
     11  * are met:
     12  *
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in
     17  *    the documentation and/or other materials provided with the
     18  *    distribution.
     19  *
     20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
     23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
     24  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
     25  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
     26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
     28  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     29  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
     30  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     31  * SUCH DAMAGE.
     32  */
     33 
     34 #if HAVE_NBTOOL_CONFIG_H
     35 #include "nbtool_config.h"
     36 #endif
     37 
     38 #include <sys/cdefs.h>
     39 __RCSID("$NetBSD: cdbr.c,v 1.2 2017/01/10 23:06:06 christos Exp $");
     40 
     41 #if !defined(_KERNEL) && !defined(_STANDALONE)
     42 #include "namespace.h"
     43 #endif
     44 
     45 #if !HAVE_NBTOOL_CONFIG_H
     46 #include <sys/bitops.h>
     47 #endif
     48 #if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
     49 #include <sys/endian.h>
     50 #endif
     51 
     52 #if defined(_KERNEL) || defined(_STANDALONE)
     53 #include <sys/cdbr.h>
     54 #include <sys/kmem.h>
     55 #include <sys/systm.h>
     56 #include <lib/libkern/libkern.h>
     57 #define SET_ERRNO(val)
     58 #define malloc(size) kmem_alloc(size, KM_SLEEP)
     59 #define free(ptr) kmem_free(ptr, sizeof(struct cdbr))
     60 #else
     61 #include <sys/mman.h>
     62 #include <sys/stat.h>
     63 #include <cdbr.h>
     64 #include <errno.h>
     65 #include <fcntl.h>
     66 #include <inttypes.h>
     67 #include <limits.h>
     68 #include <stdlib.h>
     69 #include <string.h>
     70 #include <unistd.h>
     71 #define SET_ERRNO(val) errno = (val)
     72 #endif
     73 
     74 #if !defined(_KERNEL) && !defined(_STANDALONE)
     75 #ifdef __weak_alias
     76 __weak_alias(cdbr_close,_cdbr_close)
     77 __weak_alias(cdbr_find,_cdbr_find)
     78 __weak_alias(cdbr_get,_cdbr_get)
     79 __weak_alias(cdbr_open,_cdbr_open)
     80 __weak_alias(cdbr_open_mem,_cdbr_open_mem)
     81 #endif
     82 #endif
     83 
     84 #if HAVE_NBTOOL_CONFIG_H
     85 #define	fast_divide32_prepare(d,m,s1,s2)	(void)0
     86 #define	fast_remainder32(v,d,m,s1,s2)		(v%d)
     87 #endif
     88 
     89 struct cdbr {
     90 	void (*unmap)(void *, void *, size_t);
     91 	void *cookie;
     92 	uint8_t *mmap_base;
     93 	size_t mmap_size;
     94 
     95 	uint8_t *hash_base;
     96 	uint8_t *offset_base;
     97 	uint8_t *data_base;
     98 
     99 	uint32_t data_size;
    100 	uint32_t entries;
    101 	uint32_t entries_index;
    102 	uint32_t seed;
    103 
    104 	uint8_t offset_size;
    105 	uint8_t index_size;
    106 
    107 	uint32_t entries_m;
    108 	uint32_t entries_index_m;
    109 	uint8_t entries_s1, entries_s2;
    110 	uint8_t entries_index_s1, entries_index_s2;
    111 };
    112 
    113 #if !defined(_KERNEL) && !defined(_STANDALONE)
    114 static void
    115 cdbr_unmap(void *cookie __unused, void *base, size_t size)
    116 {
    117 	munmap(base, size);
    118 }
    119 
    120 /* ARGSUSED */
    121 struct cdbr *
    122 cdbr_open(const char *path, int flags)
    123 {
    124 	void *base;
    125 	size_t size;
    126 	int fd;
    127 	struct cdbr *cdbr;
    128 	struct stat sb;
    129 
    130 	if ((fd = open(path, O_RDONLY)) == -1)
    131 		return NULL;
    132 	if (fstat(fd, &sb) == -1) {
    133 		close(fd);
    134 		return NULL;
    135 	}
    136 
    137 	if (sb.st_size >= SSIZE_MAX) {
    138 		close(fd);
    139 		SET_ERRNO(EINVAL);
    140 		return NULL;
    141 	}
    142 
    143 
    144 	size = (size_t)sb.st_size;
    145 	base = mmap(NULL, size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0);
    146 	close(fd);
    147 
    148 	if (base == MAP_FAILED)
    149 		return NULL;
    150 
    151 	cdbr = cdbr_open_mem(base, size, flags, cdbr_unmap, NULL);
    152 	if (cdbr == NULL)
    153 		munmap(base, size);
    154 	return cdbr;
    155 }
    156 #endif
    157 
    158 struct cdbr *
    159 cdbr_open_mem(void *base, size_t size, int flags __unused,
    160     void (*unmap)(void *, void *, size_t), void *cookie)
    161 {
    162 	struct cdbr *cdbr;
    163 	uint8_t *buf = base;
    164 	if (size < 40 || memcmp(buf, "NBCDB\n\0\001", 8)) {
    165 		SET_ERRNO(EINVAL);
    166 		return NULL;
    167 	}
    168 
    169 	cdbr = malloc(sizeof(*cdbr));
    170 	cdbr->unmap = unmap;
    171 	cdbr->cookie = cookie;
    172 
    173 	cdbr->data_size = le32dec(buf + 24);
    174 	cdbr->entries = le32dec(buf + 28);
    175 	cdbr->entries_index = le32dec(buf + 32);
    176 	cdbr->seed = le32dec(buf + 36);
    177 
    178 	if (cdbr->data_size < 0x100)
    179 		cdbr->offset_size = 1;
    180 	else if (cdbr->data_size < 0x10000)
    181 		cdbr->offset_size = 2;
    182 	else
    183 		cdbr->offset_size = 4;
    184 
    185 	if (cdbr->entries_index < 0x100)
    186 		cdbr->index_size = 1;
    187 	else if (cdbr->entries_index < 0x10000)
    188 		cdbr->index_size = 2;
    189 	else
    190 		cdbr->index_size = 4;
    191 
    192 	cdbr->mmap_base = base;
    193 	cdbr->mmap_size = size;
    194 
    195 	cdbr->hash_base = cdbr->mmap_base + 40;
    196 	cdbr->offset_base = cdbr->hash_base + cdbr->entries_index * cdbr->index_size;
    197 	if (cdbr->entries_index * cdbr->index_size % cdbr->offset_size)
    198 		cdbr->offset_base += cdbr->offset_size -
    199 		    cdbr->entries_index * cdbr->index_size % cdbr->offset_size;
    200 	cdbr->data_base = cdbr->offset_base + (cdbr->entries + 1) * cdbr->offset_size;
    201 
    202 	if (cdbr->hash_base < cdbr->mmap_base ||
    203 	    cdbr->offset_base < cdbr->mmap_base ||
    204 	    cdbr->data_base < cdbr->mmap_base ||
    205 	    cdbr->data_base + cdbr->data_size < cdbr->mmap_base ||
    206 	    cdbr->data_base + cdbr->data_size >
    207 	    cdbr->mmap_base + cdbr->mmap_size) {
    208 		SET_ERRNO(EINVAL);
    209 		free(cdbr);
    210 		return NULL;
    211 	}
    212 
    213 	if (cdbr->entries) {
    214 		fast_divide32_prepare(cdbr->entries, &cdbr->entries_m,
    215 		    &cdbr->entries_s1, &cdbr->entries_s2);
    216 	}
    217 	if (cdbr->entries_index) {
    218 		fast_divide32_prepare(cdbr->entries_index,
    219 		    &cdbr->entries_index_m,
    220 		    &cdbr->entries_index_s1, &cdbr->entries_index_s2);
    221 	}
    222 
    223 	return cdbr;
    224 }
    225 
    226 static inline uint32_t
    227 get_uintX(const uint8_t *addr, uint32_t idx, int size)
    228 {
    229 	addr += idx * size;
    230 
    231 	if (size == 4)
    232 		return /* LINTED */le32toh(*(const uint32_t *)addr);
    233 	else if (size == 2)
    234 		return /* LINTED */le16toh(*(const uint16_t *)addr);
    235 	else
    236 		return *addr;
    237 }
    238 
    239 uint32_t
    240 cdbr_entries(struct cdbr *cdbr)
    241 {
    242 
    243 	return cdbr->entries;
    244 }
    245 
    246 int
    247 cdbr_get(struct cdbr *cdbr, uint32_t idx, const void **data, size_t *data_len)
    248 {
    249 	uint32_t start, end;
    250 
    251 	if (idx >= cdbr->entries) {
    252 		SET_ERRNO(EINVAL);
    253 		return -1;
    254 	}
    255 
    256 	start = get_uintX(cdbr->offset_base, idx, cdbr->offset_size);
    257 	end = get_uintX(cdbr->offset_base, idx + 1, cdbr->offset_size);
    258 
    259 	if (start > end) {
    260 		SET_ERRNO(EIO);
    261 		return -1;
    262 	}
    263 
    264 	if (end > cdbr->data_size) {
    265 		SET_ERRNO(EIO);
    266 		return -1;
    267 	}
    268 
    269 	*data = cdbr->data_base + start;
    270 	*data_len = end - start;
    271 
    272 	return 0;
    273 }
    274 
    275 int
    276 cdbr_find(struct cdbr *cdbr, const void *key, size_t key_len,
    277     const void **data, size_t *data_len)
    278 {
    279 	uint32_t hashes[3], idx;
    280 
    281 	if (cdbr->entries_index == 0) {
    282 		SET_ERRNO(EINVAL);
    283 		return -1;
    284 	}
    285 
    286 	mi_vector_hash(key, key_len, cdbr->seed, hashes);
    287 
    288 	hashes[0] = fast_remainder32(hashes[0], cdbr->entries_index,
    289 	    cdbr->entries_index_m, cdbr->entries_index_s1,
    290 	    cdbr->entries_index_s2);
    291 	hashes[1] = fast_remainder32(hashes[1], cdbr->entries_index,
    292 	    cdbr->entries_index_m, cdbr->entries_index_s1,
    293 	    cdbr->entries_index_s2);
    294 	hashes[2] = fast_remainder32(hashes[2], cdbr->entries_index,
    295 	    cdbr->entries_index_m, cdbr->entries_index_s1,
    296 	    cdbr->entries_index_s2);
    297 
    298 	idx = get_uintX(cdbr->hash_base, hashes[0], cdbr->index_size);
    299 	idx += get_uintX(cdbr->hash_base, hashes[1], cdbr->index_size);
    300 	idx += get_uintX(cdbr->hash_base, hashes[2], cdbr->index_size);
    301 
    302 	return cdbr_get(cdbr, fast_remainder32(idx, cdbr->entries,
    303 	    cdbr->entries_m, cdbr->entries_s1, cdbr->entries_s2), data,
    304 	    data_len);
    305 }
    306 
    307 void
    308 cdbr_close(struct cdbr *cdbr)
    309 {
    310 	if (cdbr->unmap)
    311 		(*cdbr->unmap)(cdbr->cookie, cdbr->mmap_base, cdbr->mmap_size);
    312 	free(cdbr);
    313 }
    314