[PATCH] rhashtable: Fix missing elements when inserting.

[PATCH] rhashtable: Fix missing elements when inserting.

[Taehee Yoo]

rhltable_insert_key() inserts a node into list of element,
if node's key is duplicated, so that it becomes the chain of
element(as known as rhead). Also bucket table points that element directly.
If a inserted node's element chain is located at third,
rhltable misses first and second element chain.
This issue is causion of to failture the rhltable_remove().

After this patch, rhltable_insert_key() inserts a node into second of
element's list, so that rhlist do not misses elements.

Signed-off-by: Taehee Yoo <ap420073@gmail.com>
---
 include/linux/rhashtable.h | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 7d56a7e..d3c24b9 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -762,11 +762,9 @@ static inline void *__rhashtable_insert_fast(
 		list = container_of(obj, struct rhlist_head, rhead);
 		plist = container_of(head, struct rhlist_head, rhead);
 
-		RCU_INIT_POINTER(list->next, plist);
-		head = rht_dereference_bucket(head->next, tbl, hash);
-		RCU_INIT_POINTER(list->rhead.next, head);
-		rcu_assign_pointer(*pprev, obj);
-
+		RCU_INIT_POINTER(list->next, rht_dereference_bucket(plist->next,
+								    tbl, hash));
+		RCU_INIT_POINTER(plist->next, list);
 		goto good;
 	}
 
-- 
2.9.3

Re: [PATCH] rhashtable: Fix missing elements when inserting.

[Herbert Xu]

Taehee Yoo <ap420073@gmail.com> wrote:
> rhltable_insert_key() inserts a node into list of element,
> if node's key is duplicated, so that it becomes the chain of
> element(as known as rhead). Also bucket table points that element directly.
> If a inserted node's element chain is located at third,
> rhltable misses first and second element chain.
> This issue is causion of to failture the rhltable_remove().
> 
> After this patch, rhltable_insert_key() inserts a node into second of
> element's list, so that rhlist do not misses elements.
> 
> Signed-off-by: Taehee Yoo <ap420073@gmail.com>

I'm sorry but I don't understand your description of the problem.
The new duplicate object is always inserted at the head of the
list and therefore replaces the previous list head in the hash
bucket chain.

Do you have some code that reproduces the problem?

> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
> index 7d56a7e..d3c24b9 100644
> --- a/include/linux/rhashtable.h
> +++ b/include/linux/rhashtable.h
> @@ -762,11 +762,9 @@ static inline void *__rhashtable_insert_fast(
>                list = container_of(obj, struct rhlist_head, rhead);
>                plist = container_of(head, struct rhlist_head, rhead);
> 
> -               RCU_INIT_POINTER(list->next, plist);
> -               head = rht_dereference_bucket(head->next, tbl, hash);
> -               RCU_INIT_POINTER(list->rhead.next, head);
> -               rcu_assign_pointer(*pprev, obj);
> -
> +               RCU_INIT_POINTER(list->next, rht_dereference_bucket(plist->next,
> +                                                                   tbl, hash));
> +               RCU_INIT_POINTER(plist->next, list);

Your second RCU_INIT_POINTER needs to be rcu_assign_pointer.

Your approach of retaining the first duplicate object as the head
of the list should work too but I don't really see any point in
changing this.

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] rhashtable: Fix missing elements when inserting.

[Taehee Yoo]

2017-05-24 13:36 GMT+09:00 Herbert Xu <herbert@gondor.apana.org.au>:
> Taehee Yoo <ap420073@gmail.com> wrote:
>> rhltable_insert_key() inserts a node into list of element,
>> if node's key is duplicated, so that it becomes the chain of
>> element(as known as rhead). Also bucket table points that element directly.
>> If a inserted node's element chain is located at third,
>> rhltable misses first and second element chain.
>> This issue is causion of to failture the rhltable_remove().
>>
>> After this patch, rhltable_insert_key() inserts a node into second of
>> element's list, so that rhlist do not misses elements.
>>
>> Signed-off-by: Taehee Yoo <ap420073@gmail.com>
>
> I'm sorry but I don't understand your description of the problem.
> The new duplicate object is always inserted at the head of the
> list and therefore replaces the previous list head in the hash
> bucket chain.
>
> Do you have some code that reproduces the problem?
>
I tested this problem using netfilter, therefore a attached diff file
modifies netfilter source code.
That diff prints fail messages if return value of rhltable_remove() is -ENOENT.

I used below commands

sysctl -w net.netfilter.nf_conntrack_udp_timeout=100000
sysctl -w net.netfilter.nf_conntrack_max=1000000
iptables -t nat -A POSTROUTING -j MASQUERADE

hping3 < ip address > -2 -p 1 --flood
hping3 < ip address > -2 -p 2 --flood
conntrack -D > /dev/null
we can see "nf_nat_cleanup_conntrack, not found"

>> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
>> index 7d56a7e..d3c24b9 100644
>> --- a/include/linux/rhashtable.h
>> +++ b/include/linux/rhashtable.h
>> @@ -762,11 +762,9 @@ static inline void *__rhashtable_insert_fast(
>>                list = container_of(obj, struct rhlist_head, rhead);
>>                plist = container_of(head, struct rhlist_head, rhead);
>>
>> -               RCU_INIT_POINTER(list->next, plist);
>> -               head = rht_dereference_bucket(head->next, tbl, hash);
>> -               RCU_INIT_POINTER(list->rhead.next, head);
>> -               rcu_assign_pointer(*pprev, obj);
>> -
>> +               RCU_INIT_POINTER(list->next, rht_dereference_bucket(plist->next,
>> +                                                                   tbl, hash));
>> +               RCU_INIT_POINTER(plist->next, list);
>
> Your second RCU_INIT_POINTER needs to be rcu_assign_pointer.
>
Thank you, I won't forget this.

> Your approach of retaining the first duplicate object as the head
> of the list should work too but I don't really see any point in
> changing this.
>
> 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] rhashtable: Fix missing elements when inserting.

[Taehee Yoo]

[-- Attachment #1: Type: text/plain, Size: 2928 bytes --]

2017-05-25 1:13 GMT+09:00 Taehee Yoo <ap420073@gmail.com>:
> 2017-05-24 13:36 GMT+09:00 Herbert Xu <herbert@gondor.apana.org.au>:
>> Taehee Yoo <ap420073@gmail.com> wrote:
>>> rhltable_insert_key() inserts a node into list of element,
>>> if node's key is duplicated, so that it becomes the chain of
>>> element(as known as rhead). Also bucket table points that element directly.
>>> If a inserted node's element chain is located at third,
>>> rhltable misses first and second element chain.
>>> This issue is causion of to failture the rhltable_remove().
>>>
>>> After this patch, rhltable_insert_key() inserts a node into second of
>>> element's list, so that rhlist do not misses elements.
>>>
>>> Signed-off-by: Taehee Yoo <ap420073@gmail.com>
>>
>> I'm sorry but I don't understand your description of the problem.
>> The new duplicate object is always inserted at the head of the
>> list and therefore replaces the previous list head in the hash
>> bucket chain.
>>
>> Do you have some code that reproduces the problem?
>>
> I tested this problem using netfilter, therefore a attached diff file
> modifies netfilter source code.
> That diff prints fail messages if return value of rhltable_remove() is -ENOENT.
>
> I used below commands
>
> sysctl -w net.netfilter.nf_conntrack_udp_timeout=100000
> sysctl -w net.netfilter.nf_conntrack_max=1000000
> iptables -t nat -A POSTROUTING -j MASQUERADE
>
> hping3 < ip address > -2 -p 1 --flood
> hping3 < ip address > -2 -p 2 --flood
> conntrack -D > /dev/null
> we can see "nf_nat_cleanup_conntrack, not found"
>
>>> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
>>> index 7d56a7e..d3c24b9 100644
>>> --- a/include/linux/rhashtable.h
>>> +++ b/include/linux/rhashtable.h
>>> @@ -762,11 +762,9 @@ static inline void *__rhashtable_insert_fast(
>>>                list = container_of(obj, struct rhlist_head, rhead);
>>>                plist = container_of(head, struct rhlist_head, rhead);
>>>
>>> -               RCU_INIT_POINTER(list->next, plist);
>>> -               head = rht_dereference_bucket(head->next, tbl, hash);
>>> -               RCU_INIT_POINTER(list->rhead.next, head);
>>> -               rcu_assign_pointer(*pprev, obj);
>>> -
>>> +               RCU_INIT_POINTER(list->next, rht_dereference_bucket(plist->next,
>>> +                                                                   tbl, hash));
>>> +               RCU_INIT_POINTER(plist->next, list);
>>
>> Your second RCU_INIT_POINTER needs to be rcu_assign_pointer.
>>
> Thank you, I won't forget this.
>
>> Your approach of retaining the first duplicate object as the head
>> of the list should work too but I don't really see any point in
>> changing this.
>>
>> 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

I'm so sorry, I did not attach diff file.

[-- Attachment #2: rhashtable_test.diff --]
[-- Type: text/plain, Size: 733 bytes --]

diff --git a/net/netfilter/nf_nat_core.c b/net/netfilter/nf_nat_core.c
index b48d6b5..a1d9a59 100644
--- a/net/netfilter/nf_nat_core.c
+++ b/net/netfilter/nf_nat_core.c
@@ -701,9 +701,14 @@ EXPORT_SYMBOL_GPL(nf_nat_l3proto_unregister);
 /* No one using conntrack by the time this called. */
 static void nf_nat_cleanup_conntrack(struct nf_conn *ct)
 {
-	if (ct->status & IPS_SRC_NAT_DONE)
-		rhltable_remove(&nf_nat_bysource_table, &ct->nat_bysource,
+	int err;
+
+	if (ct->status & IPS_SRC_NAT_DONE) {
+		err = rhltable_remove(&nf_nat_bysource_table, &ct->nat_bysource,
 				nf_nat_bysource_params);
+		if (err == -ENOENT)
+			printk("%s, not found\n", __func__);
+	}
 }
 
 static struct nf_ct_ext_type nat_extend __read_mostly = {