Re: [patch 1/2] ufd v1 - unsequential O(1) fdmap core

[Davide Libenzi <davidel@xmailserver.org>]

On Mon, 4 Jun 2007, Eric Dumazet wrote:

> Goals :
> 1) libc wants 'private fds'
> 2) Latencies of get_unused_fd() for huge processes (more than 100.000 file handles)
> 
> Point 1) can use a top-down allocation, or use a 'last unused' index.
> 
> 
> Point 2) Instead of introducing a *complex* layer, couldnt we improve existing one ?

Complex layer?! It's an array with free slots chained by a double linked 
list.


> If the main problem we want to solve is the potentially slow bitmap 
> search, 
> we could logically divide the open_fds bitmap into pages (4096*8 = 32768 
> bits per page on i386/x86_64 arches)
> 
> We would have to add a new field in 'struct fdtable', pointer to an 
> array of u32 counters, that would count the number of 'one' bits in each 
> PAGE. This array is tiny : 128 bytes only for 1.000.000 file handles
> 
> get_unused_fd() could then use this array to select an appropriate page 
> (a page known to have at least one zero bit), then do a 
> find_next_zero_bit() restricted to at most PAGE_SIZE bytes. Max latency 
> would be similar to vm one when clearing a page. If applications use 
> Point 1) hint (asking kernel one fd, not the POSIX low fd), typical 
> latency will be null.

And look at what you're describing here, talking about simplicity. You'd 
still need two bitmaps, so you'd still need the out-of-fdmap.c/h code. 
You're trying to fit an horse-shoe to a deer :)
The most appropriate structure for this, is an array (O(1) lookup) with 
free elements chained by a dbl linked list (O(1) alloc and free). Plus, 
the extra pointer can nicely fit other per-allocated-fd flags w/out adding 
extra custom flags bitmaps to the fdtable.



- Davide


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/