[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <Pine.LNX.4.64.0706040523150.30231@alien.or.mcafeemobile.com>
Date: Mon, 4 Jun 2007 05:55:42 -0700 (PDT)
From: Davide Libenzi <davidel@...ilserver.org>
To: Eric Dumazet <dada1@...mosbay.com>
cc: Andrew Morton <akpm@...ux-foundation.org>,
Ingo Molnar <mingo@...e.hu>,
Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
Linus Torvalds <torvalds@...ux-foundation.org>,
Ulrich Drepper <drepper@...hat.com>
Subject: Re: [patch 1/2] ufd v1 - unsequential O(1) fdmap core
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@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists