1/* $NetBSD: cdbr.c,v 1.2.8.1 2012/06/23 22:54:58 riz 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.8.1 2012/06/23 22:54:58 riz Exp $"); 40 41#include "namespace.h" 42 43#if !HAVE_NBTOOL_CONFIG_H 44#include <sys/bitops.h> 45#endif 46#if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H 47#include <sys/endian.h> 48#endif 49 50#include <sys/mman.h> 51#include <sys/stat.h> 52#include <cdbr.h> 53#include <errno.h> 54#include <fcntl.h> 55#include <inttypes.h> 56#include <stdlib.h> 57#include <string.h> 58#include <unistd.h> 59 60#ifdef __weak_alias 61__weak_alias(cdbr_close,_cdbr_close) 62__weak_alias(cdbr_find,_cdbr_find) 63__weak_alias(cdbr_get,_cdbr_get) 64__weak_alias(cdbr_open,_cdbr_open) 65#endif 66 67#if HAVE_NBTOOL_CONFIG_H 68#define fast_divide32_prepare(d,m,s1,s2) (void)0 69#define fast_remainder32(v,d,m,s1,s2) (v%d) 70#endif 71 72struct cdbr { 73 uint8_t *mmap_base; 74 size_t mmap_size; 75 76 uint8_t *hash_base; 77 uint8_t *offset_base; 78 uint8_t *data_base; 79 80 uint32_t data_size; 81 uint32_t entries; 82 uint32_t entries_index; 83 uint32_t seed; 84 85 uint8_t offset_size; 86 uint8_t index_size; 87 88 uint32_t entries_m; 89 uint32_t entries_index_m; 90 uint8_t entries_s1, entries_s2; 91 uint8_t entries_index_s1, entries_index_s2; 92}; 93 94/* ARGSUSED */ 95struct cdbr * 96cdbr_open(const char *path, int flags) 97{ 98 uint8_t buf[40]; 99 int fd; 100 struct cdbr *cdbr; 101 struct stat sb; 102 103 if ((fd = open(path, O_RDONLY)) == -1) 104 return NULL; 105 106 errno = EINVAL; 107 if (fstat(fd, &sb) == -1 || 108 read(fd, buf, sizeof(buf)) != sizeof(buf) || 109 memcmp(buf, "NBCDB\n\0\001", 8) || 110 (cdbr = malloc(sizeof(*cdbr))) == NULL) { 111 close(fd); 112 return NULL; 113 } 114 115 cdbr->data_size = le32dec(buf + 24); 116 cdbr->entries = le32dec(buf + 28); 117 cdbr->entries_index = le32dec(buf + 32); 118 cdbr->seed = le32dec(buf + 36); 119 120 if (cdbr->data_size < 0x100) 121 cdbr->offset_size = 1; 122 else if (cdbr->data_size < 0x10000) 123 cdbr->offset_size = 2; 124 else 125 cdbr->offset_size = 4; 126 127 if (cdbr->entries_index < 0x100) 128 cdbr->index_size = 1; 129 else if (cdbr->entries_index < 0x10000) 130 cdbr->index_size = 2; 131 else 132 cdbr->index_size = 4; 133 134 cdbr->mmap_size = (size_t)sb.st_size; 135 cdbr->mmap_base = mmap(NULL, cdbr->mmap_size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0); 136 close(fd); 137 138 if (cdbr->mmap_base == MAP_FAILED) { 139 free(cdbr); 140 return NULL; 141 } 142 143 cdbr->hash_base = cdbr->mmap_base + 40; 144 cdbr->offset_base = cdbr->hash_base + cdbr->entries_index * cdbr->index_size; 145 if (cdbr->entries_index * cdbr->index_size % cdbr->offset_size) 146 cdbr->offset_base += cdbr->offset_size - 147 cdbr->entries_index * cdbr->index_size % cdbr->offset_size; 148 cdbr->data_base = cdbr->offset_base + (cdbr->entries + 1) * cdbr->offset_size; 149 150 if (cdbr->hash_base < cdbr->mmap_base || 151 cdbr->offset_base < cdbr->mmap_base || 152 cdbr->data_base < cdbr->mmap_base || 153 cdbr->data_base + cdbr->data_size < cdbr->mmap_base || 154 cdbr->data_base + cdbr->data_size > 155 cdbr->mmap_base + cdbr->mmap_size) { 156 errno = EINVAL; 157 cdbr_close(cdbr); 158 return NULL; 159 } 160 161 if (cdbr->entries) { 162 fast_divide32_prepare(cdbr->entries, &cdbr->entries_m, 163 &cdbr->entries_s1, &cdbr->entries_s2); 164 } 165 if (cdbr->entries_index) { 166 fast_divide32_prepare(cdbr->entries_index, 167 &cdbr->entries_index_m, 168 &cdbr->entries_index_s1, &cdbr->entries_index_s2); 169 } 170 171 return cdbr; 172} 173 174static inline uint32_t 175get_uintX(const uint8_t *addr, uint32_t idx, int size) 176{ 177 addr += idx * size; 178 179 if (size == 4) 180 return /* LINTED */le32toh(*(const uint32_t *)addr); 181 else if (size == 2) 182 return /* LINTED */le16toh(*(const uint16_t *)addr); 183 else 184 return *addr; 185} 186 187uint32_t 188cdbr_entries(struct cdbr *cdbr) 189{ 190 191 return cdbr->entries; 192} 193 194int 195cdbr_get(struct cdbr *cdbr, uint32_t idx, const void **data, size_t *data_len) 196{ 197 uint32_t start, end; 198 199 if (idx >= cdbr->entries) { 200 errno = EINVAL; 201 return -1; 202 } 203 204 start = get_uintX(cdbr->offset_base, idx, cdbr->offset_size); 205 end = get_uintX(cdbr->offset_base, idx + 1, cdbr->offset_size); 206 207 if (start > end) { 208 errno = EIO; 209 return -1; 210 } 211 212 if (end > cdbr->data_size) { 213 errno = EIO; 214 return -1; 215 } 216 217 *data = cdbr->data_base + start; 218 *data_len = end - start; 219 220 return 0; 221} 222 223int 224cdbr_find(struct cdbr *cdbr, const void *key, size_t key_len, 225 const void **data, size_t *data_len) 226{ 227 uint32_t hashes[3], idx; 228 229 if (cdbr->entries_index == 0) { 230 errno = EINVAL; 231 return -1; 232 } 233 234 mi_vector_hash(key, key_len, cdbr->seed, hashes); 235 236 hashes[0] = fast_remainder32(hashes[0], cdbr->entries_index, 237 cdbr->entries_index_m, cdbr->entries_index_s1, 238 cdbr->entries_index_s2); 239 hashes[1] = fast_remainder32(hashes[1], cdbr->entries_index, 240 cdbr->entries_index_m, cdbr->entries_index_s1, 241 cdbr->entries_index_s2); 242 hashes[2] = fast_remainder32(hashes[2], cdbr->entries_index, 243 cdbr->entries_index_m, cdbr->entries_index_s1, 244 cdbr->entries_index_s2); 245 246 idx = get_uintX(cdbr->hash_base, hashes[0], cdbr->index_size); 247 idx += get_uintX(cdbr->hash_base, hashes[1], cdbr->index_size); 248 idx += get_uintX(cdbr->hash_base, hashes[2], cdbr->index_size); 249 250 return cdbr_get(cdbr, fast_remainder32(idx, cdbr->entries, 251 cdbr->entries_m, cdbr->entries_s1, cdbr->entries_s2), data, 252 data_len); 253} 254 255void 256cdbr_close(struct cdbr *cdbr) 257{ 258 munmap(cdbr->mmap_base, cdbr->mmap_size); 259 free(cdbr); 260} 261