Copyright updates:
[exim.git] / src / src / lookups / cdb.c
CommitLineData
0756eb3c
PH
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
1e1ddfac 10 * Copyright (c) The Exim Maintainers 2020
0756eb3c
PH
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 * --------------------------------------------------------------
3386088d
PP
22 * Modified by The Exim Maintainers 2015:
23 * const propagation
24 * --------------------------------------------------------------
0756eb3c
PH
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 *
4c04137d 47 * There are 2 variants included within this code. One uses MMAP and
0756eb3c
PH
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"
0756eb3c
PH
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
83struct 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 */
91typedef unsigned int uint32;
92
93/*
94 * cdb_hash()
95 * Internal function to make hash value */
96
97static uint32
576bd90c 98cdb_hash(const uschar *buf, unsigned int len)
0756eb3c
PH
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
115static int
116cdb_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()
4c04137d 135 * Internal function to parse 4 byte number (endian independent) */
0756eb3c
PH
136
137static uint32
138cdb_unpack(uschar *buf)
139{
d447dbd1
JH
140uint32 num;
141num = buf[3]; num <<= 8;
142num += buf[2]; num <<= 8;
143num += buf[1]; num <<= 8;
144num += buf[0];
145return num;
0756eb3c
PH
146}
147
e6d225ae
DW
148static void cdb_close(void *handle);
149
150static void *
d447dbd1 151cdb_open(const uschar * filename, uschar ** errmsg)
0756eb3c 152{
d447dbd1
JH
153int fileno;
154struct cdb_state *cdbp;
155struct stat statbuf;
156void * mapbuf;
157
158if ((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;
0756eb3c
PH
164 }
165
d447dbd1
JH
166if (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;
0756eb3c
PH
174 }
175
d447dbd1
JH
176/* If this is a valid file, then it *must* be at least
177CDB_HASH_TABLE bytes long */
0756eb3c 178
d447dbd1
JH
179if (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 */
190cdbp = store_get(sizeof(struct cdb_state), FALSE);
191/* store_get() does not return if memory was not available... */
192/* preload the structure.... */
193cdbp->fileno = fileno;
194cdbp->filelen = statbuf.st_size;
195cdbp->cdb_map = NULL;
196cdbp->cdb_offsets = NULL;
197
198/* if we are allowed to we use mmap here.... */
0756eb3c 199#ifdef HAVE_MMAP
d447dbd1
JH
200if ((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
215back to slower methods.... However lets debug log it... */
216
217DEBUG(D_lookup) debug_printf_indent("cdb mmap failed - %d\n", errno);
0756eb3c
PH
218#endif /* HAVE_MMAP */
219
d447dbd1
JH
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
223things up a lot - especially on multiple lookups */
224
225cdbp->cdb_offsets = store_get(CDB_HASH_TABLE, FALSE);
226
227/* now fill the buffer up... */
228
229if (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;
0756eb3c
PH
239 }
240
d447dbd1
JH
241/* Everything else done - return the cache structure */
242return cdbp;
0756eb3c
PH
243}
244
245
246
247/*************************************************
248* Check entry point *
249*************************************************/
250
e6d225ae 251static BOOL
d447dbd1
JH
252cdb_check(void * handle, const uschar * filename, int modemask,
253 uid_t * owners, gid_t * owngroups, uschar ** errmsg)
0756eb3c 254{
d447dbd1
JH
255struct cdb_state * cdbp = handle;
256return lf_check_file(cdbp->fileno, filename, S_IFREG, modemask,
257 owners, owngroups, "cdb", errmsg) == 0;
0756eb3c
PH
258}
259
260
261
262/*************************************************
263* Find entry point *
264*************************************************/
265
e6d225ae 266static int
d447dbd1 267cdb_find(void * handle, const uschar * filename, const uschar * keystring,
67a57a5a
JH
268 int key_len, uschar ** result, uschar ** errmsg, uint * do_cache,
269 const uschar * opts)
0756eb3c 270{
d88f0784
JH
271struct cdb_state * cdbp = handle;
272uint32 item_key_len,
273item_dat_len,
274key_hash,
275item_hash,
276item_posn,
277cur_offset,
278end_offset,
279hash_offset_entry,
280hash_offset,
281hash_offlen,
282hash_slotnm;
d88f0784
JH
283
284/* Keep picky compilers happy */
285do_cache = do_cache;
286
287key_hash = cdb_hash(keystring, key_len);
288
289hash_offset_entry = CDB_HASH_ENTRY * (key_hash & CDB_HASH_MASK);
290hash_offset = cdb_unpack(cdbp->cdb_offsets + hash_offset_entry);
291hash_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
295if (hash_offlen == 0)
296 return FAIL;
297
298hash_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
304if ((hash_offset + (hash_offlen * CDB_HASH_ENTRY)) > cdbp->filelen)
305 {
306 *errmsg = string_sprintf("cdb: corrupt cdb file %s (too short)",
307 filename);
42c7f0b4 308 DEBUG(D_lookup) debug_printf_indent("%s\n", *errmsg);
d88f0784 309 return DEFER;
0756eb3c
PH
310 }
311
d88f0784
JH
312cur_offset = hash_offset + (hash_slotnm * CDB_HASH_ENTRY);
313end_offset = hash_offset + (hash_offlen * CDB_HASH_ENTRY);
314
315/* if we are allowed to we use mmap here.... */
316
0756eb3c 317#ifdef HAVE_MMAP
d88f0784
JH
318/* make sure the mmap was OK */
319if (cdbp->cdb_map != NULL)
320 {
321 uschar * cur_pos = cur_offset + cdbp->cdb_map;
322 uschar * end_pos = end_offset + cdbp->cdb_map;
323
d7978c0f 324 for (int loop = 0; (loop < hash_offlen); ++loop)
d88f0784
JH
325 {
326 item_hash = cdb_unpack(cur_pos);
327 cur_pos += 4;
328 item_posn = cdb_unpack(cur_pos);
329 cur_pos += 4;
330
0756eb3c 331 /* if the position is zero then we have a definite miss */
d88f0784 332
0756eb3c
PH
333 if (item_posn == 0)
334 return FAIL;
335
d88f0784
JH
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
0756eb3c 345 /* check key length matches */
d88f0784
JH
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
f3ebb786
JH
356 /* ... and the returned result. Assume it is not
357 tainted, lacking any way of telling. */
d88f0784 358
f3ebb786 359 *result = store_get(item_dat_len + 1, FALSE);
d88f0784
JH
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
d7978c0f 376for (int loop = 0; (loop < hash_offlen); ++loop)
d88f0784
JH
377 {
378 uschar packbuf[8];
379
d315eda1
JH
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;
d88f0784
JH
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 */
f3ebb786
JH
402 rmark reset_point = store_mark();
403 uschar * item_key = store_get(key_len, TRUE); /* keys liable to be tainted */
d88f0784
JH
404
405 if (cdb_bread(cdbp->fileno, item_key, key_len) == -1) return DEFER;
f3ebb786
JH
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 }
d88f0784 426 /* Reclaim some store */
f3ebb786 427 store_reset(reset_point);
0756eb3c
PH
428 }
429 }
d88f0784 430 cur_offset += 8;
0756eb3c 431
d88f0784
JH
432 /* handle warp round of table */
433 if (cur_offset == end_offset)
434 cur_offset = hash_offset;
0756eb3c 435 }
d88f0784 436return FAIL;
0756eb3c
PH
437}
438
439
440
441/*************************************************
442* Close entry point *
443*************************************************/
444
445/* See local README for interface description */
446
e6d225ae 447static void
0756eb3c
PH
448cdb_close(void *handle)
449{
450struct cdb_state * cdbp = handle;
451
452#ifdef HAVE_MMAP
d7978c0f
JH
453if (cdbp->cdb_map)
454 {
455 munmap(CS cdbp->cdb_map, cdbp->filelen);
456 if (cdbp->cdb_map == cdbp->cdb_offsets)
0756eb3c 457 cdbp->cdb_offsets = NULL;
d7978c0f 458 }
0756eb3c
PH
459#endif /* HAVE_MMAP */
460
d7978c0f 461(void)close(cdbp->fileno);
0756eb3c
PH
462}
463
6545de78
PP
464
465
466/*************************************************
467* Version reporting entry point *
468*************************************************/
469
470/* See local README for interface description. */
471
472#include "../version.h"
473
474void
475cdb_version_report(FILE *f)
476{
477#ifdef DYNLOOKUP
478fprintf(f, "Library version: CDB: Exim version %s\n", EXIM_VERSION_STR);
479#endif
480}
481
482
e6d225ae 483lookup_info cdb_lookup_info = {
9f400174
JH
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 */
e6d225ae
DW
493};
494
495#ifdef DYNLOOKUP
496#define cdb_lookup_module_info _lookup_module_info
497#endif
498
499static lookup_info *_lookup_list[] = { &cdb_lookup_info };
500lookup_module_info cdb_lookup_module_info = { LOOKUP_MODULE_INFO_MAGIC, _lookup_list, 1 };
501
0756eb3c 502/* End of lookups/cdb.c */