Skip to contentSkip to conversation

nf_conntrack: more efficient helper lookup

RFC In review Harald Welte 3 participants 4 messages Feb 12, 2006 – Feb 13, 2006

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

RFC 1/1 nf_conntrack: more efficient helper lookup

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.

---
commit 06d95115655ba6df96d8ad7c92a3d5e91eee39f7
tree 21a21e59e9ce5eccdbafb6026106c49691674dba
parent 904a871a628c42031c3093c2b90bde526f0f35f0
author Harald Welte <[email protected]> Wed, 01 Feb 2006 21:29:32 +0100 committer Harald Welte <[email protected]> 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(-)
include/net/netfilter/nf_conntrack_helper.h +5 -5
index 86ec817..3cca3c8 100644
@@ -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,
net/netfilter/nf_conntrack_core.c +60 -12

154 lines not on this page · raw message

net/netfilter/nf_conntrack_ftp.c +5 -7
index 280c5c2..daff4d3 100644
@@ -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;
 			}
Signature · 5 lines
- Harald Welte <[email protected]>                 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
#1 lore raw

Hi Harald,

Quoted 44 lines · Harald Welte

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.

---
commit 06d95115655ba6df96d8ad7c92a3d5e91eee39f7
tree 21a21e59e9ce5eccdbafb6026106c49691674dba
parent 904a871a628c42031c3093c2b90bde526f0f35f0
author Harald Welte <[email protected]> Wed, 01 Feb 2006 21:29:32 +0100 committer Harald Welte <[email protected]> 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(-)
include/net/netfilter/nf_conntrack_helper.h +1 -1
index 86ec817..3cca3c8 100644
@@ -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 */

include/net/netfilter/nf_conntrack_helper.h struct nf_conntrack_helper · line 28

Quoted 10 lines
include/net/netfilter/nf_conntrack_helper.h +3 -4
@@ -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 ;)

Quoted 34 lines
include/net/netfilter/nf_conntrack_helper.h +0 -0
 	/* Function to call when data passes; return verdict, or -1 to
            invalidate. */
 	int (*help)(struct sk_buff **pskb,
net/netfilter/nf_conntrack_core.c +3 -2
index f136e0d..451e8b3 100644
@@ -23,6 +23,8 @@
  * 26 Jan 2006: Harald Welte <[email protected]>
  * 	- restructure nf_conn (introduce nf_conn_help)
  * 	- redesign 'features' how they were originally intended
+ * 02 Feb 2006: Harald Welte <[email protected]>
+ * 	- 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;

net/netfilter/nf_conntrack_core.c unsigned int nf_ct_log_invalid; · line 92

Quoted 7 lines
net/netfilter/nf_conntrack_core.c +4 -0
@@ -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?

Signature · 1 line
Pablo
#2 lore raw
Quoted 7 lines · Pablo Neira Ayuso

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.

Signature · 1 line
Bazsi
#3 lore raw
In reply to Pablo Neira Ayuso
Quoted 3 lines · Pablo Neira Ayuso

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.

Quoted 9 lines

net/netfilter/nf_conntrack_core.c unsigned int nf_ct_log_invalid; · line 92

Quoted 4 lines
net/netfilter/nf_conntrack_core.c +4 -0
+/* 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.

Quoted 2 lines

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.

Signature · 5 lines
- Harald Welte <[email protected]>                 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