From c9b933521aa5795f5b9b6f9809325d6b21710d78 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Tue, 21 Aug 2018 23:22:54 -0400
Subject: radix tree test suite: Fix compilation

An include of xarray.h was added to lib/idr.c without updating the test
suite.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 tools/testing/radix-tree/linux/xarray.h | 2 ++
 1 file changed, 2 insertions(+)
 create mode 100644 tools/testing/radix-tree/linux/xarray.h

(limited to 'tools')

diff --git a/tools/testing/radix-tree/linux/xarray.h b/tools/testing/radix-tree/linux/xarray.h
new file mode 100644
index 000000000000..df3812cda376
--- /dev/null
+++ b/tools/testing/radix-tree/linux/xarray.h
@@ -0,0 +1,2 @@
+#include "generated/map-shift.h"
+#include "../../../../include/linux/xarray.h"
-- 
cgit v1.2.3


From d1c0d5e3c63d61226a75f24d5c35fe20755f0180 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Sat, 19 May 2018 16:30:54 -0400
Subject: radix tree test suite: Enable ubsan

Add support for the undefined behaviour sanitizer and fix the bugs
that ubsan pointed out.  Nothing major, and all in the test suite,
not the code.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 tools/testing/radix-tree/Makefile |  5 +++--
 tools/testing/radix-tree/main.c   | 20 +++++++++++---------
 2 files changed, 14 insertions(+), 11 deletions(-)

(limited to 'tools')

diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index db66f8a0d4be..da030a65d6d6 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -1,7 +1,8 @@
 # SPDX-License-Identifier: GPL-2.0
 
-CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address
-LDFLAGS += -fsanitize=address
+CFLAGS += -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address \
+	  -fsanitize=undefined
+LDFLAGS += -fsanitize=address -fsanitize=undefined
 LDLIBS+= -lpthread -lurcu
 TARGETS = main idr-test multiorder
 CORE_OFILES := radix-tree.o idr.o linux.o test.o find_bit.o
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 257f3f8aacaa..584a8732f5ce 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -27,20 +27,22 @@ void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
 		item_check_present(&tree, middle + idx);
 	item_check_absent(&tree, middle + up);
 
-	item_gang_check_present(&tree, middle - down,
-			up + down, chunk, hop);
-	item_full_scan(&tree, middle - down, down + up, chunk);
+	if (chunk > 0) {
+		item_gang_check_present(&tree, middle - down, up + down,
+				chunk, hop);
+		item_full_scan(&tree, middle - down, down + up, chunk);
+	}
 	item_kill_tree(&tree);
 }
 
 void gang_check(void)
 {
-	__gang_check(1 << 30, 128, 128, 35, 2);
-	__gang_check(1 << 31, 128, 128, 32, 32);
-	__gang_check(1 << 31, 128, 128, 32, 100);
-	__gang_check(1 << 31, 128, 128, 17, 7);
-	__gang_check(0xffff0000, 0, 65536, 17, 7);
-	__gang_check(0xfffffffe, 1, 1, 17, 7);
+	__gang_check(1UL << 30, 128, 128, 35, 2);
+	__gang_check(1UL << 31, 128, 128, 32, 32);
+	__gang_check(1UL << 31, 128, 128, 32, 100);
+	__gang_check(1UL << 31, 128, 128, 17, 7);
+	__gang_check(0xffff0000UL, 0, 65536, 17, 7);
+	__gang_check(0xfffffffeUL, 1, 1, 17, 7);
 }
 
 void __big_gang_check(void)
-- 
cgit v1.2.3


From 8ab8ba38d48867aac01812e18f48fc9173ccd400 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 18 Jun 2018 16:59:29 -0400
Subject: ida: Start new test_ida module

Start transitioning the IDA tests into kernel space.  Framework heavily
cribbed from test_xarray.c.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 lib/Kconfig.debug                   |  3 +++
 lib/Makefile                        |  1 +
 lib/test_ida.c                      | 45 +++++++++++++++++++++++++++++++++++++
 tools/testing/radix-tree/Makefile   |  1 +
 tools/testing/radix-tree/idr-test.c | 22 +++++++++++++++---
 tools/testing/radix-tree/main.c     |  3 +--
 tools/testing/radix-tree/test.h     |  3 +--
 7 files changed, 71 insertions(+), 7 deletions(-)
 create mode 100644 lib/test_ida.c

(limited to 'tools')

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 8838d1158d19..2fff661d9070 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1827,6 +1827,9 @@ config TEST_HASH
 	  This is intended to help people writing architecture-specific
 	  optimized versions.  If unsure, say N.
 
+config TEST_IDA
+	tristate "Perform selftest on IDA functions"
+
 config TEST_PARMAN
 	tristate "Perform selftest on priority array manager"
 	default n
diff --git a/lib/Makefile b/lib/Makefile
index 90dc5520b784..18d87ca4c949 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -50,6 +50,7 @@ obj-$(CONFIG_TEST_BPF) += test_bpf.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
 obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o
 obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
+obj-$(CONFIG_TEST_IDA) += test_ida.o
 obj-$(CONFIG_TEST_KASAN) += test_kasan.o
 CFLAGS_test_kasan.o += -fno-builtin
 obj-$(CONFIG_TEST_UBSAN) += test_ubsan.o
diff --git a/lib/test_ida.c b/lib/test_ida.c
new file mode 100644
index 000000000000..8c9a0672696b
--- /dev/null
+++ b/lib/test_ida.c
@@ -0,0 +1,45 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * test_ida.c: Test the IDA API
+ * Copyright (c) 2016-2018 Microsoft Corporation
+ * Copyright (c) 2018 Oracle Corporation
+ * Author: Matthew Wilcox <willy@infradead.org>
+ */
+
+#include <linux/idr.h>
+#include <linux/module.h>
+
+static unsigned int tests_run;
+static unsigned int tests_passed;
+
+#ifdef __KERNEL__
+void ida_dump(struct ida *ida) { }
+#endif
+#define IDA_BUG_ON(ida, x) do {						\
+	tests_run++;							\
+	if (x) {							\
+		ida_dump(ida);						\
+		dump_stack();						\
+	} else {							\
+		tests_passed++;						\
+	}								\
+} while (0)
+
+static int ida_checks(void)
+{
+	DEFINE_IDA(ida);
+
+	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
+
+	printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
+	return (tests_run != tests_passed) ? 0 : -EINVAL;
+}
+
+static void ida_exit(void)
+{
+}
+
+module_init(ida_checks);
+module_exit(ida_exit);
+MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
+MODULE_LICENSE("GPL");
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index da030a65d6d6..37baecc3766f 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -22,6 +22,7 @@ targets: generated/map-shift.h $(TARGETS)
 
 main:	$(OFILES)
 
+idr-test.o: ../../../lib/test_ida.c
 idr-test: idr-test.o $(CORE_OFILES)
 
 multiorder: multiorder.o $(CORE_OFILES)
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index ee820fcc29b0..604b51dc9b38 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -309,6 +309,15 @@ void idr_checks(void)
 	idr_u32_test(0);
 }
 
+#define module_init(x)
+#define module_exit(x)
+#define MODULE_AUTHOR(x)
+#define MODULE_LICENSE(x)
+#define dump_stack()    assert(0)
+void ida_dump(struct ida *);
+
+#include "../../../lib/test_ida.c"
+
 /*
  * 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.
@@ -488,7 +497,7 @@ void ida_simple_get_remove_test(void)
 	ida_destroy(&ida);
 }
 
-void ida_checks(void)
+void user_ida_checks(void)
 {
 	DEFINE_IDA(ida);
 	int id;
@@ -582,12 +591,19 @@ void ida_thread_tests(void)
 		pthread_join(threads[i], NULL);
 }
 
+void ida_tests(void)
+{
+	user_ida_checks();
+	ida_checks();
+	ida_exit();
+	ida_thread_tests();
+}
+
 int __weak main(void)
 {
 	radix_tree_init();
 	idr_checks();
-	ida_checks();
-	ida_thread_tests();
+	ida_tests();
 	radix_tree_cpu_dead(1);
 	rcu_barrier();
 	if (nr_allocated)
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 584a8732f5ce..b741686e53d6 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -324,7 +324,7 @@ static void single_thread_tests(bool long_run)
 	printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
 		nr_allocated, preempt_count);
 	idr_checks();
-	ida_checks();
+	ida_tests();
 	rcu_barrier();
 	printv(2, "after idr_checks: %d allocated, preempt %d\n",
 		nr_allocated, preempt_count);
@@ -371,7 +371,6 @@ int main(int argc, char **argv)
 	iteration_test(0, 10 + 90 * long_run);
 	iteration_test(7, 10 + 90 * long_run);
 	single_thread_tests(long_run);
-	ida_thread_tests();
 
 	/* Free any remaining preallocated nodes */
 	radix_tree_cpu_dead(0);
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 31f1d9b6f506..92d901eacf49 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -39,8 +39,7 @@ void multiorder_checks(void);
 void iteration_test(unsigned order, unsigned duration);
 void benchmark(void);
 void idr_checks(void);
-void ida_checks(void);
-void ida_thread_tests(void);
+void ida_tests(void);
 
 struct item *
 item_tag_set(struct radix_tree_root *root, unsigned long index, int tag);
-- 
cgit v1.2.3


From 06b01113664feda7647962008e901fa540ecbf6f Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 18 Jun 2018 17:06:58 -0400
Subject: idr-test: Convert ida_check_nomem to new API

We can't move this test to kernel space because there's no way to
force kmalloc to fail.  But we can use the new API and check this
works when the test is in userspace.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 tools/testing/radix-tree/idr-test.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

(limited to 'tools')

diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 604b51dc9b38..0f557784327d 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -320,19 +320,20 @@ void ida_dump(struct ida *);
 
 /*
  * 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.
+ * allocations.  In userspace, GFP_NOWAIT will always fail an allocation.
  * 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;
+	int id;
 
-	err = ida_get_new_above(&ida, 256, &id);
-	assert(err == -EAGAIN);
-	err = ida_get_new_above(&ida, 1UL << 30, &id);
-	assert(err == -EAGAIN);
+	id = ida_alloc_min(&ida, 256, GFP_NOWAIT);
+	IDA_BUG_ON(&ida, id != -ENOMEM);
+	id = ida_alloc_min(&ida, 1UL << 30, GFP_NOWAIT);
+	IDA_BUG_ON(&ida, id != -ENOMEM);
+	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
 }
 
 /*
-- 
cgit v1.2.3


From 0a3856392cff1542170b5bc37211c9a21fd0c3f6 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 18 Jun 2018 17:23:37 -0400
Subject: test_ida: Move ida_check_leaf

Convert to new API and move to kernel space.  Take the opportunity to
test the situation a little more thoroughly (ie at different offsets).

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 lib/test_ida.c                      | 25 +++++++++++++++++++++++++
 tools/testing/radix-tree/idr-test.c | 27 ---------------------------
 2 files changed, 25 insertions(+), 27 deletions(-)

(limited to 'tools')

diff --git a/lib/test_ida.c b/lib/test_ida.c
index 8c9a0672696b..1988f91a20c8 100644
--- a/lib/test_ida.c
+++ b/lib/test_ida.c
@@ -25,11 +25,36 @@ void ida_dump(struct ida *ida) { }
 	}								\
 } while (0)
 
+/*
+ * Check what happens when we fill a leaf and then delete it.  This may
+ * discover mishandling of IDR_FREE.
+ */
+static void ida_check_leaf(struct ida *ida, unsigned int base)
+{
+	unsigned long i;
+
+	for (i = 0; i < IDA_BITMAP_BITS; i++) {
+		IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
+				base + i);
+	}
+
+	ida_destroy(ida);
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+
+	IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
+	IDA_BUG_ON(ida, ida_is_empty(ida));
+	ida_free(ida, 0);
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+}
+
 static int ida_checks(void)
 {
 	DEFINE_IDA(ida);
 
 	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
+	ida_check_leaf(&ida, 0);
+	ida_check_leaf(&ida, 1024);
+	ida_check_leaf(&ida, 1024 * 64);
 
 	printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
 	return (tests_run != tests_passed) ? 0 : -EINVAL;
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 0f557784327d..fef1f45b927b 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -336,32 +336,6 @@ void ida_check_nomem(void)
 	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
 }
 
-/*
- * 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 handling of conversions between exceptional entries and full bitmaps.
  */
@@ -560,7 +534,6 @@ void user_ida_checks(void)
 	ida_destroy(&ida);
 	assert(ida_is_empty(&ida));
 
-	ida_check_leaf();
 	ida_check_max();
 	ida_check_conv();
 	ida_check_random();
-- 
cgit v1.2.3


From 161b47e31f9912947a3a72dcb161c79978a1fe04 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 18 Jun 2018 17:25:20 -0400
Subject: test_ida: Move ida_check_max

Convert to new API and move to kernel space.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 lib/test_ida.c                      | 23 +++++++++++++++++++++++
 tools/testing/radix-tree/idr-test.c | 28 ----------------------------
 2 files changed, 23 insertions(+), 28 deletions(-)

(limited to 'tools')

diff --git a/lib/test_ida.c b/lib/test_ida.c
index 1988f91a20c8..44174ec9f5bf 100644
--- a/lib/test_ida.c
+++ b/lib/test_ida.c
@@ -47,6 +47,28 @@ static void ida_check_leaf(struct ida *ida, unsigned int base)
 	IDA_BUG_ON(ida, !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.
+ */
+static void ida_check_max(struct ida *ida)
+{
+	unsigned long i, j;
+
+	for (j = 1; j < 65537; j *= 2) {
+		unsigned long base = (1UL << 31) - j;
+		for (i = 0; i < j; i++) {
+			IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
+					base + i);
+		}
+		IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
+				-ENOSPC);
+		ida_destroy(ida);
+		IDA_BUG_ON(ida, !ida_is_empty(ida));
+	}
+}
+
 static int ida_checks(void)
 {
 	DEFINE_IDA(ida);
@@ -55,6 +77,7 @@ static int ida_checks(void)
 	ida_check_leaf(&ida, 0);
 	ida_check_leaf(&ida, 1024);
 	ida_check_leaf(&ida, 1024 * 64);
+	ida_check_max(&ida);
 
 	printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
 	return (tests_run != tests_passed) ? 0 : -EINVAL;
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index fef1f45b927b..bd9699327f95 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -396,33 +396,6 @@ void ida_check_conv(void)
 	ida_destroy(&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_check_random(void)
 {
 	DEFINE_IDA(ida);
@@ -534,7 +507,6 @@ void user_ida_checks(void)
 	ida_destroy(&ida);
 	assert(ida_is_empty(&ida));
 
-	ida_check_max();
 	ida_check_conv();
 	ida_check_random();
 	ida_simple_get_remove_test();
-- 
cgit v1.2.3


From 5c78b0b1ebe16fbae39a1cada79ab067965828f5 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 18 Jun 2018 18:10:32 -0400
Subject: test_ida: Convert check_ida_conv to new API

Move as much as possible to kernel space; leave the parts in user space
that rely on checking memory allocation failures to detect the
transition between an exceptional entry and a bitmap.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 lib/test_ida.c                      | 30 ++++++++++++++++++++
 tools/testing/radix-tree/idr-test.c | 56 +++++++------------------------------
 2 files changed, 40 insertions(+), 46 deletions(-)

(limited to 'tools')

diff --git a/lib/test_ida.c b/lib/test_ida.c
index 44174ec9f5bf..eaee9a28f325 100644
--- a/lib/test_ida.c
+++ b/lib/test_ida.c
@@ -69,6 +69,35 @@ static void ida_check_max(struct ida *ida)
 	}
 }
 
+/*
+ * Check handling of conversions between exceptional entries and full bitmaps.
+ */
+static void ida_check_conv(struct ida *ida)
+{
+	unsigned long i;
+
+	for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
+		IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
+		IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
+					GFP_KERNEL) != i + BITS_PER_LONG);
+		ida_free(ida, i + 1);
+		ida_free(ida, i + BITS_PER_LONG);
+		IDA_BUG_ON(ida, !ida_is_empty(ida));
+	}
+
+	for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
+		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
+	for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
+		ida_free(ida, i - 1);
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+
+	for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
+		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
+	for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
+		ida_free(ida, i - 1);
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+}
+
 static int ida_checks(void)
 {
 	DEFINE_IDA(ida);
@@ -78,6 +107,7 @@ static int ida_checks(void)
 	ida_check_leaf(&ida, 1024);
 	ida_check_leaf(&ida, 1024 * 64);
 	ida_check_max(&ida);
+	ida_check_conv(&ida);
 
 	printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
 	return (tests_run != tests_passed) ? 0 : -EINVAL;
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index bd9699327f95..c6026cfe3145 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -339,59 +339,23 @@ void ida_check_nomem(void)
 /*
  * Check handling of conversions between exceptional entries and full bitmaps.
  */
-void ida_check_conv(void)
+void ida_check_conv_user(void)
 {
 	DEFINE_IDA(ida);
-	int id;
 	unsigned long i;
 
-	for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
-		assert(ida_pre_get(&ida, GFP_KERNEL));
-		assert(!ida_get_new_above(&ida, i + 1, &id));
-		assert(id == i + 1);
-		assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id));
-		assert(id == i + BITS_PER_LONG);
-		ida_remove(&ida, i + 1);
-		ida_remove(&ida, i + BITS_PER_LONG);
-		assert(ida_is_empty(&ida));
-	}
-
-	assert(ida_pre_get(&ida, GFP_KERNEL));
-
-	for (i = 0; i < IDA_BITMAP_BITS * 2; i++) {
-		assert(ida_pre_get(&ida, GFP_KERNEL));
-		assert(!ida_get_new(&ida, &id));
-		assert(id == i);
-	}
-
-	for (i = IDA_BITMAP_BITS * 2; i > 0; i--) {
-		ida_remove(&ida, i - 1);
-	}
-	assert(ida_is_empty(&ida));
-
-	for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) {
-		assert(ida_pre_get(&ida, GFP_KERNEL));
-		assert(!ida_get_new(&ida, &id));
-		assert(id == i);
-	}
-
-	for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) {
-		ida_remove(&ida, i - 1);
-	}
-	assert(ida_is_empty(&ida));
-
 	radix_tree_cpu_dead(1);
 	for (i = 0; i < 1000000; i++) {
-		int err = ida_get_new(&ida, &id);
-		if (err == -EAGAIN) {
-			assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2));
-			assert(ida_pre_get(&ida, GFP_KERNEL));
-			err = ida_get_new(&ida, &id);
+		int id = ida_alloc(&ida, GFP_NOWAIT);
+		if (id == -ENOMEM) {
+			IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) !=
+					BITS_PER_LONG - 2);
+			id = ida_alloc(&ida, GFP_KERNEL);
 		} else {
-			assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2));
+			IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) ==
+					BITS_PER_LONG - 2);
 		}
-		assert(!err);
-		assert(id == i);
+		IDA_BUG_ON(&ida, id != i);
 	}
 	ida_destroy(&ida);
 }
@@ -507,7 +471,7 @@ void user_ida_checks(void)
 	ida_destroy(&ida);
 	assert(ida_is_empty(&ida));
 
-	ida_check_conv();
+	ida_check_conv_user();
 	ida_check_random();
 	ida_simple_get_remove_test();
 
-- 
cgit v1.2.3


From f272668deb9108b6118a85ffd73886b9a92c1002 Mon Sep 17 00:00:00 2001
From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 18 Jun 2018 18:39:28 -0400
Subject: test_ida: check_ida_destroy and check_ida_alloc

Move these tests from the userspace test-suite to the kernel test-suite.
Also convert check_ida_random to the new API.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 lib/test_ida.c                      | 54 ++++++++++++++++++++++++++++
 tools/testing/radix-tree/idr-test.c | 70 +++----------------------------------
 2 files changed, 58 insertions(+), 66 deletions(-)

(limited to 'tools')

diff --git a/lib/test_ida.c b/lib/test_ida.c
index eaee9a28f325..2d1637d8136b 100644
--- a/lib/test_ida.c
+++ b/lib/test_ida.c
@@ -25,6 +25,58 @@ void ida_dump(struct ida *ida) { }
 	}								\
 } while (0)
 
+/*
+ * Straightforward checks that allocating and freeing IDs work.
+ */
+static void ida_check_alloc(struct ida *ida)
+{
+	int i, id;
+
+	for (i = 0; i < 10000; i++)
+		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
+
+	ida_free(ida, 20);
+	ida_free(ida, 21);
+	for (i = 0; i < 3; i++) {
+		id = ida_alloc(ida, GFP_KERNEL);
+		IDA_BUG_ON(ida, id < 0);
+		if (i == 2)
+			IDA_BUG_ON(ida, id != 10000);
+	}
+
+	for (i = 0; i < 5000; i++)
+		ida_free(ida, i);
+
+	IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
+	ida_destroy(ida);
+
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+}
+
+/* Destroy an IDA with a single entry at @base */
+static void ida_check_destroy_1(struct ida *ida, unsigned int base)
+{
+	IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
+	IDA_BUG_ON(ida, ida_is_empty(ida));
+	ida_destroy(ida);
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+}
+
+/* Check that ida_destroy and ida_is_empty work */
+static void ida_check_destroy(struct ida *ida)
+{
+	/* Destroy an already-empty IDA */
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+	ida_destroy(ida);
+	IDA_BUG_ON(ida, !ida_is_empty(ida));
+
+	ida_check_destroy_1(ida, 0);
+	ida_check_destroy_1(ida, 1);
+	ida_check_destroy_1(ida, 1023);
+	ida_check_destroy_1(ida, 1024);
+	ida_check_destroy_1(ida, 12345678);
+}
+
 /*
  * Check what happens when we fill a leaf and then delete it.  This may
  * discover mishandling of IDR_FREE.
@@ -103,6 +155,8 @@ static int ida_checks(void)
 	DEFINE_IDA(ida);
 
 	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
+	ida_check_alloc(&ida);
+	ida_check_destroy(&ida);
 	ida_check_leaf(&ida, 0);
 	ida_check_leaf(&ida, 1024);
 	ida_check_leaf(&ida, 1024 * 64);
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index c6026cfe3145..321ba92c70d2 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -364,7 +364,6 @@ void ida_check_random(void)
 {
 	DEFINE_IDA(ida);
 	DECLARE_BITMAP(bitmap, 2048);
-	int id, err;
 	unsigned int i;
 	time_t s = time(NULL);
 
@@ -375,15 +374,11 @@ void ida_check_random(void)
 		int bit = i & 2047;
 		if (test_bit(bit, bitmap)) {
 			__clear_bit(bit, bitmap);
-			ida_remove(&ida, bit);
+			ida_free(&ida, bit);
 		} else {
 			__set_bit(bit, bitmap);
-			do {
-				ida_pre_get(&ida, GFP_KERNEL);
-				err = ida_get_new_above(&ida, bit, &id);
-			} while (err == -EAGAIN);
-			assert(!err);
-			assert(id == bit);
+			IDA_BUG_ON(&ida, ida_alloc_min(&ida, bit, GFP_KERNEL)
+					!= bit);
 		}
 	}
 	ida_destroy(&ida);
@@ -411,66 +406,9 @@ void ida_simple_get_remove_test(void)
 
 void user_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_nomem();
 	ida_check_conv_user();
 	ida_check_random();
 	ida_simple_get_remove_test();
-- 
cgit v1.2.3