1 /*************************************************
2 * Exim - an Internet mail transport agent *
3 *************************************************/
6 * Exim - CDB database lookup module
7 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
9 * Copyright (c) 1998 Nigel Metheringham, Planet Online Ltd
10 * Copyright (c) The Exim Maintainers 2020
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.
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:
24 * --------------------------------------------------------------
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.
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
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
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.
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
60 #include "lf_functions.h"
63 # include <sys/mman.h>
64 /* Not all implementations declare MAP_FAILED */
66 # define MAP_FAILED ((void *) -1)
67 # endif /* MAP_FAILED */
68 #endif /* HAVE_MMAP */
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)
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....
90 /* 32 bit unsigned type - this is an int on all modern machines */
91 typedef unsigned int uint32
;
95 * Internal function to make hash value */
98 cdb_hash(const uschar
*buf
, unsigned int len
)
106 h
^= (uint32
) *buf
++;
113 * Internal function to read len bytes from disk, coping with oddities */
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; }
135 * Internal function to parse 4 byte number (endian independent) */
138 cdb_unpack(uschar
*buf
)
141 num
= buf
[3]; num
<<= 8;
142 num
+= buf
[2]; num
<<= 8;
143 num
+= buf
[1]; num
<<= 8;
148 static void cdb_close(void *handle
);
151 cdb_open(const uschar
* filename
, uschar
** errmsg
)
154 struct cdb_state
*cdbp
;
158 if ((fileno
= Uopen(filename
, O_RDONLY
, 0)) < 0)
160 int save_errno
= errno
;
161 *errmsg
= string_open_failed(errno
, "%s for cdb lookup", filename
);
166 if (fstat(fileno
, &statbuf
) != 0)
168 int save_errno
= errno
;
169 *errmsg
= string_open_failed(errno
,
170 "fstat(%s) failed - cannot do cdb lookup",
176 /* If this is a valid file, then it *must* be at least
177 CDB_HASH_TABLE bytes long */
179 if (statbuf
.st_size
< CDB_HASH_TABLE
)
181 int save_errno
= errno
;
182 *errmsg
= string_open_failed(errno
,
183 "%s too short for cdb lookup",
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
;
198 /* if we are allowed to we use mmap here.... */
200 if ((mapbuf
= mmap(NULL
, statbuf
.st_size
, PROT_READ
, MAP_SHARED
, fileno
, 0))
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
208 cdbp
->cdb_offsets
= mapbuf
;
210 /* Now return the state struct */
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... */
217 DEBUG(D_lookup
) debug_printf_indent("cdb mmap failed - %d\n", errno
);
218 #endif /* HAVE_MMAP */
220 /* In this case we have either not got MMAP allowed, or it failed */
222 /* get a buffer to stash the basic offsets in - this should speed
223 things up a lot - especially on multiple lookups */
225 cdbp
->cdb_offsets
= store_get(CDB_HASH_TABLE
, FALSE
);
227 /* now fill the buffer up... */
229 if (cdb_bread(fileno
, cdbp
->cdb_offsets
, CDB_HASH_TABLE
) == -1)
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 */
234 *errmsg
= string_open_failed(errno
,
235 "cannot read header from %s for cdb lookup",
241 /* Everything else done - return the cache structure */
247 /*************************************************
248 * Check entry point *
249 *************************************************/
252 cdb_check(void * handle
, const uschar
* filename
, int modemask
,
253 uid_t
* owners
, gid_t
* owngroups
, uschar
** errmsg
)
255 struct cdb_state
* cdbp
= handle
;
256 return lf_check_file(cdbp
->fileno
, filename
, S_IFREG
, modemask
,
257 owners
, owngroups
, "cdb", errmsg
) == 0;
262 /*************************************************
264 *************************************************/
267 cdb_find(void * handle
, const uschar
* filename
, const uschar
* keystring
,
268 int key_len
, uschar
** result
, uschar
** errmsg
, uint
* do_cache
,
271 struct cdb_state
* cdbp
= handle
;
284 /* Keep picky compilers happy */
287 key_hash
= cdb_hash(keystring
, key_len
);
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);
293 /* If the offset length is zero this key cannot be in the file */
295 if (hash_offlen
== 0)
298 hash_slotnm
= (key_hash
>> 8) % hash_offlen
;
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.... */
304 if ((hash_offset
+ (hash_offlen
* CDB_HASH_ENTRY
)) > cdbp
->filelen
)
306 *errmsg
= string_sprintf("cdb: corrupt cdb file %s (too short)",
308 DEBUG(D_lookup
) debug_printf_indent("%s\n", *errmsg
);
312 cur_offset
= hash_offset
+ (hash_slotnm
* CDB_HASH_ENTRY
);
313 end_offset
= hash_offset
+ (hash_offlen
* CDB_HASH_ENTRY
);
315 /* if we are allowed to we use mmap here.... */
318 /* make sure the mmap was OK */
319 if (cdbp
->cdb_map
!= NULL
)
321 uschar
* cur_pos
= cur_offset
+ cdbp
->cdb_map
;
322 uschar
* end_pos
= end_offset
+ cdbp
->cdb_map
;
324 for (int loop
= 0; (loop
< hash_offlen
); ++loop
)
326 item_hash
= cdb_unpack(cur_pos
);
328 item_posn
= cdb_unpack(cur_pos
);
331 /* if the position is zero then we have a definite miss */
336 if (item_hash
== key_hash
)
337 { /* matching hash value */
338 uschar
* item_ptr
= cdbp
->cdb_map
+ item_posn
;
340 item_key_len
= cdb_unpack(item_ptr
);
342 item_dat_len
= cdb_unpack(item_ptr
);
345 /* check key length matches */
347 if (item_key_len
== key_len
)
349 /* finally check if key matches */
350 if (Ustrncmp(keystring
, item_ptr
, key_len
) == 0)
352 /* we have a match.... * make item_ptr point to data */
354 item_ptr
+= item_key_len
;
356 /* ... and the returned result. Assume it is not
357 tainted, lacking any way of telling. */
359 *result
= store_get(item_dat_len
+ 1, FALSE
);
360 memcpy(*result
, item_ptr
, item_dat_len
);
361 (*result
)[item_dat_len
] = 0;
366 /* handle warp round of table */
367 if (cur_pos
== end_pos
)
368 cur_pos
= cdbp
->cdb_map
+ hash_offset
;
370 /* looks like we failed... */
374 #endif /* HAVE_MMAP */
376 for (int loop
= 0; (loop
< hash_offlen
); ++loop
)
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
;
383 item_hash
= cdb_unpack(packbuf
);
384 item_posn
= cdb_unpack(packbuf
+ 4);
386 /* if the position is zero then we have a definite miss */
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
;
396 item_key_len
= cdb_unpack(packbuf
);
398 /* check key length matches */
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 */
405 if (cdb_bread(cdbp
->fileno
, item_key
, key_len
) == -1) return DEFER
;
406 if (Ustrncmp(keystring
, item_key
, key_len
) == 0)
408 /* Reclaim some store */
409 store_reset(reset_point
);
411 /* matches - get data length */
412 item_dat_len
= cdb_unpack(packbuf
+ 4);
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 */
417 *result
= store_get(item_dat_len
+ 1, FALSE
);
418 /* coverity[tainted_data] */
419 if (cdb_bread(cdbp
->fileno
, *result
, item_dat_len
) == -1)
422 /* coverity[tainted_data] */
423 (*result
)[item_dat_len
] = 0;
426 /* Reclaim some store */
427 store_reset(reset_point
);
432 /* handle warp round of table */
433 if (cur_offset
== end_offset
)
434 cur_offset
= hash_offset
;
441 /*************************************************
442 * Close entry point *
443 *************************************************/
445 /* See local README for interface description */
448 cdb_close(void *handle
)
450 struct cdb_state
* cdbp
= handle
;
455 munmap(CS cdbp
->cdb_map
, cdbp
->filelen
);
456 if (cdbp
->cdb_map
== cdbp
->cdb_offsets
)
457 cdbp
->cdb_offsets
= NULL
;
459 #endif /* HAVE_MMAP */
461 (void)close(cdbp
->fileno
);
466 /*************************************************
467 * Version reporting entry point *
468 *************************************************/
470 /* See local README for interface description. */
472 #include "../version.h"
475 cdb_version_report(FILE *f
)
478 fprintf(f
, "Library version: CDB: Exim version %s\n", EXIM_VERSION_STR
);
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 */
496 #define cdb_lookup_module_info _lookup_module_info
499 static lookup_info
*_lookup_list
[] = { &cdb_lookup_info
};
500 lookup_module_info cdb_lookup_module_info
= { LOOKUP_MODULE_INFO_MAGIC
, _lookup_list
, 1 };
502 /* End of lookups/cdb.c */