Adjust for signed integer passed to OpenPGP card decrypt.
[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   cdbp->cdb_mapping = hMapping;
148 #else
149   mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
150   if (mem == MAP_FAILED)
151     return -1;
152 #endif /* _WIN32 */
153
154   cdbp->cdb_fd = fd;
155   cdbp->cdb_fsize = st.st_size;
156   cdbp->cdb_mem = mem;
157
158 #if 0
159   /* XXX don't know well about madvise syscall -- is it legal
160      to set different options for parts of one mmap() region?
161      There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc...
162   */
163 #ifdef MADV_RANDOM
164   /* set madvise() parameters. Ignore errors for now if system
165      doesn't support it */
166   madvise(mem, 2048, MADV_WILLNEED);
167   madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM);
168 #endif
169 #endif
170
171   cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
172
173   return 0;
174 }
175
176
177 /* Frees the internal resources held by structure.  Note that this
178    routine does not close the file. */
179 void
180 cdb_free(struct cdb *cdbp)
181 {
182   if (cdbp->cdb_mem) {
183 #ifdef _WIN32
184     UnmapViewOfFile ((void*) cdbp->cdb_mem);
185     CloseHandle (cdbp->cdb_mapping);
186     cdbp->cdb_mapping = NULL;
187 #else
188     munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
189 #endif /* _WIN32 */
190     cdbp->cdb_mem = NULL;
191   }
192   cdbp->cdb_fsize = 0;
193 }
194
195
196 /* Read data from cdb file, starting at position pos of length len,
197    placing result to buf.  This routine may be used to get actual
198    value found by cdb_find() or other routines that returns position
199    and length of a data.  Returns 0 on success or negative value on
200    error. */
201 int
202 cdb_read(const struct cdb *cdbp, void *buf, unsigned len, cdbi_t pos)
203 {
204   if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) {
205     gpg_err_set_errno (EPROTO);
206     return -1;
207   }
208   memcpy(buf, cdbp->cdb_mem + pos, len);
209   return 0;
210 }
211
212
213 /* Attempts to find a key given by (key,klen) parameters.  If key
214    exists in database, routine returns 1 and places position and
215    length of value associated with this key to internal fields inside
216    cdbp structure, to be accessible by cdb_datapos() and
217    cdb_datalen().  If key is not in database, routines returns 0.  On
218    error, negative value is returned.  Note that using cdb_find() it
219    is possible to lookup only first record with a given key. */
220 int
221 cdb_find(struct cdb *cdbp, const void *key, cdbi_t klen)
222 {
223   const unsigned char *htp;     /* hash table pointer */
224   const unsigned char *htab;    /* hash table */
225   const unsigned char *htend;   /* end of hash table */
226   cdbi_t httodo;                /* ht bytes left to look */
227   cdbi_t pos, n;
228
229   cdbi_t hval;
230
231   if (klen > cdbp->cdb_fsize)   /* if key size is larger than file */
232     return 0;
233
234   hval = cdb_hash(key, klen);
235
236   /* find (pos,n) hash table to use */
237   /* first 2048 bytes (toc) are always available */
238   /* (hval % 256) * 8 */
239   htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
240   n = cdb_unpack(htp + 4);      /* table size */
241   if (!n)                       /* empty table */
242     return 0;                   /* not found */
243   httodo = n << 3;              /* bytes of htab to lookup */
244   pos = cdb_unpack(htp);        /* htab position */
245   if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
246       || pos > cdbp->cdb_fsize /* htab start within file ? */
247       || httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
248   {
249     gpg_err_set_errno (EPROTO);
250     return -1;
251   }
252
253   htab = cdbp->cdb_mem + pos;   /* htab pointer */
254   htend = htab + httodo;        /* after end of htab */
255   /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
256   htp = htab + (((hval >> 8) % n) << 3);
257
258   for(;;) {
259     pos = cdb_unpack(htp + 4);  /* record position */
260     if (!pos)
261       return 0;
262     if (cdb_unpack(htp) == hval) {
263       if (pos > cdbp->cdb_fsize - 8) { /* key+val lengths */
264         gpg_err_set_errno (EPROTO);
265         return -1;
266       }
267       if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
268         if (cdbp->cdb_fsize - klen < pos + 8) {
269           gpg_err_set_errno (EPROTO);
270           return -1;
271         }
272         if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
273           n = cdb_unpack(cdbp->cdb_mem + pos + 4);
274           pos += 8 + klen;
275           if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
276             gpg_err_set_errno (EPROTO);
277             return -1;
278           }
279           cdbp->cdb_vpos = pos;
280           cdbp->cdb_vlen = n;
281           return 1;
282         }
283       }
284     }
285     httodo -= 8;
286     if (!httodo)
287       return 0;
288     if ((htp += 8) >= htend)
289       htp = htab;
290   }
291
292 }
293
294
295
296 /* Sequential-find routines that used separate structure.  It is
297    possible to have many than one record with the same key in a
298    database, and these routines allows to enumerate all them.
299    cdb_findinit() initializes search structure pointed to by cdbfp.
300    It will return negative value on error or 0 on success.  cdb_findĀ­
301    next() attempts to find next matching key, setting value position
302    and length in cdbfp structure.  It will return positive value if
303    given key was found, 0 if there is no more such key(s), or negative
304    value on error.  To access value position and length after
305    successeful call to cdb_findnext() (when it returned positive
306    result), use cdb_datapos() and cdb_datalen() macros with cdbp
307    pointer.  It is error to use cdb_findnext() after it returned 0 or
308    error condition.  These routines is a bit slower than
309    cdb_find().
310
311    Setting KEY to NULL will start a sequential search through the
312    entire DB.
313 */
314 int
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
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
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
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
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
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
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 */
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
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
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 seeked = 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       seeked = 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 (seeked && lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
728     return -1;
729   return 0;
730 }
731
732 int
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
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
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
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
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
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
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
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
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 }