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
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.
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 * --------------------------------------------------------------
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.
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
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
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.
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
56 #include "lf_functions.h"
59 # include <sys/mman.h>
60 /* Not all implementations declare MAP_FAILED */
62 # define MAP_FAILED ((void *) -1)
63 # endif /* MAP_FAILED */
64 #endif /* HAVE_MMAP */
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)
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....
86 /* 32 bit unsigned type - this is an int on all modern machines */
87 typedef unsigned int uint32
;
91 * Internal function to make hash value */
94 cdb_hash(uschar
*buf
, unsigned int len
)
102 h
^= (uint32
) *buf
++;
109 * Internal function to read len bytes from disk, coping with oddities */
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; }
131 * Internal function to parse 4 byte number (endian independant) */
134 cdb_unpack(uschar
*buf
)
137 num
= buf
[3]; num
<<= 8;
138 num
+= buf
[2]; num
<<= 8;
139 num
+= buf
[1]; num
<<= 8;
144 static void cdb_close(void *handle
);
147 cdb_open(uschar
*filename
,
151 struct cdb_state
*cdbp
;
155 fileno
= Uopen(filename
, O_RDONLY
, 0);
157 int save_errno
= errno
;
158 *errmsg
= string_open_failed(errno
, "%s for cdb lookup", filename
);
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",
175 int save_errno
= errno
;
176 *errmsg
= string_open_failed(errno
,
177 "fstat(%s) failed - cannot do cdb lookup",
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
;
192 /* if we are allowed to we use mmap here.... */
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
206 cdbp
->cdb_offsets
= mapbuf
;
208 /* Now return the state struct */
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...
215 DEBUG(D_lookup
) debug_printf("cdb mmap failed - %d\n", errno
);
217 #endif /* HAVE_MMAP */
219 /* In this case we have either not got MMAP allowed, or it failed */
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
);
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",
237 /* Everything else done - return the cache structure */
243 /*************************************************
244 * Check entry point *
245 *************************************************/
248 cdb_check(void *handle
,
255 struct cdb_state
* cdbp
= handle
;
256 return lf_check_file(cdbp
->fileno
,
268 /*************************************************
270 *************************************************/
273 cdb_find(void *handle
,
281 struct cdb_state
* cdbp
= handle
;
295 /* Keep picky compilers happy */
298 key_hash
= cdb_hash((uschar
*)keystring
, key_len
);
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);
304 /* If the offset length is zero this key cannot be in the file */
305 if (hash_offlen
== 0) {
308 hash_slotnm
= (key_hash
>> 8) % hash_offlen
;
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)",
316 DEBUG(D_lookup
) debug_printf("%s\n", *errmsg
);
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.... */
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
);
331 item_posn
= cdb_unpack(cur_pos
);
333 /* if the position is zero then we have a definite miss */
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
);
342 item_dat_len
= cdb_unpack(item_ptr
);
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;
359 /* handle warp round of table */
360 if (cur_pos
== end_pos
)
361 cur_pos
= cdbp
->cdb_map
+ hash_offset
;
363 /* looks like we failed... */
366 #endif /* HAVE_MMAP */
367 for (loop
= 0; (loop
< hash_offlen
); ++loop
) {
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 */
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)
396 (*result
)[item_dat_len
] = 0;
399 /* Reclaim some store */
400 store_reset(item_key
);
405 /* handle warp round of table */
406 if (cur_offset
== end_offset
)
407 cur_offset
= hash_offset
;
414 /*************************************************
415 * Close entry point *
416 *************************************************/
418 /* See local README for interface description */
421 cdb_close(void *handle
)
423 struct cdb_state
* cdbp
= handle
;
427 munmap(CS cdbp
->cdb_map
, cdbp
->filelen
);
428 if (cdbp
->cdb_map
== cdbp
->cdb_offsets
)
429 cdbp
->cdb_offsets
= NULL
;
431 #endif /* HAVE_MMAP */
433 (void)close(cdbp
->fileno
);
438 /*************************************************
439 * Version reporting entry point *
440 *************************************************/
442 /* See local README for interface description. */
444 #include "../version.h"
447 cdb_version_report(FILE *f
)
450 fprintf(f
, "Library version: CDB: Exim version %s\n", EXIM_VERSION_STR
);
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 */
468 #define cdb_lookup_module_info _lookup_module_info
471 static lookup_info
*_lookup_list
[] = { &cdb_lookup_info
};
472 lookup_module_info cdb_lookup_module_info
= { LOOKUP_MODULE_INFO_MAGIC
, _lookup_list
, 1 };
474 /* End of lookups/cdb.c */