Line data Source code
1 : /* cdblib.c - all CDB library functions.
2 : *
3 : * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
4 : * Public domain.
5 : *
6 : * Taken from tinycdb-0.73 and merged into one file for easier
7 : * inclusion into Dirmngr. By Werner Koch <wk@gnupg.org> 2003-12-12.
8 : */
9 :
10 : /* A cdb database is a single file used to map 'keys' to 'values',
11 : having records of (key,value) pairs. File consists of 3 parts: toc
12 : (table of contents), data and index (hash tables).
13 :
14 : Toc has fixed length of 2048 bytes, containing 256 pointers to hash
15 : tables inside index sections. Every pointer consists of position
16 : of a hash table in bytes from the beginning of a file, and a size
17 : of a hash table in entries, both are 4-bytes (32 bits) unsigned
18 : integers in little-endian form. Hash table length may have zero
19 : length, meaning that corresponding hash table is empty.
20 :
21 : Right after toc section, data section follows without any
22 : alingment. It consists of series of records, each is a key length,
23 : value (data) length, key and value. Again, key and value length
24 : are 4-byte unsigned integers. Each next record follows previous
25 : without any special alignment.
26 :
27 : After data section, index (hash tables) section follows. It should
28 : be looked to in conjunction with toc section, where each of max 256
29 : hash tables are defined. Index section consists of series of hash
30 : tables, with starting position and length defined in toc section.
31 : Every hash table is a sequence of records each holds two numbers:
32 : key's hash value and record position inside data section (bytes
33 : from the beginning of a file to first byte of key length starting
34 : data record). If record position is zero, then this is an empty
35 : hash table slot, pointed to nowhere.
36 :
37 : CDB hash function is
38 : hv = ((hv << 5) + hv) ^ c
39 : for every single c byte of a key, starting with hv = 5381.
40 :
41 : Toc section indexed by (hv % 256), i.e. hash value modulo 256
42 : (number of entries in toc section).
43 :
44 : In order to find a record, one should: first, compute the hash
45 : value (hv) of a key. Second, look to hash table number hv modulo
46 : 256. If it is empty, then there is no such key exists. If it is
47 : not empty, then third, loop by slots inside that hash table,
48 : starting from slot with number hv divided by 256 modulo length of
49 : that table, or ((hv / 256) % htlen), searching for this hv in hash
50 : table. Stop search on empty slot (if record position is zero) or
51 : when all slots was probed (note cyclic search, jumping from end to
52 : beginning of a table). When hash value in question is found in
53 : hash table, look to key of corresponding record, comparing it with
54 : key in question. If them of the same length and equals to each
55 : other, then record is found, overwise, repeat with next hash table
56 : slot. Note that there may be several records with the same key.
57 : */
58 :
59 : #ifdef HAVE_CONFIG_H
60 : #include <config.h>
61 : #endif
62 : #include <stdlib.h>
63 : #include <errno.h>
64 : #include <string.h>
65 : #include <unistd.h>
66 : #include <sys/types.h>
67 : #ifdef _WIN32
68 : # include <windows.h>
69 : #else
70 : # include <sys/mman.h>
71 : # ifndef MAP_FAILED
72 : # define MAP_FAILED ((void*)-1)
73 : # endif
74 : #endif
75 : #include <sys/stat.h>
76 :
77 : #include "dirmngr-err.h"
78 : #include "cdb.h"
79 :
80 : #ifndef EPROTO
81 : # define EPROTO EINVAL
82 : #endif
83 : #ifndef SEEK_SET
84 : # define SEEK_SET 0
85 : #endif
86 :
87 :
88 : struct cdb_rec {
89 : cdbi_t hval;
90 : cdbi_t rpos;
91 : };
92 :
93 : struct cdb_rl {
94 : struct cdb_rl *next;
95 : cdbi_t cnt;
96 : struct cdb_rec rec[254];
97 : };
98 :
99 : static int make_find(struct cdb_make *cdbmp,
100 : const void *key, cdbi_t klen, cdbi_t hval,
101 : struct cdb_rl **rlp);
102 : static int make_write(struct cdb_make *cdbmp,
103 : const char *ptr, cdbi_t len);
104 :
105 :
106 :
107 : /* Initializes structure given by CDBP pointer and associates it with
108 : the open file descriptor FD. Allocate memory for the structure
109 : itself if needed and file open operation should be done by
110 : application. File FD should be opened at least read-only, and
111 : should be seekable. Routine returns 0 on success or negative value
112 : on error. */
113 : int
114 0 : cdb_init(struct cdb *cdbp, int fd)
115 : {
116 : struct stat st;
117 : unsigned char *mem;
118 : #ifdef _WIN32
119 : HANDLE hFile, hMapping;
120 : #else
121 : unsigned int fsize;
122 : #endif
123 :
124 : /* get file size */
125 0 : if (fstat(fd, &st) < 0)
126 0 : return -1;
127 : /* trivial sanity check: at least toc should be here */
128 0 : if (st.st_size < 2048) {
129 0 : gpg_err_set_errno (EPROTO);
130 0 : return -1;
131 : }
132 : /* memory-map file */
133 : #ifdef _WIN32
134 : # ifdef __MINGW32CE__
135 : hFile = fd;
136 : # else
137 : hFile = (HANDLE) _get_osfhandle(fd);
138 : # endif
139 : if (hFile == (HANDLE) -1)
140 : return -1;
141 : hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
142 : if (!hMapping)
143 : return -1;
144 : mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
145 : if (!mem)
146 : return -1;
147 : cdbp->cdb_mapping = hMapping;
148 : #else /*!_WIN32*/
149 0 : fsize = (unsigned int)(st.st_size & 0xffffffffu);
150 0 : mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
151 0 : if (mem == MAP_FAILED)
152 0 : return -1;
153 : #endif /*!_WIN32*/
154 :
155 0 : cdbp->cdb_fd = fd;
156 0 : cdbp->cdb_fsize = st.st_size;
157 0 : cdbp->cdb_mem = mem;
158 :
159 : #if 0
160 : /* XXX don't know well about madvise syscall -- is it legal
161 : to set different options for parts of one mmap() region?
162 : There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc...
163 : */
164 : #ifdef MADV_RANDOM
165 : /* set madvise() parameters. Ignore errors for now if system
166 : doesn't support it */
167 : madvise(mem, 2048, MADV_WILLNEED);
168 : madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM);
169 : #endif
170 : #endif
171 :
172 0 : cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
173 :
174 0 : return 0;
175 : }
176 :
177 :
178 : /* Frees the internal resources held by structure. Note that this
179 : routine does not close the file. */
180 : void
181 0 : cdb_free(struct cdb *cdbp)
182 : {
183 0 : if (cdbp->cdb_mem) {
184 : #ifdef _WIN32
185 : UnmapViewOfFile ((void*) cdbp->cdb_mem);
186 : CloseHandle (cdbp->cdb_mapping);
187 : cdbp->cdb_mapping = NULL;
188 : #else
189 0 : munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
190 : #endif /* _WIN32 */
191 0 : cdbp->cdb_mem = NULL;
192 : }
193 0 : cdbp->cdb_fsize = 0;
194 0 : }
195 :
196 :
197 : /* Read data from cdb file, starting at position pos of length len,
198 : placing result to buf. This routine may be used to get actual
199 : value found by cdb_find() or other routines that returns position
200 : and length of a data. Returns 0 on success or negative value on
201 : error. */
202 : int
203 0 : cdb_read(const struct cdb *cdbp, void *buf, unsigned len, cdbi_t pos)
204 : {
205 0 : if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) {
206 0 : gpg_err_set_errno (EPROTO);
207 0 : return -1;
208 : }
209 0 : memcpy(buf, cdbp->cdb_mem + pos, len);
210 0 : return 0;
211 : }
212 :
213 :
214 : /* Attempts to find a key given by (key,klen) parameters. If key
215 : exists in database, routine returns 1 and places position and
216 : length of value associated with this key to internal fields inside
217 : cdbp structure, to be accessible by cdb_datapos() and
218 : cdb_datalen(). If key is not in database, routines returns 0. On
219 : error, negative value is returned. Note that using cdb_find() it
220 : is possible to lookup only first record with a given key. */
221 : int
222 0 : cdb_find(struct cdb *cdbp, const void *key, cdbi_t klen)
223 : {
224 : const unsigned char *htp; /* hash table pointer */
225 : const unsigned char *htab; /* hash table */
226 : const unsigned char *htend; /* end of hash table */
227 : cdbi_t httodo; /* ht bytes left to look */
228 : cdbi_t pos, n;
229 :
230 : cdbi_t hval;
231 :
232 0 : if (klen > cdbp->cdb_fsize) /* if key size is larger than file */
233 0 : return 0;
234 :
235 0 : hval = cdb_hash(key, klen);
236 :
237 : /* find (pos,n) hash table to use */
238 : /* first 2048 bytes (toc) are always available */
239 : /* (hval % 256) * 8 */
240 0 : htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
241 0 : n = cdb_unpack(htp + 4); /* table size */
242 0 : if (!n) /* empty table */
243 0 : return 0; /* not found */
244 0 : httodo = n << 3; /* bytes of htab to lookup */
245 0 : pos = cdb_unpack(htp); /* htab position */
246 0 : if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
247 0 : || pos > cdbp->cdb_fsize /* htab start within file ? */
248 0 : || httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
249 : {
250 0 : gpg_err_set_errno (EPROTO);
251 0 : return -1;
252 : }
253 :
254 0 : htab = cdbp->cdb_mem + pos; /* htab pointer */
255 0 : htend = htab + httodo; /* after end of htab */
256 : /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
257 0 : htp = htab + (((hval >> 8) % n) << 3);
258 :
259 : for(;;) {
260 0 : pos = cdb_unpack(htp + 4); /* record position */
261 0 : if (!pos)
262 0 : return 0;
263 0 : if (cdb_unpack(htp) == hval) {
264 0 : if (pos > cdbp->cdb_fsize - 8) { /* key+val lengths */
265 0 : gpg_err_set_errno (EPROTO);
266 0 : return -1;
267 : }
268 0 : if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
269 0 : if (cdbp->cdb_fsize - klen < pos + 8) {
270 0 : gpg_err_set_errno (EPROTO);
271 0 : return -1;
272 : }
273 0 : if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
274 0 : n = cdb_unpack(cdbp->cdb_mem + pos + 4);
275 0 : pos += 8 + klen;
276 0 : if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
277 0 : gpg_err_set_errno (EPROTO);
278 0 : return -1;
279 : }
280 0 : cdbp->cdb_vpos = pos;
281 0 : cdbp->cdb_vlen = n;
282 0 : return 1;
283 : }
284 : }
285 : }
286 0 : httodo -= 8;
287 0 : if (!httodo)
288 0 : return 0;
289 0 : if ((htp += 8) >= htend)
290 0 : htp = htab;
291 0 : }
292 :
293 : }
294 :
295 :
296 :
297 : /* Sequential-find routines that used separate structure. It is
298 : possible to have many than one record with the same key in a
299 : database, and these routines allows to enumerate all them.
300 : cdb_findinit() initializes search structure pointed to by cdbfp.
301 : It will return negative value on error or 0 on success. cdb_find
302 : next() attempts to find next matching key, setting value position
303 : and length in cdbfp structure. It will return positive value if
304 : given key was found, 0 if there is no more such key(s), or negative
305 : value on error. To access value position and length after
306 : successeful call to cdb_findnext() (when it returned positive
307 : result), use cdb_datapos() and cdb_datalen() macros with cdbp
308 : pointer. It is error to use cdb_findnext() after it returned 0 or
309 : error condition. These routines is a bit slower than
310 : cdb_find().
311 :
312 : Setting KEY to NULL will start a sequential search through the
313 : entire DB.
314 : */
315 : int
316 0 : cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
317 : const void *key, cdbi_t klen)
318 : {
319 : cdbi_t n, pos;
320 :
321 0 : cdbfp->cdb_cdbp = cdbp;
322 0 : cdbfp->cdb_key = key;
323 0 : cdbfp->cdb_klen = klen;
324 0 : cdbfp->cdb_hval = key? cdb_hash(key, klen) : 0;
325 :
326 0 : if (key)
327 : {
328 0 : cdbfp->cdb_htp = cdbp->cdb_mem + ((cdbfp->cdb_hval << 3) & 2047);
329 0 : n = cdb_unpack(cdbfp->cdb_htp + 4);
330 0 : cdbfp->cdb_httodo = n << 3; /* Set to size of hash table. */
331 0 : if (!n)
332 0 : return 0; /* The hash table is empry. */
333 0 : pos = cdb_unpack(cdbfp->cdb_htp);
334 0 : if (n > (cdbp->cdb_fsize >> 3)
335 0 : || pos > cdbp->cdb_fsize
336 0 : || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
337 : {
338 0 : gpg_err_set_errno (EPROTO);
339 0 : return -1;
340 : }
341 :
342 0 : cdbfp->cdb_htab = cdbp->cdb_mem + pos;
343 0 : cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
344 0 : cdbfp->cdb_htp = cdbfp->cdb_htab + (((cdbfp->cdb_hval >> 8) % n) << 3);
345 : }
346 : else /* Walk over all entries. */
347 : {
348 0 : cdbfp->cdb_hval = 0;
349 : /* Force stepping in findnext. */
350 0 : cdbfp->cdb_htp = cdbfp->cdb_htend = cdbp->cdb_mem;
351 : }
352 0 : return 0;
353 : }
354 :
355 :
356 : /* See cdb_findinit. */
357 : int
358 0 : cdb_findnext(struct cdb_find *cdbfp)
359 : {
360 : cdbi_t pos, n;
361 0 : struct cdb *cdbp = cdbfp->cdb_cdbp;
362 :
363 0 : if (cdbfp->cdb_key)
364 : {
365 0 : while(cdbfp->cdb_httodo) {
366 0 : pos = cdb_unpack(cdbfp->cdb_htp + 4);
367 0 : if (!pos)
368 0 : return 0;
369 0 : n = cdb_unpack(cdbfp->cdb_htp) == cdbfp->cdb_hval;
370 0 : if ((cdbfp->cdb_htp += 8) >= cdbfp->cdb_htend)
371 0 : cdbfp->cdb_htp = cdbfp->cdb_htab;
372 0 : cdbfp->cdb_httodo -= 8;
373 0 : if (n) {
374 0 : if (pos > cdbp->cdb_fsize - 8) {
375 0 : gpg_err_set_errno (EPROTO);
376 0 : return -1;
377 : }
378 0 : if (cdb_unpack(cdbp->cdb_mem + pos) == cdbfp->cdb_klen) {
379 0 : if (cdbp->cdb_fsize - cdbfp->cdb_klen < pos + 8) {
380 0 : gpg_err_set_errno (EPROTO);
381 0 : return -1;
382 : }
383 0 : if (memcmp(cdbfp->cdb_key,
384 0 : cdbp->cdb_mem + pos + 8, cdbfp->cdb_klen) == 0) {
385 0 : n = cdb_unpack(cdbp->cdb_mem + pos + 4);
386 0 : pos += 8 + cdbfp->cdb_klen;
387 0 : if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
388 0 : gpg_err_set_errno (EPROTO);
389 0 : return -1;
390 : }
391 0 : cdbp->cdb_vpos = pos;
392 0 : cdbp->cdb_vlen = n;
393 0 : return 1;
394 : }
395 : }
396 : }
397 : }
398 : }
399 : else /* Walk over all entries. */
400 : {
401 : do
402 : {
403 0 : while (cdbfp->cdb_htp >= cdbfp->cdb_htend)
404 : {
405 0 : if (cdbfp->cdb_hval > 255)
406 0 : return 0; /* No more items. */
407 :
408 0 : cdbfp->cdb_htp = cdbp->cdb_mem + cdbfp->cdb_hval * 8;
409 0 : cdbfp->cdb_hval++; /* Advance for next round. */
410 0 : pos = cdb_unpack (cdbfp->cdb_htp); /* Offset of table. */
411 0 : n = cdb_unpack (cdbfp->cdb_htp + 4); /* Number of entries. */
412 0 : cdbfp->cdb_httodo = n * 8; /* Size of table. */
413 0 : if (n > (cdbp->cdb_fsize / 8)
414 0 : || pos > cdbp->cdb_fsize
415 0 : || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
416 : {
417 0 : gpg_err_set_errno (EPROTO);
418 0 : return -1;
419 : }
420 :
421 0 : cdbfp->cdb_htab = cdbp->cdb_mem + pos;
422 0 : cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
423 0 : cdbfp->cdb_htp = cdbfp->cdb_htab;
424 : }
425 :
426 0 : pos = cdb_unpack (cdbfp->cdb_htp + 4); /* Offset of record. */
427 0 : cdbfp->cdb_htp += 8;
428 : }
429 0 : while (!pos);
430 0 : if (pos > cdbp->cdb_fsize - 8)
431 : {
432 0 : gpg_err_set_errno (EPROTO);
433 0 : return -1;
434 : }
435 :
436 0 : cdbp->cdb_kpos = pos + 8;
437 0 : cdbp->cdb_klen = cdb_unpack(cdbp->cdb_mem + pos);
438 0 : cdbp->cdb_vpos = pos + 8 + cdbp->cdb_klen;
439 0 : cdbp->cdb_vlen = cdb_unpack(cdbp->cdb_mem + pos + 4);
440 0 : n = 8 + cdbp->cdb_klen + cdbp->cdb_vlen;
441 0 : if ( pos > cdbp->cdb_fsize || pos > cdbp->cdb_fsize - n)
442 : {
443 0 : gpg_err_set_errno (EPROTO);
444 0 : return -1;
445 : }
446 0 : return 1; /* Found. */
447 : }
448 0 : return 0;
449 : }
450 :
451 : /* Read a chunk from file, ignoring interrupts (EINTR) */
452 : int
453 0 : cdb_bread(int fd, void *buf, int len)
454 : {
455 : int l;
456 0 : while(len > 0) {
457 0 : do l = read(fd, buf, len);
458 0 : while(l < 0 && errno == EINTR);
459 0 : if (l <= 0) {
460 0 : if (!l)
461 0 : gpg_err_set_errno (EIO);
462 0 : return -1;
463 : }
464 0 : buf = (char*)buf + l;
465 0 : len -= l;
466 : }
467 0 : return 0;
468 : }
469 :
470 : /* Find a given key in cdb file, seek a file pointer to it's value and
471 : place data length to *dlenp. */
472 : int
473 0 : cdb_seek(int fd, const void *key, unsigned klen, cdbi_t *dlenp)
474 : {
475 : cdbi_t htstart; /* hash table start position */
476 : cdbi_t htsize; /* number of elements in a hash table */
477 : cdbi_t httodo; /* hash table elements left to look */
478 : cdbi_t hti; /* hash table index */
479 : cdbi_t pos; /* position in a file */
480 : cdbi_t hval; /* key's hash value */
481 : unsigned char rbuf[64]; /* read buffer */
482 0 : int needseek = 1; /* if we should seek to a hash slot */
483 :
484 0 : hval = cdb_hash(key, klen);
485 0 : pos = (hval & 0xff) << 3; /* position in TOC */
486 : /* read the hash table parameters */
487 0 : if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
488 0 : return -1;
489 0 : if ((htsize = cdb_unpack(rbuf + 4)) == 0)
490 0 : return 0;
491 0 : hti = (hval >> 8) % htsize; /* start position in hash table */
492 0 : httodo = htsize;
493 0 : htstart = cdb_unpack(rbuf);
494 :
495 : for(;;) {
496 0 : if (needseek && lseek(fd, htstart + (hti << 3), SEEK_SET) < 0)
497 0 : return -1;
498 0 : if (cdb_bread(fd, rbuf, 8) < 0)
499 0 : return -1;
500 0 : if ((pos = cdb_unpack(rbuf + 4)) == 0) /* not found */
501 0 : return 0;
502 :
503 0 : if (cdb_unpack(rbuf) != hval) /* hash value not matched */
504 0 : needseek = 0;
505 : else { /* hash value matched */
506 0 : if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
507 0 : return -1;
508 0 : if (cdb_unpack(rbuf) == klen) { /* key length matches */
509 : /* read the key from file and compare with wanted */
510 0 : cdbi_t l = klen, c;
511 0 : const char *k = (const char*)key;
512 0 : if (*dlenp)
513 0 : *dlenp = cdb_unpack(rbuf + 4); /* save value length */
514 : for(;;) {
515 0 : if (!l) /* the whole key read and matches, return */
516 0 : return 1;
517 0 : c = l > sizeof(rbuf) ? sizeof(rbuf) : l;
518 0 : if (cdb_bread(fd, rbuf, c) < 0)
519 0 : return -1;
520 0 : if (memcmp(rbuf, k, c) != 0) /* no, it differs, stop here */
521 0 : break;
522 0 : k += c; l -= c;
523 0 : }
524 : }
525 0 : needseek = 1; /* we're looked to other place, should seek back */
526 : }
527 0 : if (!--httodo)
528 0 : return 0;
529 0 : if (++hti == htsize) {
530 0 : hti = htstart;
531 0 : needseek = 1;
532 : }
533 0 : }
534 : }
535 :
536 : cdbi_t
537 0 : cdb_unpack(const unsigned char buf[4])
538 : {
539 0 : cdbi_t n = buf[3];
540 0 : n <<= 8; n |= buf[2];
541 0 : n <<= 8; n |= buf[1];
542 0 : n <<= 8; n |= buf[0];
543 0 : return n;
544 : }
545 :
546 : /* Add record with key (KEY,KLEN) and value (VAL,VLEN) to a database.
547 : Returns 0 on success or negative value on error. Note that this
548 : routine does not checks if given key already exists, but cdb_find()
549 : will not see second record with the same key. It is not possible
550 : to continue building a database if cdb_make_add() returned an error
551 : indicator. */
552 : int
553 0 : cdb_make_add(struct cdb_make *cdbmp,
554 : const void *key, cdbi_t klen,
555 : const void *val, cdbi_t vlen)
556 : {
557 : unsigned char rlen[8];
558 : cdbi_t hval;
559 : struct cdb_rl *rl;
560 0 : if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
561 0 : vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
562 0 : gpg_err_set_errno (ENOMEM);
563 0 : return -1;
564 : }
565 0 : hval = cdb_hash(key, klen);
566 0 : rl = cdbmp->cdb_rec[hval&255];
567 0 : if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
568 0 : rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
569 0 : if (!rl) {
570 0 : gpg_err_set_errno (ENOMEM);
571 0 : return -1;
572 : }
573 0 : rl->cnt = 0;
574 0 : rl->next = cdbmp->cdb_rec[hval&255];
575 0 : cdbmp->cdb_rec[hval&255] = rl;
576 : }
577 0 : rl->rec[rl->cnt].hval = hval;
578 0 : rl->rec[rl->cnt].rpos = cdbmp->cdb_dpos;
579 0 : ++rl->cnt;
580 0 : ++cdbmp->cdb_rcnt;
581 0 : cdb_pack(klen, rlen);
582 0 : cdb_pack(vlen, rlen + 4);
583 0 : if (make_write(cdbmp, rlen, 8) < 0 ||
584 0 : make_write(cdbmp, key, klen) < 0 ||
585 0 : make_write(cdbmp, val, vlen) < 0)
586 0 : return -1;
587 0 : return 0;
588 : }
589 :
590 : int
591 0 : cdb_make_put(struct cdb_make *cdbmp,
592 : const void *key, cdbi_t klen,
593 : const void *val, cdbi_t vlen,
594 : int flags)
595 : {
596 : unsigned char rlen[8];
597 0 : cdbi_t hval = cdb_hash(key, klen);
598 : struct cdb_rl *rl;
599 : int c, r;
600 :
601 0 : switch(flags) {
602 : case CDB_PUT_REPLACE:
603 : case CDB_PUT_INSERT:
604 : case CDB_PUT_WARN:
605 0 : c = make_find(cdbmp, key, klen, hval, &rl);
606 0 : if (c < 0)
607 0 : return -1;
608 0 : if (c) {
609 0 : if (flags == CDB_PUT_INSERT) {
610 0 : gpg_err_set_errno (EEXIST);
611 0 : return 1;
612 : }
613 0 : else if (flags == CDB_PUT_REPLACE) {
614 0 : --c;
615 0 : r = 1;
616 0 : break;
617 : }
618 : else
619 0 : r = 1;
620 : }
621 : /* fall */
622 :
623 : case CDB_PUT_ADD:
624 0 : rl = cdbmp->cdb_rec[hval&255];
625 0 : if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
626 0 : rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
627 0 : if (!rl) {
628 0 : gpg_err_set_errno (ENOMEM);
629 0 : return -1;
630 : }
631 0 : rl->cnt = 0;
632 0 : rl->next = cdbmp->cdb_rec[hval&255];
633 0 : cdbmp->cdb_rec[hval&255] = rl;
634 : }
635 0 : c = rl->cnt;
636 0 : r = 0;
637 0 : break;
638 :
639 : default:
640 0 : gpg_err_set_errno (EINVAL);
641 0 : return -1;
642 : }
643 :
644 0 : if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
645 0 : vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
646 0 : gpg_err_set_errno (ENOMEM);
647 0 : return -1;
648 : }
649 0 : rl->rec[c].hval = hval;
650 0 : rl->rec[c].rpos = cdbmp->cdb_dpos;
651 0 : if (c == rl->cnt) {
652 0 : ++rl->cnt;
653 0 : ++cdbmp->cdb_rcnt;
654 : }
655 0 : cdb_pack(klen, rlen);
656 0 : cdb_pack(vlen, rlen + 4);
657 0 : if (make_write(cdbmp, rlen, 8) < 0 ||
658 0 : make_write(cdbmp, key, klen) < 0 ||
659 0 : make_write(cdbmp, val, vlen) < 0)
660 0 : return -1;
661 0 : return r;
662 : }
663 :
664 :
665 : static int
666 0 : match(int fd, cdbi_t pos, const char *key, cdbi_t klen)
667 : {
668 : unsigned char buf[64]; /*XXX cdb_buf may be used here instead */
669 0 : if (lseek(fd, pos, SEEK_SET) < 0 || read(fd, buf, 8) != 8)
670 0 : return -1;
671 0 : if (cdb_unpack(buf) != klen)
672 0 : return 0;
673 :
674 0 : while(klen > sizeof(buf)) {
675 0 : if (read(fd, buf, sizeof(buf)) != sizeof(buf))
676 0 : return -1;
677 0 : if (memcmp(buf, key, sizeof(buf)) != 0)
678 0 : return 0;
679 0 : key += sizeof(buf);
680 0 : klen -= sizeof(buf);
681 : }
682 0 : if (klen) {
683 0 : if (read(fd, buf, klen) != klen)
684 0 : return -1;
685 0 : if (memcmp(buf, key, klen) != 0)
686 0 : return 0;
687 : }
688 0 : return 1;
689 : }
690 :
691 :
692 : static int
693 0 : make_find (struct cdb_make *cdbmp,
694 : const void *key, cdbi_t klen, cdbi_t hval,
695 : struct cdb_rl **rlp)
696 : {
697 0 : struct cdb_rl *rl = cdbmp->cdb_rec[hval&255];
698 : int r, i;
699 0 : int seeked = 0;
700 0 : while(rl) {
701 0 : for(i = rl->cnt - 1; i >= 0; --i) { /* search backward */
702 0 : if (rl->rec[i].hval != hval)
703 0 : continue;
704 : /*XXX this explicit flush may be unnecessary having
705 : * smarter match() that looks to cdb_buf too, but
706 : * most of a time here spent in finding hash values
707 : * (above), not keys */
708 0 : if (cdbmp->cdb_bpos != cdbmp->cdb_buf) {
709 0 : if (write(cdbmp->cdb_fd, cdbmp->cdb_buf,
710 0 : cdbmp->cdb_bpos - cdbmp->cdb_buf) < 0)
711 0 : return -1;
712 0 : cdbmp->cdb_bpos = cdbmp->cdb_buf;
713 : }
714 0 : seeked = 1;
715 0 : r = match(cdbmp->cdb_fd, rl->rec[i].rpos, key, klen);
716 0 : if (!r)
717 0 : continue;
718 0 : if (r < 0)
719 0 : return -1;
720 0 : if (lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
721 0 : return -1;
722 0 : if (rlp)
723 0 : *rlp = rl;
724 0 : return i + 1;
725 : }
726 0 : rl = rl->next;
727 : }
728 0 : if (seeked && lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
729 0 : return -1;
730 0 : return 0;
731 : }
732 :
733 : int
734 0 : cdb_make_exists(struct cdb_make *cdbmp,
735 : const void *key, cdbi_t klen)
736 : {
737 0 : return make_find(cdbmp, key, klen, cdb_hash(key, klen), NULL);
738 : }
739 :
740 :
741 : void
742 0 : cdb_pack(cdbi_t num, unsigned char buf[4])
743 : {
744 0 : buf[0] = num & 255; num >>= 8;
745 0 : buf[1] = num & 255; num >>= 8;
746 0 : buf[2] = num & 255;
747 0 : buf[3] = num >> 8;
748 0 : }
749 :
750 :
751 : /* Initializes structure to create a database. File FD should be
752 : opened read-write and should be seekable. Returns 0 on success or
753 : negative value on error. */
754 : int
755 0 : cdb_make_start(struct cdb_make *cdbmp, int fd)
756 : {
757 0 : memset (cdbmp, 0, sizeof *cdbmp);
758 0 : cdbmp->cdb_fd = fd;
759 0 : cdbmp->cdb_dpos = 2048;
760 0 : cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
761 0 : return 0;
762 : }
763 :
764 :
765 : static int
766 0 : ewrite(int fd, const char *buf, int len)
767 : {
768 0 : while(len) {
769 0 : int l = write(fd, buf, len);
770 0 : if (l < 0 && errno != EINTR)
771 0 : return -1;
772 0 : if (l > 0)
773 : {
774 0 : len -= l;
775 0 : buf += l;
776 : }
777 : }
778 0 : return 0;
779 : }
780 :
781 : static int
782 0 : make_write(struct cdb_make *cdbmp, const char *ptr, cdbi_t len)
783 : {
784 0 : cdbi_t l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
785 0 : cdbmp->cdb_dpos += len;
786 0 : if (len > l) {
787 0 : memcpy(cdbmp->cdb_bpos, ptr, l);
788 0 : if (ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf, sizeof(cdbmp->cdb_buf)) < 0)
789 0 : return -1;
790 0 : ptr += l; len -= l;
791 0 : l = len / sizeof(cdbmp->cdb_buf);
792 0 : if (l) {
793 0 : l *= sizeof(cdbmp->cdb_buf);
794 0 : if (ewrite(cdbmp->cdb_fd, ptr, l) < 0)
795 0 : return -1;
796 0 : ptr += l; len -= l;
797 : }
798 0 : cdbmp->cdb_bpos = cdbmp->cdb_buf;
799 : }
800 0 : if (len) {
801 0 : memcpy(cdbmp->cdb_bpos, ptr, len);
802 0 : cdbmp->cdb_bpos += len;
803 : }
804 0 : return 0;
805 : }
806 :
807 : static int
808 0 : cdb_make_finish_internal(struct cdb_make *cdbmp)
809 : {
810 : cdbi_t hcnt[256]; /* hash table counts */
811 : cdbi_t hpos[256]; /* hash table positions */
812 : struct cdb_rec *htab;
813 : unsigned char *p;
814 : struct cdb_rl *rl;
815 : cdbi_t hsize;
816 : unsigned t, i;
817 :
818 0 : if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) {
819 0 : gpg_err_set_errno (ENOMEM);
820 0 : return -1;
821 : }
822 :
823 : /* count htab sizes and reorder reclists */
824 0 : hsize = 0;
825 0 : for (t = 0; t < 256; ++t) {
826 0 : struct cdb_rl *rlt = NULL;
827 0 : i = 0;
828 0 : rl = cdbmp->cdb_rec[t];
829 0 : while(rl) {
830 0 : struct cdb_rl *rln = rl->next;
831 0 : rl->next = rlt;
832 0 : rlt = rl;
833 0 : i += rl->cnt;
834 0 : rl = rln;
835 : }
836 0 : cdbmp->cdb_rec[t] = rlt;
837 0 : if (hsize < (hcnt[t] = i << 1))
838 0 : hsize = hcnt[t];
839 : }
840 :
841 : /* allocate memory to hold max htable */
842 0 : htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
843 0 : if (!htab) {
844 0 : gpg_err_set_errno (ENOENT);
845 0 : return -1;
846 : }
847 0 : p = (unsigned char *)htab;
848 0 : htab += 2;
849 :
850 : /* build hash tables */
851 0 : for (t = 0; t < 256; ++t) {
852 : cdbi_t len, hi;
853 0 : hpos[t] = cdbmp->cdb_dpos;
854 0 : if ((len = hcnt[t]) == 0)
855 0 : continue;
856 0 : for (i = 0; i < len; ++i)
857 0 : htab[i].hval = htab[i].rpos = 0;
858 0 : for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
859 0 : for (i = 0; i < rl->cnt; ++i) {
860 0 : hi = (rl->rec[i].hval >> 8) % len;
861 0 : while(htab[hi].rpos)
862 0 : if (++hi == len)
863 0 : hi = 0;
864 0 : htab[hi] = rl->rec[i];
865 : }
866 0 : for (i = 0; i < len; ++i) {
867 0 : cdb_pack(htab[i].hval, p + (i << 3));
868 0 : cdb_pack(htab[i].rpos, p + (i << 3) + 4);
869 : }
870 0 : if (make_write(cdbmp, p, len << 3) < 0) {
871 0 : free(p);
872 0 : return -1;
873 : }
874 : }
875 0 : free(p);
876 0 : if (cdbmp->cdb_bpos != cdbmp->cdb_buf &&
877 0 : ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf,
878 0 : cdbmp->cdb_bpos - cdbmp->cdb_buf) != 0)
879 0 : return -1;
880 0 : p = cdbmp->cdb_buf;
881 0 : for (t = 0; t < 256; ++t) {
882 0 : cdb_pack(hpos[t], p + (t << 3));
883 0 : cdb_pack(hcnt[t], p + (t << 3) + 4);
884 : }
885 0 : if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
886 0 : ewrite(cdbmp->cdb_fd, p, 2048) != 0)
887 0 : return -1;
888 :
889 0 : return 0;
890 : }
891 :
892 : static void
893 0 : cdb_make_free(struct cdb_make *cdbmp)
894 : {
895 : unsigned t;
896 0 : for(t = 0; t < 256; ++t) {
897 0 : struct cdb_rl *rl = cdbmp->cdb_rec[t];
898 0 : while(rl) {
899 0 : struct cdb_rl *tm = rl;
900 0 : rl = rl->next;
901 0 : free(tm);
902 : }
903 : }
904 0 : }
905 :
906 :
907 :
908 : /* Finalizes database file, constructing all needed indexes, and frees
909 : memory structures. It does not close the file descriptor. Returns
910 : 0 on success or a negative value on error. */
911 : int
912 0 : cdb_make_finish(struct cdb_make *cdbmp)
913 : {
914 0 : int r = cdb_make_finish_internal(cdbmp);
915 0 : cdb_make_free(cdbmp);
916 0 : return r;
917 : }
918 :
919 :
920 : cdbi_t
921 0 : cdb_hash(const void *buf, cdbi_t len)
922 : {
923 0 : register const unsigned char *p = (const unsigned char *)buf;
924 0 : register const unsigned char *end = p + len;
925 0 : register cdbi_t hash = 5381; /* start value */
926 0 : while (p < end)
927 0 : hash = (hash + (hash << 5)) ^ *p++;
928 0 : return hash;
929 : }
|
