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