2 Unix SMB/CIFS implementation.
4 trivial database library
6 Copyright (C) Andrew Tridgell 1999-2005
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 3 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, see <http://www.gnu.org/licenses/>.
28 #include "tdb_private.h"
33 non-blocking increment of the tdb sequence number if the tdb has been opened using
36 void tdb_increment_seqnum_nonblock(struct tdb_context *tdb)
40 if (!(tdb->flags & TDB_SEQNUM)) {
44 /* we ignore errors from this, as we have no sane way of
47 tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum);
49 tdb_ofs_write(tdb, TDB_SEQNUM_OFS, &seqnum);
53 increment the tdb sequence number if the tdb has been opened using
56 static void tdb_increment_seqnum(struct tdb_context *tdb)
58 if (!(tdb->flags & TDB_SEQNUM)) {
62 if (tdb_brlock(tdb, TDB_SEQNUM_OFS, F_WRLCK, F_SETLKW, 1, 1) != 0) {
66 tdb_increment_seqnum_nonblock(tdb);
68 tdb_brlock(tdb, TDB_SEQNUM_OFS, F_UNLCK, F_SETLKW, 1, 1);
71 static int tdb_key_compare(TDB_DATA key, TDB_DATA data, void *private_data)
73 return memcmp(data.dptr, key.dptr, data.dsize);
76 /* Returns 0 on fail. On success, return offset of record, and fills
78 static tdb_off_t tdb_find(struct tdb_context *tdb, TDB_DATA key, u32 hash,
79 struct list_struct *r)
83 /* read in the hash top */
84 if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
87 /* keep looking until we find the right record */
89 if (tdb_rec_read(tdb, rec_ptr, r) == -1)
92 if (!TDB_DEAD(r) && hash==r->full_hash
93 && key.dsize==r->key_len
94 && tdb_parse_data(tdb, key, rec_ptr + sizeof(*r),
95 r->key_len, tdb_key_compare,
101 return TDB_ERRCODE(TDB_ERR_NOEXIST, 0);
104 /* As tdb_find, but if you succeed, keep the lock */
105 tdb_off_t tdb_find_lock_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash, int locktype,
106 struct list_struct *rec)
110 if (tdb_lock(tdb, BUCKET(hash), locktype) == -1)
112 if (!(rec_ptr = tdb_find(tdb, key, hash, rec)))
113 tdb_unlock(tdb, BUCKET(hash), locktype);
118 /* update an entry in place - this only works if the new data size
119 is <= the old data size and the key exists.
120 on failure return -1.
122 static int tdb_update_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash, TDB_DATA dbuf)
124 struct list_struct rec;
128 if (!(rec_ptr = tdb_find(tdb, key, hash, &rec)))
131 /* must be long enough key, data and tailer */
132 if (rec.rec_len < key.dsize + dbuf.dsize + sizeof(tdb_off_t)) {
133 tdb->ecode = TDB_SUCCESS; /* Not really an error */
137 if (tdb->methods->tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
138 dbuf.dptr, dbuf.dsize) == -1)
141 if (dbuf.dsize != rec.data_len) {
143 rec.data_len = dbuf.dsize;
144 return tdb_rec_write(tdb, rec_ptr, &rec);
150 /* find an entry in the database given a key */
151 /* If an entry doesn't exist tdb_err will be set to
152 * TDB_ERR_NOEXIST. If a key has no data attached
153 * then the TDB_DATA will have zero length but
156 TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key)
159 struct list_struct rec;
163 /* find which hash bucket it is in */
164 hash = tdb->hash_fn(&key);
165 if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec)))
168 ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec) + rec.key_len,
170 ret.dsize = rec.data_len;
171 tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
176 * Find an entry in the database and hand the record's data to a parsing
177 * function. The parsing function is executed under the chain read lock, so it
178 * should be fast and should not block on other syscalls.
180 * DONT CALL OTHER TDB CALLS FROM THE PARSER, THIS MIGHT LEAD TO SEGFAULTS.
182 * For mmapped tdb's that do not have a transaction open it points the parsing
183 * function directly at the mmap area, it avoids the malloc/memcpy in this
184 * case. If a transaction is open or no mmap is available, it has to do
185 * malloc/read/parse/free.
187 * This is interesting for all readers of potentially large data structures in
188 * the tdb records, ldb indexes being one example.
191 int tdb_parse_record(struct tdb_context *tdb, TDB_DATA key,
192 int (*parser)(TDB_DATA key, TDB_DATA data,
197 struct list_struct rec;
201 /* find which hash bucket it is in */
202 hash = tdb->hash_fn(&key);
204 if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec))) {
205 return TDB_ERRCODE(TDB_ERR_NOEXIST, 0);
208 ret = tdb_parse_data(tdb, key, rec_ptr + sizeof(rec) + rec.key_len,
209 rec.data_len, parser, private_data);
211 tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
216 /* check if an entry in the database exists
218 note that 1 is returned if the key is found and 0 is returned if not found
219 this doesn't match the conventions in the rest of this module, but is
222 static int tdb_exists_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash)
224 struct list_struct rec;
226 if (tdb_find_lock_hash(tdb, key, hash, F_RDLCK, &rec) == 0)
228 tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
232 int tdb_exists(struct tdb_context *tdb, TDB_DATA key)
234 u32 hash = tdb->hash_fn(&key);
235 return tdb_exists_hash(tdb, key, hash);
238 /* actually delete an entry in the database given the offset */
239 int tdb_do_delete(struct tdb_context *tdb, tdb_off_t rec_ptr, struct list_struct*rec)
241 tdb_off_t last_ptr, i;
242 struct list_struct lastrec;
244 if (tdb->read_only || tdb->traverse_read) return -1;
246 if (tdb_write_lock_record(tdb, rec_ptr) == -1) {
247 /* Someone traversing here: mark it as dead */
248 rec->magic = TDB_DEAD_MAGIC;
249 return tdb_rec_write(tdb, rec_ptr, rec);
251 if (tdb_write_unlock_record(tdb, rec_ptr) != 0)
254 /* find previous record in hash chain */
255 if (tdb_ofs_read(tdb, TDB_HASH_TOP(rec->full_hash), &i) == -1)
257 for (last_ptr = 0; i != rec_ptr; last_ptr = i, i = lastrec.next)
258 if (tdb_rec_read(tdb, i, &lastrec) == -1)
261 /* unlink it: next ptr is at start of record. */
263 last_ptr = TDB_HASH_TOP(rec->full_hash);
264 if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1)
267 /* recover the space */
268 if (tdb_free(tdb, rec_ptr, rec) == -1)
273 static int tdb_count_dead(struct tdb_context *tdb, u32 hash)
277 struct list_struct rec;
279 /* read in the hash top */
280 if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
284 if (tdb_rec_read(tdb, rec_ptr, &rec) == -1)
287 if (rec.magic == TDB_DEAD_MAGIC) {
296 * Purge all DEAD records from a hash chain
298 static int tdb_purge_dead(struct tdb_context *tdb, u32 hash)
301 struct list_struct rec;
304 if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
308 /* read in the hash top */
309 if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
315 if (tdb_rec_read(tdb, rec_ptr, &rec) == -1) {
321 if (rec.magic == TDB_DEAD_MAGIC
322 && tdb_do_delete(tdb, rec_ptr, &rec) == -1) {
329 tdb_unlock(tdb, -1, F_WRLCK);
333 /* delete an entry in the database given a key */
334 static int tdb_delete_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash)
337 struct list_struct rec;
340 if (tdb->max_dead_records != 0) {
343 * Allow for some dead records per hash chain, mainly for
344 * tdb's with a very high create/delete rate like locking.tdb.
347 if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
350 if (tdb_count_dead(tdb, hash) >= tdb->max_dead_records) {
352 * Don't let the per-chain freelist grow too large,
353 * delete all existing dead records
355 tdb_purge_dead(tdb, hash);
358 if (!(rec_ptr = tdb_find(tdb, key, hash, &rec))) {
359 tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
364 * Just mark the record as dead.
366 rec.magic = TDB_DEAD_MAGIC;
367 ret = tdb_rec_write(tdb, rec_ptr, &rec);
370 if (!(rec_ptr = tdb_find_lock_hash(tdb, key, hash, F_WRLCK,
374 ret = tdb_do_delete(tdb, rec_ptr, &rec);
378 tdb_increment_seqnum(tdb);
381 if (tdb_unlock(tdb, BUCKET(rec.full_hash), F_WRLCK) != 0)
382 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_delete: WARNING tdb_unlock failed!\n"));
386 int tdb_delete(struct tdb_context *tdb, TDB_DATA key)
388 u32 hash = tdb->hash_fn(&key);
389 return tdb_delete_hash(tdb, key, hash);
393 * See if we have a dead record around with enough space
395 static tdb_off_t tdb_find_dead(struct tdb_context *tdb, u32 hash,
396 struct list_struct *r, tdb_len_t length)
400 /* read in the hash top */
401 if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
404 /* keep looking until we find the right record */
406 if (tdb_rec_read(tdb, rec_ptr, r) == -1)
409 if (TDB_DEAD(r) && r->rec_len >= length) {
411 * First fit for simple coding, TODO: change to best
421 /* store an element in the database, replacing any existing element
424 return 0 on success, -1 on failure
426 int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
428 struct list_struct rec;
434 if (tdb->read_only || tdb->traverse_read) {
435 tdb->ecode = TDB_ERR_RDONLY;
439 /* find which hash bucket it is in */
440 hash = tdb->hash_fn(&key);
441 if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
444 /* check for it existing, on insert. */
445 if (flag == TDB_INSERT) {
446 if (tdb_exists_hash(tdb, key, hash)) {
447 tdb->ecode = TDB_ERR_EXISTS;
451 /* first try in-place update, on modify or replace. */
452 if (tdb_update_hash(tdb, key, hash, dbuf) == 0) {
455 if (tdb->ecode == TDB_ERR_NOEXIST &&
456 flag == TDB_MODIFY) {
457 /* if the record doesn't exist and we are in TDB_MODIFY mode then
458 we should fail the store */
462 /* reset the error code potentially set by the tdb_update() */
463 tdb->ecode = TDB_SUCCESS;
465 /* delete any existing record - if it doesn't exist we don't
466 care. Doing this first reduces fragmentation, and avoids
467 coalescing with `allocated' block before it's updated. */
468 if (flag != TDB_INSERT)
469 tdb_delete_hash(tdb, key, hash);
471 /* Copy key+value *before* allocating free space in case malloc
472 fails and we are left with a dead spot in the tdb. */
474 if (!(p = (char *)malloc(key.dsize + dbuf.dsize))) {
475 tdb->ecode = TDB_ERR_OOM;
479 memcpy(p, key.dptr, key.dsize);
481 memcpy(p+key.dsize, dbuf.dptr, dbuf.dsize);
483 if (tdb->max_dead_records != 0) {
485 * Allow for some dead records per hash chain, look if we can
486 * find one that can hold the new record. We need enough space
487 * for key, data and tailer. If we find one, we don't have to
488 * consult the central freelist.
490 rec_ptr = tdb_find_dead(
492 key.dsize + dbuf.dsize + sizeof(tdb_off_t));
495 rec.key_len = key.dsize;
496 rec.data_len = dbuf.dsize;
497 rec.full_hash = hash;
498 rec.magic = TDB_MAGIC;
499 if (tdb_rec_write(tdb, rec_ptr, &rec) == -1
500 || tdb->methods->tdb_write(
501 tdb, rec_ptr + sizeof(rec),
502 p, key.dsize + dbuf.dsize) == -1) {
510 * We have to allocate some space from the freelist, so this means we
511 * have to lock it. Use the chance to purge all the DEAD records from
512 * the hash chain under the freelist lock.
515 if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
519 if ((tdb->max_dead_records != 0)
520 && (tdb_purge_dead(tdb, hash) == -1)) {
521 tdb_unlock(tdb, -1, F_WRLCK);
525 /* we have to allocate some space */
526 rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize, &rec);
528 tdb_unlock(tdb, -1, F_WRLCK);
534 /* Read hash top into next ptr */
535 if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
538 rec.key_len = key.dsize;
539 rec.data_len = dbuf.dsize;
540 rec.full_hash = hash;
541 rec.magic = TDB_MAGIC;
543 /* write out and point the top of the hash chain at it */
544 if (tdb_rec_write(tdb, rec_ptr, &rec) == -1
545 || tdb->methods->tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+dbuf.dsize)==-1
546 || tdb_ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
547 /* Need to tdb_unallocate() here */
555 tdb_increment_seqnum(tdb);
559 tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
564 /* Append to an entry. Create if not exist. */
565 int tdb_append(struct tdb_context *tdb, TDB_DATA key, TDB_DATA new_dbuf)
571 /* find which hash bucket it is in */
572 hash = tdb->hash_fn(&key);
573 if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
576 dbuf = tdb_fetch(tdb, key);
578 if (dbuf.dptr == NULL) {
579 dbuf.dptr = (unsigned char *)malloc(new_dbuf.dsize);
581 dbuf.dptr = (unsigned char *)realloc(dbuf.dptr,
582 dbuf.dsize + new_dbuf.dsize);
585 if (dbuf.dptr == NULL) {
586 tdb->ecode = TDB_ERR_OOM;
590 memcpy(dbuf.dptr + dbuf.dsize, new_dbuf.dptr, new_dbuf.dsize);
591 dbuf.dsize += new_dbuf.dsize;
593 ret = tdb_store(tdb, key, dbuf, 0);
596 tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
597 SAFE_FREE(dbuf.dptr);
603 return the name of the current tdb file
604 useful for external logging functions
606 const char *tdb_name(struct tdb_context *tdb)
612 return the underlying file descriptor being used by tdb, or -1
613 useful for external routines that want to check the device/inode
616 int tdb_fd(struct tdb_context *tdb)
622 return the current logging function
623 useful for external tdb routines that wish to log tdb errors
625 tdb_log_func tdb_log_fn(struct tdb_context *tdb)
627 return tdb->log.log_fn;
632 get the tdb sequence number. Only makes sense if the writers opened
633 with TDB_SEQNUM set. Note that this sequence number will wrap quite
634 quickly, so it should only be used for a 'has something changed'
635 test, not for code that relies on the count of the number of changes
636 made. If you want a counter then use a tdb record.
638 The aim of this sequence number is to allow for a very lightweight
639 test of a possible tdb change.
641 int tdb_get_seqnum(struct tdb_context *tdb)
645 tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum);
649 int tdb_hash_size(struct tdb_context *tdb)
651 return tdb->header.hash_size;
654 size_t tdb_map_size(struct tdb_context *tdb)
656 return tdb->map_size;
659 int tdb_get_flags(struct tdb_context *tdb)
666 enable sequence number handling on an open tdb
668 void tdb_enable_seqnum(struct tdb_context *tdb)
670 tdb->flags |= TDB_SEQNUM;