lkml.org 
[lkml]   [2017]   [Dec]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [RFC] Rebasing the IDR
Date
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

\
 
 \ /
  Last update: 2017-12-11 11:55    [W:0.141 / U:0.584 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site