summaryrefslogtreecommitdiff
path: root/tools/testing/radix-tree/main.c
diff options
context:
space:
mode:
authorMatthew Wilcox <mawilcox@microsoft.com>2016-12-20 18:27:56 +0300
committerMatthew Wilcox <mawilcox@microsoft.com>2017-02-14 05:44:01 +0300
commit0a835c4f090af2c76fc2932c539c3b32fd21fbbb (patch)
tree729c24514309afc323ee08e6d8336eb1e558406e /tools/testing/radix-tree/main.c
parent0ac398ef391b53122976325ab6953456ce8e8310 (diff)
downloadlinux-0a835c4f090af2c76fc2932c539c3b32fd21fbbb.tar.xz
Reimplement IDR and IDA using the radix tree
The IDR is very similar to the radix tree. It has some functionality that the radix tree did not have (alloc next free, cyclic allocation, a callback-based for_each, destroy tree), which is readily implementable on top of the radix tree. A few small changes were needed in order to use a tag to represent nodes with free space below them. More extensive changes were needed to support storing NULL as a valid entry in an IDR. Plain radix trees still interpret NULL as a not-present entry. The IDA is reimplemented as a client of the newly enhanced radix tree. As in the current implementation, it uses a bitmap at the last level of the tree. Signed-off-by: Matthew Wilcox <willy@infradead.org> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Tejun Heo <tj@kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'tools/testing/radix-tree/main.c')
-rw-r--r--tools/testing/radix-tree/main.c6
1 files changed, 6 insertions, 0 deletions
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index f7e9801a6754..ddd90a11db3f 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -3,6 +3,7 @@
#include <unistd.h>
#include <time.h>
#include <assert.h>
+#include <limits.h>
#include <linux/slab.h>
#include <linux/radix-tree.h>
@@ -314,6 +315,11 @@ static void single_thread_tests(bool long_run)
rcu_barrier();
printf("after dynamic_height_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
+ idr_checks();
+ ida_checks();
+ rcu_barrier();
+ printf("after idr_checks: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
big_gang_check(long_run);
rcu_barrier();
printf("after big_gang_check: %d allocated, preempt %d\n",