• Matthew Wilcox's avatar
    idr: Make 1-based IDRs more efficient · 6ce711f2
    Matthew Wilcox authored
    About 20% of the IDR users in the kernel want the allocated IDs to start
    at 1.  The implementation currently searches all the way down the left
    hand side of the tree, finds no free ID other than ID 0, walks all the
    way back up, and then all the way down again.  This patch 'rebases' the
    ID so we fill the entire radix tree, rather than leave a gap at 0.
    Chris Wilson says: "I did the quick hack of allocating index 0 of the
    idr and that eradicated idr_get_free() from being at the top of the
    profiles for the many-object stress tests. This improvement will be
    much appreciated."
    Signed-off-by: default avatarMatthew Wilcox <mawilcox@microsoft.com>
idr.c 18.6 KB