Re: [RFC] Rebasing the IDR

[Chris Wilson]

Quoting Matthew Wilcox (2017-11-30 17:36:30)
> About 40 of the approximately 180 users of the IDR in the kernel are
> "1-based" instead of "0-based".  That is, they never want to have ID 0
> allocated; they want to see IDs allocated between 1 and N.  Usually, that's
> expressed like this:
> 
>         /* Get the user-visible handle using idr. */
>         ret = idr_alloc(&file_priv->object_idr, obj, 1, 0, GFP_KERNEL);
> 
> The current implementation of this grieves me.  You see, we mark each
> node of the radix tree according to whether it has any free entries
> or not, and entry 0 is always free!  If we've already allocated 10,000
> entries from this IDR, and see this call, we'll walk all the way down
> the left side of the tree looking for entry 1, get to the bottom,
> see that entries 1-63 are allocated, then walk up to the next level,
> see that 64-4095 are allocated, walk up to the next level, see that
> 8192-12287 has a free entry, and then start walking down again.

Hmm, missing the baseline to apply this patch. But I did the quick hack
of allocating index 0 of the idr and that did eradicate the
idr_get_free_cmn() from being at the top of the profiles for the
many-object stress tests. This improvement will be much appreciated.
-Chris