5cae1535f5efb26975dbef8ca4936d7b0d33841a
[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  *
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 */