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