dirmngr: Add basic libdns support
[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 #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
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
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
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) /* entrie htab 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
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 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
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 }