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