summaryrefslogtreecommitdiffstats
path: root/common/traverse.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--common/traverse.c510
1 files changed, 510 insertions, 0 deletions
diff --git a/common/traverse.c b/common/traverse.c
new file mode 100644
index 0000000..fcd2e00
--- /dev/null
+++ b/common/traverse.c
@@ -0,0 +1,510 @@
+ /*
+ Unix SMB/CIFS implementation.
+
+ trivial database library
+
+ Copyright (C) Andrew Tridgell 1999-2005
+ Copyright (C) Paul `Rusty' Russell 2000
+ Copyright (C) Jeremy Allison 2000-2003
+
+ ** NOTE! The following LGPL license applies to the tdb
+ ** library. This does NOT imply that all of Samba is released
+ ** under the LGPL
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 3 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "tdb_private.h"
+
+#define TDB_NEXT_LOCK_ERR ((tdb_off_t)-1)
+
+/* Uses traverse lock: 0 = finish, TDB_NEXT_LOCK_ERR = error,
+ other = record offset */
+static tdb_off_t tdb_next_lock(struct tdb_context *tdb, struct tdb_traverse_lock *tlock,
+ struct tdb_record *rec)
+{
+ int want_next = (tlock->off != 0);
+
+ /* Lock each chain from the start one. */
+ for (; tlock->list < tdb->hash_size; tlock->list++) {
+ if (!tlock->off && tlock->list != 0) {
+ /* this is an optimisation for the common case where
+ the hash chain is empty, which is particularly
+ common for the use of tdb with ldb, where large
+ hashes are used. In that case we spend most of our
+ time in tdb_brlock(), locking empty hash chains.
+
+ To avoid this, we do an unlocked pre-check to see
+ if the hash chain is empty before starting to look
+ inside it. If it is empty then we can avoid that
+ hash chain. If it isn't empty then we can't believe
+ the value we get back, as we read it without a
+ lock, so instead we get the lock and re-fetch the
+ value below.
+
+ Notice that not doing this optimisation on the
+ first hash chain is critical. We must guarantee
+ that we have done at least one fcntl lock at the
+ start of a search to guarantee that memory is
+ coherent on SMP systems. If records are added by
+ others during the search then that's OK, and we
+ could possibly miss those with this trick, but we
+ could miss them anyway without this trick, so the
+ semantics don't change.
+
+ With a non-indexed ldb search this trick gains us a
+ factor of around 80 in speed on a linux 2.6.x
+ system (testing using ldbtest).
+ */
+ tdb->methods->next_hash_chain(tdb, &tlock->list);
+ if (tlock->list == tdb->hash_size) {
+ continue;
+ }
+ }
+
+ if (tdb_lock(tdb, tlock->list, tlock->lock_rw) == -1)
+ return TDB_NEXT_LOCK_ERR;
+
+ /* No previous record? Start at top of chain. */
+ if (!tlock->off) {
+ if (tdb_ofs_read(tdb, TDB_HASH_TOP(tlock->list),
+ &tlock->off) == -1)
+ goto fail;
+ } else {
+ /* Otherwise unlock the previous record. */
+ if (tdb_unlock_record(tdb, tlock->off) != 0)
+ goto fail;
+ }
+
+ if (want_next) {
+ /* We have offset of old record: grab next */
+ if (tdb_rec_read(tdb, tlock->off, rec) == -1)
+ goto fail;
+ tlock->off = rec->next;
+ }
+
+ /* Iterate through chain */
+ while( tlock->off) {
+ if (tdb_rec_read(tdb, tlock->off, rec) == -1)
+ goto fail;
+
+ /* Detect infinite loops. From "Shlomi Yaakobovich" <Shlomi@exanet.com>. */
+ if (tlock->off == rec->next) {
+ tdb->ecode = TDB_ERR_CORRUPT;
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_next_lock: loop detected.\n"));
+ goto fail;
+ }
+
+ if (!TDB_DEAD(rec)) {
+ /* Woohoo: we found one! */
+ if (tdb_lock_record(tdb, tlock->off) != 0)
+ goto fail;
+ return tlock->off;
+ }
+
+ tlock->off = rec->next;
+ }
+ tdb_unlock(tdb, tlock->list, tlock->lock_rw);
+ want_next = 0;
+ }
+ /* We finished iteration without finding anything */
+ tdb->ecode = TDB_SUCCESS;
+ return 0;
+
+ fail:
+ tlock->off = 0;
+ if (tdb_unlock(tdb, tlock->list, tlock->lock_rw) != 0)
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_next_lock: On error unlock failed!\n"));
+ return TDB_NEXT_LOCK_ERR;
+}
+
+/* traverse the entire database - calling fn(tdb, key, data) on each element.
+ return -1 on error or the record count traversed
+ if fn is NULL then it is not called
+ a non-zero return value from fn() indicates that the traversal should stop
+ */
+static int tdb_traverse_internal(struct tdb_context *tdb,
+ tdb_traverse_func fn, void *private_data,
+ struct tdb_traverse_lock *tl)
+{
+ TDB_DATA key, dbuf;
+ struct tdb_record rec;
+ int ret = 0, count = 0;
+ tdb_off_t off;
+ size_t recbuf_len;
+
+ recbuf_len = 4096;
+ key.dptr = malloc(recbuf_len);
+ if (key.dptr == NULL) {
+ return -1;
+ }
+
+ /* This was in the initialization, above, but the IRIX compiler
+ * did not like it. crh
+ */
+ tl->next = tdb->travlocks.next;
+
+ /* fcntl locks don't stack: beware traverse inside traverse */
+ tdb->travlocks.next = tl;
+
+ /* tdb_next_lock places locks on the record returned, and its chain */
+ while ((off = tdb_next_lock(tdb, tl, &rec)) != 0) {
+ tdb_len_t full_len;
+ int nread;
+
+ if (off == TDB_NEXT_LOCK_ERR) {
+ ret = -1;
+ goto out;
+ }
+
+ full_len = rec.key_len + rec.data_len;
+
+ if (full_len > recbuf_len) {
+ recbuf_len = full_len;
+
+ /*
+ * No realloc, we don't need the old data and thus can
+ * do without the memcpy
+ */
+ free(key.dptr);
+ key.dptr = malloc(recbuf_len);
+
+ if (key.dptr == NULL) {
+ ret = -1;
+ if (tdb_unlock(tdb, tl->list, tl->lock_rw)
+ != 0) {
+ goto out;
+ }
+ if (tdb_unlock_record(tdb, tl->off) != 0) {
+ TDB_LOG((tdb, TDB_DEBUG_FATAL,
+ "tdb_traverse: malloc "
+ "failed and unlock_record "
+ "failed!\n"));
+ }
+ goto out;
+ }
+ }
+
+ count++;
+ /* now read the full record */
+ nread = tdb->methods->tdb_read(tdb, tl->off + sizeof(rec),
+ key.dptr, full_len, 0);
+ if (nread == -1) {
+ ret = -1;
+ if (tdb_unlock(tdb, tl->list, tl->lock_rw) != 0)
+ goto out;
+ if (tdb_unlock_record(tdb, tl->off) != 0)
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_traverse: key.dptr == NULL and unlock_record failed!\n"));
+ goto out;
+ }
+ key.dsize = rec.key_len;
+ dbuf.dptr = key.dptr + rec.key_len;
+ dbuf.dsize = rec.data_len;
+
+ tdb_trace_1rec_retrec(tdb, "traverse", key, dbuf);
+
+ /* Drop chain lock, call out */
+ if (tdb_unlock(tdb, tl->list, tl->lock_rw) != 0) {
+ ret = -1;
+ goto out;
+ }
+ if (fn && fn(tdb, key, dbuf, private_data)) {
+ /* They want us to terminate traversal */
+ tdb_trace_ret(tdb, "tdb_traverse_end", count);
+ if (tdb_unlock_record(tdb, tl->off) != 0) {
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_traverse: unlock_record failed!\n"));;
+ ret = -1;
+ }
+ goto out;
+ }
+ }
+ tdb_trace(tdb, "tdb_traverse_end");
+out:
+ SAFE_FREE(key.dptr);
+ tdb->travlocks.next = tl->next;
+ if (ret < 0)
+ return -1;
+ else
+ return count;
+}
+
+
+/*
+ a read style traverse - temporarily marks each record read only
+*/
+_PUBLIC_ int tdb_traverse_read(struct tdb_context *tdb,
+ tdb_traverse_func fn, void *private_data)
+{
+ struct tdb_traverse_lock tl = { NULL, 0, 0, F_RDLCK };
+ int ret;
+
+ tdb->traverse_read++;
+ tdb_trace(tdb, "tdb_traverse_read_start");
+ ret = tdb_traverse_internal(tdb, fn, private_data, &tl);
+ tdb->traverse_read--;
+
+ return ret;
+}
+
+/*
+ a write style traverse - needs to get the transaction lock to
+ prevent deadlocks
+
+ WARNING: The data buffer given to the callback fn does NOT meet the
+ alignment guarantees malloc gives you.
+*/
+_PUBLIC_ int tdb_traverse(struct tdb_context *tdb,
+ tdb_traverse_func fn, void *private_data)
+{
+ struct tdb_traverse_lock tl = { NULL, 0, 0, F_WRLCK };
+ enum tdb_lock_flags lock_flags;
+ int ret;
+
+ if (tdb->read_only || tdb->traverse_read) {
+ return tdb_traverse_read(tdb, fn, private_data);
+ }
+
+ lock_flags = TDB_LOCK_WAIT;
+
+ if (tdb->allrecord_lock.count != 0) {
+ /*
+ * This avoids a deadlock between tdb_lockall() and
+ * tdb_traverse(). See
+ * https://bugzilla.samba.org/show_bug.cgi?id=11381
+ */
+ lock_flags = TDB_LOCK_NOWAIT;
+ }
+
+ if (tdb_transaction_lock(tdb, F_WRLCK, lock_flags)) {
+ return -1;
+ }
+
+ tdb->traverse_write++;
+ tdb_trace(tdb, "tdb_traverse_start");
+ ret = tdb_traverse_internal(tdb, fn, private_data, &tl);
+ tdb->traverse_write--;
+
+ tdb_transaction_unlock(tdb, F_WRLCK);
+
+ return ret;
+}
+
+
+/* find the first entry in the database and return its key */
+_PUBLIC_ TDB_DATA tdb_firstkey(struct tdb_context *tdb)
+{
+ TDB_DATA key;
+ struct tdb_record rec;
+ tdb_off_t off;
+
+ /* release any old lock */
+ if (tdb_unlock_record(tdb, tdb->travlocks.off) != 0)
+ return tdb_null;
+ tdb->travlocks.off = tdb->travlocks.list = 0;
+ tdb->travlocks.lock_rw = F_RDLCK;
+
+ /* Grab first record: locks chain and returned record. */
+ off = tdb_next_lock(tdb, &tdb->travlocks, &rec);
+ if (off == 0 || off == TDB_NEXT_LOCK_ERR) {
+ tdb_trace_retrec(tdb, "tdb_firstkey", tdb_null);
+ return tdb_null;
+ }
+ /* now read the key */
+ key.dsize = rec.key_len;
+ key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize);
+
+ tdb_trace_retrec(tdb, "tdb_firstkey", key);
+
+ /* Unlock the hash chain of the record we just read. */
+ if (tdb_unlock(tdb, tdb->travlocks.list, tdb->travlocks.lock_rw) != 0)
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_firstkey: error occurred while tdb_unlocking!\n"));
+ return key;
+}
+
+/* find the next entry in the database, returning its key */
+_PUBLIC_ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey)
+{
+ uint32_t oldlist;
+ TDB_DATA key = tdb_null;
+ struct tdb_record rec;
+ unsigned char *k = NULL;
+ tdb_off_t off;
+
+ /* Is locked key the old key? If so, traverse will be reliable. */
+ if (tdb->travlocks.off) {
+ if (tdb_lock(tdb,tdb->travlocks.list,tdb->travlocks.lock_rw))
+ return tdb_null;
+ if (tdb_rec_read(tdb, tdb->travlocks.off, &rec) == -1
+ || !(k = tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),
+ rec.key_len))
+ || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) {
+ /* No, it wasn't: unlock it and start from scratch */
+ if (tdb_unlock_record(tdb, tdb->travlocks.off) != 0) {
+ tdb_trace_1rec_retrec(tdb, "tdb_nextkey",
+ oldkey, tdb_null);
+ SAFE_FREE(k);
+ return tdb_null;
+ }
+ if (tdb_unlock(tdb, tdb->travlocks.list, tdb->travlocks.lock_rw) != 0) {
+ SAFE_FREE(k);
+ return tdb_null;
+ }
+ tdb->travlocks.off = 0;
+ }
+
+ SAFE_FREE(k);
+ }
+
+ if (!tdb->travlocks.off) {
+ /* No previous element: do normal find, and lock record */
+ tdb->travlocks.off = tdb_find_lock_hash(tdb, oldkey, tdb->hash_fn(&oldkey), tdb->travlocks.lock_rw, &rec);
+ if (!tdb->travlocks.off) {
+ tdb_trace_1rec_retrec(tdb, "tdb_nextkey", oldkey, tdb_null);
+ return tdb_null;
+ }
+ tdb->travlocks.list = BUCKET(rec.full_hash);
+ if (tdb_lock_record(tdb, tdb->travlocks.off) != 0) {
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: lock_record failed (%s)!\n", strerror(errno)));
+ return tdb_null;
+ }
+ }
+ oldlist = tdb->travlocks.list;
+
+ /* Grab next record: locks chain and returned record,
+ unlocks old record */
+ off = tdb_next_lock(tdb, &tdb->travlocks, &rec);
+ if (off != TDB_NEXT_LOCK_ERR && off != 0) {
+ key.dsize = rec.key_len;
+ key.dptr = tdb_alloc_read(tdb, tdb->travlocks.off+sizeof(rec),
+ key.dsize);
+ /* Unlock the chain of this new record */
+ if (tdb_unlock(tdb, tdb->travlocks.list, tdb->travlocks.lock_rw) != 0)
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
+ }
+ /* Unlock the chain of old record */
+ if (tdb_unlock(tdb, oldlist, tdb->travlocks.lock_rw) != 0)
+ TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
+ tdb_trace_1rec_retrec(tdb, "tdb_nextkey", oldkey, key);
+ return key;
+}
+
+_PUBLIC_ int tdb_traverse_chain(struct tdb_context *tdb,
+ unsigned chain,
+ tdb_traverse_func fn,
+ void *private_data)
+{
+ tdb_off_t rec_ptr;
+ struct tdb_chainwalk_ctx chainwalk;
+ int count = 0;
+ int ret;
+
+ if (chain >= tdb->hash_size) {
+ tdb->ecode = TDB_ERR_EINVAL;
+ return -1;
+ }
+
+ if (tdb->traverse_read != 0) {
+ tdb->ecode = TDB_ERR_LOCK;
+ return -1;
+ }
+
+ ret = tdb_lock(tdb, chain, F_RDLCK);
+ if (ret == -1) {
+ return -1;
+ }
+
+ tdb->traverse_read += 1;
+
+ ret = tdb_ofs_read(tdb, TDB_HASH_TOP(chain), &rec_ptr);
+ if (ret == -1) {
+ goto fail;
+ }
+
+ tdb_chainwalk_init(&chainwalk, rec_ptr);
+
+ while (rec_ptr != 0) {
+ struct tdb_record rec;
+ bool ok;
+
+ ret = tdb_rec_read(tdb, rec_ptr, &rec);
+ if (ret == -1) {
+ goto fail;
+ }
+
+ if (!TDB_DEAD(&rec)) {
+ /* no overflow checks, tdb_rec_read checked it */
+ tdb_off_t key_ofs = rec_ptr + sizeof(rec);
+ size_t full_len = rec.key_len + rec.data_len;
+ uint8_t *buf = NULL;
+
+ TDB_DATA key = { .dsize = rec.key_len };
+ TDB_DATA data = { .dsize = rec.data_len };
+
+ if ((tdb->transaction == NULL) &&
+ (tdb->map_ptr != NULL)) {
+ ret = tdb_oob(tdb, key_ofs, full_len, 0);
+ if (ret == -1) {
+ goto fail;
+ }
+ key.dptr = (uint8_t *)tdb->map_ptr + key_ofs;
+ } else {
+ buf = tdb_alloc_read(tdb, key_ofs, full_len);
+ if (buf == NULL) {
+ goto fail;
+ }
+ key.dptr = buf;
+ }
+ data.dptr = key.dptr + key.dsize;
+
+ ret = fn(tdb, key, data, private_data);
+ free(buf);
+
+ count += 1;
+
+ if (ret != 0) {
+ break;
+ }
+ }
+
+ rec_ptr = rec.next;
+
+ ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
+ if (!ok) {
+ goto fail;
+ }
+ }
+ tdb->traverse_read -= 1;
+ tdb_unlock(tdb, chain, F_RDLCK);
+ return count;
+
+fail:
+ tdb->traverse_read -= 1;
+ tdb_unlock(tdb, chain, F_RDLCK);
+ return -1;
+}
+
+_PUBLIC_ int tdb_traverse_key_chain(struct tdb_context *tdb,
+ TDB_DATA key,
+ tdb_traverse_func fn,
+ void *private_data)
+{
+ uint32_t hash, chain;
+ int ret;
+
+ hash = tdb->hash_fn(&key);
+ chain = BUCKET(hash);
+ ret = tdb_traverse_chain(tdb, chain, fn, private_data);
+
+ return ret;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-31 02:29:53 +0000