src/lookups/cdb.c

   1 /*************************************************
   2 *     Exim - an Internet mail transport agent    *
   3 *************************************************/
   4
   5 /*
   6  * Exim - CDB database lookup module
   7  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   8  *
   9  * Copyright (c) 1998 Nigel Metheringham, Planet Online Ltd
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU General Public License
  13  * as published by the Free Software Foundation; either version 2
  14  * of the License, or (at your option) any later version.
  15  *
  16  * --------------------------------------------------------------
  17  * Modified by PH for Exim 4:
  18  *   Changed over to using unsigned chars
  19  *   Makes use of lf_check_file() for file checking
  20  * --------------------------------------------------------------
  21  *
  22  * This program is distributed in the hope that it will be useful,
  23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  25  * GNU General Public License for more details.
  26  *
  27  * You should have received a copy of the GNU General Public License
  28  * along with this program; if not, write to the Free Software
  29  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  30  * 02111-1307, USA.
  31  *
  32  *
  33  * This code implements Dan Bernstein's Constant DataBase (cdb) spec.
  34  * Information, the spec and sample code for cdb can be obtained from
  35  *      http://www.pobox.com/~djb/cdb.html
  36  *
  37  * This implementation borrows some code from Dan Bernstein's
  38  * implementation (which has no license restrictions applied to it).
  39  * This (read-only) implementation is completely contained within
  40  * cdb.[ch] it does *not* link against an external cdb library.
  41  *
  42  *
  43  * There are 2 varients included within this code.  One uses MMAP and
  44  * should give better performance especially for multiple lookups on a
  45  * modern machine.  The other is the default implementation which is
  46  * used in the case where the MMAP fails or if MMAP was not compiled
  47  * in.  this implementation is the same as the original reference cdb
  48  * implementation.  The MMAP version is compiled in if the HAVE_MMAP
  49  * preprocessor define is defined - this should be set in the system
  50  * specific os.h file.
  51  *
  52  */
  53
  54
  55 #include "../exim.h"
  56 #include "lf_functions.h"
  57
  58 #ifdef HAVE_MMAP
  59 #  include <sys/mman.h>
  60 /* Not all implementations declare MAP_FAILED */
  61 #  ifndef MAP_FAILED
  62 #    define MAP_FAILED ((void *) -1)
  63 #  endif /* MAP_FAILED */
  64 #endif /* HAVE_MMAP */
  65
  66
  67 #define CDB_HASH_SPLIT 256     /* num pieces the hash table is split into */
  68 #define CDB_HASH_MASK  255     /* mask to and off split value */
  69 #define CDB_HASH_ENTRY 8       /* how big each offset it */
  70 #define CDB_HASH_TABLE (CDB_HASH_SPLIT * CDB_HASH_ENTRY)
  71
  72 /* State information for cdb databases that are open NB while the db
  73  * is open its contents will not change (cdb dbs are normally updated
  74  * atomically by renaming).  However the lifetime of one of these
  75  * state structures should be limited - ie a long running daemon
  76  * that opens one may hit problems....
  77  */
  78
  79 struct cdb_state {
  80   int     fileno;
  81   off_t   filelen;
  82   uschar *cdb_map;
  83   uschar *cdb_offsets;
  84 };
  85
  86 /* 32 bit unsigned type - this is an int on all modern machines */
  87 typedef unsigned int uint32;
  88
  89 /*
  90  * cdb_hash()
  91  * Internal function to make hash value */
  92
  93 static uint32
  94 cdb_hash(uschar *buf, unsigned int len)
  95 {
  96   uint32 h;
  97
  98   h = 5381;
  99   while (len) {
 100     --len;
 101     h += (h << 5);
 102     h ^= (uint32) *buf++;
 103   }
 104   return h;
 105 }
 106
 107 /*
 108  * cdb_bread()
 109  * Internal function to read len bytes from disk, coping with oddities */
 110
 111 static int
 112 cdb_bread(int fd,
 113          uschar *buf,
 114          int len)
 115 {
 116   int r;
 117   while (len > 0) {
 118     do
 119       r = Uread(fd,buf,len);
 120     while ((r == -1) && (errno == EINTR));
 121     if (r == -1) return -1;
 122     if (r == 0) { errno = EIO; return -1; }
 123     buf += r;
 124     len -= r;
 125   }
 126   return 0;
 127 }
 128
 129 /*
 130  * cdb_bread()
 131  * Internal function to parse 4 byte number (endian independant) */
 132
 133 static uint32
 134 cdb_unpack(uschar *buf)
 135 {
 136   uint32 num;
 137   num =  buf[3]; num <<= 8;
 138   num += buf[2]; num <<= 8;
 139   num += buf[1]; num <<= 8;
 140   num += buf[0];
 141   return num;
 142 }
 143
 144 static void cdb_close(void *handle);
 145
 146 static void *
 147 cdb_open(uschar *filename,
 148          uschar **errmsg)
 149 {
 150   int fileno;
 151   struct cdb_state *cdbp;
 152   struct stat statbuf;
 153   void * mapbuf;
 154
 155   fileno = Uopen(filename, O_RDONLY, 0);
 156   if (fileno == -1) {
 157     int save_errno = errno;
 158     *errmsg = string_open_failed(errno, "%s for cdb lookup", filename);
 159     errno = save_errno;
 160     return NULL;
 161   }
 162
 163   if (fstat(fileno, &statbuf) == 0) {
 164     /* If this is a valid file, then it *must* be at least
 165      * CDB_HASH_TABLE bytes long */
 166     if (statbuf.st_size < CDB_HASH_TABLE) {
 167       int save_errno = errno;
 168       *errmsg = string_open_failed(errno,
 169                                   "%s too short for cdb lookup",
 170                                   filename);
 171       errno = save_errno;
 172       return NULL;
 173     }
 174   } else {
 175     int save_errno = errno;
 176     *errmsg = string_open_failed(errno,
 177                                 "fstat(%s) failed - cannot do cdb lookup",
 178                                 filename);
 179     errno = save_errno;
 180     return NULL;
 181   }
 182
 183   /* Having got a file open we need the structure to put things in */
 184   cdbp = store_get(sizeof(struct cdb_state));
 185   /* store_get() does not return if memory was not available... */
 186   /* preload the structure.... */
 187   cdbp->fileno = fileno;
 188   cdbp->filelen = statbuf.st_size;
 189   cdbp->cdb_map = NULL;
 190   cdbp->cdb_offsets = NULL;
 191
 192   /* if we are allowed to we use mmap here.... */
 193 #ifdef HAVE_MMAP
 194   mapbuf = mmap(NULL,
 195                statbuf.st_size,
 196                PROT_READ,
 197                MAP_SHARED,
 198                fileno,
 199                0);
 200   if (mapbuf != MAP_FAILED) {
 201     /* We have an mmap-ed section.  Now we can just use it */
 202     cdbp->cdb_map = mapbuf;
 203     /* The offsets can be set to the same value since they should
 204      * effectively be cached as well
 205      */
 206     cdbp->cdb_offsets = mapbuf;
 207
 208     /* Now return the state struct */
 209     return(cdbp);
 210   } else {
 211     /* If we got here the map failed.  Basically we can ignore
 212      * this since we fall back to slower methods....
 213      * However lets debug log it...
 214      */
 215     DEBUG(D_lookup) debug_printf("cdb mmap failed - %d\n", errno);
 216   }
 217 #endif /* HAVE_MMAP */
 218
 219   /* In this case we have either not got MMAP allowed, or it failed */
 220
 221   /* get a buffer to stash the basic offsets in - this should speed
 222    * things up a lot - especially on multiple lookups */
 223   cdbp->cdb_offsets = store_get(CDB_HASH_TABLE);
 224
 225   /* now fill the buffer up... */
 226   if (cdb_bread(fileno, cdbp->cdb_offsets, CDB_HASH_TABLE) == -1) {
 227     /* read of hash table failed, oh dear, oh.....
 228      * time to give up I think....
 229      * call the close routine (deallocs the memory), and return NULL */
 230     *errmsg = string_open_failed(errno,
 231                                 "cannot read header from %s for cdb lookup",
 232                                 filename);
 233     cdb_close(cdbp);
 234     return NULL;
 235   }
 236
 237   /* Everything else done - return the cache structure */
 238   return cdbp;
 239 }
 240
 241
 242
 243 /*************************************************
 244 *             Check entry point                  *
 245 *************************************************/
 246
 247 static BOOL
 248 cdb_check(void *handle,
 249          uschar *filename,
 250          int modemask,
 251          uid_t *owners,
 252          gid_t *owngroups,
 253          uschar **errmsg)
 254 {
 255   struct cdb_state * cdbp = handle;
 256   return lf_check_file(cdbp->fileno,
 257                        filename,
 258                        S_IFREG,
 259                        modemask,
 260                        owners,
 261                        owngroups,
 262                        "cdb",
 263                        errmsg) == 0;
 264 }
 265
 266
 267
 268 /*************************************************
 269 *              Find entry point                  *
 270 *************************************************/
 271
 272 static int
 273 cdb_find(void *handle,
 274         uschar *filename,
 275         uschar *keystring,
 276         int  key_len,
 277         uschar **result,
 278         uschar **errmsg,
 279         BOOL *do_cache)
 280 {
 281   struct cdb_state * cdbp = handle;
 282   uint32 item_key_len,
 283     item_dat_len,
 284     key_hash,
 285     item_hash,
 286     item_posn,
 287     cur_offset,
 288     end_offset,
 289     hash_offset_entry,
 290     hash_offset,
 291     hash_offlen,
 292     hash_slotnm;
 293   int loop;
 294
 295   /* Keep picky compilers happy */
 296   do_cache = do_cache;
 297
 298   key_hash = cdb_hash((uschar *)keystring, key_len);
 299
 300   hash_offset_entry = CDB_HASH_ENTRY * (key_hash & CDB_HASH_MASK);
 301   hash_offset = cdb_unpack(cdbp->cdb_offsets + hash_offset_entry);
 302   hash_offlen = cdb_unpack(cdbp->cdb_offsets + hash_offset_entry + 4);
 303
 304   /* If the offset length is zero this key cannot be in the file */
 305   if (hash_offlen == 0) {
 306     return FAIL;
 307   }
 308   hash_slotnm = (key_hash >> 8) % hash_offlen;
 309
 310   /* check to ensure that the file is not corrupt
 311    * if the hash_offset + (hash_offlen * CDB_HASH_ENTRY) is longer
 312    * than the file, then we have problems.... */
 313   if ((hash_offset + (hash_offlen * CDB_HASH_ENTRY)) > cdbp->filelen) {
 314     *errmsg = string_sprintf("cdb: corrupt cdb file %s (too short)",
 315                             filename);
 316     DEBUG(D_lookup) debug_printf("%s\n", *errmsg);
 317     return DEFER;
 318   }
 319
 320   cur_offset = hash_offset + (hash_slotnm * CDB_HASH_ENTRY);
 321   end_offset = hash_offset + (hash_offlen * CDB_HASH_ENTRY);
 322   /* if we are allowed to we use mmap here.... */
 323 #ifdef HAVE_MMAP
 324   /* make sure the mmap was OK */
 325   if (cdbp->cdb_map != NULL) {
 326     uschar * cur_pos = cur_offset + cdbp->cdb_map;
 327     uschar * end_pos = end_offset + cdbp->cdb_map;
 328     for (loop = 0; (loop < hash_offlen); ++loop) {
 329       item_hash = cdb_unpack(cur_pos);
 330       cur_pos += 4;
 331       item_posn = cdb_unpack(cur_pos);
 332       cur_pos += 4;
 333       /* if the position is zero then we have a definite miss */
 334       if (item_posn == 0)
 335        return FAIL;
 336
 337       if (item_hash == key_hash) {
 338        /* matching hash value */
 339        uschar * item_ptr = cdbp->cdb_map + item_posn;
 340        item_key_len = cdb_unpack(item_ptr);
 341        item_ptr += 4;
 342        item_dat_len = cdb_unpack(item_ptr);
 343        item_ptr += 4;
 344        /* check key length matches */
 345        if (item_key_len == key_len) {
 346          /* finally check if key matches */
 347          if (Ustrncmp(keystring, item_ptr, key_len) == 0) {
 348            /* we have a match....
 349             * make item_ptr point to data */
 350            item_ptr += item_key_len;
 351            /* ... and the returned result */
 352            *result = store_get(item_dat_len + 1);
 353            memcpy(*result, item_ptr, item_dat_len);
 354            (*result)[item_dat_len] = 0;
 355            return OK;
 356          }
 357        }
 358       }
 359       /* handle warp round of table */
 360       if (cur_pos == end_pos)
 361        cur_pos = cdbp->cdb_map + hash_offset;
 362     }
 363     /* looks like we failed... */
 364     return FAIL;
 365   }
 366 #endif /* HAVE_MMAP */
 367   for (loop = 0; (loop < hash_offlen); ++loop) {
 368     uschar packbuf[8];
 369     if (lseek(cdbp->fileno, (off_t) cur_offset,SEEK_SET) == -1) return DEFER;
 370     if (cdb_bread(cdbp->fileno, packbuf,8) == -1) return DEFER;
 371     item_hash = cdb_unpack(packbuf);
 372     item_posn = cdb_unpack(packbuf + 4);
 373     /* if the position is zero then we have a definite miss */
 374     if (item_posn == 0)
 375       return FAIL;
 376
 377     if (item_hash == key_hash) {
 378       /* matching hash value */
 379       if (lseek(cdbp->fileno, (off_t) item_posn, SEEK_SET) == -1) return DEFER;
 380       if (cdb_bread(cdbp->fileno, packbuf, 8) == -1) return DEFER;
 381       item_key_len = cdb_unpack(packbuf);
 382       /* check key length matches */
 383       if (item_key_len == key_len) {
 384        /* finally check if key matches */
 385        uschar * item_key = store_get(key_len);
 386        if (cdb_bread(cdbp->fileno, item_key, key_len) == -1) return DEFER;
 387        if (Ustrncmp(keystring, item_key, key_len) == 0) {
 388          /* Reclaim some store */
 389          store_reset(item_key);
 390          /* matches - get data length */
 391          item_dat_len = cdb_unpack(packbuf + 4);
 392          /* then we build a new result string */
 393          *result = store_get(item_dat_len + 1);
 394          if (cdb_bread(cdbp->fileno, *result, item_dat_len) == -1)
 395            return DEFER;
 396          (*result)[item_dat_len] = 0;
 397          return OK;
 398        }
 399        /* Reclaim some store */
 400        store_reset(item_key);
 401       }
 402     }
 403     cur_offset += 8;
 404
 405     /* handle warp round of table */
 406     if (cur_offset == end_offset)
 407       cur_offset = hash_offset;
 408   }
 409   return FAIL;
 410 }
 411
 412
 413
 414 /*************************************************
 415 *              Close entry point                 *
 416 *************************************************/
 417
 418 /* See local README for interface description */
 419
 420 static void
 421 cdb_close(void *handle)
 422 {
 423 struct cdb_state * cdbp = handle;
 424
 425 #ifdef HAVE_MMAP
 426  if (cdbp->cdb_map) {
 427    munmap(CS cdbp->cdb_map, cdbp->filelen);
 428    if (cdbp->cdb_map == cdbp->cdb_offsets)
 429      cdbp->cdb_offsets = NULL;
 430  }
 431 #endif /* HAVE_MMAP */
 432
 433  (void)close(cdbp->fileno);
 434 }
 435
 436
 437
 438 /*************************************************
 439 *         Version reporting entry point          *
 440 *************************************************/
 441
 442 /* See local README for interface description. */
 443
 444 #include "../version.h"
 445
 446 void
 447 cdb_version_report(FILE *f)
 448 {
 449 #ifdef DYNLOOKUP
 450 fprintf(f, "Library version: CDB: Exim version %s\n", EXIM_VERSION_STR);
 451 #endif
 452 }
 453
 454
 455 lookup_info cdb_lookup_info = {
 456   US"cdb",                       /* lookup name */
 457   lookup_absfile,                /* uses absolute file name */
 458   cdb_open,                      /* open function */
 459   cdb_check,                     /* check function */
 460   cdb_find,                      /* find function */
 461   cdb_close,                     /* close function */
 462   NULL,                          /* no tidy function */
 463   NULL,                          /* no quoting function */
 464   cdb_version_report             /* version reporting */
 465 };
 466
 467 #ifdef DYNLOOKUP
 468 #define cdb_lookup_module_info _lookup_module_info
 469 #endif
 470
 471 static lookup_info *_lookup_list[] = { &cdb_lookup_info };
 472 lookup_module_info cdb_lookup_module_info = { LOOKUP_MODULE_INFO_MAGIC, _lookup_list, 1 };
 473
 474 /* End of lookups/cdb.c */