tdb: Add tdb_traverse_chain
authorVolker Lendecke <vl@samba.org>
Sun, 28 Oct 2018 08:06:39 +0000 (09:06 +0100)
committerJeremy Allison <jra@samba.org>
Tue, 6 Nov 2018 17:57:25 +0000 (18:57 +0100)
This is a lightweight readonly traverse of a single chain, see the
comment in the header file.

Signed-off-by: Volker Lendecke <vl@samba.org>
Reviewed-by: Jeremy Allison <jra@samba.org>
lib/tdb/common/traverse.c
lib/tdb/include/tdb.h

index a9af1d4..54a69dc 100644 (file)
@@ -399,3 +399,113 @@ _PUBLIC_ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey)
        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->methods->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;
+}
index 535f07a..445f48c 100644 (file)
@@ -480,6 +480,73 @@ int tdb_traverse(struct tdb_context *tdb, tdb_traverse_func fn, void *private_da
  */
 int tdb_traverse_read(struct tdb_context *tdb, tdb_traverse_func fn, void *private_data);
 
+/**
+ * @brief Traverse a single hash chain
+ *
+ * Traverse a single hash chain under a single lock operation. No
+ * database modification is possible in the callback.
+ *
+ * This exists for background cleanup of databases. In normal
+ * operations, traversing a complete database can be much too
+ * expensive. Databases can have many chains, which will all have to
+ * be looked at before tdb_traverse finishes. Also tdb_traverse does a
+ * lot of fcntl activity to protect against concurrent record deletes.
+ *
+ * With this you can walk a fraction of the whole tdb, collect the
+ * entries you want to prune, leave the traverse, and then modify or
+ * delete the records in a subsequent step.
+ *
+ * To walk the entire database, call this function tdb_hash_size()
+ * times, with 0<=chain<tdb_hash_size(tdb).
+ *
+ * @param[in]  tdb      The database to traverse.
+ *
+ * @param[in]  chain    The hash chain number to traverse.
+ *
+ * @param[in]  fn       The function to call on each entry.
+ *
+ * @param[in]  private_data The private data which should be passed to the
+ *                          traversing function.
+ *
+ * @return              The record count traversed, -1 on error.
+ */
+
+int tdb_traverse_chain(struct tdb_context *tdb,
+                      unsigned chain,
+                      tdb_traverse_func fn,
+                      void *private_data);
+
+/**
+ * @brief Traverse a single hash chain
+ *
+ * This is like tdb_traverse_chain(), but for all records that are in
+ * the same chain as the record corresponding to the key parameter.
+ *
+ * Use it for ongoing database maintenance under a lock. Whenever you
+ * are about to modify a database, you know which record you are going
+ * to write to. For that tdb_store(), an exclusive chainlock is taken
+ * behind the scenes. To utilize this exclusive lock for incremental
+ * database cleanup as well, tdb_chainlock() the key you are about to
+ * modify, then tdb_traverse_key_chain() to do the incremental
+ * maintenance, modify your record and tdb_chainunlock() the key
+ * again.
+ *
+ * @param[in]  tdb      The database to traverse.
+ *
+ * @param[in]  key      The record key to walk the chain for.
+ *
+ * @param[in]  fn       The function to call on each entry.
+ *
+ * @param[in]  private_data The private data which should be passed to the
+ *                          traversing function.
+ *
+ * @return              The record count traversed, -1 on error.
+ */
+
+int tdb_traverse_key_chain(struct tdb_context *tdb,
+                          TDB_DATA key,
+                          tdb_traverse_func fn,
+                          void *private_data);
 /**
  * @brief Check if an entry in the database exists.
  *