radix tree test harness

This code is mostly from Andrew Morton and Nick Piggin; tarball downloaded
from http://ozlabs.org/~akpm/rtth.tar.gz with sha1sum
0ce679db9ec047296b5d1ff7a1dfaa03a7bef1bd

Some small modifications were necessary to the test harness to fix the
build with the current Linux source code.

I also made minor modifications to automatically test the radix-tree.c
and radix-tree.h files that are in the current source tree, as opposed
to a copied and slightly modified version.  I am sure more could be done
to tidy up the harness, as well as adding more tests.

[koct9i@gmail.com: fix compilation]
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Cc: Shuah Khan <shuahkh@osg.samsung.com>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: Matthew Wilcox <willy@linux.intel.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Konstantin Khlebnikov <koct9i@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 220 insertions, 0 deletions

diff --git a/tools/testing/radix-tree/regression1.c b/tools/testing/radix-tree/regression1.c
new file mode 100644
index 000000000000..2d03a63bb79c
--- /dev/null
+++ b/tools/testing/radix-tree/regression1.c
@@ -0,0 +1,220 @@
+/*
+ * Regression1
+ * Description:
+ * Salman Qazi describes the following radix-tree bug:
+ *
+ * In the following case, we get can get a deadlock:
+ *
+ * 0.  The radix tree contains two items, one has the index 0.
+ * 1.  The reader (in this case find_get_pages) takes the rcu_read_lock.
+ * 2.  The reader acquires slot(s) for item(s) including the index 0 item.
+ * 3.  The non-zero index item is deleted, and as a consequence the other item
+ *     is moved to the root of the tree. The place where it used to be is queued
+ *     for deletion after the readers finish.
+ * 3b. The zero item is deleted, removing it from the direct slot, it remains in
+ *     the rcu-delayed indirect node.
+ * 4.  The reader looks at the index 0 slot, and finds that the page has 0 ref
+ *     count
+ * 5.  The reader looks at it again, hoping that the item will either be freed
+ *     or the ref count will increase. This never happens, as the slot it is
+ *     looking at will never be updated. Also, this slot can never be reclaimed
+ *     because the reader is holding rcu_read_lock and is in an infinite loop.
+ *
+ * The fix is to re-use the same "indirect" pointer case that requires a slot
+ * lookup retry into a general "retry the lookup" bit.
+ *
+ * Running:
+ * This test should run to completion in a few seconds. The above bug would
+ * cause it to hang indefinitely.
+ *
+ * Upstream commit:
+ * Not yet
+ */
+#include <linux/kernel.h>
+#include <linux/gfp.h>
+#include <linux/slab.h>
+#include <linux/radix-tree.h>
+#include <linux/rcupdate.h>
+#include <stdlib.h>
+#include <pthread.h>
+#include <stdio.h>
+#include <assert.h>
+
+#include "regression.h"
+
+static RADIX_TREE(mt_tree, GFP_KERNEL);
+static pthread_mutex_t mt_lock;
+
+struct page {
+        pthread_mutex_t lock;
+        struct rcu_head rcu;
+        int count;
+        unsigned long index;
+};
+
+static struct page *page_alloc(void)
+{
+        struct page *p;
+        p = malloc(sizeof(struct page));
+        p->count = 1;
+        p->index = 1;
+        pthread_mutex_init(&p->lock, NULL);
+
+        return p;
+}
+
+static void page_rcu_free(struct rcu_head *rcu)
+{
+        struct page *p = container_of(rcu, struct page, rcu);
+        assert(!p->count);
+        pthread_mutex_destroy(&p->lock);
+        free(p);
+}
+
+static void page_free(struct page *p)
+{
+        call_rcu(&p->rcu, page_rcu_free);
+}
+
+static unsigned find_get_pages(unsigned long start,
+                            unsigned int nr_pages, struct page **pages)
+{
+        unsigned int i;
+        unsigned int ret;
+        unsigned int nr_found;
+
+        rcu_read_lock();
+restart:
+        nr_found = radix_tree_gang_lookup_slot(&mt_tree,
+                                (void ***)pages, NULL, start, nr_pages);
+        ret = 0;
+        for (i = 0; i < nr_found; i++) {
+                struct page *page;
+repeat:
+                page = radix_tree_deref_slot((void **)pages[i]);
+                if (unlikely(!page))
+                        continue;
+
+                if (radix_tree_exception(page)) {
+                        if (radix_tree_deref_retry(page)) {
+                                /*
+                                 * Transient condition which can only trigger
+                                 * when entry at index 0 moves out of or back
+                                 * to root: none yet gotten, safe to restart.
+                                 */
+                                assert((start | i) == 0);
+                                goto restart;
+                        }
+                        /*
+                         * No exceptional entries are inserted in this test.
+                         */
+                        assert(0);
+                }
+
+                pthread_mutex_lock(&page->lock);
+                if (!page->count) {
+                        pthread_mutex_unlock(&page->lock);
+                        goto repeat;
+                }
+                /* don't actually update page refcount */
+                pthread_mutex_unlock(&page->lock);
+
+                /* Has the page moved? */
+                if (unlikely(page != *((void **)pages[i]))) {
+                        goto repeat;
+                }
+
+                pages[ret] = page;
+                ret++;
+        }
+        rcu_read_unlock();
+        return ret;
+}
+
+static pthread_barrier_t worker_barrier;
+
+static void *regression1_fn(void *arg)
+{
+        rcu_register_thread();
+
+        if (pthread_barrier_wait(&worker_barrier) ==
+                        PTHREAD_BARRIER_SERIAL_THREAD) {
+                int j;
+
+                for (j = 0; j < 1000000; j++) {
+                        struct page *p;
+
+                        p = page_alloc();
+                        pthread_mutex_lock(&mt_lock);
+                        radix_tree_insert(&mt_tree, 0, p);
+                        pthread_mutex_unlock(&mt_lock);
+
+                        p = page_alloc();
+                        pthread_mutex_lock(&mt_lock);
+                        radix_tree_insert(&mt_tree, 1, p);
+                        pthread_mutex_unlock(&mt_lock);
+
+                        pthread_mutex_lock(&mt_lock);
+                        p = radix_tree_delete(&mt_tree, 1);
+                        pthread_mutex_lock(&p->lock);
+                        p->count--;
+                        pthread_mutex_unlock(&p->lock);
+                        pthread_mutex_unlock(&mt_lock);
+                        page_free(p);
+
+                        pthread_mutex_lock(&mt_lock);
+                        p = radix_tree_delete(&mt_tree, 0);
+                        pthread_mutex_lock(&p->lock);
+                        p->count--;
+                        pthread_mutex_unlock(&p->lock);
+                        pthread_mutex_unlock(&mt_lock);
+                        page_free(p);
+                }
+        } else {
+                int j;
+
+                for (j = 0; j < 100000000; j++) {
+                        struct page *pages[10];
+
+                        find_get_pages(0, 10, pages);
+                }
+        }
+
+        rcu_unregister_thread();
+
+        return NULL;
+}
+
+static pthread_t *threads;
+void regression1_test(void)
+{
+        int nr_threads;
+        int i;
+        long arg;
+
+        /* Regression #1 */
+        printf("running regression test 1, should finish in under a minute\n");
+        nr_threads = 2;
+        pthread_barrier_init(&worker_barrier, NULL, nr_threads);
+
+        threads = malloc(nr_threads * sizeof(pthread_t *));
+
+        for (i = 0; i < nr_threads; i++) {
+                arg = i;
+                if (pthread_create(&threads[i], NULL, regression1_fn, (void *)arg)) {
+                        perror("pthread_create");
+                        exit(1);
+                }
+        }
+
+        for (i = 0; i < nr_threads; i++) {
+                if (pthread_join(threads[i], NULL)) {
+                        perror("pthread_join");
+                        exit(1);
+                }
+        }
+
+        free(threads);
+
+        printf("regression test 1, done\n");
+}