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 89struct 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) 114static void 115cdbr_unmap(void *cookie __unused, void *base, size_t size) 116{ 117 munmap(base, size); 118} 119 120/* ARGSUSED */ 121struct cdbr * 122cdbr_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 158struct cdbr * 159cdbr_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 226static inline uint32_t 227get_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 239uint32_t 240cdbr_entries(struct cdbr *cdbr) 241{ 242 243 return cdbr->entries; 244} 245 246int 247cdbr_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 275int 276cdbr_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 307void 308cdbr_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