3a95f8ed0200948575cf67cc4db45b090baf9921
[users/heiko/exim.git] / 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 */