[PATCH net 0/2] rhashtable: Fix rhltable duplicates insertion

[PATCH net 0/2] rhashtable: Fix rhltable duplicates insertion

[Paul Blakey]

On our mlx5 driver fs_core.c, we use the rhltable interface to store
flow groups. We noticed that sometimes we get a warning that flow group isn't
found at removal. This rare case was caused when a specific scenrio happened, 
insertion of a flow group with a similar match criteria (duplicate),
but only where the flow group rhash_head was second (or not first)
on the relevant rhashtable bucket list.

The first patch fixes it, and the second one adds a test that show
it is now working.

Paul Blakey (2):
  rhashtable: Fix rhltable duplicates insertion
  test_rhashtable: add test case for rhl_table with duplicate objects

 include/linux/rhashtable.h |   4 +-
 lib/test_rhashtable.c      | 121 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 124 insertions(+), 1 deletion(-)

-- 
1.8.4.3

[PATCH net 1/2] rhashtable: Fix rhltable duplicates insertion

[Paul Blakey]

When inserting duplicate objects (those with the same key),
current rhashtable implementation messes up the chain pointers by
updating the bucket pointer instead of prev next pointer to the
newly inserted node. This causes missing elements on removal and
travesal.

Fix that by properly updating pprev pointer to point to
the correct rhash_head next pointer.

Fixes: ca26893f05e8 ('rhashtable: Add rhlist interface')
Signed-off-by: Paul Blakey <paulb@mellanox.com>
---
 include/linux/rhashtable.h | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index c9df252..668a21f 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -766,8 +766,10 @@ static inline void *__rhashtable_insert_fast(
 		if (!key ||
 		    (params.obj_cmpfn ?
 		     params.obj_cmpfn(&arg, rht_obj(ht, head)) :
-		     rhashtable_compare(&arg, rht_obj(ht, head))))
+		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
+			pprev = &head->next;
 			continue;
+		}
 
 		data = rht_obj(ht, head);
 
-- 
1.8.4.3

[PATCH net 2/2] test_rhashtable: add test case for rhl_table with duplicate objects

[Paul Blakey]

Tries to insert duplicates in the middle of bucket's chain:
bucket 1:  [[val 21 (tid=1)]] -> [[ val 1 (tid=2),  val 1 (tid=0) ]]

Reuses tid to distinguish the elements insertion order.

Signed-off-by: Paul Blakey <paulb@mellanox.com>
---
 lib/test_rhashtable.c | 121 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 121 insertions(+)

diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c
index 76d3667..4a5f331 100644
--- a/lib/test_rhashtable.c
+++ b/lib/test_rhashtable.c
@@ -79,6 +79,21 @@ struct thread_data {
 	struct test_obj *objs;
 };
 
+static u32 my_hashfn(const void *data, u32 len, u32 seed)
+{
+	const struct test_obj_rhl *obj = data;
+
+	return (obj->value.id % 10) << RHT_HASH_RESERVED_SPACE;
+}
+
+static int my_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
+{
+	const struct test_obj_rhl *test_obj = obj;
+	const struct test_obj_val *val = arg->key;
+
+	return test_obj->value.id - val->id;
+}
+
 static struct rhashtable_params test_rht_params = {
 	.head_offset = offsetof(struct test_obj, node),
 	.key_offset = offsetof(struct test_obj, value),
@@ -87,6 +102,17 @@ struct thread_data {
 	.nulls_base = (3U << RHT_BASE_SHIFT),
 };
 
+static struct rhashtable_params test_rht_params_dup = {
+	.head_offset = offsetof(struct test_obj_rhl, list_node),
+	.key_offset = offsetof(struct test_obj_rhl, value),
+	.key_len = sizeof(struct test_obj_val),
+	.hashfn = jhash,
+	.obj_hashfn = my_hashfn,
+	.obj_cmpfn = my_cmpfn,
+	.nelem_hint = 128,
+	.automatic_shrinking = false,
+};
+
 static struct semaphore prestart_sem;
 static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);
 
@@ -465,6 +491,99 @@ static int __init test_rhashtable_max(struct test_obj *array,
 	return err;
 }
 
+static unsigned int __init print_ht(struct rhltable *rhlt)
+{
+	struct rhashtable *ht;
+	const struct bucket_table *tbl;
+	char buff[512] = "";
+	unsigned int i, cnt = 0;
+
+	ht = &rhlt->ht;
+	tbl = rht_dereference(ht->tbl, ht);
+	for (i = 0; i < tbl->size; i++) {
+		struct rhash_head *pos, *next;
+		struct test_obj_rhl *p;
+
+		pos = rht_dereference(tbl->buckets[i], ht);
+		next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;
+
+		if (!rht_is_a_nulls(pos)) {
+			sprintf(buff, "%s\nbucket[%d] -> ", buff, i);
+		}
+
+		while (!rht_is_a_nulls(pos)) {
+			struct rhlist_head *list = container_of(pos, struct rhlist_head, rhead);
+			sprintf(buff, "%s[[", buff);
+			do {
+				pos = &list->rhead;
+				list = rht_dereference(list->next, ht);
+				p = rht_obj(ht, pos);
+
+				sprintf(buff, "%s val %d (tid=%d)%s", buff, p->value.id, p->value.tid,
+					list? ", " : " ");
+				cnt++;
+			} while (list);
+
+			pos = next,
+			next = !rht_is_a_nulls(pos) ?
+				rht_dereference(pos->next, ht) : NULL;
+
+			sprintf(buff, "%s]]%s", buff, !rht_is_a_nulls(pos) ? " -> " : "");
+		}
+	}
+	printk(KERN_ERR "\n---- ht: ----%s\n-------------\n", buff);
+
+	return cnt;
+}
+
+static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
+				  int cnt)
+{
+	struct rhltable rhlt;
+	unsigned int i, ret;
+	int err;
+
+	err = rhltable_init(&rhlt, &test_rht_params_dup);
+	if (WARN_ON(err))
+		return err;
+
+	for (i = 0; i < cnt; i++) {
+		rhl_test_objects[i].value.tid = i;
+		err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
+				      test_rht_params_dup);
+		if (WARN(err, "error %d on element %d\n", err, i))
+			goto skip_print;
+	}
+
+	ret = print_ht(&rhlt);
+	WARN(ret != cnt, "missing rhltable elements (%d != %d)\n", ret, cnt);
+
+skip_print:
+	rhltable_destroy(&rhlt);
+
+	return 0;
+}
+
+static int __init test_insert_duplicates_run(void)
+{
+	struct test_obj_rhl rhl_test_objects[3] = {};
+
+	pr_info("test inserting duplicates\n");
+
+	/* two different values that map to same bucket */
+	rhl_test_objects[0].value.id = 1;
+	rhl_test_objects[1].value.id = 21;
+
+	/* and another duplicate with same as [0] value
+	 * which will be second on the bucket list */
+	rhl_test_objects[2].value.id = rhl_test_objects[0].value.id;
+
+	test_insert_dup(rhl_test_objects, 2);
+	test_insert_dup(rhl_test_objects, 3);
+
+	return 0;
+}
+
 static int thread_lookup_test(struct thread_data *tdata)
 {
 	unsigned int entries = tdata->entries;
@@ -613,6 +732,8 @@ static int __init test_rht_init(void)
 	do_div(total_time, runs);
 	pr_info("Average test time: %llu\n", total_time);
 
+	test_insert_duplicates_run();
+
 	if (!tcount)
 		return 0;
 
-- 
1.8.4.3

Re: [PATCH net 1/2] rhashtable: Fix rhltable duplicates insertion

[Herbert Xu]

On Sun, Mar 04, 2018 at 02:34:26PM +0200, Paul Blakey wrote:
> When inserting duplicate objects (those with the same key),
> current rhashtable implementation messes up the chain pointers by
> updating the bucket pointer instead of prev next pointer to the
> newly inserted node. This causes missing elements on removal and
> travesal.
> 
> Fix that by properly updating pprev pointer to point to
> the correct rhash_head next pointer.
> 
> Fixes: ca26893f05e8 ('rhashtable: Add rhlist interface')
> Signed-off-by: Paul Blakey <paulb@mellanox.com>

Nack.  You must not insert objects with the same key through
rhashtable.  The reason is that we cannot reliably fetch all
of the objects with the same key during a resize.

If you need duplicate objects, you should use rhlist.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net 1/2] rhashtable: Fix rhltable duplicates insertion

[Paul Blakey]

On 04/03/2018 14:57, Herbert Xu wrote:
> On Sun, Mar 04, 2018 at 02:34:26PM +0200, Paul Blakey wrote:
>> When inserting duplicate objects (those with the same key),
>> current rhashtable implementation messes up the chain pointers by
>> updating the bucket pointer instead of prev next pointer to the
>> newly inserted node. This causes missing elements on removal and
>> travesal.
>>
>> Fix that by properly updating pprev pointer to point to
>> the correct rhash_head next pointer.
>>
>> Fixes: ca26893f05e8 ('rhashtable: Add rhlist interface')
>> Signed-off-by: Paul Blakey <paulb@mellanox.com>
> 
> Nack.  You must not insert objects with the same key through
> rhashtable.  The reason is that we cannot reliably fetch all
> of the objects with the same key during a resize.
> 
> If you need duplicate objects, you should use rhlist.
> 
> Cheers,
> 


Hi, I meant the rhlist interface here, sent  v2.
Thanks,
Paul.

Re: [PATCH net 1/2] rhashtable: Fix rhltable duplicates insertion

[Herbert Xu]

On Sun, Mar 04, 2018 at 02:34:26PM +0200, Paul Blakey wrote:
> When inserting duplicate objects (those with the same key),
> current rhashtable implementation messes up the chain pointers by
> updating the bucket pointer instead of prev next pointer to the
> newly inserted node. This causes missing elements on removal and
> travesal.
> 
> Fix that by properly updating pprev pointer to point to
> the correct rhash_head next pointer.
> 
> Fixes: ca26893f05e8 ('rhashtable: Add rhlist interface')
> Signed-off-by: Paul Blakey <paulb@mellanox.com>

Ah I see, thanks for catching this!

Acked-by: Herbert Xu <herbert@gondor.apana.org.au>

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt