2 Unix SMB/CIFS implementation.
4 trivial database library
6 Copyright (C) Andrew Tridgell 1999-2004
7 Copyright (C) Paul `Rusty' Russell 2000
8 Copyright (C) Jeremy Allison 2000-2003
10 ** NOTE! The following LGPL license applies to the tdb
11 ** library. This does NOT imply that all of Samba is released
14 This library is free software; you can redistribute it and/or
15 modify it under the terms of the GNU Lesser General Public
16 License as published by the Free Software Foundation; either
17 version 2 of the License, or (at your option) any later version.
19 This library is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 Lesser General Public License for more details.
24 You should have received a copy of the GNU Lesser General Public
25 License along with this library; if not, write to the Free Software
26 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
30 /* NOTE: If you use tdbs under valgrind, and in particular if you run
31 * tdbtorture, you may get spurious "uninitialized value" warnings. I
32 * think this is because valgrind doesn't understand that the mmap'd
33 * area may be written to by other processes. Memory can, from the
34 * point of view of the grinded process, spontaneously become
37 * I can think of a few solutions. [mbp 20030311]
39 * 1 - Write suppressions for Valgrind so that it doesn't complain
40 * about this. Probably the most reasonable but people need to
41 * remember to use them.
43 * 2 - Use IO not mmap when running under valgrind. Not so nice.
45 * 3 - Use the special valgrind macros to mark memory as valid at the
46 * right time. Probably too hard -- the process just doesn't know.
64 #include "pppd-private.h"
67 #include "pathnames.h"
69 #define TDB_MAGIC_FOOD "TDB file\n"
70 #define TDB_VERSION (0x26011967 + 6)
71 #define TDB_MAGIC (0x26011999U)
72 #define TDB_FREE_MAGIC (~TDB_MAGIC)
73 #define TDB_DEAD_MAGIC (0xFEE1DEAD)
74 #define TDB_ALIGNMENT 4
75 #define MIN_REC_SIZE (2*sizeof(struct list_struct) + TDB_ALIGNMENT)
76 #define DEFAULT_HASH_SIZE 131
77 #define TDB_PAGE_SIZE 0x2000
78 #define FREELIST_TOP (sizeof(struct tdb_header))
79 #define TDB_ALIGN(x,a) (((x) + (a)-1) & ~((a)-1))
80 #define TDB_BYTEREV(x) (((((x)&0xff)<<24)|((x)&0xFF00)<<8)|(((x)>>8)&0xFF00)|((x)>>24))
81 #define TDB_DEAD(r) ((r)->magic == TDB_DEAD_MAGIC)
82 #define TDB_BAD_MAGIC(r) ((r)->magic != TDB_MAGIC && !TDB_DEAD(r))
83 #define TDB_HASH_TOP(hash) (FREELIST_TOP + (BUCKET(hash)+1)*sizeof(tdb_off))
84 #define TDB_DATA_START(hash_size) (TDB_HASH_TOP(hash_size-1) + TDB_SPINLOCK_SIZE(hash_size))
87 /* NB assumes there is a local variable called "tdb" that is the
88 * current context, also takes doubly-parenthesized print-style
90 #define TDB_LOG(x) (tdb->log_fn?((tdb->log_fn x),0) : 0)
101 #define MAP_FAILED ((void *)-1)
104 /* free memory if the pointer is valid and zero the pointer */
106 #define SAFE_FREE(x) do { if ((x) != NULL) {free((x)); (x)=NULL;} } while(0)
109 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
112 /* all contexts, to ensure no double-opens (fcntl locks don't nest!) */
113 static TDB_CONTEXT *tdbs = NULL;
115 static int tdb_munmap(TDB_CONTEXT *tdb)
117 if (tdb->flags & TDB_INTERNAL)
122 int ret = munmap(tdb->map_ptr, tdb->map_size);
131 static void tdb_mmap(TDB_CONTEXT *tdb)
133 if (tdb->flags & TDB_INTERNAL)
137 if (!(tdb->flags & TDB_NOMMAP)) {
138 tdb->map_ptr = mmap(NULL, tdb->map_size,
139 PROT_READ|(tdb->read_only? 0:PROT_WRITE),
140 MAP_SHARED|MAP_FILE, tdb->fd, 0);
143 * NB. When mmap fails it returns MAP_FAILED *NOT* NULL !!!!
146 if (tdb->map_ptr == MAP_FAILED) {
148 TDB_LOG((tdb, 2, "tdb_mmap failed for size %d (%s)\n",
149 tdb->map_size, strerror(errno)));
159 /* Endian conversion: we only ever deal with 4 byte quantities */
160 static void *convert(void *buf, u32 size)
163 for (i = 0; i < size / 4; i++)
164 p[i] = TDB_BYTEREV(p[i]);
167 #define DOCONV() (tdb->flags & TDB_CONVERT)
168 #define CONVERT(x) (DOCONV() ? convert(&x, sizeof(x)) : &x)
170 /* the body of the database is made of one list_struct for the free space
171 plus a separate data list for each hash value */
173 tdb_off next; /* offset of the next record in the list */
174 tdb_len rec_len; /* total byte length of record */
175 tdb_len key_len; /* byte length of key */
176 tdb_len data_len; /* byte length of data */
177 u32 full_hash; /* the full 32 bit hash of the key */
178 u32 magic; /* try to catch errors */
179 /* the following union is implied:
181 char record[rec_len];
186 u32 totalsize; (tailer)
191 /***************************************************************
192 Allow a caller to set a "alarm" flag that tdb can check to abort
193 a blocking lock on SIGALRM.
194 ***************************************************************/
196 static sig_atomic_t *palarm_fired;
198 void tdb_set_lock_alarm(sig_atomic_t *palarm)
200 palarm_fired = palarm;
203 /* a byte range locking function - return 0 on success
204 this functions locks/unlocks 1 byte at the specified offset.
206 On error, errno is also set so that errors are passed back properly
207 through tdb_open(). */
208 static int tdb_brlock(TDB_CONTEXT *tdb, tdb_off offset,
209 int rw_type, int lck_type, int probe)
214 if (tdb->flags & TDB_NOLOCK)
216 if ((rw_type == F_WRLCK) && (tdb->read_only)) {
222 fl.l_whence = SEEK_SET;
228 ret = fcntl(tdb->fd,lck_type,&fl);
229 if (ret == -1 && errno == EINTR && palarm_fired && *palarm_fired)
231 } while (ret == -1 && errno == EINTR);
234 if (!probe && lck_type != F_SETLK) {
235 /* Ensure error code is set for log fun to examine. */
236 if (errno == EINTR && palarm_fired && *palarm_fired)
237 tdb->ecode = TDB_ERR_LOCK_TIMEOUT;
239 tdb->ecode = TDB_ERR_LOCK;
240 TDB_LOG((tdb, 5,"tdb_brlock failed (fd=%d) at offset %d rw_type=%d lck_type=%d\n",
241 tdb->fd, offset, rw_type, lck_type));
243 /* Was it an alarm timeout ? */
244 if (errno == EINTR && palarm_fired && *palarm_fired) {
245 TDB_LOG((tdb, 5, "tdb_brlock timed out (fd=%d) at offset %d rw_type=%d lck_type=%d\n",
246 tdb->fd, offset, rw_type, lck_type));
247 return TDB_ERRCODE(TDB_ERR_LOCK_TIMEOUT, -1);
249 /* Otherwise - generic lock error. errno set by fcntl.
250 * EAGAIN is an expected return from non-blocking
252 if (errno != EAGAIN) {
253 TDB_LOG((tdb, 5, "tdb_brlock failed (fd=%d) at offset %d rw_type=%d lck_type=%d: %s\n",
254 tdb->fd, offset, rw_type, lck_type,
257 return TDB_ERRCODE(TDB_ERR_LOCK, -1);
262 /* lock a list in the database. list -1 is the alloc list */
263 static int tdb_lock(TDB_CONTEXT *tdb, int list, int ltype)
265 if (list < -1 || list >= (int)tdb->header.hash_size) {
266 TDB_LOG((tdb, 0,"tdb_lock: invalid list %d for ltype=%d\n",
270 if (tdb->flags & TDB_NOLOCK)
273 /* Since fcntl locks don't nest, we do a lock for the first one,
274 and simply bump the count for future ones */
275 if (tdb->locked[list+1].count == 0) {
276 if (!tdb->read_only && tdb->header.rwlocks) {
277 if (tdb_spinlock(tdb, list, ltype)) {
278 TDB_LOG((tdb, 0, "tdb_lock spinlock failed on list %d ltype=%d\n",
282 } else if (tdb_brlock(tdb,FREELIST_TOP+4*list,ltype,F_SETLKW, 0)) {
283 TDB_LOG((tdb, 0,"tdb_lock failed on list %d ltype=%d (%s)\n",
284 list, ltype, strerror(errno)));
287 tdb->locked[list+1].ltype = ltype;
289 tdb->locked[list+1].count++;
293 /* unlock the database: returns void because it's too late for errors. */
294 /* changed to return int it may be interesting to know there
295 has been an error --simo */
296 static int tdb_unlock(TDB_CONTEXT *tdb, int list, int ltype)
300 if (tdb->flags & TDB_NOLOCK)
304 if (list < -1 || list >= (int)tdb->header.hash_size) {
305 TDB_LOG((tdb, 0, "tdb_unlock: list %d invalid (%d)\n", list, tdb->header.hash_size));
309 if (tdb->locked[list+1].count==0) {
310 TDB_LOG((tdb, 0, "tdb_unlock: count is 0\n"));
314 if (tdb->locked[list+1].count == 1) {
315 /* Down to last nested lock: unlock underneath */
316 if (!tdb->read_only && tdb->header.rwlocks) {
317 ret = tdb_spinunlock(tdb, list, ltype);
319 ret = tdb_brlock(tdb, FREELIST_TOP+4*list, F_UNLCK, F_SETLKW, 0);
324 tdb->locked[list+1].count--;
327 TDB_LOG((tdb, 0,"tdb_unlock: An error occurred unlocking!\n"));
331 /* check for an out of bounds access - if it is out of bounds then
332 see if the database has been expanded by someone else and expand
334 note that "len" is the minimum length needed for the db
336 static int tdb_oob(TDB_CONTEXT *tdb, tdb_off len, int probe)
339 if (len <= tdb->map_size)
341 if (tdb->flags & TDB_INTERNAL) {
343 /* Ensure ecode is set for log fn. */
344 tdb->ecode = TDB_ERR_IO;
345 TDB_LOG((tdb, 0,"tdb_oob len %d beyond internal malloc size %d\n",
346 (int)len, (int)tdb->map_size));
348 return TDB_ERRCODE(TDB_ERR_IO, -1);
351 if (fstat(tdb->fd, &st) == -1)
352 return TDB_ERRCODE(TDB_ERR_IO, -1);
354 if (st.st_size < (size_t)len) {
356 /* Ensure ecode is set for log fn. */
357 tdb->ecode = TDB_ERR_IO;
358 TDB_LOG((tdb, 0,"tdb_oob len %d beyond eof at %d\n",
359 (int)len, (int)st.st_size));
361 return TDB_ERRCODE(TDB_ERR_IO, -1);
364 /* Unmap, update size, remap */
365 if (tdb_munmap(tdb) == -1)
366 return TDB_ERRCODE(TDB_ERR_IO, -1);
367 tdb->map_size = st.st_size;
372 /* write a lump of data at a specified offset */
373 static int tdb_write(TDB_CONTEXT *tdb, tdb_off off, void *buf, tdb_len len)
375 if (tdb_oob(tdb, off + len, 0) != 0)
379 memcpy(off + (char *)tdb->map_ptr, buf, len);
381 else if (pwrite(tdb->fd, buf, len, off) != (ssize_t)len) {
383 else if (lseek(tdb->fd, off, SEEK_SET) != off
384 || write(tdb->fd, buf, len) != (ssize_t)len) {
386 /* Ensure ecode is set for log fn. */
387 tdb->ecode = TDB_ERR_IO;
388 TDB_LOG((tdb, 0,"tdb_write failed at %d len=%d (%s)\n",
389 off, len, strerror(errno)));
390 return TDB_ERRCODE(TDB_ERR_IO, -1);
395 /* read a lump of data at a specified offset, maybe convert */
396 static int tdb_read(TDB_CONTEXT *tdb,tdb_off off,void *buf,tdb_len len,int cv)
398 if (tdb_oob(tdb, off + len, 0) != 0)
402 memcpy(buf, off + (char *)tdb->map_ptr, len);
404 else if (pread(tdb->fd, buf, len, off) != (ssize_t)len) {
406 else if (lseek(tdb->fd, off, SEEK_SET) != off
407 || read(tdb->fd, buf, len) != (ssize_t)len) {
409 /* Ensure ecode is set for log fn. */
410 tdb->ecode = TDB_ERR_IO;
411 TDB_LOG((tdb, 0,"tdb_read failed at %d len=%d (%s)\n",
412 off, len, strerror(errno)));
413 return TDB_ERRCODE(TDB_ERR_IO, -1);
420 /* read a lump of data, allocating the space for it */
421 static char *tdb_alloc_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_len len)
425 if (!(buf = malloc(len))) {
426 /* Ensure ecode is set for log fn. */
427 tdb->ecode = TDB_ERR_OOM;
428 TDB_LOG((tdb, 0,"tdb_alloc_read malloc failed len=%d (%s)\n",
429 len, strerror(errno)));
430 return TDB_ERRCODE(TDB_ERR_OOM, buf);
432 if (tdb_read(tdb, offset, buf, len, 0) == -1) {
439 /* read/write a tdb_off */
440 static int ofs_read(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
442 return tdb_read(tdb, offset, (char*)d, sizeof(*d), DOCONV());
444 static int ofs_write(TDB_CONTEXT *tdb, tdb_off offset, tdb_off *d)
447 return tdb_write(tdb, offset, CONVERT(off), sizeof(*d));
450 /* read/write a record */
451 static int rec_read(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
453 if (tdb_read(tdb, offset, rec, sizeof(*rec),DOCONV()) == -1)
455 if (TDB_BAD_MAGIC(rec)) {
456 /* Ensure ecode is set for log fn. */
457 tdb->ecode = TDB_ERR_CORRUPT;
458 TDB_LOG((tdb, 0,"rec_read bad magic 0x%x at offset=%d\n", rec->magic, offset));
459 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
461 return tdb_oob(tdb, rec->next+sizeof(*rec), 0);
463 static int rec_write(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
465 struct list_struct r = *rec;
466 return tdb_write(tdb, offset, CONVERT(r), sizeof(r));
469 /* read a freelist record and check for simple errors */
470 static int rec_free_read(TDB_CONTEXT *tdb, tdb_off off, struct list_struct *rec)
472 if (tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
475 if (rec->magic == TDB_MAGIC) {
476 /* this happens when a app is showdown while deleting a record - we should
477 not completely fail when this happens */
478 TDB_LOG((tdb, 0,"rec_free_read non-free magic 0x%x at offset=%d - fixing\n",
480 rec->magic = TDB_FREE_MAGIC;
481 if (tdb_write(tdb, off, rec, sizeof(*rec)) == -1)
485 if (rec->magic != TDB_FREE_MAGIC) {
486 /* Ensure ecode is set for log fn. */
487 tdb->ecode = TDB_ERR_CORRUPT;
488 TDB_LOG((tdb, 0,"rec_free_read bad magic 0x%x at offset=%d\n",
490 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
492 if (tdb_oob(tdb, rec->next+sizeof(*rec), 0) != 0)
497 /* update a record tailer (must hold allocation lock) */
498 static int update_tailer(TDB_CONTEXT *tdb, tdb_off offset,
499 const struct list_struct *rec)
503 /* Offset of tailer from record header */
504 totalsize = sizeof(*rec) + rec->rec_len;
505 return ofs_write(tdb, offset + totalsize - sizeof(tdb_off),
509 static tdb_off tdb_dump_record(TDB_CONTEXT *tdb, tdb_off offset)
511 struct list_struct rec;
512 tdb_off tailer_ofs, tailer;
514 if (tdb_read(tdb, offset, (char *)&rec, sizeof(rec), DOCONV()) == -1) {
515 printf("ERROR: failed to read record at %u\n", offset);
519 printf(" rec: offset=%u next=%d rec_len=%d key_len=%d data_len=%d full_hash=0x%x magic=0x%x\n",
520 offset, rec.next, rec.rec_len, rec.key_len, rec.data_len, rec.full_hash, rec.magic);
522 tailer_ofs = offset + sizeof(rec) + rec.rec_len - sizeof(tdb_off);
523 if (ofs_read(tdb, tailer_ofs, &tailer) == -1) {
524 printf("ERROR: failed to read tailer at %u\n", tailer_ofs);
528 if (tailer != rec.rec_len + sizeof(rec)) {
529 printf("ERROR: tailer does not match record! tailer=%u totalsize=%u\n",
530 (unsigned)tailer, (unsigned)(rec.rec_len + sizeof(rec)));
535 static int tdb_dump_chain(TDB_CONTEXT *tdb, int i)
537 tdb_off rec_ptr, top;
539 top = TDB_HASH_TOP(i);
541 if (tdb_lock(tdb, i, F_WRLCK) != 0)
544 if (ofs_read(tdb, top, &rec_ptr) == -1)
545 return tdb_unlock(tdb, i, F_WRLCK);
548 printf("hash=%d\n", i);
551 rec_ptr = tdb_dump_record(tdb, rec_ptr);
554 return tdb_unlock(tdb, i, F_WRLCK);
557 void tdb_dump_all(TDB_CONTEXT *tdb)
560 for (i=0;i<tdb->header.hash_size;i++) {
561 tdb_dump_chain(tdb, i);
563 printf("freelist:\n");
564 tdb_dump_chain(tdb, -1);
567 int tdb_printfreelist(TDB_CONTEXT *tdb)
571 tdb_off offset, rec_ptr;
572 struct list_struct rec;
574 if ((ret = tdb_lock(tdb, -1, F_WRLCK)) != 0)
577 offset = FREELIST_TOP;
579 /* read in the freelist top */
580 if (ofs_read(tdb, offset, &rec_ptr) == -1) {
581 tdb_unlock(tdb, -1, F_WRLCK);
585 printf("freelist top=[0x%08x]\n", rec_ptr );
587 if (tdb_read(tdb, rec_ptr, (char *)&rec, sizeof(rec), DOCONV()) == -1) {
588 tdb_unlock(tdb, -1, F_WRLCK);
592 if (rec.magic != TDB_FREE_MAGIC) {
593 printf("bad magic 0x%08x in free list\n", rec.magic);
594 tdb_unlock(tdb, -1, F_WRLCK);
598 printf("entry offset=[0x%08x], rec.rec_len = [0x%08x (%d)]\n", rec.next, rec.rec_len, rec.rec_len );
599 total_free += rec.rec_len;
601 /* move to the next record */
604 printf("total rec_len = [0x%08x (%d)]\n", (int)total_free,
607 return tdb_unlock(tdb, -1, F_WRLCK);
610 /* Remove an element from the freelist. Must have alloc lock. */
611 static int remove_from_freelist(TDB_CONTEXT *tdb, tdb_off off, tdb_off next)
615 /* read in the freelist top */
616 last_ptr = FREELIST_TOP;
617 while (ofs_read(tdb, last_ptr, &i) != -1 && i != 0) {
619 /* We've found it! */
620 return ofs_write(tdb, last_ptr, &next);
622 /* Follow chain (next offset is at start of record) */
625 TDB_LOG((tdb, 0,"remove_from_freelist: not on list at off=%d\n", off));
626 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
629 /* Add an element into the freelist. Merge adjacent records if
631 static int tdb_free(TDB_CONTEXT *tdb, tdb_off offset, struct list_struct *rec)
635 /* Allocation and tailer lock */
636 if (tdb_lock(tdb, -1, F_WRLCK) != 0)
639 /* set an initial tailer, so if we fail we don't leave a bogus record */
640 if (update_tailer(tdb, offset, rec) != 0) {
641 TDB_LOG((tdb, 0, "tdb_free: upfate_tailer failed!\n"));
645 /* Look right first (I'm an Australian, dammit) */
646 right = offset + sizeof(*rec) + rec->rec_len;
647 if (right + sizeof(*rec) <= tdb->map_size) {
648 struct list_struct r;
650 if (tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
651 TDB_LOG((tdb, 0, "tdb_free: right read failed at %u\n", right));
655 /* If it's free, expand to include it. */
656 if (r.magic == TDB_FREE_MAGIC) {
657 if (remove_from_freelist(tdb, right, r.next) == -1) {
658 TDB_LOG((tdb, 0, "tdb_free: right free failed at %u\n", right));
661 rec->rec_len += sizeof(r) + r.rec_len;
667 left = offset - sizeof(tdb_off);
668 if (left > TDB_DATA_START(tdb->header.hash_size)) {
669 struct list_struct l;
672 /* Read in tailer and jump back to header */
673 if (ofs_read(tdb, left, &leftsize) == -1) {
674 TDB_LOG((tdb, 0, "tdb_free: left offset read failed at %u\n", left));
677 left = offset - leftsize;
679 /* Now read in record */
680 if (tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
681 TDB_LOG((tdb, 0, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
685 /* If it's free, expand to include it. */
686 if (l.magic == TDB_FREE_MAGIC) {
687 if (remove_from_freelist(tdb, left, l.next) == -1) {
688 TDB_LOG((tdb, 0, "tdb_free: left free failed at %u\n", left));
692 rec->rec_len += leftsize;
698 if (update_tailer(tdb, offset, rec) == -1) {
699 TDB_LOG((tdb, 0, "tdb_free: update_tailer failed at %u\n", offset));
703 /* Now, prepend to free list */
704 rec->magic = TDB_FREE_MAGIC;
706 if (ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
707 rec_write(tdb, offset, rec) == -1 ||
708 ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
709 TDB_LOG((tdb, 0, "tdb_free record write failed at offset=%d\n", offset));
713 /* And we're done. */
714 tdb_unlock(tdb, -1, F_WRLCK);
718 tdb_unlock(tdb, -1, F_WRLCK);
723 /* expand a file. we prefer to use ftruncate, as that is what posix
724 says to use for mmap expansion */
725 static int expand_file(TDB_CONTEXT *tdb, tdb_off size, tdb_off addition)
728 #if HAVE_FTRUNCATE_EXTEND
729 if (ftruncate(tdb->fd, size+addition) != 0) {
730 TDB_LOG((tdb, 0, "expand_file ftruncate to %d failed (%s)\n",
731 size+addition, strerror(errno)));
738 if (pwrite(tdb->fd, &b, 1, (size+addition) - 1) != 1) {
740 if (lseek(tdb->fd, (size+addition) - 1, SEEK_SET) != (size+addition) - 1 ||
741 write(tdb->fd, &b, 1) != 1) {
743 TDB_LOG((tdb, 0, "expand_file to %d failed (%s)\n",
744 size+addition, strerror(errno)));
749 /* now fill the file with something. This ensures that the file isn't sparse, which would be
750 very bad if we ran out of disk. This must be done with write, not via mmap */
751 memset(buf, 0x42, sizeof(buf));
753 int n = addition>sizeof(buf)?sizeof(buf):addition;
755 int ret = pwrite(tdb->fd, buf, n, size);
758 if (lseek(tdb->fd, size, SEEK_SET) != size)
760 ret = write(tdb->fd, buf, n);
763 TDB_LOG((tdb, 0, "expand_file write of %d failed (%s)\n",
764 n, strerror(errno)));
774 /* expand the database at least size bytes by expanding the underlying
775 file and doing the mmap again if necessary */
776 static int tdb_expand(TDB_CONTEXT *tdb, tdb_off size)
778 struct list_struct rec;
781 if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
782 TDB_LOG((tdb, 0, "lock failed in tdb_expand\n"));
786 /* must know about any previous expansions by another process */
787 tdb_oob(tdb, tdb->map_size + 1, 1);
789 /* always make room for at least 10 more records, and round
790 the database up to a multiple of TDB_PAGE_SIZE */
791 size = TDB_ALIGN(tdb->map_size + size*10, TDB_PAGE_SIZE) - tdb->map_size;
793 if (!(tdb->flags & TDB_INTERNAL))
797 * We must ensure the file is unmapped before doing this
798 * to ensure consistency with systems like OpenBSD where
799 * writes and mmaps are not consistent.
802 /* expand the file itself */
803 if (!(tdb->flags & TDB_INTERNAL)) {
804 if (expand_file(tdb, tdb->map_size, size) != 0)
808 tdb->map_size += size;
810 if (tdb->flags & TDB_INTERNAL)
811 tdb->map_ptr = realloc(tdb->map_ptr, tdb->map_size);
814 * We must ensure the file is remapped before adding the space
815 * to ensure consistency with systems like OpenBSD where
816 * writes and mmaps are not consistent.
819 /* We're ok if the mmap fails as we'll fallback to read/write */
823 /* form a new freelist record */
824 memset(&rec,'\0',sizeof(rec));
825 rec.rec_len = size - sizeof(rec);
827 /* link it into the free list */
828 offset = tdb->map_size - size;
829 if (tdb_free(tdb, offset, &rec) == -1)
832 tdb_unlock(tdb, -1, F_WRLCK);
835 tdb_unlock(tdb, -1, F_WRLCK);
839 /* allocate some space from the free list. The offset returned points
840 to a unconnected list_struct within the database with room for at
841 least length bytes of total data
843 0 is returned if the space could not be allocated
845 static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length,
846 struct list_struct *rec)
848 tdb_off rec_ptr, last_ptr, newrec_ptr;
849 struct list_struct newrec;
851 memset(&newrec, '\0', sizeof(newrec));
853 if (tdb_lock(tdb, -1, F_WRLCK) == -1)
856 /* Extra bytes required for tailer */
857 length += sizeof(tdb_off);
860 last_ptr = FREELIST_TOP;
862 /* read in the freelist top */
863 if (ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
866 /* keep looking until we find a freelist record big enough */
868 if (rec_free_read(tdb, rec_ptr, rec) == -1)
871 if (rec->rec_len >= length) {
872 /* found it - now possibly split it up */
873 if (rec->rec_len > length + MIN_REC_SIZE) {
874 /* Length of left piece */
875 length = TDB_ALIGN(length, TDB_ALIGNMENT);
877 /* Right piece to go on free list */
878 newrec.rec_len = rec->rec_len
879 - (sizeof(*rec) + length);
880 newrec_ptr = rec_ptr + sizeof(*rec) + length;
882 /* And left record is shortened */
883 rec->rec_len = length;
887 /* Remove allocated record from the free list */
888 if (ofs_write(tdb, last_ptr, &rec->next) == -1)
891 /* Update header: do this before we drop alloc
892 lock, otherwise tdb_free() might try to
893 merge with us, thinking we're free.
894 (Thanks Jeremy Allison). */
895 rec->magic = TDB_MAGIC;
896 if (rec_write(tdb, rec_ptr, rec) == -1)
899 /* Did we create new block? */
901 /* Update allocated record tailer (we
903 if (update_tailer(tdb, rec_ptr, rec) == -1)
906 /* Free new record */
907 if (tdb_free(tdb, newrec_ptr, &newrec) == -1)
911 /* all done - return the new record offset */
912 tdb_unlock(tdb, -1, F_WRLCK);
915 /* move to the next record */
919 /* we didn't find enough space. See if we can expand the
920 database and if we can then try again */
921 if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
924 tdb_unlock(tdb, -1, F_WRLCK);
928 /* initialise a new database with a specified hash size */
929 static int tdb_new_database(TDB_CONTEXT *tdb, int hash_size)
931 struct tdb_header *newdb;
934 /* We make it up in memory, then write it out if not internal */
935 size = sizeof(struct tdb_header) + (hash_size+1)*sizeof(tdb_off);
936 if (!(newdb = calloc(size, 1)))
937 return TDB_ERRCODE(TDB_ERR_OOM, -1);
939 /* Fill in the header */
940 newdb->version = TDB_VERSION;
941 newdb->hash_size = hash_size;
942 if (tdb->flags & TDB_INTERNAL) {
943 tdb->map_size = size;
944 tdb->map_ptr = (char *)newdb;
945 memcpy(&tdb->header, newdb, sizeof(tdb->header));
946 /* Convert the `ondisk' version if asked. */
950 if (lseek(tdb->fd, 0, SEEK_SET) == -1)
953 if (ftruncate(tdb->fd, 0) == -1)
956 /* This creates an endian-converted header, as if read from disk */
958 memcpy(&tdb->header, newdb, sizeof(tdb->header));
959 /* Don't endian-convert the magic food! */
960 memcpy(newdb->magic_food, TDB_MAGIC_FOOD, strlen(TDB_MAGIC_FOOD)+1);
961 if (write(tdb->fd, newdb, size) != size)
964 ret = tdb_create_rwlocks(tdb->fd, hash_size);
971 /* Returns 0 on fail. On success, return offset of record, and fills
973 static tdb_off tdb_find(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash,
974 struct list_struct *r)
978 /* read in the hash top */
979 if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
982 /* keep looking until we find the right record */
984 if (rec_read(tdb, rec_ptr, r) == -1)
987 if (!TDB_DEAD(r) && hash==r->full_hash && key.dsize==r->key_len) {
989 /* a very likely hit - read the key */
990 k = tdb_alloc_read(tdb, rec_ptr + sizeof(*r),
995 if (memcmp(key.dptr, k, key.dsize) == 0) {
1003 return TDB_ERRCODE(TDB_ERR_NOEXIST, 0);
1006 /* As tdb_find, but if you succeed, keep the lock */
1007 static tdb_off tdb_find_lock_hash(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash, int locktype,
1008 struct list_struct *rec)
1012 if (tdb_lock(tdb, BUCKET(hash), locktype) == -1)
1014 if (!(rec_ptr = tdb_find(tdb, key, hash, rec)))
1015 tdb_unlock(tdb, BUCKET(hash), locktype);
1019 enum TDB_ERROR tdb_error(TDB_CONTEXT *tdb)
1024 static struct tdb_errname {
1025 enum TDB_ERROR ecode; const char *estring;
1026 } emap[] = { {TDB_SUCCESS, "Success"},
1027 {TDB_ERR_CORRUPT, "Corrupt database"},
1028 {TDB_ERR_IO, "IO Error"},
1029 {TDB_ERR_LOCK, "Locking error"},
1030 {TDB_ERR_OOM, "Out of memory"},
1031 {TDB_ERR_EXISTS, "Record exists"},
1032 {TDB_ERR_NOLOCK, "Lock exists on other keys"},
1033 {TDB_ERR_NOEXIST, "Record does not exist"} };
1035 /* Error string for the last tdb error */
1036 const char *tdb_errorstr(TDB_CONTEXT *tdb)
1039 for (i = 0; i < sizeof(emap) / sizeof(struct tdb_errname); i++)
1040 if (tdb->ecode == emap[i].ecode)
1041 return emap[i].estring;
1042 return "Invalid error code";
1045 /* update an entry in place - this only works if the new data size
1046 is <= the old data size and the key exists.
1047 on failure return -1.
1050 static int tdb_update_hash(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash, TDB_DATA dbuf)
1052 struct list_struct rec;
1056 if (!(rec_ptr = tdb_find(tdb, key, hash, &rec)))
1059 /* must be long enough key, data and tailer */
1060 if (rec.rec_len < key.dsize + dbuf.dsize + sizeof(tdb_off)) {
1061 tdb->ecode = TDB_SUCCESS; /* Not really an error */
1065 if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
1066 dbuf.dptr, dbuf.dsize) == -1)
1069 if (dbuf.dsize != rec.data_len) {
1071 rec.data_len = dbuf.dsize;
1072 return rec_write(tdb, rec_ptr, &rec);
1078 /* find an entry in the database given a key */
1079 /* If an entry doesn't exist tdb_err will be set to
1080 * TDB_ERR_NOEXIST. If a key has no data attached
1081 * tdb_err will not be set. Both will return a
1082 * zero pptr and zero dsize.
1085 TDB_DATA tdb_fetch(TDB_CONTEXT *tdb, TDB_DATA key)
1088 struct list_struct rec;
1092 /* find which hash bucket it is in */
1093 hash = tdb->hash_fn(&key);
1094 if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec)))
1098 ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec) + rec.key_len,
1102 ret.dsize = rec.data_len;
1103 tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
1107 /* check if an entry in the database exists
1109 note that 1 is returned if the key is found and 0 is returned if not found
1110 this doesn't match the conventions in the rest of this module, but is
1111 compatible with gdbm
1113 static int tdb_exists_hash(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash)
1115 struct list_struct rec;
1117 if (tdb_find_lock_hash(tdb, key, hash, F_RDLCK, &rec) == 0)
1119 tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
1123 int tdb_exists(TDB_CONTEXT *tdb, TDB_DATA key)
1125 u32 hash = tdb->hash_fn(&key);
1126 return tdb_exists_hash(tdb, key, hash);
1129 /* record lock stops delete underneath */
1130 static int lock_record(TDB_CONTEXT *tdb, tdb_off off)
1132 return off ? tdb_brlock(tdb, off, F_RDLCK, F_SETLKW, 0) : 0;
1135 Write locks override our own fcntl readlocks, so check it here.
1136 Note this is meant to be F_SETLK, *not* F_SETLKW, as it's not
1137 an error to fail to get the lock here.
1140 static int write_lock_record(TDB_CONTEXT *tdb, tdb_off off)
1142 struct tdb_traverse_lock *i;
1143 for (i = &tdb->travlocks; i; i = i->next)
1146 return tdb_brlock(tdb, off, F_WRLCK, F_SETLK, 1);
1150 Note this is meant to be F_SETLK, *not* F_SETLKW, as it's not
1151 an error to fail to get the lock here.
1154 static int write_unlock_record(TDB_CONTEXT *tdb, tdb_off off)
1156 return tdb_brlock(tdb, off, F_UNLCK, F_SETLK, 0);
1158 /* fcntl locks don't stack: avoid unlocking someone else's */
1159 static int unlock_record(TDB_CONTEXT *tdb, tdb_off off)
1161 struct tdb_traverse_lock *i;
1166 for (i = &tdb->travlocks; i; i = i->next)
1169 return (count == 1 ? tdb_brlock(tdb, off, F_UNLCK, F_SETLKW, 0) : 0);
1172 /* actually delete an entry in the database given the offset */
1173 static int do_delete(TDB_CONTEXT *tdb, tdb_off rec_ptr, struct list_struct*rec)
1175 tdb_off last_ptr, i;
1176 struct list_struct lastrec;
1178 if (tdb->read_only) return -1;
1180 if (write_lock_record(tdb, rec_ptr) == -1) {
1181 /* Someone traversing here: mark it as dead */
1182 rec->magic = TDB_DEAD_MAGIC;
1183 return rec_write(tdb, rec_ptr, rec);
1185 if (write_unlock_record(tdb, rec_ptr) != 0)
1188 /* find previous record in hash chain */
1189 if (ofs_read(tdb, TDB_HASH_TOP(rec->full_hash), &i) == -1)
1191 for (last_ptr = 0; i != rec_ptr; last_ptr = i, i = lastrec.next)
1192 if (rec_read(tdb, i, &lastrec) == -1)
1195 /* unlink it: next ptr is at start of record. */
1197 last_ptr = TDB_HASH_TOP(rec->full_hash);
1198 if (ofs_write(tdb, last_ptr, &rec->next) == -1)
1201 /* recover the space */
1202 if (tdb_free(tdb, rec_ptr, rec) == -1)
1207 /* Uses traverse lock: 0 = finish, -1 = error, other = record offset */
1208 static int tdb_next_lock(TDB_CONTEXT *tdb, struct tdb_traverse_lock *tlock,
1209 struct list_struct *rec)
1211 int want_next = (tlock->off != 0);
1213 /* Lock each chain from the start one. */
1214 for (; tlock->hash < tdb->header.hash_size; tlock->hash++) {
1215 if (tdb_lock(tdb, tlock->hash, F_WRLCK) == -1)
1218 /* No previous record? Start at top of chain. */
1220 if (ofs_read(tdb, TDB_HASH_TOP(tlock->hash),
1224 /* Otherwise unlock the previous record. */
1225 if (unlock_record(tdb, tlock->off) != 0)
1230 /* We have offset of old record: grab next */
1231 if (rec_read(tdb, tlock->off, rec) == -1)
1233 tlock->off = rec->next;
1236 /* Iterate through chain */
1237 while( tlock->off) {
1239 if (rec_read(tdb, tlock->off, rec) == -1)
1241 if (!TDB_DEAD(rec)) {
1242 /* Woohoo: we found one! */
1243 if (lock_record(tdb, tlock->off) != 0)
1247 /* Try to clean dead ones from old traverses */
1248 current = tlock->off;
1249 tlock->off = rec->next;
1250 if (!tdb->read_only &&
1251 do_delete(tdb, current, rec) != 0)
1254 tdb_unlock(tdb, tlock->hash, F_WRLCK);
1257 /* We finished iteration without finding anything */
1258 return TDB_ERRCODE(TDB_SUCCESS, 0);
1262 if (tdb_unlock(tdb, tlock->hash, F_WRLCK) != 0)
1263 TDB_LOG((tdb, 0, "tdb_next_lock: On error unlock failed!\n"));
1267 /* traverse the entire database - calling fn(tdb, key, data) on each element.
1268 return -1 on error or the record count traversed
1269 if fn is NULL then it is not called
1270 a non-zero return value from fn() indicates that the traversal should stop
1272 int tdb_traverse(TDB_CONTEXT *tdb, tdb_traverse_func fn, void *private)
1275 struct list_struct rec;
1276 struct tdb_traverse_lock tl = { NULL, 0, 0 };
1279 /* This was in the initializaton, above, but the IRIX compiler
1280 * did not like it. crh
1282 tl.next = tdb->travlocks.next;
1284 /* fcntl locks don't stack: beware traverse inside traverse */
1285 tdb->travlocks.next = &tl;
1287 /* tdb_next_lock places locks on the record returned, and its chain */
1288 while ((ret = tdb_next_lock(tdb, &tl, &rec)) > 0) {
1290 /* now read the full record */
1291 key.dptr = tdb_alloc_read(tdb, tl.off + sizeof(rec),
1292 rec.key_len + rec.data_len);
1295 if (tdb_unlock(tdb, tl.hash, F_WRLCK) != 0)
1297 if (unlock_record(tdb, tl.off) != 0)
1298 TDB_LOG((tdb, 0, "tdb_traverse: key.dptr == NULL and unlock_record failed!\n"));
1301 key.dsize = rec.key_len;
1302 dbuf.dptr = key.dptr + rec.key_len;
1303 dbuf.dsize = rec.data_len;
1305 /* Drop chain lock, call out */
1306 if (tdb_unlock(tdb, tl.hash, F_WRLCK) != 0) {
1310 if (fn && fn(tdb, key, dbuf, private)) {
1311 /* They want us to terminate traversal */
1313 if (unlock_record(tdb, tl.off) != 0) {
1314 TDB_LOG((tdb, 0, "tdb_traverse: unlock_record failed!\n"));;
1317 tdb->travlocks.next = tl.next;
1318 SAFE_FREE(key.dptr);
1321 SAFE_FREE(key.dptr);
1324 tdb->travlocks.next = tl.next;
1331 /* find the first entry in the database and return its key */
1332 TDB_DATA tdb_firstkey(TDB_CONTEXT *tdb)
1335 struct list_struct rec;
1337 /* release any old lock */
1338 if (unlock_record(tdb, tdb->travlocks.off) != 0)
1340 tdb->travlocks.off = tdb->travlocks.hash = 0;
1342 if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0)
1344 /* now read the key */
1345 key.dsize = rec.key_len;
1346 key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize);
1347 if (tdb_unlock(tdb, BUCKET(tdb->travlocks.hash), F_WRLCK) != 0)
1348 TDB_LOG((tdb, 0, "tdb_firstkey: error occurred while tdb_unlocking!\n"));
1352 /* find the next entry in the database, returning its key */
1353 TDB_DATA tdb_nextkey(TDB_CONTEXT *tdb, TDB_DATA oldkey)
1356 TDB_DATA key = tdb_null;
1357 struct list_struct rec;
1360 /* Is locked key the old key? If so, traverse will be reliable. */
1361 if (tdb->travlocks.off) {
1362 if (tdb_lock(tdb,tdb->travlocks.hash,F_WRLCK))
1364 if (rec_read(tdb, tdb->travlocks.off, &rec) == -1
1365 || !(k = tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),
1367 || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) {
1368 /* No, it wasn't: unlock it and start from scratch */
1369 if (unlock_record(tdb, tdb->travlocks.off) != 0)
1371 if (tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK) != 0)
1373 tdb->travlocks.off = 0;
1379 if (!tdb->travlocks.off) {
1380 /* No previous element: do normal find, and lock record */
1381 tdb->travlocks.off = tdb_find_lock_hash(tdb, oldkey, tdb->hash_fn(&oldkey), F_WRLCK, &rec);
1382 if (!tdb->travlocks.off)
1384 tdb->travlocks.hash = BUCKET(rec.full_hash);
1385 if (lock_record(tdb, tdb->travlocks.off) != 0) {
1386 TDB_LOG((tdb, 0, "tdb_nextkey: lock_record failed (%s)!\n", strerror(errno)));
1390 oldhash = tdb->travlocks.hash;
1392 /* Grab next record: locks chain and returned record,
1393 unlocks old record */
1394 if (tdb_next_lock(tdb, &tdb->travlocks, &rec) > 0) {
1395 key.dsize = rec.key_len;
1396 key.dptr = tdb_alloc_read(tdb, tdb->travlocks.off+sizeof(rec),
1398 /* Unlock the chain of this new record */
1399 if (tdb_unlock(tdb, tdb->travlocks.hash, F_WRLCK) != 0)
1400 TDB_LOG((tdb, 0, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
1402 /* Unlock the chain of old record */
1403 if (tdb_unlock(tdb, BUCKET(oldhash), F_WRLCK) != 0)
1404 TDB_LOG((tdb, 0, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
1408 /* delete an entry in the database given a key */
1409 static int tdb_delete_hash(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash)
1412 struct list_struct rec;
1415 if (!(rec_ptr = tdb_find_lock_hash(tdb, key, hash, F_WRLCK, &rec)))
1417 ret = do_delete(tdb, rec_ptr, &rec);
1418 if (tdb_unlock(tdb, BUCKET(rec.full_hash), F_WRLCK) != 0)
1419 TDB_LOG((tdb, 0, "tdb_delete: WARNING tdb_unlock failed!\n"));
1423 int tdb_delete(TDB_CONTEXT *tdb, TDB_DATA key)
1425 u32 hash = tdb->hash_fn(&key);
1426 return tdb_delete_hash(tdb, key, hash);
1429 /* store an element in the database, replacing any existing element
1432 return 0 on success, -1 on failure
1434 int tdb_store(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
1436 struct list_struct rec;
1442 /* find which hash bucket it is in */
1443 hash = tdb->hash_fn(&key);
1444 if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
1447 /* check for it existing, on insert. */
1448 if (flag == TDB_INSERT) {
1449 if (tdb_exists_hash(tdb, key, hash)) {
1450 tdb->ecode = TDB_ERR_EXISTS;
1454 /* first try in-place update, on modify or replace. */
1455 if (tdb_update_hash(tdb, key, hash, dbuf) == 0)
1457 if (tdb->ecode == TDB_ERR_NOEXIST &&
1458 flag == TDB_MODIFY) {
1459 /* if the record doesn't exist and we are in TDB_MODIFY mode then
1460 we should fail the store */
1464 /* reset the error code potentially set by the tdb_update() */
1465 tdb->ecode = TDB_SUCCESS;
1467 /* delete any existing record - if it doesn't exist we don't
1468 care. Doing this first reduces fragmentation, and avoids
1469 coalescing with `allocated' block before it's updated. */
1470 if (flag != TDB_INSERT)
1471 tdb_delete_hash(tdb, key, hash);
1473 /* Copy key+value *before* allocating free space in case malloc
1474 fails and we are left with a dead spot in the tdb. */
1476 if (!(p = (char *)malloc(key.dsize + dbuf.dsize))) {
1477 tdb->ecode = TDB_ERR_OOM;
1481 memcpy(p, key.dptr, key.dsize);
1483 memcpy(p+key.dsize, dbuf.dptr, dbuf.dsize);
1485 /* we have to allocate some space */
1486 if (!(rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize, &rec)))
1489 /* Read hash top into next ptr */
1490 if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
1493 rec.key_len = key.dsize;
1494 rec.data_len = dbuf.dsize;
1495 rec.full_hash = hash;
1496 rec.magic = TDB_MAGIC;
1498 /* write out and point the top of the hash chain at it */
1499 if (rec_write(tdb, rec_ptr, &rec) == -1
1500 || tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+dbuf.dsize)==-1
1501 || ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
1502 /* Need to tdb_unallocate() here */
1507 tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
1514 /* Attempt to append data to an entry in place - this only works if the new data size
1515 is <= the old data size and the key exists.
1516 on failure return -1. Record must be locked before calling.
1518 static int tdb_append_inplace(TDB_CONTEXT *tdb, TDB_DATA key, u32 hash, TDB_DATA new_dbuf)
1520 struct list_struct rec;
1524 if (!(rec_ptr = tdb_find(tdb, key, hash, &rec)))
1527 /* Append of 0 is always ok. */
1528 if (new_dbuf.dsize == 0)
1531 /* must be long enough for key, old data + new data and tailer */
1532 if (rec.rec_len < key.dsize + rec.data_len + new_dbuf.dsize + sizeof(tdb_off)) {
1534 tdb->ecode = TDB_SUCCESS; /* Not really an error */
1538 if (tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len + rec.data_len,
1539 new_dbuf.dptr, new_dbuf.dsize) == -1)
1543 rec.data_len += new_dbuf.dsize;
1544 return rec_write(tdb, rec_ptr, &rec);
1547 /* Append to an entry. Create if not exist. */
1549 int tdb_append(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA new_dbuf)
1551 struct list_struct rec;
1556 size_t new_data_size = 0;
1558 /* find which hash bucket it is in */
1559 hash = tdb->hash_fn(&key);
1560 if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
1563 /* first try in-place. */
1564 if (tdb_append_inplace(tdb, key, hash, new_dbuf) == 0)
1567 /* reset the error code potentially set by the tdb_append_inplace() */
1568 tdb->ecode = TDB_SUCCESS;
1571 if (!(rec_ptr = tdb_find(tdb, key, hash, &rec))) {
1572 if (tdb->ecode != TDB_ERR_NOEXIST)
1575 /* Not found - create. */
1577 ret = tdb_store(tdb, key, new_dbuf, TDB_INSERT);
1581 new_data_size = rec.data_len + new_dbuf.dsize;
1583 /* Copy key+old_value+value *before* allocating free space in case malloc
1584 fails and we are left with a dead spot in the tdb. */
1586 if (!(p = (char *)malloc(key.dsize + new_data_size))) {
1587 tdb->ecode = TDB_ERR_OOM;
1591 /* Copy the key in place. */
1592 memcpy(p, key.dptr, key.dsize);
1594 /* Now read the old data into place. */
1596 tdb_read(tdb, rec_ptr + sizeof(rec) + rec.key_len, p + key.dsize, rec.data_len, 0) == -1)
1599 /* Finally append the new data. */
1601 memcpy(p+key.dsize+rec.data_len, new_dbuf.dptr, new_dbuf.dsize);
1603 /* delete any existing record - if it doesn't exist we don't
1604 care. Doing this first reduces fragmentation, and avoids
1605 coalescing with `allocated' block before it's updated. */
1607 tdb_delete_hash(tdb, key, hash);
1609 if (!(rec_ptr = tdb_allocate(tdb, key.dsize + new_data_size, &rec)))
1612 /* Read hash top into next ptr */
1613 if (ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
1616 rec.key_len = key.dsize;
1617 rec.data_len = new_data_size;
1618 rec.full_hash = hash;
1619 rec.magic = TDB_MAGIC;
1621 /* write out and point the top of the hash chain at it */
1622 if (rec_write(tdb, rec_ptr, &rec) == -1
1623 || tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+new_data_size)==-1
1624 || ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
1625 /* Need to tdb_unallocate() here */
1631 tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
1639 static int tdb_already_open(dev_t device,
1644 for (i = tdbs; i; i = i->next) {
1645 if (i->device == device && i->inode == ino) {
1653 /* This is based on the hash algorithm from gdbm */
1654 static u32 default_tdb_hash(TDB_DATA *key)
1656 u32 value; /* Used to compute the hash value. */
1657 u32 i; /* Used to cycle through random values. */
1659 /* Set the initial value from the key size. */
1660 for (value = 0x238F13AF * key->dsize, i=0; i < key->dsize; i++)
1661 value = (value + (key->dptr[i] << (i*5 % 24)));
1663 return (1103515243 * value + 12345);
1666 /* open the database, creating it if necessary
1668 The open_flags and mode are passed straight to the open call on the
1669 database file. A flags value of O_WRONLY is invalid. The hash size
1670 is advisory, use zero for a default value.
1672 Return is NULL on error, in which case errno is also set. Don't
1673 try to call tdb_error or tdb_errname, just do strerror(errno).
1675 @param name may be NULL for internal databases. */
1676 TDB_CONTEXT *tdb_open(const char *name, int hash_size, int tdb_flags,
1677 int open_flags, mode_t mode)
1679 return tdb_open_ex(name, hash_size, tdb_flags, open_flags, mode, NULL, NULL);
1683 TDB_CONTEXT *tdb_open_ex(const char *name, int hash_size, int tdb_flags,
1684 int open_flags, mode_t mode,
1685 tdb_log_func log_fn,
1686 tdb_hash_func hash_fn)
1690 int rev = 0, locked = 0;
1694 if (!(tdb = calloc(1, sizeof *tdb))) {
1695 /* Can't log this */
1701 tdb->map_ptr = NULL;
1702 tdb->flags = tdb_flags;
1703 tdb->open_flags = open_flags;
1704 tdb->log_fn = log_fn;
1705 tdb->hash_fn = hash_fn ? hash_fn : default_tdb_hash;
1707 if ((open_flags & O_ACCMODE) == O_WRONLY) {
1708 TDB_LOG((tdb, 0, "tdb_open_ex: can't open tdb %s write-only\n",
1715 hash_size = DEFAULT_HASH_SIZE;
1716 if ((open_flags & O_ACCMODE) == O_RDONLY) {
1718 /* read only databases don't do locking or clear if first */
1719 tdb->flags |= TDB_NOLOCK;
1720 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
1723 /* internal databases don't mmap or lock, and start off cleared */
1724 if (tdb->flags & TDB_INTERNAL) {
1725 tdb->flags |= (TDB_NOLOCK | TDB_NOMMAP);
1726 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
1727 if (tdb_new_database(tdb, hash_size) != 0) {
1728 TDB_LOG((tdb, 0, "tdb_open_ex: tdb_new_database failed!"));
1735 if ((tdb->fd = open(name, open_flags, mode)) == -1) {
1736 if ((open_flags & O_CREAT) && errno == ENOENT &&
1737 mkdir_recursive(PPP_PATH_VARRUN) == 0)
1740 TDB_LOG((tdb, 5, "tdb_open_ex: could not open file %s: %s\n",
1741 name, strerror(errno)));
1742 goto fail; /* errno set by open(2) */
1745 /* ensure there is only one process initialising at once */
1746 if (tdb_brlock(tdb, GLOBAL_LOCK, F_WRLCK, F_SETLKW, 0) == -1) {
1747 TDB_LOG((tdb, 0, "tdb_open_ex: failed to get global lock on %s: %s\n",
1748 name, strerror(errno)));
1749 goto fail; /* errno set by tdb_brlock */
1752 /* we need to zero database if we are the only one with it open */
1753 if ((tdb_flags & TDB_CLEAR_IF_FIRST) &&
1754 (locked = (tdb_brlock(tdb, ACTIVE_LOCK, F_WRLCK, F_SETLK, 0) == 0))) {
1755 open_flags |= O_CREAT;
1756 if (ftruncate(tdb->fd, 0) == -1) {
1757 TDB_LOG((tdb, 0, "tdb_open_ex: "
1758 "failed to truncate %s: %s\n",
1759 name, strerror(errno)));
1760 goto fail; /* errno set by ftruncate */
1764 if (read(tdb->fd, &tdb->header, sizeof(tdb->header)) != sizeof(tdb->header)
1765 || strcmp(tdb->header.magic_food, TDB_MAGIC_FOOD) != 0
1766 || (tdb->header.version != TDB_VERSION
1767 && !(rev = (tdb->header.version==TDB_BYTEREV(TDB_VERSION))))) {
1768 /* its not a valid database - possibly initialise it */
1769 if (!(open_flags & O_CREAT) || tdb_new_database(tdb, hash_size) == -1) {
1770 errno = EIO; /* ie bad format or something */
1773 rev = (tdb->flags & TDB_CONVERT);
1775 vp = (unsigned char *)&tdb->header.version;
1776 vertest = (((u32)vp[0]) << 24) | (((u32)vp[1]) << 16) |
1777 (((u32)vp[2]) << 8) | (u32)vp[3];
1778 tdb->flags |= (vertest==TDB_VERSION) ? TDB_BIGENDIAN : 0;
1780 tdb->flags &= ~TDB_CONVERT;
1782 tdb->flags |= TDB_CONVERT;
1783 convert(&tdb->header, sizeof(tdb->header));
1785 if (fstat(tdb->fd, &st) == -1)
1788 /* Is it already in the open list? If so, fail. */
1789 if (tdb_already_open(st.st_dev, st.st_ino)) {
1790 TDB_LOG((tdb, 2, "tdb_open_ex: "
1791 "%s (%d,%d) is already open in this process\n",
1792 name, (int)st.st_dev, (int)st.st_ino));
1797 if (!(tdb->name = (char *)strdup(name))) {
1802 tdb->map_size = st.st_size;
1803 tdb->device = st.st_dev;
1804 tdb->inode = st.st_ino;
1805 tdb->locked = calloc(tdb->header.hash_size+1, sizeof(tdb->locked[0]));
1807 TDB_LOG((tdb, 2, "tdb_open_ex: "
1808 "failed to allocate lock structure for %s\n",
1815 if (!tdb->read_only)
1816 if (tdb_clear_spinlocks(tdb) != 0) {
1817 TDB_LOG((tdb, 0, "tdb_open_ex: "
1818 "failed to clear spinlock\n"));
1821 if (tdb_brlock(tdb, ACTIVE_LOCK, F_UNLCK, F_SETLK, 0) == -1) {
1822 TDB_LOG((tdb, 0, "tdb_open_ex: "
1823 "failed to take ACTIVE_LOCK on %s: %s\n",
1824 name, strerror(errno)));
1830 /* We always need to do this if the CLEAR_IF_FIRST flag is set, even if
1831 we didn't get the initial exclusive lock as we need to let all other
1832 users know we're using it. */
1834 if (tdb_flags & TDB_CLEAR_IF_FIRST) {
1835 /* leave this lock in place to indicate it's in use */
1836 if (tdb_brlock(tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1)
1842 /* Internal (memory-only) databases skip all the code above to
1843 * do with disk files, and resume here by releasing their
1844 * global lock and hooking into the active list. */
1845 if (tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0) == -1)
1852 { int save_errno = errno;
1858 if (tdb->flags & TDB_INTERNAL)
1859 SAFE_FREE(tdb->map_ptr);
1863 SAFE_FREE(tdb->name);
1865 if (close(tdb->fd) != 0)
1866 TDB_LOG((tdb, 5, "tdb_open_ex: failed to close tdb->fd on error!\n"));
1867 SAFE_FREE(tdb->locked);
1877 * @returns -1 for error; 0 for success.
1879 int tdb_close(TDB_CONTEXT *tdb)
1885 if (tdb->flags & TDB_INTERNAL)
1886 SAFE_FREE(tdb->map_ptr);
1890 SAFE_FREE(tdb->name);
1892 ret = close(tdb->fd);
1893 SAFE_FREE(tdb->locked);
1895 /* Remove from contexts list */
1896 for (i = &tdbs; *i; i = &(*i)->next) {
1903 memset(tdb, 0, sizeof(*tdb));
1909 /* lock/unlock entire database */
1910 int tdb_lockall(TDB_CONTEXT *tdb)
1914 /* There are no locks on read-only dbs */
1916 return TDB_ERRCODE(TDB_ERR_LOCK, -1);
1917 for (i = 0; i < tdb->header.hash_size; i++)
1918 if (tdb_lock(tdb, i, F_WRLCK))
1921 /* If error, release locks we have... */
1922 if (i < tdb->header.hash_size) {
1925 for ( j = 0; j < i; j++)
1926 tdb_unlock(tdb, j, F_WRLCK);
1927 return TDB_ERRCODE(TDB_ERR_NOLOCK, -1);
1932 void tdb_unlockall(TDB_CONTEXT *tdb)
1935 for (i=0; i < tdb->header.hash_size; i++)
1936 tdb_unlock(tdb, i, F_WRLCK);
1939 /* lock/unlock one hash chain. This is meant to be used to reduce
1940 contention - it cannot guarantee how many records will be locked */
1941 int tdb_chainlock(TDB_CONTEXT *tdb, TDB_DATA key)
1943 return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
1946 int tdb_chainunlock(TDB_CONTEXT *tdb, TDB_DATA key)
1948 return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
1951 int tdb_chainlock_read(TDB_CONTEXT *tdb, TDB_DATA key)
1953 return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK);
1956 int tdb_chainunlock_read(TDB_CONTEXT *tdb, TDB_DATA key)
1958 return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK);
1962 /* register a loging function */
1963 void tdb_logging_function(TDB_CONTEXT *tdb, void (*fn)(TDB_CONTEXT *, int , const char *, ...))
1968 /* reopen a tdb - this can be used after a fork to ensure that we have an independent
1969 seek pointer from our parent and to re-establish locks */
1970 int tdb_reopen(TDB_CONTEXT *tdb)
1974 if (tdb->flags & TDB_INTERNAL)
1975 return 0; /* Nothing to do. */
1976 if (tdb_munmap(tdb) != 0) {
1977 TDB_LOG((tdb, 0, "tdb_reopen: munmap failed (%s)\n", strerror(errno)));
1980 if (close(tdb->fd) != 0)
1981 TDB_LOG((tdb, 0, "tdb_reopen: WARNING closing tdb->fd failed!\n"));
1982 tdb->fd = open(tdb->name, tdb->open_flags & ~(O_CREAT|O_TRUNC), 0);
1983 if (tdb->fd == -1) {
1984 TDB_LOG((tdb, 0, "tdb_reopen: open failed (%s)\n", strerror(errno)));
1987 if (fstat(tdb->fd, &st) != 0) {
1988 TDB_LOG((tdb, 0, "tdb_reopen: fstat failed (%s)\n", strerror(errno)));
1991 if (st.st_ino != tdb->inode || st.st_dev != tdb->device) {
1992 TDB_LOG((tdb, 0, "tdb_reopen: file dev/inode has changed!\n"));
1996 if ((tdb->flags & TDB_CLEAR_IF_FIRST) && (tdb_brlock(tdb, ACTIVE_LOCK, F_RDLCK, F_SETLKW, 0) == -1)) {
1997 TDB_LOG((tdb, 0, "tdb_reopen: failed to obtain active lock\n"));
2008 /* reopen all tdb's */
2009 int tdb_reopen_all(void)
2013 for (tdb=tdbs; tdb; tdb = tdb->next) {
2014 /* Ensure no clear-if-first. */
2015 tdb->flags &= ~TDB_CLEAR_IF_FIRST;
2016 if (tdb_reopen(tdb) != 0)