netdev - Re: [Bug 106241] New: shutdown(3)/close(3) behaviour is incorrect for sockets in accept(3)

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: <1445609627.22974.150.camel@edumazet-glaptop2.roam.corp.google.com>
Date:	Fri, 23 Oct 2015 07:13:47 -0700
From:	Eric Dumazet <eric.dumazet@...il.com>
To:	Casper.Dik@...cle.com
Cc:	Al Viro <viro@...IV.linux.org.uk>,
	Alan Burlison <Alan.Burlison@...cle.com>,
	David Miller <davem@...emloft.net>, stephen@...workplumber.org,
	netdev@...r.kernel.org, dholland-tech@...bsd.org
Subject: Re: [Bug 106241] New: shutdown(3)/close(3) behaviour is incorrect
 for sockets in accept(3)

On Fri, 2015-10-23 at 15:20 +0200, Casper.Dik@...cle.com wrote:
> 
> >Yet another POSIX deficiency.
> >
> >When a server deals with 10,000,000+ socks, we absolutely do not care of
> >this requirement.
> >
> >O(log(n)) is still crazy if it involves O(log(n)) cache misses.
> 
> You miss the fire point of the algorithm; you *always* find an available 
> file descriptor in O(log(N)) (where N is the size of the table).
> 
> Does your algorithm guarantee that?

Its a simple bit map. Each cache line contains 64*8 = 512 bits. Lookup
is actually quite fast thanks to hardware prefetches. 

Main problem we had until recently was that we used to acquire fd table
lock 3 times per accept()/close() pair

This patch took care of the issue :

http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=8a81252b774b53e628a8a0fe18e2b8fc236d92cc

Then, adding a O_RANDOMFD flag (or O_DO_NOT_REQUIRE_POSIX_FD_RULES) is
helping a lot, as it allows us to pick a random starting point during
the bitmap search.

In practice, finding a slot in fd array is O(1) : one cache line miss
exactly.


--
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