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 }