[SCM] Samba Shared Repository - branch master updated

Stefan Metzmacher metze at samba.org
Fri Nov 27 12:18:05 UTC 2015


The branch, master has been updated
       via  bb9f13a s3:torture: add traverse testing to LOCAL-RBTREE
       via  0f46da0 dbwrap_rbt: fix modifying the db during traverse
       via  5905079 dbwrap_rbt: add nested traverse protection
       via  f3d1fc1 dbwrap_rbt: use talloc_zero_size() instead of a partial ZERO_STRUCT()
      from  257ec9c docs: Fix some typos in the idmap backend section.

https://git.samba.org/?p=samba.git;a=shortlog;h=master


- Log -----------------------------------------------------------------
commit bb9f13ab4165f150e01a88ddcc51605a7c176f5d
Author: Stefan Metzmacher <metze at samba.org>
Date:   Wed Nov 25 00:13:17 2015 +0100

    s3:torture: add traverse testing to LOCAL-RBTREE
    
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11375
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11394
    
    Signed-off-by: Stefan Metzmacher <metze at samba.org>
    Reviewed-by: Volker Lendecke <vl at samba.org>
    
    Autobuild-User(master): Stefan Metzmacher <metze at samba.org>
    Autobuild-Date(master): Fri Nov 27 13:16:59 CET 2015 on sn-devel-104

commit 0f46da08e160e6712e5282af14e1ec4012614fc7
Author: Stefan Metzmacher <metze at samba.org>
Date:   Wed Nov 25 09:22:08 2015 +0100

    dbwrap_rbt: fix modifying the db during traverse
    
    We delete and add of records rebalace the tree, but our
    traverse code doesn't handle that and skips records
    randomly.
    
    We maintain records in a linked list for now
    in addition to the rbtree and use that list during
    traverse.
    
    This add a bit overhead, but at least it works reliable.
    If someone finds a way to do reliable traverse with the
    rebalanced tree, we can replace this commit.
    
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11375
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11394
    
    Signed-off-by: Stefan Metzmacher <metze at samba.org>
    Reviewed-by: Volker Lendecke <vl at samba.org>

commit 590507951fc514a679f44b8bfdd03c721189c3fa
Author: Stefan Metzmacher <metze at samba.org>
Date:   Wed Nov 25 09:22:08 2015 +0100

    dbwrap_rbt: add nested traverse protection
    
    Multiple dbwrap_traverse_read() calls are possible.
    
    store() and delete() on a fetch locked record
    are rejected during dbwrap_traverse_read().
    
    A dbwrap_traverse() within a dbwrap_traverse_read()
    behaves like a dbwrap_traverse_read().
    
    Nested dbwrap_traverse() calls are not possible.
    
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11375
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11394
    
    Signed-off-by: Stefan Metzmacher <metze at samba.org>
    Reviewed-by: Volker Lendecke <vl at samba.org>

commit f3d1fc1d06822a951a2a3eeb5aa53748b9b5b299
Author: Stefan Metzmacher <metze at samba.org>
Date:   Wed Nov 25 10:17:34 2015 +0100

    dbwrap_rbt: use talloc_zero_size() instead of a partial ZERO_STRUCT()
    
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11375
    BUG: https://bugzilla.samba.org/show_bug.cgi?id=11394
    
    Signed-off-by: Stefan Metzmacher <metze at samba.org>
    Reviewed-by: Volker Lendecke <vl at samba.org>

-----------------------------------------------------------------------

Summary of changes:
 lib/dbwrap/dbwrap_rbt.c   | 159 +++++++++++++++++++++++++---------------------
 source3/torture/torture.c |  39 ++++++++++++
 2 files changed, 127 insertions(+), 71 deletions(-)


Changeset truncated at 500 lines:

diff --git a/lib/dbwrap/dbwrap_rbt.c b/lib/dbwrap/dbwrap_rbt.c
index 0764a2c..3b5e589 100644
--- a/lib/dbwrap/dbwrap_rbt.c
+++ b/lib/dbwrap/dbwrap_rbt.c
@@ -22,11 +22,15 @@
 #include "dbwrap/dbwrap_private.h"
 #include "dbwrap/dbwrap_rbt.h"
 #include "../lib/util/rbtree.h"
+#include "../lib/util/dlinklist.h"
 
 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
 
 struct db_rbt_ctx {
 	struct rb_root tree;
+	struct db_rbt_node *nodes;
+	size_t traverse_read;
+	struct db_rbt_node **traverse_nextp;
 };
 
 struct db_rbt_rec {
@@ -38,6 +42,7 @@ struct db_rbt_rec {
 struct db_rbt_node {
 	struct rb_node rb_node;
 	size_t keysize, valuesize;
+	struct db_rbt_node *prev, *next;
 };
 
 /*
@@ -121,11 +126,16 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 	struct db_rbt_node *node;
 
 	struct rb_node ** p;
-	struct rb_node * parent;
+	struct rb_node *parent = NULL;
+	struct db_rbt_node *parent_node = NULL;
 
 	ssize_t reclen;
 	TDB_DATA this_key, this_val;
 
+	if (db_ctx->traverse_read > 0) {
+		return NT_STATUS_MEDIA_WRITE_PROTECTED;
+	}
+
 	if (rec_priv->node != NULL) {
 
 		/*
@@ -153,18 +163,25 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 		return NT_STATUS_INSUFFICIENT_RESOURCES;
 	}
 
-	node = talloc_size(db_ctx, reclen);
+	node = talloc_zero_size(db_ctx, reclen);
 	if (node == NULL) {
 		return NT_STATUS_NO_MEMORY;
 	}
 
 	if (rec_priv->node != NULL) {
+		if (db_ctx->traverse_nextp != NULL) {
+			if (*db_ctx->traverse_nextp == rec_priv->node) {
+				*db_ctx->traverse_nextp = node;
+			}
+		}
+
 		/*
 		 * We need to delete the key from the tree and start fresh,
 		 * there's not enough space in the existing record
 		 */
 
 		rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
+		DLIST_REMOVE(db_ctx->nodes, rec_priv->node);
 
 		/*
 		 * Keep the existing node around for a while: If the record
@@ -172,8 +189,6 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 		 */
 	}
 
-	ZERO_STRUCT(node->rb_node);
-
 	node->keysize = rec->key.dsize;
 	node->valuesize = data.dsize;
 
@@ -193,10 +208,11 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 		TDB_DATA search_key, search_val;
 		int res;
 
-		parent = (*p);
-
 		r = db_rbt2node(*p);
 
+		parent = (*p);
+		parent_node = r;
+
 		db_rbt_parse_node(r, &search_key, &search_val);
 
 		res = db_rbt_compare(this_key, search_key);
@@ -213,6 +229,7 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 	}
 
 	rb_link_node(&node->rb_node, parent, p);
+	DLIST_ADD_AFTER(db_ctx->nodes, node, parent_node);
 	rb_insert_color(&node->rb_node, &db_ctx->tree);
 
 	return NT_STATUS_OK;
@@ -224,26 +241,27 @@ static NTSTATUS db_rbt_delete(struct db_record *rec)
 		rec->db->private_data, struct db_rbt_ctx);
 	struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
 
+	if (db_ctx->traverse_read > 0) {
+		return NT_STATUS_MEDIA_WRITE_PROTECTED;
+	}
+
 	if (rec_priv->node == NULL) {
 		return NT_STATUS_OK;
 	}
 
+	if (db_ctx->traverse_nextp != NULL) {
+		if (*db_ctx->traverse_nextp == rec_priv->node) {
+			*db_ctx->traverse_nextp = rec_priv->node->next;
+		}
+	}
+
 	rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
+	DLIST_REMOVE(db_ctx->nodes, rec_priv->node);
 	TALLOC_FREE(rec_priv->node);
 
 	return NT_STATUS_OK;
 }
 
-static NTSTATUS db_rbt_store_deny(struct db_record *rec, TDB_DATA data, int flag)
-{
-	return NT_STATUS_MEDIA_WRITE_PROTECTED;
-}
-
-static NTSTATUS db_rbt_delete_deny(struct db_record *rec)
-{
-	return NT_STATUS_MEDIA_WRITE_PROTECTED;
-}
-
 struct db_rbt_search_result {
 	TDB_DATA key;
 	TDB_DATA val;
@@ -385,75 +403,65 @@ static NTSTATUS db_rbt_parse_record(struct db_context *db, TDB_DATA key,
 }
 
 static int db_rbt_traverse_internal(struct db_context *db,
-				    struct rb_node *n,
 				    int (*f)(struct db_record *db,
 					     void *private_data),
 				    void *private_data, uint32_t* count,
 				    bool rw)
 {
-	struct rb_node *rb_right;
-	struct rb_node *rb_left;
-	struct db_record rec;
-	struct db_rbt_rec rec_priv;
+	struct db_rbt_ctx *ctx = talloc_get_type_abort(
+		db->private_data, struct db_rbt_ctx);
+	struct db_rbt_node *cur = NULL;
+	struct db_rbt_node *next = NULL;
 	int ret;
 
-	if (n == NULL) {
-		return 0;
-	}
+	for (cur = ctx->nodes; cur != NULL; cur = next) {
+		struct db_record rec;
+		struct db_rbt_rec rec_priv;
 
-	rb_left = n->rb_left;
-	rb_right = n->rb_right;
+		rec_priv.node = cur;
+		next = rec_priv.node->next;
 
-	ret = db_rbt_traverse_internal(db, rb_left, f, private_data, count, rw);
-	if (ret != 0) {
-		return ret;
-	}
-
-	rec_priv.node = db_rbt2node(n);
-	/* n might be altered by the callback function */
-	n = NULL;
-
-	ZERO_STRUCT(rec);
-	rec.db = db;
-	rec.private_data = &rec_priv;
-	if (rw) {
+		ZERO_STRUCT(rec);
+		rec.db = db;
+		rec.private_data = &rec_priv;
 		rec.store = db_rbt_store;
 		rec.delete_rec = db_rbt_delete;
-	} else {
-		rec.store = db_rbt_store_deny;
-		rec.delete_rec = db_rbt_delete_deny;
-	}
-	db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
-
-	ret = f(&rec, private_data);
-	(*count) ++;
-	if (ret != 0) {
-		return ret;
-	}
+		db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
 
-	if (rec_priv.node != NULL) {
-		/*
-		 * If the current record is still there
-		 * we should take the current rb_right.
-		 */
-		rb_right = rec_priv.node->rb_node.rb_right;
+		if (rw) {
+			ctx->traverse_nextp = &next;
+		}
+		ret = f(&rec, private_data);
+		(*count) ++;
+		if (rw) {
+			ctx->traverse_nextp = NULL;
+		}
+		if (ret != 0) {
+			return ret;
+		}
+		if (rec_priv.node != NULL) {
+			next = rec_priv.node->next;
+		}
 	}
 
-	return db_rbt_traverse_internal(db, rb_right, f, private_data, count, rw);
+	return 0;
 }
 
-static int db_rbt_traverse(struct db_context *db,
-			   int (*f)(struct db_record *db,
-				    void *private_data),
-			   void *private_data)
+static int db_rbt_traverse_read(struct db_context *db,
+				int (*f)(struct db_record *db,
+					 void *private_data),
+				void *private_data)
 {
 	struct db_rbt_ctx *ctx = talloc_get_type_abort(
 		db->private_data, struct db_rbt_ctx);
 	uint32_t count = 0;
+	int ret;
 
-	int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
-					   f, private_data, &count,
-					   true /* rw */);
+	ctx->traverse_read++;
+	ret = db_rbt_traverse_internal(db,
+				       f, private_data, &count,
+				       false /* rw */);
+	ctx->traverse_read--;
 	if (ret != 0) {
 		return -1;
 	}
@@ -463,18 +471,27 @@ static int db_rbt_traverse(struct db_context *db,
 	return count;
 }
 
-static int db_rbt_traverse_read(struct db_context *db,
-				int (*f)(struct db_record *db,
-					 void *private_data),
-				void *private_data)
+static int db_rbt_traverse(struct db_context *db,
+			   int (*f)(struct db_record *db,
+				    void *private_data),
+			   void *private_data)
 {
 	struct db_rbt_ctx *ctx = talloc_get_type_abort(
 		db->private_data, struct db_rbt_ctx);
 	uint32_t count = 0;
+	int ret;
+
+	if (ctx->traverse_nextp != NULL) {
+		return -1;
+	};
+
+	if (ctx->traverse_read > 0) {
+		return db_rbt_traverse_read(db, f, private_data);
+	}
 
-	int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
-					   f, private_data, &count,
-					   false /* rw */);
+	ret = db_rbt_traverse_internal(db,
+				       f, private_data, &count,
+				       true /* rw */);
 	if (ret != 0) {
 		return -1;
 	}
diff --git a/source3/torture/torture.c b/source3/torture/torture.c
index ef75d21..6c34e4c 100644
--- a/source3/torture/torture.c
+++ b/source3/torture/torture.c
@@ -8347,11 +8347,29 @@ static bool rbt_testval(struct db_context *db, const char *key,
 	return ret;
 }
 
+static int local_rbtree_traverse_read(struct db_record *rec, void *private_data)
+{
+	int *count2 = (int *)private_data;
+	(*count2)++;
+	return 0;
+}
+
+static int local_rbtree_traverse_delete(struct db_record *rec, void *private_data)
+{
+	int *count2 = (int *)private_data;
+	(*count2)++;
+	dbwrap_record_delete(rec);
+	return 0;
+}
+
 static bool run_local_rbtree(int dummy)
 {
 	struct db_context *db;
 	bool ret = false;
 	int i;
+	NTSTATUS status;
+	int count = 0;
+	int count2 = 0;
 
 	db = db_open_rbt(NULL);
 
@@ -8394,6 +8412,27 @@ static bool run_local_rbtree(int dummy)
 	}
 
 	ret = true;
+	count = 0; count2 = 0;
+	status = dbwrap_traverse_read(db, local_rbtree_traverse_read,
+				      &count2, &count);
+	printf("%s: read1: %d %d, %s\n", __func__, count, count2, nt_errstr(status));
+	if ((count != count2) || (count != 1000)) {
+		ret = false;
+	}
+	count = 0; count2 = 0;
+	status = dbwrap_traverse(db, local_rbtree_traverse_delete,
+				 &count2, &count);
+	printf("%s: delete: %d %d, %s\n", __func__, count, count2, nt_errstr(status));
+	if ((count != count2) || (count != 1000)) {
+		ret = false;
+	}
+	count = 0; count2 = 0;
+	status = dbwrap_traverse_read(db, local_rbtree_traverse_read,
+				      &count2, &count);
+	printf("%s: read2: %d %d, %s\n", __func__, count, count2, nt_errstr(status));
+	if ((count != count2) || (count != 0)) {
+		ret = false;
+	}
 
  done:
 	TALLOC_FREE(db);


-- 
Samba Shared Repository



More information about the samba-cvs mailing list