TODO list before feature freeze

Hi all,

	With four months to go before the feature freeze, it's
important to compile a feature list for netfilter-related things.  I
see the following coming up:

Connection tracking:
	o TCP window tracking finally goes in.
	o Fix the extremely low TCP RST timeout
	o Fix the UDP timeout calculations to be per-port.
	o Improve hashing
	o Fix the massive timer performance problem.
	o Zero-copy-safe the connection tracking framework
	o ctnetlink support

iptables:
	o Change over to a netlink interface
		o Back to add/delete/replace interface + commit.
	o Rewrite libiptc to use netlink (to port iptables).
	o Write new ip extension for iptables.
	o Zero-copy-safe the iptables framework

NAT:
	o Zero-copy-safe the NAT framework

Please add feature requests: note that I have not been following the
lists, so "obvious" things may not be obvious to me.

Thanks for your patience,
Rusty.
--
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

On Thu, Jul 18, 2002 at 07:34:53PM +1000, Rusty Russell wrote:

Hi all,

	With four months to go before the feature freeze, it's
important to compile a feature list for netfilter-related things.  I
see the following coming up:

Connection tracking:
	o TCP window tracking finally goes in.
	o Fix the extremely low TCP RST timeout
	o Fix the UDP timeout calculations to be per-port.
	o Improve hashing
	o Fix the massive timer performance problem.
	o Zero-copy-safe the connection tracking framework
	o ctnetlink support

iptables:
	o Change over to a netlink interface
		o Back to add/delete/replace interface + commit.
	o Rewrite libiptc to use netlink (to port iptables).
	o Write new ip extension for iptables.
	o Zero-copy-safe the iptables framework

NAT:
	o Zero-copy-safe the NAT framework

Please add feature requests: note that I have not been following the
lists, so "obvious" things may not be obvious to me.

I think conntrack exemptions and transparent proxy support should be added
to the list. The latter is working for me in production at least for TCP
connections. UDP support is to be dependant on conntrack exemptions, so that
is not yet implemented. (at least the sendmsg side, the recvmsg side should
be working)

-- 
Bazsi
PGP info: KeyID 9AF8D0A9 Fingerprint CD27 CFB0 802C 0944 9CFD 804E C82C 8EB1

On Thu, 18 Jul 2002, Rusty Russell wrote:

Hi all,

	With four months to go before the feature freeze,

Really? ;->

Connection tracking:

Fix perfomance problems with this thing. You may have seen reports of
performance degradation it introduces. I was hoping to take a look at some
point time hasnt been visiting this side.

iptables:
	o Change over to a netlink interface
		o Back to add/delete/replace interface + commit.
	o Rewrite libiptc to use netlink (to port iptables).

I hope this resolves the current scheme where the whole
add/delete/replace interface + commit happens in user space?
If you use netlink it would make sense to do incremental updates to the
kernel.

cheers,
jamal

quoted

Connection tracking:

Fix perfomance problems with this thing. You may have seen reports of
performance degradation it introduces. I was hoping to take a look at some
point time hasnt been visiting this side.

One obvious problem that it has is that it uses vmalloc to allocate its
big hash table. This will likely lead to TLB thrashing on a busy box. It should 
try to allocate the hashtable with get_free_pages() first and only fall
back to vmalloc if that fails. This way it would run with large pages.

(case in point: we have at least one report that routing 
performance breaks down with ip_conntrack when memory size is increased over 
1GB on P3s. The hash table size depends on the memory size. The problem does 
not occur on P4s. P4s have larger TLBs than P3s.)

-Andi

On Mon, 29 Jul 2002, Andi Kleen wrote:

One obvious problem that it has is that it uses vmalloc to allocate its
big hash table. This will likely lead to TLB thrashing on a busy box. It should
try to allocate the hashtable with get_free_pages() first and only fall
back to vmalloc if that fails. This way it would run with large pages.

(case in point: we have at least one report that routing
performance breaks down with ip_conntrack when memory size is increased over
1GB on P3s. The hash table size depends on the memory size. The problem does
not occur on P4s. P4s have larger TLBs than P3s.)

They also have a lot of problems with their per-packet computations.
Robert and I spent a short time looking at "this thing that is making
us look bad" (perfomance wise) and talked to Harald.
Something that looked like needs improvement at first glance was the aging
and hashing schemes.

cheers,
jamal

On Mon, Jul 29, 2002 at 07:23:49AM -0400, jamal wrote:

On Mon, 29 Jul 2002, Andi Kleen wrote:

quoted

One obvious problem that it has is that it uses vmalloc to allocate its
big hash table. This will likely lead to TLB thrashing on a busy box. It should
try to allocate the hashtable with get_free_pages() first and only fall
back to vmalloc if that fails. This way it would run with large pages.

(case in point: we have at least one report that routing
performance breaks down with ip_conntrack when memory size is increased over
1GB on P3s. The hash table size depends on the memory size. The problem does
not occur on P4s. P4s have larger TLBs than P3s.)

They also have a lot of problems with their per-packet computations.
Robert and I spent a short time looking at "this thing that is making
us look bad" (perfomance wise) and talked to Harald.
Something that looked like needs improvement at first glance was the aging
and hashing schemes.

Yes, some more tuning is probably needed.

here is a patch for 2.4 that just makes it use get_free_pages to test the 
TLB theory. Another obvious improvement would be to not use list_heads 
for the hash table buckets - a single pointer would likely suffice and 
it would cut the hash table in half, saving cache, TLB and memory.

-Andi

--- linux-work/net/ipv4/netfilter/ip_conntrack_core.c-CONNTRACK	Thu Jul 25 13:36:42 2002
+++ linux-work/net/ipv4/netfilter/ip_conntrack_core.c	Mon Jul 29 13:48:33 2002

@@ -50,6 +50,7 @@
 LIST_HEAD(protocol_list);
 static LIST_HEAD(helpers);
 unsigned int ip_conntrack_htable_size = 0;
+static int ip_conntrack_vmalloc;
 static int ip_conntrack_max = 0;
 static atomic_t ip_conntrack_count = ATOMIC_INIT(0);
 struct list_head *ip_conntrack_hash;

@@ -1053,6 +1054,15 @@
 	return 1;
 }
 
+static void free_conntrack_hash(void)
+{
+	if (ip_conntrack_vmalloc)
+		vfree(ip_conntrack_hash);
+	else
+		free_pages((unsigned long)ip_conntrack_hash, 
+			   get_order(sizeof(struct list_head) * ip_conntrack_htable_size));
+}
+
 /* Mishearing the voices in his head, our hero wonders how he's
    supposed to kill the mall. */
 void ip_conntrack_cleanup(void)

@@ -1075,7 +1085,7 @@
 	}
 
 	kmem_cache_destroy(ip_conntrack_cachep);
-	vfree(ip_conntrack_hash);
+	free_conntrack_hash();
 	nf_unregister_sockopt(&so_getorigdst);
 }
 

@@ -1109,8 +1119,17 @@
 	if (ret != 0)
 		return ret;
 
-	ip_conntrack_hash = vmalloc(sizeof(struct list_head)
-				    * ip_conntrack_htable_size);
+	/* AK: the hash table is twice as big than needed because it uses list_head.
+	   it would be much nicer to caches to use a single pointer list head here. */
+	ip_conntrack_vmalloc = 0; 
+	ip_conntrack_hash = (void *)__get_free_pages(GFP_KERNEL, 
+					     get_order(sizeof(struct list_head) * 
+						       ip_conntrack_htable_size));
+	if (!ip_conntrack_hash) { 
+		ip_conntrack_vmalloc = 1;
+		printk("ip_conntrack: falling back to vmalloc. performance may be degraded.\n");
+		ip_conntrack_hash = vmalloc(sizeof(struct list_head) * ip_conntrack_htable_size);
+	}
 	if (!ip_conntrack_hash) {
 		nf_unregister_sockopt(&so_getorigdst);
 		return -ENOMEM;

@@ -1121,7 +1140,7 @@
 	                                        SLAB_HWCACHE_ALIGN, NULL, NULL);
 	if (!ip_conntrack_cachep) {
 		printk(KERN_ERR "Unable to create ip_conntrack slab cache\n");
-		vfree(ip_conntrack_hash);
+		free_conntrack_hash();
 		nf_unregister_sockopt(&so_getorigdst);
 		return -ENOMEM;
 	}

@@ -1145,7 +1164,7 @@
 		= register_sysctl_table(ip_conntrack_root_table, 0);
 	if (ip_conntrack_sysctl_header == NULL) {
 		kmem_cache_destroy(ip_conntrack_cachep);
-		vfree(ip_conntrack_hash);
+		free_conntrack_hash();
 		nf_unregister_sockopt(&so_getorigdst);
 		return -ENOMEM;
 	}

On Mon, 2002-07-29 at 13:56, Andi Kleen wrote:

here is a patch for 2.4 that just makes it use get_free_pages to test the 
TLB theory. Another obvious improvement would be to not use list_heads 
for the hash table buckets - a single pointer would likely suffice and 
it would cut the hash table in half, saving cache, TLB and memory.

I think the list_heads are used for only one thing currently, for the
early eviction in case of overload, then it scans backwards in the
chains to find unreplied connections to evict, or so the comment in
early_drop() says:

/* Traverse backwards: gives us oldest, which is roughly LRU */

but then it uses the normal LIST_FIND macro which I think traverses the
list in the normal forward direction. I havn't looked into the rest of
the code but I can't seem to remember anything that needs list_heads.

I think Patrick Schaaf is looking into conntrack as we speak. Maybe he
has any ideas?

I know I've had plans on rewriting the locking in conntrack which is
quite frankly horrible, one giant rwlock used for almost everything
(including the hashtable). One idea that has come to mind is using RCU
(need to learn more about it) or maybe use one rwlock per N buckets or
something. Looking at some stats from one of my routers I see that an
average connection is over 130 packets long so the ratio between reads
and writes is quite good.

And this eviction which occurs at overload needs to be redone, we can't
go around dropping one unreplied connection at a time, we need
gang-eviction of unreplied connections. We've had some nasty DDoS's here
in which our routers have been spending all cputime in conntrack trying
to evict connections to make room for the SYN floods coming in at

130kpps.

-- 
/Martin

Never argue with an idiot. They drag you down to their level, then beat
you with experience.

On Mon, 2002-07-29 at 13:56, Andi Kleen wrote:

here is a patch for 2.4 that just makes it use get_free_pages to test the 
TLB theory. Another obvious improvement would be to not use list_heads 
for the hash table buckets - a single pointer would likely suffice and 
it would cut the hash table in half, saving cache, TLB and memory.

ip_nat_core is also allocating it's hashtable via vmalloc and it's twice
as large as the one in ip_conntrack. (or rather, it's two hashtables
allocated at once, maybe they should be split up into two allocations?)


diff -x *.orig -x *.rej -urN linux-2.4.19-rc3.old/net/ipv4/netfilter/ip_nat_core.c linux-2.4.19-rc3/net/ipv4/netfilter/ip_nat_core.c

--- linux-2.4.19-rc3.old/net/ipv4/netfilter/ip_nat_core.c	Thu Jul 25 18:26:42 2002
+++ linux-2.4.19-rc3/net/ipv4/netfilter/ip_nat_core.c	Tue Jul 30 00:14:12 2002

@@ -43,6 +43,8 @@
 /* Calculated at init based on memory size */
 static unsigned int ip_nat_htable_size;
 
+static int ip_nat_vmalloc;
+
 static struct list_head *bysource;
 static struct list_head *byipsproto;
 LIST_HEAD(protos);

@@ -958,8 +960,16 @@
 	/* Leave them the same for the moment. */
 	ip_nat_htable_size = ip_conntrack_htable_size;
 
-	/* One vmalloc for both hash tables */
-	bysource = vmalloc(sizeof(struct list_head) * ip_nat_htable_size*2);
+	/* One allocation for both hash tables */
+	ip_nat_vmalloc = 0;
+	bysource = (void *)__get_free_pages(GFP_KERNEL,
+					get_order(sizeof(struct list_head) *
+						  ip_nat_htable_size * 2));
+	if (!bysource) {
+		ip_nat_vmalloc = 1;
+		printk("ip_nat: falling back to vmalloc. performance may be degraded.\n");
+		bysource = vmalloc(sizeof(struct list_head) * ip_nat_htable_size * 2);
+	}
 	if (!bysource) {
 		return -ENOMEM;
 	}

@@ -999,5 +1009,10 @@
 {
 	ip_ct_selective_cleanup(&clean_nat, NULL);
 	ip_conntrack_destroyed = NULL;
-	vfree(bysource);
+
+	if (ip_nat_vmalloc)
+		vfree(bysource);
+	else
+		free_pages((unsigned long)bysource,
+			   get_order(sizeof(struct list_head) * ip_nat_htable_size * 2));
 }
 

-- 
/Martin

Never argue with an idiot. They drag you down to their level, then beat
you with experience.