summaryrefslogtreecommitdiffstats
path: root/tools
diff options
context:
space:
mode:
authorMatthew Wilcox <mawilcox@microsoft.com>2016-12-20 10:27:56 -0500
committerMatthew Wilcox <mawilcox@microsoft.com>2017-02-13 21:44:01 -0500
commit0a835c4f090af2c76fc2932c539c3b32fd21fbbb (patch)
tree729c24514309afc323ee08e6d8336eb1e558406e /tools
parent0ac398ef391b53122976325ab6953456ce8e8310 (diff)
downloadlinux-0a835c4f090af2c76fc2932c539c3b32fd21fbbb.tar.gz
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')
-rw-r--r--tools/testing/radix-tree/.gitignore1
-rw-r--r--tools/testing/radix-tree/Makefile10
-rw-r--r--tools/testing/radix-tree/idr-test.c342
-rw-r--r--tools/testing/radix-tree/linux/gfp.h8
-rw-r--r--tools/testing/radix-tree/linux/idr.h1
-rw-r--r--tools/testing/radix-tree/linux/kernel.h1
-rw-r--r--tools/testing/radix-tree/main.c6
-rw-r--r--tools/testing/radix-tree/test.h2
8 files changed, 365 insertions, 6 deletions
diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore
index 11d888c..3b5534b 100644
--- a/tools/testing/radix-tree/.gitignore
+++ b/tools/testing/radix-tree/.gitignore
@@ -1,2 +1,3 @@
main
radix-tree.c
+idr.c
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 5274e88..3597a3a 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -2,8 +2,8 @@
CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE
LDFLAGS += -lpthread -lurcu
TARGETS = main
-OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_bit.o \
- regression1.o regression2.o regression3.o multiorder.o \
+OFILES = main.o radix-tree.o idr.o linux.o test.o tag_check.o find_bit.o \
+ regression1.o regression2.o regression3.o multiorder.o idr-test.o \
iteration_check.o benchmark.o
ifdef BENCHMARK
@@ -23,7 +23,11 @@ vpath %.c ../../lib
$(OFILES): *.h */*.h \
../../include/linux/*.h \
../../include/asm/*.h \
- ../../../include/linux/radix-tree.h
+ ../../../include/linux/radix-tree.h \
+ ../../../include/linux/idr.h
radix-tree.c: ../../../lib/radix-tree.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
+
+idr.c: ../../../lib/idr.c
+ sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
new file mode 100644
index 0000000..4dffad9
--- /dev/null
+++ b/tools/testing/radix-tree/idr-test.c
@@ -0,0 +1,342 @@
+/*
+ * idr-test.c: Test the IDR API
+ * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
+ * more details.
+ */
+#include <linux/idr.h>
+#include <linux/slab.h>
+#include <linux/kernel.h>
+#include <linux/errno.h>
+
+#include "test.h"
+
+#define DUMMY_PTR ((void *)0x12)
+
+int item_idr_free(int id, void *p, void *data)
+{
+ struct item *item = p;
+ assert(item->index == id);
+ free(p);
+
+ return 0;
+}
+
+void item_idr_remove(struct idr *idr, int id)
+{
+ struct item *item = idr_find(idr, id);
+ assert(item->index == id);
+ idr_remove(idr, id);
+ free(item);
+}
+
+void idr_alloc_test(void)
+{
+ unsigned long i;
+ DEFINE_IDR(idr);
+
+ assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0);
+ assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd);
+ idr_remove(&idr, 0x3ffd);
+ idr_remove(&idr, 0);
+
+ for (i = 0x3ffe; i < 0x4003; i++) {
+ int id;
+ struct item *item;
+
+ if (i < 0x4000)
+ item = item_create(i, 0);
+ else
+ item = item_create(i - 0x3fff, 0);
+
+ id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL);
+ assert(id == item->index);
+ }
+
+ idr_for_each(&idr, item_idr_free, &idr);
+ idr_destroy(&idr);
+}
+
+void idr_replace_test(void)
+{
+ DEFINE_IDR(idr);
+
+ idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL);
+ idr_replace(&idr, &idr, 10);
+
+ idr_destroy(&idr);
+}
+
+/*
+ * Unlike the radix tree, you can put a NULL pointer -- with care -- into
+ * the IDR. Some interfaces, like idr_find() do not distinguish between
+ * "present, value is NULL" and "not present", but that's exactly what some
+ * users want.
+ */
+void idr_null_test(void)
+{
+ int i;
+ DEFINE_IDR(idr);
+
+ assert(idr_is_empty(&idr));
+
+ assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
+ assert(!idr_is_empty(&idr));
+ idr_remove(&idr, 0);
+ assert(idr_is_empty(&idr));
+
+ assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
+ assert(!idr_is_empty(&idr));
+ idr_destroy(&idr);
+ assert(idr_is_empty(&idr));
+
+ for (i = 0; i < 10; i++) {
+ assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i);
+ }
+
+ assert(idr_replace(&idr, DUMMY_PTR, 3) == NULL);
+ assert(idr_replace(&idr, DUMMY_PTR, 4) == NULL);
+ assert(idr_replace(&idr, NULL, 4) == DUMMY_PTR);
+ assert(idr_replace(&idr, DUMMY_PTR, 11) == ERR_PTR(-ENOENT));
+ idr_remove(&idr, 5);
+ assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5);
+ idr_remove(&idr, 5);
+
+ for (i = 0; i < 9; i++) {
+ idr_remove(&idr, i);
+ assert(!idr_is_empty(&idr));
+ }
+ idr_remove(&idr, 8);
+ assert(!idr_is_empty(&idr));
+ idr_remove(&idr, 9);
+ assert(idr_is_empty(&idr));
+
+ assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
+ assert(idr_replace(&idr, DUMMY_PTR, 3) == ERR_PTR(-ENOENT));
+ assert(idr_replace(&idr, DUMMY_PTR, 0) == NULL);
+ assert(idr_replace(&idr, NULL, 0) == DUMMY_PTR);
+
+ idr_destroy(&idr);
+ assert(idr_is_empty(&idr));
+
+ for (i = 1; i < 10; i++) {
+ assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i);
+ }
+
+ idr_destroy(&idr);
+ assert(idr_is_empty(&idr));
+}
+
+void idr_nowait_test(void)
+{
+ unsigned int i;
+ DEFINE_IDR(idr);
+
+ idr_preload(GFP_KERNEL);
+
+ for (i = 0; i < 3; i++) {
+ struct item *item = item_create(i, 0);
+ assert(idr_alloc(&idr, item, i, i + 1, GFP_NOWAIT) == i);
+ }
+
+ idr_preload_end();
+
+ idr_for_each(&idr, item_idr_free, &idr);
+ idr_destroy(&idr);
+}
+
+void idr_checks(void)
+{
+ unsigned long i;
+ DEFINE_IDR(idr);
+
+ for (i = 0; i < 10000; i++) {
+ struct item *item = item_create(i, 0);
+ assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i);
+ }
+
+ assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0);
+
+ for (i = 0; i < 5000; i++)
+ item_idr_remove(&idr, i);
+
+ idr_remove(&idr, 3);
+
+ idr_for_each(&idr, item_idr_free, &idr);
+ idr_destroy(&idr);
+
+ assert(idr_is_empty(&idr));
+
+ idr_remove(&idr, 3);
+ idr_remove(&idr, 0);
+
+ for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
+ struct item *item = item_create(i, 0);
+ assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
+ }
+ assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC);
+
+ idr_for_each(&idr, item_idr_free, &idr);
+ idr_destroy(&idr);
+ idr_destroy(&idr);
+
+ assert(idr_is_empty(&idr));
+
+ for (i = 1; i < 10000; i++) {
+ struct item *item = item_create(i, 0);
+ assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i);
+ }
+
+ idr_for_each(&idr, item_idr_free, &idr);
+ idr_destroy(&idr);
+
+ idr_replace_test();
+ idr_alloc_test();
+ idr_null_test();
+ idr_nowait_test();
+}
+
+/*
+ * Check that we get the correct error when we run out of memory doing
+ * allocations. To ensure we run out of memory, just "forget" to preload.
+ * The first test is for not having a bitmap available, and the second test
+ * is for not being able to allocate a level of the radix tree.
+ */
+void ida_check_nomem(void)
+{
+ DEFINE_IDA(ida);
+ int id, err;
+
+ err = ida_get_new(&ida, &id);
+ assert(err == -EAGAIN);
+ err = ida_get_new_above(&ida, 1UL << 30, &id);
+ assert(err == -EAGAIN);
+}
+
+/*
+ * Check what happens when we fill a leaf and then delete it. This may
+ * discover mishandling of IDR_FREE.
+ */
+void ida_check_leaf(void)
+{
+ DEFINE_IDA(ida);
+ int id;
+ unsigned long i;
+
+ for (i = 0; i < IDA_BITMAP_BITS; i++) {
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new(&ida, &id));
+ assert(id == i);
+ }
+
+ ida_destroy(&ida);
+ assert(ida_is_empty(&ida));
+
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new(&ida, &id));
+ assert(id == 0);
+ ida_destroy(&ida);
+ assert(ida_is_empty(&ida));
+}
+
+/*
+ * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
+ * Allocating up to 2^31-1 should succeed, and then allocating the next one
+ * should fail.
+ */
+void ida_check_max(void)
+{
+ DEFINE_IDA(ida);
+ int id, err;
+ unsigned long i, j;
+
+ for (j = 1; j < 65537; j *= 2) {
+ unsigned long base = (1UL << 31) - j;
+ for (i = 0; i < j; i++) {
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, base, &id));
+ assert(id == base + i);
+ }
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ err = ida_get_new_above(&ida, base, &id);
+ assert(err == -ENOSPC);
+ ida_destroy(&ida);
+ assert(ida_is_empty(&ida));
+ rcu_barrier();
+ }
+}
+
+void ida_checks(void)
+{
+ DEFINE_IDA(ida);
+ int id;
+ unsigned long i;
+
+ radix_tree_cpu_dead(1);
+ ida_check_nomem();
+
+ for (i = 0; i < 10000; i++) {
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new(&ida, &id));
+ assert(id == i);
+ }
+
+ ida_remove(&ida, 20);
+ ida_remove(&ida, 21);
+ for (i = 0; i < 3; i++) {
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new(&ida, &id));
+ if (i == 2)
+ assert(id == 10000);
+ }
+
+ for (i = 0; i < 5000; i++)
+ ida_remove(&ida, i);
+
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, 5000, &id));
+ assert(id == 10001);
+
+ ida_destroy(&ida);
+
+ assert(ida_is_empty(&ida));
+
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, 1, &id));
+ assert(id == 1);
+
+ ida_remove(&ida, id);
+ assert(ida_is_empty(&ida));
+ ida_destroy(&ida);
+ assert(ida_is_empty(&ida));
+
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, 1, &id));
+ ida_destroy(&ida);
+ assert(ida_is_empty(&ida));
+
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, 1, &id));
+ assert(id == 1);
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, 1025, &id));
+ assert(id == 1025);
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, 10000, &id));
+ assert(id == 10000);
+ ida_remove(&ida, 1025);
+ ida_destroy(&ida);
+ assert(ida_is_empty(&ida));
+
+ ida_check_leaf();
+ ida_check_max();
+
+ radix_tree_cpu_dead(1);
+}
diff --git a/tools/testing/radix-tree/linux/gfp.h b/tools/testing/radix-tree/linux/gfp.h
index 7012098..39a0dcb 100644
--- a/tools/testing/radix-tree/linux/gfp.h
+++ b/tools/testing/radix-tree/linux/gfp.h
@@ -15,10 +15,12 @@
#define __GFP_DIRECT_RECLAIM 0x400000u
#define __GFP_KSWAPD_RECLAIM 0x2000000u
-#define __GFP_RECLAIM (__GFP_DIRECT_RECLAIM|__GFP_KSWAPD_RECLAIM)
+#define __GFP_RECLAIM (__GFP_DIRECT_RECLAIM|__GFP_KSWAPD_RECLAIM)
+
+#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
+#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
+#define GFP_NOWAIT (__GFP_KSWAPD_RECLAIM)
-#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
-#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
static inline bool gfpflags_allow_blocking(const gfp_t gfp_flags)
{
diff --git a/tools/testing/radix-tree/linux/idr.h b/tools/testing/radix-tree/linux/idr.h
new file mode 100644
index 0000000..4e342f2
--- /dev/null
+++ b/tools/testing/radix-tree/linux/idr.h
@@ -0,0 +1 @@
+#include "../../../../include/linux/idr.h"
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index dd1d9ae..63fce55 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -20,6 +20,7 @@
#define printk printf
#define pr_debug printk
+#define pr_cont printk
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index f7e9801..ddd90a1 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",
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 056a23b..b30e11d 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -34,6 +34,8 @@ void tag_check(void);
void multiorder_checks(void);
void iteration_test(unsigned order, unsigned duration);
void benchmark(void);
+void idr_checks(void);
+void ida_checks(void);
struct item *
item_tag_set(struct radix_tree_root *root, unsigned long index, int tag);