Skip to contentSkip to conversation

first conntrack ID must be 1 not 2

PATCH In review Pablo Neira Ayuso 7 participants 40 messages Feb 13, 2006 – Apr 12, 2006 1 message not in the archive

Subsystems (2)
lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH 4/4 first conntrack ID must be 1 not 2

[NF_CONNTRACK] first conntrack ID must be 1 not 2

The first conntrack ID must be 1. If a new conntrack is created, the general ID counter must be post-incremented instead pre-incremented since [ip|nf]_conntrack_next_id is initialized to 1. Same applies for expectations.

Signature · 2 lines
The dawn of the fourth age of Linux firewalling is coming; a time of
great struggle and heroic deeds -- J.Kadlecsik got inspired by J.Morris

[NETFILTER] first conntrack ID must be 1 not 2

The first conntrack ID must be 1. If a new conntrack is created, the general ID counter must be post-incremented instead pre-incremented since [ip|nf]_conntrack_next_id is initialized to 1. Same applies for expectations.

net/netfilter/nf_conntrack_core.c +2 -2
Index: net-2.6.git/net/netfilter/nf_conntrack_core.c
===================================================================
@@ -682,7 +682,7 @@ static void __nf_conntrack_hash_insert(s
 				       unsigned int hash,
 				       unsigned int repl_hash) 
 {
-	ct->id = ++nf_conntrack_next_id;
+	ct->id = nf_conntrack_next_id++;
 	list_prepend(&nf_conntrack_hash[hash],
 		     &ct->tuplehash[IP_CT_DIR_ORIGINAL].list);
 	list_prepend(&nf_conntrack_hash[repl_hash],
@@ -1247,7 +1247,7 @@ static void nf_conntrack_expect_insert(s
 	exp->timeout.expires = jiffies + exp->master->helper->timeout * HZ;
 	add_timer(&exp->timeout);
 
-	exp->id = ++nf_conntrack_expect_next_id;
+	exp->id = nf_conntrack_expect_next_id++;
 	atomic_inc(&exp->use);
 	NF_CT_STAT_INC(expect_create);
 }
net/ipv4/netfilter/ip_conntrack_core.c +2 -2
Index: net-2.6.git/net/ipv4/netfilter/ip_conntrack_core.c
===================================================================
@@ -417,7 +417,7 @@ static void __ip_conntrack_hash_insert(s
 					unsigned int hash,
 					unsigned int repl_hash) 
 {
-	ct->id = ++ip_conntrack_next_id;
+	ct->id = ip_conntrack_next_id++;
 	list_prepend(&ip_conntrack_hash[hash],
 		     &ct->tuplehash[IP_CT_DIR_ORIGINAL].list);
 	list_prepend(&ip_conntrack_hash[repl_hash],
@@ -971,7 +971,7 @@ static void ip_conntrack_expect_insert(s
 	exp->timeout.expires = jiffies + exp->master->helper->timeout * HZ;
 	add_timer(&exp->timeout);
 
-	exp->id = ++ip_conntrack_expect_next_id;
+	exp->id = ip_conntrack_expect_next_id++;
 	atomic_inc(&exp->use);
 	CONNTRACK_STAT_INC(expect_create);
 }
#1 lore raw
Quoted 6 lines · Pablo Neira Ayuso

[NF_CONNTRACK] first conntrack ID must be 1 not 2

The first conntrack ID must be 1. If a new conntrack is created, the general ID counter must be post-incremented instead pre-incremented since [ip|nf]_conntrack_next_id is initialized to 1. Same applies for expectations.

looks clean to me. Interesting question though: Does it matter whether we start with 1 or 2? Am I missing something?

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
#2 lore raw
Quoted 4 lines · Harald Welte
Quoted 2 lines · Pablo Neira Ayuso

[NF_CONNTRACK] first conntrack ID must be 1 not 2

Quoted 8 lines
Quoted 4 lines

The first conntrack ID must be 1. If a new conntrack is created, the general ID counter must be post-incremented instead pre-incremented since [ip|nf]_conntrack_next_id is initialized to 1. Same applies for expectations.

looks clean to me. Interesting question though: Does it matter whether we start with 1 or 2? Am I missing something?

Its irrelevant since the number doesn't have any meaning beyond beeing an identifier. Anyway, I'd prefer a patch that just removes the initialization to 1.

#3 lore raw
Quoted 11 lines · Patrick McHardy
Quoted 10 lines · Harald Welte
Quoted 6 lines · Pablo Neira Ayuso

[NF_CONNTRACK] first conntrack ID must be 1 not 2

The first conntrack ID must be 1. If a new conntrack is created, the general ID counter must be post-incremented instead pre-incremented since [ip|nf]_conntrack_next_id is initialized to 1. Same applies for expectations.

Quoted 6 lines
Quoted 2 lines

looks clean to me. Interesting question though: Does it matter whether we start with 1 or 2? Am I missing something?

Its irrelevant since the number doesn't have any meaning beyond beeing an identifier. Anyway, I'd prefer a patch that just removes the initialization to 1.

Couldn't the id be simply equal to the jiffies when creating the conntrack entry? (And adding time_after/before when comparing ids, of course.)

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#4 lore raw
Quoted 2 lines · Jozsef Kadlecsik

Couldn't the id be simply equal to the jiffies when creating the conntrack entry? (And adding time_after/before when comparing ids, of course.)

We can create more than one entry per jiffy, so that wouldn't be unique anymore.

#5 lore raw
Quoted 6 lines · Patrick McHardy
Quoted 2 lines · Jozsef Kadlecsik

Couldn't the id be simply equal to the jiffies when creating the conntrack entry? (And adding time_after/before when comparing ids, of course.)

We can create more than one entry per jiffy, so that wouldn't be unique anymore.

(jiffies, tuples) would be unique even in that case.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#6 lore raw
Quoted 5 lines · Jozsef Kadlecsik
Quoted 2 lines · Patrick McHardy

Jozsef Kadlecsik wrote:

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

Couldn't the id be simply equal to the jiffies when creating the conntrack entry? (And adding time_after/before when comparing ids, of course.)

We can create more than one entry per jiffy, so that wouldn't be unique anymore.

(jiffies, tuples) would be unique even in that case.

Thats true. But what is the advantage over using the counter?

#7 lore raw
Quoted 8 lines · Patrick McHardy
Quoted 7 lines · Jozsef Kadlecsik
Quoted 5 lines · Patrick McHardy
Quoted 2 lines · Jozsef Kadlecsik

Couldn't the id be simply equal to the jiffies when creating the conntrack entry? (And adding time_after/before when comparing ids, of course.)

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

We can create more than one entry per jiffy, so that wouldn't be unique anymore.

(jiffies, tuples) would be unique even in that case.

Thats true. But what is the advantage over using the counter?

Currently nothing :-).

However, the counter poses an internal bottleneck in the overall system when one attempts to replace the hashtable by hashtrie. (What I really like about hashtrie is that it naturally implements the 'region locking' suggested by Patrick Schaaf, compared to the 'brute force' per bucket locking.)

As I see, we have got three bottlenecks in conntrack in SMP systems:
the hashtable approach, the id and the expectation list. The first two could be eliminated by hashtrie and jiffies as ids.

Some clever solution should only be found to spread the expectations over multiple, separatedly locked buckets...

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#8 lore raw
Quoted 5 lines · Jozsef Kadlecsik
Quoted 3 lines · Patrick McHardy
Quoted 1 line

(jiffies, tuples) would be unique even in that case.

Thats true. But what is the advantage over using the counter?

Actually it would still not be unique if connections live shorter than a jiffy and are resurrected.

Quoted 8 lines

Currently nothing :-).

However, the counter poses an internal bottleneck in the overall system when one attempts to replace the hashtable by hashtrie. (What I really like about hashtrie is that it naturally implements the 'region locking' suggested by Patrick Schaaf, compared to the 'brute force' per bucket locking.)

Quoted 6 lines

As I see, we have got three bottlenecks in conntrack in SMP systems:
the hashtable approach, the id and the expectation list. The first two could be eliminated by hashtrie and jiffies as ids.

Some clever solution should only be found to spread the expectations over multiple, separatedly locked buckets...

I've talked to Harald about this and as a start we can start by allowing masks only for the source part of the tuple. That means we can hash by destinations.

#9 lore raw
Quoted 9 lines · Patrick McHardy
Quoted 5 lines · Jozsef Kadlecsik
Quoted 3 lines · Patrick McHardy
Quoted 1 line

(jiffies, tuples) would be unique even in that case.

Thats true. But what is the advantage over using the counter?

Actually it would still not be unique if connections live shorter than a jiffy and are resurrected.

I can imagine such a situation only when the conntrack table is full and we are forced to drop unassured connections - when we are in trouble anyway.

Quoted 6 lines
Quoted 2 lines

Some clever solution should only be found to spread the expectations over multiple, separatedly locked buckets...

I've talked to Harald about this and as a start we can start by allowing masks only for the source part of the tuple. That means we can hash by destinations.

That's actually fine! Now I should complete that hashtrie/hashtable testing I have been planning...

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#10 lore raw
Quoted 9 lines · Jozsef Kadlecsik
Quoted 6 lines
Quoted 2 lines

Some clever solution should only be found to spread the expectations over multiple, separatedly locked buckets...

I've talked to Harald about this and as a start we can start by allowing masks only for the source part of the tuple. That means we can hash by destinations.

That's actually fine! Now I should complete that hashtrie/hashtable testing I have been planning...

Great that you are testing hashtrie, it works fine in all my simple tests but there might still be a lot of bugs in it, especially in the forced eviction, it might not be optimal, me and rusty tried to come up with a way to make it fair wrt the depth in the tree we are evicting at.

If you have any suggestions and/or patches, please let me know :)

Are you using the 060104 version, that's the latest version I have of the userspace code.
I have an old untested patch against nf_conntrack as well but it needs some rewriting of the conntrack locking in order to avoid an SMP deadlock.

/Martin

#30 lore raw
In reply to Jozsef Kadlecsik
Quoted 9 lines · Jozsef Kadlecsik
Quoted 2 lines · Patrick McHardy

Actually it would still not be unique if connections live shorter than a jiffy and are resurrected.

I can imagine such a situation only when the conntrack table is full and we are forced to drop unassured connections - when we are in trouble anyway.

I guess it depends on how fast the everything is. Someone at the workshop made the point that given how fast speed increases, it will probably be a realistic problem at some point. But I was never convinced of the current half-assed approach to a unique ID anyway, its either unique or its not. So in my opinion, we could eliminate it if we find a better solution for the dumping problem.

Quoted 10 lines
Quoted 6 lines
Quoted 2 lines

Some clever solution should only be found to spread the expectations over multiple, separatedly locked buckets...

I've talked to Harald about this and as a start we can start by allowing masks only for the source part of the tuple. That means we can hash by destinations.

That's actually fine! Now I should complete that hashtrie/hashtable testing I have been planning...

I wanted to work on the expectation lookup thing soon, I'll let you know once I have something working.

#11 lore raw
In reply to Martin Josefsson
Quoted 9 lines · Martin Josefsson
Quoted 2 lines

That's actually fine! Now I should complete that hashtrie/hashtable testing I have been planning...

Great that you are testing hashtrie, it works fine in all my simple tests but there might still be a lot of bugs in it, especially in the forced eviction, it might not be optimal, me and rusty tried to come up with a way to make it fair wrt the depth in the tree we are evicting at.

If you have any suggestions and/or patches, please let me know :)

Here are the tests I'd like to see against hashtrie:

- larger hashentry, i.e. when HASHSIFT is equal to 6, 7 or 8
- other HASHALIGN, hashbit_t values: (32, u8), (64, u16) and (64, u32). The current (32, u8) doesn't look optimal on 64bit CPUs, (64, u16) seems to be the best, but without testing it's hard to choose.
- DoS against hashtrie by non-random tuples: single fixed destination IP, port and successive source IP, port numbers. (I don't think the current max 7 levels (childs) can survive such an attack.)

Somehow I don't really like the eviction algorithm. What about some lazy auto-eviction instead: say, if there are more than 90% of the max elements, then drop a (any) unassured connection which can be found on the path when inserting a new one. Thus the current fixed stack could be eliminated and there were no builtin limit in the depth.

I'm collecting the ideas, so can't submit patches yet ;-).

Quoted 2 lines

I have an old untested patch against nf_conntrack as well but it needs some rewriting of the conntrack locking in order to avoid an SMP deadlock.

Rusty's lock-ordering is a sure solution, but penalizes the process. I have been thinking on wether we could use simply, separated, unordered locking:

1. lock bucket according to tuple1
add element
unlock bucket
2. lock bucket according to tuple2,
add element
unlock bucket
if (add element failed)

	undo 1.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#12 lore raw

Hi Martin,

Quoted 1 line · Jozsef Kadlecsik

I'm collecting the ideas, so can't submit patches yet ;-).

Two more things:

- the Jenkins hash internally produces 96 bits, which we could use in the hashtrie
- there should be some (whatever artifical) tests to study the dynamical behaviour of the hashtrie: say all the entries are added, then half of them deleted and added back again, but in reverse order. Will the maxdepth grow?

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#13 lore raw

Hashtrie testing (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

On Fri, 2006-02-17 at 19:41 +0100, Jozsef Kadlecsik wrote:

(Changing subject and removing some cc's)

Quoted 1 line

Hi Martin,

Hi Jozsef

Quoted 3 lines · Jozsef Kadlecsik
Quoted 2 lines

I'm collecting the ideas, so can't submit patches yet ;-).

:)

I'll move my svn tree to the netfilter svn sometime soon.

Quoted 4 lines

Two more things:

- the Jenkins hash internally produces 96 bits, which we could use in the hashtrie

That's a great idea, will look into it.

Quoted 4 lines

- there should be some (whatever artifical) tests to study the dynamical behaviour of the hashtrie: say all the entries are added, then half of them deleted and added back again, but in reverse order. Will the maxdepth grow?

I've performed some simple tests with this and here are the results:

First I tried removing the upper half of the conntrack entries (it's the conntrack entries index in the test array that's printed out in the "Removing" line below)

Number of entries in hashtrie: 819200
Number of children in hashtrie: 27345
Maxdepth of hashtrie: 3 (0 == root)
Removing entries between 204800 and 409599. Adding entries between 409599 and 204800.
insert (half reverse): time: 1484 cyc, 929 ns (1076184/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 27345
Maxdepth of hashtrie: 3 (0 == root)

No diffrence at all which is a bit weird, I had to doublecheck the code to see that I really readded the entries in reverse order and I did.

Then I tried it with the lower half of the conntrack entries, those lower in the tree and got this:

Number of entries in hashtrie: 819200
Number of children in hashtrie: 27273
Maxdepth of hashtrie: 3 (0 == root)
Removing entries between 0 and 204799.
Adding entries between 204799 and 0.
insert (half reverse): time: 1627 cyc, 1018 ns (981869/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 29189
Maxdepth of hashtrie: 3 (0 == root)

Here wee see that the number of child-nodes has increased from 27273 to 29189, that's a 7.0% increase, but the max depth hasn't increased in this particular test. Given the right sitation the maxdepth will probably increase, it's likely to occur sometimes since the number of child-nodes has increased.

Then I tried to remove every other entry and then readding them in reverse order (this test is performed after the previous readd of the lower half, not the same testrun as above so the absolute numbers doesn't match those above):

Number of entries in hashtrie: 819200
Number of children in hashtrie: 27329
Maxdepth of hashtrie: 3 (0 == root)
Removing entries between 0 and 204799.
Adding entries between 204799 and 0.
insert (half reverse): time: 1590 cyc, 996 ns (1004079/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 29253
Maxdepth of hashtrie: 3 (0 == root)
Removing every other entry from 0 to 409599 Adding every other entry from 409599 to 0
insert (other reverse): time: 1637 cyc, 1025 ns (975239/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 29376
Maxdepth of hashtrie: 3 (0 == root)

Here we see that the number of child-nodes increased in the remove_lower_half_and_readd_in_reverse_order test just as it did before, and then the number of child-nodes increased again after removing every other entry and adding them back in reverse order. The total increase after both tests is 7.5%

More testing is clearly needed.

Signature · 1 line
/Martin
#16 lore raw

Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

In reply to Jozsef Kadlecsik
Quoted 3 lines · Jozsef Kadlecsik

Here are the tests I'd like to see against hashtrie:

- larger hashentry, i.e. when HASHSIFT is equal to 6, 7 or 8

I have seen good results when sizeof(struct hashentry) = 64 on my laptop. But on the other hand my laptop likes the padding of struct hashentry at the beginning with gives unaligned pointers. It's an Pentium M processor in my laptop.

Quoted 1 line

- other HASHALIGN, hashbit_t values: (32, u8), (64, u16) and (64, u32).

Yes this needs more testing as well.

Quoted 2 lines

The current (32, u8) doesn't look optimal on 64bit CPUs, (64, u16) seems to be the best, but without testing it's hard to choose.

Currently I don't have any 64bit cpus to test things on.

Quoted 3 lines

- DoS against hashtrie by non-random tuples: single fixed destination IP, port and successive source IP, port numbers. (I don't think the current max 7 levels (childs) can survive such an attack.)

I just ran some tests on this with this code:

dstip = 192 << 24 | 168 << 16 | 1 << 8 | 1;
srcip = 200 << 24 | 100 << 16 | 50 << 8 | 0;

conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = srcip + rand() % 1024; conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = (u16)rand(); conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = dstip; conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = 80;

And this is the result I got:

sizeof struct hashentry: 32
sizeof struct ip_conntrack: 48
number of conntrack entries: 1228800
number of slots per hashtrie bucket: 5
number of pad bytes: 3
number of bytes per child: 2048
insert: time: 11299 cyc, 18854 ns (53040/s)
Number of failed inserts: 22232
Number of entries in hashtrie: 2435368
Number of children in hashtrie: 238756
Maxdepth of hashtrie: 3 (0 == root)
Maximum memory usage: 488972288

2.4 million entries in the hashtrie with fixed dstip, port and 1024 srcip's with random ports and a maxdepth of 3. I'd say the jenkins hash is doing its job quite nicely, wasn't expecting such good results.

In the results above you see my main worry regarding hashtrie, the memory usage, 200 bytes per entry in hashtrie (400 bytes per conntrack) in this scenario, which means that the child-nodes aren't very populated in the leaf nodes.

2435368 entries / 238756 child-nodes = 10.2 entries/child-node

And there's 2048 / 32 = 64 struct hashentry per child-node. That's 64 * 5 = 320 entries/child-node

10.2 / 320 = 3.2% usage of child-nodes in average which is simply horrible.

I'm almost starting to think there's a major bug in there somewhere. I need to write some code to walk the tree and calculate the usage of each level to see that it's actually 100% for all buckets that has a child.

Quoted 5 lines

Somehow I don't really like the eviction algorithm. What about some lazy auto-eviction instead: say, if there are more than 90% of the max elements, then drop a (any) unassured connection which can be found on the path when inserting a new one. Thus the current fixed stack could be eliminated and there were no builtin limit in the depth.

Couldn't this lead to the situation where we evict an entry early on the path, and then that slot gets reused for another entry that's also unassured, and it repeats...
The problem with eviction in the hashtrie is that the depth of the entry has no correlation to the age of the entry like in the current hashtable (that's only true if you have long linked lists which leads to poor performance, so no real-world installation has properly working evication anyway today so maybe it doesn't matter too much)

Quoted 7 lines
Quoted 2 lines

I have an old untested patch against nf_conntrack as well but it needs some rewriting of the conntrack locking in order to avoid an SMP deadlock.

Rusty's lock-ordering is a sure solution, but penalizes the process. I have been thinking on wether we could use simply, separated, unordered locking:

Quoted 8 lines

1. lock bucket according to tuple1
add element
unlock bucket
2. lock bucket according to tuple2,
add element
unlock bucket
if (add element failed)

	undo 1.

Yes this is the way I've been thinking about. If we get into the case where we have conntrack A and B that have the exact same tuples but in reverse it doesn't really matter if one gets dropped or both, this is strictly best effort, no need to bend over backwards in order to minimize racewindows if it isn't anything serious.
The only case I can think about where it might matter is the case of simultaneous open from both sides with the same source/destination ports, dns (some clients issue requests from port 53), games and ipsec isakmp come to mind.

Signature · 1 line
/Martin
#14 lore raw

Re: Hashtrie testing (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

In reply to Martin Josefsson

Hi Martin,

Quoted 1 line · Martin Josefsson

I'll move my svn tree to the netfilter svn sometime soon.

That'll be great!

Quoted 21 lines
Quoted 4 lines

- there should be some (whatever artifical) tests to study the dynamical behaviour of the hashtrie: say all the entries are added, then half of them deleted and added back again, but in reverse order. Will the maxdepth grow?

I've performed some simple tests with this and here are the results:

First I tried removing the upper half of the conntrack entries (it's the conntrack entries index in the test array that's printed out in the "Removing" line below)

Number of entries in hashtrie: 819200
Number of children in hashtrie: 27345
Maxdepth of hashtrie: 3 (0 == root)
Removing entries between 204800 and 409599. Adding entries between 409599 and 204800.
insert (half reverse): time: 1484 cyc, 929 ns (1076184/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 27345
Maxdepth of hashtrie: 3 (0 == root)

Quoted 2 lines

No diffrence at all which is a bit weird, I had to doublecheck the code to see that I really readded the entries in reverse order and I did.

That's really weird: same maxdepth and exactly the same number of children!

Quoted 13 lines

Then I tried it with the lower half of the conntrack entries, those lower in the tree and got this:

Number of entries in hashtrie: 819200
Number of children in hashtrie: 27273
Maxdepth of hashtrie: 3 (0 == root)
Removing entries between 0 and 204799.
Adding entries between 204799 and 0.
insert (half reverse): time: 1627 cyc, 1018 ns (981869/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 29189
Maxdepth of hashtrie: 3 (0 == root)

Quoted 5 lines

Here wee see that the number of child-nodes has increased from 27273 to 29189, that's a 7.0% increase, but the max depth hasn't increased in this particular test. Given the right sitation the maxdepth will probably increase, it's likely to occur sometimes since the number of child-nodes has increased.

Half of the entries were removed then re-added and it produced 7% increase in the number of the child nodes. That might be good or bad as well.

[...]

Quoted 1 line

More testing is clearly needed.

Yes, one is somehow uneasy. Hm. What about filling up the hashtrie and then some long loop of deleting 10% at random and adding *new* random entries? We could measure the change in maxdepth/childnodes after every delete/add cycle. What were the peak numbers? At what numbers would it stabilize?

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#17 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

In reply to Martin Josefsson

Hi Martin,

Quoted 10 lines · Martin Josefsson
Quoted 3 lines · Jozsef Kadlecsik

Here are the tests I'd like to see against hashtrie:

- larger hashentry, i.e. when HASHSIFT is equal to 6, 7 or 8

I have seen good results when sizeof(struct hashentry) = 64 on my laptop. But on the other hand my laptop likes the padding of struct hashentry at the beginning with gives unaligned pointers. It's an Pentium M processor in my laptop.

HASHSIFT (i.e. HASHNUM) defines the hash size of the hashtrie. But the hashtrie - according to your tests - are much "wider" than "deep". So there might be no point in widening the hash.

Quoted 8 lines
Quoted 1 line

- other HASHALIGN, hashbit_t values: (32, u8), (64, u16) and (64, u32).

Yes this needs more testing as well.

Quoted 2 lines

The current (32, u8) doesn't look optimal on 64bit CPUs, (64, u16) seems to be the best, but without testing it's hard to choose.

Currently I don't have any 64bit cpus to test things on.

With the default (32, u8) settings NUMENTRY looks too small on 64bit CPUs:

HASHALIGN = 32
hashbits_t = u8

    32bit CPU:  NUMENTRY = (32 - 4)/(1+4) = 5
                PADNUM = 32 - 4 - 5*(1+4) = 3

    64bit CPU:  NUMENTRY = (32 - 8)/(1+8) = 2
                PADNUM = 32 - 8 - 2*(1+8) = 6

HASHALIGN = 64
hashbits_t = u16

    32bit CPU:  NUMENTRY = (64 - 4)/(2+4) = 10
                PADNUM = 64 - 4 - 10*(2+4) = 0

    64bit CPU:  NUMENTRY = (64 - 8)/(2+8) = 5
                PADNUM = 64 - 8 - 5*(2+8) = 6

HASHALIGN = 64
hashbits_t = u32

    32bit CPU:  NUMENTRY = (64 - 4)/(4+4) = 7
                PADNUM = 64 - 4 - 7*(4+4) = 4

    64bit CPU:  NUMENTRY = (64 - 8)/(4+8) = 4
                PADNUM = 64 - 8 - 4*(4+8) = 8
Quoted 5 lines
Quoted 3 lines

- DoS against hashtrie by non-random tuples: single fixed destination IP, port and successive source IP, port numbers. (I don't think the current max 7 levels (childs) can survive such an attack.)

I just ran some tests on this with this code:

[...]

Quoted 15 lines

And this is the result I got:

sizeof struct hashentry: 32
sizeof struct ip_conntrack: 48
number of conntrack entries: 1228800
number of slots per hashtrie bucket: 5
number of pad bytes: 3
number of bytes per child: 2048
insert: time: 11299 cyc, 18854 ns (53040/s)
Number of failed inserts: 22232
Number of entries in hashtrie: 2435368
Number of children in hashtrie: 238756
Maxdepth of hashtrie: 3 (0 == root)
Maximum memory usage: 488972288

Quoted 3 lines

2.4 million entries in the hashtrie with fixed dstip, port and 1024 srcip's with random ports and a maxdepth of 3. I'd say the jenkins hash is doing its job quite nicely, wasn't expecting such good results.

The hashtrie tends to grow wider and not deeper:

level: childs (max) entries (max)
0 64 320
1 4160 20800
2 266304 1331520
3 17043520 85217600

Quoted 10 lines

In the results above you see my main worry regarding hashtrie, the memory usage, 200 bytes per entry in hashtrie (400 bytes per conntrack) in this scenario, which means that the child-nodes aren't very populated in the leaf nodes.

2435368 entries / 238756 child-nodes = 10.2 entries/child-node

And there's 2048 / 32 = 64 struct hashentry per child-node. That's 64 * 5 = 320 entries/child-node

Quoted 7 lines

10.2 / 320 = 3.2% usage of child-nodes in average which is simply horrible.

I'm almost starting to think there's a major bug in there somewhere. I need to write some code to walk the tree and calculate the usage of each level to see that it's actually 100% for all buckets that has a child.

Yes, that could help to spot the problem. But if there are clashes (due to using to small parts of the hash key, i.e hashbits_t = u8), then the node can be fairly low utilized and still there is a need to expand by new childs.

Quoted 9 lines
Quoted 5 lines

Somehow I don't really like the eviction algorithm. What about some lazy auto-eviction instead: say, if there are more than 90% of the max elements, then drop a (any) unassured connection which can be found on the path when inserting a new one. Thus the current fixed stack could be eliminated and there were no builtin limit in the depth.

Couldn't this lead to the situation where we evict an entry early on the path, and then that slot gets reused for another entry that's also unassured, and it repeats...

You mean, we could always evict the newest unassured entries instead of the oldest ones? The algorithm could be extended so that we'd walk the whole tree and register the oldest unassured entry in the path. I'm more worried that we'd check too litle number of entries as the tree is shorter than I thought.

Quoted 2 lines
Quoted 2 lines

I have been thinking on wether we could use simply, separated, unordered locking:

[...]

Quoted 4 lines

The only case I can think about where it might matter is the case of simultaneous open from both sides with the same source/destination ports, dns (some clients issue requests from port 53), games and ipsec isakmp come to mind.

That can be fixed by checking that we undo the insertion for the same conntrack entry we were unable to add at the second step.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#15 lore raw

Re: Hashtrie testing (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

In reply to Jozsef Kadlecsik
Quoted 1 line · Jozsef Kadlecsik

Hi Martin,

Hi Jozsef

Quoted 3 lines
Quoted 1 line

I'll move my svn tree to the netfilter svn sometime soon.

That'll be great!

After a small struggle with 'svnadmin dump', 'svndumpfilter' and 'sed' it's finally there with all history.

trunk/hashtrie

Enjoy and don't laugh too much at all the early experimentation :)

Quoted 14 lines
Quoted 14 lines

First I tried removing the upper half of the conntrack entries (it's the conntrack entries index in the test array that's printed out in the "Removing" line below)

Number of entries in hashtrie: 819200
Number of children in hashtrie: 27345
Maxdepth of hashtrie: 3 (0 == root)
Removing entries between 204800 and 409599. Adding entries between 409599 and 204800.
insert (half reverse): time: 1484 cyc, 929 ns (1076184/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 27345
Maxdepth of hashtrie: 3 (0 == root)

Quoted 5 lines
Quoted 2 lines

No diffrence at all which is a bit weird, I had to doublecheck the code to see that I really readded the entries in reverse order and I did.

That's really weird: same maxdepth and exactly the same number of children!

Yes I thought so too, I even added a bunch of debug printf's to the code to verify that it actually readded them in reverse order, and it did.

Quoted 13 lines
Quoted 13 lines

Then I tried it with the lower half of the conntrack entries, those lower in the tree and got this:

Number of entries in hashtrie: 819200
Number of children in hashtrie: 27273
Maxdepth of hashtrie: 3 (0 == root)
Removing entries between 0 and 204799.
Adding entries between 204799 and 0.
insert (half reverse): time: 1627 cyc, 1018 ns (981869/s) Number of entries in hashtrie: 819200
Number of children in hashtrie: 29189
Maxdepth of hashtrie: 3 (0 == root)

Quoted 8 lines
Quoted 5 lines

Here wee see that the number of child-nodes has increased from 27273 to 29189, that's a 7.0% increase, but the max depth hasn't increased in this particular test. Given the right sitation the maxdepth will probably increase, it's likely to occur sometimes since the number of child-nodes has increased.

Half of the entries were removed then re-added and it produced 7% increase in the number of the child nodes. That might be good or bad as well.

Yes I don't know either :)
In these tests both source and destination ipaddresses are random, that's usually not the case in most installations.
With fixed dst ip, port and 1024 sourceipaddresses and random src ports it increases by 7.2%

Quoted 8 lines

[...]

Quoted 1 line

More testing is clearly needed.

Yes, one is somehow uneasy. Hm. What about filling up the hashtrie and then some long loop of deleting 10% at random and adding *new* random entries? We could measure the change in maxdepth/childnodes after every delete/add cycle. What were the peak numbers? At what numbers would it stabilize?

I'll test this as well during the evening.
Removing 10% of the entries at random, and then give those entries new random values and readd them.

Signature · 1 line
/Martin
#18 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

In reply to Jozsef Kadlecsik
Quoted 1 line · Jozsef Kadlecsik

Hi Martin,

Hi Jozsef

Quoted 3 lines

HASHSIFT (i.e. HASHNUM) defines the hash size of the hashtrie. But the hashtrie - according to your tests - are much "wider" than "deep". So there might be no point in widening the hash.

HASHSHIFT and HASHNUM controls the number of struct hashentry per child. The original idea was to allocate 1 page (4kB) for each child but I got better results with 2kB, which means it isn't as wide as it was from the start.

Quoted 8 lines
Quoted 8 lines
Quoted 1 line

- other HASHALIGN, hashbit_t values: (32, u8), (64, u16) and (64, u32).

Yes this needs more testing as well.

Quoted 2 lines

The current (32, u8) doesn't look optimal on 64bit CPUs, (64, u16) seems to be the best, but without testing it's hard to choose.

Currently I don't have any 64bit cpus to test things on.

HASHALIGN is the size of struct hashentry, the idea is that HASHALIGN should be equal to the cacheline size of the cpu it's running on. That way you only get one cachemiss per level in the tree. HASHALIGN is set to 32 bytes just because my laptop has 32byte cachelines, other cpus has 64bytes or even 128bytes.

hashbit_t is an u8 because in my tests I havn't see any gain by going to more bits.
The only purpose of hashbits is to "cheat" a bit during lookup, store a part of the hash-value in the datastructure so you can easily determine if a member even can be a possible match by comparing the hashbits to the hashvalue you are searching for, this eliminates a lot of cachemisses (without this the datastructure will behave more like a linked list).

I've tested with diffrent number of bits for hashbits but I havn't seen any real gain by going over 7 bits which is what is currently used, and the last bit is used as status bit for ASSURED.

Quoted 2 lines

With the default (32, u8) settings NUMENTRY looks too small on 64bit CPUs:

Yes it's too small, luckily I don't know of any 64bit cpus that have 32byte cachelines :)
Lets say we keep hashbits as an u8 then we get the following results for diffrent cacheline sizes (I believe the intel p4 has 128byte cachelines)

HASHALIGN = 32
hashbits_t = u8

    32bit CPU:  NUMENTRY = (32 - 4)/(1+4) = 5
                PADNUM = 32 - 4 - 5*(1+4) = 3

    64bit CPU:  NUMENTRY = (32 - 8)/(1+8) = 2
                PADNUM = 32 - 8 - 2*(1+8) = 6

HASHALIGN = 64
hashbits_t = u8

    32bit CPU: NUMENTRY = (64 - 4)/(1 + 4) = 12
                       PADNUM = 64 - 4 - 12*(1 + 4) = 0

    64bit CPU: NUMENTRY = (64 - 8)/(1 + 8) = 6
                       PADNUM = 64 - 8 - 6*(1 + 8) = 2

HASHALIGN = 128
hashbits_t = u8

    32bit CPU: NUMENTRY = (128 - 4)/(1 +4) = 24
                       PADNUM = 128 - 4 - 24*(1 + 4) = 4

    64bit CPU: NUMENTRY = (128 - 8)/(1 + 8) = 13
                       PADNUM = 128 - 8 - 13*(1 + 8) = 3

When HASHALIGN goes up we need to reduce HASHSHIFT in order to make sure we don't try to allocate > 1 page (usually 4kB) of memory.

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

- DoS against hashtrie by non-random tuples: single fixed destination IP, port and successive source IP, port numbers. (I don't think the current max 7 levels (childs) can survive such an attack.)

[snip]

Quoted 11 lines
Quoted 3 lines

2.4 million entries in the hashtrie with fixed dstip, port and 1024 srcip's with random ports and a maxdepth of 3. I'd say the jenkins hash is doing its job quite nicely, wasn't expecting such good results.

The hashtrie tends to grow wider and not deeper:

level: childs (max) entries (max)
0 64 320
1 4160 20800
2 266304 1331520
3 17043520 85217600

It grows wider if and only if we get hashvalues that aren't too similar in the high bits. If that happens we grow deeper instead of wider. But it seems the jenkins hash is really good at distributing the changes over all of the bits in the hashvalue. (it's just a little bit on the heavy side, it uses plenty of cpu)

Quoted 9 lines
Quoted 4 lines

I'm almost starting to think there's a major bug in there somewhere. I need to write some code to walk the tree and calculate the usage of each level to see that it's actually 100% for all buckets that has a child.

Yes, that could help to spot the problem. But if there are clashes (due to using to small parts of the hash key, i.e hashbits_t = u8), then the node can be fairly low utilized and still there is a need to expand by new childs.

Small hashbits_t doesn't have anything to do with it, hashbits_t is just for accelerating lookups. If we have a low number of struct hashentry per child-node we'll probably fill them up faster since there's fewer of them to be filled. And if we have a low NUMENTRY they will also be filled faster.

Quoted 9 lines
Quoted 3 lines

Couldn't this lead to the situation where we evict an entry early on the path, and then that slot gets reused for another entry that's also unassured, and it repeats...

You mean, we could always evict the newest unassured entries instead of the oldest ones? The algorithm could be extended so that we'd walk the whole tree and register the oldest unassured entry in the path. I'm more worried that we'd check too litle number of entries as the tree is shorter than I thought.

The problem is how do you know which entry along a path is the oldest? Entries aren't always added to the front like with the current linked lists in the hashtable.

Quoted 10 lines
Quoted 2 lines
Quoted 2 lines

I have been thinking on wether we could use simply, separated, unordered locking:

[...]

Quoted 4 lines

The only case I can think about where it might matter is the case of simultaneous open from both sides with the same source/destination ports, dns (some clients issue requests from port 53), games and ipsec isakmp come to mind.

That can be fixed by checking that we undo the insertion for the same conntrack entry we were unable to add at the second step.

What I meant is the following situation:

clients A & B are both located behind NAT and are trying to connect to each other.
Both bind to the same port, lets say X and try to connect to each others external ip.
Currently if the packets from both clients arrive at the same time at an SMP firewall we add a conntrack entry for one of the clients but drop the second one because of the global lock.
With Rustys lock ordering we keep this behaviour since both buckets are locked in the same order for both packets.
With the "unordered independent locking" of buckets we might end up with:

these happen at the same time:
packet from client A hashes into bucket C, lock and add entry. packet from client B hashes into bucket D, lock and add entry.

and after that these happen at the same time:
packet from client A hashes into bucket D, lock and find entry, remove entry in bucket C
packet from client B hashes into bucket C, lock and find entry, remove entry in bucket D

This leads to no conntrack entry created for any of the clients connection attempts.

The solution would be "ordered independent locking" which locks and adds entries based on bucket number that the tuplex hash into. That way we still keep the current behaviour while simplifying the locking, no chance of deadlocks.

Signature · 1 line
/Martin
#19 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

Hi Martin

Quoted 4 lines · Martin Josefsson

HASHSHIFT and HASHNUM controls the number of struct hashentry per child. The original idea was to allocate 1 page (4kB) for each child but I got better results with 2kB, which means it isn't as wide as it was from the start.

Did you get faster lookups/insertions/deletions with half of the page size?

Quoted 5 lines

HASHALIGN is the size of struct hashentry, the idea is that HASHALIGN should be equal to the cacheline size of the cpu it's running on. That way you only get one cachemiss per level in the tree. HASHALIGN is set to 32 bytes just because my laptop has 32byte cachelines, other cpus has 64bytes or even 128bytes.

As far as I see, the structure should satisfy "contradicting" requirements. We want an as low tree as possible, thus minimising the cost of the operations. That includes the number of levels of the childs and the number of slots in a bucket and the latter depends on the HASHALIGN, hashbits_t parameters and the members of the hashentry structure. So in theory we should maximize HASHSHIFT and minimize NUMENTRY. However we do not want a preallocated, huge, sparse hash either, and therefore it is hard to tell the best values.

Quoted 8 lines

hashbit_t is an u8 because in my tests I havn't see any gain by going to more bits.
The only purpose of hashbits is to "cheat" a bit during lookup, store a part of the hash-value in the datastructure so you can easily determine if a member even can be a possible match by comparing the hashbits to the hashvalue you are searching for, this eliminates a lot of cachemisses (without this the datastructure will behave more like a linked list).

This structure is quite tricky :-).

Quoted 10 lines
Quoted 4 lines

Yes, that could help to spot the problem. But if there are clashes (due to using to small parts of the hash key, i.e hashbits_t = u8), then the node can be fairly low utilized and still there is a need to expand by new childs.

Small hashbits_t doesn't have anything to do with it, hashbits_t is just for accelerating lookups. If we have a low number of struct hashentry per child-node we'll probably fill them up faster since there's fewer of them to be filled. And if we have a low NUMENTRY they will also be filled faster.

But how can we explain the so few entries in the buckets? Your numbers suggest that most of the buckets are pretty empty, as if there were two slots full from the 64 in the DoS case.

Or we can say that the DoS has got an effect: the jenkins hash were unable to produce good enough keys. Or using the 32 bits from the 96 internal ones is not sufficient.

But in the non-DoS random pattern case, there was 819200 entries / 27345 child-nodes =~ 29 entries/child-nodes, that's still around 10% utilization. So it looks it's not the jenkins hash which produces the sparse tree.

Quoted 3 lines

The problem is how do you know which entry along a path is the oldest? Entries aren't always added to the front like with the current linked lists in the hashtable.

We could check the timer of the entry: the oldest one is that which would time out nearest in the future.

[...]

Quoted 10 lines

these happen at the same time:
packet from client A hashes into bucket C, lock and add entry. packet from client B hashes into bucket D, lock and add entry.

and after that these happen at the same time:
packet from client A hashes into bucket D, lock and find entry, remove entry in bucket C
packet from client B hashes into bucket C, lock and find entry, remove entry in bucket D

Quoted 7 lines

This leads to no conntrack entry created for any of the clients connection attempts.

The solution would be "ordered independent locking" which locks and adds entries based on bucket number that the tuplex hash into. That way we still keep the current behaviour while simplifying the locking, no chance of deadlocks.

That looks perfect!

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#20 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

Quoted 1 line · Jozsef Kadlecsik

Hi Martin

Hi Jozsef

Quoted 7 lines
Quoted 4 lines

HASHSHIFT and HASHNUM controls the number of struct hashentry per child. The original idea was to allocate 1 page (4kB) for each child but I got better results with 2kB, which means it isn't as wide as it was from the start.

Did you get faster lookups/insertions/deletions with half of the page size?

Yes I did, but I don't trust my testresults 100% (run on my laptop) because of the fact that my laptop gets better results if I put the padding at the start of struct hashentry than if I put the padding at the end.

Quoted 8 lines

As far as I see, the structure should satisfy "contradicting" requirements. We want an as low tree as possible, thus minimising the cost of the operations. That includes the number of levels of the childs and the number of slots in a bucket and the latter depends on the HASHALIGN, hashbits_t parameters and the members of the hashentry structure. So in theory we should maximize HASHSHIFT and minimize NUMENTRY. However we do not want a preallocated, huge, sparse hash either, and therefore it is hard to tell the best values.

Maximizing HASHSHIFT makes us allocate a lot for each node. And minimizing HASHNUM makes struct hashentry smaller, thus giving a _lot_ of buckets in each node.
Will having say 200 buckets with 3 entries in each bucket be better than 50 buckets with 12 entries in each bucket? Same number of entries in the node but one child-pointer per bucket, which might lead to even more child-nodes in the case where we have 200 buckets that fill up rather quick since they only hold a small number of entries. But on the other hand we hash to 200 buckets instead of 50 buckets so the total fill-rate of the node is the same for both cases.
And having lots of entries in a bucket doesn't really cause a performance degradation as long as you keep the bucket not larger than the cacheline size and it has to be cacheline aligned.

Having lots of buckets will give an even flatter tree.
I think I've tested this as well about a year ago but I can't remember the results.

Quoted 1 line

This structure is quite tricky :-).

Yes it is :) Image how I felt when I got it described to me in conversations on irc.
There's been a lot of experimentations and failures along the path and there's still a lot of things to test and rewrite.

Quoted 9 lines
Quoted 5 lines

Small hashbits_t doesn't have anything to do with it, hashbits_t is just for accelerating lookups. If we have a low number of struct hashentry per child-node we'll probably fill them up faster since there's fewer of them to be filled. And if we have a low NUMENTRY they will also be filled faster.

But how can we explain the so few entries in the buckets? Your numbers suggest that most of the buckets are pretty empty, as if there were two slots full from the 64 in the DoS case.

Yes, it's weird. Havn't had time to write the code to traverse the produce stats from the tree yet, who knows, tonight may be the night when that happens :)

Quoted 3 lines

Or we can say that the DoS has got an effect: the jenkins hash were unable to produce good enough keys. Or using the 32 bits from the 96 internal ones is not sufficient.

That might be the case.

Quoted 4 lines

But in the non-DoS random pattern case, there was 819200 entries / 27345 child-nodes =~ 29 entries/child-nodes, that's still around 10% utilization. So it looks it's not the jenkins hash which produces the sparse tree.

I'll see what I can dig out from the entries in the nodes, it might be very unbalanced.

Quoted 6 lines
Quoted 3 lines

The problem is how do you know which entry along a path is the oldest? Entries aren't always added to the front like with the current linked lists in the hashtable.

We could check the timer of the entry: the oldest one is that which would time out nearest in the future.

Ouch, this is exactly what we don't want to do. If we are under attack we don't want to start looking at entries to determine which entries to evict, that would result in lots of cachemisses which slows things down a lot.
The current eviction algorithm tries to evict entries along the path that the new entry will use, and respect the level of the entries so you don't end up evicting entries from the root-node all the time, those free slots will get filled up with new entries rather quickly and we don't want to evict things we probably just added.
But that doesn't say the current eviction algorithm does the right thing, it was just something me and Rusty came up with during the workshop as an aproximation.
Fast batch-killing of entries, but try to not evict from the often walked parts of the path too often. It is best-effort, no need to bend over backwards just to do the right thing in all situations, it's not worth it in the end.

Quoted 6 lines
Quoted 4 lines

The solution would be "ordered independent locking" which locks and adds entries based on bucket number that the tuplex hash into. That way we still keep the current behaviour while simplifying the locking, no chance of deadlocks.

That looks perfect!

It came to me after writing the description of the "unordered independent locking", it hit me like a punch in the face, it was so simple.

Signature · 1 line
/Martin
#21 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

Quoted 4 lines
Quoted 1 line

This structure is quite tricky :-).

Yes it is :) Image how I felt when I got it described to me in conversations on irc.

Hmm. Evoke this feeling again. :) Now I'll describe an easy way (haha) to get rid of half of the tuples, for the case of no-NAT. I did that before, but if you are now revisiting conntracking basics, maybe it's time to retell:

Notice that for the non-NAT case, the two tuples of a connection are fully symmetric in src(ip|port) vs. dst(ip|port). For ease of exposition, imagine each (ip|port) to be an 48-bit number.

Given two numbers A and B, a function can easily be implemented:

	symsort: N x N -> N x N x Z2
		given (a, b), if a <= b, result is (a, b, 0)
		given (a, b), if a  > b, result is (b, a, 1)

Given the symmetric tuples from both halves of one connection, this function returns the same A/B results in both cases, with a different flip bit (third result).

So, when doing the hash lookup, run symsort first, and look for the resulting "sorted" tuple.

The flip bit output of symsort needs to be taken into account when classifying original / other destination. Details...

One would have a single tuple, instead of two, in struct ip_conntrack. For NATted connections, an additional tuple would be allocated on demand, referenced from ip_conntrack by a pointer, and also put into the hashes.

When a non-NAT conntrack gets deleted, only one hash entry needs to be removed, avoiding the need for complex lock ordering schemes in that place. You can always tell you have this case, by looking whether the NAT-tuple-pointer is != 0.

Downsides:
- complexity
- second tuple in separate memory, in the NAT case. Maybe more cache misses in some places

Upsides in the non-NAT case:
- half the memory for tuples
- half the number of hash insertions and deletions with their assorted cache influences

best regards
Patrick

#22 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

In reply to Martin Josefsson

On Tue, 2006-03-07 at 19:33 +0100, Martin Josefsson wrote:

Hi Jozsef

Quoted 7 lines
Quoted 4 lines

But in the non-DoS random pattern case, there was 819200 entries / 27345 child-nodes =~ 29 entries/child-nodes, that's still around 10% utilization. So it looks it's not the jenkins hash which produces the sparse tree.

I'll see what I can dig out from the entries in the nodes, it might be very unbalanced.

I've added some very simple debug-code and here's what I've found so far when testing with random src/dst ip/port.

number of slots per hashtrie bucket: 5
...
Depth 4 - Number of children 0
Depth 4 - Number of buckets 0
Depth 4 - Number of not full buckets 0

Depth 3 - Number of children 0
Depth 3 - Number of buckets 7801856
Depth 3 - Number of entries 291689 (0%)
Depth 3 - Number of not full buckets 7801856

Depth 2 - Number of children 121904
Depth 2 - Number of buckets 262144
Depth 2 - Number of entries 1121175 (85%)
Depth 2 - Number of not full buckets 99698

Depth 1 - Number of children 4096
Depth 1 - Number of buckets 4096
Depth 1 - Number of entries 20480 (100%)
Depth 1 - Number of not full buckets 0

Depth 0 - Number of children 64
Depth 0 - Number of buckets 64
Depth 0 - Number of entries 256 (100%)
Depth 0 - Number of not full buckets 0

If we look at depth 2 we can see the following:

We have 121904 buckets that are "overfull", thus leading to an expansion.
(121904 * 5 + 291689) / (121904 * 5) = 1.48 = 148%

And we have 262144 - 121904 - 99698 = 40542 buckets that are 100% full.

And we have 99698 not full buckets with a number of entries:
1121175 - (121904 + 40542) * 5 = 308945 entries 308945 / (99698 * 5) = 0.62 = 62% usage

Summary:
121904 buckets that are 148% used.
40542 buckets that are 100% used.
99698 buckets that are 62% used.

So the jenkins hash doesn't seem to be able to distribute the entries very well.

This leads to the allocation of 121904 children for just 291689 entries, that's a huge waste of memory. But even if we are able to come up with a better hash algorithm for this we'll still have this problem when we start expanding deeper, the size of the tree simply explodes. One idea I've played with earlier is to change the number of buckets per child depending on the depth, so we have larger children at the top of the tree and then they get smaller further down. I'll have to revive that code (should be somewhere in svn) in order to say if it helped the memory usage or not, I know it made things a bit slower.

I've also tried making the buckets larger and decreasing HASHSHIFT in order to not exceed 4kB allocations, this allows the buckets to absorb the imperfectness of the hashing and memory usage goes down a _lot_. But... this is will simply destroy performance on machines with small cachelines as it will lead to lots of cachemisses per bucket.

Any ideas?

Signature · 1 line
/Martin
#23 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

Hi Martin,

Quoted 2 lines · Martin Josefsson

I've added some very simple debug-code and here's what I've found so far when testing with random src/dst ip/port.

[...]

Quoted 7 lines

Summary:
121904 buckets that are 148% used.
40542 buckets that are 100% used.
99698 buckets that are 62% used.

So the jenkins hash doesn't seem to be able to distribute the entries very well.

I wrote first such words out of frustation, but actually I think the jenkins hash is fine. It was selected after a lot of testing, checking, comparison. There might of course be flaws in it, but

Quoted 4 lines

This leads to the allocation of 121904 children for just 291689 entries, that's a huge waste of memory. But even if we are able to come up with a better hash algorithm for this we'll still have this problem when we start expanding deeper, the size of the tree simply explodes.

we may simply see the consequences of the inherent behaviour of hashtree *and* the goodness of the jenkins hash: as part of the hash keys clash (they do because HASHSHIFT is relatively small) and as the tree grows, there will be too many empty branches (the whole hash key is pretty unique, there are to *few* near-clashes at the higher levels). But that's an assumption only.

Quoted 5 lines

One idea I've played with earlier is to change the number of buckets per child depending on the depth, so we have larger children at the top of the tree and then they get smaller further down. I'll have to revive that code (should be somewhere in svn) in order to say if it helped the memory usage or not, I know it made things a bit slower.

Usually we trade speed for memory. Double hashing does not help really either, because it slows down the lookups too :-( - I learnt it at ipset.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#24 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

In reply to Martin Josefsson

Hi Martin,

On Sun, 12 Mar 2006, Martin Josefsson wrote:

[...]

Quoted 7 lines

I've also tried making the buckets larger and decreasing HASHSHIFT in order to not exceed 4kB allocations, this allows the buckets to absorb the imperfectness of the hashing and memory usage goes down a _lot_. But... this is will simply destroy performance on machines with small cachelines as it will lead to lots of cachemisses per bucket.

Any ideas?

I took your code and messed with it: added input parameters (hashsize/number of elements), HASHNUM-dependent variants of hashtrie, added Paul Hsiesh's superfasthash function and an implementation of the shared-node fast hash from a SIGCOMM article. Then ran the different methods with increasing number of elements (table is half, full, two and four times more entry than hashsize) and created some graphs by gnuplot.

The results are at http://people.netfilter.org/kadlec/hashtrie/

What I could conclude is that hashtable requires the least memory and the fastest at inserting elements. Hashtrie is better in looking up entries when there are more than two times entries in the hash than the hashsize of the hashtable.

Something is required to improve hashtrie, so that it'd require less memory. Without losing speed, but possibly gaining, at insertion.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#25 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

Quoted 1 line · Jozsef Kadlecsik

Hi Martin,

Hi Jozsef

Quoted 6 lines

I took your code and messed with it: added input parameters (hashsize/number of elements), HASHNUM-dependent variants of hashtrie, added Paul Hsiesh's superfasthash function and an implementation of the shared-node fast hash from a SIGCOMM article. Then ran the different methods with increasing number of elements (table is half, full, two and four times more entry than hashsize) and created some graphs by gnuplot.

Wonderful, finally someone playing with it :)

Quoted 1 line

The results are at http://people.netfilter.org/kadlec/hashtrie/

Wow, that's some nice work. Must have taken quite a bit of time to rewrite my crappy code (started out as a single small .c file :) into something useful for testing and then performing all those tests.

A lot of your changes should go into svn, you have full freedom to change whatever you want.

I see that you have tested with HASHSHIFT 3, 4, 5, 6 and a 32byte cachelinesize.
That gives:

HASHSHIFT = 3
HASHNUM (buckets per child) = 8
childsize = HASHNUM * bucketsize (cachelinesize) = 256 bytes

HASHSHIFT = 4
HASHNUM (buckets per child) = 16
childsize = HASHNUM * bucketsize (cachelinesize) = 512 bytes

HASHSHIFT = 5
HASHNUM (buckets per child) = 32
childsize = HASHNUM * bucketsize (cachelinesize) = 1024 bytes

HASHSHIFT = 6
HASHNUM (buckets per child) = 64
childsize = HASHNUM * bucketsize (cachelinesize) = 2048 bytes

The original idea was to allocate PAGE_SIZE (4096 on i386) bytes at a time so it would be interesting to test HASHSHIFT = 7 (assuming a 32byte cachelinesize)

Another idea is to have varible number of buckets (HASHNUM) in the nodes, more buckets at the top of the trie and then decrease the number of buckets as we descend deeper into the trie. I've tried this earlier but with lowered performance, I don't remember anything about the change in memory-usage, and I don't trust my memory so it should be tested again.

HASHSHIFT=8 or 9 or even larger at depth 0 would be interesting to test.

Allocating more than PAGE_SIZE makes it an order-1 or larger allocation in kernel which is slower and more likely to fail but the the root-node it doesn't matter if it takes a little longer to allocate, and it's usually performed just after bootup when memory isn't very fragmented so it shouldn't fail.

Quoted 4 lines

What I could conclude is that hashtable requires the least memory and the fastest at inserting elements. Hashtrie is better in looking up entries when there are more than two times entries in the hash than the hashsize of the hashtable.

Yes, this matches the results I've seen as well. I've also run it under the cachegrind module of valgrind and among other things it keeps statistics on the number of instructions executed, and hashtrie executes a lot more instructions than the plain hashtable during lookup, yet hashtrie gets better performance in some cases due to the fact that it gets less cachemisses.

Quoted 2 lines

Something is required to improve hashtrie, so that it'd require less memory. Without losing speed, but possibly gaining, at insertion.

Yes, something is needed, right now I don't really see any solution to the memory-usage problem. The problem is less severe with larger cachelinesizes than 32bytes. 64byte cachelines gives a lot lower memory usage, 128bytes like the P4 has decreases the memoryusage even more (you have to decrease HASHSHIFT in order to not allocate too much memory for each node).

Now I'm going to think about the other hashtrie email I havn't responded to yet :)

Signature · 1 line
/Martin
#26 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

Hi Martin,

On Thu, 23 Mar 2006, Martin Josefsson wrote:

[...]

Quoted 2 lines

A lot of your changes should go into svn, you have full freedom to change whatever you want.

OK, I'll commit it sometime at the weekend. :-)

Quoted 7 lines

I see that you have tested with HASHSHIFT 3, 4, 5, 6 and a 32byte cachelinesize.
That gives:

HASHSHIFT = 3
HASHNUM (buckets per child) = 8
childsize = HASHNUM * bucketsize (cachelinesize) = 256 bytes

[...]

Quoted 3 lines

The original idea was to allocate PAGE_SIZE (4096 on i386) bytes at a time so it would be interesting to test HASHSHIFT = 7 (assuming a 32byte cachelinesize)

I just wanted to see the effect of different HASHSHIFT values. But I'll add HASHSHIFT = 7, that's just some new lines.

Quoted 8 lines

Another idea is to have varible number of buckets (HASHNUM) in the nodes, more buckets at the top of the trie and then decrease the number of buckets as we descend deeper into the trie. I've tried this earlier but with lowered performance, I don't remember anything about the change in memory-usage, and I don't trust my memory so it should be tested again.

HASHSHIFT=8 or 9 or even larger at depth 0 would be interesting to test.

I'm going into that direction: probably even higher HASHSHIF value at depth = 0 was fairer. The slow insert time compared to hashtable may come from the preallocated large hash in hashtable.

Quoted 6 lines

Yes, this matches the results I've seen as well. I've also run it under the cachegrind module of valgrind and among other things it keeps statistics on the number of instructions executed, and hashtrie executes a lot more instructions than the plain hashtable during lookup, yet hashtrie gets better performance in some cases due to the fact that it gets less cachemisses.

I'm thinking on an array-version, where instead of chaining of pointers, basically an array of ip_conntrack_tuple is used in the hashtable to avoid clashing. And IPv6 should be taken into account, too.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#27 lore raw

Re: Hashtrie testing2 (was: Re: [PATCH 4/4] first conntrack ID must be 1 not 2)

Hi Martin,

Quoted 4 lines · Jozsef Kadlecsik
Quoted 2 lines

A lot of your changes should go into svn, you have full freedom to change whatever you want.

OK, I'll commit it sometime at the weekend. :-)

[...]

The new version finally is in svn :-) The new results and comments can be found at

http://people.netfilter.org/kadlec/hashtrie

A short summary:

- sfhash does indeed faster than jhash when CPU-dependent optimization is enabled
- hastrie with variable hash sizes at the different level can help, surprisingly both in memory and speed. I tested three variants, there may easily be other ones which are even better.
- hasharray is very good on the price of some memory. But very good, and simple.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#28 lore raw

Re: Hashtrie testing2, dancing trees

In reply to Martin Josefsson

Just for interest, and I don't know how well tuned for processor cache it is, but Hans Reisers dancing trees are build to solve some of this problem; dancing trees keep themselves balanced.

I realise that filesystem timescales are not the same as packet processing timecales, I merely mention it for completeness.

Sam

#31 lore raw
In reply to Patrick McHardy
Quoted 5 lines · Patrick McHardy
Quoted 3 lines · Jozsef Kadlecsik

On Thu, 16 Feb 2006, Patrick McHardy wrote:

Quoted 7 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

(jiffies, tuples) would be unique even in that case.

Thats true. But what is the advantage over using the counter?

Actually it would still not be unique if connections live shorter than a jiffy and are resurrected.

In which case would there be any harm in it not being unqiue, if it were the same connection resurrected, why try to avoid having the same id?

Sam

#32 lore raw
Quoted 14 lines · Amin Azez
Quoted 12 lines · Patrick McHardy
Quoted 7 lines · Jozsef Kadlecsik
Quoted 4 lines · Patrick McHardy
Quoted 1 line

(jiffies, tuples) would be unique even in that case.

Thats true. But what is the advantage over using the counter?

Quoted 6 lines
Quoted 2 lines

Actually it would still not be unique if connections live shorter than a jiffy and are resurrected.

In which case would there be any harm in it not being unqiue, if it were the same connection resurrected, why try to avoid having the same id?

Besides solving an implementation problem, so ID was meant as a long-term unique identifier. For the life-time of a connection the tuples are already a unique identifier.

It's amazing, I've never had so many discussions about a single 32 bit field :)

#33 lore raw
Quoted 6 lines · Patrick McHardy
Quoted 5 lines
Quoted 2 lines

Actually it would still not be unique if connections live shorter than a jiffy and are resurrected.

In which case would there be any harm in it not being unqiue, if it were the same connection resurrected, why try to avoid having the same id?

Quoted 6 lines

Besides solving an implementation problem, so ID was meant as a long-term unique identifier. For the life-time of a connection the tuples are already a unique identifier.

It's amazing, I've never had so many discussions about a single 32 bit field :)

It's amazingly hard to accept we need it :-).

Putting aside the implementation problem, there are so many information already available in the conntrack entries: tuples, packet and byte counters, state, timeout value. Those together can serve as a short-term unique identifier, even after the entry is actually deleted. Not bulletproof, but in practice those can be sufficient.

I could not resist... :-))

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#29 lore raw

Re: Hashtrie testing2, dancing trees

In reply to Amin Azez
Quoted 6 lines · Amin Azez

Just for interest, and I don't know how well tuned for processor cache it is, but Hans Reisers dancing trees are build to solve some of this problem; dancing trees keep themselves balanced.

I realise that filesystem timescales are not the same as packet processing timecales, I merely mention it for completeness.

I pondered over trees but excluded the whole family as too slow for our purposes.

We aim to process packets near at wire speed and that implies the fastest algorithms. A little complexity can have dire consequences - I was quite surprised that the shared node method was so weak compared to the hashes/tries when it required just a little bit more internal maintenance.

I believe keeping a tree balanced requires too expensive operations which we cannot afford.

Best regards,
Jozsef
-
E-mail : [email protected], [email protected] PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics

          H-1525 Budapest 114, POB. 49, Hungary
#34 lore raw
In reply to Jozsef Kadlecsik
Quoted 19 lines · Jozsef Kadlecsik
Quoted 6 lines · Patrick McHardy
Quoted 5 lines
Quoted 2 lines

Actually it would still not be unique if connections live shorter than a jiffy and are resurrected.

In which case would there be any harm in it not being unqiue, if it were the same connection resurrected, why try to avoid having the same id?

Quoted 6 lines

Besides solving an implementation problem, so ID was meant as a long-term unique identifier. For the life-time of a connection the tuples are already a unique identifier.

It's amazing, I've never had so many discussions about a single 32 bit field :)

It's amazingly hard to accept we need it :-).

Quoted 7 lines

Putting aside the implementation problem, there are so many information already available in the conntrack entries: tuples, packet and byte counters, state, timeout value. Those together can serve as a short-term unique identifier, even after the entry is actually deleted. Not bulletproof, but in practice those can be sufficient.

I could not resist... :-))

Me neither :) I was just pointing out the idea behind the ID, not necessarily condoning it. After discussing it with Rusty in Sevilla, it became clear that we can provide guarantees similar to filesystems without it, which seems to be good enough. So I have absolutely nothing against removing it. In fact, IIRC the last discussion stopped after I had sent a patch to remove it. I need to dig out that patch again :)

#35 lore raw
Quoted 7 lines · Patrick McHardy

Me neither :) I was just pointing out the idea behind the ID, not necessarily condoning it. After discussing it with Rusty in Sevilla, it became clear that we can provide guarantees similar to filesystems without it, which seems to be good enough. So I have absolutely nothing against removing it. In fact, IIRC the last discussion stopped after I had sent a patch to remove it. I need to dig out that patch again :)

I didn't contribute to any of these discussions anymore, since I already made my opinion on this quite clear very early on: I don't have any problem whatsoever with non-uniqueness ;)

So if there's now a majority of people who want to delete the ID: Go for it :)

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
#36 lore raw
Quoted 2 lines · Harald Welte

So if there's now a majority of people who want to delete the ID: Go for it :)

Found the patch again. What it does is:

- note entry of next conntrack to be dumped and keep a reference to it
- when continuing, look for the conntrack and continue at it if its still there
- if not, dump the entire bucket again

In theory we could end up in an endless loop if the conntrack entry we're keeping the reference to is deleted everytime we want to continue dumping. It shouldn't be triggerable intentionally because of the jenkins hash though. If there are no objections I'll port it to nf_conntrack_netlink and submit it.

net/ipv4/netfilter/ip_conntrack_netlink.c +22 -8
index e0b5926..5a1769d 100644
@@ -387,38 +387,52 @@ nfattr_failure:
 static int ctnetlink_done(struct netlink_callback *cb)
 {
 	DEBUGP("entered %s\n", __FUNCTION__);
+	if (cb->args[1])
+		ip_conntrack_put(cb->args[1]);
 	return 0;
 }
 
 static int
 ctnetlink_dump_table(struct sk_buff *skb, struct netlink_callback *cb)
 {
-	struct ip_conntrack *ct = NULL;
+	struct ip_conntrack *ct;
 	struct ip_conntrack_tuple_hash *h;
 	struct list_head *i;
-	u_int32_t *id = (u_int32_t *) &cb->args[1];
 
 	DEBUGP("entered %s, last bucket=%lu id=%u\n", __FUNCTION__, 
 			cb->args[0], *id);
 
 	read_lock_bh(&ip_conntrack_lock);
-	for (; cb->args[0] < ip_conntrack_htable_size; cb->args[0]++, *id = 0) {
+	for (; cb->args[0] < ip_conntrack_htable_size; cb->args[0]++) {
+restart:
 		list_for_each_prev(i, &ip_conntrack_hash[cb->args[0]]) {
 			h = (struct ip_conntrack_tuple_hash *) i;
 			if (DIRECTION(h) != IP_CT_DIR_ORIGINAL)
 				continue;
 			ct = tuplehash_to_ctrack(h);
-			if (ct->id <= *id)
-				continue;
+			if (cb->args[1]) {
+				if (ct == cb->args[1]) {
+					ip_conntrack_put(cb->args[1]);
+					cb->args[1] = NULL;
+				} else
+					continue;
+			}
 			if (ctnetlink_fill_info(skb, NETLINK_CB(cb->skb).pid,
 		                        	cb->nlh->nlmsg_seq,
 						IPCTNL_MSG_CT_NEW,
-						1, ct) < 0)
+						1, ct) < 0) {
+				nf_conntrack_get(&ct->ct_general);
+				cb->args[1] = ct;
 				goto out;
-			*id = ct->id;
+			}
+		}
+		if (cb->args[1]) {
+			ip_conntrack_put(cb->args[1]);
+			cb->args[1] = NULL;
+			goto restart;
 		}
 	}
-out:	
+out:
 	read_unlock_bh(&ip_conntrack_lock);
 
 	DEBUGP("leaving, last bucket=%lu id=%u\n", cb->args[0], *id);
#37 lore raw
Quoted 8 lines · Patrick McHardy
Quoted 2 lines · Harald Welte

So if there's now a majority of people who want to delete the ID: Go for it :)

Found the patch again. What it does is:

Quoted 8 lines

- note entry of next conntrack to be dumped and keep a reference to it
- when continuing, look for the conntrack and continue at it if its still there
- if not, dump the entire bucket again

In theory we could end up in an endless loop if the conntrack entry we're keeping the reference to is deleted everytime we want to continue dumping.

Why not defer the ip_conntrack_put until after ctnetlink_fill_info, would that avoid the problem altogether?

It's no longer the entry of the next conntrack but the entry of the last conntrack by the time it gets deleted then...? Or have I misunderstood the way in which the loop would occur?

Sam

#38 lore raw
Quoted 14 lines · Amin Azez
Quoted 10 lines · Patrick McHardy

Found the patch again. What it does is:

- note entry of next conntrack to be dumped and keep a reference to it
- when continuing, look for the conntrack and continue at it if its still there
- if not, dump the entire bucket again

In theory we could end up in an endless loop if the conntrack entry we're keeping the reference to is deleted everytime we want to continue dumping.

Quoted 6 lines

Why not defer the ip_conntrack_put until after ctnetlink_fill_info, would that avoid the problem altogether?

It's no longer the entry of the next conntrack but the entry of the last conntrack by the time it gets deleted then...? Or have I misunderstood the way in which the loop would occur?

Yes, the loop is interrupted when the skb is full and continued when userspace issues the next recvmsg(). The reference is kept to find the point where to continue.

#40 lore raw
In reply to a message not in the archive
Quoted 8 lines · Amin Azez
Quoted 6 lines · Patrick McHardy
Quoted 4 lines

It's no longer the entry of the next conntrack but the entry of the last conntrack by the time it gets deleted then...? Or have I misunderstood the way in which the loop would occur?

Quoted 6 lines
Quoted 5 lines

Yes, the loop is interrupted when the skb is full and continued when userspace issues the next recvmsg(). The reference is kept to find the point where to continue.

Did you mean "yes, you misunderstood" or "yes, good idea"?

Yes, you misunderstood :)

Quoted 3 lines

I thought that what would theoretically cause the problem if the next-conntrack is deleted was the fact that conntrack-put is called before ctnetlink_fill_info.

Its only a marker, once we have found it in the list we don't need that reference anymore.

Quoted 8 lines

The problem may not be entirely theoretical if the conntrack is being deleted by a userspace conntrack client in response to what it reads when enumerating conntracks. (The conntrack may spring back into existance as an resurrected established connection - and also may therefore be likely in the case of a full contrack table where connections flip-flop their resurrected conntrack entry, Rather than issue warnings to conntrack developers to avoid certain kinds of design, it would be better to avoid this.

The marker points to the next entry that beed dumped yet, so enumerate-and-delete won't affect it. It is also not the ID of the connection but the pointer to the conntrack entry that is used, so resurrections don't affect it in any way.

The problem is in my opinion purely theoretical so far:

- the bucket beeing dumped must contain enough entries to exceed the size of a single netlink message (very unlikely)

- when continuing to dump, the entry we wanted to dump next must be gone - and there must still be enough entries in the bucket to exceed the skb.

For an endless loop we must have a steady refill of the bucket with new conntrack entries, otherwise at some point it won't exceed the skb anymore and we can move on to the next bucket. The jenkins hash should prevent this situation.