[RFC] [NETFILTER] nf_conntrack: more efficient helper lookup

[RFC] [NETFILTER] nf_conntrack: more efficient helper lookup

[Harald Welte]

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

Hi!

As Patrick and I discussed about two weeks ago, the linear iteration
over the list of helpers with a full tuple compare per helper is
overkill.

Please review this suggested patch and comment, thanks.

Cheers,
	Harald


[NETFILTER] nf_conntrack: more efficient helper lookup

Instead of iterating over a linear list of helpers, we now keep a hash
table of them.  Also, we restrict helper match lookup to (l3proto, l4proto,
dstport) instead of a full-blown tuple/mask lookup.

Signed-off-by: Harald Welte <laforge@netfilter.org>

---
commit 06d95115655ba6df96d8ad7c92a3d5e91eee39f7
tree 21a21e59e9ce5eccdbafb6026106c49691674dba
parent 904a871a628c42031c3093c2b90bde526f0f35f0
author Harald Welte <laforge@netfilter.org> Wed, 01 Feb 2006 21:29:32 +0100
committer Harald Welte <laforge@netfilter.org> Wed, 01 Feb 2006 21:29:32 +0100

 include/net/netfilter/nf_conntrack_helper.h |   10 ++--
 net/netfilter/nf_conntrack_core.c           |   72 +++++++++++++++++++++++----
 net/netfilter/nf_conntrack_ftp.c            |   12 ++---
 3 files changed, 70 insertions(+), 24 deletions(-)

diff --git a/include/net/netfilter/nf_conntrack_helper.h b/include/net/netfilter/nf_conntrack_helper.h
index 86ec817..3cca3c8 100644
--- a/include/net/netfilter/nf_conntrack_helper.h
+++ b/include/net/netfilter/nf_conntrack_helper.h
@@ -15,7 +15,7 @@ struct module;
 
 struct nf_conntrack_helper
 {	
-	struct list_head list; 		/* Internal use. */
+	struct hlist_node list;		/* Internal use. */
 
 	const char *name;		/* name of the module */
 	struct module *me;		/* pointer to self */
@@ -23,10 +23,10 @@ struct nf_conntrack_helper
 					 * expected connections */
 	unsigned int timeout;		/* timeout for expecteds */
 
-	/* Mask of things we will help (compared against server response) */
-	struct nf_conntrack_tuple tuple;
-	struct nf_conntrack_tuple mask;
-	
+	union nf_conntrack_man_proto l4;
+	u_int8_t l4proto;
+	u_int8_t l3proto;
+
 	/* Function to call when data passes; return verdict, or -1 to
            invalidate. */
 	int (*help)(struct sk_buff **pskb,
diff --git a/net/netfilter/nf_conntrack_core.c b/net/netfilter/nf_conntrack_core.c
index f136e0d..451e8b3 100644
--- a/net/netfilter/nf_conntrack_core.c
+++ b/net/netfilter/nf_conntrack_core.c
@@ -23,6 +23,8 @@
  * 26 Jan 2006: Harald Welte <laforge@netfilter.org>
  * 	- restructure nf_conn (introduce nf_conn_help)
  * 	- redesign 'features' how they were originally intended
+ * 02 Feb 2006: Harald Welte <laforge@netfilter.org>
+ * 	- replace tuple/mask helper lookup by more efficient method
  *
  * Derived from net/ipv4/netfilter/ip_conntrack_core.c
  */
@@ -58,7 +60,7 @@
 #include <net/netfilter/nf_conntrack_core.h>
 #include <linux/netfilter_ipv4/listhelp.h>
 
-#define NF_CONNTRACK_VERSION	"0.5.0"
+#define NF_CONNTRACK_VERSION	"0.5.1"
 
 #if 0
 #define DEBUGP printk
@@ -75,7 +77,6 @@ void (*nf_conntrack_destroyed)(struct nf
 LIST_HEAD(nf_conntrack_expect_list);
 struct nf_conntrack_protocol **nf_ct_protos[PF_MAX];
 struct nf_conntrack_l3proto *nf_ct_l3protos[PF_MAX];
-static LIST_HEAD(helpers);
 unsigned int nf_conntrack_htable_size = 0;
 int nf_conntrack_max;
 struct list_head *nf_conntrack_hash;
@@ -85,6 +86,11 @@ unsigned int nf_ct_log_invalid;
 static LIST_HEAD(unconfirmed);
 static int nf_conntrack_vmalloc;
 
+/* normally the number of helpers is small, so we try to save some cache */
+#define NFCT_HELPER_BUCKETS 	8
+#define NFCT_HELPER_INITVAL	0x23424223
+static struct hlist_head *helpers;
+
 static unsigned int nf_conntrack_next_id = 1;
 static unsigned int nf_conntrack_expect_next_id = 1;
 #ifdef CONFIG_NF_CONNTRACK_EVENTS
@@ -787,18 +793,31 @@ static int early_drop(struct list_head *
 	return dropped;
 }
 
+static unsigned int helper_hashfn(const struct nf_conntrack_tuple *tuple)
+{
+	return jhash_2words(tuple->dst.protonum, tuple->src.u.all, 
+			    NFCT_HELPER_INITVAL) % NFCT_HELPER_BUCKETS;
+}
+
 static inline int helper_cmp(const struct nf_conntrack_helper *i,
 			     const struct nf_conntrack_tuple *rtuple)
 {
-	return nf_ct_tuple_mask_cmp(rtuple, &i->tuple, &i->mask);
+	return ((i->l4proto == rtuple->dst.protonum)
+		&& (i->l3proto == rtuple->src.l3num)
+		&& (i->l4.all == rtuple->src.u.all));
 }
 
 static struct nf_conntrack_helper *
 __nf_ct_helper_find(const struct nf_conntrack_tuple *tuple)
 {
-	return LIST_FIND(&helpers, helper_cmp,
-			 struct nf_conntrack_helper *,
-			 tuple);
+	struct nf_conntrack_helper *h;
+	struct hlist_node *pos;
+
+	hlist_for_each_entry(h, pos, &helpers[helper_hashfn(tuple)], list)
+		if (helper_cmp(h, tuple))
+			return h;
+
+	return NULL;
 }
 
 struct nf_conntrack_helper *
@@ -1283,9 +1302,20 @@ out:
 	return ret;
 }
 
+static void helper2tuple(struct nf_conntrack_tuple *fake_tuple,
+			 const struct nf_conntrack_helper *me)
+{
+	memset(fake_tuple, 0, sizeof(*fake_tuple));
+	fake_tuple->src.l3num = me->l3proto;
+	fake_tuple->dst.protonum = me->l4proto;
+	fake_tuple->dst.u.all = me->l4.all;
+}
+
 int nf_conntrack_helper_register(struct nf_conntrack_helper *me)
 {
 	int ret;
+	struct nf_conntrack_tuple fake_tuple;
+
 	BUG_ON(me->timeout == 0);
 
 	ret = nf_conntrack_register_cache(NF_CT_F_HELP, "nf_conntrack:help",
@@ -1296,8 +1326,11 @@ int nf_conntrack_helper_register(struct 
 		printk(KERN_ERR "nf_conntrack_helper_reigster: Unable to create slab cache for conntracks\n");
 		return ret;
 	}
+
+	helper2tuple(&fake_tuple, me);
+
 	write_lock_bh(&nf_conntrack_lock);
-	list_prepend(&helpers, me);
+	hlist_add_head(&me->list, &helpers[helper_hashfn(&fake_tuple)]);
 	write_unlock_bh(&nf_conntrack_lock);
 
 	return 0;
@@ -1306,11 +1339,16 @@ int nf_conntrack_helper_register(struct 
 struct nf_conntrack_helper *
 __nf_conntrack_helper_find_byname(const char *name)
 {
-	struct nf_conntrack_helper *h;
+	unsigned int i;
 
-	list_for_each_entry(h, &helpers, list) {
-		if (!strcmp(h->name, name))
-			return h;
+	for (i = 0; i < NFCT_HELPER_BUCKETS; i++) {
+		struct nf_conntrack_helper *h;
+		struct hlist_node *pos;
+
+		hlist_for_each_entry(h, pos, &helpers[i], list) {
+			if (!strcmp(h->name, name))
+				return h;
+		}
 	}
 
 	return NULL;
@@ -1333,10 +1371,13 @@ void nf_conntrack_helper_unregister(stru
 {
 	unsigned int i;
 	struct nf_conntrack_expect *exp, *tmp;
+	struct nf_conntrack_tuple fake_tuple;
+
+	helper2tuple(&fake_tuple, me);
 
 	/* Need write lock here, to delete helper. */
 	write_lock_bh(&nf_conntrack_lock);
-	LIST_DELETE(&helpers, me);
+	hlist_del(&me->list);
 
 	/* Get rid of expectations */
 	list_for_each_entry_safe(exp, tmp, &nf_conntrack_expect_list, list) {
@@ -1694,6 +1735,11 @@ int __init nf_conntrack_init(void)
 		goto err_free_conntrack_slab;
 	}
 
+	helpers = kmalloc(sizeof(struct hlist_head) * NFCT_HELPER_BUCKETS,
+			  GFP_KERNEL);
+	if (!helpers)
+		goto err_free_expect_slab;
+
 	/* Don't NEED lock here, but good form anyway. */
 	write_lock_bh(&nf_conntrack_lock);
         for (i = 0; i < PF_MAX; i++)
@@ -1708,6 +1754,8 @@ int __init nf_conntrack_init(void)
 
 	return ret;
 
+err_free_expect_slab:
+	kmem_cache_destroy(nf_conntrack_expect_cachep);
 err_free_conntrack_slab:
 	nf_conntrack_unregister_cache(NF_CT_F_BASIC);
 err_free_hash:
diff --git a/net/netfilter/nf_conntrack_ftp.c b/net/netfilter/nf_conntrack_ftp.c
index 280c5c2..daff4d3 100644
--- a/net/netfilter/nf_conntrack_ftp.c
+++ b/net/netfilter/nf_conntrack_ftp.c
@@ -659,13 +659,11 @@ static int __init init(void)
 	for (i = 0; i < ports_c; i++) {
 		memset(&ftp[i], 0, sizeof(struct nf_conntrack_helper));
 
-		ftp[i][0].tuple.src.l3num = PF_INET;
-		ftp[i][1].tuple.src.l3num = PF_INET6;
+		ftp[i][0].l3proto = PF_INET;
+		ftp[i][1].l3proto = PF_INET6;
 		for (j = 0; j < 2; j++) {
-			ftp[i][j].tuple.src.u.tcp.port = htons(ports[i]);
-			ftp[i][j].tuple.dst.protonum = IPPROTO_TCP;
-			ftp[i][j].mask.src.u.tcp.port = 0xFFFF;
-			ftp[i][j].mask.dst.protonum = 0xFF;
+			ftp[i][j].l4.tcp.port = htons(ports[i]);
+			ftp[i][j].l4proto = IPPROTO_TCP;
 			ftp[i][j].max_expected = 1;
 			ftp[i][j].timeout = 5 * 60;	/* 5 Minutes */
 			ftp[i][j].me = THIS_MODULE;
@@ -684,7 +682,7 @@ static int __init init(void)
 			if (ret) {
 				printk("nf_ct_ftp: failed to register helper "
 				       " for pf: %d port: %d\n",
-					ftp[i][j].tuple.src.l3num, ports[i]);
+					ftp[i][j].l3proto, ports[i]);
 				fini();
 				return ret;
 			}
-- 
- Harald Welte <laforge@netfilter.org>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC] [NETFILTER] nf_conntrack: more efficient helper lookup

[Pablo Neira Ayuso]

Hi Harald,

Harald Welte wrote:
> As Patrick and I discussed about two weeks ago, the linear iteration
> over the list of helpers with a full tuple compare per helper is
> overkill.
> 
> Please review this suggested patch and comment, thanks.
> 
> Cheers,
> 	Harald
> 
> 
> [NETFILTER] nf_conntrack: more efficient helper lookup
> 
> Instead of iterating over a linear list of helpers, we now keep a hash
> table of them.  Also, we restrict helper match lookup to (l3proto, l4proto,
> dstport) instead of a full-blown tuple/mask lookup.
> 
> Signed-off-by: Harald Welte <laforge@netfilter.org>
> 
> ---
> commit 06d95115655ba6df96d8ad7c92a3d5e91eee39f7
> tree 21a21e59e9ce5eccdbafb6026106c49691674dba
> parent 904a871a628c42031c3093c2b90bde526f0f35f0
> author Harald Welte <laforge@netfilter.org> Wed, 01 Feb 2006 21:29:32 +0100
> committer Harald Welte <laforge@netfilter.org> Wed, 01 Feb 2006 21:29:32 +0100
> 
>  include/net/netfilter/nf_conntrack_helper.h |   10 ++--
>  net/netfilter/nf_conntrack_core.c           |   72 +++++++++++++++++++++++----
>  net/netfilter/nf_conntrack_ftp.c            |   12 ++---
>  3 files changed, 70 insertions(+), 24 deletions(-)
> 
> diff --git a/include/net/netfilter/nf_conntrack_helper.h b/include/net/netfilter/nf_conntrack_helper.h
> index 86ec817..3cca3c8 100644
> --- a/include/net/netfilter/nf_conntrack_helper.h
> +++ b/include/net/netfilter/nf_conntrack_helper.h
> @@ -15,7 +15,7 @@ struct module;
>  
>  struct nf_conntrack_helper
>  {	
> -	struct list_head list; 		/* Internal use. */
> +	struct hlist_node list;		/* Internal use. */
>  
>  	const char *name;		/* name of the module */
>  	struct module *me;		/* pointer to self */
> @@ -23,10 +23,10 @@ struct nf_conntrack_helper
>  					 * expected connections */
>  	unsigned int timeout;		/* timeout for expecteds */
>  
> -	/* Mask of things we will help (compared against server response) */
> -	struct nf_conntrack_tuple tuple;
> -	struct nf_conntrack_tuple mask;
> -	
> +	union nf_conntrack_man_proto l4;
> +	u_int8_t l4proto;
> +	u_int8_t l3proto;

Just a remark if this patch goes forward. The bits to make
nf_conntrack_netlink work with this new layout are still missing :(.
Anyway this is not the point now ;)

>  	/* Function to call when data passes; return verdict, or -1 to
>             invalidate. */
>  	int (*help)(struct sk_buff **pskb,
> diff --git a/net/netfilter/nf_conntrack_core.c b/net/netfilter/nf_conntrack_core.c
> index f136e0d..451e8b3 100644
> --- a/net/netfilter/nf_conntrack_core.c
> +++ b/net/netfilter/nf_conntrack_core.c
> @@ -23,6 +23,8 @@
>   * 26 Jan 2006: Harald Welte <laforge@netfilter.org>
>   * 	- restructure nf_conn (introduce nf_conn_help)
>   * 	- redesign 'features' how they were originally intended
> + * 02 Feb 2006: Harald Welte <laforge@netfilter.org>
> + * 	- replace tuple/mask helper lookup by more efficient method
>   *
>   * Derived from net/ipv4/netfilter/ip_conntrack_core.c
>   */
> @@ -58,7 +60,7 @@
>  #include <net/netfilter/nf_conntrack_core.h>
>  #include <linux/netfilter_ipv4/listhelp.h>
>  
> -#define NF_CONNTRACK_VERSION	"0.5.0"
> +#define NF_CONNTRACK_VERSION	"0.5.1"
>  
>  #if 0
>  #define DEBUGP printk
> @@ -75,7 +77,6 @@ void (*nf_conntrack_destroyed)(struct nf
>  LIST_HEAD(nf_conntrack_expect_list);
>  struct nf_conntrack_protocol **nf_ct_protos[PF_MAX];
>  struct nf_conntrack_l3proto *nf_ct_l3protos[PF_MAX];
> -static LIST_HEAD(helpers);
>  unsigned int nf_conntrack_htable_size = 0;
>  int nf_conntrack_max;
>  struct list_head *nf_conntrack_hash;
> @@ -85,6 +86,11 @@ unsigned int nf_ct_log_invalid;
>  static LIST_HEAD(unconfirmed);
>  static int nf_conntrack_vmalloc;
>  
> +/* normally the number of helpers is small, so we try to save some cache */
> +#define NFCT_HELPER_BUCKETS 	8
> +#define NFCT_HELPER_INITVAL	0x23424223
> +static struct hlist_head *helpers;

Since the number of helpers is really small, I'm not sure about the
benefits of this patch. The hash calculation adds a constant to the
algorithm complexity that could result in a similar execution time for
this and the current approach. A benchmark could throw some light on this.

What about just killing the tuple and mask fields and keep the current
approach of the helper list?

-- 
Pablo

Re: [RFC] [NETFILTER] nf_conntrack: more efficient helper lookup

[Balazs Scheidler]

On Sun, 2006-02-12 at 22:25 +0100, Pablo Neira Ayuso wrote:

> Since the number of helpers is really small, I'm not sure about the
> benefits of this patch. The hash calculation adds a constant to the
> algorithm complexity that could result in a similar execution time for
> this and the current approach. A benchmark could throw some light on this.
> 
> What about just killing the tuple and mask fields and keep the current
> approach of the helper list?

Maybe a simple dynamically sized array of helper structures would be
more cache friendly instead of the linked list. IIRC hipac used arrays
instead of lists/hashtables for the very same reason.

A single helper would be no more than 8 bytes (l3proto, l4proto
dstproto, pointer to helper structure), maybe we can also skip the
dynamically allocated part. Statically allocated 256 bytes (a single
cacheline!) would be enough for 32 helpers which is plenty.

-- 
Bazsi

Re: [RFC] [NETFILTER] nf_conntrack: more efficient helper lookup

[Harald Welte]

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

On Sun, Feb 12, 2006 at 10:25:58PM +0100, Pablo Neira Ayuso wrote:

> Just a remark if this patch goes forward. The bits to make
> nf_conntrack_netlink work with this new layout are still missing :(.
> Anyway this is not the point now ;)

yes, thanks for the reminder.

> > +/* normally the number of helpers is small, so we try to save some cache */
> > +#define NFCT_HELPER_BUCKETS 	8
> > +#define NFCT_HELPER_INITVAL	0x23424223
> > +static struct hlist_head *helpers;
> 
> Since the number of helpers is really small, I'm not sure about the
> benefits of this patch. The hash calculation adds a constant to the
> algorithm complexity that could result in a similar execution time for
> this and the current approach. A benchmark could throw some light on this.

Yes.  Some thoughts:

First, I tried with some easy modulo hashing in order to save some
overhed, but the distribution of the existing helper port numbers was
not very good in such a hash :(

The number of registered helpers is expected to grow quite a lot in the
near future, when userspace helpers will exist.

> What about just killing the tuple and mask fields and keep the current
> approach of the helper list?

Even if we only have three or four helpers loaded, for every new
connection we iterate over all four helpers just to know that we have no
helper for this connection.  Since every helper is in a separate kernel
module, that's four more cache misses for every new connection.

A hash table [with a good distribution and reasonable size] should get
that down to an average of 1 for every new connection.  Maybe the bucket
heads are already in cache, and for the most common case (no helper) we
get the lookup almost for free.

So I still think it's worth the effort, even though jenkins hash might
be overkill.

If anybody wants to do benchmarks on this, I'm very eager to see the
results.



What is a way bigger problem is the expectation matching (all expecteds
are one linked list).  In a loaded real world system, chances are high
that the number of expectations is way bigger than the number of
helpers.  Also, a system can easily be forced into a high number of
expectations (by creating dozens of masters with one unconfirmed expect
each).

Patrick and I had some thoughs on this, but the problem is reasonably
non-trivial.  We cannot fully avoid the tuple/mask matching, which
precludes something like an easy hash table.

The intermediate conclusion was to dynamically keep track of which masks
helpers use to register their expectations, and then create one hash
table per mask.  So in the end we would have N lookups into N different
hash tables when we have N different masks.

Maybe we can even just use different hash functions and hash into one
table, that's not fully thought through yet.

Also, it helps to cut back on the number of possible choices.  A helper
is unlikely to use anything else but 0 or 0xffff for a port number, so
we can reduce the port numbers to 2 bits (1 source, 1 dest).

As for IP addresses, all but the netbios helper use only 0 or
0xffffffff, so they could be restricted to 1 bit, too.  This would only
mean 5 bit of different masks, a total of 32 lookups in the very 
unrealistic worst case.

As for the netbios helper, we probably need to keep the linear list
around as a fallback.

This sounds a bit complicated, but it's the best we've been able to come
up with so far.  There's definitely the need to optimize the expect
lookup. though.

-- 
- Harald Welte <laforge@netfilter.org>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]