* [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND
@ 2019-02-25 11:16 Li RongQing
2019-02-25 11:26 ` Florian Westphal
0 siblings, 1 reply; 7+ messages in thread
From: Li RongQing @ 2019-02-25 11:16 UTC (permalink / raw)
To: netfilter-devel
CONNTRACK_LOCKS is 1024 and power of 2, so modulo operations
can be replaced with AND (CONNTRACK_LOCKS - 1)
and bitwise AND operation is quicker than module operation
Signed-off-by: Zhang Yu <zhangyu31@baidu.com>
Signed-off-by: Li RongQing <lirongqing@baidu.com>
---
include/net/netfilter/nf_conntrack_core.h | 4 +++-
net/netfilter/nf_conntrack_core.c | 10 +++++-----
net/netfilter/nf_conntrack_netlink.c | 2 +-
net/netfilter/nf_nat_core.c | 6 +++---
4 files changed, 12 insertions(+), 10 deletions(-)
diff --git a/include/net/netfilter/nf_conntrack_core.h b/include/net/netfilter/nf_conntrack_core.h
index ae41e92251dd..1b75a141c63d 100644
--- a/include/net/netfilter/nf_conntrack_core.h
+++ b/include/net/netfilter/nf_conntrack_core.h
@@ -67,7 +67,9 @@ static inline int nf_conntrack_confirm(struct sk_buff *skb)
void print_tuple(struct seq_file *s, const struct nf_conntrack_tuple *tuple,
const struct nf_conntrack_l4proto *proto);
-#define CONNTRACK_LOCKS 1024
+#define CONNTRACK_LOCKS_BIT 10
+#define CONNTRACK_LOCKS (1 << CONNTRACK_LOCKS_BIT)
+#define CONNTRACK_LOCKS_MASK (CONNTRACK_LOCKS - 1)
extern spinlock_t nf_conntrack_locks[CONNTRACK_LOCKS];
void nf_conntrack_lock(spinlock_t *lock);
diff --git a/net/netfilter/nf_conntrack_core.c b/net/netfilter/nf_conntrack_core.c
index e139c256e269..a0feb530ed00 100644
--- a/net/netfilter/nf_conntrack_core.c
+++ b/net/netfilter/nf_conntrack_core.c
@@ -116,8 +116,8 @@ EXPORT_SYMBOL_GPL(nf_conntrack_lock);
static void nf_conntrack_double_unlock(unsigned int h1, unsigned int h2)
{
- h1 %= CONNTRACK_LOCKS;
- h2 %= CONNTRACK_LOCKS;
+ h1 &= CONNTRACK_LOCKS_MASK;
+ h2 &= CONNTRACK_LOCKS_MASK;
spin_unlock(&nf_conntrack_locks[h1]);
if (h1 != h2)
spin_unlock(&nf_conntrack_locks[h2]);
@@ -127,8 +127,8 @@ static void nf_conntrack_double_unlock(unsigned int h1, unsigned int h2)
static bool nf_conntrack_double_lock(struct net *net, unsigned int h1,
unsigned int h2, unsigned int sequence)
{
- h1 %= CONNTRACK_LOCKS;
- h2 %= CONNTRACK_LOCKS;
+ h1 &= CONNTRACK_LOCKS_MASK;
+ h2 &= CONNTRACK_LOCKS_MASK;
if (h1 <= h2) {
nf_conntrack_lock(&nf_conntrack_locks[h1]);
if (h1 != h2)
@@ -1971,7 +1971,7 @@ get_next_corpse(int (*iter)(struct nf_conn *i, void *data),
spinlock_t *lockp;
for (; *bucket < nf_conntrack_htable_size; (*bucket)++) {
- lockp = &nf_conntrack_locks[*bucket % CONNTRACK_LOCKS];
+ lockp = &nf_conntrack_locks[*bucket & CONNTRACK_LOCKS_MASK];
local_bh_disable();
nf_conntrack_lock(lockp);
if (*bucket < nf_conntrack_htable_size) {
diff --git a/net/netfilter/nf_conntrack_netlink.c b/net/netfilter/nf_conntrack_netlink.c
index 349b42a65c8a..8f22743c270f 100644
--- a/net/netfilter/nf_conntrack_netlink.c
+++ b/net/netfilter/nf_conntrack_netlink.c
@@ -918,7 +918,7 @@ ctnetlink_dump_table(struct sk_buff *skb, struct netlink_callback *cb)
nf_ct_put(nf_ct_evict[i]);
}
- lockp = &nf_conntrack_locks[cb->args[0] % CONNTRACK_LOCKS];
+ lockp = &nf_conntrack_locks[cb->args[0] & CONNTRACK_LOCKS_MASK];
nf_conntrack_lock(lockp);
if (cb->args[0] >= nf_conntrack_htable_size) {
spin_unlock(lockp);
diff --git a/net/netfilter/nf_nat_core.c b/net/netfilter/nf_nat_core.c
index 35e61038ae96..2b1d377bf3ab 100644
--- a/net/netfilter/nf_nat_core.c
+++ b/net/netfilter/nf_nat_core.c
@@ -588,7 +588,7 @@ nf_nat_setup_info(struct nf_conn *ct,
srchash = hash_by_src(net,
&ct->tuplehash[IP_CT_DIR_ORIGINAL].tuple);
- lock = &nf_nat_locks[srchash % CONNTRACK_LOCKS];
+ lock = &nf_nat_locks[srchash & CONNTRACK_LOCKS_MASK];
spin_lock_bh(lock);
hlist_add_head_rcu(&ct->nat_bysource,
&nf_nat_bysource[srchash]);
@@ -773,9 +773,9 @@ static void __nf_nat_cleanup_conntrack(struct nf_conn *ct)
unsigned int h;
h = hash_by_src(nf_ct_net(ct), &ct->tuplehash[IP_CT_DIR_ORIGINAL].tuple);
- spin_lock_bh(&nf_nat_locks[h % CONNTRACK_LOCKS]);
+ spin_lock_bh(&nf_nat_locks[h & CONNTRACK_LOCKS_MASK]);
hlist_del_rcu(&ct->nat_bysource);
- spin_unlock_bh(&nf_nat_locks[h % CONNTRACK_LOCKS]);
+ spin_unlock_bh(&nf_nat_locks[h & CONNTRACK_LOCKS_MASK]);
}
static int nf_nat_proto_clean(struct nf_conn *ct, void *data)
--
2.16.2
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND
2019-02-25 11:16 [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND Li RongQing
@ 2019-02-25 11:26 ` Florian Westphal
2019-02-25 11:35 ` 答复: " Li,Rongqing
0 siblings, 1 reply; 7+ messages in thread
From: Florian Westphal @ 2019-02-25 11:26 UTC (permalink / raw)
To: Li RongQing; +Cc: netfilter-devel
Li RongQing <lirongqing@baidu.com> wrote:
> CONNTRACK_LOCKS is 1024 and power of 2, so modulo operations
> can be replaced with AND (CONNTRACK_LOCKS - 1)
>
> and bitwise AND operation is quicker than module operation
Uh. What kind of compiler doesn't figure that out?!
I would prefer to keep it as-is and let compiler do the optimization.
^ permalink raw reply [flat|nested] 7+ messages in thread
* 答复: [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND
2019-02-25 11:26 ` Florian Westphal
@ 2019-02-25 11:35 ` Li,Rongqing
2019-02-25 11:54 ` Florian Westphal
0 siblings, 1 reply; 7+ messages in thread
From: Li,Rongqing @ 2019-02-25 11:35 UTC (permalink / raw)
To: Florian Westphal; +Cc: netfilter-devel
> -----邮件原件-----
> 发件人: Florian Westphal [mailto:fw@strlen.de]
> 发送时间: 2019年2月25日 19:27
> 收件人: Li,Rongqing <lirongqing@baidu.com>
> 抄送: netfilter-devel@vger.kernel.org
> 主题: Re: [PATCH][nf-next] netfilter: replace modulo operation with bitwise
> AND
>
> Li RongQing <lirongqing@baidu.com> wrote:
> > CONNTRACK_LOCKS is 1024 and power of 2, so modulo operations can be
> > replaced with AND (CONNTRACK_LOCKS - 1)
> >
> > and bitwise AND operation is quicker than module operation
>
> Uh. What kind of compiler doesn't figure that out?!
>
> I would prefer to keep it as-is and let compiler do the optimization.
gcc version 7.3.0 (GCC)
main()
{
int i=1000000000;
i= i % 1024;
return i;
}
00000000004004a7 <main>:
4004a7: 55 push %rbp
4004a8: 48 89 e5 mov %rsp,%rbp
4004ab: c7 45 fc 00 ca 9a 3b movl $0x3b9aca00,-0x4(%rbp)
4004b2: 8b 45 fc mov -0x4(%rbp),%eax
4004b5: 99 cltd
4004b6: c1 ea 16 shr $0x16,%edx
4004b9: 01 d0 add %edx,%eax
4004bb: 25 ff 03 00 00 and $0x3ff,%eax
4004c0: 29 d0 sub %edx,%eax
4004c2: 89 45 fc mov %eax,-0x4(%rbp)
4004c5: 8b 45 fc mov -0x4(%rbp),%eax
4004c8: 5d pop %rbp
4004c9: c3 retq
4004ca: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
=================================
main()
{
int i=1000000000;
i= i & (1024-1);
return i;
}
00000000004004a7 <main>:
4004a7: 55 push %rbp
4004a8: 48 89 e5 mov %rsp,%rbp
4004ab: c7 45 fc 00 ca 9a 3b movl $0x3b9aca00,-0x4(%rbp)
4004b2: 81 65 fc ff 03 00 00 andl $0x3ff,-0x4(%rbp)
4004b9: 8b 45 fc mov -0x4(%rbp),%eax
4004bc: 5d pop %rbp
4004bd: c3 retq
4004be: 66 90 xchg %ax,%ax
Similar patch:
commit 1a1d74d378b13ad3f93e8975a0ade0980a49d28b
Author: Jakub Kicinski <jakub.kicinski@netronome.com>
Date: Mon Oct 31 20:43:17 2016 +0000
nfp: use AND instead of modulo to get ring indexes
thanks
-RongQing
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: 答复: [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND
2019-02-25 11:35 ` 答复: " Li,Rongqing
@ 2019-02-25 11:54 ` Florian Westphal
2019-02-26 1:15 ` 答复: " Li,Rongqing
0 siblings, 1 reply; 7+ messages in thread
From: Florian Westphal @ 2019-02-25 11:54 UTC (permalink / raw)
To: Li,Rongqing; +Cc: Florian Westphal, netfilter-devel
Li,Rongqing <lirongqing@baidu.com> wrote:
>
>
> > -----邮件原件-----
> > 发件人: Florian Westphal [mailto:fw@strlen.de]
> > 发送时间: 2019年2月25日 19:27
> > 收件人: Li,Rongqing <lirongqing@baidu.com>
> > 抄送: netfilter-devel@vger.kernel.org
> > 主题: Re: [PATCH][nf-next] netfilter: replace modulo operation with bitwise
> > AND
> >
> > Li RongQing <lirongqing@baidu.com> wrote:
> > > CONNTRACK_LOCKS is 1024 and power of 2, so modulo operations can be
> > > replaced with AND (CONNTRACK_LOCKS - 1)
> > >
> > > and bitwise AND operation is quicker than module operation
> >
> > Uh. What kind of compiler doesn't figure that out?!
> >
> > I would prefer to keep it as-is and let compiler do the optimization.
>
>
> gcc version 7.3.0 (GCC)
>
>
> main()
> {
> int i=1000000000;
>
> i= i % 1024;
>
> return i;
> }
>
> 00000000004004a7 <main>:
> 4004a7: 55 push %rbp
> 4004a8: 48 89 e5 mov %rsp,%rbp
> 4004ab: c7 45 fc 00 ca 9a 3b movl $0x3b9aca00,-0x4(%rbp)
> 4004b2: 8b 45 fc mov -0x4(%rbp),%eax
> 4004b5: 99 cltd
> 4004b6: c1 ea 16 shr $0x16,%edx
> 4004b9: 01 d0 add %edx,%eax
> 4004bb: 25 ff 03 00 00 and $0x3ff,%eax
& 1023.
With -O2 gcc emits same code regardless of % 1024 or & 1023.
> Similar patch:
>
> commit 1a1d74d378b13ad3f93e8975a0ade0980a49d28b
> Author: Jakub Kicinski <jakub.kicinski@netronome.com>
> Date: Mon Oct 31 20:43:17 2016 +0000
>
> nfp: use AND instead of modulo to get ring indexes
But in that case the value isn't known at compile time.
gcc can't know that '= reg1 % reg2' can be rewritten as 'reg1 & (reg2 - 1)'
But it can do it if reg2 is a known constant (and a power of 2).
^ permalink raw reply [flat|nested] 7+ messages in thread
* 答复: 答复: [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND
2019-02-25 11:54 ` Florian Westphal
@ 2019-02-26 1:15 ` Li,Rongqing
2019-02-26 6:31 ` Florian Westphal
0 siblings, 1 reply; 7+ messages in thread
From: Li,Rongqing @ 2019-02-26 1:15 UTC (permalink / raw)
To: Florian Westphal; +Cc: netfilter-devel
> -----邮件原件-----
> 发件人: Florian Westphal [mailto:fw@strlen.de]
> 发送时间: 2019年2月25日 19:54
> 收件人: Li,Rongqing <lirongqing@baidu.com>
> 抄送: Florian Westphal <fw@strlen.de>; netfilter-devel@vger.kernel.org
> 主题: Re: 答复: [PATCH][nf-next] netfilter: replace modulo operation with
> bitwise AND
>
> Li,Rongqing <lirongqing@baidu.com> wrote:
> >
> >
> > > -----邮件原件-----
> > > 发件人: Florian Westphal [mailto:fw@strlen.de]
> > > 发送时间: 2019年2月25日 19:27
> > > 收件人: Li,Rongqing <lirongqing@baidu.com>
> > > 抄送: netfilter-devel@vger.kernel.org
> > > 主题: Re: [PATCH][nf-next] netfilter: replace modulo operation with
> > > bitwise AND
> > >
> > > Li RongQing <lirongqing@baidu.com> wrote:
> > > > CONNTRACK_LOCKS is 1024 and power of 2, so modulo operations can
> > > > be replaced with AND (CONNTRACK_LOCKS - 1)
> > > >
> > > > and bitwise AND operation is quicker than module operation
> > >
> > > Uh. What kind of compiler doesn't figure that out?!
> > >
> > > I would prefer to keep it as-is and let compiler do the optimization.
> >
> >
> > gcc version 7.3.0 (GCC)
> >
> >
> > main()
> > {
> > int i=1000000000;
> >
> > i= i % 1024;
> >
> > return i;
> > }
> >
> > 00000000004004a7 <main>:
> > 4004a7: 55 push %rbp
> > 4004a8: 48 89 e5 mov %rsp,%rbp
> > 4004ab: c7 45 fc 00 ca 9a 3b movl $0x3b9aca00,-0x4(%rbp)
> > 4004b2: 8b 45 fc mov -0x4(%rbp),%eax
> > 4004b5: 99 cltd
> > 4004b6: c1 ea 16 shr $0x16,%edx
> > 4004b9: 01 d0 add %edx,%eax
> > 4004bb: 25 ff 03 00 00 and $0x3ff,%eax
>
> & 1023.
>
> With -O2 gcc emits same code regardless of % 1024 or & 1023.
>
> > Similar patch:
> >
> > commit 1a1d74d378b13ad3f93e8975a0ade0980a49d28b
> > Author: Jakub Kicinski <jakub.kicinski@netronome.com>
> > Date: Mon Oct 31 20:43:17 2016 +0000
> >
> > nfp: use AND instead of modulo to get ring indexes
>
> But in that case the value isn't known at compile time.
>
> gcc can't know that '= reg1 % reg2' can be rewritten as 'reg1 & (reg2 - 1)'
>
> But it can do it if reg2 is a known constant (and a power of 2).
Thanks, You are right
I think this patches maybe doing two thing:
1. make codes not depend on compiler optimization
2. remind to not change CONNTRACK_LOCKS to a value which is not power of 2
-RongQing
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: 答复: 答复: [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND
2019-02-26 1:15 ` 答复: " Li,Rongqing
@ 2019-02-26 6:31 ` Florian Westphal
2019-02-26 9:20 ` 答复: " Li,Rongqing
0 siblings, 1 reply; 7+ messages in thread
From: Florian Westphal @ 2019-02-26 6:31 UTC (permalink / raw)
To: Li,Rongqing; +Cc: Florian Westphal, netfilter-devel
Li,Rongqing <lirongqing@baidu.com> wrote:
> I think this patches maybe doing two thing:
>
> 1. make codes not depend on compiler optimization
> 2. remind to not change CONNTRACK_LOCKS to a value which is not power of 2
You could add a BUILD_BUG_ON_NOT_POWER_OF_2() check for that.
^ permalink raw reply [flat|nested] 7+ messages in thread
* 答复: 答复: 答复: [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND
2019-02-26 6:31 ` Florian Westphal
@ 2019-02-26 9:20 ` Li,Rongqing
0 siblings, 0 replies; 7+ messages in thread
From: Li,Rongqing @ 2019-02-26 9:20 UTC (permalink / raw)
To: Florian Westphal; +Cc: netfilter-devel
> -----邮件原件-----
> 发件人: Florian Westphal [mailto:fw@strlen.de]
> 发送时间: 2019年2月26日 14:32
> 收件人: Li,Rongqing <lirongqing@baidu.com>
> 抄送: Florian Westphal <fw@strlen.de>; netfilter-devel@vger.kernel.org
> 主题: Re: 答复: 答复: [PATCH][nf-next] netfilter: replace modulo operation
> with bitwise AND
>
> Li,Rongqing <lirongqing@baidu.com> wrote:
> > I think this patches maybe doing two thing:
> >
> > 1. make codes not depend on compiler optimization 2. remind to not
> > change CONNTRACK_LOCKS to a value which is not power of 2
>
> You could add a BUILD_BUG_ON_NOT_POWER_OF_2() check for that.
OK, please drop this patch, I will send a new one based on your advice
-RongQing
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2019-02-26 9:20 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-02-25 11:16 [PATCH][nf-next] netfilter: replace modulo operation with bitwise AND Li RongQing
2019-02-25 11:26 ` Florian Westphal
2019-02-25 11:35 ` 答复: " Li,Rongqing
2019-02-25 11:54 ` Florian Westphal
2019-02-26 1:15 ` 答复: " Li,Rongqing
2019-02-26 6:31 ` Florian Westphal
2019-02-26 9:20 ` 答复: " Li,Rongqing
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.