1 | /* $NetBSD: cdbr.c,v 1.1 2013/12/11 01:24:08 joerg 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.1 2013/12/11 01:24:08 joerg 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, |
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 | |