* [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion
@ 2018-03-07 14:00 Paul Blakey
2018-03-07 14:00 ` [PATCH net v4 1/2] rhashtable: Fix rhlist " Paul Blakey
` (2 more replies)
0 siblings, 3 replies; 8+ messages in thread
From: Paul Blakey @ 2018-03-07 14:00 UTC (permalink / raw)
To: Thomas Graf, Herbert Xu, David Miller
Cc: netdev, Yevgeny Kliteynik, Roi Dayan, Shahar Klein, Mark Bloch,
Jiri Pirko, Or Gerlitz, Matan Barak, 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 scenario happened,
insertion of a flow group with a similar match criteria (a 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.
v4 --> v3 changes:
* Added Herbert Xu's ack (thanks)
* Removed extra commit tags
v3 --> v2 changes:
* Added missing fix in rhashtable_lookup_one code path as well.
v2 --> v1 changes:
* Changed commit messages to better reflect the change
Paul Blakey (2):
rhashtable: Fix rhlist duplicates insertion
test_rhashtable: add test case for rhltable with duplicate objects
include/linux/rhashtable.h | 4 +-
lib/rhashtable.c | 4 +-
lib/test_rhashtable.c | 134 +++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 140 insertions(+), 2 deletions(-)
--
1.8.4.3
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH net v4 1/2] rhashtable: Fix rhlist duplicates insertion
2018-03-07 14:00 [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion Paul Blakey
@ 2018-03-07 14:00 ` Paul Blakey
2018-03-07 14:00 ` [PATCH net v4 2/2] test_rhashtable: add test case for rhltable with duplicate objects Paul Blakey
2018-03-07 16:23 ` [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion David Miller
2 siblings, 0 replies; 8+ messages in thread
From: Paul Blakey @ 2018-03-07 14:00 UTC (permalink / raw)
To: Thomas Graf, Herbert Xu, David Miller
Cc: netdev, Yevgeny Kliteynik, Roi Dayan, Shahar Klein, Mark Bloch,
Jiri Pirko, Or Gerlitz, Matan Barak, Paul Blakey
When inserting duplicate objects (those with the same key),
current rhlist 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 +++-
lib/rhashtable.c | 4 +++-
2 files changed, 6 insertions(+), 2 deletions(-)
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);
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 3825c30..47de025 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -506,8 +506,10 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
if (!key ||
(ht->p.obj_cmpfn ?
ht->p.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;
+ }
if (!ht->rhlist)
return rht_obj(ht, head);
--
1.8.4.3
^ permalink raw reply related [flat|nested] 8+ messages in thread
* [PATCH net v4 2/2] test_rhashtable: add test case for rhltable with duplicate objects
2018-03-07 14:00 [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion Paul Blakey
2018-03-07 14:00 ` [PATCH net v4 1/2] rhashtable: Fix rhlist " Paul Blakey
@ 2018-03-07 14:00 ` Paul Blakey
2018-03-07 16:23 ` [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion David Miller
2 siblings, 0 replies; 8+ messages in thread
From: Paul Blakey @ 2018-03-07 14:00 UTC (permalink / raw)
To: Thomas Graf, Herbert Xu, David Miller
Cc: netdev, Yevgeny Kliteynik, Roi Dayan, Shahar Klein, Mark Bloch,
Jiri Pirko, Or Gerlitz, Matan Barak, 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 | 134 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 134 insertions(+)
diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c
index 76d3667..f4000c1 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,112 @@ 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, bool slow)
+{
+ struct rhltable rhlt;
+ unsigned int i, ret;
+ const char *key;
+ int err = 0;
+
+ 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;
+ key = rht_obj(&rhlt.ht, &rhl_test_objects[i].list_node.rhead);
+ key += test_rht_params_dup.key_offset;
+
+ if (slow) {
+ err = PTR_ERR(rhashtable_insert_slow(&rhlt.ht, key,
+ &rhl_test_objects[i].list_node.rhead));
+ if (err == -EAGAIN)
+ err = 0;
+ } else
+ err = rhltable_insert(&rhlt,
+ &rhl_test_objects[i].list_node,
+ test_rht_params_dup);
+ if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
+ goto skip_print;
+ }
+
+ ret = print_ht(&rhlt);
+ WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");
+
+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, false);
+ test_insert_dup(rhl_test_objects, 3, false);
+ test_insert_dup(rhl_test_objects, 2, true);
+ test_insert_dup(rhl_test_objects, 3, true);
+
+ return 0;
+}
+
static int thread_lookup_test(struct thread_data *tdata)
{
unsigned int entries = tdata->entries;
@@ -613,6 +745,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
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion
2018-03-07 14:00 [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion Paul Blakey
2018-03-07 14:00 ` [PATCH net v4 1/2] rhashtable: Fix rhlist " Paul Blakey
2018-03-07 14:00 ` [PATCH net v4 2/2] test_rhashtable: add test case for rhltable with duplicate objects Paul Blakey
@ 2018-03-07 16:23 ` David Miller
2018-03-08 8:01 ` Paul Blakey
2018-03-11 9:16 ` Or Gerlitz
2 siblings, 2 replies; 8+ messages in thread
From: David Miller @ 2018-03-07 16:23 UTC (permalink / raw)
To: paulb
Cc: tgraf, herbert, netdev, kliteyn, roid, shahark, markb, jiri,
ogerlitz, matanb
From: Paul Blakey <paulb@mellanox.com>
Date: Wed, 7 Mar 2018 16:00:11 +0200
> 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 scenario happened,
> insertion of a flow group with a similar match criteria (a 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.
>
> v4 --> v3 changes:
> * Added Herbert Xu's ack (thanks)
> * Removed extra commit tags
I already applied v3, sorry. But I did add Herbert's ACKs.
:-)
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion
2018-03-07 16:23 ` [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion David Miller
@ 2018-03-08 8:01 ` Paul Blakey
2018-03-11 9:16 ` Or Gerlitz
1 sibling, 0 replies; 8+ messages in thread
From: Paul Blakey @ 2018-03-08 8:01 UTC (permalink / raw)
To: David Miller
Cc: paulb, tgraf, herbert, netdev, kliteyn, roid, shahark, markb,
jiri, ogerlitz, matanb
On 07/03/2018 18:23, David Miller wrote:
> From: Paul Blakey <paulb@mellanox.com>
> Date: Wed, 7 Mar 2018 16:00:11 +0200
>
>> 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 scenario happened,
>> insertion of a flow group with a similar match criteria (a 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.
>>
>> v4 --> v3 changes:
>> * Added Herbert Xu's ack (thanks)
>> * Removed extra commit tags
>
> I already applied v3, sorry. But I did add Herbert's ACKs.
> :-)
>
thanks
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion
2018-03-07 16:23 ` [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion David Miller
2018-03-08 8:01 ` Paul Blakey
@ 2018-03-11 9:16 ` Or Gerlitz
2018-03-12 2:48 ` David Miller
1 sibling, 1 reply; 8+ messages in thread
From: Or Gerlitz @ 2018-03-11 9:16 UTC (permalink / raw)
To: David Miller, paulb
Cc: tgraf, herbert, netdev, kliteyn, roid, shahark, markb, jiri, matanb
On 3/7/2018 6:23 PM, David Miller wrote:
> From: Paul Blakey <paulb@mellanox.com>
> Date: Wed, 7 Mar 2018 16:00:11 +0200
>
>> 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 scenario happened,
>> insertion of a flow group with a similar match criteria (a duplicate),
>> but only where the flow group rhash_head was second (or not first)
>> on the relevant rhashtable bucket list.
> I already applied v3, sorry. But I did add Herbert's ACKs.
Hi Dave,
In mlx5 we use this facility since 4.14, can you please push to -stable of at least 4.14 if not earlier?
Or.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion
2018-03-11 9:16 ` Or Gerlitz
@ 2018-03-12 2:48 ` David Miller
2018-03-12 6:40 ` Or Gerlitz
0 siblings, 1 reply; 8+ messages in thread
From: David Miller @ 2018-03-12 2:48 UTC (permalink / raw)
To: ogerlitz
Cc: paulb, tgraf, herbert, netdev, kliteyn, roid, shahark, markb,
jiri, matanb
From: Or Gerlitz <ogerlitz@mellanox.com>
Date: Sun, 11 Mar 2018 11:16:44 +0200
> On 3/7/2018 6:23 PM, David Miller wrote:
>> From: Paul Blakey <paulb@mellanox.com>
>> Date: Wed, 7 Mar 2018 16:00:11 +0200
>>
>>> 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 scenario happened,
>>> insertion of a flow group with a similar match criteria (a duplicate),
>>> but only where the flow group rhash_head was second (or not first)
>>> on the relevant rhashtable bucket list.
>
>> I already applied v3, sorry. But I did add Herbert's ACKs.
>
> Hi Dave,
>
> In mlx5 we use this facility since 4.14, can you please push to
> -stable of at least 4.14 if not earlier?
Ok, queued up.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion
2018-03-12 2:48 ` David Miller
@ 2018-03-12 6:40 ` Or Gerlitz
0 siblings, 0 replies; 8+ messages in thread
From: Or Gerlitz @ 2018-03-12 6:40 UTC (permalink / raw)
To: David Miller; +Cc: paulb, netdev
On 3/12/2018 4:48 AM, David Miller wrote:
> Ok, queued up.
thank you
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2018-03-12 6:40 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-03-07 14:00 [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion Paul Blakey
2018-03-07 14:00 ` [PATCH net v4 1/2] rhashtable: Fix rhlist " Paul Blakey
2018-03-07 14:00 ` [PATCH net v4 2/2] test_rhashtable: add test case for rhltable with duplicate objects Paul Blakey
2018-03-07 16:23 ` [PATCH net v4 0/2] rhashtable: Fix rhltable duplicates insertion David Miller
2018-03-08 8:01 ` Paul Blakey
2018-03-11 9:16 ` Or Gerlitz
2018-03-12 2:48 ` David Miller
2018-03-12 6:40 ` Or Gerlitz
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.