Skip to contentSkip to conversation

performance issues (nat / conntrack)

DISCUSSION Don Cohen 3 participants 7 messages Jun 24, 2002 – Jun 25, 2002 2 messages not in the archive netfilter

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Don Cohen

author
#1 lore raw
Quoted 2 lines

From: "Jean-Michel Hemstedt" <[email protected]>

Quoted 1 line
Quoted 1 line

Since in my test, each connection is ephemeral (<10ms) ...

One question here is whether the traffic generator is acting like a real set of users or like an attacker. A real user would not keep trying to make connections at the same rate if the previous attempts were not being served. I suspect you're acting more like an attacker.

Quoted 4 lines
Quoted 2 lines

So I'm guessing that large number of entries in conntrack table is evidence that packets are being lost.

not only: a crashed endpoint breaking the tcp sequence causes also garbage entries in conntrack (known issue).

Again, a crashed endpoint would likely not get as many hits. My guess is that the reason for all the conntrack entries is related to what I described in my earlier mail. Creating conntrack entries is expensive. My machine could only do it about 1000 time/sec. Off hand I don't know which packets are dropped. I'd guess that the ones that make it through the conntrack code do get forwarded, but I don't know. If, for example, the return packets are lost because we're too busy adding new conntrack entries, then there's nothing to cause the entries to go away, other than those timeouts.

Quoted 4 lines
Quoted 1 line

Just wondering, how did you measure cpu load?

procinfo -n10 ; [d] for showing differences, which in fact, computes
the differences of cumulated cpu time (got from /proc/stat) on the given period: (tsys1-tsys0)/T

I see /proc/stat - user, nice, system, idle. Thank you. Very useful.

================

Quoted 2 lines
Quoted 1 line

Everybody agrees that NAT is evil and it should be avoided in all

circumstances.

This is news to me! Is this just because the implementation is lacking or some more fundamental reason?

#2 lore raw
Quoted 7 lines · Don Cohen
Quoted 2 lines

From: "Jean-Michel Hemstedt" <[email protected]>

Quoted 1 line
Quoted 1 line

Since in my test, each connection is ephemeral (<10ms) ...

One question here is whether the traffic generator is acting like a real set of users or like an attacker. A real user would not keep trying to make connections at the same rate if the previous attempts were not being served. I suspect you're acting more like an attacker.

He definitely is. The test he described is completely artificial, and does not represent any normal real world workload.

Nevertheless, it does point out a valid optimization chance. We discussed that months ago, and it's still there.

In the real world, nobody seems to care. I know I don't, and I really looked. It doesn't matter.

As for theories, the last time, we almost agreed that the hash function is very bad. Nobody did confirm that feeling, though.

Quoted 5 lines
Quoted 4 lines
Quoted 1 line

Just wondering, how did you measure cpu load?

procinfo -n10 ; [d] for showing differences, which in fact, computes
the differences of cumulated cpu time (got from /proc/stat) on the given period: (tsys1-tsys0)/T

I see /proc/stat - user, nice, system, idle. Thank you. Very useful.

A lot better would be a test with kernel profiling enabled.

best regards
Patrick

A message that is not in the archive (sent off-list or not yet received): [email protected]

#4 lore raw

Don,

(hope you don't mind me replying on-list)

Quoted 4 lines · Don Cohen
Quoted 2 lines · Patrick Schaaf

Nevertheless, it does point out a valid optimization chance. We discussed that months ago, and it's still there.

What's that?

Looking at the quality of the hash function used, and improving it.

Quoted 4 lines
Quoted 3 lines

In the real world, nobody seems to care. I know I don't, and I really looked. It doesn't matter.

I'm really lost here. What doesn't matter?

The relative slowness of conntrack vs. nonconntrack doesn't matter in the real world. I can reproduce it in artificial tests, but in reality, the arrival rates for new connections are lower. The reason, at least for me, is that I parallelize on multiple boxes long before conntrack reaches its breaking point, and I do that for different reasons (resilience and the other workload the boxes tend to have, like user level proxying.)

Quoted 3 lines
Quoted 2 lines

As for theories, the last time, we almost agreed that the hash function is very bad. Nobody did confirm that feeling, though.

What's wrong with the hash function?

It's suspected to be bad. Chains are suspected to become long. Bucket occupation is suspected to have high variance. Nobody checked, or at least nobody reported the results of such checking.

best regards
Patrick

author
#5 lore raw
Quoted 3 lines · Patrick Schaaf

Don,

(hope you don't mind me replying on-list)

No, I just hope the rest of the list doesn't mind.

Quoted 6 lines

The relative slowness of conntrack vs. nonconntrack doesn't matter in the real world. I can reproduce it in artificial tests, but in reality, the arrival rates for new connections are lower. The reason, at least for me, is that I parallelize on multiple boxes long before conntrack reaches its breaking point, and I do that for different reasons (resilience and the other workload the boxes tend to have, like user level proxying.)

It seems to me like a real problem when you're under attack. It means that a syn flood at a relatively low rate is effective. But I don't think that the hash function is the problem in that case. In fact, there is no hash function that solves that problem, since the attacker can always feed you data that ruins the hash function, unless of course you want the function to differ from one machine to the next and in effect be another secret.
I suggest instead that the hash lookup be limited to a small number of probes. If not found in, say, 10 probes, act like it's not there and the table is full. The attacker can still attack some particular bucket(s) (which doesn't do a lot of good - he's denying service to some small number of customers but has no control over which ones), but not the whole machine.

Quoted 7 lines
Quoted 3 lines
Quoted 2 lines

As for theories, the last time, we almost agreed that the hash function is very bad. Nobody did confirm that feeling, though.

What's wrong with the hash function?

It's suspected to be bad. Chains are suspected to become long. Bucket occupation is suspected to have high variance. Nobody checked, or at least nobody reported the results of such checking.

To me something like the sum of IP's and ports all mod something that is not a multiple of 2 seems ideal. I suppose it's something like that.

#6 lore raw
Quoted 5 lines

But I don't think that the hash function is the problem in that case. In fact, there is no hash function that solves that problem, since the attacker can always feed you data that ruins the hash function, unless of course you want the function to differ from one machine to the next and in effect be another secret.

I agree that such secret localization is the only chance you have against attacks on the hashes. It may even be doable.

Quoted 3 lines

I suggest instead that the hash lookup be limited to a small number of probes. If not found in, say, 10 probes, act like it's not there and the table is full.

For each packet, there is exactly one hash chain to look up. So you end up limiting the _length_ of the single chain when creating new entries.

To the user, that would mean random breakage long before saturation, for the sake of handling a hypothetical attack.

Thus, you also need an "am I under attack" algorithm first, and enable that limiting behaviour only when that algorithm triggers.

In practise, the denial of service attacks I've seen fill your slowest link, and there's nothing you can do about that except rate limit on the _other_ side.

best regards
Patrick

author
#7 lore raw
Quoted 6 lines · Patrick Schaaf
Quoted 3 lines

I suggest instead that the hash lookup be limited to a small number of probes. If not found in, say, 10 probes, act like it's not there and the table is full.

For each packet, there is exactly one hash chain to look up. So you end up limiting the _length_ of the single chain when creating new entries.

So far I agree.

Quoted 2 lines

To the user, that would mean random breakage long before saturation, for the sake of handling a hypothetical attack.

I'm not sure what meaning you have in mind here for the term "random". It should happen with extremely low probability. I'm expecting the max chain length to be a lot longer than the average chain length when the table is "full". But still short enough that a search of that length has negligible cost in comparison to the rest of the processing that has to be done for any packet.

Any statistics majors out there?
Assuming the choice of bucket is uniformly distributed, what's the probability in a table containing E entries in B buckets, that the next entry will fall into a bucket containing >= n elements?

Since a hash bucket costs much less than a conntrack entry I think we can afford to make the expected number of entries per bucket pretty small. Just choose an acceptable probability of this particular failure and a maximum search cost (proportional to the number of entries allowed in a bucket) and do the computation to be provided by our friendly statistics major to find the hash table size.

I'd expect my proposed sum of IP addresses and ports mod the largest odd number less than the table size to be uniformly distributed, but perhaps our volunteer can also tell us how to test that. Probably the answer is to do a printk when a bucket search reaches the limit. Then try to determine whether in those cases you're actually under attack or this is really just bad luck.

Quoted 2 lines

Thus, you also need an "am I under attack" algorithm first, and enable that limiting behaviour only when that algorithm triggers.

I prefer an algorithm that does not have to make this decision.

Quoted 3 lines

In practise, the denial of service attacks I've seen fill your slowest link, and there's nothing you can do about that except rate limit on the _other_ side.

This is a different problem. Here we have a situation where there are particular packets that have much greater cost than others. The attacker can succeed with much lower bandwidth than the slowest link. In my case the forwarding machine was saturated with 1000 small packets/sec (about 50KBytes), which was far below the network bandwidth. Even if we manage to fix the bandwidth attack problem you still have to deal with this other problem of requests that have low cost in bandwidth but high costs in other dimensions.

#8 lore raw

On Mon, Jun 24, 2002 at 08:18:57AM -0700, Don Cohen wrote:

First of all, excuse me being very quiet about this thread so far.

I want to point out that the core team is definitely interested in reports of performance and/or security/dos weaknesses, as well as proposed solutions how to fix them.

Thus, even if there are people arguing that we have been pointing out potential problems of the hash function or the overall conntrack implementation weeks/months ago, it still doesn't mean that there is no interest of having them fixed.

The current problem seems to be that nobody has enough time to thoroughly debug any of those issues.

So in the direction of Don this means:

1) we appreciate your reports
2) if you want this to be fixed soon, please do more detailed profiling in order to point out the code causing the problems
3) don't be discouraged if the overall response from the netfilter developers seems slow. For my part, I'm extremely busy right now, since I'm at the linux kernel summit together with other kernel subsystem maintainers, and I'm going to visit some two other conferences until mid-july. Apart from that, there's always the 'normal' maintaining and the long TODO list as well as the 2.5.x plans keeping me busy...

Thanks

Signature · 5 lines
Live long and prosper
- Harald Welte / [email protected]               http://www.gnumonks.org/
============================================================================
GCS/E/IT d- s-: a-- C+++ UL++++$ P+++ L++++$ E--- W- N++ o? K- w--- O- M- 
V-- PS+ PE-- Y+ PGP++ t++ 5-- !X !R tv-- b+++ DI? !D G+ e* h+ r% y+(*)