idr: Fix idr_get_next race with idr_remove

[mirror_ubuntu-bionic-kernel.git] / tools / testing / radix-tree / idr-test.c

diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 8e61aad0ca3f7ff65ca7ef640d6f9c9c0e7b75a9..07cec1b5a0d86a0219252f07fa123530364bea38 100644 (file)
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -177,6 +177,57 @@ void idr_get_next_test(void)
        idr_destroy(&idr);
 }
 
+static inline void *idr_mk_value(unsigned long v)
+{
+       BUG_ON((long)v < 0);
+       return (void *)((v & 1) | 2 | (v << 1));
+}
+
+DEFINE_IDR(find_idr);
+
+static void *idr_throbber(void *arg)
+{
+       time_t start = time(NULL);
+       int id = *(int *)arg;
+
+       rcu_register_thread();
+       do {
+               idr_alloc(&find_idr, idr_mk_value(id), id, id + 1, GFP_KERNEL);
+               idr_remove(&find_idr, id);
+       } while (time(NULL) < start + 10);
+       rcu_unregister_thread();
+
+       return NULL;
+}
+
+void idr_find_test_1(int anchor_id, int throbber_id)
+{
+       pthread_t throbber;
+       time_t start = time(NULL);
+
+       pthread_create(&throbber, NULL, idr_throbber, &throbber_id);
+
+       BUG_ON(idr_alloc(&find_idr, idr_mk_value(anchor_id), anchor_id,
+                               anchor_id + 1, GFP_KERNEL) != anchor_id);
+
+       do {
+               int id = 0;
+               void *entry = idr_get_next(&find_idr, &id);
+               BUG_ON(entry != idr_mk_value(id));
+       } while (time(NULL) < start + 11);
+
+       pthread_join(throbber, NULL);
+
+       idr_remove(&find_idr, anchor_id);
+       BUG_ON(!idr_is_empty(&find_idr));
+}
+
+void idr_find_test(void)
+{
+       idr_find_test_1(100000, 0);
+       idr_find_test_1(0, 100000);
+}
+
 void idr_checks(void)
 {
        unsigned long i;
@@ -234,6 +285,7 @@ void idr_checks(void)
        idr_null_test();
        idr_nowait_test();
        idr_get_next_test();
+       idr_find_test();
 }
 
 /*