netdev - Re: [RFC] [PATCH] udp: optimize lookup of UDP sockets to by including destination address in the hash key

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4AF30DE8.8010102@gmail.com>
Date:	Thu, 05 Nov 2009 18:39:52 +0100
From:	Eric Dumazet <eric.dumazet@...il.com>
To:	Octavian Purdila <opurdila@...acom.com>
CC:	Lucian Adrian Grijincu <lgrijincu@...acom.com>,
	netdev@...r.kernel.org
Subject: Re: [RFC] [PATCH] udp: optimize lookup of UDP sockets to by including
 destination address in the hash key

Octavian Purdila a écrit :
> On Thursday 05 November 2009 18:36:50 you wrote:
>> Octavian Purdila a écrit :
>>> IIRC, we first saw this issue in VoIP tests with up to 16000 sockets
>>> bound on a certain port and IP addresses (each IP address is assigned to
>>> a particular interface). We need this setup in order to emulate lots of
>>> VoIP users each with a different IP address and possible a different L2
>>> encapsulation.
>> Interesting case indeed, is it SIP 5060 port or RTP ports ?
>> (I want to know how many messages per second you want to receive)
>>
>> An rbtree with 16000 elements has 15 levels, its a lot, but OK
>> for small trafic.
>>
> 
> Yep the signaling port not the RTP port, and yes I think there is a fairly  
> small amount of traffic and rbtree might work.
> 
> BTW, there is another side of this problem, the time to bind() those 16K 
> sockets before starting the test - at least on 2.6.7 we didn't yet get to look 
> at this issue on a recent kernel.
> 

Yes, this is O(N^2) algo :

0.3 seconds to bind 8000 UDP sockets on same port (different IPs)
1.5 secs / 12000 sockets
5.3 secs / 16000 sockets 
18  secs / 24000 sockets
36  secs / 32000 sockets

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html