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

On Mon, 4 Jun 2007 05:55:42 -0700 (PDT)
Davide Libenzi <davidel@xxxxxxxxxxxxxxx> wrote:

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.


Bitmaps are already there, you didnt zap them.

Your proposal is going to double size taken by file table, since you need two long words
per file instead of one pointer.

You add conditional branches on very hot spots.

When you open/close a file, you need to access previous and next cells, so you need 3 cache lines, exactly like
current *legacy* code. (one for file pointer, one on each bitmap flags(open/close_on_exec) )

O(1) lookup doesnt imply it needs to be super-fast. You make a confusion about this.

O(128) is still O(1) for instance. Having to search a bit in a PAGE is a sensible compromise, if we dont add overhead
on each fget() calls.

Instead of adding complexity and a pile of new bugs (see how long it takes to bring RCU on files to a stable state), we can take a safe path. Then if it happens to still be a problem, we can consider the painfull way.

I probably can code a < 100 lines patch, later this evening after my day job.

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

Relevant Pages

  • Re: char **argv & char *argv[]
    ... "pointer to pointer to char". ... >> pointer)) pointing to the first element of an array. ... so we have to start adding more context. ... type "pointer to char", rather than "array MISSING_SIZE of char". ...
    (comp.lang.c)
  • Re: why cannot assign to function call
    ... hypothetical C-like languages, ... sizeof business would still indicate that a pointer was being passed. ... talk about variables of an array type. ... the earlier version of the standard didn't have numbered ...
    (comp.lang.python)
  • Re: multi dimensional arrays as one dimension array
    ... please - where does the standard say that such a conversion ... Pointer conversion yields a pointer to the same object as ... exist only where there are array declarations. ...
    (comp.lang.c)
  • Re: Pointer Equality for Different Array Objects
    ... Pointers to the same object are pointers to the same region of data storage. ... A pointer comaprison (for exact equality, ... we have the vague ("if the array is large enough"). ...
    (comp.lang.c)
  • Re: Evaluating unary *
    ... 'arr' exists, ... value can be used with the same syntax as would be used to access a 2D array of the kind you're referring to, but that 2D array is just a different way of looking as the same object that was already created by the definition of 'arr'. ... to me, it makes sense to return a pointer to the first value of an array, but to return the address of the pointer to the first value of an array, is not directly possible as such. ... lea eax, ...
    (comp.std.c)