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