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
cdbr_unmap(void * cookie __unused,void * base,size_t size)115 cdbr_unmap(void *cookie __unused, void *base, size_t size)
116 {
117 munmap(base, size);
118 }
119
120 /* ARGSUSED */
121 struct cdbr *
cdbr_open(const char * path,int flags)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 *
cdbr_open_mem(void * base,size_t size,int flags __unused,void (* unmap)(void *,void *,size_t),void * cookie)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
get_uintX(const uint8_t * addr,uint32_t idx,int size)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
cdbr_entries(struct cdbr * cdbr)240 cdbr_entries(struct cdbr *cdbr)
241 {
242
243 return cdbr->entries;
244 }
245
246 int
cdbr_get(struct cdbr * cdbr,uint32_t idx,const void ** data,size_t * data_len)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
cdbr_find(struct cdbr * cdbr,const void * key,size_t key_len,const void ** data,size_t * data_len)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
cdbr_close(struct cdbr * cdbr)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