On Sun, 3 Jun 2007, Eric Dumazet wrote:

quoted text
> Davide Libenzi a =E9crit :
> > Core code for the unsequential fdmap implementation. Random allocation,
> > exact allocation, de-allocation and lookup are all O(1) operations.
> > The only operation that is O(N) is the strict from-N-up kind of allocat=
ion,
quoted text
> > but that only used by F_DUPFD and it's definitely not frequently used
> > (and current code is O(N) too).
> > Like the "struct fdtable", the unsequential fdmap is RCU friendly too.
> >=20
> >=20
> >=20
>=20
> Could you please provide a diffstat ?

With or w/out the comments? :)



quoted text
> Me think : "Huge patch, and icache pressure for what exact gain ?"
>
> File descriptor allocation is dust compared to socket setup costs and net=
work
quoted text
> stuf. (Not speaking of close() wich is O(1) obviously)
>=20
> If we want a different file descriptor allocation, why should we use a
> parallel structure, and adding one level of complexity ?
>=20
> Instead of finding the first zero bit in a bitmap, we could just use a cy=
clic
quoted text
> allocation, ie finding a zero bit from a 'last' position. Keeping fd_coun=
t
quoted text
> would help not atempting a findzerobit in the case all bits are known to =
be
quoted text
> set.

A bitmap allocator made sense because it has the property of making=20
allocations compact. Once that requirement is relaxed, it does not make=20
any sense to use it (and you have still to modify it in any case).
I generally agree on code re-use, but that just not the right structure.=20
You can tweak it how much you like, but you're still doing a search inside=
=20
an N-sized bitmap. It's just the *wrong* structure.
I-cache pressure? All the extra code that you see out of fdmap.c/h, comes=
=20
from handling two "bitmaps", that you still have to have (unless you=20
plan to have a single huge botmap that covers legacy and non-sequential=20
areas). But with a bitmap structure, you're gonna have more D-cache=20
pressure. And that's a fact.



- Davide