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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
