Merge branch 'idr-2018-02-06' of git://git.infradead.org/users/willy/linux-dax

Pull idr updates from Matthew Wilcox:

 - test-suite improvements

 - replace the extended API by improving the normal API

 - performance improvement for IDRs which are 1-based rather than
   0-based

 - add documentation

* 'idr-2018-02-06' of git://git.infradead.org/users/willy/linux-dax:
  idr: Add documentation
  idr: Make 1-based IDRs more efficient
  idr: Warn if old iterators see large IDs
  idr: Rename idr_for_each_entry_ext
  idr: Remove idr_alloc_ext
  cls_u32: Convert to idr_alloc_u32
  cls_u32: Reinstate cyclic allocation
  cls_flower: Convert to idr_alloc_u32
  cls_bpf: Convert to use idr_alloc_u32
  cls_basic: Convert to use idr_alloc_u32
  cls_api: Convert to idr_alloc_u32
  net sched actions: Convert to use idr_alloc_u32
  idr: Add idr_alloc_u32 helper
  idr: Delete idr_find_ext function
  idr: Delete idr_replace_ext function
  idr: Delete idr_remove_ext function
  IDR test suite: Check handling negative end correctly
  idr test suite: Fix ida_test_random()
  radix tree test suite: Remove ARRAY_SIZE

2 files changed, 25 insertions, 6 deletions

diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 30cd0b296f1a..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};
 
@@ -207,6 +208,7 @@ void idr_checks(void)
 		assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
 	}
 	assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC);
+	assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i + 10, GFP_KERNEL) == -ENOSPC);
 
 	idr_for_each(&idr, item_idr_free, &idr);
 	idr_destroy(&idr);
@@ -214,6 +216,23 @@ void idr_checks(void)
 
 	assert(idr_is_empty(&idr));
 
+	idr_set_cursor(&idr, INT_MAX - 3UL);
+	for (i = INT_MAX - 3UL; i < INT_MAX + 3UL; i++) {
+		struct item *item;
+		unsigned int id;
+		if (i <= INT_MAX)
+			item = item_create(i, 0);
+		else
+			item = item_create(i - INT_MAX - 1, 0);
+
+		id = idr_alloc_cyclic(&idr, item, 0, 0, GFP_KERNEL);
+		assert(id == item->index);
+	}
+
+	idr_for_each(&idr, item_idr_free, &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);
@@ -226,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);
 }
 
 /*
@@ -380,7 +401,7 @@ void ida_check_random(void)
 			do {
 				ida_pre_get(&ida, GFP_KERNEL);
 				err = ida_get_new_above(&ida, bit, &id);
-			} while (err == -ENOMEM);
+			} while (err == -EAGAIN);
 			assert(!err);
 			assert(id == bit);
 		}
@@ -489,7 +510,7 @@ static void *ida_random_fn(void *arg)
 
 void ida_thread_tests(void)
 {
-	pthread_t threads[10];
+	pthread_t threads[20];
 	int i;
 
 	for (i = 0; i < ARRAY_SIZE(threads); i++)
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index c3bc3f364f68..426f32f28547 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -17,6 +17,4 @@
 #define pr_debug printk
 #define pr_cont printk
 
-#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
-
 #endif /* _KERNEL_H */