On Tuesday 13 March 2007 10:32, Evgeniy Polyakov wrote:
On Fri, Mar 02, 2007 at 11:52:47AM +0300, Evgeniy Polyakov
([EMAIL PROTECTED]) wrote:
So, I ask network developers about testing environment for socket lookup
benchmarking. What would be the best test case to determine performance
of the
On Tue, Mar 13, 2007 at 11:08:27AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Tuesday 13 March 2007 10:32, Evgeniy Polyakov wrote:
On Fri, Mar 02, 2007 at 11:52:47AM +0300, Evgeniy Polyakov
([EMAIL PROTECTED]) wrote:
So, I ask network developers about testing environment for socket
Michael K. Edwards writes:
This, incidentally, seems very similar to the process that Robert
Olsson and Stefan Nilsson have gone through with their trie/hash
project. Although I haven't tried it out yet and don't have any basis
for an independent opinion, the data and analysis provided
On Sun, Mar 04, 2007 at 02:02:36AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
On 3/3/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
Btw, you could try to implement something you have written above to show
its merits, so that it would not be an empty words :)
Before I implement, I
On 3/3/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
Btw, you could try to implement something you have written above to show
its merits, so that it would not be an empty words :)
Before I implement, I design. Before I design, I analyze. Before I
analyze, I prototype. Before I prototype, I
From: Michael K. Edwards [EMAIL PROTECTED]
Date: Sun, 4 Mar 2007 02:02:36 -0800
On 3/3/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
Btw, you could try to implement something you have written above to show
its merits, so that it would not be an empty words :)
Before I implement, I design.
On 3/4/07, David Miller [EMAIL PROTECTED] wrote:
From: Michael K. Edwards [EMAIL PROTECTED]
Before I implement, I design. Before I design, I analyze. Before I
analyze, I prototype. Before I prototype, I gather requirements.
How the heck do you ever get to writing ANYTHING if you work that
On Fri, Mar 02, 2007 at 12:45:36PM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
On 3/2/07, Eric Dumazet [EMAIL PROTECTED] wrote:
Thank you for this report. (Still avoiding cache misses studies, while they
obviously are the limiting factor)
1) The entire point of going to a
On Sat, Feb 17, 2007 at 04:13:02PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea for solving it.
Yes, I have been playing around with the same idea
On Friday 02 March 2007 09:52, Evgeniy Polyakov wrote:
Ok, I've ran an analysis of linked lists and trie traversals and found
that (at least on x86) optimized one list traversal is about 4 (!)
times faster than one bit lookup in trie traversal (or actually one
lookup in binary tree-like
On Fri, Mar 02, 2007 at 10:56:23AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Friday 02 March 2007 09:52, Evgeniy Polyakov wrote:
Ok, I've ran an analysis of linked lists and trie traversals and found
that (at least on x86) optimized one list traversal is about 4 (!)
times faster
On 3/2/07, Eric Dumazet [EMAIL PROTECTED] wrote:
Thank you for this report. (Still avoiding cache misses studies, while they
obviously are the limiting factor)
1) The entire point of going to a tree-like structure would be to
allow the leaves to age out of cache (or even forcibly evict them)
From: Michael K. Edwards [EMAIL PROTECTED]
Date: Wed, 21 Feb 2007 13:15:51 -0800
it had better be a 2-left hash with a compact
overflow pool for the rare case of second collision.
Just like Evgeniy, you should do your research too :-
The gain for multiple-hash schemes, such as 2-left,
On 2/22/07, David Miller [EMAIL PROTECTED] wrote:
From: Michael K. Edwards [EMAIL PROTECTED]
Date: Wed, 21 Feb 2007 13:15:51 -0800
it had better be a 2-left hash with a compact
overflow pool for the rare case of second collision.
Just like Evgeniy, you should do your research too :-
With 100k flows we typically see an aver depth 1.3 and a max depth 4. Right
This includes full srcport:dstport?
now there is only a dst entry in leaf nodes. So yes anything else we can put
in leaf is free.
How much would fit there?
-Andi
-
To unsubscribe from this list: send the line
From: Andi Kleen [EMAIL PROTECTED]
Date: Thu, 22 Feb 2007 12:41:05 +0100
With 100k flows we typically see an aver depth 1.3 and a max depth 4.
Right
This includes full srcport:dstport?
Yes.
-
To unsubscribe from this list: send the line unsubscribe netdev in
the body of a message to
On 22 Feb 2007 18:49:00 -0500, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
The rehash-every-10-minutes detail is theoretically unnecessary,
but does cover the case where a would-be attacker *does* get a chance
to look at a machine, such as by using routing delays to measure the
effectiveness of a
On Tue, Feb 20, 2007 at 12:03:04PM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
I just shown a problem in jenkins hash - it is not how to find a
differnet input for the same output - it is a _law_ which allows to
break a hash. You will add some constant, and that law will be turned
On Tue, Feb 20, 2007 at 12:09:59PM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
On 2/20/07, Michael K. Edwards [EMAIL PROTECTED] wrote:
Correct. That's called a weak hash, and Jenkins is known to be a
thoroughly weak hash. That's why you never, ever use it without a
salt, and you
On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
I shown that numbers 4 times already, do you read mails and links?
Did you see an artifact Eric showed with his data?
I showed all your thinking is wrong.
Some guys think MD5 checksum is full of artifacts, since its certainly
On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
I shown that numbers 4 times already, do you read mails and links?
Did you see an artifact Eric showed with his data?
I showed all your thinking
From: Evgeniy Polyakov [EMAIL PROTECTED]
Date: Wed, 21 Feb 2007 11:56:08 +0300
On Tue, Feb 20, 2007 at 12:09:59PM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
On 2/20/07, Michael K. Edwards [EMAIL PROTECTED] wrote:
Correct. That's called a weak hash, and Jenkins is known to be a
On Wednesday 21 February 2007 10:27, Evgeniy Polyakov wrote:
On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
I shown that numbers 4 times already, do you read mails and links?
Did you see an
On Wed, Feb 21, 2007 at 01:34:40AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
I repeat again - add your salt into jenkins hash and I will show you
that it has the same problems.
So, I'm waiting for your patch for jhash_*_words().
The problem is that whilst XOR, with arbitrary random
On Wed, Feb 21, 2007 at 10:38:22AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Wednesday 21 February 2007 10:27, Evgeniy Polyakov wrote:
On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
From: Evgeniy Polyakov [EMAIL PROTECTED]
Date: Wed, 21 Feb 2007 12:51:09 +0300
Linux route cache does not change $c (third parameter), and it _seems_
that distribution for the random $a and $b is fair, while when $c is
formed over attacker's data, random per-boot $initval does not help.
It is
Eric Dumazet [EMAIL PROTECTED] writes:
For example, sock_wfree() uses 1.6612 % of cpu because of false sharing of
sk_flags (dirtied each time SOCK_QUEUE_SHRUNK is set :(
Might be easily fixable by moving the fields around a bit?
If we want to optimize tcp, we should reorder fields to
On Wednesday 21 February 2007 13:41, Andi Kleen wrote:
Eric Dumazet [EMAIL PROTECTED] writes:
For example, sock_wfree() uses 1.6612 % of cpu because of false sharing
of sk_flags (dirtied each time SOCK_QUEUE_SHRUNK is set :(
Might be easily fixable by moving the fields around a bit?
For
From: Eric Dumazet [EMAIL PROTECTED]
Date: Wed, 21 Feb 2007 14:19:30 +0100
Now, when the rate of lookups/inserts/delete is high, with totally random
endpoints and cache *always* cold , 'tree structures' are not welcome (not
cache friendly)
But what about if tree lookup were free :-)
This
Look, Evgeniy. Eric and I may be morons but davem is not. He's
telling you, again and again, that DoS attacks do happen, that to
survive them you need for the distribution of tuples within hash
buckets to vary unpredictably from system to system and boot to boot,
and that XOR hash does not
David Miller writes:
But what about if tree lookup were free :-)
This is why I consider Robert Olsson's trash work the most promising,
if we stick sockets into his full flow identified routing cache trie
entries, we can eliminate lookup altogether.
Just like how he already uses
Robert Olsson a écrit :
David Miller writes:
But what about if tree lookup were free :-)
This is why I consider Robert Olsson's trash work the most promising,
if we stick sockets into his full flow identified routing cache trie
entries, we can eliminate lookup altogether.
Just
On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Monday 19 February 2007 16:14, Eric Dumazet wrote:
Because O(1) is different of O(log(N)) ?
if N = 2^20, it certainly makes a difference.
Yes, 1% of chains might have a length 10, but yet 99% of the
From: Evgeniy Polyakov [EMAIL PROTECTED]
Date: Tue, 20 Feb 2007 12:25:23 +0300
What you miss is the fact, that upper layers of the tree are always in the
cache. So its access cost nothing compared to every time new entry in
the hash table.
It will not be on a real computer spending reasonable
On Tuesday 20 February 2007 10:25, Evgeniy Polyakov wrote:
On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Monday 19 February 2007 16:14, Eric Dumazet wrote:
Because O(1) is different of O(log(N)) ?
if N = 2^20, it certainly makes a difference.
From: Eric Dumazet [EMAIL PROTECTED]
Date: Tue, 20 Feb 2007 11:04:15 +0100
Using a jenkin's hash permits a better hash distribution for a litle
cpu cost. I will post later a distribution simulation based on the
data gathered from the same real server.
Actually someone (I think it was Evgeniy
On Tue, Feb 20, 2007 at 01:57:45AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
What you miss is the fact, that upper layers of the tree are always in the
cache. So its access cost nothing compared to every time new entry in
the hash table.
It will not be on a real computer spending
On Tue, Feb 20, 2007 at 02:12:09AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
From: Eric Dumazet [EMAIL PROTECTED]
Date: Tue, 20 Feb 2007 11:04:15 +0100
Using a jenkin's hash permits a better hash distribution for a litle
cpu cost. I will post later a distribution simulation based on
On Tue, Feb 20, 2007 at 11:04:15AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
You totally miss the fact that the 1-2-4 MB cache is not available for you at
all. It is filled by User accesses. I dont care about DOS. I care about real
servers, servicing tcp clients. The TCP service/stack
On Tuesday 20 February 2007 11:12, David Miller wrote:
From: Eric Dumazet [EMAIL PROTECTED]
Date: Tue, 20 Feb 2007 11:04:15 +0100
Using a jenkin's hash permits a better hash distribution for a litle
cpu cost. I will post later a distribution simulation based on the
data gathered from the
On Tuesday 20 February 2007 11:30, Evgeniy Polyakov wrote:
On Tue, Feb 20, 2007 at 02:12:09AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
From: Eric Dumazet [EMAIL PROTECTED]
Date: Tue, 20 Feb 2007 11:04:15 +0100
Using a jenkin's hash permits a better hash distribution for a litle
On Tuesday 20 February 2007 11:44, Evgeniy Polyakov wrote:
On Tue, Feb 20, 2007 at 11:04:15AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
You totally miss the fact that the 1-2-4 MB cache is not available for
you at all. It is filled by User accesses. I dont care about DOS. I care
about
On Tue, Feb 20, 2007 at 12:10:22PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Please explain why you choseh = jhash_2words(faddr, laddr, ports);
h ^= h 16;
h ^= h 8;
jhash is very good, no need to try to be smarter, shufling some bytes... and
adding artifacts.
On Tue, Feb 20, 2007 at 12:09:51PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
If we want to optimize tcp, we should reorder fields to reduce number of
cache
lines, not change algos. struct sock fields are currently placed to reduce
holes, while they should be grouped by related fields
On Tuesday 20 February 2007 12:10, Eric Dumazet wrote:
Yep, it happend to be my tests :)
Jenkins hash was slower and had significant artifacts for some usage
cases ended up with extremely long chain length.
One can find more details at
On Tuesday 20 February 2007 12:29, Evgeniy Polyakov wrote:
On Tue, Feb 20, 2007 at 12:09:51PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
If we want to optimize tcp, we should reorder fields to reduce number of
cache lines, not change algos. struct sock fields are currently placed to
On Tue, Feb 20, 2007 at 12:34:59PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Getting into account that network stack with NAPI schedules several
packets to be queued into socket and all that happens without any
infuence from userspace, trie/tree wins again in that regard that
On Tue, Feb 20, 2007 at 12:30:18PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Tuesday 20 February 2007 12:10, Eric Dumazet wrote:
Yep, it happend to be my tests :)
Jenkins hash was slower and had significant artifacts for some usage
cases ended up with extremely long chain
On Tue, Feb 20, 2007 at 12:25:23PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
And there is _no_ O(1) - O(1) is just a hash entry selection, then you
need to add the whole chain path, which can be long enough.
For example for the length 9 you have 1000 entries - it is exactly size
of
On 2/20/07, David Miller [EMAIL PROTECTED] wrote:
Actually someone (I think it was Evgeniy in fact) made such
comparisons and found in his studies that not only does the current
ehash xor hash function distribute about as well as jenkins, it's
significantly cheaper to calculate :-)
However,
On Tue, Feb 20, 2007 at 07:07:16AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
On 2/20/07, David Miller [EMAIL PROTECTED] wrote:
Actually someone (I think it was Evgeniy in fact) made such
comparisons and found in his studies that not only does the current
ehash xor hash function
On 2/20/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
Jenkins _does_ have them, I showed tests half a year ago and in this
thread too. Actually _any_ hash has them it is just a matter of time
to find one.
I think you misunderstood me. If you are trying to DoS me from
outside with a hash
On Tue, Feb 20, 2007 at 07:49:11AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
On 2/20/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
Jenkins _does_ have them, I showed tests half a year ago and in this
thread too. Actually _any_ hash has them it is just a matter of time
to find one.
On Tuesday 20 February 2007 16:49, Michael K. Edwards wrote:
On 2/20/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
Jenkins _does_ have them, I showed tests half a year ago and in this
thread too. Actually _any_ hash has them it is just a matter of time
to find one.
I think you
On Tuesday 20 February 2007 16:59, Evgeniy Polyakov wrote:
On Tue, Feb 20, 2007 at 07:49:11AM -0800, Michael K. Edwards
([EMAIL PROTECTED]) wrote:
On 2/20/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
Jenkins _does_ have them, I showed tests half a year ago and in this
thread too. Actually
On Tue, Feb 20, 2007 at 05:08:12PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Adding XOR with constant value does not change distribution.
Variable salt will end up with differnet buckets for the same flow.
It is forbidden - it is not the situation created for passwd/des decades
ago.
On Tuesday 20 February 2007 17:20, Evgeniy Polyakov wrote:
On Tue, Feb 20, 2007 at 05:08:12PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Adding XOR with constant value does not change distribution.
Variable salt will end up with differnet buckets for the same flow.
It is forbidden -
On Tue, Feb 20, 2007 at 05:38:19PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
It is secrecy, not security - attacker will check the source and find
where constant per-boot value is added and recalculate attack vector -
we all were college students, it would be even more fun to crack.
On Tue, Feb 20, 2007 at 07:59:07PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
I've attached source code and running script.
$ ./run.sh
Yep, of course.
--
Evgeniy Polyakov
#include stdlib.h
#include stdio.h
#include errno.h
#include string.h
#include unistd.h
#include time.h
On Tuesday 20 February 2007 17:59, Evgeniy Polyakov wrote:
On Tue, Feb 20, 2007 at 05:38:19PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
It is secrecy, not security - attacker will check the source and find
where constant per-boot value is added and recalculate attack vector -
we
On Tuesday 20 February 2007 18:05, Evgeniy Polyakov wrote:
On Tue, Feb 20, 2007 at 07:59:07PM +0300, Evgeniy Polyakov
([EMAIL PROTECTED]) wrote:
I've attached source code and running script.
$ ./run.sh
Yep, of course.
Your test program is just bogus. artefacts come from your 'random'
On Tue, Feb 20, 2007 at 06:53:59PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
I've attached source code and running script.
$ ./run.sh
Yep, of course.
Your test program is just bogus. artefacts come from your 'random' generator.
You just increment a counter, assuming the key
On Tue, Feb 20, 2007 at 08:55:50PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
Here is a dump of possible addr/port pairs which end up badly
distributed:
8e363a50:27652 - c0a80001:20480
8e363a50:35529 - c0a80001:20480
8e363a50:40919 - c0a80001:20480
8e363a50:46720 - c0a80001:20480
On Tuesday 20 February 2007 19:00, Evgeniy Polyakov wrote:
As you can see, jhash has problems in a really trivial case of 2^16,
which in local lan is a disaster. The only reason jenkins hash is good
for hashing purposes is that is it more complex than xor one, and thus
it is harder to find a
On Tue, Feb 20, 2007 at 07:55:15PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Tuesday 20 February 2007 19:00, Evgeniy Polyakov wrote:
As you can see, jhash has problems in a really trivial case of 2^16,
which in local lan is a disaster. The only reason jenkins hash is good
for
On 2/20/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
And here are another ones which produce the same hash value.
Of course searching for pair for jhash('jhash is broken')
will require more steps, but it is doable.
That means that if attacker has a full control over one host, it can
create a
On Tuesday 20 February 2007 20:06, Evgeniy Polyakov wrote:
I added to my 'simulator_plugged_on_real_server' the average cost
calculation, relative to number of cache line per lookup.
ehash_size=2^20
xor hash :
386290 sockets, Avg lookup cost=3.2604 cache lines/lookup
393667 sockets,
All right, Eric, you and me so clevvah, let's embarrass our own selves
designing this thing in public instead of picking on poor Evgeniy.
Which would you rather RCU, a 2-left hash or a splay tree? 2-left
hash gets you excellent occupation fraction before the first real
collision, so you can be
On Tue, Feb 20, 2007 at 11:13:50AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
On 2/20/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
And here are another ones which produce the same hash value.
Of course searching for pair for jhash('jhash is broken')
will require more steps, but it
On Tue, Feb 20, 2007 at 08:17:31PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
I shown your test was bogus. All your claims are just bogus.
I claim your 'true random data' is a joke. rand() in your program is a pure
joke.
Care to reread your mail about your true random case with hash
On 2/20/07, Evgeniy Polyakov [EMAIL PROTECTED] wrote:
How I like personal insults - it is always fun to read about myself from
people who never knew me :)
On this occasion, I did not set out to insult you. I set out to
suggest an explanation for why cooler and grayer heads than mine are
not
On 2/20/07, Michael K. Edwards [EMAIL PROTECTED] wrote:
Correct. That's called a weak hash, and Jenkins is known to be a
thoroughly weak hash. That's why you never, ever use it without a
salt, and you don't let an attacker inspect the hash output either.
Weak in a cryptographic sense, of
Eric Dumazet [EMAIL PROTECTED] writes:
So are you speaking of one memory cache miss per lookup ?
Actually two: if the trie'ing allows RCUing you would save
the spinlock cache line too. This would increase the
break-even budget for the trie.
If not, you loose.
It all depends on if the
Michael K. Edwards [EMAIL PROTECTED] writes:
A better data structure for RCU, even with a fixed key space, is
probably a splay tree. Much less vulnerable to cache eviction DDoS
than a hash, because the hot connections get rotated up into non-leaf
layers and get traversed enough to keep them
On Sun, Feb 18, 2007 at 09:21:30PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Evgeniy Polyakov a e'crit :
On Sun, Feb 18, 2007 at 07:46:22PM +0100, Eric Dumazet
([EMAIL PROTECTED]) wrote:
Why anyone do not want to use trie - for socket-like loads it has
exactly constant
Andi Kleen writes:
If not, you loose.
It all depends on if the higher levels on the trie are small
enough to be kept in cache. Even with two cache misses it might
still break even, but have better scalability.
Yes the trick to keep root large to allow a very flat tree and few
On Monday 19 February 2007 12:41, Evgeniy Polyakov wrote:
1 microsecond ? Are you kidding ? We want no more than 50 ns.
Theory again.
Theory is nice, but I personally prefer oprofile :)
I base my comments on real facts.
We *want* 50 ns tcp lookups (2 cache line misses, one with reader
On Mon, Feb 19, 2007 at 02:38:13PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Monday 19 February 2007 12:41, Evgeniy Polyakov wrote:
1 microsecond ? Are you kidding ? We want no more than 50 ns.
Theory again.
Theory is nice, but I personally prefer oprofile :)
I base my
Actually for socket code any other binary tree will work perfectly ok -
socket code does not have wildcards (except listening sockets), so it is
possible to combine all values into one search key used in flat
one-dimensional tree - it scales as hell and allows still very high
lookup time.
As of
On Monday 19 February 2007 14:56, Evgeniy Polyakov wrote:
On Mon, Feb 19, 2007 at 02:38:13PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
On Monday 19 February 2007 12:41, Evgeniy Polyakov wrote:
1 microsecond ? Are you kidding ? We want no more than 50 ns.
Theory again.
Theory
On Mon, Feb 19, 2007 at 03:14:02PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Forget about cache misses and cache lines - we have a hash table, only
part of which is used (part for time-wait sockets, part for established
ones).
No you didnt not read my mail. Current ehash is not as
On Monday 19 February 2007 15:25, Evgeniy Polyakov wrote:
On Mon, Feb 19, 2007 at 03:14:02PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Forget about cache misses and cache lines - we have a hash table, only
part of which is used (part for time-wait sockets, part for established
On Monday 19 February 2007 16:14, Eric Dumazet wrote:
Because O(1) is different of O(log(N)) ?
if N = 2^20, it certainly makes a difference.
Yes, 1% of chains might have a length 10, but yet 99% of the lookups are
touching less than 4 cache lines.
With a binary tree, log(2^20) is 20. or
On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet wrote:
So even with a lazy hash function, 89 % of lookups are satisfied with less
than 6 compares.
Which sucks, as those are typically going to be cache misses (costing many
hundreds of cpu cycles). Hash chains fair very poorly under DoS
On Mon, Feb 19, 2007 at 01:26:42PM -0500, Benjamin LaHaise wrote:
On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet wrote:
So even with a lazy hash function, 89 % of lookups are satisfied with less
than 6 compares.
Which sucks, as those are typically going to be cache misses (costing
On 19 Feb 2007 13:04:12 +0100, Andi Kleen [EMAIL PROTECTED] wrote:
LRU tends to be hell for caches in MP systems, because it writes to
the cache lines too and makes them exclusive and more expensive.
That's why you let the hardware worry about LRU. You don't write to
the upper layers of the
Evgeniy Polyakov [EMAIL PROTECTED] writes:
My experiment shows almost 400 nsecs without _any_ locks - they are
removed completely - it is pure hash selection/list traverse time.
Are you sure you're not measuring TLB misses too? In user space
you likely use 4K pages. The kernel would use 2MB
Evgeniy Polyakov a e'crit :
On Mon, Feb 05, 2007 at 10:02:53AM -0800, [EMAIL PROTECTED] ([EMAIL PROTECTED])
wrote:
On Sat, 4 Feb 2007 [EMAIL PROTECTED] wrote:
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea
Evgeniy Polyakov a e'crit :
On Sun, Feb 18, 2007 at 07:46:22PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Why anyone do not want to use trie - for socket-like loads it has
exactly constant search/insert/delete time and scales as hell.
Because we want to be *very* fast. You cannot beat
A better data structure for RCU, even with a fixed key space, is
probably a splay tree. Much less vulnerable to cache eviction DDoS
than a hash, because the hot connections get rotated up into non-leaf
layers and get traversed enough to keep them in the LRU set. But I am
not a data structures
On 2/18/07, Michael K. Edwards [EMAIL PROTECTED] wrote:
... Much less vulnerable to cache eviction DDoS
than a hash, because the hot connections get rotated up into non-leaf
layers and get traversed enough to keep them in the LRU set.
Let me enlarge on this a bit. I used to work for a
On Mon, Feb 05, 2007 at 10:02:53AM -0800, [EMAIL PROTECTED] ([EMAIL PROTECTED])
wrote:
On Sat, 4 Feb 2007 [EMAIL PROTECTED] wrote:
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea for solving it.
Yes, I have
For purposes of discussion, I've attached a toy implementation
for doing dynamic resizing of a hashtable. It is useless, except
as a proof of concept.
I think this is very similar to what you are describing, no?
Er... not quite; that has a lot more overhead than what I was
thinking about.
On Sat, 4 Feb 2007 [EMAIL PROTECTED] wrote:
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea for solving it.
Yes, I have been playing around with the same idea for
doing dynamic resizing of the TCP hashtable.
Did
On Sat, 4 Feb 2007 [EMAIL PROTECTED] wrote:
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea for solving it.
I'm assuming the table is a power of 2 in size with open chaining
for collisions. When the chains get too long
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea for solving it.
I'm assuming the table is a power of 2 in size with open chaining
for collisions. When the chains get too long, the table is doubled.
When the chains get too
96 matches
Mail list logo
