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