Use C99 initialisations for iterators
[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));
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("cdb mmap failed - %d\n", errno);
219 }
220 #endif /* HAVE_MMAP */
221
222 /* In this case we have either not got MMAP allowed, or it failed */
223
224 /* get a buffer to stash the basic offsets in - this should speed
225 * things up a lot - especially on multiple lookups */
226 cdbp->cdb_offsets = store_get(CDB_HASH_TABLE);
227
228 /* now fill the buffer up... */
229 if (cdb_bread(fileno, cdbp->cdb_offsets, CDB_HASH_TABLE) == -1) {
230 /* read of hash table failed, oh dear, oh.....
231 * time to give up I think....
232 * call the close routine (deallocs the memory), and return NULL */
233 *errmsg = string_open_failed(errno,
234 "cannot read header from %s for cdb lookup",
235 filename);
236 cdb_close(cdbp);
237 return NULL;
238 }
239
240 /* Everything else done - return the cache structure */
241 return cdbp;
242 }
243
244
245
246 /*************************************************
247 * Check entry point *
248 *************************************************/
249
250 static BOOL
251 cdb_check(void *handle,
252 uschar *filename,
253 int modemask,
254 uid_t *owners,
255 gid_t *owngroups,
256 uschar **errmsg)
257 {
258 struct cdb_state * cdbp = handle;
259 return lf_check_file(cdbp->fileno,
260 filename,
261 S_IFREG,
262 modemask,
263 owners,
264 owngroups,
265 "cdb",
266 errmsg) == 0;
267 }
268
269
270
271 /*************************************************
272 * Find entry point *
273 *************************************************/
274
275 static int
276 cdb_find(void *handle,
277 uschar *filename,
278 const uschar *keystring,
279 int key_len,
280 uschar **result,
281 uschar **errmsg,
282 uint *do_cache)
283 {
284 struct cdb_state * cdbp = handle;
285 uint32 item_key_len,
286 item_dat_len,
287 key_hash,
288 item_hash,
289 item_posn,
290 cur_offset,
291 end_offset,
292 hash_offset_entry,
293 hash_offset,
294 hash_offlen,
295 hash_slotnm;
296
297 /* Keep picky compilers happy */
298 do_cache = do_cache;
299
300 key_hash = cdb_hash(keystring, key_len);
301
302 hash_offset_entry = CDB_HASH_ENTRY * (key_hash & CDB_HASH_MASK);
303 hash_offset = cdb_unpack(cdbp->cdb_offsets + hash_offset_entry);
304 hash_offlen = cdb_unpack(cdbp->cdb_offsets + hash_offset_entry + 4);
305
306 /* If the offset length is zero this key cannot be in the file */
307
308 if (hash_offlen == 0)
309 return FAIL;
310
311 hash_slotnm = (key_hash >> 8) % hash_offlen;
312
313 /* check to ensure that the file is not corrupt
314 * if the hash_offset + (hash_offlen * CDB_HASH_ENTRY) is longer
315 * than the file, then we have problems.... */
316
317 if ((hash_offset + (hash_offlen * CDB_HASH_ENTRY)) > cdbp->filelen)
318 {
319 *errmsg = string_sprintf("cdb: corrupt cdb file %s (too short)",
320 filename);
321 DEBUG(D_lookup) debug_printf("%s\n", *errmsg);
322 return DEFER;
323 }
324
325 cur_offset = hash_offset + (hash_slotnm * CDB_HASH_ENTRY);
326 end_offset = hash_offset + (hash_offlen * CDB_HASH_ENTRY);
327
328 /* if we are allowed to we use mmap here.... */
329
330 #ifdef HAVE_MMAP
331 /* make sure the mmap was OK */
332 if (cdbp->cdb_map != NULL)
333 {
334 uschar * cur_pos = cur_offset + cdbp->cdb_map;
335 uschar * end_pos = end_offset + cdbp->cdb_map;
336
337 for (int loop = 0; (loop < hash_offlen); ++loop)
338 {
339 item_hash = cdb_unpack(cur_pos);
340 cur_pos += 4;
341 item_posn = cdb_unpack(cur_pos);
342 cur_pos += 4;
343
344 /* if the position is zero then we have a definite miss */
345
346 if (item_posn == 0)
347 return FAIL;
348
349 if (item_hash == key_hash)
350 { /* matching hash value */
351 uschar * item_ptr = cdbp->cdb_map + item_posn;
352
353 item_key_len = cdb_unpack(item_ptr);
354 item_ptr += 4;
355 item_dat_len = cdb_unpack(item_ptr);
356 item_ptr += 4;
357
358 /* check key length matches */
359
360 if (item_key_len == key_len)
361 {
362 /* finally check if key matches */
363 if (Ustrncmp(keystring, item_ptr, key_len) == 0)
364 {
365 /* we have a match.... * make item_ptr point to data */
366
367 item_ptr += item_key_len;
368
369 /* ... and the returned result */
370
371 *result = store_get(item_dat_len + 1);
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 uschar * item_key = store_get(key_len);
415
416 if (cdb_bread(cdbp->fileno, item_key, key_len) == -1) return DEFER;
417 if (Ustrncmp(keystring, item_key, key_len) == 0) {
418
419 /* Reclaim some store */
420 store_reset(item_key);
421
422 /* matches - get data length */
423 item_dat_len = cdb_unpack(packbuf + 4);
424
425 /* then we build a new result string. We know we have enough
426 memory so disable Coverity errors about the tainted item_dat_ken */
427
428 *result = store_get(item_dat_len + 1);
429 /* coverity[tainted_data] */
430 if (cdb_bread(cdbp->fileno, *result, item_dat_len) == -1)
431 return DEFER;
432
433 /* coverity[tainted_data] */
434 (*result)[item_dat_len] = 0;
435 return OK;
436 }
437 /* Reclaim some store */
438 store_reset(item_key);
439 }
440 }
441 cur_offset += 8;
442
443 /* handle warp round of table */
444 if (cur_offset == end_offset)
445 cur_offset = hash_offset;
446 }
447 return FAIL;
448 }
449
450
451
452 /*************************************************
453 * Close entry point *
454 *************************************************/
455
456 /* See local README for interface description */
457
458 static void
459 cdb_close(void *handle)
460 {
461 struct cdb_state * cdbp = handle;
462
463 #ifdef HAVE_MMAP
464 if (cdbp->cdb_map)
465 {
466 munmap(CS cdbp->cdb_map, cdbp->filelen);
467 if (cdbp->cdb_map == cdbp->cdb_offsets)
468 cdbp->cdb_offsets = NULL;
469 }
470 #endif /* HAVE_MMAP */
471
472 (void)close(cdbp->fileno);
473 }
474
475
476
477 /*************************************************
478 * Version reporting entry point *
479 *************************************************/
480
481 /* See local README for interface description. */
482
483 #include "../version.h"
484
485 void
486 cdb_version_report(FILE *f)
487 {
488 #ifdef DYNLOOKUP
489 fprintf(f, "Library version: CDB: Exim version %s\n", EXIM_VERSION_STR);
490 #endif
491 }
492
493
494 lookup_info cdb_lookup_info = {
495 US"cdb", /* lookup name */
496 lookup_absfile, /* uses absolute file name */
497 cdb_open, /* open function */
498 cdb_check, /* check function */
499 cdb_find, /* find function */
500 cdb_close, /* close function */
501 NULL, /* no tidy function */
502 NULL, /* no quoting function */
503 cdb_version_report /* version reporting */
504 };
505
506 #ifdef DYNLOOKUP
507 #define cdb_lookup_module_info _lookup_module_info
508 #endif
509
510 static lookup_info *_lookup_list[] = { &cdb_lookup_info };
511 lookup_module_info cdb_lookup_module_info = { LOOKUP_MODULE_INFO_MAGIC, _lookup_list, 1 };
512
513 /* End of lookups/cdb.c */