2 Unix SMB/CIFS implementation.
3 Samba database functions
4 Copyright (C) Andrew Tridgell 1999-2000
5 Copyright (C) Luke Kenneth Casson Leighton 2000
6 Copyright (C) Paul `Rusty' Russell 2000
7 Copyright (C) Jeremy Allison 2000-2003
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
25 /* NOTE: If you use tdbs under valgrind, and in particular if you run
26 * tdbtorture, you may get spurious "uninitialized value" warnings. I
27 * think this is because valgrind doesn't understand that the mmap'd
28 * area may be written to by other processes. Memory can, from the
29 * point of view of the grinded process, spontaneously become
32 * I can think of a few solutions. [mbp 20030311]
34 * 1 - Write suppressions for Valgrind so that it doesn't complain
35 * about this. Probably the most reasonable but people need to
36 * remember to use them.
38 * 2 - Use IO not mmap when running under valgrind. Not so nice.
40 * 3 - Use the special valgrind macros to mark memory as valid at the
41 * right time. Probably too hard -- the process just doesn't know.
48 /* this should prevent deadlocks loops on corrupt databases
49 * we've discovered. Most deadlocks happend by iterating over the
50 * list of entries with the same hash value. */
51 #define LOOP_MAX 100000
52 #define TDB_LOG(x) TDB_LOG_UDEV x
53 #define TDB_LOG_UDEV(tdb, level, format, arg...) info(format, ##arg)
60 #define _KLIBC_HAS_ARCH_SIG_ATOMIC_T
73 #include "../udev_lib.h"
74 #include "../logging.h"
79 #define TDB_MAGIC_FOOD "TDB file\n"
80 #define TDB_VERSION (0x26011967 + 6)
81 #define TDB_MAGIC (0x26011999U)
82 #define TDB_FREE_MAGIC (~TDB_MAGIC)
83 #define TDB_DEAD_MAGIC (0xFEE1DEAD)
84 #define TDB_ALIGNMENT 4
85 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGNMENT)
86 #define DEFAULT_HASH_SIZE 131
87 #define TDB_PAGE_SIZE 0x2000
88 #define FREELIST_TOP (sizeof(struct tdb_header))
89 #define TDB_ALIGN(x,a) (((x) + (a)-1) & ~((a)-1))
90 #define TDB_BYTEREV(x) (((((x)&0xff)<<24)|((x)&0xFF00)<<8)|(((x)>>8)&0xFF00)|((x)>>24))
91 #define TDB_DEAD(r) ((r)->magic == TDB_DEAD_MAGIC)
92 #define TDB_BAD_MAGIC(r) ((r)->magic != TDB_MAGIC && !TDB_DEAD(r))
93 #define TDB_HASH_TOP(hash) (FREELIST_TOP + (BUCKET(hash)+1)*sizeof(tdb_off))
95 /* NB assumes there is a local variable called "tdb" that is the
96 * current context, also takes doubly-parenthesized print-style
99 #define TDB_LOG(x) (tdb->log_fn?((tdb->log_fn x),0) : 0)
103 #define GLOBAL_LOCK 0
104 #define ACTIVE_LOCK 4
111 #define MAP_FAILED ((void *)-1)
114 /* free memory if the pointer is valid and zero the pointer */
116 #define SAFE_FREE(x) do { if ((x) != NULL) {free((x)); (x)=NULL;} } while(0)
119 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
122 /* all contexts, to ensure no double-opens (fcntl locks don't nest!) */
123 static TDB_CONTEXT *tdbs = NULL;
125 static int tdb_munmap(TDB_CONTEXT *tdb)
127 if (tdb->flags & TDB_INTERNAL)
132 int ret = munmap(tdb->map_ptr, tdb->map_size);
141 static void tdb_mmap(TDB_CONTEXT *tdb)
143 if (tdb->flags & TDB_INTERNAL)
147 if (!(tdb->flags & TDB_NOMMAP)) {
148 tdb->map_ptr = mmap(NULL, tdb->map_size,
149 PROT_READ|(tdb->read_only? 0:PROT_WRITE),
150 MAP_SHARED|MAP_FILE, tdb->fd, 0);
153 * NB. When mmap fails it returns MAP_FAILED *NOT* NULL !!!!
156 if (tdb->map_ptr == MAP_FAILED) {
158 TDB_LOG((tdb, 2, "tdb_mmap failed for size %d (%s)\n",
159 tdb->map_size, strerror(errno)));
169 /* Endian conversion: we only ever deal with 4 byte quantities */
170 static void *convert(void *buf, u32 size)
173 for (i = 0; i < size / 4; i++)
174 p[i] = TDB_BYTEREV(p[i]);
177 #define DOCONV() (tdb->flags & TDB_CONVERT)
178 #define CONVERT(x) (DOCONV() ? convert(&x, sizeof(x)) : &x)
180 /* the body of the database is made of one list_struct for the free space
181 plus a separate data list for each hash value */
183 tdb_off next; /* offset of the next record in the list */
184 tdb_len rec_len; /* total byte length of record */
185 tdb_len key_len; /* byte length of key */
186 tdb_len data_len; /* byte length of data */
187 u32 full_hash; /* the full 32 bit hash of the key */
188 u32 magic; /* try to catch errors */
189 /* the following union is implied:
191 char record[rec_len];
196 u32 totalsize; (tailer)
201 /***************************************************************
202 Allow a caller to set a "alarm" flag that tdb can check to abort
203 a blocking lock on SIGALRM.
204 ***************************************************************/
206 static sig_atomic_t *palarm_fired;
208 void tdb_set_lock_alarm(sig_atomic_t *palarm)
210 palarm_fired = palarm;
213 /* a byte range locking function - return 0 on success
214 this functions locks/unlocks 1 byte at the specified offset.
216 On error, errno is also set so that errors are passed back properly
217 through tdb_open(). */
218 static int tdb_brlock(TDB_CONTEXT *tdb, tdb_off offset,
219 int rw_type, int lck_type, int probe)
224 if (tdb->flags & TDB_NOLOCK)
226 if ((rw_type == F_WRLCK) && (tdb->read_only)) {
232 fl.l_whence = SEEK_SET;
238 ret = fcntl(tdb->fd,lck_type,&fl);
239 if (ret == -1 && errno == EINTR && palarm_fired && *palarm_fired)
241 } while (ret == -1 && errno == EINTR);
244 if (!probe && lck_type != F_SETLK) {
245 /* Ensure error code is set for log fun to examine. */
246 if (errno == EINTR && palarm_fired && *palarm_fired)
247 tdb->ecode = TDB_ERR_LOCK_TIMEOUT;
249 tdb->ecode = TDB_ERR_LOCK;
250 TDB_LOG((tdb, 5,"tdb_brlock failed (fd=%d) at offset %d rw_type=%d lck_type=%d\n",
251 tdb->fd, offset, rw_type, lck_type));
253 /* Was it an alarm timeout ? */
254 if (errno == EINTR && palarm_fired && *palarm_fired)
255 return TDB_ERRCODE(TDB_ERR_LOCK_TIMEOUT, -1);
256 /* Otherwise - generic lock error. */
257 /* errno set by fcntl */
258 return TDB_ERRCODE(TDB_ERR_LOCK, -1);
263 /* lock a list in the database. list -1 is the alloc list */
264 static int tdb_lock(TDB_CONTEXT *tdb, int list, int ltype)
266 if (list < -1 || list >= (int)tdb->header.hash_size) {
267 TDB_LOG((tdb, 0,"tdb_lock: invalid list %d for ltype=%d\n",
271 if (tdb->flags & TDB_NOLOCK)
274 /* Since fcntl locks don't nest, we do a lock for the first one,
275 and simply bump the count for future ones */
276 if (tdb->locked[list+1].count == 0) {
277 if (!tdb->read_only && tdb->header.rwlocks) {
278 if (tdb_spinlock(tdb, list, ltype)) {
279 TDB_LOG((tdb, 0, "tdb_lock spinlock failed on list %d ltype=%d\n",
283 } else if (tdb_brlock(tdb,FREELIST_TOP+4*list,ltype,F_SETLKW, 0)) {
284 TDB_LOG((tdb, 0,"tdb_lock failed on list %d ltype=%d (%s)\n",
285 list, ltype, strerror(errno)));
288 tdb->locked[list+1].ltype = ltype;
290 tdb->locked[list+1].count++;
294 /* unlock the database: returns void because it's too late for errors. */
295 /* changed to return int it may be interesting to know there
296 has been an error --simo */
297 static int tdb_unlock(TDB_CONTEXT *tdb, int list, int ltype)
301 if (tdb->flags & TDB_NOLOCK)
305 if (list < -1 || list >= (int)tdb->header.hash_size) {
306 TDB_LOG((tdb, 0, "tdb_unlock: list %d invalid (%d)\n", list, tdb->header.hash_size));
310 if (tdb->locked[list+1].count==0) {
311 TDB_LOG((tdb, 0, "tdb_unlock: count is 0\n"));
315 if (tdb->locked[list+1].count == 1) {
316 /* Down to last nested lock: unlock underneath */
317 if (!tdb->read_only && tdb->header.rwlocks) {
318 ret = tdb_spinunlock(tdb, list, ltype);
320 ret = tdb_brlock(tdb, FREELIST_TOP+4*list, F_UNLCK, F_SETLKW, 0);
325 tdb->locked[list+1].count--;
328 TDB_LOG((tdb, 0,"tdb_unlock: An error occurred unlocking!\n"));
332 /* This is based on the hash algorithm from gdbm */
333 static u32 tdb_hash(TDB_DATA *key)
335 u32 value; /* Used to compute the hash value. */
336 u32 i; /* Used to cycle through random values. */
338 /* Set the initial value from the key size. */
339 for (value = 0x238F13AF * key->dsize, i=0; i < key->dsize; i++)
340 value = (value + (key->dptr[i] << (i*5 % 24)));
342 return (1103515243 * value + 12345);
345 /* check for an out of bounds access - if it is out of bounds then
346 see if the database has been expanded by someone else and expand
348 note that "len" is the minimum length needed for the db
350 static int tdb_oob(TDB_CONTEXT *tdb, tdb_off len, int probe)
353 if (len <= tdb->map_size)
355 if (tdb->flags & TDB_INTERNAL) {
357 /* Ensure ecode is set for log fn. */
358 tdb->ecode = TDB_ERR_IO;
359 TDB_LOG((tdb, 0,"tdb_oob len %d beyond internal malloc size %d\n",
360 (int)len, (int)tdb->map_size));
362 return TDB_ERRCODE(TDB_ERR_IO, -1);
365 if (fstat(tdb->fd, &st) == -1)
366 return TDB_ERRCODE(TDB_ERR_IO, -1);
368 if (st.st_size < (size_t)len) {
370 /* Ensure ecode is set for log fn. */
371 tdb->ecode = TDB_ERR_IO;
372 TDB_LOG((tdb, 0,"tdb_oob len %d beyond eof at %d\n",
373 (int)len, (int)st.st_size));
375 return TDB_ERRCODE(TDB_ERR_IO, -1);
378 /* Unmap, update size, remap */
379 if (tdb_munmap(tdb) == -1)
380 return TDB_ERRCODE(TDB_ERR_IO, -1);
381 tdb->map_size = st.st_size;
386 /* write a lump of data at a specified offset */
387 static int tdb_write(TDB_CONTEXT *tdb, tdb_off off, void *buf, tdb_len len)
389 if (tdb_oob(tdb, off + len, 0) != 0)
393 memcpy(off + (char *)tdb->map_ptr, buf, len);
395 else if (pwrite(tdb->fd, buf, len, off) != (ssize_t)len) {
397 else if (lseek(tdb->fd, off, SEEK_SET) != off
398 || write(tdb->fd, buf, len) != (ssize_t)len) {
400 /* Ensure ecode is set for log fn. */
401 tdb->ecode = TDB_ERR_IO;
402 TDB_LOG((tdb, 0,"tdb_write failed at %d len=%d (%s)\n",
403 off, len, strerror(errno)));
404 return TDB_ERRCODE(TDB_ERR_IO, -1);
409 /* read a lump of data at a specified offset, maybe convert */
410 static int tdb_read(TDB_CONTEXT *tdb,tdb_off off,void *buf,tdb_len len,int cv)
412 if (tdb_oob(tdb, off + len, 0) != 0)
416 memcpy(buf, off + (char *)tdb->map_ptr, len);
418 else if (pread(tdb->fd, buf, len, off) != (ssize_t)len) {
420 else if (lseek(tdb->fd, off, SEEK_SET) != off
421 || read(tdb->fd, buf, len) != (ssize_t)len) {
423 /* Ensure ecode is set for log fn. */
424 tdb->ecode = TDB_ERR_IO;
425 TDB_LOG((tdb, 0,"tdb_read failed at %d len=%d (%s)\n",
426 off, len, strerror(errno)));
427 return TDB_ERRCODE(TDB_ERR_IO, -1);
434 /* read a lump of data, allocating the space for it */
435 static char *tdb_alloc_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_len len)
439 if (!(buf = malloc(len))) {
440 /* Ensure ecode is set for log fn. */
441 tdb->ecode = TDB_ERR_OOM;
442 TDB_LOG((tdb, 0,"tdb_alloc_read malloc failed len=%d (%s)\n",
443 len, strerror(errno)));
444 return TDB_ERRCODE(TDB_ERR_OOM, buf);
446 if (tdb_read(tdb, offset, buf, len, 0) == -1) {
453 /* read/write a tdb_off */
454 static int ofs_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
456 return tdb_read(tdb, offset, (char*)d, sizeof(*d), DOCONV());
458 static int ofs_write(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
461 return tdb_write(tdb, offset, CONVERT(off), sizeof(*d));
464 /* read/write a record */
465 static int rec_read(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
467 if (tdb_read(tdb, offset, rec, sizeof(*rec),DOCONV()) == -1)
469 if (TDB_BAD_MAGIC(rec)) {
470 /* Ensure ecode is set for log fn. */
471 tdb->ecode = TDB_ERR_CORRUPT;
472 TDB_LOG((tdb, 0,"rec_read bad magic 0x%x at offset=%d\n", rec->magic, offset));
473 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
475 return tdb_oob(tdb, rec->next+sizeof(*rec), 0);
477 static int rec_write(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
479 struct list_struct r = *rec;
480 return tdb_write(tdb, offset, CONVERT(r), sizeof(r));
483 /* read a freelist record and check for simple errors */
484 static int rec_free_read(TDB_CONTEXT *tdb, tdb_off off, struct list_struct *rec)
486 if (tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
489 if (rec->magic == TDB_MAGIC) {
490 /* this happens when a app is showdown while deleting a record - we should
491 not completely fail when this happens */
492 TDB_LOG((tdb, 0,"rec_free_read non-free magic 0x%x at offset=%d - fixing\n",
494 rec->magic = TDB_FREE_MAGIC;
495 if (tdb_write(tdb, off, rec, sizeof(*rec)) == -1)
499 if (rec->magic != TDB_FREE_MAGIC) {
500 /* Ensure ecode is set for log fn. */
501 tdb->ecode = TDB_ERR_CORRUPT;
502 TDB_LOG((tdb, 0,"rec_free_read bad magic 0x%x at offset=%d\n",
504 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
506 if (tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0)
511 /* update a record tailer (must hold allocation lock) */
512 static int update_tailer(TDB_CONTEXT *tdb, tdb_off offset,
513 const struct list_struct *rec)
517 /* Offset of tailer from record header */
518 totalsize = sizeof(*rec) + rec->rec_len;
519 return ofs_write(tdb, offset + totalsize - sizeof(tdb_off),
523 static tdb_off tdb_dump_record(TDB_CONTEXT *tdb, tdb_off offset)
525 struct list_struct rec;
526 tdb_off tailer_ofs, tailer;
528 if (tdb_read(tdb, offset, (char *)&rec, sizeof(rec), DOCONV()) == -1) {
529 printf("ERROR: failed to read record at %u\n", offset);
533 printf(" rec: offset=%u next=%d rec_len=%d key_len=%d data_len=%d full_hash=0x%x magic=0x%x\n",
534 offset, rec.next, rec.rec_len, rec.key_len, rec.data_len, rec.full_hash, rec.magic);
536 tailer_ofs = offset + sizeof(rec) + rec.rec_len - sizeof(tdb_off);
537 if (ofs_read(tdb, tailer_ofs, &tailer) == -1) {
538 printf("ERROR: failed to read tailer at %u\n", tailer_ofs);
542 if (tailer != rec.rec_len + sizeof(rec)) {
543 printf("ERROR: tailer does not match record! tailer=%u totalsize=%u\n",
544 (unsigned)tailer, (unsigned)(rec.rec_len + sizeof(rec)));
549 static int tdb_dump_chain(TDB_CONTEXT *tdb, int i)
551 tdb_off rec_ptr, top;
553 top = TDB_HASH_TOP(i);
555 if (tdb_lock(tdb, i, F_WRLCK) != 0)
558 if (ofs_read(tdb, top, &rec_ptr) == -1)
559 return tdb_unlock(tdb, i, F_WRLCK);
562 printf("hash=%d\n", i);
565 rec_ptr = tdb_dump_record(tdb, rec_ptr);
568 return tdb_unlock(tdb, i, F_WRLCK);
571 void tdb_dump_all(TDB_CONTEXT *tdb)
574 for (i=0;i<tdb->header.hash_size;i++) {
575 tdb_dump_chain(tdb, i);
577 printf("freelist:\n");
578 tdb_dump_chain(tdb, -1);
581 int tdb_printfreelist(TDB_CONTEXT *tdb)
585 tdb_off offset, rec_ptr;
586 struct list_struct rec;
588 if ((ret = tdb_lock(tdb, -1, F_WRLCK)) != 0)
591 offset = FREELIST_TOP;
593 /* read in the freelist top */
594 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
595 tdb_unlock(tdb, -1, F_WRLCK);
599 printf("freelist top=[0x%08x]\n", rec_ptr );
601 if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec), DOCONV()) == -1) {
602 tdb_unlock(tdb, -1, F_WRLCK);
606 if (rec.magic != TDB_FREE_MAGIC) {
607 printf("bad magic 0x%08x in free list\n", rec.magic);
608 tdb_unlock(tdb, -1, F_WRLCK);
612 printf("entry offset=[0x%08x], rec.rec_len = [0x%08x (%d)]\n", rec.next, rec.rec_len, rec.rec_len );
613 total_free += rec.rec_len;
615 /* move to the next record */
618 printf("total rec_len = [0x%08x (%d)]\n", (int)total_free,
621 return tdb_unlock(tdb, -1, F_WRLCK);
624 /* Remove an element from the freelist. Must have alloc lock. */
625 static int remove_from_freelist(TDB_CONTEXT *tdb, tdb_off off, tdb_off next)
630 /* read in the freelist top */
632 last_ptr = FREELIST_TOP;
633 while (ofs_read(tdb, last_ptr, &i) != -1 && i != 0) {
635 /* We've found it! */
636 return ofs_write(tdb, last_ptr, &next);
638 /* Follow chain (next offset is at start of record) */
643 TDB_LOG((tdb, 0, "remove_from_freelist: maxloop reached; corrupt database!\n"));
644 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
647 TDB_LOG((tdb, 0,"remove_from_freelist: not on list at off=%d\n", off));
648 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
651 /* Add an element into the freelist. Merge adjacent records if
653 static int tdb_free(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
657 /* Allocation and tailer lock */
658 if (tdb_lock(tdb, -1, F_WRLCK) != 0)
661 /* set an initial tailer, so if we fail we don't leave a bogus record */
662 if (update_tailer(tdb, offset, rec) != 0) {
663 TDB_LOG((tdb, 0, "tdb_free: upfate_tailer failed!\n"));
667 /* Look right first (I'm an Australian, dammit) */
668 right = offset + sizeof(*rec) + rec->rec_len;
669 if (right + sizeof(*rec) <= tdb->map_size) {
670 struct list_struct r;
672 if (tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
673 TDB_LOG((tdb, 0, "tdb_free: right read failed at %u\n", right));
677 /* If it's free, expand to include it. */
678 if (r.magic == TDB_FREE_MAGIC) {
679 if (remove_from_freelist(tdb, right, r.next) == -1) {
680 TDB_LOG((tdb, 0, "tdb_free: right free failed at %u\n", right));
683 rec->rec_len += sizeof(r) + r.rec_len;
689 left = offset - sizeof(tdb_off);
690 if (left > TDB_HASH_TOP(tdb->header.hash_size-1)) {
691 struct list_struct l;
694 /* Read in tailer and jump back to header */
695 if (ofs_read(tdb, left, &leftsize) == -1) {
696 TDB_LOG((tdb, 0, "tdb_free: left offset read failed at %u\n", left));
699 left = offset - leftsize;
701 /* Now read in record */
702 if (tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
703 TDB_LOG((tdb, 0, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
707 /* If it's free, expand to include it. */
708 if (l.magic == TDB_FREE_MAGIC) {
709 if (remove_from_freelist(tdb, left, l.next) == -1) {
710 TDB_LOG((tdb, 0, "tdb_free: left free failed at %u\n", left));
714 rec->rec_len += leftsize;
720 if (update_tailer(tdb, offset, rec) == -1) {
721 TDB_LOG((tdb, 0, "tdb_free: update_tailer failed at %u\n", offset));
725 /* Now, prepend to free list */
726 rec->magic = TDB_FREE_MAGIC;
728 if (ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
729 rec_write(tdb, offset, rec) == -1 ||
730 ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
731 TDB_LOG((tdb, 0, "tdb_free record write failed at offset=%d\n", offset));
735 /* And we're done. */
736 tdb_unlock(tdb, -1, F_WRLCK);
740 tdb_unlock(tdb, -1, F_WRLCK);
745 /* expand a file. we prefer to use ftruncate, as that is what posix
746 says to use for mmap expansion */
747 static int expand_file(TDB_CONTEXT *tdb, tdb_off size, tdb_off addition)
750 #if HAVE_FTRUNCATE_EXTEND
751 if (ftruncate(tdb->fd, size+addition) != 0) {
752 TDB_LOG((tdb, 0, "expand_file ftruncate to %d failed (%s)\n",
753 size+addition, strerror(errno)));
760 if (pwrite(tdb->fd, &b, 1, (size+addition) - 1) != 1) {
762 if (lseek(tdb->fd, (size+addition) - 1, SEEK_SET) != (size+addition) - 1 ||
763 write(tdb->fd, &b, 1) != 1) {
765 TDB_LOG((tdb, 0, "expand_file to %d failed (%s)\n",
766 size+addition, strerror(errno)));
771 /* now fill the file with something. This ensures that the file isn't sparse, which would be
772 very bad if we ran out of disk. This must be done with write, not via mmap */
773 memset(buf, 0x42, sizeof(buf));
775 int n = addition>sizeof(buf)?sizeof(buf):addition;
777 int ret = pwrite(tdb->fd, buf, n, size);
780 if (lseek(tdb->fd, size, SEEK_SET) != size)
782 ret = write(tdb->fd, buf, n);
785 TDB_LOG((tdb, 0, "expand_file write of %d failed (%s)\n",
786 n, strerror(errno)));
796 /* expand the database at least size bytes by expanding the underlying
797 file and doing the mmap again if necessary */
798 static int tdb_expand(TDB_CONTEXT *tdb, tdb_off size)
800 struct list_struct rec;
803 if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
804 TDB_LOG((tdb, 0, "lock failed in tdb_expand\n"));
808 /* must know about any previous expansions by another process */
809 tdb_oob(tdb, tdb->map_size + 1, 1);
811 /* always make room for at least 10 more records, and round
812 the database up to a multiple of TDB_PAGE_SIZE */
813 size = TDB_ALIGN(tdb->map_size + size*10, TDB_PAGE_SIZE) - tdb->map_size;
815 if (!(tdb->flags & TDB_INTERNAL))
819 * We must ensure the file is unmapped before doing this
820 * to ensure consistency with systems like OpenBSD where
821 * writes and mmaps are not consistent.
824 /* expand the file itself */
825 if (!(tdb->flags & TDB_INTERNAL)) {
826 if (expand_file(tdb, tdb->map_size, size) != 0)
830 tdb->map_size += size;
832 if (tdb->flags & TDB_INTERNAL)
833 tdb->map_ptr = realloc(tdb->map_ptr, tdb->map_size);
836 * We must ensure the file is remapped before adding the space
837 * to ensure consistency with systems like OpenBSD where
838 * writes and mmaps are not consistent.
841 /* We're ok if the mmap fails as we'll fallback to read/write */
845 /* form a new freelist record */
846 memset(&rec,'\0',sizeof(rec));
847 rec.rec_len = size - sizeof(rec);
849 /* link it into the free list */
850 offset = tdb->map_size - size;
851 if (tdb_free(tdb, offset, &rec) == -1)
854 tdb_unlock(tdb, -1, F_WRLCK);
857 tdb_unlock(tdb, -1, F_WRLCK);
861 /* allocate some space from the free list. The offset returned points
862 to a unconnected list_struct within the database with room for at
863 least length bytes of total data
865 0 is returned if the space could not be allocated
867 static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length,
868 struct list_struct *rec)
870 tdb_off rec_ptr, last_ptr, newrec_ptr;
871 struct list_struct newrec;
874 if (tdb_lock(tdb, -1, F_WRLCK) == -1)
877 /* Extra bytes required for tailer */
878 length += sizeof(tdb_off);
881 last_ptr = FREELIST_TOP;
883 /* read in the freelist top */
884 if (ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
887 /* keep looking until we find a freelist record big enough */
890 if (rec_free_read(tdb, rec_ptr, rec) == -1)
893 if (rec->rec_len >= length) {
894 /* found it - now possibly split it up */
895 if (rec->rec_len > length + MIN_REC_SIZE) {
896 /* Length of left piece */
897 length = TDB_ALIGN(length, TDB_ALIGNMENT);
899 /* Right piece to go on free list */
900 newrec.rec_len = rec->rec_len
901 - (sizeof(*rec) + length);
902 newrec_ptr = rec_ptr + sizeof(*rec) + length;
904 /* And left record is shortened */
905 rec->rec_len = length;
909 /* Remove allocated record from the free list */
910 if (ofs_write(tdb, last_ptr, &rec->next) == -1)
913 /* Update header: do this before we drop alloc
914 lock, otherwise tdb_free() might try to
915 merge with us, thinking we're free.
916 (Thanks Jeremy Allison). */
917 rec->magic = TDB_MAGIC;
918 if (rec_write(tdb, rec_ptr, rec) == -1)
921 /* Did we create new block? */
923 /* Update allocated record tailer (we
925 if (update_tailer(tdb, rec_ptr, rec) == -1)
928 /* Free new record */
929 if (tdb_free(tdb, newrec_ptr, &newrec) == -1)
933 /* all done - return the new record offset */
934 tdb_unlock(tdb, -1, F_WRLCK);
937 /* move to the next record */
943 TDB_LOG((tdb, 0, "tdb_allocate: maxloop reached; corrupt database!\n"));
944 return TDB_ERRCODE(TDB_ERR_CORRUPT, 0);
947 /* we didn't find enough space. See if we can expand the
948 database and if we can then try again */
949 if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
952 tdb_unlock(tdb, -1, F_WRLCK);
956 /* initialise a new database with a specified hash size */
957 static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size)
959 struct tdb_header *newdb;
962 /* We make it up in memory, then write it out if not internal */
963 size = sizeof(struct tdb_header) + (hash_size+1)*sizeof(tdb_off);
964 if (!(newdb = calloc(size, 1)))
965 return TDB_ERRCODE(TDB_ERR_OOM, -1);
967 /* Fill in the header */
968 newdb->version = TDB_VERSION;
969 newdb->hash_size = hash_size;
971 newdb->rwlocks = size;
973 if (tdb->flags & TDB_INTERNAL) {
974 tdb->map_size = size;
975 tdb->map_ptr = (char *)newdb;
976 memcpy(&tdb->header, newdb, sizeof(tdb->header));
977 /* Convert the `ondisk' version if asked. */
981 if (lseek(tdb->fd, 0, SEEK_SET) == -1)
984 if (ftruncate(tdb->fd, 0) == -1)
987 /* This creates an endian-converted header, as if read from disk */
989 memcpy(&tdb->header, newdb, sizeof(tdb->header));
990 /* Don't endian-convert the magic food! */
991 memcpy(newdb->magic_food, TDB_MAGIC_FOOD, strlen(TDB_MAGIC_FOOD)+1);
992 if (write(tdb->fd, newdb, size) != size)
995 ret = tdb_create_rwlocks(tdb->fd, hash_size);
1002 /* Returns 0 on fail. On success, return offset of record, and fills
1004 static tdb_off tdb_find(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash,
1005 struct list_struct *r)
1010 /* read in the hash top */
1011 if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
1014 /* keep looking until we find the right record */
1017 if (rec_read(tdb, rec_ptr, r) == -1)
1020 if (!TDB_DEAD(r) && hash==r->full_hash && key.dsize==r->key_len) {
1022 /* a very likely hit - read the key */
1023 k = tdb_alloc_read(tdb, rec_ptr + sizeof(*r),
1028 if (memcmp(key.dptr, k, key.dsize) == 0) {
1038 TDB_LOG((tdb, 0, "tdb_find maxloop reached; corrupt database!\n"));
1039 return TDB_ERRCODE(TDB_ERR_CORRUPT, 0);
1042 return TDB_ERRCODE(TDB_ERR_NOEXIST, 0);
1045 /* If they do lockkeys, check that this hash is one they locked */
1046 static int tdb_keylocked(TDB_CONTEXT *tdb, u32 hash)
1049 if (!tdb->lockedkeys)
1051 for (i = 0; i < tdb->lockedkeys[0]; i++)
1052 if (tdb->lockedkeys[i+1] == hash)
1054 return TDB_ERRCODE(TDB_ERR_NOLOCK, 0);
1057 /* As tdb_find, but if you succeed, keep the lock */
1058 static tdb_off tdb_find_lock(TDB_CONTEXT *tdb, TDB_DATA key, int locktype,
1059 struct list_struct *rec)
1063 hash = tdb_hash(&key);
1064 if (!tdb_keylocked(tdb, hash))
1066 if (tdb_lock(tdb, BUCKET(hash), locktype) == -1)
1068 if (!(rec_ptr = tdb_find(tdb, key, hash, rec)))
1069 tdb_unlock(tdb, BUCKET(hash), locktype);
1073 enum TDB_ERROR tdb_error(TDB_CONTEXT *tdb)
1078 static struct tdb_errname {
1079 enum TDB_ERROR ecode; const char *estring;
1080 } emap[] = { {TDB_SUCCESS, "Success"},
1081 {TDB_ERR_CORRUPT, "Corrupt database"},
1082 {TDB_ERR_IO, "IO Error"},
1083 {TDB_ERR_LOCK, "Locking error"},
1084 {TDB_ERR_OOM, "Out of memory"},
1085 {TDB_ERR_EXISTS, "Record exists"},
1086 {TDB_ERR_NOLOCK, "Lock exists on other keys"},
1087 {TDB_ERR_NOEXIST, "Record does not exist"} };
1089 /* Error string for the last tdb error */
1090 const char *tdb_errorstr(TDB_CONTEXT *tdb)
1093 for (i = 0; i < sizeof(emap) / sizeof(struct tdb_errname); i++)
1094 if (tdb->ecode == emap[i].ecode)
1095 return emap[i].estring;
1096 return "Invalid error code";
1099 /* update an entry in place - this only works if the new data size
1100 is <= the old data size and the key exists.
1101 on failure return -1.
1104 static int tdb_update(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf)
1106 struct list_struct rec;
1110 if (!(rec_ptr = tdb_find(tdb, key, tdb_hash(&key), &rec)))
1113 /* must be long enough key, data and tailer */
1114 if (rec.rec_len < key.dsize + dbuf.dsize + sizeof(tdb_off)) {
1115 tdb->ecode = TDB_SUCCESS; /* Not really an error */
1119 if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
1120 dbuf.dptr, dbuf.dsize) == -1)
1123 if (dbuf.dsize != rec.data_len) {
1125 rec.data_len = dbuf.dsize;
1126 return rec_write(tdb, rec_ptr, &rec);
1132 /* find an entry in the database given a key */
1133 /* If an entry doesn't exist tdb_err will be set to
1134 * TDB_ERR_NOEXIST. If a key has no data attached
1135 * tdb_err will not be set. Both will return a
1136 * zero pptr and zero dsize.
1139 TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key)
1142 struct list_struct rec;
1145 /* find which hash bucket it is in */
1146 if (!(rec_ptr = tdb_find_lock(tdb,key,F_RDLCK,&rec)))
1150 ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec) + rec.key_len,
1154 ret.dsize = rec.data_len;
1155 tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
1159 /* check if an entry in the database exists
1161 note that 1 is returned if the key is found and 0 is returned if not found
1162 this doesn't match the conventions in the rest of this module, but is
1163 compatible with gdbm
1165 int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key)
1167 struct list_struct rec;
1169 if (tdb_find_lock(tdb, key, F_RDLCK, &rec) == 0)
1171 tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
1175 /* record lock stops delete underneath */
1176 static int lock_record(TDB_CONTEXT *tdb, tdb_off off)
1178 return off ? tdb_brlock(tdb, off, F_RDLCK, F_SETLKW, 0) : 0;
1181 Write locks override our own fcntl readlocks, so check it here.
1182 Note this is meant to be F_SETLK, *not* F_SETLKW, as it's not
1183 an error to fail to get the lock here.
1186 static int write_lock_record(TDB_CONTEXT *tdb, tdb_off off)
1188 struct tdb_traverse_lock *i;
1189 for (i = &tdb->travlocks; i; i = i->next)
1192 return tdb_brlock(tdb, off, F_WRLCK, F_SETLK, 1);
1196 Note this is meant to be F_SETLK, *not* F_SETLKW, as it's not
1197 an error to fail to get the lock here.
1200 static int write_unlock_record(TDB_CONTEXT *tdb, tdb_off off)
1202 return tdb_brlock(tdb, off, F_UNLCK, F_SETLK, 0);
1204 /* fcntl locks don't stack: avoid unlocking someone else's */
1205 static int unlock_record(TDB_CONTEXT *tdb, tdb_off off)
1207 struct tdb_traverse_lock *i;
1212 for (i = &tdb->travlocks; i; i = i->next)
1215 return (count == 1 ? tdb_brlock(tdb, off, F_UNLCK, F_SETLKW, 0) : 0);
1218 /* actually delete an entry in the database given the offset */
1219 static int do_delete(TDB_CONTEXT *tdb, tdb_off rec_ptr, struct list_struct*rec)
1221 tdb_off last_ptr, i;
1222 struct list_struct lastrec;
1225 if (tdb->read_only) return -1;
1227 if (write_lock_record(tdb, rec_ptr) == -1) {
1228 /* Someone traversing here: mark it as dead */
1229 rec->magic = TDB_DEAD_MAGIC;
1230 return rec_write(tdb, rec_ptr, rec);
1232 if (write_unlock_record(tdb, rec_ptr) != 0)
1235 /* find previous record in hash chain */
1236 if (ofs_read(tdb, TDB_HASH_TOP(rec->full_hash), &i) == -1)
1240 for (last_ptr = 0; i != rec_ptr; last_ptr = i, i = lastrec.next) {
1241 if (rec_read(tdb, i, &lastrec) == -1)
1246 TDB_LOG((tdb, 0, "(tdb)do_delete: maxloop reached; corrupt database!\n"));
1247 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
1251 /* unlink it: next ptr is at start of record. */
1253 last_ptr = TDB_HASH_TOP(rec->full_hash);
1254 if (ofs_write(tdb, last_ptr, &rec->next) == -1)
1257 /* recover the space */
1258 if (tdb_free(tdb, rec_ptr, rec) == -1)
1263 /* Uses traverse lock: 0 = finish, -1 = error, other = record offset */
1264 static int tdb_next_lock(TDB_CONTEXT *tdb, struct tdb_traverse_lock *tlock,
1265 struct list_struct *rec)
1267 int want_next = (tlock->off != 0);
1269 /* No traversal allows if you've called tdb_lockkeys() */
1270 if (tdb->lockedkeys)
1271 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1273 /* Lock each chain from the start one. */
1274 for (; tlock->hash < tdb->header.hash_size; tlock->hash++) {
1275 if (tdb_lock(tdb, tlock->hash, F_WRLCK) == -1)
1278 /* No previous record? Start at top of chain. */
1280 if (ofs_read(tdb, TDB_HASH_TOP(tlock->hash),
1284 /* Otherwise unlock the previous record. */
1285 if (unlock_record(tdb, tlock->off) != 0)
1290 /* We have offset of old record: grab next */
1291 if (rec_read(tdb, tlock->off, rec) == -1)
1293 tlock->off = rec->next;
1296 /* Iterate through chain */
1297 while( tlock->off) {
1299 if (rec_read(tdb, tlock->off, rec) == -1)
1301 if (!TDB_DEAD(rec)) {
1302 /* Woohoo: we found one! */
1303 if (lock_record(tdb, tlock->off) != 0)
1307 /* Try to clean dead ones from old traverses */
1308 current = tlock->off;
1309 tlock->off = rec->next;
1310 if (!tdb->read_only &&
1311 do_delete(tdb, current, rec) != 0)
1314 tdb_unlock(tdb, tlock->hash, F_WRLCK);
1317 /* We finished iteration without finding anything */
1318 return TDB_ERRCODE(TDB_SUCCESS, 0);
1322 if (tdb_unlock(tdb, tlock->hash, F_WRLCK) != 0)
1323 TDB_LOG((tdb, 0, "tdb_next_lock: On error unlock failed!\n"));
1327 /* traverse the entire database - calling fn(tdb, key, data) on each element.
1328 return -1 on error or the record count traversed
1329 if fn is NULL then it is not called
1330 a non-zero return value from fn() indicates that the traversal should stop
1332 int tdb_traverse(TDB_CONTEXT *tdb, tdb_traverse_func fn, void *state)
1335 struct list_struct rec;
1336 struct tdb_traverse_lock tl = { NULL, 0, 0 };
1339 /* This was in the initializaton, above, but the IRIX compiler
1340 * did not like it. crh
1342 tl.next = tdb->travlocks.next;
1344 /* fcntl locks don't stack: beware traverse inside traverse */
1345 tdb->travlocks.next = &tl;
1347 /* tdb_next_lock places locks on the record returned, and its chain */
1348 while ((ret = tdb_next_lock(tdb, &tl, &rec)) > 0) {
1350 /* now read the full record */
1351 key.dptr = tdb_alloc_read(tdb, tl.off + sizeof(rec),
1352 rec.key_len + rec.data_len);
1355 if (tdb_unlock(tdb, tl.hash, F_WRLCK) != 0)
1357 if (unlock_record(tdb, tl.off) != 0)
1358 TDB_LOG((tdb, 0, "tdb_traverse: key.dptr == NULL and unlock_record failed!\n"));
1361 key.dsize = rec.key_len;
1362 dbuf.dptr = key.dptr + rec.key_len;
1363 dbuf.dsize = rec.data_len;
1365 /* Drop chain lock, call out */
1366 if (tdb_unlock(tdb, tl.hash, F_WRLCK) != 0) {
1370 if (fn && fn(tdb, key, dbuf, state)) {
1371 /* They want us to terminate traversal */
1373 if (unlock_record(tdb, tl.off) != 0) {
1374 TDB_LOG((tdb, 0, "tdb_traverse: unlock_record failed!\n"));;
1377 tdb->travlocks.next = tl.next;
1378 SAFE_FREE(key.dptr);
1381 SAFE_FREE(key.dptr);
1384 tdb->travlocks.next = tl.next;
1391 /* find the first entry in the database and return its key */
1392 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
1395 struct list_struct rec;
1397 /* release any old lock */
1398 if (unlock_record(tdb, tdb->travlocks.off) != 0)
1400 tdb->travlocks.off = tdb->travlocks.hash = 0;
1402 if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0)
1404 /* now read the key */
1405 key.dsize = rec.key_len;
1406 key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize);
1407 if (tdb_unlock(tdb, BUCKET(tdb->travlocks.hash), F_WRLCK) != 0)
1408 TDB_LOG((tdb, 0, "tdb_firstkey: error occurred while tdb_unlocking!\n"));
1412 /* find the next entry in the database, returning its key */
1413 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA oldkey)
1416 TDB_DATA key = tdb_null;
1417 struct list_struct rec;
1420 /* Is locked key the old key? If so, traverse will be reliable. */
1421 if (tdb->travlocks.off) {
1422 if (tdb_lock(tdb,tdb->travlocks.hash,F_WRLCK))
1424 if (rec_read(tdb, tdb->travlocks.off, &rec) == -1
1425 || !(k = tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),
1427 || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) {
1428 /* No, it wasn't: unlock it and start from scratch */
1429 if (unlock_record(tdb, tdb->travlocks.off) != 0)
1431 if (tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK) != 0)
1433 tdb->travlocks.off = 0;
1439 if (!tdb->travlocks.off) {
1440 /* No previous element: do normal find, and lock record */
1441 tdb->travlocks.off = tdb_find_lock(tdb, oldkey, F_WRLCK, &rec);
1442 if (!tdb->travlocks.off)
1444 tdb->travlocks.hash = BUCKET(rec.full_hash);
1445 if (lock_record(tdb, tdb->travlocks.off) != 0) {
1446 TDB_LOG((tdb, 0, "tdb_nextkey: lock_record failed (%s)!\n", strerror(errno)));
1450 oldhash = tdb->travlocks.hash;
1452 /* Grab next record: locks chain and returned record,
1453 unlocks old record */
1454 if (tdb_next_lock(tdb, &tdb->travlocks, &rec) > 0) {
1455 key.dsize = rec.key_len;
1456 key.dptr = tdb_alloc_read(tdb, tdb->travlocks.off+sizeof(rec),
1458 /* Unlock the chain of this new record */
1459 if (tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK) != 0)
1460 TDB_LOG((tdb, 0, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
1462 /* Unlock the chain of old record */
1463 if (tdb_unlock(tdb, BUCKET(oldhash), F_WRLCK) != 0)
1464 TDB_LOG((tdb, 0, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
1468 /* delete an entry in the database given a key */
1469 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
1472 struct list_struct rec;
1475 if (!(rec_ptr = tdb_find_lock(tdb, key, F_WRLCK, &rec)))
1477 ret = do_delete(tdb, rec_ptr, &rec);
1478 if (tdb_unlock(tdb, BUCKET(rec.full_hash), F_WRLCK) != 0)
1479 TDB_LOG((tdb, 0, "tdb_delete: WARNING tdb_unlock failed!\n"));
1483 /* store an element in the database, replacing any existing element
1486 return 0 on success, -1 on failure
1488 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
1490 struct list_struct rec;
1496 /* find which hash bucket it is in */
1497 hash = tdb_hash(&key);
1498 if (!tdb_keylocked(tdb, hash))
1500 if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
1503 /* check for it existing, on insert. */
1504 if (flag == TDB_INSERT) {
1505 if (tdb_exists(tdb, key)) {
1506 tdb->ecode = TDB_ERR_EXISTS;
1510 /* first try in-place update, on modify or replace. */
1511 if (tdb_update(tdb, key, dbuf) == 0)
1513 if (flag == TDB_MODIFY && tdb->ecode == TDB_ERR_NOEXIST)
1516 /* reset the error code potentially set by the tdb_update() */
1517 tdb->ecode = TDB_SUCCESS;
1519 /* delete any existing record - if it doesn't exist we don't
1520 care. Doing this first reduces fragmentation, and avoids
1521 coalescing with `allocated' block before it's updated. */
1522 if (flag != TDB_INSERT)
1523 tdb_delete(tdb, key);
1525 /* Copy key+value *before* allocating free space in case malloc
1526 fails and we are left with a dead spot in the tdb. */
1528 if (!(p = (char *)malloc(key.dsize + dbuf.dsize))) {
1529 tdb->ecode = TDB_ERR_OOM;
1533 memcpy(p, key.dptr, key.dsize);
1535 memcpy(p+key.dsize, dbuf.dptr, dbuf.dsize);
1537 /* now we're into insert / modify / replace of a record which
1538 * we know could not be optimised by an in-place store (for
1539 * various reasons). */
1540 if (!(rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize, &rec)))
1543 /* Read hash top into next ptr */
1544 if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
1547 rec.key_len = key.dsize;
1548 rec.data_len = dbuf.dsize;
1549 rec.full_hash = hash;
1550 rec.magic = TDB_MAGIC;
1552 /* write out and point the top of the hash chain at it */
1553 if (rec_write(tdb, rec_ptr, &rec) == -1
1554 || tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+dbuf.dsize)==-1
1555 || ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
1556 /* Need to tdb_unallocate() here */
1561 tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
1568 /* Attempt to append data to an entry in place - this only works if the new data size
1569 is <= the old data size and the key exists.
1570 on failure return -1. Record must be locked before calling.
1572 static int tdb_append_inplace(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA new_dbuf)
1574 struct list_struct rec;
1578 if (!(rec_ptr = tdb_find(tdb, key, tdb_hash(&key), &rec)))
1581 /* Append of 0 is always ok. */
1582 if (new_dbuf.dsize == 0)
1585 /* must be long enough for key, old data + new data and tailer */
1586 if (rec.rec_len < key.dsize + rec.data_len + new_dbuf.dsize + sizeof(tdb_off)) {
1588 tdb->ecode = TDB_SUCCESS; /* Not really an error */
1592 if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len + rec.data_len,
1593 new_dbuf.dptr, new_dbuf.dsize) == -1)
1597 rec.data_len += new_dbuf.dsize;
1598 return rec_write(tdb, rec_ptr, &rec);
1601 /* Append to an entry. Create if not exist. */
1603 int tdb_append(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA new_dbuf)
1605 struct list_struct rec;
1610 size_t new_data_size = 0;
1612 /* find which hash bucket it is in */
1613 hash = tdb_hash(&key);
1614 if (!tdb_keylocked(tdb, hash))
1616 if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
1619 /* first try in-place. */
1620 if (tdb_append_inplace(tdb, key, new_dbuf) == 0)
1623 /* reset the error code potentially set by the tdb_append_inplace() */
1624 tdb->ecode = TDB_SUCCESS;
1627 if (!(rec_ptr = tdb_find(tdb, key, hash, &rec))) {
1628 if (tdb->ecode != TDB_ERR_NOEXIST)
1631 /* Not found - create. */
1633 ret = tdb_store(tdb, key, new_dbuf, TDB_INSERT);
1637 new_data_size = rec.data_len + new_dbuf.dsize;
1639 /* Copy key+old_value+value *before* allocating free space in case malloc
1640 fails and we are left with a dead spot in the tdb. */
1642 if (!(p = (char *)malloc(key.dsize + new_data_size))) {
1643 tdb->ecode = TDB_ERR_OOM;
1647 /* Copy the key in place. */
1648 memcpy(p, key.dptr, key.dsize);
1650 /* Now read the old data into place. */
1652 tdb_read(tdb, rec_ptr + sizeof(rec) + rec.key_len, p + key.dsize, rec.data_len, 0) == -1)
1655 /* Finally append the new data. */
1657 memcpy(p+key.dsize+rec.data_len, new_dbuf.dptr, new_dbuf.dsize);
1659 /* delete any existing record - if it doesn't exist we don't
1660 care. Doing this first reduces fragmentation, and avoids
1661 coalescing with `allocated' block before it's updated. */
1663 tdb_delete(tdb, key);
1665 if (!(rec_ptr = tdb_allocate(tdb, key.dsize + new_data_size, &rec)))
1668 /* Read hash top into next ptr */
1669 if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
1672 rec.key_len = key.dsize;
1673 rec.data_len = new_data_size;
1674 rec.full_hash = hash;
1675 rec.magic = TDB_MAGIC;
1677 /* write out and point the top of the hash chain at it */
1678 if (rec_write(tdb, rec_ptr, &rec) == -1
1679 || tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+new_data_size)==-1
1680 || ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
1681 /* Need to tdb_unallocate() here */
1687 tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
1695 static int tdb_already_open(dev_t device,
1700 for (i = tdbs; i; i = i->next) {
1701 if (i->device == device && i->inode == ino) {
1709 /* open the database, creating it if necessary
1711 The open_flags and mode are passed straight to the open call on the
1712 database file. A flags value of O_WRONLY is invalid. The hash size
1713 is advisory, use zero for a default value.
1715 Return is NULL on error, in which case errno is also set. Don't
1716 try to call tdb_error or tdb_errname, just do strerror(errno).
1718 @param name may be NULL for internal databases. */
1719 TDB_CONTEXT *tdb_open(const char *name, int hash_size, int tdb_flags,
1720 int open_flags, mode_t mode)
1722 return tdb_open_ex(name, hash_size, tdb_flags, open_flags, mode, NULL);
1726 TDB_CONTEXT *tdb_open_ex(const char *name, int hash_size, int tdb_flags,
1727 int open_flags, mode_t mode,
1728 tdb_log_func log_fn)
1732 int rev = 0, locked;
1736 if (!(tdb = calloc(1, sizeof *tdb))) {
1737 /* Can't log this */
1743 tdb->map_ptr = NULL;
1744 tdb->lockedkeys = NULL;
1745 tdb->flags = tdb_flags;
1746 tdb->open_flags = open_flags;
1747 tdb->log_fn = log_fn;
1749 if ((open_flags & O_ACCMODE) == O_WRONLY) {
1750 TDB_LOG((tdb, 0, "tdb_open_ex: can't open tdb %s write-only\n",
1757 hash_size = DEFAULT_HASH_SIZE;
1758 if ((open_flags & O_ACCMODE) == O_RDONLY) {
1760 /* read only databases don't do locking or clear if first */
1761 tdb->flags |= TDB_NOLOCK;
1762 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
1765 /* internal databases don't mmap or lock, and start off cleared */
1766 if (tdb->flags & TDB_INTERNAL) {
1767 tdb->flags |= (TDB_NOLOCK | TDB_NOMMAP);
1768 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
1769 if (tdb_new_database(tdb, hash_size) != 0) {
1770 TDB_LOG((tdb, 0, "tdb_open_ex: tdb_new_database failed!"));
1776 if ((tdb->fd = open(name, open_flags, mode)) == -1) {
1777 TDB_LOG((tdb, 5, "tdb_open_ex: could not open file %s: %s\n",
1778 name, strerror(errno)));
1779 goto fail; /* errno set by open(2) */
1783 Close file when execing another process.
1784 Prevents SELinux access errors.
1786 set_cloexec_flag(tdb->fd, 1);
1788 /* ensure there is only one process initialising at once */
1789 if (tdb_brlock(tdb, GLOBAL_LOCK, F_WRLCK, F_SETLKW, 0) == -1) {
1790 TDB_LOG((tdb, 0, "tdb_open_ex: failed to get global lock on %s: %s\n",
1791 name, strerror(errno)));
1792 goto fail; /* errno set by tdb_brlock */
1795 /* we need to zero database if we are the only one with it open */
1796 if ((locked = (tdb_brlock(tdb, ACTIVE_LOCK, F_WRLCK, F_SETLK, 0) == 0))
1797 && (tdb_flags & TDB_CLEAR_IF_FIRST)) {
1798 open_flags |= O_CREAT;
1799 if (ftruncate(tdb->fd, 0) == -1) {
1800 TDB_LOG((tdb, 0, "tdb_open_ex: "
1801 "failed to truncate %s: %s\n",
1802 name, strerror(errno)));
1803 goto fail; /* errno set by ftruncate */
1807 if (read(tdb->fd, &tdb->header, sizeof(tdb->header)) != sizeof(tdb->header)
1808 || strcmp(tdb->header.magic_food, TDB_MAGIC_FOOD) != 0
1809 || (tdb->header.version != TDB_VERSION
1810 && !(rev = (tdb->header.version==TDB_BYTEREV(TDB_VERSION))))) {
1811 /* its not a valid database - possibly initialise it */
1812 if (!(open_flags & O_CREAT) || tdb_new_database(tdb, hash_size) == -1) {
1813 errno = EIO; /* ie bad format or something */
1816 rev = (tdb->flags & TDB_CONVERT);
1818 vp = (unsigned char *)&tdb->header.version;
1819 vertest = (((u32)vp[0]) << 24) | (((u32)vp[1]) << 16) |
1820 (((u32)vp[2]) << 8) | (u32)vp[3];
1821 tdb->flags |= (vertest==TDB_VERSION) ? TDB_BIGENDIAN : 0;
1823 tdb->flags &= ~TDB_CONVERT;
1825 tdb->flags |= TDB_CONVERT;
1826 convert(&tdb->header, sizeof(tdb->header));
1828 if (fstat(tdb->fd, &st) == -1)
1831 /* Is it already in the open list? If so, fail. */
1832 if (tdb_already_open(st.st_dev, st.st_ino)) {
1833 TDB_LOG((tdb, 2, "tdb_open_ex: "
1834 "%s (%d:%d,%lld) is already open in this process\n",
1835 name, major(st.st_dev), minor(st.st_dev), (unsigned long long)st.st_ino));
1840 if (!(tdb->name = (char *)strdup(name))) {
1845 tdb->map_size = st.st_size;
1846 tdb->device = st.st_dev;
1847 tdb->inode = st.st_ino;
1848 tdb->locked = calloc(tdb->header.hash_size+1, sizeof(tdb->locked[0]));
1850 TDB_LOG((tdb, 2, "tdb_open_ex: "
1851 "failed to allocate lock structure for %s\n",
1858 if (!tdb->read_only)
1859 if (tdb_clear_spinlocks(tdb) != 0) {
1860 TDB_LOG((tdb, 0, "tdb_open_ex: "
1861 "failed to clear spinlock\n"));
1864 if (tdb_brlock(tdb, ACTIVE_LOCK, F_UNLCK, F_SETLK, 0) == -1) {
1865 TDB_LOG((tdb, 0, "tdb_open_ex: "
1866 "failed to take ACTIVE_LOCK on %s: %s\n",
1867 name, strerror(errno)));
1871 /* leave this lock in place to indicate it's in use */
1872 if (tdb_brlock(tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1)
1876 /* Internal (memory-only) databases skip all the code above to
1877 * do with disk files, and resume here by releasing their
1878 * global lock and hooking into the active list. */
1879 if (tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0) == -1)
1886 { int save_errno = errno;
1892 if (tdb->flags & TDB_INTERNAL)
1893 SAFE_FREE(tdb->map_ptr);
1897 SAFE_FREE(tdb->name);
1899 if (close(tdb->fd) != 0)
1900 TDB_LOG((tdb, 5, "tdb_open_ex: failed to close tdb->fd on error!\n"));
1901 SAFE_FREE(tdb->locked);
1911 * @returns -1 for error; 0 for success.
1913 int tdb_close(TDB_CONTEXT *tdb)
1919 if (tdb->flags & TDB_INTERNAL)
1920 SAFE_FREE(tdb->map_ptr);
1924 SAFE_FREE(tdb->name);
1926 ret = close(tdb->fd);
1927 SAFE_FREE(tdb->locked);
1928 SAFE_FREE(tdb->lockedkeys);
1930 /* Remove from contexts list */
1931 for (i = &tdbs; *i; i = &(*i)->next) {
1938 memset(tdb, 0, sizeof(*tdb));
1944 /* lock/unlock entire database */
1945 int tdb_lockall(TDB_CONTEXT *tdb)
1949 /* There are no locks on read-only dbs */
1951 return TDB_ERRCODE(TDB_ERR_LOCK, -1);
1952 if (tdb->lockedkeys)
1953 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1954 for (i = 0; i < tdb->header.hash_size; i++)
1955 if (tdb_lock(tdb, i, F_WRLCK))
1958 /* If error, release locks we have... */
1959 if (i < tdb->header.hash_size) {
1962 for ( j = 0; j < i; j++)
1963 tdb_unlock(tdb, j, F_WRLCK);
1964 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1969 void tdb_unlockall(TDB_CONTEXT *tdb)
1972 for (i=0; i < tdb->header.hash_size; i++)
1973 tdb_unlock(tdb, i, F_WRLCK);
1976 int tdb_lockkeys(TDB_CONTEXT *tdb, u32 number, TDB_DATA keys[])
1980 /* Can't lock more keys if already locked */
1981 if (tdb->lockedkeys)
1982 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1983 if (!(tdb->lockedkeys = malloc(sizeof(u32) * (number+1))))
1984 return TDB_ERRCODE(TDB_ERR_OOM, -1);
1985 /* First number in array is # keys */
1986 tdb->lockedkeys[0] = number;
1988 /* Insertion sort by bucket */
1989 for (i = 0; i < number; i++) {
1990 hash = tdb_hash(&keys[i]);
1991 for (j = 0; j < i && BUCKET(tdb->lockedkeys[j+1]) < BUCKET(hash); j++);
1992 memmove(&tdb->lockedkeys[j+2], &tdb->lockedkeys[j+1], sizeof(u32) * (i-j));
1993 tdb->lockedkeys[j+1] = hash;
1995 /* Finally, lock in order */
1996 for (i = 0; i < number; i++)
1997 if (tdb_lock(tdb, i, F_WRLCK))
2000 /* If error, release locks we have... */
2002 for ( j = 0; j < i; j++)
2003 tdb_unlock(tdb, j, F_WRLCK);
2004 SAFE_FREE(tdb->lockedkeys);
2005 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
2010 /* Unlock the keys previously locked by tdb_lockkeys() */
2011 void tdb_unlockkeys(TDB_CONTEXT *tdb)
2014 if (!tdb->lockedkeys)
2016 for (i = 0; i < tdb->lockedkeys[0]; i++)
2017 tdb_unlock(tdb, tdb->lockedkeys[i+1], F_WRLCK);
2018 SAFE_FREE(tdb->lockedkeys);
2021 /* lock/unlock one hash chain. This is meant to be used to reduce
2022 contention - it cannot guarantee how many records will be locked */
2023 int tdb_chainlock(TDB_CONTEXT *tdb, TDB_DATA key)
2025 return tdb_lock(tdb, BUCKET(tdb_hash(&key)), F_WRLCK);
2028 int tdb_chainunlock(TDB_CONTEXT *tdb, TDB_DATA key)
2030 return tdb_unlock(tdb, BUCKET(tdb_hash(&key)), F_WRLCK);
2033 int tdb_chainlock_read(TDB_CONTEXT *tdb, TDB_DATA key)
2035 return tdb_lock(tdb, BUCKET(tdb_hash(&key)), F_RDLCK);
2038 int tdb_chainunlock_read(TDB_CONTEXT *tdb, TDB_DATA key)
2040 return tdb_unlock(tdb, BUCKET(tdb_hash(&key)), F_RDLCK);
2044 /* register a loging function */
2045 void tdb_logging_function(TDB_CONTEXT *tdb, void (*fn)(TDB_CONTEXT *, int , const char *, ...))
2051 /* reopen a tdb - this is used after a fork to ensure that we have an independent
2052 seek pointer from our parent and to re-establish locks */
2053 int tdb_reopen(TDB_CONTEXT *tdb)
2057 if (tdb_munmap(tdb) != 0) {
2058 TDB_LOG((tdb, 0, "tdb_reopen: munmap failed (%s)\n", strerror(errno)));
2061 if (close(tdb->fd) != 0)
2062 TDB_LOG((tdb, 0, "tdb_reopen: WARNING closing tdb->fd failed!\n"));
2063 tdb->fd = open(tdb->name, tdb->open_flags & ~(O_CREAT|O_TRUNC), 0);
2064 if (tdb->fd == -1) {
2065 TDB_LOG((tdb, 0, "tdb_reopen: open failed (%s)\n", strerror(errno)));
2068 if (fstat(tdb->fd, &st) != 0) {
2069 TDB_LOG((tdb, 0, "tdb_reopen: fstat failed (%s)\n", strerror(errno)));
2072 if (st.st_ino != tdb->inode || st.st_dev != tdb->device) {
2073 TDB_LOG((tdb, 0, "tdb_reopen: file dev/inode has changed!\n"));
2077 if (tdb_brlock(tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1) {
2078 TDB_LOG((tdb, 0, "tdb_reopen: failed to obtain active lock\n"));
2089 /* reopen all tdb's */
2090 int tdb_reopen_all(void)
2094 for (tdb=tdbs; tdb; tdb = tdb->next) {
2095 if (tdb_reopen(tdb) != 0) return -1;