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