summaryrefslogtreecommitdiffstats
path: root/tools
diff options
context:
space:
mode:
authorMatthew Wilcox <mawilcox@microsoft.com>2017-11-30 13:45:11 -0500
committerMatthew Wilcox <mawilcox@microsoft.com>2018-02-06 16:41:29 -0500
commit6ce711f2750031d12cec91384ac5cfa0a485b60a (patch)
treed1d3b3754641b22e51cc0fdeecb02a0ac7b31b54 /tools
parent72fd6c7be701d80eef34da305a6294c61520fe13 (diff)
downloadlinux-6ce711f2750031d12cec91384ac5cfa0a485b60a.tar.bz2
idr: Make 1-based IDRs more efficient
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: Matthew Wilcox <mawilcox@microsoft.com>
Diffstat (limited to 'tools')
-rw-r--r--tools/testing/radix-tree/idr-test.c7
1 files changed, 5 insertions, 2 deletions
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 36437ade429c..44ef9eba5a7a 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -153,11 +153,12 @@ void idr_nowait_test(void)
idr_destroy(&idr);
}
-void idr_get_next_test(void)
+void idr_get_next_test(int base)
{
unsigned long i;
int nextid;
DEFINE_IDR(idr);
+ idr_init_base(&idr, base);
int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
@@ -244,7 +245,9 @@ void idr_checks(void)
idr_alloc_test();
idr_null_test();
idr_nowait_test();
- idr_get_next_test();
+ idr_get_next_test(0);
+ idr_get_next_test(1);
+ idr_get_next_test(4);
}
/*