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

[Andrew Morton <akpm@linux-foundation.org>]

On Mon, 4 Jun 2007 10:42:27 +0200 Ingo Molnar <mingo@elte.hu> wrote:

> 
> * Andrew Morton <akpm@linux-foundation.org> wrote:
> 
> > If we just want some pseudo-private fd space for glibc to use then I'd 
> > have thought that the existing code could be tweaked to do that: 
> > top-down allocation, start at some high offset, etc.  But apparently 
> > there's more to it than this.
> 
> top-down has the problem of rlimits: 'where is top' is a variable 
> notion.

Well, sort-of.  rlimits affect the number of open files, not the actual fd
indices.  But whatever.

> start-at-high-offset using the existing scheme has a 'bitmap size' 
> problem: even at 2^28 the bitmap size would be 32+ MB. per process (!). 
> The bitmap could be allocated on demand, but that slows down the current 
> code, uglifies it, and it would still end up somewhere looking a bit 
> like Davide's clean new code.

OK, so the existing code doesn't support a holey bitmap.

> so, instead of trying to mesh this thing into the old fd data structures 
> which are very much centered around and tailored to the 
> continuous-allocation usage model, Davide cleanly separated it out into 
> a separate data structure that fits this independently-allocated usage 
> model well and leaves the original data structure alone. I'm strongly in 
> favor of such clean data structure separations.

a) Were IDR trees evaluated and if so, why were they rejected?

b) it's a bit disappointing that this new allocator is only usable for
   one specific application.  We have a *lot* of places in the kernel which
   want allocators of this type.  Many of them are open-coded and crappy. 
   Some use IDR trees.

   If we're going to go and add a complete new allocator, it would be
   good to position it as a library thing if poss.