Re: [PATCH 10/10] idr: Rework idr_preload()

[Tejun Heo <tj@kernel.org>]

Hello, Kent.

On Tue, Jun 18, 2013 at 05:02:30PM -0700, Kent Overstreet wrote:
> With the new ida implementation, that doesn't work anymore - the new ida
> code grows its bitmap tree by reallocating the entire thing in power of
> two increments. Doh.

So, I'm not sure about the single contiguous array implementation.  It
introduces some nasty characteristics such as possibly too large
contiguous allocation, bursty CPU usages, and loss of the ability to
handle ID allocations clustered in high areas - sure, the old ida
wasn't great on that part either but this can be much worse.

In addition, I'm not sure what this single contiguous allocation buys
us.  Let's say each leaf node size is 4k.  Even with in-array tree
implementation, it should be able to serve 2k IDs per-page, which
would be enough for most use cases and with a bit of caching it can
easily achieve both the performance benefits of array implementation
and the flexibility of allocating each leaf separately.  Even without
caching, the tree depth would normally be much lower than the current
implementation and the performance should be better.  If you're
bothered by having to implement another radix tree for it, it should
be possible to just implement the leaf node logic and use the existing
radix tree for internal nodes, right?

> So we need a slightly different trick. Note that if all allocations from
> an idr start by calling idr_prealloc() and disabling premption, at
> most nr_cpus() allocations can happen before someone calls
> idr_prealloc() again.

But we allow mixing preloaded and normal allocations and users are
allowed to allocate as many IDs they want after preloading.  It should
guarantee that the first allocation after preloading follows the
stronger allocation flag, and the above approach can't guarantee that.
You can declare that if preload is to work, all allocators of the ida
should preload and enforce it but that restriction arises only because
you're using this single array implementation.  It's another drawback
of this particular approach.  There seem to be a lot of cons and I
can't really see what the pros are.

Thanks.

-- 
tejun