LCOV - code coverage report
Current view: top level - dirmngr - cdblib.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 447 0.0 %
Date: 2016-09-12 12:29:17 Functions: 0 22 0.0 %

          Line data    Source code
       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           0 : 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           0 :   if (fstat(fd, &st) < 0)
     126           0 :     return -1;
     127             :   /* trivial sanity check: at least toc should be here */
     128           0 :   if (st.st_size < 2048) {
     129           0 :     gpg_err_set_errno (EPROTO);
     130           0 :     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           0 :   fsize = (unsigned int)(st.st_size & 0xffffffffu);
     150           0 :   mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
     151           0 :   if (mem == MAP_FAILED)
     152           0 :     return -1;
     153             : #endif /*!_WIN32*/
     154             : 
     155           0 :   cdbp->cdb_fd = fd;
     156           0 :   cdbp->cdb_fsize = st.st_size;
     157           0 :   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           0 :   cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
     173             : 
     174           0 :   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           0 : cdb_free(struct cdb *cdbp)
     182             : {
     183           0 :   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           0 :     munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
     190             : #endif /* _WIN32 */
     191           0 :     cdbp->cdb_mem = NULL;
     192             :   }
     193           0 :   cdbp->cdb_fsize = 0;
     194           0 : }
     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           0 : cdb_read(const struct cdb *cdbp, void *buf, unsigned len, cdbi_t pos)
     204             : {
     205           0 :   if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) {
     206           0 :     gpg_err_set_errno (EPROTO);
     207           0 :     return -1;
     208             :   }
     209           0 :   memcpy(buf, cdbp->cdb_mem + pos, len);
     210           0 :   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           0 : 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           0 :   if (klen > cdbp->cdb_fsize)     /* if key size is larger than file */
     233           0 :     return 0;
     234             : 
     235           0 :   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           0 :   htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
     241           0 :   n = cdb_unpack(htp + 4);      /* table size */
     242           0 :   if (!n)                       /* empty table */
     243           0 :     return 0;                   /* not found */
     244           0 :   httodo = n << 3;                /* bytes of htab to lookup */
     245           0 :   pos = cdb_unpack(htp);        /* htab position */
     246           0 :   if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
     247           0 :       || pos > cdbp->cdb_fsize /* htab start within file ? */
     248           0 :       || httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
     249             :   {
     250           0 :     gpg_err_set_errno (EPROTO);
     251           0 :     return -1;
     252             :   }
     253             : 
     254           0 :   htab = cdbp->cdb_mem + pos;        /* htab pointer */
     255           0 :   htend = htab + httodo;        /* after end of htab */
     256             :   /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
     257           0 :   htp = htab + (((hval >> 8) % n) << 3);
     258             : 
     259             :   for(;;) {
     260           0 :     pos = cdb_unpack(htp + 4);  /* record position */
     261           0 :     if (!pos)
     262           0 :       return 0;
     263           0 :     if (cdb_unpack(htp) == hval) {
     264           0 :       if (pos > cdbp->cdb_fsize - 8) { /* key+val lengths */
     265           0 :         gpg_err_set_errno (EPROTO);
     266           0 :         return -1;
     267             :       }
     268           0 :       if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
     269           0 :         if (cdbp->cdb_fsize - klen < pos + 8) {
     270           0 :           gpg_err_set_errno (EPROTO);
     271           0 :           return -1;
     272             :         }
     273           0 :         if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
     274           0 :           n = cdb_unpack(cdbp->cdb_mem + pos + 4);
     275           0 :           pos += 8 + klen;
     276           0 :           if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
     277           0 :             gpg_err_set_errno (EPROTO);
     278           0 :             return -1;
     279             :           }
     280           0 :           cdbp->cdb_vpos = pos;
     281           0 :           cdbp->cdb_vlen = n;
     282           0 :           return 1;
     283             :         }
     284             :       }
     285             :     }
     286           0 :     httodo -= 8;
     287           0 :     if (!httodo)
     288           0 :       return 0;
     289           0 :     if ((htp += 8) >= htend)
     290           0 :       htp = htab;
     291           0 :   }
     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.  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           0 : cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
     317             :              const void *key, cdbi_t klen)
     318             : {
     319             :   cdbi_t n, pos;
     320             : 
     321           0 :   cdbfp->cdb_cdbp = cdbp;
     322           0 :   cdbfp->cdb_key  = key;
     323           0 :   cdbfp->cdb_klen = klen;
     324           0 :   cdbfp->cdb_hval = key? cdb_hash(key, klen) : 0;
     325             : 
     326           0 :   if (key)
     327             :     {
     328           0 :       cdbfp->cdb_htp = cdbp->cdb_mem + ((cdbfp->cdb_hval << 3) & 2047);
     329           0 :       n = cdb_unpack(cdbfp->cdb_htp + 4);
     330           0 :       cdbfp->cdb_httodo = n << 3; /* Set to size of hash table. */
     331           0 :       if (!n)
     332           0 :         return 0; /* The hash table is empry. */
     333           0 :       pos = cdb_unpack(cdbfp->cdb_htp);
     334           0 :       if (n > (cdbp->cdb_fsize >> 3)
     335           0 :           || pos > cdbp->cdb_fsize
     336           0 :           || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
     337             :         {
     338           0 :           gpg_err_set_errno (EPROTO);
     339           0 :           return -1;
     340             :         }
     341             : 
     342           0 :       cdbfp->cdb_htab = cdbp->cdb_mem + pos;
     343           0 :       cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
     344           0 :       cdbfp->cdb_htp = cdbfp->cdb_htab + (((cdbfp->cdb_hval >> 8) % n) << 3);
     345             :     }
     346             :   else /* Walk over all entries. */
     347             :     {
     348           0 :       cdbfp->cdb_hval = 0;
     349             :       /* Force stepping in findnext. */
     350           0 :       cdbfp->cdb_htp = cdbfp->cdb_htend = cdbp->cdb_mem;
     351             :     }
     352           0 :   return 0;
     353             : }
     354             : 
     355             : 
     356             : /* See cdb_findinit. */
     357             : int
     358           0 : cdb_findnext(struct cdb_find *cdbfp)
     359             : {
     360             :   cdbi_t pos, n;
     361           0 :   struct cdb *cdbp = cdbfp->cdb_cdbp;
     362             : 
     363           0 :   if (cdbfp->cdb_key)
     364             :     {
     365           0 :       while(cdbfp->cdb_httodo) {
     366           0 :         pos = cdb_unpack(cdbfp->cdb_htp + 4);
     367           0 :         if (!pos)
     368           0 :           return 0;
     369           0 :         n = cdb_unpack(cdbfp->cdb_htp) == cdbfp->cdb_hval;
     370           0 :         if ((cdbfp->cdb_htp += 8) >= cdbfp->cdb_htend)
     371           0 :           cdbfp->cdb_htp = cdbfp->cdb_htab;
     372           0 :         cdbfp->cdb_httodo -= 8;
     373           0 :         if (n) {
     374           0 :           if (pos > cdbp->cdb_fsize - 8) {
     375           0 :             gpg_err_set_errno (EPROTO);
     376           0 :             return -1;
     377             :           }
     378           0 :           if (cdb_unpack(cdbp->cdb_mem + pos) == cdbfp->cdb_klen) {
     379           0 :             if (cdbp->cdb_fsize - cdbfp->cdb_klen < pos + 8) {
     380           0 :               gpg_err_set_errno (EPROTO);
     381           0 :               return -1;
     382             :             }
     383           0 :             if (memcmp(cdbfp->cdb_key,
     384           0 :                        cdbp->cdb_mem + pos + 8, cdbfp->cdb_klen) == 0) {
     385           0 :               n = cdb_unpack(cdbp->cdb_mem + pos + 4);
     386           0 :               pos += 8 + cdbfp->cdb_klen;
     387           0 :               if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
     388           0 :                 gpg_err_set_errno (EPROTO);
     389           0 :                 return -1;
     390             :               }
     391           0 :               cdbp->cdb_vpos = pos;
     392           0 :               cdbp->cdb_vlen = n;
     393           0 :               return 1;
     394             :             }
     395             :           }
     396             :         }
     397             :       }
     398             :     }
     399             :   else /* Walk over all entries. */
     400             :     {
     401             :       do
     402             :         {
     403           0 :           while (cdbfp->cdb_htp >= cdbfp->cdb_htend)
     404             :             {
     405           0 :               if (cdbfp->cdb_hval > 255)
     406           0 :                 return 0; /* No more items. */
     407             : 
     408           0 :               cdbfp->cdb_htp = cdbp->cdb_mem + cdbfp->cdb_hval * 8;
     409           0 :               cdbfp->cdb_hval++; /* Advance for next round. */
     410           0 :               pos = cdb_unpack (cdbfp->cdb_htp);     /* Offset of table. */
     411           0 :               n   = cdb_unpack (cdbfp->cdb_htp + 4); /* Number of entries. */
     412           0 :               cdbfp->cdb_httodo = n * 8;             /* Size of table. */
     413           0 :               if (n > (cdbp->cdb_fsize / 8)
     414           0 :                   || pos > cdbp->cdb_fsize
     415           0 :                   || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
     416             :                 {
     417           0 :                   gpg_err_set_errno (EPROTO);
     418           0 :                   return -1;
     419             :                 }
     420             : 
     421           0 :               cdbfp->cdb_htab  = cdbp->cdb_mem + pos;
     422           0 :               cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
     423           0 :               cdbfp->cdb_htp   = cdbfp->cdb_htab;
     424             :             }
     425             : 
     426           0 :           pos = cdb_unpack (cdbfp->cdb_htp + 4); /* Offset of record. */
     427           0 :           cdbfp->cdb_htp += 8;
     428             :         }
     429           0 :       while (!pos);
     430           0 :       if (pos > cdbp->cdb_fsize - 8)
     431             :         {
     432           0 :           gpg_err_set_errno (EPROTO);
     433           0 :           return -1;
     434             :         }
     435             : 
     436           0 :       cdbp->cdb_kpos = pos + 8;
     437           0 :       cdbp->cdb_klen = cdb_unpack(cdbp->cdb_mem + pos);
     438           0 :       cdbp->cdb_vpos = pos + 8 + cdbp->cdb_klen;
     439           0 :       cdbp->cdb_vlen = cdb_unpack(cdbp->cdb_mem + pos + 4);
     440           0 :       n = 8 + cdbp->cdb_klen + cdbp->cdb_vlen;
     441           0 :       if ( pos > cdbp->cdb_fsize || pos > cdbp->cdb_fsize - n)
     442             :         {
     443           0 :           gpg_err_set_errno (EPROTO);
     444           0 :           return -1;
     445             :         }
     446           0 :       return 1; /* Found. */
     447             :     }
     448           0 :   return 0;
     449             : }
     450             : 
     451             : /* Read a chunk from file, ignoring interrupts (EINTR) */
     452             : int
     453           0 : cdb_bread(int fd, void *buf, int len)
     454             : {
     455             :   int l;
     456           0 :   while(len > 0) {
     457           0 :     do l = read(fd, buf, len);
     458           0 :     while(l < 0 && errno == EINTR);
     459           0 :     if (l <= 0) {
     460           0 :       if (!l)
     461           0 :         gpg_err_set_errno (EIO);
     462           0 :       return -1;
     463             :     }
     464           0 :     buf = (char*)buf + l;
     465           0 :     len -= l;
     466             :   }
     467           0 :   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           0 : 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           0 :   int needseek = 1;             /* if we should seek to a hash slot */
     483             : 
     484           0 :   hval = cdb_hash(key, klen);
     485           0 :   pos = (hval & 0xff) << 3; /* position in TOC */
     486             :   /* read the hash table parameters */
     487           0 :   if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
     488           0 :     return -1;
     489           0 :   if ((htsize = cdb_unpack(rbuf + 4)) == 0)
     490           0 :     return 0;
     491           0 :   hti = (hval >> 8) % htsize;     /* start position in hash table */
     492           0 :   httodo = htsize;
     493           0 :   htstart = cdb_unpack(rbuf);
     494             : 
     495             :   for(;;) {
     496           0 :     if (needseek && lseek(fd, htstart + (hti << 3), SEEK_SET) < 0)
     497           0 :       return -1;
     498           0 :     if (cdb_bread(fd, rbuf, 8) < 0)
     499           0 :       return -1;
     500           0 :     if ((pos = cdb_unpack(rbuf + 4)) == 0) /* not found */
     501           0 :       return 0;
     502             : 
     503           0 :     if (cdb_unpack(rbuf) != hval) /* hash value not matched */
     504           0 :       needseek = 0;
     505             :     else { /* hash value matched */
     506           0 :       if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
     507           0 :         return -1;
     508           0 :       if (cdb_unpack(rbuf) == klen) { /* key length matches */
     509             :         /* read the key from file and compare with wanted */
     510           0 :         cdbi_t l = klen, c;
     511           0 :         const char *k = (const char*)key;
     512           0 :         if (*dlenp)
     513           0 :           *dlenp = cdb_unpack(rbuf + 4); /* save value length */
     514             :         for(;;) {
     515           0 :           if (!l) /* the whole key read and matches, return */
     516           0 :             return 1;
     517           0 :           c = l > sizeof(rbuf) ? sizeof(rbuf) : l;
     518           0 :           if (cdb_bread(fd, rbuf, c) < 0)
     519           0 :             return -1;
     520           0 :           if (memcmp(rbuf, k, c) != 0) /* no, it differs, stop here */
     521           0 :             break;
     522           0 :           k += c; l -= c;
     523           0 :         }
     524             :       }
     525           0 :       needseek = 1; /* we're looked to other place, should seek back */
     526             :     }
     527           0 :     if (!--httodo)
     528           0 :       return 0;
     529           0 :     if (++hti == htsize) {
     530           0 :       hti = htstart;
     531           0 :       needseek = 1;
     532             :     }
     533           0 :   }
     534             : }
     535             : 
     536             : cdbi_t
     537           0 : cdb_unpack(const unsigned char buf[4])
     538             : {
     539           0 :   cdbi_t n = buf[3];
     540           0 :   n <<= 8; n |= buf[2];
     541           0 :   n <<= 8; n |= buf[1];
     542           0 :   n <<= 8; n |= buf[0];
     543           0 :   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           0 : 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           0 :   if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
     561           0 :       vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
     562           0 :     gpg_err_set_errno (ENOMEM);
     563           0 :     return -1;
     564             :   }
     565           0 :   hval = cdb_hash(key, klen);
     566           0 :   rl = cdbmp->cdb_rec[hval&255];
     567           0 :   if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
     568           0 :     rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
     569           0 :     if (!rl) {
     570           0 :       gpg_err_set_errno (ENOMEM);
     571           0 :       return -1;
     572             :     }
     573           0 :     rl->cnt = 0;
     574           0 :     rl->next = cdbmp->cdb_rec[hval&255];
     575           0 :     cdbmp->cdb_rec[hval&255] = rl;
     576             :   }
     577           0 :   rl->rec[rl->cnt].hval = hval;
     578           0 :   rl->rec[rl->cnt].rpos = cdbmp->cdb_dpos;
     579           0 :   ++rl->cnt;
     580           0 :   ++cdbmp->cdb_rcnt;
     581           0 :   cdb_pack(klen, rlen);
     582           0 :   cdb_pack(vlen, rlen + 4);
     583           0 :   if (make_write(cdbmp, rlen, 8) < 0 ||
     584           0 :       make_write(cdbmp, key, klen) < 0 ||
     585           0 :       make_write(cdbmp, val, vlen) < 0)
     586           0 :     return -1;
     587           0 :   return 0;
     588             : }
     589             : 
     590             : int
     591           0 : 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           0 :   cdbi_t hval = cdb_hash(key, klen);
     598             :   struct cdb_rl *rl;
     599             :   int c, r;
     600             : 
     601           0 :   switch(flags) {
     602             :     case CDB_PUT_REPLACE:
     603             :     case CDB_PUT_INSERT:
     604             :     case CDB_PUT_WARN:
     605           0 :       c = make_find(cdbmp, key, klen, hval, &rl);
     606           0 :       if (c < 0)
     607           0 :         return -1;
     608           0 :       if (c) {
     609           0 :         if (flags == CDB_PUT_INSERT) {
     610           0 :           gpg_err_set_errno (EEXIST);
     611           0 :           return 1;
     612             :         }
     613           0 :         else if (flags == CDB_PUT_REPLACE) {
     614           0 :           --c;
     615           0 :           r = 1;
     616           0 :           break;
     617             :         }
     618             :         else
     619           0 :           r = 1;
     620             :       }
     621             :       /* fall */
     622             : 
     623             :     case CDB_PUT_ADD:
     624           0 :       rl = cdbmp->cdb_rec[hval&255];
     625           0 :       if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
     626           0 :         rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
     627           0 :         if (!rl) {
     628           0 :           gpg_err_set_errno (ENOMEM);
     629           0 :           return -1;
     630             :         }
     631           0 :         rl->cnt = 0;
     632           0 :         rl->next = cdbmp->cdb_rec[hval&255];
     633           0 :         cdbmp->cdb_rec[hval&255] = rl;
     634             :       }
     635           0 :       c = rl->cnt;
     636           0 :       r = 0;
     637           0 :       break;
     638             : 
     639             :     default:
     640           0 :       gpg_err_set_errno (EINVAL);
     641           0 :       return -1;
     642             :   }
     643             : 
     644           0 :   if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
     645           0 :       vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
     646           0 :     gpg_err_set_errno (ENOMEM);
     647           0 :     return -1;
     648             :   }
     649           0 :   rl->rec[c].hval = hval;
     650           0 :   rl->rec[c].rpos = cdbmp->cdb_dpos;
     651           0 :   if (c == rl->cnt) {
     652           0 :     ++rl->cnt;
     653           0 :     ++cdbmp->cdb_rcnt;
     654             :   }
     655           0 :   cdb_pack(klen, rlen);
     656           0 :   cdb_pack(vlen, rlen + 4);
     657           0 :   if (make_write(cdbmp, rlen, 8) < 0 ||
     658           0 :       make_write(cdbmp, key, klen) < 0 ||
     659           0 :       make_write(cdbmp, val, vlen) < 0)
     660           0 :     return -1;
     661           0 :   return r;
     662             : }
     663             : 
     664             : 
     665             : static int
     666           0 : 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           0 :   if (lseek(fd, pos, SEEK_SET) < 0 || read(fd, buf, 8) != 8)
     670           0 :     return -1;
     671           0 :   if (cdb_unpack(buf) != klen)
     672           0 :     return 0;
     673             : 
     674           0 :   while(klen > sizeof(buf)) {
     675           0 :     if (read(fd, buf, sizeof(buf)) != sizeof(buf))
     676           0 :       return -1;
     677           0 :     if (memcmp(buf, key, sizeof(buf)) != 0)
     678           0 :       return 0;
     679           0 :     key += sizeof(buf);
     680           0 :     klen -= sizeof(buf);
     681             :   }
     682           0 :   if (klen) {
     683           0 :     if (read(fd, buf, klen) != klen)
     684           0 :       return -1;
     685           0 :     if (memcmp(buf, key, klen) != 0)
     686           0 :       return 0;
     687             :   }
     688           0 :   return 1;
     689             : }
     690             : 
     691             : 
     692             : static int
     693           0 : make_find (struct cdb_make *cdbmp,
     694             :            const void *key, cdbi_t klen, cdbi_t hval,
     695             :            struct cdb_rl **rlp)
     696             : {
     697           0 :   struct cdb_rl *rl = cdbmp->cdb_rec[hval&255];
     698             :   int r, i;
     699           0 :   int sought = 0;
     700           0 :   while(rl) {
     701           0 :     for(i = rl->cnt - 1; i >= 0; --i) { /* search backward */
     702           0 :       if (rl->rec[i].hval != hval)
     703           0 :         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           0 :       if (cdbmp->cdb_bpos != cdbmp->cdb_buf) {
     709           0 :         if (write(cdbmp->cdb_fd, cdbmp->cdb_buf,
     710           0 :                   cdbmp->cdb_bpos - cdbmp->cdb_buf) < 0)
     711           0 :           return -1;
     712           0 :         cdbmp->cdb_bpos = cdbmp->cdb_buf;
     713             :       }
     714           0 :       sought = 1;
     715           0 :       r = match(cdbmp->cdb_fd, rl->rec[i].rpos, key, klen);
     716           0 :       if (!r)
     717           0 :         continue;
     718           0 :       if (r < 0)
     719           0 :         return -1;
     720           0 :       if (lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
     721           0 :         return -1;
     722           0 :       if (rlp)
     723           0 :         *rlp = rl;
     724           0 :       return i + 1;
     725             :     }
     726           0 :     rl = rl->next;
     727             :   }
     728           0 :   if (sought && lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
     729           0 :     return -1;
     730           0 :   return 0;
     731             : }
     732             : 
     733             : int
     734           0 : cdb_make_exists(struct cdb_make *cdbmp,
     735             :                 const void *key, cdbi_t klen)
     736             : {
     737           0 :   return make_find(cdbmp, key, klen, cdb_hash(key, klen), NULL);
     738             : }
     739             : 
     740             : 
     741             : void
     742           0 : cdb_pack(cdbi_t num, unsigned char buf[4])
     743             : {
     744           0 :   buf[0] = num & 255; num >>= 8;
     745           0 :   buf[1] = num & 255; num >>= 8;
     746           0 :   buf[2] = num & 255;
     747           0 :   buf[3] = num >> 8;
     748           0 : }
     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           0 : cdb_make_start(struct cdb_make *cdbmp, int fd)
     756             : {
     757           0 :   memset (cdbmp, 0, sizeof *cdbmp);
     758           0 :   cdbmp->cdb_fd = fd;
     759           0 :   cdbmp->cdb_dpos = 2048;
     760           0 :   cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
     761           0 :   return 0;
     762             : }
     763             : 
     764             : 
     765             : static int
     766           0 : ewrite(int fd, const char *buf, int len)
     767             : {
     768           0 :   while(len) {
     769           0 :     int l = write(fd, buf, len);
     770           0 :     if (l < 0 && errno != EINTR)
     771           0 :       return -1;
     772           0 :     if (l > 0)
     773             :       {
     774           0 :         len -= l;
     775           0 :         buf += l;
     776             :       }
     777             :   }
     778           0 :   return 0;
     779             : }
     780             : 
     781             : static int
     782           0 : make_write(struct cdb_make *cdbmp, const char *ptr, cdbi_t len)
     783             : {
     784           0 :   cdbi_t l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
     785           0 :   cdbmp->cdb_dpos += len;
     786           0 :   if (len > l) {
     787           0 :     memcpy(cdbmp->cdb_bpos, ptr, l);
     788           0 :     if (ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf, sizeof(cdbmp->cdb_buf)) < 0)
     789           0 :       return -1;
     790           0 :     ptr += l; len -= l;
     791           0 :     l = len / sizeof(cdbmp->cdb_buf);
     792           0 :     if (l) {
     793           0 :       l *= sizeof(cdbmp->cdb_buf);
     794           0 :       if (ewrite(cdbmp->cdb_fd, ptr, l) < 0)
     795           0 :         return -1;
     796           0 :       ptr += l; len -= l;
     797             :     }
     798           0 :     cdbmp->cdb_bpos = cdbmp->cdb_buf;
     799             :   }
     800           0 :   if (len) {
     801           0 :     memcpy(cdbmp->cdb_bpos, ptr, len);
     802           0 :     cdbmp->cdb_bpos += len;
     803             :   }
     804           0 :   return 0;
     805             : }
     806             : 
     807             : static int
     808           0 : 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           0 :   if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) {
     819           0 :     gpg_err_set_errno (ENOMEM);
     820           0 :     return -1;
     821             :   }
     822             : 
     823             :   /* count htab sizes and reorder reclists */
     824           0 :   hsize = 0;
     825           0 :   for (t = 0; t < 256; ++t) {
     826           0 :     struct cdb_rl *rlt = NULL;
     827           0 :     i = 0;
     828           0 :     rl = cdbmp->cdb_rec[t];
     829           0 :     while(rl) {
     830           0 :       struct cdb_rl *rln = rl->next;
     831           0 :       rl->next = rlt;
     832           0 :       rlt = rl;
     833           0 :       i += rl->cnt;
     834           0 :       rl = rln;
     835             :     }
     836           0 :     cdbmp->cdb_rec[t] = rlt;
     837           0 :     if (hsize < (hcnt[t] = i << 1))
     838           0 :       hsize = hcnt[t];
     839             :   }
     840             : 
     841             :   /* allocate memory to hold max htable */
     842           0 :   htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
     843           0 :   if (!htab) {
     844           0 :     gpg_err_set_errno (ENOENT);
     845           0 :     return -1;
     846             :   }
     847           0 :   p = (unsigned char *)htab;
     848           0 :   htab += 2;
     849             : 
     850             :   /* build hash tables */
     851           0 :   for (t = 0; t < 256; ++t) {
     852             :     cdbi_t len, hi;
     853           0 :     hpos[t] = cdbmp->cdb_dpos;
     854           0 :     if ((len = hcnt[t]) == 0)
     855           0 :       continue;
     856           0 :     for (i = 0; i < len; ++i)
     857           0 :       htab[i].hval = htab[i].rpos = 0;
     858           0 :     for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
     859           0 :       for (i = 0; i < rl->cnt; ++i) {
     860           0 :         hi = (rl->rec[i].hval >> 8) % len;
     861           0 :         while(htab[hi].rpos)
     862           0 :           if (++hi == len)
     863           0 :             hi = 0;
     864           0 :         htab[hi] = rl->rec[i];
     865             :       }
     866           0 :     for (i = 0; i < len; ++i) {
     867           0 :       cdb_pack(htab[i].hval, p + (i << 3));
     868           0 :       cdb_pack(htab[i].rpos, p + (i << 3) + 4);
     869             :     }
     870           0 :     if (make_write(cdbmp, p, len << 3) < 0) {
     871           0 :       free(p);
     872           0 :       return -1;
     873             :     }
     874             :   }
     875           0 :   free(p);
     876           0 :   if (cdbmp->cdb_bpos != cdbmp->cdb_buf &&
     877           0 :       ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf,
     878           0 :              cdbmp->cdb_bpos - cdbmp->cdb_buf) != 0)
     879           0 :       return -1;
     880           0 :   p = cdbmp->cdb_buf;
     881           0 :   for (t = 0; t < 256; ++t) {
     882           0 :     cdb_pack(hpos[t], p + (t << 3));
     883           0 :     cdb_pack(hcnt[t], p + (t << 3) + 4);
     884             :   }
     885           0 :   if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
     886           0 :       ewrite(cdbmp->cdb_fd, p, 2048) != 0)
     887           0 :     return -1;
     888             : 
     889           0 :   return 0;
     890             : }
     891             : 
     892             : static void
     893           0 : cdb_make_free(struct cdb_make *cdbmp)
     894             : {
     895             :   unsigned t;
     896           0 :   for(t = 0; t < 256; ++t) {
     897           0 :     struct cdb_rl *rl = cdbmp->cdb_rec[t];
     898           0 :     while(rl) {
     899           0 :       struct cdb_rl *tm = rl;
     900           0 :       rl = rl->next;
     901           0 :       free(tm);
     902             :     }
     903             :   }
     904           0 : }
     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           0 : cdb_make_finish(struct cdb_make *cdbmp)
     913             : {
     914           0 :   int r = cdb_make_finish_internal(cdbmp);
     915           0 :   cdb_make_free(cdbmp);
     916           0 :   return r;
     917             : }
     918             : 
     919             : 
     920             : cdbi_t
     921           0 : cdb_hash(const void *buf, cdbi_t len)
     922             : {
     923           0 :   register const unsigned char *p = (const unsigned char *)buf;
     924           0 :   register const unsigned char *end = p + len;
     925           0 :   register cdbi_t hash = 5381;  /* start value */
     926           0 :   while (p < end)
     927           0 :     hash = (hash + (hash << 5)) ^ *p++;
     928           0 :   return hash;
     929             : }

Generated by: LCOV version 1.11