3 * Copyright (C) Andrew Tridgell 1999
5 * Redistribution and use in source and binary forms are permitted
6 * provided that the above copyright notice and this paragraph are
7 * duplicated in all such forms AND provided that this software or
8 * any derived work is only used as part of the PPP daemon (pppd)
9 * and related utilities.
10 * The name of the author may not be used to endorse or promote products
11 * derived from this software without specific prior written permission.
12 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
13 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
14 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
16 * Note: this software is also available under the Gnu Public License
31 #define TDB_VERSION (0x26011967 + 1)
32 #define TDB_MAGIC (0x26011999U)
33 #define TDB_FREE_MAGIC (~TDB_MAGIC)
35 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGN)
36 #define DEFAULT_HASH_SIZE 128
37 #define TDB_PAGE_SIZE 0x2000
38 #define TDB_LEN_MULTIPLIER 10
39 #define FREELIST_TOP (sizeof(struct tdb_header))
47 #define LIST_LOCK_BASE 1024
49 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
55 /* the body of the database is made of one list_struct for the free space
56 plus a separate data list for each hash value */
58 tdb_len rec_len
; /* total byte length of record */
59 tdb_off next
; /* offset of the next record in the list */
60 tdb_len key_len
; /* byte length of key */
61 tdb_len data_len
; /* byte length of data */
62 unsigned full_hash
; /* the full 32 bit hash of the key */
63 unsigned magic
; /* try to catch errors */
65 the following union is implied
76 /* a null data record - useful for error returns */
77 static TDB_DATA null_data
;
79 /* a byte range locking function - return 0 on success
80 this functions locks/unlocks 1 byte at the specified offset */
81 static int tdb_brlock(TDB_CONTEXT
*tdb
, tdb_off offset
,
82 int set
, int rw_type
, int lck_type
)
89 if (tdb
->fd
== -1) return 0; /* for in memory tdb */
91 if (tdb
->read_only
) return -1;
93 fl
.l_type
= set
==LOCK_SET
?rw_type
:F_UNLCK
;
94 fl
.l_whence
= SEEK_SET
;
99 if (fcntl(tdb
->fd
, lck_type
, &fl
) != 0) {
101 if (lck_type
== F_SETLKW
) {
102 printf("lock %d failed at %d (%s)\n",
103 set
, offset
, strerror(errno
));
106 tdb
->ecode
= TDB_ERR_LOCK
;
113 /* lock a list in the database. list -1 is the alloc list */
114 static int tdb_lock(TDB_CONTEXT
*tdb
, int list
)
116 if (list
< -1 || list
>= (int)tdb
->header
.hash_size
) {
118 printf("bad list %d\n", list
);
122 if (tdb
->locked
[list
+1] == 0) {
123 if (tdb_brlock(tdb
, LIST_LOCK_BASE
+ 4*list
, LOCK_SET
,
124 F_WRLCK
, F_SETLKW
) != 0) {
128 tdb
->locked
[list
+1]++;
132 /* unlock the database. */
133 static int tdb_unlock(TDB_CONTEXT
*tdb
, int list
)
135 if (list
< -1 || list
>= (int)tdb
->header
.hash_size
) {
137 printf("bad unlock list %d\n", list
);
142 if (tdb
->locked
[list
+1] == 0) {
144 printf("not locked %d\n", list
);
146 tdb
->ecode
= TDB_ERR_LOCK
;
149 if (tdb
->locked
[list
+1] == 1) {
150 if (tdb_brlock(tdb
, LIST_LOCK_BASE
+ 4*list
, LOCK_CLEAR
,
151 F_WRLCK
, F_SETLKW
) != 0) {
155 tdb
->locked
[list
+1]--;
159 /* the hash algorithm - turn a key into an integer
160 This is based on the hash agorithm from gdbm */
161 static unsigned tdb_hash(TDB_DATA
*key
)
163 unsigned value
; /* Used to compute the hash value. */
164 unsigned i
; /* Used to cycle through random values. */
166 /* Set the initial value from the key size. */
167 value
= 0x238F13AF * key
->dsize
;
168 for (i
=0; i
< key
->dsize
; i
++) {
169 value
= (value
+ (key
->dptr
[i
] << (i
*5 % 24)));
172 value
= (1103515243 * value
+ 12345);
177 /* find the top of the hash chain for an open database */
178 static tdb_off
tdb_hash_top(TDB_CONTEXT
*tdb
, unsigned hash
)
182 ret
= FREELIST_TOP
+ (hash
+1)*sizeof(tdb_off
);
187 /* check for an out of bounds access - if it is out of bounds then
188 see if the database has been expanded by someone else and expand
190 static int tdb_oob(TDB_CONTEXT
*tdb
, tdb_off offset
)
193 if ((offset
<= tdb
->map_size
) || (tdb
->fd
== -1)) return 0;
196 if (st
.st_size
<= (ssize_t
)offset
) {
197 tdb
->ecode
= TDB_ERR_IO
;
203 munmap(tdb
->map_ptr
, tdb
->map_size
);
208 tdb
->map_size
= st
.st_size
;
210 tdb
->map_ptr
= (void *)mmap(NULL
, tdb
->map_size
,
211 tdb
->read_only
?PROT_READ
:PROT_READ
|PROT_WRITE
,
212 MAP_SHARED
| MAP_FILE
, tdb
->fd
, 0);
218 /* write a lump of data at a specified offset */
219 static int tdb_write(TDB_CONTEXT
*tdb
, tdb_off offset
, const char *buf
, tdb_len len
)
221 if (tdb_oob(tdb
, offset
+ len
) != 0) {
222 /* oops - trying to write beyond the end of the database! */
227 memcpy(offset
+ (char *)tdb
->map_ptr
, buf
, len
);
229 if (lseek(tdb
->fd
, offset
, SEEK_SET
) != offset
||
230 write(tdb
->fd
, buf
, len
) != (ssize_t
)len
) {
231 tdb
->ecode
= TDB_ERR_IO
;
238 /* read a lump of data at a specified offset */
239 static int tdb_read(TDB_CONTEXT
*tdb
, tdb_off offset
, char *buf
, tdb_len len
)
241 if (tdb_oob(tdb
, offset
+ len
) != 0) {
242 /* oops - trying to read beyond the end of the database! */
247 memcpy(buf
, offset
+ (char *)tdb
->map_ptr
, len
);
249 if (lseek(tdb
->fd
, offset
, SEEK_SET
) != offset
||
250 read(tdb
->fd
, buf
, len
) != (ssize_t
)len
) {
251 tdb
->ecode
= TDB_ERR_IO
;
259 /* read a lump of data, allocating the space for it */
260 static char *tdb_alloc_read(TDB_CONTEXT
*tdb
, tdb_off offset
, tdb_len len
)
264 buf
= (char *)malloc(len
);
267 tdb
->ecode
= TDB_ERR_OOM
;
271 if (tdb_read(tdb
, offset
, buf
, len
) == -1) {
279 /* convenience routine for writing a record */
280 static int rec_write(TDB_CONTEXT
*tdb
, tdb_off offset
, struct list_struct
*rec
)
282 return tdb_write(tdb
, offset
, (char *)rec
, sizeof(*rec
));
285 /* convenience routine for writing a tdb_off */
286 static int ofs_write(TDB_CONTEXT
*tdb
, tdb_off offset
, tdb_off
*d
)
288 return tdb_write(tdb
, offset
, (char *)d
, sizeof(*d
));
291 /* read a tdb_off from the store */
292 static int ofs_read(TDB_CONTEXT
*tdb
, tdb_off offset
, tdb_off
*d
)
294 return tdb_read(tdb
, offset
, (char *)d
, sizeof(*d
));
297 /* read a record and check for simple errors */
298 static int rec_read(TDB_CONTEXT
*tdb
, tdb_off offset
, struct list_struct
*rec
)
300 if (tdb_read(tdb
, offset
, (char *)rec
, sizeof(*rec
)) == -1) return -1;
301 if (rec
->magic
!= TDB_MAGIC
) {
303 printf("bad magic 0x%08x at offset %d\n",
306 tdb
->ecode
= TDB_ERR_CORRUPT
;
309 if (tdb_oob(tdb
, rec
->next
) != 0) {
315 /* expand the database at least length bytes by expanding the
316 underlying file and doing the mmap again if necessary */
317 static int tdb_expand(TDB_CONTEXT
*tdb
, tdb_off length
)
319 struct list_struct rec
;
325 /* make sure we know about any previous expansions by another
327 tdb_oob(tdb
,tdb
->map_size
+ 1);
329 /* always make room for at least 10 more records */
330 length
*= TDB_LEN_MULTIPLIER
;
332 /* and round the database up to a multiple of TDB_PAGE_SIZE */
333 length
= ((tdb
->map_size
+ length
+ TDB_PAGE_SIZE
) & ~(TDB_PAGE_SIZE
- 1)) - tdb
->map_size
;
335 /* expand the file itself */
337 lseek(tdb
->fd
, tdb
->map_size
+ length
- 1, SEEK_SET
);
338 if (write(tdb
->fd
, &b
, 1) != 1) goto fail
;
341 /* form a new freelist record */
342 offset
= FREELIST_TOP
;
343 rec
.rec_len
= length
- sizeof(rec
);
344 rec
.magic
= TDB_FREE_MAGIC
;
345 if (ofs_read(tdb
, offset
, &rec
.next
) == -1) {
350 if (tdb
->fd
!= -1 && tdb
->map_ptr
) {
351 munmap(tdb
->map_ptr
, tdb
->map_size
);
356 tdb
->map_size
+= length
;
359 tdb
->map_ptr
= realloc(tdb
->map_ptr
, tdb
->map_size
);
363 if (rec_write(tdb
, tdb
->map_size
- length
, &rec
) == -1) {
367 /* link it into the free list */
368 ptr
= tdb
->map_size
- length
;
369 if (ofs_write(tdb
, offset
, &ptr
) == -1) goto fail
;
373 tdb
->map_ptr
= (void *)mmap(NULL
, tdb
->map_size
,
374 PROT_READ
|PROT_WRITE
,
375 MAP_SHARED
| MAP_FILE
, tdb
->fd
, 0);
387 /* allocate some space from the free list. The offset returned points
388 to a unconnected list_struct within the database with room for at
389 least length bytes of total data
391 0 is returned if the space could not be allocated
393 static tdb_off
tdb_allocate(TDB_CONTEXT
*tdb
, tdb_len length
)
395 tdb_off offset
, rec_ptr
, last_ptr
;
396 struct list_struct rec
, lastrec
, newrec
;
402 offset
= FREELIST_TOP
;
404 /* read in the freelist top */
405 if (ofs_read(tdb
, offset
, &rec_ptr
) == -1) {
409 /* keep looking until we find a freelist record that is big
412 if (tdb_read(tdb
, rec_ptr
, (char *)&rec
, sizeof(rec
)) == -1) {
416 if (rec
.magic
!= TDB_FREE_MAGIC
) {
418 printf("bad magic 0x%08x in free list\n", rec
.magic
);
423 if (rec
.rec_len
>= length
) {
424 /* found it - now possibly split it up */
425 if (rec
.rec_len
> length
+ MIN_REC_SIZE
) {
426 length
= (length
+ TDB_ALIGN
) & ~(TDB_ALIGN
-1);
428 newrec
.rec_len
= rec
.rec_len
- (sizeof(rec
) + length
);
429 newrec
.next
= rec
.next
;
430 newrec
.magic
= TDB_FREE_MAGIC
;
432 rec
.rec_len
= length
;
433 rec
.next
= rec_ptr
+ sizeof(rec
) + rec
.rec_len
;
435 if (rec_write(tdb
, rec
.next
, &newrec
) == -1) {
439 if (rec_write(tdb
, rec_ptr
, &rec
) == -1) {
444 /* remove it from the list */
446 offset
= FREELIST_TOP
;
448 if (ofs_write(tdb
, offset
, &rec
.next
) == -1) {
452 lastrec
.next
= rec
.next
;
453 if (rec_write(tdb
, last_ptr
, &lastrec
) == -1) {
458 /* all done - return the new record offset */
463 /* move to the next record */
469 /* we didn't find enough space. See if we can expand the
470 database and if we can then try again */
471 if (tdb_expand(tdb
, length
+ sizeof(rec
)) == 0) goto again
;
475 printf("tdb_allocate failed for size %u\n", length
);
481 /* initialise a new database with a specified hash size */
482 static int tdb_new_database(TDB_CONTEXT
*tdb
, int hash_size
)
484 struct tdb_header header
;
489 /* create the header */
490 memset(&header
, 0, sizeof(header
));
491 memcpy(header
.magic_food
, TDB_MAGIC_FOOD
, strlen(TDB_MAGIC_FOOD
)+1);
492 header
.version
= TDB_VERSION
;
493 header
.hash_size
= hash_size
;
494 lseek(tdb
->fd
, 0, SEEK_SET
);
495 ftruncate(tdb
->fd
, 0);
497 if (tdb
->fd
!= -1 && write(tdb
->fd
, &header
, sizeof(header
)) !=
499 tdb
->ecode
= TDB_ERR_IO
;
501 } else size
+= sizeof(header
);
503 /* the freelist and hash pointers */
505 memset(buf
, 0, sizeof(buf
));
507 for (i
=0;(hash_size
+1)-i
>= 16; i
+= 16) {
508 if (tdb
->fd
!= -1 && write(tdb
->fd
, buf
, sizeof(buf
)) !=
510 tdb
->ecode
= TDB_ERR_IO
;
512 } else size
+= sizeof(buf
);
515 for (;i
<hash_size
+1; i
++) {
516 if (tdb
->fd
!= -1 && write(tdb
->fd
, buf
, sizeof(tdb_off
)) !=
518 tdb
->ecode
= TDB_ERR_IO
;
520 } else size
+= sizeof(tdb_off
);
524 tdb
->map_ptr
= calloc(size
, 1);
525 tdb
->map_size
= size
;
526 if (tdb
->map_ptr
== NULL
) {
527 tdb
->ecode
= TDB_ERR_IO
;
530 memcpy(&tdb
->header
, &header
, sizeof(header
));
534 printf("initialised database of hash_size %u\n",
540 /* Returns 0 on fail. On success, return offset of record, and fills
542 static tdb_off
tdb_find(TDB_CONTEXT
*tdb
, TDB_DATA key
, unsigned int hash
,
543 struct list_struct
*rec
)
545 tdb_off offset
, rec_ptr
;
547 /* find the top of the hash chain */
548 offset
= tdb_hash_top(tdb
, hash
);
550 /* read in the hash top */
551 if (ofs_read(tdb
, offset
, &rec_ptr
) == -1)
554 /* keep looking until we find the right record */
556 if (rec_read(tdb
, rec_ptr
, rec
) == -1)
559 if (hash
== rec
->full_hash
&& key
.dsize
== rec
->key_len
) {
561 /* a very likely hit - read the key */
562 k
= tdb_alloc_read(tdb
, rec_ptr
+ sizeof(*rec
),
568 if (memcmp(key
.dptr
, k
, key
.dsize
) == 0) {
575 /* move to the next record */
582 return an error string for the last tdb error
584 char *tdb_error(TDB_CONTEXT
*tdb
)
588 enum TDB_ERROR ecode
;
591 {TDB_SUCCESS
, "Success"},
592 {TDB_ERR_CORRUPT
, "Corrupt database"},
593 {TDB_ERR_IO
, "IO Error"},
594 {TDB_ERR_LOCK
, "Locking error"},
595 {TDB_ERR_OOM
, "Out of memory"},
596 {TDB_ERR_EXISTS
, "Record exists"},
599 for (i
=0;emap
[i
].estring
;i
++) {
600 if (tdb
->ecode
== emap
[i
].ecode
) return emap
[i
].estring
;
603 return "Invalid tdb context";
605 return "Invalid error code";
609 /* update an entry in place - this only works if the new data size
610 is <= the old data size and the key exists.
613 int tdb_update(TDB_CONTEXT
*tdb
, TDB_DATA key
, TDB_DATA dbuf
)
616 struct list_struct rec
;
622 printf("tdb_update() called with null context\n");
627 /* find which hash bucket it is in */
628 hash
= tdb_hash(&key
);
630 tdb_lock(tdb
, BUCKET(hash
));
631 rec_ptr
= tdb_find(tdb
, key
, hash
, &rec
);
636 /* must be long enough */
637 if (rec
.rec_len
< key
.dsize
+ dbuf
.dsize
)
640 if (tdb_write(tdb
, rec_ptr
+ sizeof(rec
) + rec
.key_len
,
641 dbuf
.dptr
, dbuf
.dsize
) == -1)
644 if (dbuf
.dsize
!= rec
.data_len
) {
646 rec
.data_len
= dbuf
.dsize
;
647 ret
= rec_write(tdb
, rec_ptr
, &rec
);
652 tdb_unlock(tdb
, BUCKET(hash
));
656 /* find an entry in the database given a key */
657 TDB_DATA
tdb_fetch(TDB_CONTEXT
*tdb
, TDB_DATA key
)
661 struct list_struct rec
;
662 TDB_DATA ret
= null_data
;
666 printf("tdb_fetch() called with null context\n");
671 /* find which hash bucket it is in */
672 hash
= tdb_hash(&key
);
674 tdb_lock(tdb
, BUCKET(hash
));
675 rec_ptr
= tdb_find(tdb
, key
, hash
, &rec
);
678 ret
.dptr
= tdb_alloc_read(tdb
,
679 rec_ptr
+ sizeof(rec
) + rec
.key_len
,
681 ret
.dsize
= rec
.data_len
;
684 tdb_unlock(tdb
, BUCKET(hash
));
688 /* check if an entry in the database exists
690 note that 1 is returned if the key is found and 0 is returned if not found
691 this doesn't match the conventions in the rest of this module, but is
694 int tdb_exists(TDB_CONTEXT
*tdb
, TDB_DATA key
)
698 struct list_struct rec
;
702 printf("tdb_exists() called with null context\n");
707 /* find which hash bucket it is in */
708 hash
= tdb_hash(&key
);
710 tdb_lock(tdb
, BUCKET(hash
));
711 rec_ptr
= tdb_find(tdb
, key
, hash
, &rec
);
712 tdb_unlock(tdb
, BUCKET(hash
));
717 /* traverse the entire database - calling fn(tdb, key, data) on each element.
718 return -1 on error or the record count traversed
719 if fn is NULL then it is not called
720 a non-zero return value from fn() indicates that the traversal should stop
722 int tdb_traverse(TDB_CONTEXT
*tdb
, int (*fn
)(TDB_CONTEXT
*tdb
, TDB_DATA key
, TDB_DATA dbuf
, void* state
), void* state
)
726 tdb_off offset
, rec_ptr
;
727 struct list_struct rec
;
733 printf("tdb_traverse() called with null context\n");
738 /* loop over all hash chains */
739 for (h
= 0; h
< tdb
->header
.hash_size
; h
++) {
740 tdb_lock(tdb
, BUCKET(h
));
742 /* read in the hash top */
743 offset
= tdb_hash_top(tdb
, h
);
744 if (ofs_read(tdb
, offset
, &rec_ptr
) == -1) {
748 /* traverse all records for this hash */
750 if (rec_read(tdb
, rec_ptr
, &rec
) == -1) {
754 /* now read the full record */
755 data
= tdb_alloc_read(tdb
, rec_ptr
+ sizeof(rec
),
756 rec
.key_len
+ rec
.data_len
);
762 key
.dsize
= rec
.key_len
;
763 dbuf
.dptr
= data
+ rec
.key_len
;
764 dbuf
.dsize
= rec
.data_len
;
767 if (fn
&& fn(tdb
, key
, dbuf
, state
) != 0) {
768 /* they want us to stop traversing */
770 tdb_unlock(tdb
, BUCKET(h
));
777 /* move to the next record */
780 tdb_unlock(tdb
, BUCKET(h
));
783 /* return the number traversed */
787 tdb_unlock(tdb
, BUCKET(h
));
792 /* find the first entry in the database and return its key */
793 TDB_DATA
tdb_firstkey(TDB_CONTEXT
*tdb
)
795 tdb_off offset
, rec_ptr
;
796 struct list_struct rec
;
802 printf("tdb_firstkey() called with null context\n");
807 /* look for a non-empty hash chain */
808 for (hash
= 0, rec_ptr
= 0;
809 hash
< tdb
->header
.hash_size
;
811 /* find the top of the hash chain */
812 offset
= tdb_hash_top(tdb
, hash
);
814 tdb_lock(tdb
, BUCKET(hash
));
816 /* read in the hash top */
817 if (ofs_read(tdb
, offset
, &rec_ptr
) == -1) {
823 tdb_unlock(tdb
, BUCKET(hash
));
826 if (rec_ptr
== 0) return null_data
;
828 /* we've found a non-empty chain, now read the record */
829 if (rec_read(tdb
, rec_ptr
, &rec
) == -1) {
833 /* allocate and read the key space */
834 ret
.dptr
= tdb_alloc_read(tdb
, rec_ptr
+ sizeof(rec
), rec
.key_len
);
835 ret
.dsize
= rec
.key_len
;
836 tdb_unlock(tdb
, BUCKET(hash
));
840 tdb_unlock(tdb
, BUCKET(hash
));
844 /* find the next entry in the database, returning its key */
845 TDB_DATA
tdb_nextkey(TDB_CONTEXT
*tdb
, TDB_DATA key
)
847 unsigned hash
, hbucket
;
848 tdb_off rec_ptr
, offset
;
849 struct list_struct rec
;
854 printf("tdb_nextkey() called with null context\n");
859 /* find which hash bucket it is in */
860 hash
= tdb_hash(&key
);
861 hbucket
= BUCKET(hash
);
863 tdb_lock(tdb
, hbucket
);
864 rec_ptr
= tdb_find(tdb
, key
, hash
, &rec
);
866 /* we want the next record after this one */
870 /* not found or last in hash: look for next non-empty hash chain */
871 while (rec_ptr
== 0) {
872 tdb_unlock(tdb
, hbucket
);
874 if (++hbucket
>= tdb
->header
.hash_size
- 1)
877 offset
= tdb_hash_top(tdb
, hbucket
);
878 tdb_lock(tdb
, hbucket
);
879 /* read in the hash top */
880 if (ofs_read(tdb
, offset
, &rec_ptr
) == -1) {
881 tdb_unlock(tdb
, hbucket
);
886 /* Read the record. */
887 if (rec_read(tdb
, rec_ptr
, &rec
) == -1) {
888 tdb_unlock(tdb
, hbucket
);
891 /* allocate and read the key */
892 ret
.dptr
= tdb_alloc_read(tdb
, rec_ptr
+ sizeof(rec
), rec
.key_len
);
893 ret
.dsize
= rec
.key_len
;
894 tdb_unlock(tdb
, hbucket
);
899 /* delete an entry in the database given a key */
900 int tdb_delete(TDB_CONTEXT
*tdb
, TDB_DATA key
)
903 tdb_off offset
, rec_ptr
, last_ptr
;
904 struct list_struct rec
, lastrec
;
909 printf("tdb_delete() called with null context\n");
914 /* find which hash bucket it is in */
915 hash
= tdb_hash(&key
);
917 tdb_lock(tdb
, BUCKET(hash
));
919 /* find the top of the hash chain */
920 offset
= tdb_hash_top(tdb
, hash
);
922 /* read in the hash top */
923 if (ofs_read(tdb
, offset
, &rec_ptr
) == -1) {
929 /* keep looking until we find the right record */
931 if (rec_read(tdb
, rec_ptr
, &rec
) == -1) {
935 if (hash
== rec
.full_hash
&& key
.dsize
== rec
.key_len
) {
936 /* a very likely hit - read the record and full key */
937 data
= tdb_alloc_read(tdb
, rec_ptr
+ sizeof(rec
),
943 if (memcmp(key
.dptr
, data
, key
.dsize
) == 0) {
944 /* a definite match - delete it */
946 offset
= tdb_hash_top(tdb
, hash
);
947 if (ofs_write(tdb
, offset
, &rec
.next
) == -1) {
951 lastrec
.next
= rec
.next
;
952 if (rec_write(tdb
, last_ptr
, &lastrec
) == -1) {
956 tdb_unlock(tdb
, BUCKET(hash
));
958 /* and recover the space */
959 offset
= FREELIST_TOP
;
960 if (ofs_read(tdb
, offset
, &rec
.next
) == -1) {
963 rec
.magic
= TDB_FREE_MAGIC
;
964 if (rec_write(tdb
, rec_ptr
, &rec
) == -1) {
967 if (ofs_write(tdb
, offset
, &rec_ptr
) == -1) {
971 /* yipee - all done */
982 /* move to the next record */
989 if (data
) free(data
);
990 tdb_unlock(tdb
, BUCKET(hash
));
994 if (data
) free(data
);
1000 /* store an element in the database, replacing any existing element
1003 return 0 on success, -1 on failure
1005 int tdb_store(TDB_CONTEXT
*tdb
, TDB_DATA key
, TDB_DATA dbuf
, int flag
)
1007 struct list_struct rec
;
1009 tdb_off rec_ptr
, offset
;
1014 printf("tdb_store() called with null context\n");
1019 /* find which hash bucket it is in */
1020 hash
= tdb_hash(&key
);
1022 /* check for it existing */
1023 if (flag
== TDB_INSERT
&& tdb_exists(tdb
, key
)) {
1024 tdb
->ecode
= TDB_ERR_EXISTS
;
1028 /* first try in-place update */
1029 if (flag
!= TDB_INSERT
&& tdb_update(tdb
, key
, dbuf
) == 0) {
1033 rec_ptr
= tdb_allocate(tdb
, key
.dsize
+ dbuf
.dsize
);
1038 tdb_lock(tdb
, BUCKET(hash
));
1040 /* delete any existing record - if it doesn't exist we don't care */
1041 if (flag
!= TDB_INSERT
) {
1042 tdb_delete(tdb
, key
);
1045 /* read the newly created record */
1046 if (tdb_read(tdb
, rec_ptr
, (char *)&rec
, sizeof(rec
)) == -1) {
1050 if (rec
.magic
!= TDB_FREE_MAGIC
) goto fail
;
1052 /* find the top of the hash chain */
1053 offset
= tdb_hash_top(tdb
, hash
);
1055 /* read in the hash top diretcly into our next pointer */
1056 if (ofs_read(tdb
, offset
, &rec
.next
) == -1) {
1060 rec
.key_len
= key
.dsize
;
1061 rec
.data_len
= dbuf
.dsize
;
1062 rec
.full_hash
= hash
;
1063 rec
.magic
= TDB_MAGIC
;
1065 p
= (char *)malloc(sizeof(rec
) + key
.dsize
+ dbuf
.dsize
);
1067 tdb
->ecode
= TDB_ERR_OOM
;
1071 memcpy(p
, &rec
, sizeof(rec
));
1072 memcpy(p
+sizeof(rec
), key
.dptr
, key
.dsize
);
1073 memcpy(p
+sizeof(rec
)+key
.dsize
, dbuf
.dptr
, dbuf
.dsize
);
1075 if (tdb_write(tdb
, rec_ptr
, p
, sizeof(rec
)+key
.dsize
+dbuf
.dsize
) == -1)
1081 /* and point the top of the hash chain at it */
1082 if (ofs_write(tdb
, offset
, &rec_ptr
) == -1) goto fail
;
1084 tdb_unlock(tdb
, BUCKET(hash
));
1089 printf("store failed for hash 0x%08x in bucket %u\n", hash
, BUCKET(hash
));
1092 tdb_unlock(tdb
, BUCKET(hash
));
1097 /* open the database, creating it if necessary
1099 The open_flags and mode are passed straight to the open call on the database
1100 file. A flags value of O_WRONLY is invalid
1102 The hash size is advisory, use zero for a default value.
1104 return is NULL on error
1106 TDB_CONTEXT
*tdb_open(char *name
, int hash_size
, int tdb_flags
,
1107 int open_flags
, mode_t mode
)
1109 TDB_CONTEXT tdb
, *ret
;
1112 memset(&tdb
, 0, sizeof(tdb
));
1118 if ((open_flags
& O_ACCMODE
) == O_WRONLY
) {
1122 if (hash_size
== 0) hash_size
= DEFAULT_HASH_SIZE
;
1124 tdb
.read_only
= ((open_flags
& O_ACCMODE
) == O_RDONLY
);
1127 tdb
.fd
= open(name
, open_flags
, mode
);
1133 /* ensure there is only one process initialising at once */
1134 tdb_brlock(&tdb
, GLOBAL_LOCK
, LOCK_SET
, F_WRLCK
, F_SETLKW
);
1136 if (tdb_flags
& TDB_CLEAR_IF_FIRST
) {
1137 /* we need to zero the database if we are the only
1139 if (tdb_brlock(&tdb
, ACTIVE_LOCK
, LOCK_SET
, F_WRLCK
, F_SETLK
) == 0) {
1140 ftruncate(tdb
.fd
, 0);
1141 tdb_brlock(&tdb
, ACTIVE_LOCK
, LOCK_CLEAR
, F_WRLCK
, F_SETLK
);
1145 /* leave this lock in place */
1146 tdb_brlock(&tdb
, ACTIVE_LOCK
, LOCK_SET
, F_RDLCK
, F_SETLKW
);
1148 if (read(tdb
.fd
, &tdb
.header
, sizeof(tdb
.header
)) != sizeof(tdb
.header
) ||
1149 strcmp(tdb
.header
.magic_food
, TDB_MAGIC_FOOD
) != 0 ||
1150 tdb
.header
.version
!= TDB_VERSION
) {
1151 /* its not a valid database - possibly initialise it */
1152 if (!(open_flags
& O_CREAT
)) {
1155 if (tdb_new_database(&tdb
, hash_size
) == -1) goto fail
;
1157 lseek(tdb
.fd
, 0, SEEK_SET
);
1158 if (tdb
.fd
!= -1 && read(tdb
.fd
, &tdb
.header
,
1159 sizeof(tdb
.header
)) !=
1167 /* map the database and fill in the return structure */
1168 tdb
.name
= (char *)strdup(name
);
1169 tdb
.map_size
= st
.st_size
;
1172 tdb
.locked
= (int *)calloc(tdb
.header
.hash_size
+1,
1173 sizeof(tdb
.locked
[0]));
1180 tdb
.map_ptr
= (void *)mmap(NULL
, st
.st_size
,
1181 tdb
.read_only
? PROT_READ
: PROT_READ
|PROT_WRITE
,
1182 MAP_SHARED
| MAP_FILE
, tdb
.fd
, 0);
1186 ret
= (TDB_CONTEXT
*)malloc(sizeof(tdb
));
1187 if (!ret
) goto fail
;
1192 printf("mapped database of hash_size %u map_size=%u\n",
1193 hash_size
, tdb
.map_size
);
1196 tdb_brlock(&tdb
, GLOBAL_LOCK
, LOCK_CLEAR
, F_WRLCK
, F_SETLKW
);
1200 if (tdb
.name
) free(tdb
.name
);
1201 if (tdb
.fd
!= -1) close(tdb
.fd
);
1202 if (tdb
.map_ptr
) munmap(tdb
.map_ptr
, tdb
.map_size
);
1207 /* close a database */
1208 int tdb_close(TDB_CONTEXT
*tdb
)
1210 if (!tdb
) return -1;
1212 if (tdb
->name
) free(tdb
->name
);
1213 if (tdb
->fd
!= -1) close(tdb
->fd
);
1214 if (tdb
->locked
) free(tdb
->locked
);
1217 if (tdb
->fd
!= -1) {
1218 munmap(tdb
->map_ptr
, tdb
->map_size
);
1224 memset(tdb
, 0, sizeof(*tdb
));
1230 /* lock the database. If we already have it locked then don't do anything */
1231 int tdb_writelock(TDB_CONTEXT
*tdb
)
1235 printf("tdb_writelock() called with null context\n");
1240 return tdb_lock(tdb
, -1);
1243 /* unlock the database. */
1244 int tdb_writeunlock(TDB_CONTEXT
*tdb
)
1248 printf("tdb_writeunlock() called with null context\n");
1253 return tdb_unlock(tdb
, -1);
1256 /* lock one hash chain. This is meant to be used to reduce locking
1257 contention - it cannot guarantee how many records will be locked */
1258 int tdb_lockchain(TDB_CONTEXT
*tdb
, TDB_DATA key
)
1262 printf("tdb_lockchain() called with null context\n");
1267 return tdb_lock(tdb
, BUCKET(tdb_hash(&key
)));
1271 /* unlock one hash chain */
1272 int tdb_unlockchain(TDB_CONTEXT
*tdb
, TDB_DATA key
)
1276 printf("tdb_unlockchain() called with null context\n");
1281 return tdb_unlock(tdb
, BUCKET(tdb_hash(&key
)));