Changeset 29b8138 in mainline

Timestamp:

2012-11-23T19:58:34Z (11 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

a879d73

Parents:

a2f42e5

Message:

urcu: Added sanity tests.

File:

• uspace/app/rcutest/rcutest.c (modified) (2 diffs)

uspace/app/rcutest/rcutest.c

@@ -42 +42 @@
 #include <thread.h>
 #include <assert.h>
-
+#include <async.h>
 #include <fibril.h>
+#include <compiler/barrier.h>
 
 #include <rcu.h>
 
 
-static void invoke_rcu(void)
-{
-        rcu_read_lock();
+#define USECS_PER_SEC (1000 * 1000)
+#define USECS_PER_MS  1000
+
+
+typedef struct test_desc {
+        /* Aggregate test that runs other tests already in the table test_desc. */
+        bool aggregate;
+        enum {
+                T_OTHER,
+                T_SANITY,
+                T_STRESS
+        } type;
+        bool (*func)(void);
+        const char *name;
+        const char *desc;
+} test_desc_t;
+
+
+static bool run_all_tests(void);
+static bool run_sanity_tests(void);
+static bool run_stress_tests(void);
+
+static bool wait_for_one_reader(void);
+static bool basic_sanity_check(void);
+static bool dont_wait_for_new_reader(void);
+
+
+static test_desc_t test_desc[] = {
+        {
+                .aggregate = true,
+                .type = T_OTHER,
+                .func = run_all_tests,
+                .name = "*",
+                .desc = "Runs all tests.",
+        },
+        {
+                .aggregate = true,
+                .type = T_SANITY,
+                .func = run_sanity_tests,
+                .name = "sanity-tests",
+                .desc = "Runs all RCU sanity tests.",
+        },
+        {
+                .aggregate = true,
+                .type = T_STRESS,
+                .func = run_stress_tests,
+                .name = "stress-tests",
+                .desc = "Runs all RCU stress tests.",
+        },
+
+        {
+                .aggregate = false,
+                .type = T_SANITY,
+                .func = basic_sanity_check,
+                .name = "basic-sanity",
+                .desc = "Locks/unlocks and syncs in a single fibril, no contention.",
+        },
+        {
+                .aggregate = false,
+                .type = T_SANITY,
+                .func = wait_for_one_reader,
+                .name = "wait-for-one",
+                .desc = "Syncs with one 2 secs sleeping reader.",
+        },
+        {
+                .aggregate = false,
+                .type = T_SANITY,
+                .func = dont_wait_for_new_reader,
+                .name = "ignore-new-r",
+                .desc = "Syncs with preexisting reader but ignores new reader.",
+        },
+        {
+                .aggregate = false,
+                .type = T_OTHER,
+                .func = NULL,
+                .name = "(null)",
+                .desc = "",
+        },
+};
+
+static const size_t test_desc_cnt = sizeof(test_desc) / sizeof(test_desc[0]);
+
+/*--------------------------------------------------------------------*/
+
+typedef int (*fibril_func_t)(void *);
+
+static bool create_fibril(int (*func)(void*), void *arg)
+{
+        fid_t fid = fibril_create(func, arg);
+        
+        if (0 == fid) {
+                printf("Failed to create a fibril!\n");
+                return false;
+        }
+        
+        fibril_add_ready(fid);
+        return true;
+}
+
+/*--------------------------------------------------------------------*/
+
+static bool run_tests(bool (*include_filter)(test_desc_t *)) 
+{
+        size_t failed_cnt = 0;
+        size_t ok_cnt = 0;
+        
+        for (size_t i = 0; i < test_desc_cnt; ++i) {
+                test_desc_t *t = &test_desc[i];
+                
+                if (t->func && !t->aggregate && include_filter(t)) {
+                        printf("Running \'%s\'...\n", t->name);
+                        bool ok = test_desc[i].func();
+                        
+                        if (ok) {
+                                ++ok_cnt;
+                                printf("Passed: \'%s\'\n", t->name);
+                        } else {
+                                ++failed_cnt;
+                                printf("FAILED: \'%s\'\n", t->name);
+                        }
+                }
+        }
+        
+        printf("\n");
+
+        printf("%zu tests passed\n", ok_cnt);
+
+        if (failed_cnt) {
+                printf("%zu tests failed\n", failed_cnt);
+        } 
+        
+        return 0 == failed_cnt;
+}
+
+/*--------------------------------------------------------------------*/
+
+static bool all_tests_include_filter(test_desc_t *desc)
+{
+        return true;
+}
+
+/* Runs all available tests tests one-by-one. */
+static bool run_all_tests(void)
+{
+        printf("Running all tests...\n");
+        return run_tests(all_tests_include_filter);
+}
+
+/*--------------------------------------------------------------------*/
+
+static bool stress_tests_include_filter(test_desc_t *desc)
+{
+        return desc->type == T_STRESS;
+}
+
+/* Runs all available stress tests one-by-one. */
+static bool run_stress_tests(void)
+{
+        printf("Running stress tests...\n");
+        return run_tests(stress_tests_include_filter);
+}
+
+/*--------------------------------------------------------------------*/
+
+static bool sanity_tests_include_filter(test_desc_t *desc)
+{
+        return desc->type == T_SANITY;
+}
+
+/* Runs all available sanity tests one-by-one. */
+static bool run_sanity_tests(void)
+{
+        printf("Running sanity tests...\n");
+        return run_tests(sanity_tests_include_filter);
+}
+
+/*--------------------------------------------------------------------*/
+
+/* Locks/unlocks rcu and synchronizes without contention in a single fibril. */
+static bool basic_sanity_check(void)
+{
         rcu_read_lock();
         /* nop */
         rcu_read_unlock();
+
+        rcu_read_lock();
+        /* nop */
         rcu_read_unlock();
         
         rcu_synchronize();
-        
-        printf("Woohoo, did not crash after invoking rcu functions.\n");
-}
+
+        /* Nested lock with yield(). */
+        rcu_read_lock();
+        fibril_yield();
+        rcu_read_lock();
+        fibril_yield();
+        rcu_read_unlock();
+        fibril_yield();
+        rcu_read_unlock();
+        
+        fibril_yield();
+        rcu_synchronize();
+        rcu_synchronize();
+        
+        rcu_read_lock();
+        /* nop */
+        if (!rcu_read_locked())
+                return false;
+
+        rcu_read_unlock();
+        
+        return !rcu_read_locked();
+}
+
+typedef struct one_reader_info {
+        bool entered_cs;
+        bool exited_cs;
+        size_t done_sleeps_cnt;
+        bool synching;
+        bool synched;
+} one_reader_info_t;
+
+
+static int sleeping_reader(one_reader_info_t *arg)
+{
+        rcu_register_fibril();
+        
+        printf("lock{");
+        rcu_read_lock();
+        arg->entered_cs = true;
+
+        printf("r-sleep{");
+        /* 2 sec */
+        async_usleep(2 * USECS_PER_SEC);
+        ++arg->done_sleeps_cnt;
+        printf("}");
+        
+        arg->exited_cs = true;
+        rcu_read_unlock();
+        printf("}");
+        
+        rcu_deregister_fibril();
+        return 0;
+}
+
+static bool wait_for_one_reader(void)
+{
+        one_reader_info_t info = { 0 };
+        
+        if (!create_fibril((fibril_func_t) sleeping_reader, &info))
+                return false;
+        
+        /* 1 sec, waits for the reader to enter its critical section and sleep. */
+        async_usleep(1 * USECS_PER_SEC);
+        
+        if (!info.entered_cs || info.exited_cs) {
+                printf("Error: reader is unexpectedly outside of critical section.\n");
+                return false;
+        }
+        
+        info.synching = true;
+        printf("sync[");
+        rcu_synchronize();
+        printf("]\n");
+        info.synched = true;
+
+        /* Load info.exited_cs */
+        memory_barrier();
+        
+        if (!info.exited_cs) {
+                printf("Error: rcu_sync() returned before the reader exited its CS.\n");
+                /* 
+                 * Sleep some more so we don't free info on stack while the reader 
+                 * is using it.
+                 */
+                /* 1.5 sec */
+                async_usleep(1500 * 1000);
+                return false;
+        } else {
+                return true;
+        }
+}
+
+/*--------------------------------------------------------------------*/
+
+#define WAIT_STEP_US  1000 * USECS_PER_MS
+
+typedef struct two_reader_info {
+        bool new_entered_cs;
+        bool new_exited_cs;
+        bool old_entered_cs;
+        bool old_exited_cs;
+        bool synching;
+        bool synched;
+        size_t failed;
+} two_reader_info_t;
+
+
+static int preexisting_reader(two_reader_info_t *arg)
+{
+        rcu_register_fibril();
+        
+        printf("old-lock{");
+        rcu_read_lock();
+        arg->old_entered_cs = true;
+        
+        printf("wait-for-sync{");
+        /* Wait for rcu_sync() to start waiting for us. */
+        while (!arg->synching) {
+                async_usleep(WAIT_STEP_US);
+        }
+        printf(" }");
+        
+        /* A new reader starts while rcu_sync() is in progress. */
+        
+        printf("wait-for-new-R{");
+        /* Wait for the new reader to enter its reader section. */
+        while (!arg->new_entered_cs) {
+                async_usleep(WAIT_STEP_US);
+        }
+        printf(" }");
+        
+        arg->old_exited_cs = true;
+        
+        assert(!arg->new_exited_cs);
+        
+        if (arg->synched) {
+                arg->failed = 1;
+                printf("Error: rcu_sync() did not wait for preexisting reader.\n");
+        }
+        
+        rcu_read_unlock();
+        printf(" }");
+        
+        rcu_deregister_fibril();
+        return 0;
+}
+
+static int new_reader(two_reader_info_t *arg)
+{
+        rcu_register_fibril();
+        
+        /* Wait until rcu_sync() starts. */
+        while (!arg->synching) {
+                async_usleep(WAIT_STEP_US);
+        }
+        
+        /* 
+         * synching is set when rcu_sync() is about to be entered so wait
+         * some more to make sure it really does start executing.
+         */
+        async_usleep(WAIT_STEP_US);
+        
+        printf("new-lock(");
+        rcu_read_lock();
+        arg->new_entered_cs = true;
+
+        /* Wait for rcu_sync() exit, ie stop waiting for the preexisting reader. */
+        while (!arg->synched) {
+                async_usleep(WAIT_STEP_US);
+        }
+        
+        arg->new_exited_cs = true;
+        /* Write new_exited_cs before exiting reader section. */
+        memory_barrier();
+        
+        /* 
+         * Preexisting reader should have exited by now, so rcu_synchronize() 
+         * must have returned.
+         */
+        if (!arg->old_exited_cs) {
+                arg->failed = 1;
+                printf("Error: preexisting reader should have exited by now!\n");
+        }
+        
+        rcu_read_unlock();
+        printf(")");
+
+        rcu_deregister_fibril();
+        return 0;
+}
+
+static bool dont_wait_for_new_reader(void)
+{
+        two_reader_info_t info = { 0 };
+        
+        if (!create_fibril((fibril_func_t) preexisting_reader, &info))
+                return false;
+
+        if (!create_fibril((fibril_func_t) new_reader, &info))
+                return false;
+        
+        /* Waits for the preexisting_reader to enter its CS.*/
+        while (!info.old_entered_cs) {
+                async_usleep(WAIT_STEP_US);
+        }
+        
+        assert(!info.old_exited_cs);
+        assert(!info.new_entered_cs);
+        assert(!info.new_exited_cs);
+        
+        printf("sync[");
+        info.synching = true;
+        rcu_synchronize();
+        printf(" ]");
+        
+        /* Load info.exited_cs */
+        memory_barrier();
+        
+        if (!info.old_exited_cs) {
+                printf("Error: rcu_sync() returned before preexisting reader exited.\n");
+                info.failed = 1;
+        }
+        
+        bool new_outside_cs = !info.new_entered_cs || info.new_exited_cs;
+        
+        /* Test if new reader is waiting in CS before setting synched. */
+        compiler_barrier();
+        info.synched = true;
+                
+        if (new_outside_cs) {
+                printf("Error: new reader CS held up rcu_sync(). (4)\n");
+                info.failed = 1;
+        } else {
+                /* Wait for the new reader. */
+                rcu_synchronize();
+                
+                if (!info.new_exited_cs) {
+                        printf("Error: 2nd rcu_sync() returned before new reader exited.\n");
+                        info.failed = 1;
+                }
+                
+                printf("\n");
+        }
+        
+        if (info.failed) {
+                /* 
+                 * Sleep some more so we don't free info on stack while readers 
+                 * are using it.
+                 */
+                async_usleep(WAIT_STEP_US);
+        }
+        
+        return 0 == info.failed;
+}
+
+#undef WAIT_STEP_US
+/*--------------------------------------------------------------------*/
+/*--------------------------------------------------------------------*/
+static test_desc_t *find_test(const char *name)
+{
+        /* First match for test name. */
+        for (size_t k = 0; k < test_desc_cnt; ++k) {
+                test_desc_t *t = &test_desc[k];
+                
+                if (t->func && 0 == str_cmp(t->name, name))
+                        return t;
+        }
+        
+        /* Try to match the test number. */
+        uint32_t test_num = 0;
+        
+        if (EOK == str_uint32_t(name, NULL, 0, true, &test_num)) {
+                if (test_num < test_desc_cnt && test_desc[test_num].func) {
+                        printf("[%u]\n", test_num);
+                        return &test_desc[test_num];
+                }
+        }
+        
+        return NULL;
+}
+
+static void list_tests(void)
+{
+        printf("Available tests: \n");
+        
+        for (size_t i = 0; i < test_desc_cnt; ++i) {
+                test_desc_t *t = &test_desc[i];
+                
+                if (!t->func) 
+                        continue;
+                
+                const char *type = "";
+                
+                if (t->type == T_SANITY)
+                        type = " (sanity)";
+                if (t->type == T_STRESS)
+                        type = " (stress)";
+
+                printf("%zu: %s ..%s %s\n", i, t->name, type, t->desc);
+        }
+}
+
 
 static void print_usage(void)
 {
-        printf("Usage: rcutest \n");
+        printf("Usage: rcutest [test_name|test_number]\n");
+        list_tests();
+        
+        printf("\nExample usage:\n");
+        printf("\trcutest *\n");
+        printf("\trcutest sanity-tests\n");
 }
 
@@ -69 +556 @@
 int main(int argc, char **argv)
 {
-        if (argc >= 2) {
+        rcu_register_fibril();
+        
+        if (argc != 2) {
                 print_usage();
-                return 1;
-        }
-        
-        rcu_register_fibril();
-        
-        invoke_rcu();
-        /* todo: impl */
-        
-        rcu_deregister_fibril();
-        
-        return 0;
+                
+                rcu_deregister_fibril();
+                return 2;
+        }
+        
+        test_desc_t *t = find_test(argv[1]);
+        
+        if (t) {
+                printf("Running '%s'...\n", t->name);
+                bool ok = t->func();
+                
+                printf("%s: '%s'\n", ok ? "Passed" : "FAILED", t->name);
+                
+                rcu_deregister_fibril();
+                return ok ? 0 : 1;
+        } else {
+                printf("Non-existent test name.\n");
+                list_tests();
+                
+                rcu_deregister_fibril();
+                return 3;
+        }
 }