[PATCH] lib: test_rhashtable: fix for large entry counts

Subsystems: library code, rhashtable, the rest

STALE3333d

3 messages, 3 authors, 2017-07-24 · open the first message on its own page

[PATCH] lib: test_rhashtable: fix for large entry counts

From: Phil Sutter <phil@nwl.cc>
Date: 2017-07-21 14:51:44

During concurrent access testing, threadfunc() concatenated thread ID
and object index to create a unique key like so:

| tdata->objs[i].value = (tdata->id << 16) | i;

This breaks if a user passes an entries parameter of 64k or higher,
since 'i' might use more than 16 bits then. Effectively, this will lead
to duplicate keys in the table.

Fix the problem by introducing a struct holding object and thread ID and
using that as key instead of a single integer type field.

Fixes: f4a3e90ba5739 ("rhashtable-test: extend to test concurrency")
Reported by: Manuel Messner [off-list ref]
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 lib/test_rhashtable.c | 53 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 32 insertions(+), 21 deletions(-)
diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c
index 64e899b633371..16949d219291a 100644
--- a/lib/test_rhashtable.c
+++ b/lib/test_rhashtable.c
@@ -56,8 +56,13 @@ static bool enomem_retry = false;
 module_param(enomem_retry, bool, 0);
 MODULE_PARM_DESC(enomem_retry, "Retry insert even if -ENOMEM was returned (default: off)");
 
+struct test_obj_val {
+	int	id;
+	int	tid;
+};
+
 struct test_obj {
-	int			value;
+	struct test_obj_val	value;
 	struct rhash_head	node;
 };
 
@@ -72,7 +77,7 @@ static struct test_obj array[MAX_ENTRIES];
 static struct rhashtable_params test_rht_params = {
 	.head_offset = offsetof(struct test_obj, node),
 	.key_offset = offsetof(struct test_obj, value),
-	.key_len = sizeof(int),
+	.key_len = sizeof(struct test_obj_val),
 	.hashfn = jhash,
 	.nulls_base = (3U << RHT_BASE_SHIFT),
 };
@@ -109,24 +114,26 @@ static int __init test_rht_lookup(struct rhashtable *ht)
 	for (i = 0; i < entries * 2; i++) {
 		struct test_obj *obj;
 		bool expected = !(i % 2);
-		u32 key = i;
+		struct test_obj_val key = {
+			.id = i,
+		};
 
-		if (array[i / 2].value == TEST_INSERT_FAIL)
+		if (array[i / 2].value.id == TEST_INSERT_FAIL)
 			expected = false;
 
 		obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
 
 		if (expected && !obj) {
-			pr_warn("Test failed: Could not find key %u\n", key);
+			pr_warn("Test failed: Could not find key %u\n", key.id);
 			return -ENOENT;
 		} else if (!expected && obj) {
 			pr_warn("Test failed: Unexpected entry found for key %u\n",
-				key);
+				key.id);
 			return -EEXIST;
 		} else if (expected && obj) {
-			if (obj->value != i) {
+			if (obj->value.id != i) {
 				pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
-					obj->value, i);
+					obj->value.id, i);
 				return -EINVAL;
 			}
 		}
@@ -195,7 +202,7 @@ static s64 __init test_rhashtable(struct rhashtable *ht)
 	for (i = 0; i < entries; i++) {
 		struct test_obj *obj = &array[i];
 
-		obj->value = i * 2;
+		obj->value.id = i * 2;
 		err = insert_retry(ht, &obj->node, test_rht_params);
 		if (err > 0)
 			insert_retries += err;
@@ -218,7 +225,7 @@ static s64 __init test_rhashtable(struct rhashtable *ht)
 	for (i = 0; i < entries; i++) {
 		u32 key = i * 2;
 
-		if (array[i].value != TEST_INSERT_FAIL) {
+		if (array[i].value.id != TEST_INSERT_FAIL) {
 			obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
 			BUG_ON(!obj);
 
@@ -242,18 +249,21 @@ static int thread_lookup_test(struct thread_data *tdata)
 
 	for (i = 0; i < entries; i++) {
 		struct test_obj *obj;
-		int key = (tdata->id << 16) | i;
+		struct test_obj_val key = {
+			.id = i,
+			.tid = tdata->id,
+		};
 
 		obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
-		if (obj && (tdata->objs[i].value == TEST_INSERT_FAIL)) {
-			pr_err("  found unexpected object %d\n", key);
+		if (obj && (tdata->objs[i].value.id == TEST_INSERT_FAIL)) {
+			pr_err("  found unexpected object %d-%d\n", key.tid, key.id);
 			err++;
-		} else if (!obj && (tdata->objs[i].value != TEST_INSERT_FAIL)) {
-			pr_err("  object %d not found!\n", key);
+		} else if (!obj && (tdata->objs[i].value.id != TEST_INSERT_FAIL)) {
+			pr_err("  object %d-%d not found!\n", key.tid, key.id);
 			err++;
-		} else if (obj && (obj->value != key)) {
-			pr_err("  wrong object returned (got %d, expected %d)\n",
-			       obj->value, key);
+		} else if (obj && memcmp(&obj->value, &key, sizeof(key))) {
+			pr_err("  wrong object returned (got %d-%d, expected %d-%d)\n",
+			       obj->value.tid, obj->value.id, key.tid, key.id);
 			err++;
 		}
 
@@ -272,7 +282,8 @@ static int threadfunc(void *data)
 		pr_err("  thread[%d]: down_interruptible failed\n", tdata->id);
 
 	for (i = 0; i < entries; i++) {
-		tdata->objs[i].value = (tdata->id << 16) | i;
+		tdata->objs[i].value.id = i;
+		tdata->objs[i].value.tid = tdata->id;
 		err = insert_retry(&ht, &tdata->objs[i].node, test_rht_params);
 		if (err > 0) {
 			insert_retries += err;
@@ -295,7 +306,7 @@ static int threadfunc(void *data)
 
 	for (step = 10; step > 0; step--) {
 		for (i = 0; i < entries; i += step) {
-			if (tdata->objs[i].value == TEST_INSERT_FAIL)
+			if (tdata->objs[i].value.id == TEST_INSERT_FAIL)
 				continue;
 			err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
 			                             test_rht_params);
@@ -304,7 +315,7 @@ static int threadfunc(void *data)
 				       tdata->id);
 				goto out;
 			}
-			tdata->objs[i].value = TEST_INSERT_FAIL;
+			tdata->objs[i].value.id = TEST_INSERT_FAIL;
 
 			cond_resched();
 		}
-- 
2.13.1

Re: [PATCH] lib: test_rhashtable: fix for large entry counts

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: 2017-07-24 03:19:15

On Fri, Jul 21, 2017 at 04:51:31PM +0200, Phil Sutter wrote:
During concurrent access testing, threadfunc() concatenated thread ID
and object index to create a unique key like so:

| tdata->objs[i].value = (tdata->id << 16) | i;

This breaks if a user passes an entries parameter of 64k or higher,
since 'i' might use more than 16 bits then. Effectively, this will lead
to duplicate keys in the table.

Fix the problem by introducing a struct holding object and thread ID and
using that as key instead of a single integer type field.

Fixes: f4a3e90ba5739 ("rhashtable-test: extend to test concurrency")
Reported by: Manuel Messner [off-list ref]
Signed-off-by: Phil Sutter <phil@nwl.cc>
Acked-by: Herbert Xu <herbert@gondor.apana.org.au>
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] lib: test_rhashtable: fix for large entry counts

From: David Miller <davem@davemloft.net>
Date: 2017-07-24 21:14:19

From: Phil Sutter <phil@nwl.cc>
Date: Fri, 21 Jul 2017 16:51:31 +0200
During concurrent access testing, threadfunc() concatenated thread ID
and object index to create a unique key like so:

| tdata->objs[i].value = (tdata->id << 16) | i;

This breaks if a user passes an entries parameter of 64k or higher,
since 'i' might use more than 16 bits then. Effectively, this will lead
to duplicate keys in the table.

Fix the problem by introducing a struct holding object and thread ID and
using that as key instead of a single integer type field.

Fixes: f4a3e90ba5739 ("rhashtable-test: extend to test concurrency")
Reported by: Manuel Messner [off-list ref]
Signed-off-by: Phil Sutter <phil@nwl.cc>
Applied, thanks Phil.
Keyboard shortcuts
hback out one level
jnext message in thread
kprevious message in thread
ldrill in
Escclose help / fold thread tree
?toggle this help