[PATCH 1/1] salad: fix mhash 'random' method

[PATCH 1/1] salad: fix mhash 'random' method

[Vladislav Shpilevoy]

Mhash 'random' method is supposed to return a valid node id given
an arbitrary integer, likely generated randomly. But on some
values it was returning 'end' marker despite emptiness of the
container.

This was because of confusion in usage of mh_size() and mh_end().
Mh_size() means real number of objects, stored in the cache,
while mh_end() means hash capacity, or 'number of buckets' as it
is named. Generally capacity is bigger than size, and sometimes
it led to a situation like this:

    size = 1
    capacity = 4
    rnd = 3

    [0]  [1]  [2]  [3]
     -    -    x    -

When code iterates only 'size' times, looking for an element
starting from 'rnd' position, it will not find anything. It
should iterate 'capacity' times instead.
---
Branch: https://github.com/tarantool/tarantool/tree/gerold103/mhash-random-fix

 src/lib/salad/mhash.h          | 11 +++---
 test/unit/CMakeLists.txt       |  2 ++
 test/unit/mhash.c              | 64 +++++++++++++++++++++++++++++++++-
 test/unit/mhash.result         | 14 ++++++++
 test/unit/mhash_bytemap.result | 14 ++++++++
 5 files changed, 97 insertions(+), 8 deletions(-)

diff --git a/src/lib/salad/mhash.h b/src/lib/salad/mhash.h
index a9b0e4d90..b555cad4c 100644
--- a/src/lib/salad/mhash.h
+++ b/src/lib/salad/mhash.h
@@ -238,13 +238,10 @@ _mh(get)(struct _mh(t) *h, const mh_node_t *node,
 static inline mh_int_t
 _mh(random)(struct _mh(t) *h, mh_int_t rnd)
 {
-	for (mh_int_t i = 0; i < mh_size(h); i++, rnd++) {
-		rnd %= h->n_buckets;
-		if (mh_exist(h, rnd))
-			return rnd;
-	}
-
-	return h->n_buckets;
+	mh_int_t res = mh_next(h, rnd % mh_end(h));
+	if (res != mh_end(h))
+		return res;
+	return mh_first(h);
 }
 
 static inline mh_int_t
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 04bc659e7..c13528400 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -25,7 +25,9 @@ add_executable(uri.test uri.c unit.c)
 target_link_libraries(uri.test uri unit)
 add_executable(queue.test queue.c)
 add_executable(mhash.test mhash.c)
+target_link_libraries(mhash.test unit)
 add_executable(mhash_bytemap.test mhash_bytemap.c)
+target_link_libraries(mhash_bytemap.test unit)
 add_executable(rope_basic.test rope_basic.c)
 target_link_libraries(rope_basic.test salad)
 add_executable(rope_avl.test rope_avl.c)
diff --git a/test/unit/mhash.c b/test/unit/mhash.c
index 72f9b57fa..5f37ae8d4 100644
--- a/test/unit/mhash.c
+++ b/test/unit/mhash.c
@@ -1,5 +1,6 @@
 #include <stdint.h>
 #include <stdio.h>
+#include <stdbool.h>
 #include "unit.h"
 
 #ifndef bytemap
@@ -38,6 +39,7 @@ struct mh_i32_collision_node_t {
 static void mhash_int32_id_test()
 {
 	header();
+	plan(0);
 	int k;
 	struct mh_i32_t *h;
 #define init()		({ mh_i32_new();		})
@@ -59,12 +61,14 @@ static void mhash_int32_id_test()
 
 #include "mhash_body.c"
 	footer();
+	check_plan();
 }
 
 
 static void mhash_int32_collision_test()
 {
 	header();
+	plan(0);
 	int k;
 	struct mh_i32_collision_t *h;
 #define init()		({ mh_i32_collision_new();		})
@@ -86,11 +90,69 @@ static void mhash_int32_collision_test()
 
 #include "mhash_body.c"
 	footer();
+	check_plan();
+}
+
+static void
+mhash_random_test(void)
+{
+	header();
+	plan(3);
+	struct mh_i32_t *h = mh_i32_new();
+	const int end = 100;
+	int i, size;
+	bool is_found[end], all_is_found[end];
+	memset(all_is_found, 1, sizeof(all_is_found));
+
+	for (i = 0; i < end; ++i) {
+		if (mh_i32_random(h, i) != mh_end(h))
+			break;
+	}
+	is(i, end, "empty random is always 'end'");
+
+	for (i = 0; i < end; ++i) {
+		struct mh_i32_node_t node = {i, i};
+		mh_int_t rc = mh_i32_put(h, &node, NULL, NULL);
+		int j;
+		for (j = 0; j < end; ++j) {
+			if (mh_i32_random(h, j) != rc)
+				break;
+		}
+		mh_i32_del(h, rc, NULL);
+		if (j != end)
+			break;
+	}
+	is(i, end, "one element is always found");
+
+	for (i = 0, size = sizeof(bool); i < end; ++i, size += sizeof(bool)) {
+		struct mh_i32_node_t *n, node = {i, i};
+		mh_i32_put(h, &node, NULL, NULL);
+		memset(is_found, 0, sizeof(is_found));
+		for (int j = 0; j < end; ++j) {
+			mh_int_t rc = mh_i32_random(h, j);
+			n = mh_i32_node(h, rc);
+			is_found[n->key] = true;
+		}
+		if (memcmp(is_found, all_is_found, size) != 0)
+			break;
+	}
+	is(i, end, "incremental random from mutable hash");
+
+	mh_i32_delete(h);
+	check_plan();
+	footer();
 }
 
 int main(void)
 {
+	header();
+	plan(3);
+
 	mhash_int32_id_test();
 	mhash_int32_collision_test();
-	return 0;
+	mhash_random_test();
+
+	int rc = check_plan();
+	footer();
+	return rc;
 }
diff --git a/test/unit/mhash.result b/test/unit/mhash.result
index ff958136a..fc757fa35 100644
--- a/test/unit/mhash.result
+++ b/test/unit/mhash.result
@@ -1,4 +1,18 @@
+	*** main ***
+1..3
 	*** mhash_int32_id_test ***
+    1..0
 	*** mhash_int32_id_test: done ***
+ok 1 - subtests
 	*** mhash_int32_collision_test ***
+    1..0
 	*** mhash_int32_collision_test: done ***
+ok 2 - subtests
+	*** mhash_random_test ***
+    1..3
+    ok 1 - empty random is always 'end'
+    ok 2 - one element is always found
+    ok 3 - incremental random from mutable hash
+ok 3 - subtests
+	*** mhash_random_test: done ***
+	*** main: done ***
diff --git a/test/unit/mhash_bytemap.result b/test/unit/mhash_bytemap.result
index ff958136a..fc757fa35 100644
--- a/test/unit/mhash_bytemap.result
+++ b/test/unit/mhash_bytemap.result
@@ -1,4 +1,18 @@
+	*** main ***
+1..3
 	*** mhash_int32_id_test ***
+    1..0
 	*** mhash_int32_id_test: done ***
+ok 1 - subtests
 	*** mhash_int32_collision_test ***
+    1..0
 	*** mhash_int32_collision_test: done ***
+ok 2 - subtests
+	*** mhash_random_test ***
+    1..3
+    ok 1 - empty random is always 'end'
+    ok 2 - one element is always found
+    ok 3 - incremental random from mutable hash
+ok 3 - subtests
+	*** mhash_random_test: done ***
+	*** main: done ***
-- 
2.17.2 (Apple Git-113)

Re: [tarantool-patches] [PATCH 1/1] salad: fix mhash 'random' method

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/03/01 00:29]:
> -	return h->n_buckets;
> +	mh_int_t res = mh_next(h, rnd % mh_end(h));
> +	if (res != mh_end(h))
> +		return res;
> +	return mh_first(h);


Well, it takes some time to understand this code.

OK to push.


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [tarantool-patches] Re: [PATCH 1/1] salad: fix mhash 'random' method

[Vladislav Shpilevoy]

On 01/03/2019 01:04, Konstantin Osipov wrote:
> * Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/03/01 00:29]:
>> -	return h->n_buckets;
>> +	mh_int_t res = mh_next(h, rnd % mh_end(h));
>> +	if (res != mh_end(h))
>> +		return res;
>> +	return mh_first(h);
> 
> 
> Well, it takes some time to understand this code.

IMO, it is much better to encapsulate those 'for' loops
scanning for an occupied non-dirty slot, than put them
into each function, working with buckets array.

> 
> OK to push.

Pushed to 2.1.

> 
> 
> -- 
> Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
> http://tarantool.io - www.twitter.com/kostja_osipov
>