File: | src/lib/libc/stdlib/icdb.c |
Warning: | line 229, column 2 Value stored to 'idxlen' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: icdb.c,v 1.8 2016/09/04 16:56:02 nicm Exp $ */ |
2 | /* |
3 | * Copyright (c) 2015 Ted Unangst <tedu@openbsd.org> |
4 | * |
5 | * Permission to use, copy, modify, and distribute this software for any |
6 | * purpose with or without fee is hereby granted, provided that the above |
7 | * copyright notice and this permission notice appear in all copies. |
8 | * |
9 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
10 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
11 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR |
12 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
13 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN |
14 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF |
15 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
16 | */ |
17 | |
18 | #include <errno(*__errno()).h> |
19 | #include <fcntl.h> |
20 | #include <icdb.h> |
21 | #include <stddef.h> |
22 | #include <stdint.h> |
23 | #include <stdio.h> |
24 | #include <stdlib.h> |
25 | #include <string.h> |
26 | #include <unistd.h> |
27 | |
28 | #include <sys/mman.h> |
29 | #include <sys/stat.h> |
30 | |
31 | #include <siphash.h> |
32 | |
33 | /* |
34 | * Creating a new icdb: icdb_new |
35 | * Opening existing icdb: icdb_open |
36 | * |
37 | * Adding new entries: icdb_add |
38 | * Adding entries does not update the disk or indices. |
39 | * |
40 | * Save to disk: icdb_save |
41 | * Update indices: icdb_rehash |
42 | * icdb_save will call rehash. |
43 | * |
44 | * Change an existing entry: icdb_update |
45 | * Changing entries does write to disk. |
46 | * |
47 | * Find an entry: icdb_lookup |
48 | * Looking up an entry is only defined when the indices are synced. |
49 | * |
50 | * Close and free resources: icdb_close |
51 | */ |
52 | |
53 | /* |
54 | * There are two major modes of operation. |
55 | * |
56 | * Existing databases use the mmap codepath. The entire database is mapped |
57 | * into the address space for quick access. Individual entries may be updated, |
58 | * but no new entries added. |
59 | * |
60 | * New databases use malloc backed memory instead. The database may be saved |
61 | * with icdb_save. It should be saved to a new file to avoid corrupting any |
62 | * open databases in other processes. |
63 | */ |
64 | |
65 | /* |
66 | * An icdb has the following format: |
67 | * struct icbinfo header |
68 | * indexes [ uint32_t * indexsize * nkeys ] |
69 | * entries [ entrysize * nentries ] |
70 | * |
71 | * To find an entry in the file, the user specifies which key to use. |
72 | * The key is hashed and looked up in the index. The index contains the |
73 | * position of the entry in the entries array. -1 identifies not found. |
74 | * Chaining is done by rehashing the hash. All keys are fixed size byte arrays. |
75 | */ |
76 | |
77 | /* |
78 | * Header info for icdb. This struct is stored on disk. |
79 | */ |
80 | struct icdbinfo { |
81 | uint32_t magic; /* magic */ |
82 | uint32_t version; /* user specified version */ |
83 | uint32_t nentries; /* number of entries stored */ |
84 | uint32_t entrysize; /* size of each entry */ |
85 | uint32_t indexsize; /* number of entries in hash index */ |
86 | uint32_t nkeys; /* number of keys defined */ |
87 | uint32_t keysize[8]; /* size of each key */ |
88 | uint32_t keyoffset[8]; /* offset of each key in entry */ |
89 | SIPHASH_KEY siphashkey; /* random hash key */ |
90 | }; |
91 | |
92 | /* |
93 | * In memory representation with auxiliary data. |
94 | * idxdata and entries will be written to disk after info. |
95 | */ |
96 | struct icdb { |
97 | struct icdbinfo *info; |
98 | void *idxdata[8]; |
99 | void *entries; |
100 | size_t maplen; |
101 | uint32_t allocated; |
102 | int fd; |
103 | }; |
104 | |
105 | static const uint32_t magic = 0x1ca9d0b7; |
106 | |
107 | static uint32_t |
108 | roundup(uint32_t num) |
109 | { |
110 | uint32_t r = 2; |
111 | |
112 | while (r < num * 3 / 2) |
113 | r *= 2; |
114 | return r; |
115 | } |
116 | |
117 | struct icdb * |
118 | icdb_new(uint32_t version, uint32_t nentries, uint32_t entrysize, |
119 | uint32_t nkeys, const uint32_t *keysizes, const uint32_t *keyoffsets) |
120 | { |
121 | struct icdb *db; |
122 | struct icdbinfo *info; |
123 | int i; |
124 | |
125 | if (entrysize == 0 || entrysize > 1048576 || nkeys > 8) { |
126 | errno(*__errno()) = EINVAL22; |
127 | return NULL((void*)0); |
128 | } |
129 | |
130 | if (!(db = calloc(1, sizeof(*db)))) |
131 | return NULL((void*)0); |
132 | if (!(info = calloc(1, sizeof(*info)))) { |
133 | free(db); |
134 | return NULL((void*)0); |
135 | } |
136 | db->info = info; |
137 | db->fd = -1; |
138 | info->magic = magic; |
139 | info->version = version; |
140 | if (nentries) |
141 | if ((db->entries = reallocarray(NULL((void*)0), nentries, entrysize))) |
142 | db->allocated = nentries; |
143 | info->entrysize = entrysize; |
144 | info->nkeys = nkeys; |
145 | for (i = 0; i < nkeys; i++) { |
146 | info->keysize[i] = keysizes[i]; |
147 | info->keyoffset[i] = keyoffsets[i]; |
148 | } |
149 | return db; |
150 | } |
151 | DEF_WEAK(icdb_new)__asm__(".weak " "icdb_new" " ; " "icdb_new" " = " "_libc_icdb_new" ); |
152 | |
153 | struct icdb * |
154 | icdb_open(const char *name, int flags, uint32_t version) |
155 | { |
156 | struct icdb *db = NULL((void*)0); |
157 | struct icdbinfo *info; |
158 | struct stat sb; |
159 | uint8_t *ptr = MAP_FAILED((void *)-1); |
160 | uint32_t baseoff, indexsize, idxmask, idxlen; |
161 | int fd, i, saved_errno; |
162 | |
163 | if ((fd = open(name, flags | O_CLOEXEC0x10000)) == -1) |
164 | return NULL((void*)0); |
165 | if (fstat(fd, &sb) != 0) |
166 | goto fail; |
167 | if (sb.st_size < sizeof(struct icdbinfo)) |
168 | goto fail; |
169 | ptr = mmap(NULL((void*)0), sb.st_size, PROT_READ0x01 | |
170 | ((flags & O_RDWR0x0002) ? PROT_WRITE0x02 : 0), MAP_SHARED0x0001, fd, 0); |
171 | if (ptr == MAP_FAILED((void *)-1)) |
172 | goto fail; |
173 | info = (struct icdbinfo *)ptr; |
174 | if (info->magic != magic || info->version != version) { |
175 | errno(*__errno()) = ENOENT2; |
176 | goto fail; |
177 | } |
178 | |
179 | if (!(db = calloc(1, sizeof(*db)))) |
180 | goto fail; |
181 | db->info = info; |
182 | |
183 | indexsize = info->indexsize; |
184 | idxmask = indexsize - 1; |
185 | idxlen = indexsize * sizeof(uint32_t); |
186 | baseoff = sizeof(*info) + idxlen * info->nkeys; |
187 | |
188 | for (i = 0; i < info->nkeys; i++) |
189 | db->idxdata[i] = ptr + sizeof(*info) + i * idxlen; |
190 | db->entries = ptr + baseoff; |
191 | db->maplen = sb.st_size; |
192 | db->fd = fd; |
193 | return db; |
194 | |
195 | fail: |
196 | saved_errno = errno(*__errno()); |
197 | if (ptr != MAP_FAILED((void *)-1)) |
198 | munmap(ptr, sb.st_size); |
199 | if (fd != -1) |
200 | close(fd); |
201 | free(db); |
202 | errno(*__errno()) = saved_errno; |
203 | return NULL((void*)0); |
204 | } |
205 | DEF_WEAK(icdb_open)__asm__(".weak " "icdb_open" " ; " "icdb_open" " = " "_libc_icdb_open" ); |
206 | |
207 | int |
208 | icdb_get(struct icdb *db, void *entry, uint32_t idx) |
209 | { |
210 | uint32_t entrysize = db->info->entrysize; |
211 | |
212 | memcpy(entry, (uint8_t *)db->entries + idx * entrysize, entrysize); |
213 | return 0; |
214 | } |
215 | DEF_WEAK(icdb_get)__asm__(".weak " "icdb_get" " ; " "icdb_get" " = " "_libc_icdb_get" ); |
216 | |
217 | int |
218 | icdb_lookup(struct icdb *db, int keynum, const void *key, void *entry, |
219 | uint32_t *idxp) |
220 | { |
221 | struct icdbinfo *info = db->info; |
222 | uint32_t offset; |
223 | uint64_t hash; |
224 | uint32_t indexsize, idxmask, idxlen; |
225 | uint32_t *idxdata; |
226 | |
227 | indexsize = info->indexsize; |
228 | idxmask = indexsize - 1; |
229 | idxlen = indexsize * sizeof(uint32_t); |
Value stored to 'idxlen' is never read | |
230 | |
231 | idxdata = db->idxdata[keynum]; |
232 | |
233 | hash = SipHash24(&info->siphashkey, key, info->keysize[keynum])SipHash((&info->siphashkey), 2, 4, (key), (info->keysize [keynum])); |
234 | while ((offset = idxdata[hash & idxmask]) != -1) { |
235 | if (icdb_get(db, entry, offset) != 0) { |
236 | errno(*__errno()) = ENOENT2; |
237 | return -1; |
238 | } |
239 | if (memcmp((uint8_t *)entry + info->keyoffset[keynum], key, |
240 | info->keysize[keynum]) == 0) { |
241 | if (idxp) |
242 | *idxp = offset; |
243 | return 0; |
244 | } |
245 | hash = SipHash24(&info->siphashkey, &hash, sizeof(hash))SipHash((&info->siphashkey), 2, 4, (&hash), (sizeof (hash))); |
246 | } |
247 | return 1; |
248 | } |
249 | DEF_WEAK(icdb_lookup)__asm__(".weak " "icdb_lookup" " ; " "icdb_lookup" " = " "_libc_icdb_lookup" ); |
250 | |
251 | int |
252 | icdb_nentries(struct icdb *db) |
253 | { |
254 | return db->info->nentries; |
255 | } |
256 | DEF_WEAK(icdb_nentries)__asm__(".weak " "icdb_nentries" " ; " "icdb_nentries" " = " "_libc_icdb_nentries" ); |
257 | |
258 | const void * |
259 | icdb_entries(struct icdb *db) |
260 | { |
261 | return db->entries; |
262 | } |
263 | DEF_WEAK(icdb_entries)__asm__(".weak " "icdb_entries" " ; " "icdb_entries" " = " "_libc_icdb_entries" ); |
264 | |
265 | int |
266 | icdb_update(struct icdb *db, const void *entry, int offset) |
267 | { |
268 | struct icdbinfo *info = db->info; |
269 | uint32_t entrysize = info->entrysize; |
270 | uint32_t baseoff; |
271 | uint32_t indexsize, idxmask, idxlen; |
272 | |
273 | indexsize = info->indexsize; |
274 | idxmask = indexsize - 1; |
275 | idxlen = indexsize * sizeof(uint32_t); |
276 | baseoff = sizeof(*info) + idxlen * info->nkeys; |
277 | |
278 | memcpy((uint8_t *)db->entries + offset * entrysize, entry, entrysize); |
279 | if (db->fd != -1) { |
280 | msync((uint8_t *)db->entries + offset * entrysize, entrysize, |
281 | MS_SYNC0x02); |
282 | } |
283 | return 0; |
284 | } |
285 | DEF_WEAK(icdb_update)__asm__(".weak " "icdb_update" " ; " "icdb_update" " = " "_libc_icdb_update" ); |
286 | |
287 | int |
288 | icdb_add(struct icdb *db, const void *entry) |
289 | { |
290 | struct icdbinfo *info = db->info; |
291 | size_t entrysize = info->entrysize; |
292 | |
293 | if (db->allocated == info->nentries) { |
294 | void *p; |
295 | size_t amt = db->allocated ? db->allocated * 2 : 63; |
296 | if (!(p = reallocarray(db->entries, amt, entrysize))) |
297 | return -1; |
298 | db->allocated = amt; |
299 | db->entries = p; |
300 | } |
301 | memcpy((uint8_t *)db->entries + info->nentries * entrysize, |
302 | entry, entrysize); |
303 | info->nentries++; |
304 | return 0; |
305 | } |
306 | DEF_WEAK(icdb_add)__asm__(".weak " "icdb_add" " ; " "icdb_add" " = " "_libc_icdb_add" ); |
307 | |
308 | int |
309 | icdb_rehash(struct icdb *db) |
310 | { |
311 | struct icdbinfo *info = db->info; |
312 | uint32_t entrysize = info->entrysize; |
313 | uint32_t indexsize, idxmask, idxlen; |
314 | int i, j; |
315 | |
316 | indexsize = info->indexsize = roundup(info->nentries); |
317 | idxmask = indexsize - 1; |
318 | idxlen = sizeof(uint32_t) * indexsize; |
319 | |
320 | arc4random_buf(&info->siphashkey, sizeof(info->siphashkey)); |
321 | |
322 | for (i = 0; i < info->nkeys; i++) { |
323 | uint32_t *idxdata = reallocarray(db->idxdata[i], |
324 | indexsize, sizeof(uint32_t)); |
325 | if (!idxdata) |
326 | return -1; |
327 | memset(idxdata, 0xff, idxlen); |
328 | db->idxdata[i] = idxdata; |
329 | } |
330 | for (j = 0; j < info->nentries; j++) { |
331 | for (i = 0; i < info->nkeys; i++) { |
332 | uint32_t *idxdata = db->idxdata[i]; |
333 | uint64_t hash = SipHash24(&info->siphashkey,SipHash((&info->siphashkey), 2, 4, ((uint8_t *)db-> entries + j * entrysize + info->keyoffset[i]), (info->keysize [i])) |
334 | (uint8_t *)db->entries + j * entrysize +SipHash((&info->siphashkey), 2, 4, ((uint8_t *)db-> entries + j * entrysize + info->keyoffset[i]), (info->keysize [i])) |
335 | info->keyoffset[i], info->keysize[i])SipHash((&info->siphashkey), 2, 4, ((uint8_t *)db-> entries + j * entrysize + info->keyoffset[i]), (info->keysize [i])); |
336 | while (idxdata[hash & idxmask] != -1) |
337 | hash = SipHash24(&info->siphashkey, &hash, sizeof(hash))SipHash((&info->siphashkey), 2, 4, (&hash), (sizeof (hash))); |
338 | idxdata[hash & idxmask] = j; |
339 | } |
340 | } |
341 | return 0; |
342 | } |
343 | DEF_WEAK(icdb_rehash)__asm__(".weak " "icdb_rehash" " ; " "icdb_rehash" " = " "_libc_icdb_rehash" ); |
344 | |
345 | int |
346 | icdb_save(struct icdb *db, int fd) |
347 | { |
348 | struct icdbinfo *info = db->info; |
349 | uint32_t entrysize = info->entrysize; |
350 | uint32_t indexsize, idxlen; |
351 | int i; |
352 | |
353 | if (icdb_rehash(db) != 0) |
354 | return -1; |
355 | |
356 | indexsize = info->indexsize; |
357 | idxlen = sizeof(uint32_t) * indexsize; |
358 | |
359 | if (ftruncate(fd, 0) != 0) |
360 | return -1; |
361 | if (write(fd, info, sizeof(*info)) != sizeof(*info)) |
362 | return -1; |
363 | for (i = 0; i < info->nkeys; i++) { |
364 | if (write(fd, db->idxdata[i], idxlen) != idxlen) |
365 | return -1; |
366 | } |
367 | if (write(fd, db->entries, info->nentries * entrysize) != |
368 | info->nentries * entrysize) |
369 | return -1; |
370 | return 0; |
371 | } |
372 | DEF_WEAK(icdb_save)__asm__(".weak " "icdb_save" " ; " "icdb_save" " = " "_libc_icdb_save" ); |
373 | |
374 | int |
375 | icdb_close(struct icdb *db) |
376 | { |
377 | int i; |
378 | |
379 | if (db->fd == -1) { |
380 | for (i = 0; i < db->info->nkeys; i++) |
381 | free(db->idxdata[i]); |
382 | free(db->entries); |
383 | free(db->info); |
384 | } else { |
385 | munmap(db->info, db->maplen); |
386 | close(db->fd); |
387 | } |
388 | free(db); |
389 | return 0; |
390 | } |
391 | DEF_WEAK(icdb_close)__asm__(".weak " "icdb_close" " ; " "icdb_close" " = " "_libc_icdb_close" ); |