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