source: mainline/uspace/app/rcutest/rcutest.c@ 29b8138

/*
 * Copyright (c) 2012 Adam Hraska
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup test
 * @{
 */

/**
 * @file rcutest.c
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <mem.h>
#include <errno.h>
#include <thread.h>
#include <assert.h>
#include <async.h>
#include <fibril.h>
#include <compiler/barrier.h>

#include <rcu.h>


#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();

        /* 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 [test_name|test_number]\n");
        list_tests();
        
        printf("\nExample usage:\n");
        printf("\trcutest *\n");
        printf("\trcutest sanity-tests\n");
}


int main(int argc, char **argv)
{
        rcu_register_fibril();
        
        if (argc != 2) {
                print_usage();
                
                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;
        }
}


/**
 * @}
 */