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 alignment. 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, otherwise, 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
cdb_init(struct cdb * cdbp,int fd)114 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 if (fstat(fd, &st) < 0)
126 return -1;
127 /* trivial sanity check: at least toc should be here */
128 if (st.st_size < 2048) {
129 gpg_err_set_errno (EPROTO);
130 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 fsize = (unsigned int)(st.st_size & 0xffffffffu);
150 mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
151 if (mem == MAP_FAILED)
152 return -1;
153 #endif /*!_WIN32*/
154
155 cdbp->cdb_fd = fd;
156 cdbp->cdb_fsize = st.st_size;
157 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 cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
173
174 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
cdb_free(struct cdb * cdbp)181 cdb_free(struct cdb *cdbp)
182 {
183 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 munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
190 #endif /* _WIN32 */
191 cdbp->cdb_mem = NULL;
192 }
193 cdbp->cdb_fsize = 0;
194 }
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
cdb_read(const struct cdb * cdbp,void * buf,unsigned len,cdbi_t pos)203 cdb_read(const struct cdb *cdbp, void *buf, unsigned len, cdbi_t pos)
204 {
205 if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) {
206 gpg_err_set_errno (EPROTO);
207 return -1;
208 }
209 memcpy(buf, cdbp->cdb_mem + pos, len);
210 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
cdb_find(struct cdb * cdbp,const void * key,cdbi_t klen)222 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 if (klen > cdbp->cdb_fsize) /* if key size is larger than file */
233 return 0;
234
235 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 htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
241 n = cdb_unpack(htp + 4); /* table size */
242 if (!n) /* empty table */
243 return 0; /* not found */
244 httodo = n << 3; /* bytes of htab to lookup */
245 pos = cdb_unpack(htp); /* htab position */
246 if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
247 || pos > cdbp->cdb_fsize /* htab start within file ? */
248 || httodo > cdbp->cdb_fsize - pos) /* htab entry within file ? */
249 {
250 gpg_err_set_errno (EPROTO);
251 return -1;
252 }
253
254 htab = cdbp->cdb_mem + pos; /* htab pointer */
255 htend = htab + httodo; /* after end of htab */
256 /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
257 htp = htab + (((hval >> 8) % n) << 3);
258
259 for(;;) {
260 pos = cdb_unpack(htp + 4); /* record position */
261 if (!pos)
262 return 0;
263 if (cdb_unpack(htp) == hval) {
264 if (pos > cdbp->cdb_fsize - 8) { /* key+val lengths */
265 gpg_err_set_errno (EPROTO);
266 return -1;
267 }
268 if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
269 if (cdbp->cdb_fsize - klen < pos + 8) {
270 gpg_err_set_errno (EPROTO);
271 return -1;
272 }
273 if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
274 n = cdb_unpack(cdbp->cdb_mem + pos + 4);
275 pos += 8 + klen;
276 if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
277 gpg_err_set_errno (EPROTO);
278 return -1;
279 }
280 cdbp->cdb_vpos = pos;
281 cdbp->cdb_vlen = n;
282 return 1;
283 }
284 }
285 }
286 httodo -= 8;
287 if (!httodo)
288 return 0;
289 if ((htp += 8) >= htend)
290 htp = htab;
291 }
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
cdb_findinit(struct cdb_find * cdbfp,struct cdb * cdbp,const void * key,cdbi_t klen)315 cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
316 const void *key, cdbi_t klen)
317 {
318 cdbi_t n, pos;
319
320 cdbfp->cdb_cdbp = cdbp;
321 cdbfp->cdb_key = key;
322 cdbfp->cdb_klen = klen;
323 cdbfp->cdb_hval = key? cdb_hash(key, klen) : 0;
324
325 if (key)
326 {
327 cdbfp->cdb_htp = cdbp->cdb_mem + ((cdbfp->cdb_hval << 3) & 2047);
328 n = cdb_unpack(cdbfp->cdb_htp + 4);
329 cdbfp->cdb_httodo = n << 3; /* Set to size of hash table. */
330 if (!n)
331 return 0; /* The hash table is empry. */
332 pos = cdb_unpack(cdbfp->cdb_htp);
333 if (n > (cdbp->cdb_fsize >> 3)
334 || pos > cdbp->cdb_fsize
335 || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
336 {
337 gpg_err_set_errno (EPROTO);
338 return -1;
339 }
340
341 cdbfp->cdb_htab = cdbp->cdb_mem + pos;
342 cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
343 cdbfp->cdb_htp = cdbfp->cdb_htab + (((cdbfp->cdb_hval >> 8) % n) << 3);
344 }
345 else /* Walk over all entries. */
346 {
347 cdbfp->cdb_hval = 0;
348 /* Force stepping in findnext. */
349 cdbfp->cdb_htp = cdbfp->cdb_htend = cdbp->cdb_mem;
350 }
351 return 0;
352 }
353
354
355 /* See cdb_findinit. */
356 int
cdb_findnext(struct cdb_find * cdbfp)357 cdb_findnext(struct cdb_find *cdbfp)
358 {
359 cdbi_t pos, n;
360 struct cdb *cdbp = cdbfp->cdb_cdbp;
361
362 if (cdbfp->cdb_key)
363 {
364 while(cdbfp->cdb_httodo) {
365 pos = cdb_unpack(cdbfp->cdb_htp + 4);
366 if (!pos)
367 return 0;
368 n = cdb_unpack(cdbfp->cdb_htp) == cdbfp->cdb_hval;
369 if ((cdbfp->cdb_htp += 8) >= cdbfp->cdb_htend)
370 cdbfp->cdb_htp = cdbfp->cdb_htab;
371 cdbfp->cdb_httodo -= 8;
372 if (n) {
373 if (pos > cdbp->cdb_fsize - 8) {
374 gpg_err_set_errno (EPROTO);
375 return -1;
376 }
377 if (cdb_unpack(cdbp->cdb_mem + pos) == cdbfp->cdb_klen) {
378 if (cdbp->cdb_fsize - cdbfp->cdb_klen < pos + 8) {
379 gpg_err_set_errno (EPROTO);
380 return -1;
381 }
382 if (memcmp(cdbfp->cdb_key,
383 cdbp->cdb_mem + pos + 8, cdbfp->cdb_klen) == 0) {
384 n = cdb_unpack(cdbp->cdb_mem + pos + 4);
385 pos += 8 + cdbfp->cdb_klen;
386 if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
387 gpg_err_set_errno (EPROTO);
388 return -1;
389 }
390 cdbp->cdb_vpos = pos;
391 cdbp->cdb_vlen = n;
392 return 1;
393 }
394 }
395 }
396 }
397 }
398 else /* Walk over all entries. */
399 {
400 do
401 {
402 while (cdbfp->cdb_htp >= cdbfp->cdb_htend)
403 {
404 if (cdbfp->cdb_hval > 255)
405 return 0; /* No more items. */
406
407 cdbfp->cdb_htp = cdbp->cdb_mem + cdbfp->cdb_hval * 8;
408 cdbfp->cdb_hval++; /* Advance for next round. */
409 pos = cdb_unpack (cdbfp->cdb_htp); /* Offset of table. */
410 n = cdb_unpack (cdbfp->cdb_htp + 4); /* Number of entries. */
411 cdbfp->cdb_httodo = n * 8; /* Size of table. */
412 if (n > (cdbp->cdb_fsize / 8)
413 || pos > cdbp->cdb_fsize
414 || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
415 {
416 gpg_err_set_errno (EPROTO);
417 return -1;
418 }
419
420 cdbfp->cdb_htab = cdbp->cdb_mem + pos;
421 cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
422 cdbfp->cdb_htp = cdbfp->cdb_htab;
423 }
424
425 pos = cdb_unpack (cdbfp->cdb_htp + 4); /* Offset of record. */
426 cdbfp->cdb_htp += 8;
427 }
428 while (!pos);
429 if (pos > cdbp->cdb_fsize - 8)
430 {
431 gpg_err_set_errno (EPROTO);
432 return -1;
433 }
434
435 cdbp->cdb_kpos = pos + 8;
436 cdbp->cdb_klen = cdb_unpack(cdbp->cdb_mem + pos);
437 cdbp->cdb_vpos = pos + 8 + cdbp->cdb_klen;
438 cdbp->cdb_vlen = cdb_unpack(cdbp->cdb_mem + pos + 4);
439 n = 8 + cdbp->cdb_klen + cdbp->cdb_vlen;
440 if ( pos > cdbp->cdb_fsize || pos > cdbp->cdb_fsize - n)
441 {
442 gpg_err_set_errno (EPROTO);
443 return -1;
444 }
445 return 1; /* Found. */
446 }
447 return 0;
448 }
449
450 /* Read a chunk from file, ignoring interrupts (EINTR) */
451 int
cdb_bread(int fd,void * buf,int len)452 cdb_bread(int fd, void *buf, int len)
453 {
454 int l;
455 while(len > 0) {
456 do l = read(fd, buf, len);
457 while(l < 0 && errno == EINTR);
458 if (l <= 0) {
459 if (!l)
460 gpg_err_set_errno (EIO);
461 return -1;
462 }
463 buf = (char*)buf + l;
464 len -= l;
465 }
466 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
cdb_seek(int fd,const void * key,unsigned klen,cdbi_t * dlenp)472 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 int needseek = 1; /* if we should seek to a hash slot */
482
483 hval = cdb_hash(key, klen);
484 pos = (hval & 0xff) << 3; /* position in TOC */
485 /* read the hash table parameters */
486 if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
487 return -1;
488 if ((htsize = cdb_unpack(rbuf + 4)) == 0)
489 return 0;
490 hti = (hval >> 8) % htsize; /* start position in hash table */
491 httodo = htsize;
492 htstart = cdb_unpack(rbuf);
493
494 for(;;) {
495 if (needseek && lseek(fd, htstart + (hti << 3), SEEK_SET) < 0)
496 return -1;
497 if (cdb_bread(fd, rbuf, 8) < 0)
498 return -1;
499 if ((pos = cdb_unpack(rbuf + 4)) == 0) /* not found */
500 return 0;
501
502 if (cdb_unpack(rbuf) != hval) /* hash value not matched */
503 needseek = 0;
504 else { /* hash value matched */
505 if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
506 return -1;
507 if (cdb_unpack(rbuf) == klen) { /* key length matches */
508 /* read the key from file and compare with wanted */
509 cdbi_t l = klen, c;
510 const char *k = (const char*)key;
511 if (*dlenp)
512 *dlenp = cdb_unpack(rbuf + 4); /* save value length */
513 for(;;) {
514 if (!l) /* the whole key read and matches, return */
515 return 1;
516 c = l > sizeof(rbuf) ? sizeof(rbuf) : l;
517 if (cdb_bread(fd, rbuf, c) < 0)
518 return -1;
519 if (memcmp(rbuf, k, c) != 0) /* no, it differs, stop here */
520 break;
521 k += c; l -= c;
522 }
523 }
524 needseek = 1; /* we're looked to other place, should seek back */
525 }
526 if (!--httodo)
527 return 0;
528 if (++hti == htsize) {
529 hti = htstart;
530 needseek = 1;
531 }
532 }
533 }
534
535 cdbi_t
cdb_unpack(const unsigned char buf[4])536 cdb_unpack(const unsigned char buf[4])
537 {
538 cdbi_t n = buf[3];
539 n <<= 8; n |= buf[2];
540 n <<= 8; n |= buf[1];
541 n <<= 8; n |= buf[0];
542 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
cdb_make_add(struct cdb_make * cdbmp,const void * key,cdbi_t klen,const void * val,cdbi_t vlen)552 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 if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
560 vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
561 gpg_err_set_errno (ENOMEM);
562 return -1;
563 }
564 hval = cdb_hash(key, klen);
565 rl = cdbmp->cdb_rec[hval&255];
566 if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
567 rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
568 if (!rl) {
569 gpg_err_set_errno (ENOMEM);
570 return -1;
571 }
572 rl->cnt = 0;
573 rl->next = cdbmp->cdb_rec[hval&255];
574 cdbmp->cdb_rec[hval&255] = rl;
575 }
576 rl->rec[rl->cnt].hval = hval;
577 rl->rec[rl->cnt].rpos = cdbmp->cdb_dpos;
578 ++rl->cnt;
579 ++cdbmp->cdb_rcnt;
580 cdb_pack(klen, rlen);
581 cdb_pack(vlen, rlen + 4);
582 if (make_write(cdbmp, rlen, 8) < 0 ||
583 make_write(cdbmp, key, klen) < 0 ||
584 make_write(cdbmp, val, vlen) < 0)
585 return -1;
586 return 0;
587 }
588
589 int
cdb_make_put(struct cdb_make * cdbmp,const void * key,cdbi_t klen,const void * val,cdbi_t vlen,int flags)590 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 cdbi_t hval = cdb_hash(key, klen);
597 struct cdb_rl *rl;
598 int c, r;
599
600 switch(flags) {
601 case CDB_PUT_REPLACE:
602 case CDB_PUT_INSERT:
603 case CDB_PUT_WARN:
604 c = make_find(cdbmp, key, klen, hval, &rl);
605 if (c < 0)
606 return -1;
607 if (c) {
608 if (flags == CDB_PUT_INSERT) {
609 gpg_err_set_errno (EEXIST);
610 return 1;
611 }
612 else if (flags == CDB_PUT_REPLACE) {
613 --c;
614 r = 1;
615 break;
616 }
617 else
618 r = 1;
619 }
620 /* fall through */
621
622 case CDB_PUT_ADD:
623 rl = cdbmp->cdb_rec[hval&255];
624 if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
625 rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
626 if (!rl) {
627 gpg_err_set_errno (ENOMEM);
628 return -1;
629 }
630 rl->cnt = 0;
631 rl->next = cdbmp->cdb_rec[hval&255];
632 cdbmp->cdb_rec[hval&255] = rl;
633 }
634 c = rl->cnt;
635 r = 0;
636 break;
637
638 default:
639 gpg_err_set_errno (EINVAL);
640 return -1;
641 }
642
643 if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
644 vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
645 gpg_err_set_errno (ENOMEM);
646 return -1;
647 }
648 rl->rec[c].hval = hval;
649 rl->rec[c].rpos = cdbmp->cdb_dpos;
650 if (c == rl->cnt) {
651 ++rl->cnt;
652 ++cdbmp->cdb_rcnt;
653 }
654 cdb_pack(klen, rlen);
655 cdb_pack(vlen, rlen + 4);
656 if (make_write(cdbmp, rlen, 8) < 0 ||
657 make_write(cdbmp, key, klen) < 0 ||
658 make_write(cdbmp, val, vlen) < 0)
659 return -1;
660 return r;
661 }
662
663
664 static int
match(int fd,cdbi_t pos,const char * key,cdbi_t klen)665 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 if (lseek(fd, pos, SEEK_SET) < 0 || read(fd, buf, 8) != 8)
669 return -1;
670 if (cdb_unpack(buf) != klen)
671 return 0;
672
673 while(klen > sizeof(buf)) {
674 if (read(fd, buf, sizeof(buf)) != sizeof(buf))
675 return -1;
676 if (memcmp(buf, key, sizeof(buf)) != 0)
677 return 0;
678 key += sizeof(buf);
679 klen -= sizeof(buf);
680 }
681 if (klen) {
682 if (read(fd, buf, klen) != klen)
683 return -1;
684 if (memcmp(buf, key, klen) != 0)
685 return 0;
686 }
687 return 1;
688 }
689
690
691 static int
make_find(struct cdb_make * cdbmp,const void * key,cdbi_t klen,cdbi_t hval,struct cdb_rl ** rlp)692 make_find (struct cdb_make *cdbmp,
693 const void *key, cdbi_t klen, cdbi_t hval,
694 struct cdb_rl **rlp)
695 {
696 struct cdb_rl *rl = cdbmp->cdb_rec[hval&255];
697 int r, i;
698 int sought = 0;
699 while(rl) {
700 for(i = rl->cnt - 1; i >= 0; --i) { /* search backward */
701 if (rl->rec[i].hval != hval)
702 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 if (cdbmp->cdb_bpos != cdbmp->cdb_buf) {
708 if (write(cdbmp->cdb_fd, cdbmp->cdb_buf,
709 cdbmp->cdb_bpos - cdbmp->cdb_buf) < 0)
710 return -1;
711 cdbmp->cdb_bpos = cdbmp->cdb_buf;
712 }
713 sought = 1;
714 r = match(cdbmp->cdb_fd, rl->rec[i].rpos, key, klen);
715 if (!r)
716 continue;
717 if (r < 0)
718 return -1;
719 if (lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
720 return -1;
721 if (rlp)
722 *rlp = rl;
723 return i + 1;
724 }
725 rl = rl->next;
726 }
727 if (sought && lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
728 return -1;
729 return 0;
730 }
731
732 int
cdb_make_exists(struct cdb_make * cdbmp,const void * key,cdbi_t klen)733 cdb_make_exists(struct cdb_make *cdbmp,
734 const void *key, cdbi_t klen)
735 {
736 return make_find(cdbmp, key, klen, cdb_hash(key, klen), NULL);
737 }
738
739
740 void
cdb_pack(cdbi_t num,unsigned char buf[4])741 cdb_pack(cdbi_t num, unsigned char buf[4])
742 {
743 buf[0] = num & 255; num >>= 8;
744 buf[1] = num & 255; num >>= 8;
745 buf[2] = num & 255;
746 buf[3] = num >> 8;
747 }
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
cdb_make_start(struct cdb_make * cdbmp,int fd)754 cdb_make_start(struct cdb_make *cdbmp, int fd)
755 {
756 memset (cdbmp, 0, sizeof *cdbmp);
757 cdbmp->cdb_fd = fd;
758 cdbmp->cdb_dpos = 2048;
759 cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
760 return 0;
761 }
762
763
764 static int
ewrite(int fd,const char * buf,int len)765 ewrite(int fd, const char *buf, int len)
766 {
767 while(len) {
768 int l = write(fd, buf, len);
769 if (l < 0 && errno != EINTR)
770 return -1;
771 if (l > 0)
772 {
773 len -= l;
774 buf += l;
775 }
776 }
777 return 0;
778 }
779
780 static int
make_write(struct cdb_make * cdbmp,const char * ptr,cdbi_t len)781 make_write(struct cdb_make *cdbmp, const char *ptr, cdbi_t len)
782 {
783 cdbi_t l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
784 cdbmp->cdb_dpos += len;
785 if (len > l) {
786 memcpy(cdbmp->cdb_bpos, ptr, l);
787 if (ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf, sizeof(cdbmp->cdb_buf)) < 0)
788 return -1;
789 ptr += l; len -= l;
790 l = len / sizeof(cdbmp->cdb_buf);
791 if (l) {
792 l *= sizeof(cdbmp->cdb_buf);
793 if (ewrite(cdbmp->cdb_fd, ptr, l) < 0)
794 return -1;
795 ptr += l; len -= l;
796 }
797 cdbmp->cdb_bpos = cdbmp->cdb_buf;
798 }
799 if (len) {
800 memcpy(cdbmp->cdb_bpos, ptr, len);
801 cdbmp->cdb_bpos += len;
802 }
803 return 0;
804 }
805
806 static int
cdb_make_finish_internal(struct cdb_make * cdbmp)807 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 if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) {
818 gpg_err_set_errno (ENOMEM);
819 return -1;
820 }
821
822 /* count htab sizes and reorder reclists */
823 hsize = 0;
824 for (t = 0; t < 256; ++t) {
825 struct cdb_rl *rlt = NULL;
826 i = 0;
827 rl = cdbmp->cdb_rec[t];
828 while(rl) {
829 struct cdb_rl *rln = rl->next;
830 rl->next = rlt;
831 rlt = rl;
832 i += rl->cnt;
833 rl = rln;
834 }
835 cdbmp->cdb_rec[t] = rlt;
836 if (hsize < (hcnt[t] = i << 1))
837 hsize = hcnt[t];
838 }
839
840 /* allocate memory to hold max htable */
841 htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
842 if (!htab) {
843 gpg_err_set_errno (ENOENT);
844 return -1;
845 }
846 p = (unsigned char *)htab;
847 htab += 2;
848
849 /* build hash tables */
850 for (t = 0; t < 256; ++t) {
851 cdbi_t len, hi;
852 hpos[t] = cdbmp->cdb_dpos;
853 if ((len = hcnt[t]) == 0)
854 continue;
855 for (i = 0; i < len; ++i)
856 htab[i].hval = htab[i].rpos = 0;
857 for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
858 for (i = 0; i < rl->cnt; ++i) {
859 hi = (rl->rec[i].hval >> 8) % len;
860 while(htab[hi].rpos)
861 if (++hi == len)
862 hi = 0;
863 htab[hi] = rl->rec[i];
864 }
865 for (i = 0; i < len; ++i) {
866 cdb_pack(htab[i].hval, p + (i << 3));
867 cdb_pack(htab[i].rpos, p + (i << 3) + 4);
868 }
869 if (make_write(cdbmp, p, len << 3) < 0) {
870 free(p);
871 return -1;
872 }
873 }
874 free(p);
875 if (cdbmp->cdb_bpos != cdbmp->cdb_buf &&
876 ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf,
877 cdbmp->cdb_bpos - cdbmp->cdb_buf) != 0)
878 return -1;
879 p = cdbmp->cdb_buf;
880 for (t = 0; t < 256; ++t) {
881 cdb_pack(hpos[t], p + (t << 3));
882 cdb_pack(hcnt[t], p + (t << 3) + 4);
883 }
884 if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
885 ewrite(cdbmp->cdb_fd, p, 2048) != 0)
886 return -1;
887
888 return 0;
889 }
890
891 static void
cdb_make_free(struct cdb_make * cdbmp)892 cdb_make_free(struct cdb_make *cdbmp)
893 {
894 unsigned t;
895 for(t = 0; t < 256; ++t) {
896 struct cdb_rl *rl = cdbmp->cdb_rec[t];
897 while(rl) {
898 struct cdb_rl *tm = rl;
899 rl = rl->next;
900 free(tm);
901 }
902 }
903 }
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
cdb_make_finish(struct cdb_make * cdbmp)911 cdb_make_finish(struct cdb_make *cdbmp)
912 {
913 int r = cdb_make_finish_internal(cdbmp);
914 cdb_make_free(cdbmp);
915 return r;
916 }
917
918
919 cdbi_t
cdb_hash(const void * buf,cdbi_t len)920 cdb_hash(const void *buf, cdbi_t len)
921 {
922 register const unsigned char *p = (const unsigned char *)buf;
923 register const unsigned char *end = p + len;
924 register cdbi_t hash = 5381; /* start value */
925 while (p < end)
926 hash = (hash + (hash << 5)) ^ *p++;
927 return hash;
928 }
929