Skip to contentSkip to conversation

netfilter: conntrack: prepare for hashtable merge, take 1

PATCH In review Florian Westphal 3 participants 9 messages Apr 18, 2016 – Apr 25, 2016

Subsystems (2)
lore
Share & tools
lore

Florian Westphal

author maintainer
#0 lore raw

cover netfilter: conntrack: prepare for hashtable merge, take 1

This small series prepares for upcoming merge of the per-namespace hash tables into a single table (or rater, three tables
-- conntrack hash, expect hash and nat bysrc hash).

Arguments for merging it:
- We stop wasting (assuming default size) 250k backing store per namespace
- net namespace is just another part of the connection id, much like ip addresses or conntrack zones -- no need to treat it specially
- allows to get rid of the per-netns conntrack slab as well

These patches are first preparations.
We replace per-netns conntrack has generation seqcount by single one.

While at it, this replaces the method used to obtain the hash seed by the (nowadays) more common get_random_once().

author maintainer
#1 lore raw

PATCH 1/3 netfilter: conntrack: move generation seqcnt out of netns_ct

We only allow rehash in init namespace, so we only use init_ns.generation. And even if we would allow it, it makes no sense as the conntrack locks are global; any ongoing rehash prevents insert/ delete.

So make this private to nf_conntrack_core instead.

---
 include/net/netns/conntrack.h     |  1 -
 net/netfilter/nf_conntrack_core.c | 20 +++++++++++---------
 2 files changed, 11 insertions(+), 10 deletions(-)
include/net/netns/conntrack.h +0 -1
index 723b61c..b052785 100644
@@ -94,7 +94,6 @@ struct netns_ct {
 	int			sysctl_checksum;
 
 	unsigned int		htable_size;
-	seqcount_t		generation;
 	struct kmem_cache	*nf_conntrack_cachep;
 	struct hlist_nulls_head	*hash;
 	struct hlist_head	*expect_hash;
net/netfilter/nf_conntrack_core.c +11 -9
index 2fd6074..a53c009 100644
@@ -69,6 +69,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(nf_conntrack_expect_lock);
 EXPORT_SYMBOL_GPL(nf_conntrack_expect_lock);
 
 static __read_mostly spinlock_t nf_conntrack_locks_all_lock;
+static __read_mostly seqcount_t nf_conntrack_generation;
 static __read_mostly bool nf_conntrack_locks_all;
 
 void nf_conntrack_lock(spinlock_t *lock) __acquires(lock)
@@ -107,7 +108,7 @@ static bool nf_conntrack_double_lock(struct net *net, unsigned int h1,
 		spin_lock_nested(&nf_conntrack_locks[h1],
 				 SINGLE_DEPTH_NESTING);
 	}
-	if (read_seqcount_retry(&net->ct.generation, sequence)) {
+	if (read_seqcount_retry(&nf_conntrack_generation, sequence)) {
 		nf_conntrack_double_unlock(h1, h2);
 		return true;
 	}
@@ -393,7 +394,7 @@ static void nf_ct_delete_from_lists(struct nf_conn *ct)
 
 	local_bh_disable();
 	do {
-		sequence = read_seqcount_begin(&net->ct.generation);
+		sequence = read_seqcount_begin(&nf_conntrack_generation);
 		hash = hash_conntrack(net,
 				      &ct->tuplehash[IP_CT_DIR_ORIGINAL].tuple);
 		reply_hash = hash_conntrack(net,
@@ -560,7 +561,7 @@ nf_conntrack_hash_check_insert(struct nf_conn *ct)
 
 	local_bh_disable();
 	do {
-		sequence = read_seqcount_begin(&net->ct.generation);
+		sequence = read_seqcount_begin(&nf_conntrack_generation);
 		hash = hash_conntrack(net,
 				      &ct->tuplehash[IP_CT_DIR_ORIGINAL].tuple);
 		reply_hash = hash_conntrack(net,
@@ -628,7 +629,7 @@ __nf_conntrack_confirm(struct sk_buff *skb)
 	local_bh_disable();
 
 	do {
-		sequence = read_seqcount_begin(&net->ct.generation);
+		sequence = read_seqcount_begin(&nf_conntrack_generation);
 		/* reuse the hash saved before */
 		hash = *(unsigned long *)&ct->tuplehash[IP_CT_DIR_REPLY].hnnode.pprev;
 		hash = hash_bucket(hash, net);
@@ -771,12 +772,12 @@ static noinline int early_drop(struct net *net, unsigned int _hash)
 
 	local_bh_disable();
 restart:
-	sequence = read_seqcount_begin(&net->ct.generation);
+	sequence = read_seqcount_begin(&nf_conntrack_generation);
 	hash = hash_bucket(_hash, net);
 	for (; i < net->ct.htable_size; i++) {
 		lockp = &nf_conntrack_locks[hash % CONNTRACK_LOCKS];
 		nf_conntrack_lock(lockp);
-		if (read_seqcount_retry(&net->ct.generation, sequence)) {
+		if (read_seqcount_retry(&nf_conntrack_generation, sequence)) {
 			spin_unlock(lockp);
 			goto restart;
 		}
@@ -1607,7 +1608,7 @@ int nf_conntrack_set_hashsize(const char *val, struct kernel_param *kp)
 
 	local_bh_disable();
 	nf_conntrack_all_lock();
-	write_seqcount_begin(&init_net.ct.generation);
+	write_seqcount_begin(&nf_conntrack_generation);
 
 	/* Lookups in the old hash might happen in parallel, which means we
 	 * might get false negatives during connection lookup. New connections
@@ -1631,7 +1632,7 @@ int nf_conntrack_set_hashsize(const char *val, struct kernel_param *kp)
 	init_net.ct.htable_size = nf_conntrack_htable_size = hashsize;
 	init_net.ct.hash = hash;
 
-	write_seqcount_end(&init_net.ct.generation);
+	write_seqcount_end(&nf_conntrack_generation);
 	nf_conntrack_all_unlock();
 	local_bh_enable();
 
@@ -1657,6 +1658,8 @@ int nf_conntrack_init_start(void)
 	int max_factor = 8;
 	int i, ret, cpu;
 
+	seqcount_init(&nf_conntrack_generation);
+
 	for (i = 0; i < CONNTRACK_LOCKS; i++)
 		spin_lock_init(&nf_conntrack_locks[i]);
 
@@ -1783,7 +1786,6 @@ int nf_conntrack_init_net(struct net *net)
 	int cpu;
 
 	atomic_set(&net->ct.count, 0);
-	seqcount_init(&net->ct.generation);
 
 	net->ct.pcpu_lists = alloc_percpu(struct ct_pcpu);
 	if (!net->ct.pcpu_lists)
Signature · 1 line
2.7.3
author maintainer
#2 lore raw

PATCH 2/3 netfilter: conntrack: use get_random_once for nat and expectations

In reply to Florian Westphal

Use a private seed and init it using get_random_once.

---
 net/netfilter/nf_conntrack_expect.c | 7 +++----
 net/netfilter/nf_nat_core.c         | 6 ++++--
 2 files changed, 7 insertions(+), 6 deletions(-)
net/netfilter/nf_conntrack_expect.c +3 -4
index 278927a..c2f7c4f 100644
@@ -38,6 +38,7 @@ EXPORT_SYMBOL_GPL(nf_ct_expect_hsize);
 unsigned int nf_ct_expect_max __read_mostly;
 
 static struct kmem_cache *nf_ct_expect_cachep __read_mostly;
+static unsigned int nf_ct_expect_hashrnd __read_mostly;
 
 /* nf_conntrack_expect helper functions */
 void nf_ct_unlink_expect_report(struct nf_conntrack_expect *exp,
@@ -76,13 +77,11 @@ static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple
 {
 	unsigned int hash;
 
-	if (unlikely(!nf_conntrack_hash_rnd)) {
-		init_nf_conntrack_hash_rnd();
-	}
+	get_random_once(&nf_ct_expect_hashrnd, sizeof(nf_ct_expect_hashrnd));
 
 	hash = jhash2(tuple->dst.u3.all, ARRAY_SIZE(tuple->dst.u3.all),
 		      (((tuple->dst.protonum ^ tuple->src.l3num) << 16) |
-		       (__force __u16)tuple->dst.u.all) ^ nf_conntrack_hash_rnd);
+		       (__force __u16)tuple->dst.u.all) ^ nf_ct_expect_hashrnd);
 
 	return reciprocal_scale(hash, nf_ct_expect_hsize);
 }
net/netfilter/nf_nat_core.c +4 -2
index 06a9f45..3d52271 100644
@@ -37,7 +37,7 @@ static const struct nf_nat_l3proto __rcu *nf_nat_l3protos[NFPROTO_NUMPROTO]
 						__read_mostly;
 static const struct nf_nat_l4proto __rcu **nf_nat_l4protos[NFPROTO_NUMPROTO]
 						__read_mostly;
-
+static unsigned int nf_nat_hash_rnd __read_mostly;
 
 inline const struct nf_nat_l3proto *
 __nf_nat_l3proto_find(u8 family)
@@ -122,9 +122,11 @@ hash_by_src(const struct net *net, const struct nf_conntrack_tuple *tuple)
 {
 	unsigned int hash;
 
+	get_random_once(&nf_nat_hash_rnd, sizeof(nf_nat_hash_rnd));
+
 	/* Original src, to ensure we map it consistently if poss. */
 	hash = jhash2((u32 *)&tuple->src, sizeof(tuple->src) / sizeof(u32),
-		      tuple->dst.protonum ^ nf_conntrack_hash_rnd);
+		      tuple->dst.protonum ^ nf_nat_hash_rnd);
 
 	return reciprocal_scale(hash, net->ct.nat_htable_size);
 }
Signature · 1 line
2.7.3
#3 lore raw

Re: [PATCH nf-next 2/3] netfilter: conntrack: use get_random_once for nat and expectations

Hi Florian,

Quoted 21 lines · Florian Westphal

Use a private seed and init it using get_random_once.

---
 net/netfilter/nf_conntrack_expect.c | 7 +++----
 net/netfilter/nf_nat_core.c         | 6 ++++--
 2 files changed, 7 insertions(+), 6 deletions(-)
net/netfilter/nf_conntrack_expect.c +1 -0
index 278927a..c2f7c4f 100644
@@ -38,6 +38,7 @@ EXPORT_SYMBOL_GPL(nf_ct_expect_hsize);
 unsigned int nf_ct_expect_max __read_mostly;
 
 static struct kmem_cache *nf_ct_expect_cachep __read_mostly;
+static unsigned int nf_ct_expect_hashrnd __read_mostly;
 
 /* nf_conntrack_expect helper functions */
 void nf_ct_unlink_expect_report(struct nf_conntrack_expect *exp,

net/netfilter/nf_conntrack_expect.c static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple · line 80

Quoted 7 lines
net/netfilter/nf_conntrack_expect.c +1 -3
@@ -76,13 +77,11 @@ static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple
 {
 	unsigned int hash;
 
-	if (unlikely(!nf_conntrack_hash_rnd)) {
-		init_nf_conntrack_hash_rnd();
-	}
+	get_random_once(&nf_ct_expect_hashrnd, sizeof(nf_ct_expect_hashrnd));

Not related to your patch, but to the underlying infrastructure: I can see get_random_once() implementation uses static_key_true() branch check.

Shouldn't this be static_key_false() instead? On architectures with not jump_labels support, this will translate to unlikely().

If so, I can send a patch for this. I can see this DO_ONCE() API is also using the deprecated interfaces.

author maintainer
#4 lore raw

Re: [PATCH nf-next 2/3] netfilter: conntrack: use get_random_once for nat and expectations

Pablo Neira Ayuso <[email protected]> wrote:

[ CC Hannes ]

Quoted 34 lines · Florian Westphal
Quoted 21 lines

Use a private seed and init it using get_random_once.

---
 net/netfilter/nf_conntrack_expect.c | 7 +++----
 net/netfilter/nf_nat_core.c         | 6 ++++--
 2 files changed, 7 insertions(+), 6 deletions(-)
net/netfilter/nf_conntrack_expect.c +1 -0
index 278927a..c2f7c4f 100644
@@ -38,6 +38,7 @@ EXPORT_SYMBOL_GPL(nf_ct_expect_hsize);
 unsigned int nf_ct_expect_max __read_mostly;
 
 static struct kmem_cache *nf_ct_expect_cachep __read_mostly;
+static unsigned int nf_ct_expect_hashrnd __read_mostly;
 
 /* nf_conntrack_expect helper functions */
 void nf_ct_unlink_expect_report(struct nf_conntrack_expect *exp,

net/netfilter/nf_conntrack_expect.c static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple · line 80

Quoted 7 lines
net/netfilter/nf_conntrack_expect.c +1 -3
@@ -76,13 +77,11 @@ static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple
 {
 	unsigned int hash;
 
-	if (unlikely(!nf_conntrack_hash_rnd)) {
-		init_nf_conntrack_hash_rnd();
-	}
+	get_random_once(&nf_ct_expect_hashrnd, sizeof(nf_ct_expect_hashrnd));

Not related to your patch, but to the underlying infrastructure: I can see get_random_once() implementation uses static_key_true() branch check.

Quoted 2 lines

Shouldn't this be static_key_false() instead? On architectures with not jump_labels support, this will translate to unlikely().

Yes, looks like it. Hannes?

Quoted 2 lines

If so, I can send a patch for this. I can see this DO_ONCE() API is also using the deprecated interfaces.

I think it just predates the new api.

#5 lore raw

Re: [PATCH nf-next 2/3] netfilter: conntrack: use get_random_once for nat and expectations

Hello,

Quoted 38 lines · Florian Westphal

Pablo Neira Ayuso <[email protected]> wrote:

[ CC Hannes ]

Quoted 34 lines · Florian Westphal
Quoted 21 lines

Use a private seed and init it using get_random_once.

---
 net/netfilter/nf_conntrack_expect.c | 7 +++----
 net/netfilter/nf_nat_core.c         | 6 ++++--
 2 files changed, 7 insertions(+), 6 deletions(-)
net/netfilter/nf_conntrack_expect.c +1 -0
index 278927a..c2f7c4f 100644
@@ -38,6 +38,7 @@ EXPORT_SYMBOL_GPL(nf_ct_expect_hsize);
 unsigned int nf_ct_expect_max __read_mostly;
 
 static struct kmem_cache *nf_ct_expect_cachep __read_mostly;
+static unsigned int nf_ct_expect_hashrnd __read_mostly;
 
 /* nf_conntrack_expect helper functions */
 void nf_ct_unlink_expect_report(struct nf_conntrack_expect *exp,

net/netfilter/nf_conntrack_expect.c static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple · line 80

Quoted 7 lines
net/netfilter/nf_conntrack_expect.c +1 -3
@@ -76,13 +77,11 @@ static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple
 {
 	unsigned int hash;
 
-	if (unlikely(!nf_conntrack_hash_rnd)) {
-		init_nf_conntrack_hash_rnd();
-	}
+	get_random_once(&nf_ct_expect_hashrnd, sizeof(nf_ct_expect_hashrnd));

Not related to your patch, but to the underlying infrastructure: I can see get_random_once() implementation uses static_key_true() branch check.

Quoted 4 lines
Quoted 2 lines

Shouldn't this be static_key_false() instead? On architectures with not jump_labels support, this will translate to unlikely().

Yes, looks like it. Hannes?

The code is a bit tricky but still looks correct to me.

static_keys are only allowed to be used in two ways:

static_key_false()/INIT_FALSE -> after boot the hook is disabled and the branch is unlikely
static_key_true()/INIT_TRUE -> after book the hook is enabled and the branch is likely

I actually need the following: after boot the hook is enabled *but* the branch is unlikely, but this isn't really implemented in the jump_label api and wouldn't be that easy.

I worked around this but Linus suggested that likely/unlikely doesn't really matter that much on modern CPUs and I should simply use static_key_true instead. The unlikely is the wrong annotation for this particular case but the static keys internally do automatic the right thing. We just have an unconditional jump instead of a nop in case of the fast path right now.

If we really would like to improve that we would need to extend the static key state, which doesn't seem worthwhile for that.

Quoted 5 lines
Quoted 2 lines

If so, I can send a patch for this. I can see this DO_ONCE() API is also using the deprecated interfaces.

I think it just predates the new api.

Yes, that is true, we could upgrade to the new API. But also with the new API all the above still holds and we still end up having the wrong likely/unlikely.

Bye,
Hannes

#6 lore raw

Re: [PATCH nf-next 2/3] netfilter: conntrack: use get_random_once for nat and expectations

Quoted 72 lines · Hannes Frederic Sowa

Hello,

Quoted 38 lines · Florian Westphal

Pablo Neira Ayuso <[email protected]> wrote:

[ CC Hannes ]

Quoted 34 lines · Florian Westphal
Quoted 21 lines

Use a private seed and init it using get_random_once.

---
 net/netfilter/nf_conntrack_expect.c | 7 +++----
 net/netfilter/nf_nat_core.c         | 6 ++++--
 2 files changed, 7 insertions(+), 6 deletions(-)
net/netfilter/nf_conntrack_expect.c +1 -0
index 278927a..c2f7c4f 100644
@@ -38,6 +38,7 @@ EXPORT_SYMBOL_GPL(nf_ct_expect_hsize);
 unsigned int nf_ct_expect_max __read_mostly;
 
 static struct kmem_cache *nf_ct_expect_cachep __read_mostly;
+static unsigned int nf_ct_expect_hashrnd __read_mostly;
 
 /* nf_conntrack_expect helper functions */
 void nf_ct_unlink_expect_report(struct nf_conntrack_expect *exp,

net/netfilter/nf_conntrack_expect.c static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple · line 80

Quoted 7 lines
net/netfilter/nf_conntrack_expect.c +1 -3
@@ -76,13 +77,11 @@ static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple
 {
 	unsigned int hash;
 
-	if (unlikely(!nf_conntrack_hash_rnd)) {
-		init_nf_conntrack_hash_rnd();
-	}
+	get_random_once(&nf_ct_expect_hashrnd, sizeof(nf_ct_expect_hashrnd));

Not related to your patch, but to the underlying infrastructure: I can see get_random_once() implementation uses static_key_true() branch check.

Quoted 4 lines
Quoted 2 lines

Shouldn't this be static_key_false() instead? On architectures with not jump_labels support, this will translate to unlikely().

Yes, looks like it. Hannes?

The code is a bit tricky but still looks correct to me.

static_keys are only allowed to be used in two ways:

static_key_false()/INIT_FALSE -> after boot the hook is disabled and the branch is unlikely
static_key_true()/INIT_TRUE -> after book the hook is enabled and the branch is likely

I actually need the following: after boot the hook is enabled *but* the branch is unlikely, but this isn't really implemented in the jump_label api and wouldn't be that easy.

I worked around this but Linus suggested that likely/unlikely doesn't really matter that much on modern CPUs and I should simply use static_key_true instead. The unlikely is the wrong annotation for this particular case but the static keys internally do automatic the right thing. We just have an unconditional jump instead of a nop in case of the fast path right now.

If we really would like to improve that we would need to extend the static key state, which doesn't seem worthwhile for that.

Quoted 3 lines
Quoted 2 lines

If so, I can send a patch for this. I can see this DO_ONCE() API is also using the deprecated interfaces.

Quoted 6 lines
Quoted 2 lines

I think it just predates the new api.

Yes, that is true, we could upgrade to the new API. But also with the new API all the above still holds and we still end up having the wrong likely/unlikely.

I just updated myself about the new API and we now can actually express the correct intention and state. If no one is already working on that, I can provide a patch to update net_get_random_once to the new API.

Thanks,
Hannes

author maintainer
#7 lore raw

PATCH 3/3 netfilter: conntrack: use get_random_once for conntrack hash seed

In reply to Florian Westphal

As earlier commit removed accessed to the hash from other files we can also make it static.

---
 include/net/netfilter/nf_conntrack.h |  2 --
 net/netfilter/nf_conntrack_core.c    | 26 +++-----------------------
 2 files changed, 3 insertions(+), 25 deletions(-)
include/net/netfilter/nf_conntrack.h +0 -2
index fde4068..dd78bea 100644
@@ -289,8 +289,6 @@ struct kernel_param;
 int nf_conntrack_set_hashsize(const char *val, struct kernel_param *kp);
 extern unsigned int nf_conntrack_htable_size;
 extern unsigned int nf_conntrack_max;
-extern unsigned int nf_conntrack_hash_rnd;
-void init_nf_conntrack_hash_rnd(void);
 
 struct nf_conn *nf_ct_tmpl_alloc(struct net *net,
 				 const struct nf_conntrack_zone *zone,
net/netfilter/nf_conntrack_core.c +3 -23
index a53c009..1fd0ff1 100644
@@ -142,13 +142,14 @@ EXPORT_SYMBOL_GPL(nf_conntrack_max);
 DEFINE_PER_CPU(struct nf_conn, nf_conntrack_untracked);
 EXPORT_PER_CPU_SYMBOL(nf_conntrack_untracked);
 
-unsigned int nf_conntrack_hash_rnd __read_mostly;
-EXPORT_SYMBOL_GPL(nf_conntrack_hash_rnd);
+static unsigned int nf_conntrack_hash_rnd __read_mostly;
 
 static u32 hash_conntrack_raw(const struct nf_conntrack_tuple *tuple)
 {
 	unsigned int n;
 
+	get_random_once(&nf_conntrack_hash_rnd, sizeof(nf_conntrack_hash_rnd));
+
 	/* The direction must be ignored, so we hash everything up to the
 	 * destination ports (which is a multiple of 4) and treat the last
 	 * three bytes manually.
@@ -815,21 +816,6 @@ restart:
 	return dropped;
 }
 
-void init_nf_conntrack_hash_rnd(void)
-{
-	unsigned int rand;
-
-	/*
-	 * Why not initialize nf_conntrack_rnd in a "init()" function ?
-	 * Because there isn't enough entropy when system initializing,
-	 * and we initialize it as late as possible.
-	 */
-	do {
-		get_random_bytes(&rand, sizeof(rand));
-	} while (!rand);
-	cmpxchg(&nf_conntrack_hash_rnd, 0, rand);
-}
-
 static struct nf_conn *
 __nf_conntrack_alloc(struct net *net,
 		     const struct nf_conntrack_zone *zone,
@@ -839,12 +825,6 @@ __nf_conntrack_alloc(struct net *net,
 {
 	struct nf_conn *ct;
 
-	if (unlikely(!nf_conntrack_hash_rnd)) {
-		init_nf_conntrack_hash_rnd();
-		/* recompute the hash as nf_conntrack_hash_rnd is initialized */
-		hash = hash_conntrack_raw(orig);
-	}
-
 	/* We don't want any race condition at early drop stage */
 	atomic_inc(&net->ct.count);
 
Signature · 1 line
2.7.3
#8 lore raw
In reply to Florian Westphal
Quoted 10 lines · Florian Westphal

This small series prepares for upcoming merge of the per-namespace hash tables into a single table (or rater, three tables
-- conntrack hash, expect hash and nat bysrc hash).

Arguments for merging it:
- We stop wasting (assuming default size) 250k backing store per namespace
- net namespace is just another part of the connection id, much like ip addresses or conntrack zones -- no need to treat it specially
- allows to get rid of the per-netns conntrack slab as well

Quoted 5 lines

These patches are first preparations.
We replace per-netns conntrack has generation seqcount by single one.

While at it, this replaces the method used to obtain the hash seed by the (nowadays) more common get_random_once().

Series applied, thanks Florian.