kern/rcu: new module

This module implements preemptible RCU.

3 files changed, 235 insertions, 0 deletions

diff --git a/test/Kconfig b/test/Kconfig
index 8f3ae8ba..6a6221bb 100644
--- a/test/Kconfig
+++ b/test/Kconfig
@@ -22,6 +22,9 @@ config TEST_MODULE_MUTEX_PI
 config TEST_MODULE_PMAP_UPDATE_MP
 	bool "pmap_update_mp"
 
+config TEST_MODULE_RCU_DEFER
+	bool "rcu_defer"
+
 config TEST_MODULE_SREF_DIRTY_ZEROES
 	bool "sref_dirty_zeroes"
 
diff --git a/test/Makefile b/test/Makefile
index 098cecbd..b7ac3d7f 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -2,6 +2,7 @@ x15_SOURCES-$(CONFIG_TEST_MODULE_LLSYNC_DEFER)          += test/test_llsync_defe
 x15_SOURCES-$(CONFIG_TEST_MODULE_MUTEX)                 += test/test_mutex.c
 x15_SOURCES-$(CONFIG_TEST_MODULE_MUTEX_PI)              += test/test_mutex_pi.c
 x15_SOURCES-$(CONFIG_TEST_MODULE_PMAP_UPDATE_MP)        += test/test_pmap_update_mp.c
+x15_SOURCES-$(CONFIG_TEST_MODULE_RCU_DEFER)             += test/test_rcu_defer.c
 x15_SOURCES-$(CONFIG_TEST_MODULE_SREF_DIRTY_ZEROES)     += test/test_sref_dirty_zeroes.c
 x15_SOURCES-$(CONFIG_TEST_MODULE_SREF_NOREF)            += test/test_sref_noref.c
 x15_SOURCES-$(CONFIG_TEST_MODULE_SREF_WEAKREF)          += test/test_sref_weakref.c
diff --git a/test/test_rcu_defer.c b/test/test_rcu_defer.c
new file mode 100644
index 00000000..e1ab0e51
--- /dev/null
+++ b/test/test_rcu_defer.c
@@ -0,0 +1,231 @@
+/*
+ * Copyright (c) 2014-2018 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that 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.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * This test module is a stress test, expected to never terminate, of the
+ * work deferring functionality of the rcu module. It creates three
+ * threads, a producer, a consumer, and a reader. The producer allocates
+ * a page and writes it. It then transfers the page to the consumer, using
+ * the rcu interface to update the global page pointer. Once at the
+ * consumer, the rcu interface is used to defer the release of the page.
+ * Concurrently, the reader accesses the page and checks its content when
+ * available. These accesses are performed inside a read-side critical
+ * section and should therefore never fail.
+ *
+ * Each thread regularly prints a string to report that it's making progress.
+ */
+
+#include <stddef.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <kern/condition.h>
+#include <kern/cpumap.h>
+#include <kern/error.h>
+#include <kern/kmem.h>
+#include <kern/macros.h>
+#include <kern/mutex.h>
+#include <kern/panic.h>
+#include <kern/rcu.h>
+#include <kern/thread.h>
+#include <kern/work.h>
+#include <machine/page.h>
+#include <test/test.h>
+#include <vm/vm_kmem.h>
+
+#define TEST_LOOPS_PER_PRINT 100000
+
+struct test_pdsc {
+    struct work work;
+    void *addr;
+};
+
+#define TEST_VALIDATION_BYTE 0xab
+
+static struct mutex test_lock;
+static struct condition test_condition;
+static struct test_pdsc *test_pdsc;
+
+static struct kmem_cache test_pdsc_cache;
+
+static void
+test_alloc(void *arg)
+{
+    struct test_pdsc *pdsc;
+    unsigned long nr_loops;
+
+    (void)arg;
+
+    nr_loops = 0;
+
+    mutex_lock(&test_lock);
+
+    for (;;) {
+        while (test_pdsc != NULL) {
+            condition_wait(&test_condition, &test_lock);
+        }
+
+        pdsc = kmem_cache_alloc(&test_pdsc_cache);
+
+        if (pdsc != NULL) {
+            pdsc->addr = vm_kmem_alloc(PAGE_SIZE);
+
+            if (pdsc->addr != NULL) {
+                memset(pdsc->addr, TEST_VALIDATION_BYTE, PAGE_SIZE);
+            }
+        }
+
+        rcu_store_ptr(test_pdsc, pdsc);
+        condition_signal(&test_condition);
+
+        if ((nr_loops % TEST_LOOPS_PER_PRINT) == 0) {
+            printf("alloc ");
+        }
+
+        nr_loops++;
+    }
+}
+
+static void
+test_deferred_free(struct work *work)
+{
+    struct test_pdsc *pdsc;
+
+    pdsc = structof(work, struct test_pdsc, work);
+
+    if (pdsc->addr != NULL) {
+        vm_kmem_free(pdsc->addr, PAGE_SIZE);
+    }
+
+    kmem_cache_free(&test_pdsc_cache, pdsc);
+}
+
+static void
+test_free(void *arg)
+{
+    struct test_pdsc *pdsc;
+    unsigned long nr_loops;
+
+    (void)arg;
+
+    nr_loops = 0;
+
+    mutex_lock(&test_lock);
+
+    for (;;) {
+        while (test_pdsc == NULL) {
+            condition_wait(&test_condition, &test_lock);
+        }
+
+        pdsc = test_pdsc;
+        rcu_store_ptr(test_pdsc, NULL);
+
+        if (pdsc != NULL) {
+            work_init(&pdsc->work, test_deferred_free);
+            rcu_defer(&pdsc->work);
+        }
+
+        condition_signal(&test_condition);
+
+        if ((nr_loops % TEST_LOOPS_PER_PRINT) == 0) {
+            printf("free ");
+        }
+
+        nr_loops++;
+    }
+}
+
+static void
+test_read(void *arg)
+{
+    const struct test_pdsc *pdsc;
+    const unsigned char *s;
+    unsigned long nr_loops;
+
+    (void)arg;
+
+    nr_loops = 0;
+
+    for (;;) {
+        rcu_read_enter();
+
+        pdsc = rcu_load_ptr(test_pdsc);
+
+        if (pdsc != NULL) {
+            s = (const unsigned char *)pdsc->addr;
+
+            if (s != NULL) {
+                for (unsigned int i = 0; i < PAGE_SIZE; i++) {
+                    if (s[i] != TEST_VALIDATION_BYTE) {
+                        panic("invalid content");
+                    }
+                }
+
+                if ((nr_loops % TEST_LOOPS_PER_PRINT) == 0) {
+                    printf("read ");
+                }
+
+                nr_loops++;
+            }
+        }
+
+        rcu_read_leave();
+    }
+}
+
+void
+test_setup(void)
+{
+    struct thread_attr attr;
+    struct thread *thread;
+    struct cpumap *cpumap;
+    int error;
+
+    condition_init(&test_condition);
+    mutex_init(&test_lock);
+
+    error = cpumap_create(&cpumap);
+    error_check(error, "cpumap_create");
+
+    kmem_cache_init(&test_pdsc_cache, "test_pdsc",
+                    sizeof(struct test_pdsc), 0, NULL, 0);
+
+    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_alloc");
+    thread_attr_set_detached(&attr);
+    cpumap_zero(cpumap);
+    cpumap_set(cpumap, cpu_count() - 1);
+    thread_attr_set_cpumap(&attr, cpumap);
+    error = thread_create(&thread, &attr, test_alloc, NULL);
+    error_check(error, "thread_create");
+
+    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_free");
+    thread_attr_set_detached(&attr);
+    cpumap_zero(cpumap);
+    cpumap_set(cpumap, cpu_count() - 1);
+    thread_attr_set_cpumap(&attr, cpumap);
+    error = thread_create(&thread, &attr, test_free, NULL);
+    error_check(error, "thread_create");
+
+    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_read");
+    thread_attr_set_detached(&attr);
+    cpumap_zero(cpumap);
+    cpumap_set(cpumap, 0);
+    thread_attr_set_cpumap(&attr, cpumap);
+    error = thread_create(&thread, &attr, test_read, NULL);
+    error_check(error, "thread_create");
+
+    cpumap_destroy(cpumap);
+}