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 allows to enumerate all them.
 300    cdb_findinit() initializes search structure pointed to by cdbfp.
 301    It will return negative value on error or 0 on success.  cdb_find
 302    next() attempts to find next matching key, setting value position
 303    and length in cdbfp structure.  It will return positive value if
 304    given key was found, 0 if there is no more such key(s), or negative
 305    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
 310    cdb_find().
 311
 312    Setting KEY to NULL will start a sequential search through the
 313    entire DB.
 314 */
 315 int
 316 cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
 317              const void *key, cdbi_t klen)
 318 {
 319   cdbi_t n, pos;
 320
 321   cdbfp->cdb_cdbp = cdbp;
 322   cdbfp->cdb_key  = key;
 323   cdbfp->cdb_klen = klen;
 324   cdbfp->cdb_hval = key? cdb_hash(key, klen) : 0;
 325
 326   if (key)
 327     {
 328       cdbfp->cdb_htp = cdbp->cdb_mem + ((cdbfp->cdb_hval << 3) & 2047);
 329       n = cdb_unpack(cdbfp->cdb_htp + 4);
 330       cdbfp->cdb_httodo = n << 3; /* Set to size of hash table. */
 331       if (!n)
 332         return 0; /* The hash table is empry. */
 333       pos = cdb_unpack(cdbfp->cdb_htp);
 334       if (n > (cdbp->cdb_fsize >> 3)
 335           || pos > cdbp->cdb_fsize
 336           || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
 337         {
 338           gpg_err_set_errno (EPROTO);
 339           return -1;
 340         }
 341
 342       cdbfp->cdb_htab = cdbp->cdb_mem + pos;
 343       cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
 344       cdbfp->cdb_htp = cdbfp->cdb_htab + (((cdbfp->cdb_hval >> 8) % n) << 3);
 345     }
 346   else /* Walk over all entries. */
 347     {
 348       cdbfp->cdb_hval = 0;
 349       /* Force stepping in findnext. */
 350       cdbfp->cdb_htp = cdbfp->cdb_htend = cdbp->cdb_mem;
 351     }
 352   return 0;
 353 }
 354
 355
 356 /* See cdb_findinit. */
 357 int
 358 cdb_findnext(struct cdb_find *cdbfp)
 359 {
 360   cdbi_t pos, n;
 361   struct cdb *cdbp = cdbfp->cdb_cdbp;
 362
 363   if (cdbfp->cdb_key)
 364     {
 365       while(cdbfp->cdb_httodo) {
 366         pos = cdb_unpack(cdbfp->cdb_htp + 4);
 367         if (!pos)
 368           return 0;
 369         n = cdb_unpack(cdbfp->cdb_htp) == cdbfp->cdb_hval;
 370         if ((cdbfp->cdb_htp += 8) >= cdbfp->cdb_htend)
 371           cdbfp->cdb_htp = cdbfp->cdb_htab;
 372         cdbfp->cdb_httodo -= 8;
 373         if (n) {
 374           if (pos > cdbp->cdb_fsize - 8) {
 375             gpg_err_set_errno (EPROTO);
 376             return -1;
 377           }
 378           if (cdb_unpack(cdbp->cdb_mem + pos) == cdbfp->cdb_klen) {
 379             if (cdbp->cdb_fsize - cdbfp->cdb_klen < pos + 8) {
 380               gpg_err_set_errno (EPROTO);
 381               return -1;
 382             }
 383             if (memcmp(cdbfp->cdb_key,
 384                        cdbp->cdb_mem + pos + 8, cdbfp->cdb_klen) == 0) {
 385               n = cdb_unpack(cdbp->cdb_mem + pos + 4);
 386               pos += 8 + cdbfp->cdb_klen;
 387               if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
 388                 gpg_err_set_errno (EPROTO);
 389                 return -1;
 390               }
 391               cdbp->cdb_vpos = pos;
 392               cdbp->cdb_vlen = n;
 393               return 1;
 394             }
 395           }
 396         }
 397       }
 398     }
 399   else /* Walk over all entries. */
 400     {
 401       do
 402         {
 403           while (cdbfp->cdb_htp >= cdbfp->cdb_htend)
 404             {
 405               if (cdbfp->cdb_hval > 255)
 406                 return 0; /* No more items. */
 407
 408               cdbfp->cdb_htp = cdbp->cdb_mem + cdbfp->cdb_hval * 8;
 409               cdbfp->cdb_hval++; /* Advance for next round. */
 410               pos = cdb_unpack (cdbfp->cdb_htp);     /* Offset of table. */
 411               n   = cdb_unpack (cdbfp->cdb_htp + 4); /* Number of entries. */
 412               cdbfp->cdb_httodo = n * 8;             /* Size of table. */
 413               if (n > (cdbp->cdb_fsize / 8)
 414                   || pos > cdbp->cdb_fsize
 415                   || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
 416                 {
 417                   gpg_err_set_errno (EPROTO);
 418                   return -1;
 419                 }
 420
 421               cdbfp->cdb_htab  = cdbp->cdb_mem + pos;
 422               cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
 423               cdbfp->cdb_htp   = cdbfp->cdb_htab;
 424             }
 425
 426           pos = cdb_unpack (cdbfp->cdb_htp + 4); /* Offset of record. */
 427           cdbfp->cdb_htp += 8;
 428         }
 429       while (!pos);
 430       if (pos > cdbp->cdb_fsize - 8)
 431         {
 432           gpg_err_set_errno (EPROTO);
 433           return -1;
 434         }
 435
 436       cdbp->cdb_kpos = pos + 8;
 437       cdbp->cdb_klen = cdb_unpack(cdbp->cdb_mem + pos);
 438       cdbp->cdb_vpos = pos + 8 + cdbp->cdb_klen;
 439       cdbp->cdb_vlen = cdb_unpack(cdbp->cdb_mem + pos + 4);
 440       n = 8 + cdbp->cdb_klen + cdbp->cdb_vlen;
 441       if ( pos > cdbp->cdb_fsize || pos > cdbp->cdb_fsize - n)
 442         {
 443           gpg_err_set_errno (EPROTO);
 444           return -1;
 445         }
 446       return 1; /* Found. */
 447     }
 448   return 0;
 449 }
 450
 451 /* Read a chunk from file, ignoring interrupts (EINTR) */
 452 int
 453 cdb_bread(int fd, void *buf, int len)
 454 {
 455   int l;
 456   while(len > 0) {
 457     do l = read(fd, buf, len);
 458     while(l < 0 && errno == EINTR);
 459     if (l <= 0) {
 460       if (!l)
 461         gpg_err_set_errno (EIO);
 462       return -1;
 463     }
 464     buf = (char*)buf + l;
 465     len -= l;
 466   }
 467   return 0;
 468 }
 469
 470 /* Find a given key in cdb file, seek a file pointer to it's value and
 471    place data length to *dlenp. */
 472 int
 473 cdb_seek(int fd, const void *key, unsigned klen, cdbi_t *dlenp)
 474 {
 475   cdbi_t htstart;               /* hash table start position */
 476   cdbi_t htsize;                /* number of elements in a hash table */
 477   cdbi_t httodo;                /* hash table elements left to look */
 478   cdbi_t hti;                   /* hash table index */
 479   cdbi_t pos;                   /* position in a file */
 480   cdbi_t hval;                  /* key's hash value */
 481   unsigned char rbuf[64];       /* read buffer */
 482   int needseek = 1;             /* if we should seek to a hash slot */
 483
 484   hval = cdb_hash(key, klen);
 485   pos = (hval & 0xff) << 3; /* position in TOC */
 486   /* read the hash table parameters */
 487   if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
 488     return -1;
 489   if ((htsize = cdb_unpack(rbuf + 4)) == 0)
 490     return 0;
 491   hti = (hval >> 8) % htsize;   /* start position in hash table */
 492   httodo = htsize;
 493   htstart = cdb_unpack(rbuf);
 494
 495   for(;;) {
 496     if (needseek && lseek(fd, htstart + (hti << 3), SEEK_SET) < 0)
 497       return -1;
 498     if (cdb_bread(fd, rbuf, 8) < 0)
 499       return -1;
 500     if ((pos = cdb_unpack(rbuf + 4)) == 0) /* not found */
 501       return 0;
 502
 503     if (cdb_unpack(rbuf) != hval) /* hash value not matched */
 504       needseek = 0;
 505     else { /* hash value matched */
 506       if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
 507         return -1;
 508       if (cdb_unpack(rbuf) == klen) { /* key length matches */
 509         /* read the key from file and compare with wanted */
 510         cdbi_t l = klen, c;
 511         const char *k = (const char*)key;
 512         if (*dlenp)
 513           *dlenp = cdb_unpack(rbuf + 4); /* save value length */
 514         for(;;) {
 515           if (!l) /* the whole key read and matches, return */
 516             return 1;
 517           c = l > sizeof(rbuf) ? sizeof(rbuf) : l;
 518           if (cdb_bread(fd, rbuf, c) < 0)
 519             return -1;
 520           if (memcmp(rbuf, k, c) != 0) /* no, it differs, stop here */
 521             break;
 522           k += c; l -= c;
 523         }
 524       }
 525       needseek = 1; /* we're looked to other place, should seek back */
 526     }
 527     if (!--httodo)
 528       return 0;
 529     if (++hti == htsize) {
 530       hti = htstart;
 531       needseek = 1;
 532     }
 533   }
 534 }
 535
 536 cdbi_t
 537 cdb_unpack(const unsigned char buf[4])
 538 {
 539   cdbi_t n = buf[3];
 540   n <<= 8; n |= buf[2];
 541   n <<= 8; n |= buf[1];
 542   n <<= 8; n |= buf[0];
 543   return n;
 544 }
 545
 546 /* Add record with key (KEY,KLEN) and value (VAL,VLEN) to a database.
 547    Returns 0 on success or negative value on error.  Note that this
 548    routine does not checks if given key already exists, but cdb_find()
 549    will not see second record with the same key.  It is not possible
 550    to continue building a database if cdb_make_add() returned an error
 551    indicator. */
 552 int
 553 cdb_make_add(struct cdb_make *cdbmp,
 554              const void *key, cdbi_t klen,
 555              const void *val, cdbi_t vlen)
 556 {
 557   unsigned char rlen[8];
 558   cdbi_t hval;
 559   struct cdb_rl *rl;
 560   if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
 561       vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
 562     gpg_err_set_errno (ENOMEM);
 563     return -1;
 564   }
 565   hval = cdb_hash(key, klen);
 566   rl = cdbmp->cdb_rec[hval&255];
 567   if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
 568     rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
 569     if (!rl) {
 570       gpg_err_set_errno (ENOMEM);
 571       return -1;
 572     }
 573     rl->cnt = 0;
 574     rl->next = cdbmp->cdb_rec[hval&255];
 575     cdbmp->cdb_rec[hval&255] = rl;
 576   }
 577   rl->rec[rl->cnt].hval = hval;
 578   rl->rec[rl->cnt].rpos = cdbmp->cdb_dpos;
 579   ++rl->cnt;
 580   ++cdbmp->cdb_rcnt;
 581   cdb_pack(klen, rlen);
 582   cdb_pack(vlen, rlen + 4);
 583   if (make_write(cdbmp, rlen, 8) < 0 ||
 584       make_write(cdbmp, key, klen) < 0 ||
 585       make_write(cdbmp, val, vlen) < 0)
 586     return -1;
 587   return 0;
 588 }
 589
 590 int
 591 cdb_make_put(struct cdb_make *cdbmp,
 592              const void *key, cdbi_t klen,
 593              const void *val, cdbi_t vlen,
 594              int flags)
 595 {
 596   unsigned char rlen[8];
 597   cdbi_t hval = cdb_hash(key, klen);
 598   struct cdb_rl *rl;
 599   int c, r;
 600
 601   switch(flags) {
 602     case CDB_PUT_REPLACE:
 603     case CDB_PUT_INSERT:
 604     case CDB_PUT_WARN:
 605       c = make_find(cdbmp, key, klen, hval, &rl);
 606       if (c < 0)
 607         return -1;
 608       if (c) {
 609         if (flags == CDB_PUT_INSERT) {
 610           gpg_err_set_errno (EEXIST);
 611           return 1;
 612         }
 613         else if (flags == CDB_PUT_REPLACE) {
 614           --c;
 615           r = 1;
 616           break;
 617         }
 618         else
 619           r = 1;
 620       }
 621       /* fall */
 622
 623     case CDB_PUT_ADD:
 624       rl = cdbmp->cdb_rec[hval&255];
 625       if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
 626         rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
 627         if (!rl) {
 628           gpg_err_set_errno (ENOMEM);
 629           return -1;
 630         }
 631         rl->cnt = 0;
 632         rl->next = cdbmp->cdb_rec[hval&255];
 633         cdbmp->cdb_rec[hval&255] = rl;
 634       }
 635       c = rl->cnt;
 636       r = 0;
 637       break;
 638
 639     default:
 640       gpg_err_set_errno (EINVAL);
 641       return -1;
 642   }
 643
 644   if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
 645       vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
 646     gpg_err_set_errno (ENOMEM);
 647     return -1;
 648   }
 649   rl->rec[c].hval = hval;
 650   rl->rec[c].rpos = cdbmp->cdb_dpos;
 651   if (c == rl->cnt) {
 652     ++rl->cnt;
 653     ++cdbmp->cdb_rcnt;
 654   }
 655   cdb_pack(klen, rlen);
 656   cdb_pack(vlen, rlen + 4);
 657   if (make_write(cdbmp, rlen, 8) < 0 ||
 658       make_write(cdbmp, key, klen) < 0 ||
 659       make_write(cdbmp, val, vlen) < 0)
 660     return -1;
 661   return r;
 662 }
 663
 664
 665 static int
 666 match(int fd, cdbi_t pos, const char *key, cdbi_t klen)
 667 {
 668   unsigned char buf[64]; /*XXX cdb_buf may be used here instead */
 669   if (lseek(fd, pos, SEEK_SET) < 0 || read(fd, buf, 8) != 8)
 670     return -1;
 671   if (cdb_unpack(buf) != klen)
 672     return 0;
 673
 674   while(klen > sizeof(buf)) {
 675     if (read(fd, buf, sizeof(buf)) != sizeof(buf))
 676       return -1;
 677     if (memcmp(buf, key, sizeof(buf)) != 0)
 678       return 0;
 679     key += sizeof(buf);
 680     klen -= sizeof(buf);
 681   }
 682   if (klen) {
 683     if (read(fd, buf, klen) != klen)
 684       return -1;
 685     if (memcmp(buf, key, klen) != 0)
 686       return 0;
 687   }
 688   return 1;
 689 }
 690
 691
 692 static int
 693 make_find (struct cdb_make *cdbmp,
 694            const void *key, cdbi_t klen, cdbi_t hval,
 695            struct cdb_rl **rlp)
 696 {
 697   struct cdb_rl *rl = cdbmp->cdb_rec[hval&255];
 698   int r, i;
 699   int sought = 0;
 700   while(rl) {
 701     for(i = rl->cnt - 1; i >= 0; --i) { /* search backward */
 702       if (rl->rec[i].hval != hval)
 703         continue;
 704       /*XXX this explicit flush may be unnecessary having
 705        * smarter match() that looks to cdb_buf too, but
 706        * most of a time here spent in finding hash values
 707        * (above), not keys */
 708       if (cdbmp->cdb_bpos != cdbmp->cdb_buf) {
 709         if (write(cdbmp->cdb_fd, cdbmp->cdb_buf,
 710                   cdbmp->cdb_bpos - cdbmp->cdb_buf) < 0)
 711           return -1;
 712         cdbmp->cdb_bpos = cdbmp->cdb_buf;
 713       }
 714       sought = 1;
 715       r = match(cdbmp->cdb_fd, rl->rec[i].rpos, key, klen);
 716       if (!r)
 717         continue;
 718       if (r < 0)
 719         return -1;
 720       if (lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
 721         return -1;
 722       if (rlp)
 723         *rlp = rl;
 724       return i + 1;
 725     }
 726     rl = rl->next;
 727   }
 728   if (sought && lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
 729     return -1;
 730   return 0;
 731 }
 732
 733 int
 734 cdb_make_exists(struct cdb_make *cdbmp,
 735                 const void *key, cdbi_t klen)
 736 {
 737   return make_find(cdbmp, key, klen, cdb_hash(key, klen), NULL);
 738 }
 739
 740
 741 void
 742 cdb_pack(cdbi_t num, unsigned char buf[4])
 743 {
 744   buf[0] = num & 255; num >>= 8;
 745   buf[1] = num & 255; num >>= 8;
 746   buf[2] = num & 255;
 747   buf[3] = num >> 8;
 748 }
 749
 750
 751 /* Initializes structure to create a database.  File FD should be
 752    opened read-write and should be seekable.  Returns 0 on success or
 753    negative value on error. */
 754 int
 755 cdb_make_start(struct cdb_make *cdbmp, int fd)
 756 {
 757   memset (cdbmp, 0, sizeof *cdbmp);
 758   cdbmp->cdb_fd = fd;
 759   cdbmp->cdb_dpos = 2048;
 760   cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
 761   return 0;
 762 }
 763
 764
 765 static int
 766 ewrite(int fd, const char *buf, int len)
 767 {
 768   while(len) {
 769     int l = write(fd, buf, len);
 770     if (l < 0 && errno != EINTR)
 771       return -1;
 772     if (l > 0)
 773       {
 774         len -= l;
 775         buf += l;
 776       }
 777   }
 778   return 0;
 779 }
 780
 781 static int
 782 make_write(struct cdb_make *cdbmp, const char *ptr, cdbi_t len)
 783 {
 784   cdbi_t l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
 785   cdbmp->cdb_dpos += len;
 786   if (len > l) {
 787     memcpy(cdbmp->cdb_bpos, ptr, l);
 788     if (ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf, sizeof(cdbmp->cdb_buf)) < 0)
 789       return -1;
 790     ptr += l; len -= l;
 791     l = len / sizeof(cdbmp->cdb_buf);
 792     if (l) {
 793       l *= sizeof(cdbmp->cdb_buf);
 794       if (ewrite(cdbmp->cdb_fd, ptr, l) < 0)
 795         return -1;
 796       ptr += l; len -= l;
 797     }
 798     cdbmp->cdb_bpos = cdbmp->cdb_buf;
 799   }
 800   if (len) {
 801     memcpy(cdbmp->cdb_bpos, ptr, len);
 802     cdbmp->cdb_bpos += len;
 803   }
 804   return 0;
 805 }
 806
 807 static int
 808 cdb_make_finish_internal(struct cdb_make *cdbmp)
 809 {
 810   cdbi_t hcnt[256];             /* hash table counts */
 811   cdbi_t hpos[256];             /* hash table positions */
 812   struct cdb_rec *htab;
 813   unsigned char *p;
 814   struct cdb_rl *rl;
 815   cdbi_t hsize;
 816   unsigned t, i;
 817
 818   if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) {
 819     gpg_err_set_errno (ENOMEM);
 820     return -1;
 821   }
 822
 823   /* count htab sizes and reorder reclists */
 824   hsize = 0;
 825   for (t = 0; t < 256; ++t) {
 826     struct cdb_rl *rlt = NULL;
 827     i = 0;
 828     rl = cdbmp->cdb_rec[t];
 829     while(rl) {
 830       struct cdb_rl *rln = rl->next;
 831       rl->next = rlt;
 832       rlt = rl;
 833       i += rl->cnt;
 834       rl = rln;
 835     }
 836     cdbmp->cdb_rec[t] = rlt;
 837     if (hsize < (hcnt[t] = i << 1))
 838       hsize = hcnt[t];
 839   }
 840
 841   /* allocate memory to hold max htable */
 842   htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
 843   if (!htab) {
 844     gpg_err_set_errno (ENOENT);
 845     return -1;
 846   }
 847   p = (unsigned char *)htab;
 848   htab += 2;
 849
 850   /* build hash tables */
 851   for (t = 0; t < 256; ++t) {
 852     cdbi_t len, hi;
 853     hpos[t] = cdbmp->cdb_dpos;
 854     if ((len = hcnt[t]) == 0)
 855       continue;
 856     for (i = 0; i < len; ++i)
 857       htab[i].hval = htab[i].rpos = 0;
 858     for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
 859       for (i = 0; i < rl->cnt; ++i) {
 860         hi = (rl->rec[i].hval >> 8) % len;
 861         while(htab[hi].rpos)
 862           if (++hi == len)
 863             hi = 0;
 864         htab[hi] = rl->rec[i];
 865       }
 866     for (i = 0; i < len; ++i) {
 867       cdb_pack(htab[i].hval, p + (i << 3));
 868       cdb_pack(htab[i].rpos, p + (i << 3) + 4);
 869     }
 870     if (make_write(cdbmp, p, len << 3) < 0) {
 871       free(p);
 872       return -1;
 873     }
 874   }
 875   free(p);
 876   if (cdbmp->cdb_bpos != cdbmp->cdb_buf &&
 877       ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf,
 878              cdbmp->cdb_bpos - cdbmp->cdb_buf) != 0)
 879       return -1;
 880   p = cdbmp->cdb_buf;
 881   for (t = 0; t < 256; ++t) {
 882     cdb_pack(hpos[t], p + (t << 3));
 883     cdb_pack(hcnt[t], p + (t << 3) + 4);
 884   }
 885   if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
 886       ewrite(cdbmp->cdb_fd, p, 2048) != 0)
 887     return -1;
 888
 889   return 0;
 890 }
 891
 892 static void
 893 cdb_make_free(struct cdb_make *cdbmp)
 894 {
 895   unsigned t;
 896   for(t = 0; t < 256; ++t) {
 897     struct cdb_rl *rl = cdbmp->cdb_rec[t];
 898     while(rl) {
 899       struct cdb_rl *tm = rl;
 900       rl = rl->next;
 901       free(tm);
 902     }
 903   }
 904 }
 905
 906
 907
 908 /* Finalizes database file, constructing all needed indexes, and frees
 909    memory structures.  It does not close the file descriptor.  Returns
 910    0 on success or a negative value on error. */
 911 int
 912 cdb_make_finish(struct cdb_make *cdbmp)
 913 {
 914   int r = cdb_make_finish_internal(cdbmp);
 915   cdb_make_free(cdbmp);
 916   return r;
 917 }
 918
 919
 920 cdbi_t
 921 cdb_hash(const void *buf, cdbi_t len)
 922 {
 923   register const unsigned char *p = (const unsigned char *)buf;
 924   register const unsigned char *end = p + len;
 925   register cdbi_t hash = 5381;  /* start value */
 926   while (p < end)
 927     hash = (hash + (hash << 5)) ^ *p++;
 928   return hash;
 929 }