netdev - Re: Allowing more than 64k connections and heavily optimize bind(0) time.

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: <20081226083107.GA2462@ioremap.net>
Date:	Fri, 26 Dec 2008 11:31:07 +0300
From:	Evgeniy Polyakov <zbr@...emap.net>
To:	David Miller <davem@...emloft.net>
Cc:	netdev@...r.kernel.org
Subject: Re: Allowing more than 64k connections and heavily optimize bind(0) time.

On Wed, Dec 24, 2008 at 10:09:26PM +0300, Evgeniy Polyakov (zbr@...emap.net) wrote:
> With simple extension to the binding mechanism, which allows to bind more
> than 64k sockets (or smaller amount, depending on sysctl parameters),
> we have to traverse the whole bind hash table to find out empty bucket.
> And while it is not a problem for example for 32k connections, bind()
> completion time grows exponentially (since after each successful binding
> we have to traverse one bucket more to find empty one) even if we start
> each time from random offset inside the hash table.
> 
> So, when hash table is full, and we want to add another socket, we have
> to traverse the whole table no matter what, so effectivelly this will be
> the worst case performance and it will be constant.
> 
> Attached picture shows bind() time depending on number of already bound
> sockets.

Really attached.

-- 
	Evgeniy Polyakov

Download attachment "bind_time.png" of type "image/png" (38816 bytes)