added TDB_INTERNAL, TDB_NOLOCK and TDB_NOMMAP flags.
[kai/samba.git] / source / tdb / tdb.c
1 /* 
2    Unix SMB/Netbios implementation.
3    Version 3.0
4    Samba database functions
5    Copyright (C) Andrew Tridgell              1999-2000
6    Copyright (C) Luke Kenneth Casson Leighton      2000
7    
8    This program is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2 of the License, or
11    (at your option) any later version.
12    
13    This program is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17    
18    You should have received a copy of the GNU General Public License
19    along with this program; if not, write to the Free Software
20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 */
22
23 #if STANDALONE
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <fcntl.h>
27 #include <unistd.h>
28 #include <string.h>
29 #include <fcntl.h>
30 #include <errno.h>
31 #include <sys/mman.h>
32 #include <sys/stat.h>
33 #include "tdb.h"
34 #else
35 #include "includes.h"
36 #endif
37
38 #define TDB_VERSION (0x26011967 + 1)
39 #define TDB_MAGIC (0x26011999U)
40 #define TDB_FREE_MAGIC (~TDB_MAGIC)
41 #define TDB_ALIGN 4
42 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGN)
43 #define DEFAULT_HASH_SIZE 128
44 #define TDB_PAGE_SIZE 0x2000
45 #define TDB_LEN_MULTIPLIER 10
46 #define FREELIST_TOP (sizeof(struct tdb_header))
47
48 #define LOCK_SET 1
49 #define LOCK_CLEAR 0
50
51 /* lock offsets */
52 #define GLOBAL_LOCK 0
53 #define ACTIVE_LOCK 4
54 #define LIST_LOCK_BASE 1024
55
56 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
57
58 #ifndef MAP_FILE
59 #define MAP_FILE 0
60 #endif
61
62 /* the body of the database is made of one list_struct for the free space
63    plus a separate data list for each hash value */
64 struct list_struct {
65         tdb_len rec_len; /* total byte length of record */
66         tdb_off next; /* offset of the next record in the list */
67         tdb_len key_len; /* byte length of key */
68         tdb_len data_len; /* byte length of data */
69         unsigned full_hash; /* the full 32 bit hash of the key */
70         unsigned magic;   /* try to catch errors */
71         /*
72            the following union is implied 
73            union {
74               char record[rec_len];
75               struct {
76                 char key[key_len];
77                 char data[data_len];
78               }
79            }
80         */
81 };
82
83 /* a null data record - useful for error returns */
84 static TDB_DATA null_data;
85
86 /* a byte range locking function - return 0 on success
87    this functions locks/unlocks 1 byte at the specified offset */
88 static int tdb_brlock(TDB_CONTEXT *tdb, tdb_off offset, 
89                       int set, int rw_type, int lck_type)
90 {
91         struct flock fl;
92
93         if (tdb->flags & TDB_NOLOCK) return 0;
94
95         if (tdb->read_only) return -1;
96
97         fl.l_type = set==LOCK_SET?rw_type:F_UNLCK;
98         fl.l_whence = SEEK_SET;
99         fl.l_start = offset;
100         fl.l_len = 1;
101         fl.l_pid = 0;
102
103         if (fcntl(tdb->fd, lck_type, &fl) != 0) {
104 #if TDB_DEBUG
105                 if (lck_type == F_SETLKW) {
106                         printf("lock %d failed at %d (%s)\n", 
107                                set, offset, strerror(errno));
108                 }
109 #endif
110                 tdb->ecode = TDB_ERR_LOCK;
111                 return -1;
112         }
113         return 0;
114 }
115
116 /* lock a list in the database. list -1 is the alloc list */
117 static int tdb_lock(TDB_CONTEXT *tdb, int list)
118 {
119         if (list < -1 || list >= (int)tdb->header.hash_size) {
120 #if TDB_DEBUG
121                 printf("bad list %d\n", list);
122 #endif
123                 return -1;
124         }
125
126         if (tdb->flags & TDB_NOLOCK) return 0;
127
128         if (tdb->locked[list+1] == 0) {
129                 if (tdb_brlock(tdb, LIST_LOCK_BASE + 4*list, LOCK_SET, 
130                                F_WRLCK, F_SETLKW) != 0) {
131                         return -1;
132                 }
133         }
134         tdb->locked[list+1]++;
135         return 0;
136 }
137
138 /* unlock the database. */
139 static int tdb_unlock(TDB_CONTEXT *tdb, int list)
140 {
141         if (list < -1 || list >= (int)tdb->header.hash_size) {
142 #if TDB_DEBUG
143                 printf("bad unlock list %d\n", list);
144 #endif
145                 return -1;
146         }
147
148         if (tdb->flags & TDB_NOLOCK) return 0;
149
150         if (tdb->locked[list+1] == 0) {
151 #if TDB_DEBUG
152                 printf("not locked %d\n", list);
153 #endif
154                 tdb->ecode = TDB_ERR_LOCK;
155                 return -1;
156         }
157         if (tdb->locked[list+1] == 1) {
158                 if (tdb_brlock(tdb, LIST_LOCK_BASE + 4*list, LOCK_CLEAR, 
159                                F_WRLCK, F_SETLKW) != 0) {
160                         return -1;
161                 }
162         }
163         tdb->locked[list+1]--;
164         return 0;
165 }
166
167 /* the hash algorithm - turn a key into an integer
168    This is based on the hash agorithm from gdbm */
169 static unsigned tdb_hash(TDB_DATA *key)
170 {
171         unsigned value; /* Used to compute the hash value.  */
172         unsigned   i;   /* Used to cycle through random values. */
173
174         /* Set the initial value from the key size. */
175         value = 0x238F13AF * key->dsize;
176         for (i=0; i < key->dsize; i++) {
177                 value = (value + (key->dptr[i] << (i*5 % 24)));
178         }
179
180         value = (1103515243 * value + 12345);  
181
182         return value;
183 }
184
185 /* find the top of the hash chain for an open database */
186 static tdb_off tdb_hash_top(TDB_CONTEXT *tdb, unsigned hash)
187 {
188         tdb_off ret;
189         hash = BUCKET(hash);
190         ret = FREELIST_TOP + (hash+1)*sizeof(tdb_off);
191         return ret;
192 }
193
194
195 /* check for an out of bounds access - if it is out of bounds then
196    see if the database has been expanded by someone else and expand
197    if necessary */
198 static int tdb_oob(TDB_CONTEXT *tdb, tdb_off offset)
199 {
200         struct stat st;
201         if (offset <= tdb->map_size) return 0;
202
203         if (tdb->flags & TDB_INTERNAL) return 0;
204
205         fstat(tdb->fd, &st);
206         if (st.st_size <= (size_t)offset) {
207                 tdb->ecode = TDB_ERR_IO;
208                 return -1;
209         }
210
211 #if HAVE_MMAP
212         if (tdb->map_ptr) {
213                 munmap(tdb->map_ptr, tdb->map_size);
214                 tdb->map_ptr = NULL;
215         }
216 #endif
217
218         tdb->map_size = st.st_size;
219 #if HAVE_MMAP
220         if (!(tdb->flags & TDB_NOMMAP)) {
221                 tdb->map_ptr = (void *)mmap(NULL, tdb->map_size, 
222                                             tdb->read_only?PROT_READ:PROT_READ|PROT_WRITE,
223                                             MAP_SHARED | MAP_FILE, tdb->fd, 0);
224         }
225 #endif  
226         return 0;
227 }
228
229
230 /* write a lump of data at a specified offset */
231 static int tdb_write(TDB_CONTEXT *tdb, tdb_off offset, const char *buf, tdb_len len)
232 {
233         if (tdb_oob(tdb, offset + len) != 0) {
234                 /* oops - trying to write beyond the end of the database! */
235                 return -1;
236         }
237
238         if (tdb->map_ptr) {
239                 memcpy(offset + (char *)tdb->map_ptr, buf, len);
240         } else {
241                 if (lseek(tdb->fd, offset, SEEK_SET) != offset ||
242                     write(tdb->fd, buf, len) != (ssize_t)len) {
243                         tdb->ecode = TDB_ERR_IO;
244                         return -1;
245                 }
246         }
247         return 0;
248 }
249
250 /* read a lump of data at a specified offset */
251 static int tdb_read(TDB_CONTEXT *tdb, tdb_off offset, char *buf, tdb_len len)
252 {
253         if (tdb_oob(tdb, offset + len) != 0) {
254                 /* oops - trying to read beyond the end of the database! */
255                 return -1;
256         }
257
258         if (tdb->map_ptr) {
259                 memcpy(buf, offset + (char *)tdb->map_ptr, len);
260         } else {
261                 if (lseek(tdb->fd, offset, SEEK_SET) != offset ||
262                     read(tdb->fd, buf, len) != (ssize_t)len) {
263                         tdb->ecode = TDB_ERR_IO;
264                         return -1;
265                 }
266         }
267         return 0;
268 }
269
270
271 /* read a lump of data, allocating the space for it */
272 static char *tdb_alloc_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_len len)
273 {
274         char *buf;
275
276         buf = (char *)malloc(len);
277
278         if (!buf) {
279                 tdb->ecode = TDB_ERR_OOM;
280                 return NULL;
281         }
282
283         if (tdb_read(tdb, offset, buf, len) == -1) {
284                 free(buf);
285                 return NULL;
286         }
287         
288         return buf;
289 }
290
291 /* convenience routine for writing a record */
292 static int rec_write(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
293 {
294         return tdb_write(tdb, offset, (char *)rec, sizeof(*rec));
295 }
296
297 /* convenience routine for writing a tdb_off */
298 static int ofs_write(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
299 {
300         return tdb_write(tdb, offset, (char *)d, sizeof(*d));
301 }
302
303 /* read a tdb_off from the store */
304 static int ofs_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
305 {
306         return tdb_read(tdb, offset, (char *)d, sizeof(*d));
307 }
308
309 /* read a record and check for simple errors */
310 static int rec_read(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
311 {
312         if (tdb_read(tdb, offset, (char *)rec, sizeof(*rec)) == -1) return -1;
313         if (rec->magic != TDB_MAGIC) {
314 #if TDB_DEBUG
315                 printf("bad magic 0x%08x at offset %d\n",
316                        rec->magic, offset);
317 #endif
318                 tdb->ecode = TDB_ERR_CORRUPT;
319                 return -1;
320         }
321         if (tdb_oob(tdb, rec->next) != 0) {
322                 return -1;
323         }
324         return 0;
325 }
326
327 /* expand the database at least length bytes by expanding the
328    underlying file and doing the mmap again if necessary */
329 static int tdb_expand(TDB_CONTEXT *tdb, tdb_off length)
330 {
331         struct list_struct rec;
332         tdb_off offset, ptr;
333         char b = 0;
334
335         tdb_lock(tdb,-1);
336
337         /* make sure we know about any previous expansions by another
338            process */
339         tdb_oob(tdb,tdb->map_size + 1);
340
341         /* always make room for at least 10 more records */
342         length *= TDB_LEN_MULTIPLIER;
343
344         /* and round the database up to a multiple of TDB_PAGE_SIZE */
345         length = ((tdb->map_size + length + TDB_PAGE_SIZE) & ~(TDB_PAGE_SIZE - 1)) - tdb->map_size;
346
347         /* expand the file itself */
348         if (!(tdb->flags & TDB_INTERNAL)) {
349                 lseek(tdb->fd, tdb->map_size + length - 1, SEEK_SET);
350                 if (write(tdb->fd, &b, 1) != 1) goto fail;
351         }
352
353         /* form a new freelist record */
354         offset = FREELIST_TOP;
355         rec.rec_len = length - sizeof(rec);
356         rec.magic = TDB_FREE_MAGIC;
357         if (ofs_read(tdb, offset, &rec.next) == -1) {
358                 goto fail;
359         }
360
361 #if HAVE_MMAP
362         if (!(tdb->flags & TDB_INTERNAL) && tdb->map_ptr) {
363                 munmap(tdb->map_ptr, tdb->map_size);
364                 tdb->map_ptr = NULL;
365         }
366 #endif
367
368         tdb->map_size += length;
369
370         if (tdb->flags & TDB_INTERNAL) {
371                 tdb->map_ptr = realloc(tdb->map_ptr, tdb->map_size);
372         }
373
374         /* write it out */
375         if (rec_write(tdb, tdb->map_size - length, &rec) == -1) {
376                 goto fail;
377         }
378
379         /* link it into the free list */
380         ptr = tdb->map_size - length;
381         if (ofs_write(tdb, offset, &ptr) == -1) goto fail;
382
383 #if HAVE_MMAP
384         if (!(tdb->flags & TDB_NOMMAP)) {
385                 tdb->map_ptr = (void *)mmap(NULL, tdb->map_size, 
386                                             PROT_READ|PROT_WRITE,
387                                             MAP_SHARED | MAP_FILE, tdb->fd, 0);
388         }
389 #endif
390
391         tdb_unlock(tdb, -1);
392         return 0;
393
394  fail:
395         tdb_unlock(tdb,-1);
396         return -1;
397 }
398
399 /* allocate some space from the free list. The offset returned points
400    to a unconnected list_struct within the database with room for at
401    least length bytes of total data
402
403    0 is returned if the space could not be allocated
404  */
405 static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length)
406 {
407         tdb_off offset, rec_ptr, last_ptr;
408         struct list_struct rec, lastrec, newrec;
409
410         tdb_lock(tdb, -1);
411
412  again:
413         last_ptr = 0;
414         offset = FREELIST_TOP;
415
416         /* read in the freelist top */
417         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
418                 goto fail;
419         }
420
421         /* keep looking until we find a freelist record that is big
422            enough */
423         while (rec_ptr) {
424                 if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
425                         goto fail;
426                 }
427
428                 if (rec.magic != TDB_FREE_MAGIC) {
429 #if TDB_DEBUG
430                         printf("bad magic 0x%08x in free list\n", rec.magic);
431 #endif
432                         goto fail;
433                 }
434
435                 if (rec.rec_len >= length) {
436                         /* found it - now possibly split it up  */
437                         if (rec.rec_len > length + MIN_REC_SIZE) {
438                                 length = (length + TDB_ALIGN) & ~(TDB_ALIGN-1);
439
440                                 newrec.rec_len = rec.rec_len - (sizeof(rec) + length);
441                                 newrec.next = rec.next;
442                                 newrec.magic = TDB_FREE_MAGIC;
443
444                                 rec.rec_len = length;
445                                 rec.next = rec_ptr + sizeof(rec) + rec.rec_len;
446                                 
447                                 if (rec_write(tdb, rec.next, &newrec) == -1) {
448                                         goto fail;
449                                 }
450
451                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
452                                         goto fail;
453                                 }
454                         }
455
456                         /* remove it from the list */
457                         if (last_ptr == 0) {
458                                 offset = FREELIST_TOP;
459
460                                 if (ofs_write(tdb, offset, &rec.next) == -1) {
461                                         goto fail;
462                                 }                               
463                         } else {
464                                 lastrec.next = rec.next;
465                                 if (rec_write(tdb, last_ptr, &lastrec) == -1) {
466                                         goto fail;
467                                 }
468                         }
469
470                         /* all done - return the new record offset */
471                         tdb_unlock(tdb, -1);
472                         return rec_ptr;
473                 }
474
475                 /* move to the next record */
476                 lastrec = rec;
477                 last_ptr = rec_ptr;
478                 rec_ptr = rec.next;
479         }
480
481         /* we didn't find enough space. See if we can expand the
482            database and if we can then try again */
483         if (tdb_expand(tdb, length + sizeof(rec)) == 0) goto again;
484
485  fail:
486 #if TDB_DEBUG
487         printf("tdb_allocate failed for size %u\n", length);
488 #endif
489         tdb_unlock(tdb, -1);
490         return 0;
491 }
492
493 /* initialise a new database with a specified hash size */
494 static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size)
495 {
496         struct tdb_header header;
497         tdb_off offset;
498         int i, size = 0;
499         tdb_off buf[16];
500
501         /* create the header */
502         memset(&header, 0, sizeof(header));
503         memcpy(header.magic_food, TDB_MAGIC_FOOD, strlen(TDB_MAGIC_FOOD)+1);
504         header.version = TDB_VERSION;
505         header.hash_size = hash_size;
506         if (tdb->fd != -1) {
507                 lseek(tdb->fd, 0, SEEK_SET);
508                 ftruncate(tdb->fd, 0);
509         }
510         
511         if (tdb->fd != -1 && write(tdb->fd, &header, sizeof(header)) != 
512             sizeof(header)) {
513             tdb->ecode = TDB_ERR_IO;
514             return -1;
515         } else size += sizeof(header);
516         
517         /* the freelist and hash pointers */
518         offset = 0;
519         memset(buf, 0, sizeof(buf));
520
521         for (i=0;(hash_size+1)-i >= 16; i += 16) {
522             if (tdb->fd != -1 && write(tdb->fd, buf, sizeof(buf)) != 
523                 sizeof(buf)) {
524                 tdb->ecode = TDB_ERR_IO;
525                 return -1;
526             } else size += sizeof(buf);
527         }
528
529         for (;i<hash_size+1; i++) {
530             if (tdb->fd != -1 && write(tdb->fd, buf, sizeof(tdb_off)) != 
531                 sizeof(tdb_off)) {
532                 tdb->ecode = TDB_ERR_IO;
533                 return -1;
534             } else size += sizeof(tdb_off);
535         }
536
537         if (tdb->flags & TDB_INTERNAL) {
538                 tdb->map_ptr = calloc(size,1);
539                 tdb->map_size = size;
540                 if (tdb->map_ptr == NULL) {
541                         tdb->ecode = TDB_ERR_IO;
542                         return -1;
543                 }
544                 memcpy(&tdb->header, &header, sizeof(header));
545         }
546
547 #if TDB_DEBUG
548         printf("initialised database of hash_size %u\n", 
549                hash_size);
550 #endif
551         return 0;
552 }
553
554 /* Returns 0 on fail.  On success, return offset of record, and fills
555    in rec */
556 static tdb_off tdb_find(TDB_CONTEXT *tdb, TDB_DATA key, unsigned int hash,
557                         struct list_struct *rec)
558 {
559         tdb_off offset, rec_ptr;
560         
561         /* find the top of the hash chain */
562         offset = tdb_hash_top(tdb, hash);
563
564         /* read in the hash top */
565         if (ofs_read(tdb, offset, &rec_ptr) == -1)
566                 return 0;
567
568         /* keep looking until we find the right record */
569         while (rec_ptr) {
570                 if (rec_read(tdb, rec_ptr, rec) == -1)
571                         return 0;
572
573                 if (hash == rec->full_hash && key.dsize == rec->key_len) {
574                         char *k;
575                         /* a very likely hit - read the key */
576                         k = tdb_alloc_read(tdb, rec_ptr + sizeof(*rec), 
577                                            rec->key_len);
578
579                         if (!k)
580                                 return 0;
581
582                         if (memcmp(key.dptr, k, key.dsize) == 0) {
583                                 free(k);
584                                 return rec_ptr;
585                         }
586                         free(k);
587                 }
588
589                 /* move to the next record */
590                 rec_ptr = rec->next;
591         }
592         return 0;
593 }
594
595 /* 
596    return an error string for the last tdb error
597 */
598 char *tdb_error(TDB_CONTEXT *tdb)
599 {
600         int i;
601         static struct {
602                 enum TDB_ERROR ecode;
603                 char *estring;
604         } emap[] = {
605                 {TDB_SUCCESS, "Success"},
606                 {TDB_ERR_CORRUPT, "Corrupt database"},
607                 {TDB_ERR_IO, "IO Error"},
608                 {TDB_ERR_LOCK, "Locking error"},
609                 {TDB_ERR_OOM, "Out of memory"},
610                 {TDB_ERR_EXISTS, "Record exists"},
611                 {TDB_ERR_NOEXIST, "Record does not exist"},
612                 {-1, NULL}};
613         if (tdb != NULL) {
614             for (i=0;emap[i].estring;i++) {
615                 if (tdb->ecode == emap[i].ecode) return emap[i].estring;
616             }
617         } else {
618             return "Invalid tdb context";
619         }
620         return "Invalid error code";
621 }
622
623
624 /* update an entry in place - this only works if the new data size
625    is <= the old data size and the key exists.
626    on failure return -1
627 */
628 int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)
629 {
630         unsigned hash;
631         struct list_struct rec;
632         tdb_off rec_ptr;
633         int ret = -1;
634
635         if (tdb == NULL) {
636 #ifdef TDB_DEBUG
637             printf("tdb_update() called with null context\n");
638 #endif
639             return -1;
640         }
641
642         /* initialise error code to ok, first */
643         tdb->ecode = 0;
644
645         /* find which hash bucket it is in */
646         hash = tdb_hash(&key);
647
648         tdb_lock(tdb, BUCKET(hash));
649         rec_ptr = tdb_find(tdb, key, hash, &rec);
650
651         if (!rec_ptr) {
652                 tdb->ecode = TDB_ERR_NOEXIST;
653                 goto out;
654         }
655
656         /* must be long enough */
657         if (rec.rec_len < key.dsize + dbuf.dsize)
658                 goto out;
659
660         if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
661                       dbuf.dptr, dbuf.dsize) == -1)
662                 goto out;
663
664         if (dbuf.dsize != rec.data_len) {
665                 /* update size */
666                 rec.data_len = dbuf.dsize;
667                 ret = rec_write(tdb, rec_ptr, &rec);
668         } else
669                 ret = 0;
670
671  out:
672         tdb_unlock(tdb, BUCKET(hash));
673         return ret;
674 }
675
676 /* find an entry in the database given a key */
677 TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key)
678 {
679         unsigned hash;
680         tdb_off rec_ptr;
681         struct list_struct rec;
682         TDB_DATA ret = null_data;
683
684         if (tdb == NULL) {
685 #ifdef TDB_DEBUG
686             printf("tdb_fetch() called with null context\n");
687 #endif
688             return null_data;
689         }
690
691         /* find which hash bucket it is in */
692         hash = tdb_hash(&key);
693
694         tdb_lock(tdb, BUCKET(hash));
695         rec_ptr = tdb_find(tdb, key, hash, &rec);
696
697         if (rec_ptr) {
698                 ret.dptr = tdb_alloc_read(tdb,
699                                           rec_ptr + sizeof(rec) + rec.key_len,
700                                           rec.data_len);
701                 ret.dsize = rec.data_len;
702         }
703         
704         tdb_unlock(tdb, BUCKET(hash));
705         return ret;
706 }
707
708 /* check if an entry in the database exists 
709
710    note that 1 is returned if the key is found and 0 is returned if not found
711    this doesn't match the conventions in the rest of this module, but is
712    compatible with gdbm
713 */
714 int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key)
715 {
716         unsigned hash;
717         tdb_off rec_ptr;
718         struct list_struct rec;
719         
720         if (tdb == NULL) {
721 #ifdef TDB_DEBUG
722             printf("tdb_exists() called with null context\n");
723 #endif
724             return 0;
725         }
726
727         /* find which hash bucket it is in */
728         hash = tdb_hash(&key);
729
730         tdb_lock(tdb, BUCKET(hash));
731         rec_ptr = tdb_find(tdb, key, hash, &rec);
732         tdb_unlock(tdb, BUCKET(hash));
733
734         return rec_ptr != 0;
735 }
736
737 /* traverse the entire database - calling fn(tdb, key, data) on each element.
738    return -1 on error or the record count traversed
739    if fn is NULL then it is not called
740    a non-zero return value from fn() indicates that the traversal should stop
741   */
742 int tdb_traverse(TDB_CONTEXT *tdb, int (*fn)(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, void* state), void* state)
743 {
744         int count = 0;
745         unsigned h;
746         tdb_off offset, rec_ptr;
747         struct list_struct rec;
748         char *data;
749         TDB_DATA key, dbuf;
750
751         if (tdb == NULL) {
752 #ifdef TDB_DEBUG
753             printf("tdb_traverse() called with null context\n");
754 #endif
755             return -1;
756         }
757
758         /* loop over all hash chains */
759         for (h = 0; h < tdb->header.hash_size; h++) {
760                 tdb_lock(tdb, BUCKET(h));
761
762                 /* read in the hash top */
763                 offset = tdb_hash_top(tdb, h);
764                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
765                         goto fail;
766                 }
767
768                 /* traverse all records for this hash */
769                 while (rec_ptr) {
770                         if (rec_read(tdb, rec_ptr, &rec) == -1) {
771                                 goto fail;
772                         }
773
774                         /* now read the full record */
775                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), 
776                                              rec.key_len + rec.data_len);
777                         if (!data) {
778                                 goto fail;
779                         }
780
781                         key.dptr = data;
782                         key.dsize = rec.key_len;
783                         dbuf.dptr = data + rec.key_len;
784                         dbuf.dsize = rec.data_len;
785                         count++;
786
787                         if (fn && fn(tdb, key, dbuf, state) != 0) {
788                                 /* they want us to stop traversing */
789                                 free(data);
790                                 tdb_unlock(tdb, BUCKET(h));
791                                 return count;
792                         }
793
794                         /* a miss - drat */
795                         free(data);
796
797                         /* move to the next record */
798                         rec_ptr = rec.next;
799                 }
800                 tdb_unlock(tdb, BUCKET(h));
801         }
802
803         /* return the number traversed */
804         return count;
805
806  fail:
807         tdb_unlock(tdb, BUCKET(h));
808         return -1;
809 }
810
811
812 /* find the first entry in the database and return its key */
813 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
814 {
815         tdb_off offset, rec_ptr;
816         struct list_struct rec;
817         unsigned hash;
818         TDB_DATA ret;
819
820         if (tdb == NULL) {
821 #ifdef TDB_DEBUG
822             printf("tdb_firstkey() called with null context\n");
823 #endif
824             return null_data;
825         }
826
827         /* look for a non-empty hash chain */
828         for (hash = 0, rec_ptr = 0; 
829              hash < tdb->header.hash_size;
830              hash++) {
831                 /* find the top of the hash chain */
832                 offset = tdb_hash_top(tdb, hash);
833
834                 tdb_lock(tdb, BUCKET(hash));
835
836                 /* read in the hash top */
837                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
838                         goto fail;
839                 }
840
841                 if (rec_ptr) break;
842
843                 tdb_unlock(tdb, BUCKET(hash));
844         }
845
846         if (rec_ptr == 0) return null_data;
847
848         /* we've found a non-empty chain, now read the record */
849         if (rec_read(tdb, rec_ptr, &rec) == -1) {
850                 goto fail;
851         }
852
853         /* allocate and read the key space */
854         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
855         ret.dsize = rec.key_len;
856         tdb_unlock(tdb, BUCKET(hash));
857         return ret;
858
859  fail:
860         tdb_unlock(tdb, BUCKET(hash));
861         return null_data;
862 }
863
864 /* find the next entry in the database, returning its key */
865 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA key)
866 {
867         unsigned hash, hbucket;
868         tdb_off rec_ptr, offset;
869         struct list_struct rec;
870         TDB_DATA ret;
871
872         if (tdb == NULL) {
873 #ifdef TDB_DEBUG
874             printf("tdb_nextkey() called with null context\n");
875 #endif
876             return null_data;
877         }
878
879         /* find which hash bucket it is in */
880         hash = tdb_hash(&key);
881         hbucket = BUCKET(hash);
882         
883         tdb_lock(tdb, hbucket);
884         rec_ptr = tdb_find(tdb, key, hash, &rec);
885         if (rec_ptr) {
886                 /* we want the next record after this one */
887                 rec_ptr = rec.next;
888         }
889
890         /* not found or last in hash: look for next non-empty hash chain */
891         while (rec_ptr == 0) {
892                 tdb_unlock(tdb, hbucket);
893
894                 if (++hbucket >= tdb->header.hash_size - 1)
895                         return null_data;
896
897                 offset = tdb_hash_top(tdb, hbucket);
898                 tdb_lock(tdb, hbucket);
899                 /* read in the hash top */
900                 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
901                         tdb_unlock(tdb, hbucket);
902                         return null_data;
903                 }
904         }
905
906         /* Read the record. */
907         if (rec_read(tdb, rec_ptr, &rec) == -1) {
908                 tdb_unlock(tdb, hbucket);
909                 return null_data;
910         }
911         /* allocate and read the key */
912         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), rec.key_len);
913         ret.dsize = rec.key_len;
914         tdb_unlock(tdb, hbucket);
915
916         return ret;
917 }
918
919 /* delete an entry in the database given a key */
920 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
921 {
922         unsigned hash;
923         tdb_off offset, rec_ptr, last_ptr;
924         struct list_struct rec, lastrec;
925         char *data = NULL;
926
927         if (tdb == NULL) {
928 #ifdef TDB_DEBUG
929             printf("tdb_delete() called with null context\n");
930 #endif
931             return -1;
932         }
933
934         /* find which hash bucket it is in */
935         hash = tdb_hash(&key);
936
937         tdb_lock(tdb, BUCKET(hash));
938
939         /* find the top of the hash chain */
940         offset = tdb_hash_top(tdb, hash);
941
942         /* read in the hash top */
943         if (ofs_read(tdb, offset, &rec_ptr) == -1) {
944                 goto fail;
945         }
946
947         last_ptr = 0;
948
949         /* keep looking until we find the right record */
950         while (rec_ptr) {
951                 if (rec_read(tdb, rec_ptr, &rec) == -1) {
952                         goto fail;
953                 }
954
955                 if (hash == rec.full_hash && key.dsize == rec.key_len) {
956                         /* a very likely hit - read the record and full key */
957                         data = tdb_alloc_read(tdb, rec_ptr + sizeof(rec), 
958                                              rec.key_len);
959                         if (!data) {
960                                 goto fail;
961                         }
962
963                         if (memcmp(key.dptr, data, key.dsize) == 0) {
964                                 /* a definite match - delete it */
965                                 if (last_ptr == 0) {
966                                         offset = tdb_hash_top(tdb, hash);
967                                         if (ofs_write(tdb, offset, &rec.next) == -1) {
968                                                 goto fail;
969                                         }
970                                 } else {
971                                         lastrec.next = rec.next;
972                                         if (rec_write(tdb, last_ptr, &lastrec) == -1) {
973                                                 goto fail;
974                                         }                                       
975                                 }
976                                 tdb_unlock(tdb, BUCKET(hash));
977                                 tdb_lock(tdb, -1);
978                                 /* and recover the space */
979                                 offset = FREELIST_TOP;
980                                 if (ofs_read(tdb, offset, &rec.next) == -1) {
981                                         goto fail2;
982                                 }
983                                 rec.magic = TDB_FREE_MAGIC;
984                                 if (rec_write(tdb, rec_ptr, &rec) == -1) {
985                                         goto fail2;
986                                 }
987                                 if (ofs_write(tdb, offset, &rec_ptr) == -1) {
988                                         goto fail2;
989                                 }
990
991                                 /* yipee - all done */
992                                 free(data);
993                                 tdb_unlock(tdb, -1);
994                                 return 0;
995                         }
996
997                         /* a miss - drat */
998                         free(data);
999                         data = NULL;
1000                 }
1001
1002                 /* move to the next record */
1003                 last_ptr = rec_ptr;
1004                 lastrec = rec;
1005                 rec_ptr = rec.next;
1006         }
1007
1008  fail:
1009         if (data) free(data);
1010         tdb_unlock(tdb, BUCKET(hash));
1011         return -1;
1012
1013  fail2:
1014         if (data) free(data);
1015         tdb_unlock(tdb, -1);
1016         return -1;
1017 }
1018
1019
1020 /* store an element in the database, replacing any existing element
1021    with the same key 
1022
1023    return 0 on success, -1 on failure
1024 */
1025 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
1026 {
1027         struct list_struct rec;
1028         unsigned hash;
1029         tdb_off rec_ptr, offset;
1030         char *p = NULL;
1031
1032         if (tdb == NULL) {
1033 #ifdef TDB_DEBUG
1034             printf("tdb_store() called with null context\n");
1035 #endif
1036             return -1;
1037         }
1038
1039         /* find which hash bucket it is in */
1040         hash = tdb_hash(&key);
1041
1042         /* check for it existing, on insert. */
1043         if (flag == TDB_INSERT && tdb_exists(tdb, key)) {
1044                 tdb->ecode = TDB_ERR_EXISTS;
1045                 return -1;
1046         }
1047
1048         /* first try in-place update, on modify or replace. */
1049         if (flag != TDB_INSERT && tdb_update(tdb, key, dbuf) == 0) {
1050                 return 0;
1051         }
1052
1053         /* check for it _not_ existing, from error code of the update. */
1054         if (flag == TDB_MODIFY && tdb->ecode == TDB_ERR_NOEXIST) {
1055                 return -1;
1056         }
1057
1058         /* reset the error code potentially set by the tdb_update() */
1059         tdb->ecode = 0;
1060
1061         /*
1062          * now we're into insert / modify / replace of a record
1063          * which we know could not be optimised by an in-place
1064          * store (for various reasons).
1065          */
1066
1067         rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize);
1068         if (rec_ptr == 0) {
1069                 return -1;
1070         }
1071
1072         tdb_lock(tdb, BUCKET(hash));
1073
1074         /* delete any existing record - if it doesn't exist we don't care */
1075         if (flag != TDB_INSERT) {
1076                 tdb_delete(tdb, key);
1077         }
1078
1079         /* read the newly created record */
1080         if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec)) == -1) {
1081                 goto fail;
1082         }
1083
1084         if (rec.magic != TDB_FREE_MAGIC) goto fail;
1085
1086         /* find the top of the hash chain */
1087         offset = tdb_hash_top(tdb, hash);
1088
1089         /* read in the hash top diretcly into our next pointer */
1090         if (ofs_read(tdb, offset, &rec.next) == -1) {
1091                 goto fail;
1092         }
1093
1094         rec.key_len = key.dsize;
1095         rec.data_len = dbuf.dsize;
1096         rec.full_hash = hash;
1097         rec.magic = TDB_MAGIC;
1098
1099         p = (char *)malloc(sizeof(rec) + key.dsize + dbuf.dsize);
1100         if (!p) {
1101                 tdb->ecode = TDB_ERR_OOM;
1102                 goto fail;
1103         }
1104
1105         memcpy(p, &rec, sizeof(rec));
1106         memcpy(p+sizeof(rec), key.dptr, key.dsize);
1107         memcpy(p+sizeof(rec)+key.dsize, dbuf.dptr, dbuf.dsize);
1108
1109         if (tdb_write(tdb, rec_ptr, p, sizeof(rec)+key.dsize+dbuf.dsize) == -1)
1110                 goto fail;
1111
1112         free(p); 
1113         p = NULL;
1114
1115         /* and point the top of the hash chain at it */
1116         if (ofs_write(tdb, offset, &rec_ptr) == -1) goto fail;
1117
1118         tdb_unlock(tdb, BUCKET(hash));
1119         return 0;
1120
1121  fail:
1122 #if TDB_DEBUG
1123         printf("store failed for hash 0x%08x in bucket %u\n", hash, BUCKET(hash));
1124 #endif
1125         if (p) free(p);
1126         tdb_unlock(tdb, BUCKET(hash));
1127         return -1;
1128 }
1129
1130
1131 /* open the database, creating it if necessary 
1132
1133    The open_flags and mode are passed straight to the open call on the database
1134    file. A flags value of O_WRONLY is invalid
1135
1136    The hash size is advisory, use zero for a default value. 
1137
1138    return is NULL on error
1139 */
1140 TDB_CONTEXT *tdb_open(char *name, int hash_size, int tdb_flags,
1141                       int open_flags, mode_t mode)
1142 {
1143         TDB_CONTEXT tdb, *ret;
1144         struct stat st;
1145
1146         memset(&tdb, 0, sizeof(tdb));
1147
1148         tdb.fd = -1;
1149         tdb.name = NULL;
1150         tdb.map_ptr = NULL;
1151         tdb.flags = tdb_flags;
1152
1153         if ((open_flags & O_ACCMODE) == O_WRONLY) {
1154                 goto fail;
1155         }
1156
1157         if (hash_size == 0) hash_size = DEFAULT_HASH_SIZE;
1158
1159         tdb.read_only = ((open_flags & O_ACCMODE) == O_RDONLY);
1160
1161         /* internal databases don't use mmap or locking,
1162            and start off cleared */
1163         if (tdb.flags & TDB_INTERNAL) {
1164                 tdb.flags |= (TDB_NOLOCK | TDB_NOMMAP);
1165                 tdb.flags &= ~TDB_CLEAR_IF_FIRST;
1166         }
1167         
1168         /* read only databases don't do locking */
1169         if (tdb.read_only) tdb.flags |= TDB_NOLOCK;
1170
1171         if (tdb.flags & TDB_INTERNAL) {
1172                 tdb_new_database(&tdb, hash_size);
1173                 goto internal;
1174         }
1175
1176         tdb.fd = open(name, open_flags, mode);
1177         if (tdb.fd == -1) {
1178                 goto fail;
1179         }
1180
1181         /* ensure there is only one process initialising at once */
1182         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_SET, F_WRLCK, F_SETLKW);
1183         
1184         if (tdb_flags & TDB_CLEAR_IF_FIRST) {
1185                 /* we need to zero the database if we are the only
1186                    one with it open */
1187                 if (tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_WRLCK, F_SETLK) == 0) {
1188                         ftruncate(tdb.fd, 0);
1189                         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLK);
1190                 }
1191         }
1192
1193         /* leave this lock in place */
1194         tdb_brlock(&tdb, ACTIVE_LOCK, LOCK_SET, F_RDLCK, F_SETLKW);
1195
1196         if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header) ||
1197             strcmp(tdb.header.magic_food, TDB_MAGIC_FOOD) != 0 ||
1198             tdb.header.version != TDB_VERSION) {
1199                 /* its not a valid database - possibly initialise it */
1200                 if (!(open_flags & O_CREAT)) {
1201                         goto fail;
1202                 }
1203                 if (tdb_new_database(&tdb, hash_size) == -1) goto fail;
1204
1205                 lseek(tdb.fd, 0, SEEK_SET);
1206                 if (read(tdb.fd, &tdb.header, sizeof(tdb.header)) != sizeof(tdb.header)) 
1207                     goto fail;
1208         }
1209
1210         fstat(tdb.fd, &st);
1211
1212         /* map the database and fill in the return structure */
1213         tdb.name = (char *)strdup(name);
1214         tdb.map_size = st.st_size;
1215
1216         tdb.locked = (int *)calloc(tdb.header.hash_size+1, 
1217                                    sizeof(tdb.locked[0]));
1218         if (!tdb.locked) {
1219                 goto fail;
1220         }
1221
1222 #if HAVE_MMAP
1223         if (!(tdb->flags & TDB_NOMMAP)) {
1224                 tdb.map_ptr = (void *)mmap(NULL, st.st_size, 
1225                                            tdb.read_only? PROT_READ : PROT_READ|PROT_WRITE,
1226                                            MAP_SHARED | MAP_FILE, tdb.fd, 0);
1227         }
1228 #endif
1229
1230  internal:
1231         ret = (TDB_CONTEXT *)malloc(sizeof(tdb));
1232         if (!ret) goto fail;
1233
1234         *ret = tdb;
1235
1236 #if TDB_DEBUG
1237         printf("mapped database of hash_size %u map_size=%u\n", 
1238                hash_size, tdb.map_size);
1239 #endif
1240
1241         tdb_brlock(&tdb, GLOBAL_LOCK, LOCK_CLEAR, F_WRLCK, F_SETLKW);
1242         return ret;
1243
1244  fail:
1245         if (tdb.name) free(tdb.name);
1246         if (tdb.fd != -1) close(tdb.fd);
1247         if (tdb.map_ptr) munmap(tdb.map_ptr, tdb.map_size);
1248
1249         return NULL;
1250 }
1251
1252 /* close a database */
1253 int tdb_close(TDB_CONTEXT *tdb)
1254 {
1255         if (!tdb) return -1;
1256
1257         if (tdb->name) free(tdb->name);
1258         if (tdb->fd != -1) close(tdb->fd);
1259         if (tdb->locked) free(tdb->locked);
1260
1261         if (tdb->map_ptr) {
1262                 if (tdb->flags & TDB_INTERNAL) {
1263                         free(tdb->map_ptr);
1264                 } else {
1265                         munmap(tdb->map_ptr, tdb->map_size);
1266                 }
1267         }
1268
1269         memset(tdb, 0, sizeof(*tdb));
1270         free(tdb);
1271
1272         return 0;
1273 }
1274
1275 /* lock the database. If we already have it locked then don't do anything */
1276 int tdb_writelock(TDB_CONTEXT *tdb)
1277 {
1278         if (tdb == NULL) {
1279 #ifdef TDB_DEBUG
1280             printf("tdb_writelock() called with null context\n");
1281 #endif
1282             return -1;
1283         }
1284
1285         return tdb_lock(tdb, -1);
1286 }
1287
1288 /* unlock the database. */
1289 int tdb_writeunlock(TDB_CONTEXT *tdb)
1290 {
1291         if (tdb == NULL) {
1292 #ifdef TDB_DEBUG
1293             printf("tdb_writeunlock() called with null context\n");
1294 #endif
1295             return -1;
1296         }
1297
1298         return tdb_unlock(tdb, -1);
1299 }
1300
1301 /* lock one hash chain. This is meant to be used to reduce locking
1302    contention - it cannot guarantee how many records will be locked */
1303 int tdb_lockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1304 {
1305         if (tdb == NULL) {
1306 #ifdef TDB_DEBUG
1307             printf("tdb_lockchain() called with null context\n");
1308 #endif
1309             return -1;
1310         }
1311
1312         return tdb_lock(tdb, BUCKET(tdb_hash(&key)));
1313 }
1314
1315
1316 /* unlock one hash chain */
1317 int tdb_unlockchain(TDB_CONTEXT *tdb, TDB_DATA key)
1318 {
1319         if (tdb == NULL) {
1320 #ifdef TDB_DEBUG
1321             printf("tdb_unlockchain() called with null context\n");
1322 #endif
1323             return -1;
1324         }
1325
1326         return tdb_unlock(tdb, BUCKET(tdb_hash(&key)));
1327 }
1328
1329