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@oracle.com wrote:

quoted

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.