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