Line data Source code
1 : /* cdblib.c - all CDB library functions.
2 : *
3 : * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
4 : * Public domain.
5 : *
6 : * Taken from tinycdb-0.73 and merged into one file for easier
7 : * inclusion into Dirmngr. By Werner Koch <wk@gnupg.org> 2003-12-12.
8 : */
9 :
10 : /* A cdb database is a single file used to map 'keys' to 'values',
11 : having records of (key,value) pairs. File consists of 3 parts: toc
12 : (table of contents), data and index (hash tables).
13 :
14 : Toc has fixed length of 2048 bytes, containing 256 pointers to hash
15 : tables inside index sections. Every pointer consists of position
16 : of a hash table in bytes from the beginning of a file, and a size
17 : of a hash table in entries, both are 4-bytes (32 bits) unsigned
18 : integers in little-endian form. Hash table length may have zero
19 : length, meaning that corresponding hash table is empty.
20 :
21 : Right after toc section, data section follows without any
22 : alingment. It consists of series of records, each is a key length,
23 : value (data) length, key and value. Again, key and value length
24 : are 4-byte unsigned integers. Each next record follows previous
25 : without any special alignment.
26 :
27 : After data section, index (hash tables) section follows. It should
28 : be looked to in conjunction with toc section, where each of max 256
29 : hash tables are defined. Index section consists of series of hash
30 : tables, with starting position and length defined in toc section.
31 : Every hash table is a sequence of records each holds two numbers:
32 : key's hash value and record position inside data section (bytes
33 : from the beginning of a file to first byte of key length starting
34 : data record). If record position is zero, then this is an empty
35 : hash table slot, pointed to nowhere.
36 :
37 : CDB hash function is
38 : hv = ((hv << 5) + hv) ^ c
39 : for every single c byte of a key, starting with hv = 5381.
40 :
41 : Toc section indexed by (hv % 256), i.e. hash value modulo 256
42 : (number of entries in toc section).
43 :
44 : In order to find a record, one should: first, compute the hash
45 : value (hv) of a key. Second, look to hash table number hv modulo
46 : 256. If it is empty, then there is no such key exists. If it is
47 : not empty, then third, loop by slots inside that hash table,
48 : starting from slot with number hv divided by 256 modulo length of
49 : that table, or ((hv / 256) % htlen), searching for this hv in hash
50 : table. Stop search on empty slot (if record position is zero) or
51 : when all slots was probed (note cyclic search, jumping from end to
52 : beginning of a table). When hash value in question is found in
53 : hash table, look to key of corresponding record, comparing it with
54 : key in question. If them of the same length and equals to each
55 : other, then record is found, overwise, repeat with next hash table
56 : slot. Note that there may be several records with the same key.
57 : */
58 :
59 : #ifdef HAVE_CONFIG_H
60 : #include <config.h>
61 : #endif
62 : #include <stdlib.h>
63 : #include <errno.h>
64 : #include <string.h>
65 : #include <unistd.h>
66 : #include <sys/types.h>
67 : #ifdef _WIN32
68 : # include <windows.h>
69 : #else
70 : # include <sys/mman.h>
71 : # ifndef MAP_FAILED
72 : # define MAP_FAILED ((void*)-1)
73 : # endif
74 : #endif
75 : #include <sys/stat.h>
76 :
77 : #include "dirmngr-err.h"
78 : #include "cdb.h"
79 :
80 : #ifndef EPROTO
81 : # define EPROTO EINVAL
82 : #endif
83 : #ifndef SEEK_SET
84 : # define SEEK_SET 0
85 : #endif
86 :
87 :
88 : struct cdb_rec {
89 : cdbi_t hval;
90 : cdbi_t rpos;
91 : };
92 :
93 : struct cdb_rl {
94 : struct cdb_rl *next;
95 : cdbi_t cnt;
96 : struct cdb_rec rec[254];
97 : };
98 :
99 : static int make_find(struct cdb_make *cdbmp,
100 : const void *key, cdbi_t klen, cdbi_t hval,
101 : struct cdb_rl **rlp);
102 : static int make_write(struct cdb_make *cdbmp,
103 : const char *ptr, cdbi_t len);
104 :
105 :
106 :
107 : /* Initializes structure given by CDBP pointer and associates it with
108 : the open file descriptor FD. Allocate memory for the structure
109 : itself if needed and file open operation should be done by
110 : application. File FD should be opened at least read-only, and
111 : should be seekable. Routine returns 0 on success or negative value
112 : on error. */
113 : int
114 0 : cdb_init(struct cdb *cdbp, int fd)
115 : {
116 : struct stat st;
117 : unsigned char *mem;
118 : #ifdef _WIN32
119 : HANDLE hFile, hMapping;
120 : #else
121 : unsigned int fsize;
122 : #endif
123 :
124 : /* get file size */
125 0 : if (fstat(fd, &st) < 0)
126 0 : return -1;
127 : /* trivial sanity check: at least toc should be here */
128 0 : if (st.st_size < 2048) {
129 0 : gpg_err_set_errno (EPROTO);
130 0 : return -1;
131 : }
132 : /* memory-map file */
133 : #ifdef _WIN32
134 : # ifdef __MINGW32CE__
135 : hFile = fd;
136 : # else
137 : hFile = (HANDLE) _get_osfhandle(fd);
138 : # endif
139 : if (hFile == (HANDLE) -1)
140 : return -1;
141 : hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
142 : if (!hMapping)
143 : return -1;
144 : mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
145 : if (!mem)
146 : return -1;
147 : cdbp->cdb_mapping = hMapping;
148 : #else /*!_WIN32*/
149 0 : fsize = (unsigned int)(st.st_size & 0xffffffffu);
150 0 : mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
151 0 : if (mem == MAP_FAILED)
152 0 : return -1;
153 : #endif /*!_WIN32*/
154 :
155 0 : cdbp->cdb_fd = fd;
156 0 : cdbp->cdb_fsize = st.st_size;
157 0 : cdbp->cdb_mem = mem;
158 :
159 : #if 0
160 : /* XXX don't know well about madvise syscall -- is it legal
161 : to set different options for parts of one mmap() region?
162 : There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc...
163 : */
164 : #ifdef MADV_RANDOM
165 : /* set madvise() parameters. Ignore errors for now if system
166 : doesn't support it */
167 : madvise(mem, 2048, MADV_WILLNEED);
168 : madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM);
169 : #endif
170 : #endif
171 :
172 0 : cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
173 :
174 0 : return 0;
175 : }
176 :
177 :
178 : /* Frees the internal resources held by structure. Note that this
179 : routine does not close the file. */
180 : void
181 0 : cdb_free(struct cdb *cdbp)
182 : {
183 0 : if (cdbp->cdb_mem) {
184 : #ifdef _WIN32
185 : UnmapViewOfFile ((void*) cdbp->cdb_mem);
186 : CloseHandle (cdbp->cdb_mapping);
187 : cdbp->cdb_mapping = NULL;
188 : #else
189 0 : munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
190 : #endif /* _WIN32 */
191 0 : cdbp->cdb_mem = NULL;
192 : }
193 0 : cdbp->cdb_fsize = 0;
194 0 : }
195 :
196 :
197 : /* Read data from cdb file, starting at position pos of length len,
198 : placing result to buf. This routine may be used to get actual
199 : value found by cdb_find() or other routines that returns position
200 : and length of a data. Returns 0 on success or negative value on
201 : error. */
202 : int
203 0 : cdb_read(const struct cdb *cdbp, void *buf, unsigned len, cdbi_t pos)
204 : {
205 0 : if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) {
206 0 : gpg_err_set_errno (EPROTO);
207 0 : return -1;
208 : }
209 0 : memcpy(buf, cdbp->cdb_mem + pos, len);
210 0 : return 0;
211 : }
212 :
213 :
214 : /* Attempts to find a key given by (key,klen) parameters. If key
215 : exists in database, routine returns 1 and places position and
216 : length of value associated with this key to internal fields inside
217 : cdbp structure, to be accessible by cdb_datapos() and
218 : cdb_datalen(). If key is not in database, routines returns 0. On
219 : error, negative value is returned. Note that using cdb_find() it
220 : is possible to lookup only first record with a given key. */
221 : int
222 0 : cdb_find(struct cdb *cdbp, const void *key, cdbi_t klen)
223 : {
224 : const unsigned char *htp; /* hash table pointer */
225 : const unsigned char *htab; /* hash table */
226 : const unsigned char *htend; /* end of hash table */
227 : cdbi_t httodo; /* ht bytes left to look */
228 : cdbi_t pos, n;
229 :
230 : cdbi_t hval;
231 :
232 0 : if (klen > cdbp->cdb_fsize) /* if key size is larger than file */
233 0 : return 0;
234 :
235 0 : hval = cdb_hash(key, klen);
236 :
237 : /* find (pos,n) hash table to use */
238 : /* first 2048 bytes (toc) are always available */
239 : /* (hval % 256) * 8 */
240 0 : htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
241 0 : n = cdb_unpack(htp + 4); /* table size */
242 0 : if (!n) /* empty table */
243 0 : return 0; /* not found */
244 0 : httodo = n << 3; /* bytes of htab to lookup */
245 0 : pos = cdb_unpack(htp); /* htab position */
246 0 : if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
247 0 : || pos > cdbp->cdb_fsize /* htab start within file ? */
248 0 : || httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
249 : {
250 0 : gpg_err_set_errno (EPROTO);
251 0 : return -1;
252 : }
253 :
254 0 : htab = cdbp->cdb_mem + pos; /* htab pointer */
255 0 : htend = htab + httodo; /* after end of htab */
256 : /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
257 0 : htp = htab + (((hval >> 8) % n) << 3);
258 :
259 : for(;;) {
260 0 : pos = cdb_unpack(htp + 4); /* record position */
261 0 : if (!pos)
262 0 : return 0;
263 0 : if (cdb_unpack(htp) == hval) {
264 0 : if (pos > cdbp->cdb_fsize - 8) { /* key+val lengths */
265 0 : gpg_err_set_errno (EPROTO);
266 0 : return -1;
267 : }
268 0 : if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
269 0 : if (cdbp->cdb_fsize - klen < pos + 8) {
270 0 : gpg_err_set_errno (EPROTO);
271 0 : return -1;
272 : }
273 0 : if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
274 0 : n = cdb_unpack(cdbp->cdb_mem + pos + 4);
275 0 : pos += 8 + klen;
276 0 : if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
277 0 : gpg_err_set_errno (EPROTO);
278 0 : return -1;
279 : }
280 0 : cdbp->cdb_vpos = pos;
281 0 : cdbp->cdb_vlen = n;
282 0 : return 1;
283 : }
284 : }
285 : }
286 0 : httodo -= 8;
287 0 : if (!httodo)
288 0 : return 0;
289 0 : if ((htp += 8) >= htend)
290 0 : htp = htab;
291 0 : }
292 :
293 : }
294 :
295 :
296 :
297 : /* Sequential-find routines that used separate structure. It is
298 : possible to have many than one record with the same key in a
299 : database, and these routines allow enumeration of all of them.
300 : cdb_findinit() initializes search structure pointed to by cdbfp.
301 : It will return negative value on error or 0 on success.
302 : cdb_findnext() attempts to find next matching key, setting value
303 : position and length in cdbfp structure. It will return positive
304 : value if given key was found, 0 if there is no more such key(s), or
305 : negative value on error. To access value position and length after
306 : successeful call to cdb_findnext() (when it returned positive
307 : result), use cdb_datapos() and cdb_datalen() macros with cdbp
308 : pointer. It is error to use cdb_findnext() after it returned 0 or
309 : error condition. These routines is a bit slower than cdb_find().
310 :
311 : Setting KEY to NULL will start a sequential search through the
312 : entire DB.
313 : */
314 : int
315 0 : cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
316 : const void *key, cdbi_t klen)
317 : {
318 : cdbi_t n, pos;
319 :
320 0 : cdbfp->cdb_cdbp = cdbp;
321 0 : cdbfp->cdb_key = key;
322 0 : cdbfp->cdb_klen = klen;
323 0 : cdbfp->cdb_hval = key? cdb_hash(key, klen) : 0;
324 :
325 0 : if (key)
326 : {
327 0 : cdbfp->cdb_htp = cdbp->cdb_mem + ((cdbfp->cdb_hval << 3) & 2047);
328 0 : n = cdb_unpack(cdbfp->cdb_htp + 4);
329 0 : cdbfp->cdb_httodo = n << 3; /* Set to size of hash table. */
330 0 : if (!n)
331 0 : return 0; /* The hash table is empry. */
332 0 : pos = cdb_unpack(cdbfp->cdb_htp);
333 0 : if (n > (cdbp->cdb_fsize >> 3)
334 0 : || pos > cdbp->cdb_fsize
335 0 : || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
336 : {
337 0 : gpg_err_set_errno (EPROTO);
338 0 : return -1;
339 : }
340 :
341 0 : cdbfp->cdb_htab = cdbp->cdb_mem + pos;
342 0 : cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
343 0 : cdbfp->cdb_htp = cdbfp->cdb_htab + (((cdbfp->cdb_hval >> 8) % n) << 3);
344 : }
345 : else /* Walk over all entries. */
346 : {
347 0 : cdbfp->cdb_hval = 0;
348 : /* Force stepping in findnext. */
349 0 : cdbfp->cdb_htp = cdbfp->cdb_htend = cdbp->cdb_mem;
350 : }
351 0 : return 0;
352 : }
353 :
354 :
355 : /* See cdb_findinit. */
356 : int
357 0 : cdb_findnext(struct cdb_find *cdbfp)
358 : {
359 : cdbi_t pos, n;
360 0 : struct cdb *cdbp = cdbfp->cdb_cdbp;
361 :
362 0 : if (cdbfp->cdb_key)
363 : {
364 0 : while(cdbfp->cdb_httodo) {
365 0 : pos = cdb_unpack(cdbfp->cdb_htp + 4);
366 0 : if (!pos)
367 0 : return 0;
368 0 : n = cdb_unpack(cdbfp->cdb_htp) == cdbfp->cdb_hval;
369 0 : if ((cdbfp->cdb_htp += 8) >= cdbfp->cdb_htend)
370 0 : cdbfp->cdb_htp = cdbfp->cdb_htab;
371 0 : cdbfp->cdb_httodo -= 8;
372 0 : if (n) {
373 0 : if (pos > cdbp->cdb_fsize - 8) {
374 0 : gpg_err_set_errno (EPROTO);
375 0 : return -1;
376 : }
377 0 : if (cdb_unpack(cdbp->cdb_mem + pos) == cdbfp->cdb_klen) {
378 0 : if (cdbp->cdb_fsize - cdbfp->cdb_klen < pos + 8) {
379 0 : gpg_err_set_errno (EPROTO);
380 0 : return -1;
381 : }
382 0 : if (memcmp(cdbfp->cdb_key,
383 0 : cdbp->cdb_mem + pos + 8, cdbfp->cdb_klen) == 0) {
384 0 : n = cdb_unpack(cdbp->cdb_mem + pos + 4);
385 0 : pos += 8 + cdbfp->cdb_klen;
386 0 : if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
387 0 : gpg_err_set_errno (EPROTO);
388 0 : return -1;
389 : }
390 0 : cdbp->cdb_vpos = pos;
391 0 : cdbp->cdb_vlen = n;
392 0 : return 1;
393 : }
394 : }
395 : }
396 : }
397 : }
398 : else /* Walk over all entries. */
399 : {
400 : do
401 : {
402 0 : while (cdbfp->cdb_htp >= cdbfp->cdb_htend)
403 : {
404 0 : if (cdbfp->cdb_hval > 255)
405 0 : return 0; /* No more items. */
406 :
407 0 : cdbfp->cdb_htp = cdbp->cdb_mem + cdbfp->cdb_hval * 8;
408 0 : cdbfp->cdb_hval++; /* Advance for next round. */
409 0 : pos = cdb_unpack (cdbfp->cdb_htp); /* Offset of table. */
410 0 : n = cdb_unpack (cdbfp->cdb_htp + 4); /* Number of entries. */
411 0 : cdbfp->cdb_httodo = n * 8; /* Size of table. */
412 0 : if (n > (cdbp->cdb_fsize / 8)
413 0 : || pos > cdbp->cdb_fsize
414 0 : || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
415 : {
416 0 : gpg_err_set_errno (EPROTO);
417 0 : return -1;
418 : }
419 :
420 0 : cdbfp->cdb_htab = cdbp->cdb_mem + pos;
421 0 : cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
422 0 : cdbfp->cdb_htp = cdbfp->cdb_htab;
423 : }
424 :
425 0 : pos = cdb_unpack (cdbfp->cdb_htp + 4); /* Offset of record. */
426 0 : cdbfp->cdb_htp += 8;
427 : }
428 0 : while (!pos);
429 0 : if (pos > cdbp->cdb_fsize - 8)
430 : {
431 0 : gpg_err_set_errno (EPROTO);
432 0 : return -1;
433 : }
434 :
435 0 : cdbp->cdb_kpos = pos + 8;
436 0 : cdbp->cdb_klen = cdb_unpack(cdbp->cdb_mem + pos);
437 0 : cdbp->cdb_vpos = pos + 8 + cdbp->cdb_klen;
438 0 : cdbp->cdb_vlen = cdb_unpack(cdbp->cdb_mem + pos + 4);
439 0 : n = 8 + cdbp->cdb_klen + cdbp->cdb_vlen;
440 0 : if ( pos > cdbp->cdb_fsize || pos > cdbp->cdb_fsize - n)
441 : {
442 0 : gpg_err_set_errno (EPROTO);
443 0 : return -1;
444 : }
445 0 : return 1; /* Found. */
446 : }
447 0 : return 0;
448 : }
449 :
450 : /* Read a chunk from file, ignoring interrupts (EINTR) */
451 : int
452 0 : cdb_bread(int fd, void *buf, int len)
453 : {
454 : int l;
455 0 : while(len > 0) {
456 0 : do l = read(fd, buf, len);
457 0 : while(l < 0 && errno == EINTR);
458 0 : if (l <= 0) {
459 0 : if (!l)
460 0 : gpg_err_set_errno (EIO);
461 0 : return -1;
462 : }
463 0 : buf = (char*)buf + l;
464 0 : len -= l;
465 : }
466 0 : return 0;
467 : }
468 :
469 : /* Find a given key in cdb file, seek a file pointer to it's value and
470 : place data length to *dlenp. */
471 : int
472 0 : cdb_seek(int fd, const void *key, unsigned klen, cdbi_t *dlenp)
473 : {
474 : cdbi_t htstart; /* hash table start position */
475 : cdbi_t htsize; /* number of elements in a hash table */
476 : cdbi_t httodo; /* hash table elements left to look */
477 : cdbi_t hti; /* hash table index */
478 : cdbi_t pos; /* position in a file */
479 : cdbi_t hval; /* key's hash value */
480 : unsigned char rbuf[64]; /* read buffer */
481 0 : int needseek = 1; /* if we should seek to a hash slot */
482 :
483 0 : hval = cdb_hash(key, klen);
484 0 : pos = (hval & 0xff) << 3; /* position in TOC */
485 : /* read the hash table parameters */
486 0 : if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
487 0 : return -1;
488 0 : if ((htsize = cdb_unpack(rbuf + 4)) == 0)
489 0 : return 0;
490 0 : hti = (hval >> 8) % htsize; /* start position in hash table */
491 0 : httodo = htsize;
492 0 : htstart = cdb_unpack(rbuf);
493 :
494 : for(;;) {
495 0 : if (needseek && lseek(fd, htstart + (hti << 3), SEEK_SET) < 0)
496 0 : return -1;
497 0 : if (cdb_bread(fd, rbuf, 8) < 0)
498 0 : return -1;
499 0 : if ((pos = cdb_unpack(rbuf + 4)) == 0) /* not found */
500 0 : return 0;
501 :
502 0 : if (cdb_unpack(rbuf) != hval) /* hash value not matched */
503 0 : needseek = 0;
504 : else { /* hash value matched */
505 0 : if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
506 0 : return -1;
507 0 : if (cdb_unpack(rbuf) == klen) { /* key length matches */
508 : /* read the key from file and compare with wanted */
509 0 : cdbi_t l = klen, c;
510 0 : const char *k = (const char*)key;
511 0 : if (*dlenp)
512 0 : *dlenp = cdb_unpack(rbuf + 4); /* save value length */
513 : for(;;) {
514 0 : if (!l) /* the whole key read and matches, return */
515 0 : return 1;
516 0 : c = l > sizeof(rbuf) ? sizeof(rbuf) : l;
517 0 : if (cdb_bread(fd, rbuf, c) < 0)
518 0 : return -1;
519 0 : if (memcmp(rbuf, k, c) != 0) /* no, it differs, stop here */
520 0 : break;
521 0 : k += c; l -= c;
522 0 : }
523 : }
524 0 : needseek = 1; /* we're looked to other place, should seek back */
525 : }
526 0 : if (!--httodo)
527 0 : return 0;
528 0 : if (++hti == htsize) {
529 0 : hti = htstart;
530 0 : needseek = 1;
531 : }
532 0 : }
533 : }
534 :
535 : cdbi_t
536 0 : cdb_unpack(const unsigned char buf[4])
537 : {
538 0 : cdbi_t n = buf[3];
539 0 : n <<= 8; n |= buf[2];
540 0 : n <<= 8; n |= buf[1];
541 0 : n <<= 8; n |= buf[0];
542 0 : return n;
543 : }
544 :
545 : /* Add record with key (KEY,KLEN) and value (VAL,VLEN) to a database.
546 : Returns 0 on success or negative value on error. Note that this
547 : routine does not checks if given key already exists, but cdb_find()
548 : will not see second record with the same key. It is not possible
549 : to continue building a database if cdb_make_add() returned an error
550 : indicator. */
551 : int
552 0 : cdb_make_add(struct cdb_make *cdbmp,
553 : const void *key, cdbi_t klen,
554 : const void *val, cdbi_t vlen)
555 : {
556 : unsigned char rlen[8];
557 : cdbi_t hval;
558 : struct cdb_rl *rl;
559 0 : if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
560 0 : vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
561 0 : gpg_err_set_errno (ENOMEM);
562 0 : return -1;
563 : }
564 0 : hval = cdb_hash(key, klen);
565 0 : rl = cdbmp->cdb_rec[hval&255];
566 0 : if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
567 0 : rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
568 0 : if (!rl) {
569 0 : gpg_err_set_errno (ENOMEM);
570 0 : return -1;
571 : }
572 0 : rl->cnt = 0;
573 0 : rl->next = cdbmp->cdb_rec[hval&255];
574 0 : cdbmp->cdb_rec[hval&255] = rl;
575 : }
576 0 : rl->rec[rl->cnt].hval = hval;
577 0 : rl->rec[rl->cnt].rpos = cdbmp->cdb_dpos;
578 0 : ++rl->cnt;
579 0 : ++cdbmp->cdb_rcnt;
580 0 : cdb_pack(klen, rlen);
581 0 : cdb_pack(vlen, rlen + 4);
582 0 : if (make_write(cdbmp, rlen, 8) < 0 ||
583 0 : make_write(cdbmp, key, klen) < 0 ||
584 0 : make_write(cdbmp, val, vlen) < 0)
585 0 : return -1;
586 0 : return 0;
587 : }
588 :
589 : int
590 0 : cdb_make_put(struct cdb_make *cdbmp,
591 : const void *key, cdbi_t klen,
592 : const void *val, cdbi_t vlen,
593 : int flags)
594 : {
595 : unsigned char rlen[8];
596 0 : cdbi_t hval = cdb_hash(key, klen);
597 : struct cdb_rl *rl;
598 : int c, r;
599 :
600 0 : switch(flags) {
601 : case CDB_PUT_REPLACE:
602 : case CDB_PUT_INSERT:
603 : case CDB_PUT_WARN:
604 0 : c = make_find(cdbmp, key, klen, hval, &rl);
605 0 : if (c < 0)
606 0 : return -1;
607 0 : if (c) {
608 0 : if (flags == CDB_PUT_INSERT) {
609 0 : gpg_err_set_errno (EEXIST);
610 0 : return 1;
611 : }
612 0 : else if (flags == CDB_PUT_REPLACE) {
613 0 : --c;
614 0 : r = 1;
615 0 : break;
616 : }
617 : else
618 0 : r = 1;
619 : }
620 : /* fall */
621 :
622 : case CDB_PUT_ADD:
623 0 : rl = cdbmp->cdb_rec[hval&255];
624 0 : if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
625 0 : rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
626 0 : if (!rl) {
627 0 : gpg_err_set_errno (ENOMEM);
628 0 : return -1;
629 : }
630 0 : rl->cnt = 0;
631 0 : rl->next = cdbmp->cdb_rec[hval&255];
632 0 : cdbmp->cdb_rec[hval&255] = rl;
633 : }
634 0 : c = rl->cnt;
635 0 : r = 0;
636 0 : break;
637 :
638 : default:
639 0 : gpg_err_set_errno (EINVAL);
640 0 : return -1;
641 : }
642 :
643 0 : if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
644 0 : vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
645 0 : gpg_err_set_errno (ENOMEM);
646 0 : return -1;
647 : }
648 0 : rl->rec[c].hval = hval;
649 0 : rl->rec[c].rpos = cdbmp->cdb_dpos;
650 0 : if (c == rl->cnt) {
651 0 : ++rl->cnt;
652 0 : ++cdbmp->cdb_rcnt;
653 : }
654 0 : cdb_pack(klen, rlen);
655 0 : cdb_pack(vlen, rlen + 4);
656 0 : if (make_write(cdbmp, rlen, 8) < 0 ||
657 0 : make_write(cdbmp, key, klen) < 0 ||
658 0 : make_write(cdbmp, val, vlen) < 0)
659 0 : return -1;
660 0 : return r;
661 : }
662 :
663 :
664 : static int
665 0 : match(int fd, cdbi_t pos, const char *key, cdbi_t klen)
666 : {
667 : unsigned char buf[64]; /*XXX cdb_buf may be used here instead */
668 0 : if (lseek(fd, pos, SEEK_SET) < 0 || read(fd, buf, 8) != 8)
669 0 : return -1;
670 0 : if (cdb_unpack(buf) != klen)
671 0 : return 0;
672 :
673 0 : while(klen > sizeof(buf)) {
674 0 : if (read(fd, buf, sizeof(buf)) != sizeof(buf))
675 0 : return -1;
676 0 : if (memcmp(buf, key, sizeof(buf)) != 0)
677 0 : return 0;
678 0 : key += sizeof(buf);
679 0 : klen -= sizeof(buf);
680 : }
681 0 : if (klen) {
682 0 : if (read(fd, buf, klen) != klen)
683 0 : return -1;
684 0 : if (memcmp(buf, key, klen) != 0)
685 0 : return 0;
686 : }
687 0 : return 1;
688 : }
689 :
690 :
691 : static int
692 0 : make_find (struct cdb_make *cdbmp,
693 : const void *key, cdbi_t klen, cdbi_t hval,
694 : struct cdb_rl **rlp)
695 : {
696 0 : struct cdb_rl *rl = cdbmp->cdb_rec[hval&255];
697 : int r, i;
698 0 : int sought = 0;
699 0 : while(rl) {
700 0 : for(i = rl->cnt - 1; i >= 0; --i) { /* search backward */
701 0 : if (rl->rec[i].hval != hval)
702 0 : continue;
703 : /*XXX this explicit flush may be unnecessary having
704 : * smarter match() that looks to cdb_buf too, but
705 : * most of a time here spent in finding hash values
706 : * (above), not keys */
707 0 : if (cdbmp->cdb_bpos != cdbmp->cdb_buf) {
708 0 : if (write(cdbmp->cdb_fd, cdbmp->cdb_buf,
709 0 : cdbmp->cdb_bpos - cdbmp->cdb_buf) < 0)
710 0 : return -1;
711 0 : cdbmp->cdb_bpos = cdbmp->cdb_buf;
712 : }
713 0 : sought = 1;
714 0 : r = match(cdbmp->cdb_fd, rl->rec[i].rpos, key, klen);
715 0 : if (!r)
716 0 : continue;
717 0 : if (r < 0)
718 0 : return -1;
719 0 : if (lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
720 0 : return -1;
721 0 : if (rlp)
722 0 : *rlp = rl;
723 0 : return i + 1;
724 : }
725 0 : rl = rl->next;
726 : }
727 0 : if (sought && lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
728 0 : return -1;
729 0 : return 0;
730 : }
731 :
732 : int
733 0 : cdb_make_exists(struct cdb_make *cdbmp,
734 : const void *key, cdbi_t klen)
735 : {
736 0 : return make_find(cdbmp, key, klen, cdb_hash(key, klen), NULL);
737 : }
738 :
739 :
740 : void
741 0 : cdb_pack(cdbi_t num, unsigned char buf[4])
742 : {
743 0 : buf[0] = num & 255; num >>= 8;
744 0 : buf[1] = num & 255; num >>= 8;
745 0 : buf[2] = num & 255;
746 0 : buf[3] = num >> 8;
747 0 : }
748 :
749 :
750 : /* Initializes structure to create a database. File FD should be
751 : opened read-write and should be seekable. Returns 0 on success or
752 : negative value on error. */
753 : int
754 0 : cdb_make_start(struct cdb_make *cdbmp, int fd)
755 : {
756 0 : memset (cdbmp, 0, sizeof *cdbmp);
757 0 : cdbmp->cdb_fd = fd;
758 0 : cdbmp->cdb_dpos = 2048;
759 0 : cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
760 0 : return 0;
761 : }
762 :
763 :
764 : static int
765 0 : ewrite(int fd, const char *buf, int len)
766 : {
767 0 : while(len) {
768 0 : int l = write(fd, buf, len);
769 0 : if (l < 0 && errno != EINTR)
770 0 : return -1;
771 0 : if (l > 0)
772 : {
773 0 : len -= l;
774 0 : buf += l;
775 : }
776 : }
777 0 : return 0;
778 : }
779 :
780 : static int
781 0 : make_write(struct cdb_make *cdbmp, const char *ptr, cdbi_t len)
782 : {
783 0 : cdbi_t l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
784 0 : cdbmp->cdb_dpos += len;
785 0 : if (len > l) {
786 0 : memcpy(cdbmp->cdb_bpos, ptr, l);
787 0 : if (ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf, sizeof(cdbmp->cdb_buf)) < 0)
788 0 : return -1;
789 0 : ptr += l; len -= l;
790 0 : l = len / sizeof(cdbmp->cdb_buf);
791 0 : if (l) {
792 0 : l *= sizeof(cdbmp->cdb_buf);
793 0 : if (ewrite(cdbmp->cdb_fd, ptr, l) < 0)
794 0 : return -1;
795 0 : ptr += l; len -= l;
796 : }
797 0 : cdbmp->cdb_bpos = cdbmp->cdb_buf;
798 : }
799 0 : if (len) {
800 0 : memcpy(cdbmp->cdb_bpos, ptr, len);
801 0 : cdbmp->cdb_bpos += len;
802 : }
803 0 : return 0;
804 : }
805 :
806 : static int
807 0 : cdb_make_finish_internal(struct cdb_make *cdbmp)
808 : {
809 : cdbi_t hcnt[256]; /* hash table counts */
810 : cdbi_t hpos[256]; /* hash table positions */
811 : struct cdb_rec *htab;
812 : unsigned char *p;
813 : struct cdb_rl *rl;
814 : cdbi_t hsize;
815 : unsigned t, i;
816 :
817 0 : if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) {
818 0 : gpg_err_set_errno (ENOMEM);
819 0 : return -1;
820 : }
821 :
822 : /* count htab sizes and reorder reclists */
823 0 : hsize = 0;
824 0 : for (t = 0; t < 256; ++t) {
825 0 : struct cdb_rl *rlt = NULL;
826 0 : i = 0;
827 0 : rl = cdbmp->cdb_rec[t];
828 0 : while(rl) {
829 0 : struct cdb_rl *rln = rl->next;
830 0 : rl->next = rlt;
831 0 : rlt = rl;
832 0 : i += rl->cnt;
833 0 : rl = rln;
834 : }
835 0 : cdbmp->cdb_rec[t] = rlt;
836 0 : if (hsize < (hcnt[t] = i << 1))
837 0 : hsize = hcnt[t];
838 : }
839 :
840 : /* allocate memory to hold max htable */
841 0 : htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
842 0 : if (!htab) {
843 0 : gpg_err_set_errno (ENOENT);
844 0 : return -1;
845 : }
846 0 : p = (unsigned char *)htab;
847 0 : htab += 2;
848 :
849 : /* build hash tables */
850 0 : for (t = 0; t < 256; ++t) {
851 : cdbi_t len, hi;
852 0 : hpos[t] = cdbmp->cdb_dpos;
853 0 : if ((len = hcnt[t]) == 0)
854 0 : continue;
855 0 : for (i = 0; i < len; ++i)
856 0 : htab[i].hval = htab[i].rpos = 0;
857 0 : for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
858 0 : for (i = 0; i < rl->cnt; ++i) {
859 0 : hi = (rl->rec[i].hval >> 8) % len;
860 0 : while(htab[hi].rpos)
861 0 : if (++hi == len)
862 0 : hi = 0;
863 0 : htab[hi] = rl->rec[i];
864 : }
865 0 : for (i = 0; i < len; ++i) {
866 0 : cdb_pack(htab[i].hval, p + (i << 3));
867 0 : cdb_pack(htab[i].rpos, p + (i << 3) + 4);
868 : }
869 0 : if (make_write(cdbmp, p, len << 3) < 0) {
870 0 : free(p);
871 0 : return -1;
872 : }
873 : }
874 0 : free(p);
875 0 : if (cdbmp->cdb_bpos != cdbmp->cdb_buf &&
876 0 : ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf,
877 0 : cdbmp->cdb_bpos - cdbmp->cdb_buf) != 0)
878 0 : return -1;
879 0 : p = cdbmp->cdb_buf;
880 0 : for (t = 0; t < 256; ++t) {
881 0 : cdb_pack(hpos[t], p + (t << 3));
882 0 : cdb_pack(hcnt[t], p + (t << 3) + 4);
883 : }
884 0 : if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
885 0 : ewrite(cdbmp->cdb_fd, p, 2048) != 0)
886 0 : return -1;
887 :
888 0 : return 0;
889 : }
890 :
891 : static void
892 0 : cdb_make_free(struct cdb_make *cdbmp)
893 : {
894 : unsigned t;
895 0 : for(t = 0; t < 256; ++t) {
896 0 : struct cdb_rl *rl = cdbmp->cdb_rec[t];
897 0 : while(rl) {
898 0 : struct cdb_rl *tm = rl;
899 0 : rl = rl->next;
900 0 : free(tm);
901 : }
902 : }
903 0 : }
904 :
905 :
906 :
907 : /* Finalizes database file, constructing all needed indexes, and frees
908 : memory structures. It does not close the file descriptor. Returns
909 : 0 on success or a negative value on error. */
910 : int
911 0 : cdb_make_finish(struct cdb_make *cdbmp)
912 : {
913 0 : int r = cdb_make_finish_internal(cdbmp);
914 0 : cdb_make_free(cdbmp);
915 0 : return r;
916 : }
917 :
918 :
919 : cdbi_t
920 0 : cdb_hash(const void *buf, cdbi_t len)
921 : {
922 0 : register const unsigned char *p = (const unsigned char *)buf;
923 0 : register const unsigned char *end = p + len;
924 0 : register cdbi_t hash = 5381; /* start value */
925 0 : while (p < end)
926 0 : hash = (hash + (hash << 5)) ^ *p++;
927 0 : return hash;
928 : }
|
