Add element acquire/release capabilities to rtree.

This makes it possible to acquire short-term "ownership" of rtree
elements so that it is possible to read an extent pointer *and* read the
extent's contents with a guarantee that the element will not be modified
until the ownership is released.  This is intended as a mechanism for
resolving rtree read/write races rather than as a way to lock extents.

1 files changed, 119 insertions, 34 deletions

diff --git a/test/unit/rtree.c b/test/unit/rtree.c
index 30b1c54..671e2c8 100644
--- a/test/unit/rtree.c
+++ b/test/unit/rtree.c
@@ -1,20 +1,24 @@
 #include "test/jemalloc_test.h"
 
-static rtree_node_elm_t *
+static rtree_elm_t *
 node_alloc(size_t nelms)
 {
+	rtree_elm_t *node;
 
-	return ((rtree_node_elm_t *)calloc(nelms, sizeof(rtree_node_elm_t)));
+	node = (rtree_elm_t *)calloc(nelms, sizeof(rtree_elm_t));
+	assert_ptr_not_null(node, "Unexpected calloc() failure");
+
+	return (node);
 }
 
 static void
-node_dalloc(rtree_node_elm_t *node)
+node_dalloc(rtree_elm_t *node)
 {
 
 	free(node);
 }
 
-TEST_BEGIN(test_rtree_get_empty)
+TEST_BEGIN(test_rtree_read_empty)
 {
 	unsigned i;
 
@@ -22,13 +26,89 @@ TEST_BEGIN(test_rtree_get_empty)
 		rtree_t rtree;
 		assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
 		    "Unexpected rtree_new() failure");
-		assert_ptr_null(rtree_get(&rtree, 0, false),
-		    "rtree_get() should return NULL for empty tree");
+		assert_ptr_null(rtree_read(&rtree, 0, false),
+		    "rtree_read() should return NULL for empty tree");
 		rtree_delete(&rtree);
 	}
 }
 TEST_END
 
+#define	NTHREADS	8
+#define	MAX_NBITS	18
+#define	NITERS		1000
+#define	SEED		42
+
+typedef struct {
+	unsigned	nbits;
+	rtree_t		rtree;
+	uint32_t	seed;
+} thd_start_arg_t;
+
+static void *
+thd_start(void *varg)
+{
+	thd_start_arg_t *arg = (thd_start_arg_t *)varg;
+	sfmt_t	*sfmt;
+	extent_t *extent;
+	unsigned i;
+
+	sfmt = init_gen_rand(arg->seed);
+	extent = (extent_t *)malloc(sizeof(extent));
+	assert_ptr_not_null(extent, "Unexpected malloc() failure");
+
+	for (i = 0; i < NITERS; i++) {
+		uintptr_t key = (uintptr_t)gen_rand64(sfmt);
+		if (i % 2 == 0) {
+			rtree_elm_t *elm;
+
+			elm = rtree_elm_acquire(&arg->rtree, key, false, true);
+			assert_ptr_not_null(elm,
+			    "Unexpected rtree_elm_acquire() failure");
+			rtree_elm_write_acquired(elm, extent);
+			rtree_elm_release(elm);
+
+			elm = rtree_elm_acquire(&arg->rtree, key, true, false);
+			assert_ptr_not_null(elm,
+			    "Unexpected rtree_elm_acquire() failure");
+			rtree_elm_read_acquired(elm);
+			rtree_elm_release(elm);
+		} else
+			rtree_read(&arg->rtree, key, false);
+	}
+
+	free(extent);
+	fini_gen_rand(sfmt);
+	return (NULL);
+}
+
+TEST_BEGIN(test_rtree_concurrent)
+{
+	thd_start_arg_t arg;
+	thd_t thds[NTHREADS];
+	sfmt_t *sfmt;
+	unsigned i, j;
+
+	sfmt = init_gen_rand(SEED);
+	for (i = 1; i < MAX_NBITS; i++) {
+		arg.nbits = i;
+		assert_false(rtree_new(&arg.rtree, arg.nbits, node_alloc,
+		    node_dalloc), "Unexpected rtree_new() failure");
+		arg.seed = gen_rand32(sfmt);
+		for (j = 0; j < NTHREADS; j++)
+			thd_create(&thds[j], thd_start, (void *)&arg);
+		for (j = 0; j < NTHREADS; j++)
+			thd_join(thds[j], NULL);
+		rtree_delete(&arg.rtree);
+	}
+	fini_gen_rand(sfmt);
+}
+TEST_END
+
+#undef NTHREADS
+#undef MAX_NBITS
+#undef NITERS
+#undef SEED
+
 TEST_BEGIN(test_rtree_extrema)
 {
 	unsigned i;
@@ -39,16 +119,16 @@ TEST_BEGIN(test_rtree_extrema)
 		assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
 		    "Unexpected rtree_new() failure");
 
-		assert_false(rtree_set(&rtree, 0, &extent_a),
-		    "Unexpected rtree_set() failure");
-		assert_ptr_eq(rtree_get(&rtree, 0, true), &extent_a,
-		    "rtree_get() should return previously set value");
+		assert_false(rtree_write(&rtree, 0, &extent_a),
+		    "Unexpected rtree_write() failure, i=%u", i);
+		assert_ptr_eq(rtree_read(&rtree, 0, true), &extent_a,
+		    "rtree_read() should return previously set value, i=%u", i);
 
-		assert_false(rtree_set(&rtree, ~((uintptr_t)0), &extent_b),
-		    "Unexpected rtree_set() failure");
-		assert_ptr_eq(rtree_get(&rtree, ~((uintptr_t)0), true),
+		assert_false(rtree_write(&rtree, ~((uintptr_t)0), &extent_b),
+		    "Unexpected rtree_write() failure, i=%u", i);
+		assert_ptr_eq(rtree_read(&rtree, ~((uintptr_t)0), true),
 		    &extent_b,
-		    "rtree_get() should return previously set value");
+		    "rtree_read() should return previously set value, i=%u", i);
 
 		rtree_delete(&rtree);
 	}
@@ -69,22 +149,21 @@ TEST_BEGIN(test_rtree_bits)
 		    "Unexpected rtree_new() failure");
 
 		for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) {
-			assert_false(rtree_set(&rtree, keys[j], &extent),
-			    "Unexpected rtree_set() failure");
+			assert_false(rtree_write(&rtree, keys[j], &extent),
+			    "Unexpected rtree_write() failure");
 			for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) {
-				assert_ptr_eq(rtree_get(&rtree, keys[k], true),
-				    &extent, "rtree_get() should return "
+				assert_ptr_eq(rtree_read(&rtree, keys[k], true),
+				    &extent, "rtree_read() should return "
 				    "previously set value and ignore "
 				    "insignificant key bits; i=%u, j=%u, k=%u, "
 				    "set key=%#"FMTxPTR", get key=%#"FMTxPTR, i,
 				    j, k, keys[j], keys[k]);
 			}
-			assert_ptr_null(rtree_get(&rtree,
+			assert_ptr_null(rtree_read(&rtree,
 			    (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)), false),
 			    "Only leftmost rtree leaf should be set; "
 			    "i=%u, j=%u", i, j);
-			assert_false(rtree_set(&rtree, keys[j], NULL),
-			    "Unexpected rtree_set() failure");
+			rtree_clear(&rtree, keys[j]);
 		}
 
 		rtree_delete(&rtree);
@@ -105,31 +184,36 @@ TEST_BEGIN(test_rtree_random)
 		extent_t extent;
 		unsigned j;
 		rtree_t rtree;
+		rtree_elm_t *elm;
 
 		assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc),
 		    "Unexpected rtree_new() failure");
 
 		for (j = 0; j < NSET; j++) {
 			keys[j] = (uintptr_t)gen_rand64(sfmt);
-			assert_false(rtree_set(&rtree, keys[j], &extent),
-			    "Unexpected rtree_set() failure");
-			assert_ptr_eq(rtree_get(&rtree, keys[j], true), &extent,
-			    "rtree_get() should return previously set value");
+			elm = rtree_elm_acquire(&rtree, keys[j], false, true);
+			assert_ptr_not_null(elm,
+			    "Unexpected rtree_elm_acquire() failure");
+			rtree_elm_write_acquired(elm, &extent);
+			rtree_elm_release(elm);
+			assert_ptr_eq(rtree_read(&rtree, keys[j], true),
+			    &extent,
+			    "rtree_read() should return previously set value");
 		}
 		for (j = 0; j < NSET; j++) {
-			assert_ptr_eq(rtree_get(&rtree, keys[j], true), &extent,
-			    "rtree_get() should return previously set value");
+			assert_ptr_eq(rtree_read(&rtree, keys[j], true),
+			    &extent, "rtree_read() should return previously "
+			    "set value, j=%u", j);
 		}
 
 		for (j = 0; j < NSET; j++) {
-			assert_false(rtree_set(&rtree, keys[j], NULL),
-			    "Unexpected rtree_set() failure");
-			assert_ptr_null(rtree_get(&rtree, keys[j], true),
-			    "rtree_get() should return previously set value");
+			rtree_clear(&rtree, keys[j]);
+			assert_ptr_null(rtree_read(&rtree, keys[j], true),
+			    "rtree_read() should return previously set value");
 		}
 		for (j = 0; j < NSET; j++) {
-			assert_ptr_null(rtree_get(&rtree, keys[j], true),
-			    "rtree_get() should return previously set value");
+			assert_ptr_null(rtree_read(&rtree, keys[j], true),
+			    "rtree_read() should return previously set value");
 		}
 
 		rtree_delete(&rtree);
@@ -145,7 +229,8 @@ main(void)
 {
 
 	return (test(
-	    test_rtree_get_empty,
+	    test_rtree_read_empty,
+	    test_rtree_concurrent,
 	    test_rtree_extrema,
 	    test_rtree_bits,
 	    test_rtree_random));