Skip to contentSkip to conversation

rhashtable: Fix missing elements when inserting.

PATCH In review Taehee Yoo 2 participants 4 messages May 24, 2017

Subsystems (4)
Networking Network drivers netfilter Rhashtable
lore
Share & tools
lore

Taehee Yoo

author
#0 lore raw

PATCH 1/1 rhashtable: Fix missing elements when inserting.

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 <[email protected]>
---
 include/linux/rhashtable.h | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
include/linux/rhashtable.h +3 -5
index 7d56a7e..d3c24b9 100644
@@ -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;
 	}
Signature · 1 line
2.9.3
maintainer
#1 lore raw
Quoted 11 lines · 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 <[email protected]>

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?

Quoted 6 lines
include/linux/rhashtable.h +0 -0
index 7d56a7e..d3c24b9 100644
@@ -762,11 +762,9 @@ static inline void *__rhashtable_insert_fast(
               list = container_of(obj, struct rhlist_head, rhead);

include/linux/rhashtable.h static inline void *__rhashtable_insert_fast( · line 767

Quoted 10 lines
include/linux/rhashtable.h +3 -5
               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,

Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
author
#2 lore raw

2017-05-24 13:36 GMT+09:00 Herbert Xu <[email protected]>:

Quoted 11 lines
Quoted 10 lines · 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.

Quoted 9 lines
Quoted 1 line
Signed-off-by Taehee Yoo <[email protected]>

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"

Quoted 8 lines
Quoted 8 lines
include/linux/rhashtable.h +0 -0
index 7d56a7e..d3c24b9 100644
@@ -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);
Quoted 11 lines

include/linux/rhashtable.h static inline void *__rhashtable_insert_fast( · line 767

Quoted 8 lines
include/linux/rhashtable.h +3 -5
-               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.

Quoted 9 lines

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 <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

author
#3 lore raw

2017-05-25 1:13 GMT+09:00 Taehee Yoo <[email protected]>:

Quoted 55 lines

2017-05-24 13:36 GMT+09:00 Herbert Xu <[email protected]>:

Quoted 11 lines
Quoted 10 lines · 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.

Quoted 9 lines
Quoted 1 line
Signed-off-by Taehee Yoo <[email protected]>

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"

Quoted 8 lines
Quoted 8 lines
include/linux/rhashtable.h +0 -0
index 7d56a7e..d3c24b9 100644
@@ -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);
Quoted 11 lines

include/linux/rhashtable.h static inline void *__rhashtable_insert_fast( · line 767

Quoted 8 lines
include/linux/rhashtable.h +3 -5
-               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.

Quoted 11 lines

Thank you, I won't forget this.

Quoted 9 lines

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 <[email protected]> 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.

net/netfilter/nf_nat_core.c +7 -2
index b48d6b5..a1d9a59 100644
@@ -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 = {