code:
/*
 * Copyright (c) 2017 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
 * priority inheritance with mutexes. It creates a priority inheritance
 * tree by starting multiple threads manipulating multiple mutexes.
 *
 * Here is one intended state of the priority inheritance tree :
 *
 *
 *            C->M2-+
 *                  |
 *         D--+     +->B->M1->A
 *            |     |
 *            +->M3-+
 *            |
 *         E--+
 *
 *
 * M1,M2,M3,etc... are mutexes and A,B,C,etc... are threads. The thread
 * priorities p(thread) are ordered such that p(A) < p(B) < p(C) etc...
 * An arrow from a mutex to a thread indicates ownership, such that
 * M1->A means that A owns M1. An arrow from a thread to a mutex indicates
 * waiting, such that B->M1 means that B is waiting for M1 to be unlocked.
 *
 * In addition, thread B is actually many threads, each terminating after
 * unlocking their mutexes. Also, the priority of thread C is regularly
 * increased to p(E) + 1 and later restored to p(C).
 *
 * Here is the list of all the cases this test must cover :
 *  - Priority inheritance: All threads can get their real priority boosted.
 *    C can be boosted if it owns M2 and B waits for it while inheriting
 *    from E, and E can be boosted when p(C) is temporarily increased.
 *  - Return to normal priority: after releasing all locks, a thread must
 *    have reset its real priority to its user priority.
 *  - Priority changes: When the priority of C is increased, that priority
 *    must take precedence over all others.
 *  - Thread destruction resilience: Check that priority propagation never
 *    accesses a destroyed thread.
 *
 * Note that this test doesn't check that priority propagation correctly
 * adjusts the top priority after lowering the priority of thread C back
 * to p(C).
 *
 * In order to artificially create priority inversions, all threads run on
 * separate processors, making this test require 5 processors.
 *
 * The test should output a couple of messages about thread priorities
 * being boosted, and then frequent updates from each thread to show
 * they're all making progress. Thread B suffers from contention the most
 * so its report frequency should be lower. Thread A suffers from contention
 * the least and should be the most frequent to report progress. Because of
 * contention from B, D and E on M3, D rarely gets boosted. The reason is
 * that, when B owns the mutex, E is likely to wait on M3 soon enough that
 * it will be awaken before D, preventing the conditions for priority
 * inheritance to occur.
 *
 * Note that the test uses regular mutexes instead of real-time mutexes,
 * so that its behaviour can be analyzed for both types depending on
 * build options.
 */

#include <stddef.h>
#include <stdio.h>
#include <string.h>

#include <kern/cpumap.h>
#include <kern/error.h>
#include <kern/init.h>
#include <kern/mutex.h>
#include <kern/panic.h>
#include <kern/syscnt.h>
#include <kern/thread.h>
#include <kern/turnstile.h>
#include <test/test.h>

#define TEST_MIN_CPUS 5

#define TEST_PRIO_A (THREAD_SCHED_RT_PRIO_MIN + 1)
#define TEST_PRIO_B (TEST_PRIO_A + 1)
#define TEST_PRIO_C (TEST_PRIO_B + 1)
#define TEST_PRIO_D (TEST_PRIO_C + 1)
#define TEST_PRIO_E (TEST_PRIO_D + 1)

#define TEST_NR_LOCK_LOOPS          500
#define TEST_NR_CONSUME_CPU_LOOPS   10000000

static struct mutex test_mutex_1;
static struct mutex test_mutex_2;
static struct mutex test_mutex_3;

static const char *
test_thread_from_priority(unsigned short priority)
{
    switch (priority) {
    case TEST_PRIO_A:
        return "a";
    case TEST_PRIO_B:
        return "b";
    case TEST_PRIO_C:
        return "c";
    case TEST_PRIO_D:
        return "d";
    case TEST_PRIO_E:
        return "e";
    case TEST_PRIO_E + 1:
        return "e+";
    default:
        panic("invalid priority %u", priority);
    }
}

static char
test_get_name(void)
{
    const char *name;
    size_t length;

    name = thread_self()->name;
    length = strlen(name);
    return name[length - 1];
}

static void
test_delay(void)
{
    volatile unsigned int i;

    /*
     * Put the thread to sleep to make some CPU time available, and then
     * busy-wait to avoid synchronizing all threads on the clock tick.
     */

    thread_delay(1, false);

    for (i = 0; i < TEST_NR_CONSUME_CPU_LOOPS; i++);
}

static void
test_check_initial_priority(void)
{
    unsigned short user_priority, real_priority;
    struct thread *thread;

    thread = thread_self();
    user_priority = thread_user_priority(thread);
    real_priority = thread_real_priority(thread);

    if (user_priority != real_priority) {
        panic("%c: invalid initial priority %hu",
              test_get_name(), real_priority);
    }
}

static void
test_for_priority_boosted(unsigned short *highest_priority)
{
    unsigned short user_priority, real_priority;
    struct turnstile_td *td;
    struct thread *thread;

    thread = thread_self();
    td = thread_turnstile_td(thread);

    turnstile_td_lock(td);

    user_priority = thread_user_priority(thread);
    real_priority = thread_real_priority(thread);

    if (user_priority != real_priority) {
        if (user_priority > real_priority) {
            panic("%c: invalid real priority: %hu (boosted:%u)",
                  test_get_name(), real_priority, thread->boosted);
        }

        if (real_priority > *highest_priority) {
            printf("%c: real priority boosted to %s\n",
                   test_get_name(), test_thread_from_priority(real_priority));
            *highest_priority = real_priority;
        }
    }

    turnstile_td_unlock(td);
}

static void
test_for_priority_deboosted(void)
{
    unsigned short user_priority, real_priority;
    struct turnstile_td *td;
    struct thread *thread;

    thread = thread_self();
    td = thread_turnstile_td(thread);

    turnstile_td_lock(td);

    user_priority = thread_user_priority(thread);
    real_priority = thread_real_priority(thread);

    if (user_priority != real_priority) {
        panic("%c: real priority not reset (boosted:%d)", test_get_name(), thread->boosted);
    }

    turnstile_td_unlock(td);
}

static void
test_report_progress(unsigned int i)
{
    printf("%c:%u ", test_get_name(), i);
}

static void
test_a(void *arg)
{
    unsigned short highest_priority;
    unsigned int i, j;

    (void)arg;

    test_check_initial_priority();

    highest_priority = 0;

    for (i = 1; /* no condition */; i++) {
        for (j = 0; j < TEST_NR_LOCK_LOOPS; j++) {
            mutex_lock(&test_mutex_1);
            test_delay();
            test_for_priority_boosted(&highest_priority);
            mutex_unlock(&test_mutex_1);

            test_for_priority_deboosted();

            test_delay();
        }

        test_report_progress(i);
    }
}

static void
test_b(void *arg)
{
    test_check_initial_priority();

    mutex_lock(&test_mutex_3);
    mutex_lock(&test_mutex_2);
    mutex_lock(&test_mutex_1);
    test_delay();
    test_for_priority_boosted(arg);
    mutex_unlock(&test_mutex_1);
    test_delay();
    mutex_unlock(&test_mutex_2);
    test_delay();
    mutex_unlock(&test_mutex_3);

    /*
     * It would be better if the thread could immediately terminate, but
     * it's also the thread that locks multiple mutexes, so make sure it
     * was correctly deboosted. This should be cheap enough to not matter
     * much.
     */
    test_for_priority_deboosted();
}

static void
test_manage_b(void *arg)
{
    unsigned short highest_priority;
    struct thread_attr attr;
    struct thread *thread_b;
    struct cpumap *cpumap;
    unsigned int i, j;
    int error;

    (void)arg;

    error = cpumap_create(&cpumap);
    error_check(error, "cpumap_create");
    cpumap_zero(cpumap);
    cpumap_set(cpumap, 1);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_b");
    thread_attr_set_policy(&attr, THREAD_SCHED_POLICY_FIFO);
    thread_attr_set_priority(&attr, TEST_PRIO_B);
    thread_attr_set_cpumap(&attr, cpumap);
    cpumap_destroy(cpumap);

    highest_priority = 0;

    for (i = 1; /* no condition */; i++) {
        for (j = 0; j < TEST_NR_LOCK_LOOPS; j++) {
            error = thread_create(&thread_b, &attr, test_b, &highest_priority);
            error_check(error, "thread_create");
            thread_join(thread_b);

            test_delay();
        }

        printf("b:%u ", i);
        syscnt_info("thread_boosts");
    }
}

static void
test_c(void *arg)
{
    unsigned short highest_priority;
    unsigned int i, j;

    (void)arg;

    test_check_initial_priority();

    highest_priority = 0;

    for (i = 1; /* no condition */; i++) {
        for (j = 0; j < TEST_NR_LOCK_LOOPS; j++) {
            mutex_lock(&test_mutex_2);
            test_delay();
            test_for_priority_boosted(&highest_priority);
            mutex_unlock(&test_mutex_2);

            test_for_priority_deboosted();

            test_delay();
        }

        test_report_progress(i);
    }
}

static void
test_chprio_c(void *arg)
{
    struct thread *thread_c;

    thread_c = arg;

    test_delay();

    for (;;) {
        thread_setscheduler(thread_c, THREAD_SCHED_POLICY_FIFO,
                            TEST_PRIO_E + 1);
        thread_setscheduler(thread_c, THREAD_SCHED_POLICY_FIFO,
                            TEST_PRIO_C);
    }
}

static void
test_d(void *arg)
{
    unsigned short highest_priority;
    unsigned int i, j;

    (void)arg;

    test_check_initial_priority();

    highest_priority = 0;

    for (i = 1; /* no condition */; i++) {
        for (j = 0; j < TEST_NR_LOCK_LOOPS; j++) {
            mutex_lock(&test_mutex_3);
            test_delay();
            test_for_priority_boosted(&highest_priority);
            mutex_unlock(&test_mutex_3);

            test_for_priority_deboosted();

            test_delay();
        }

        test_report_progress(i);
    }
}

static void
test_e(void *arg)
{
    unsigned short highest_priority;
    unsigned int i, j;

    (void)arg;

    test_check_initial_priority();

    highest_priority = 0;

    for (i = 1; /* no condition */; i++) {
        for (j = 0; j < TEST_NR_LOCK_LOOPS; j++) {
            mutex_lock(&test_mutex_3);
            test_delay();
            test_for_priority_boosted(&highest_priority);
            mutex_unlock(&test_mutex_3);

            test_for_priority_deboosted();

            test_delay();
        }

        test_report_progress(i);
    }
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    struct thread *thread;
    struct cpumap *cpumap;
    int error;

    if (cpu_count() < TEST_MIN_CPUS) {
        panic("test: at least %u processors are required", TEST_MIN_CPUS);
    }

    mutex_init(&test_mutex_1);
    mutex_init(&test_mutex_2);
    mutex_init(&test_mutex_3);

    error = cpumap_create(&cpumap);
    error_check(error, "cpumap_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 0);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_a");
    thread_attr_set_detached(&attr);
    thread_attr_set_policy(&attr, THREAD_SCHED_POLICY_FIFO);
    thread_attr_set_priority(&attr, TEST_PRIO_A);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_a, NULL);
    error_check(error, "thread_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 1);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_manage_b");
    thread_attr_set_detached(&attr);
    thread_attr_set_policy(&attr, THREAD_SCHED_POLICY_FIFO);
    thread_attr_set_priority(&attr, TEST_PRIO_B);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_manage_b, NULL);
    error_check(error, "thread_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 2);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_c");
    thread_attr_set_detached(&attr);
    thread_attr_set_policy(&attr, THREAD_SCHED_POLICY_FIFO);
    thread_attr_set_priority(&attr, TEST_PRIO_C);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_c, NULL);
    error_check(error, "thread_create");

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_chprio_c");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, test_chprio_c, thread);
    error_check(error, "thread_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 3);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_d");
    thread_attr_set_detached(&attr);
    thread_attr_set_policy(&attr, THREAD_SCHED_POLICY_FIFO);
    thread_attr_set_priority(&attr, TEST_PRIO_D);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_d, NULL);
    error_check(error, "thread_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 4);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_e");
    thread_attr_set_detached(&attr);
    thread_attr_set_policy(&attr, THREAD_SCHED_POLICY_FIFO);
    thread_attr_set_priority(&attr, TEST_PRIO_E);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_e, NULL);
    error_check(error, "thread_create");

    cpumap_destroy(cpumap);
}


code:
/*
 * Copyright (c) 2014-2018 Remy Noel.
 * 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 checks the behavior of performance monitoring on a CPU.
 * It creates a group with two events, cycle and instruction, and attaches
 * that group to CPU1, where a thread is bound and runs a tight loop to
 * make sure the target CPU is never idle. After some time, the measurement
 * stops and values are reported.
 */

#include <errno.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#include <kern/atomic.h>
#include <kern/clock.h>
#include <kern/cpumap.h>
#include <kern/error.h>
#include <kern/list.h>
#include <kern/log.h>
#include <kern/panic.h>
#include <kern/perfmon.h>
#include <kern/thread.h>
#include <machine/cpu.h>
#include <test/test.h>

#define TEST_WAIT_DELAY_MS 1000

/*
 * Using another CPU than the BSP as the monitored CPU checks that PMUs are
 * correctly initialized on APs.
 */
#define TEST_CONTROL_CPU    0
#define TEST_MONITORED_CPU  (TEST_CONTROL_CPU + 1)
#define TEST_MIN_CPUS       (TEST_MONITORED_CPU + 1)

#define TEST_EVENT_NAME_MAX_SIZE 32

struct test_event {
    struct list node;
    struct perfmon_event pm_event;
    char name[TEST_EVENT_NAME_MAX_SIZE];
};

struct test_group {
    struct list events;
};

static unsigned int test_run_stop;

static void
test_wait(void)
{
    thread_delay(clock_ticks_from_ms(TEST_WAIT_DELAY_MS), false);
}

static void
test_event_init(struct test_event *event, unsigned int id, const char *name)
{
    int error;

    error = perfmon_event_init(&event->pm_event, id, PERFMON_EF_KERN);
    error_check(error, "perfmon_event_init");
    strlcpy(event->name, name, sizeof(event->name));
}

static void
test_event_report(struct test_event *event)
{
    uint64_t count;
    int error;

    count = perfmon_event_read(&event->pm_event);
    error = (count == 0) ? EINVAL : 0;
    error_check(error, __func__);
    log_info("test: %s: %llu", event->name, (unsigned long long)count);
}

static void
test_event_attach_cpu(struct test_event *event, unsigned int cpu)
{
    int error;

    error = perfmon_event_attach_cpu(&event->pm_event, cpu);
    error_check(error, "perfmon_event_attach_cpu");
}

static void
test_event_detach(struct test_event *event)
{
    int error;

    error = perfmon_event_detach(&event->pm_event);
    error_check(error, "perfmon_event_detach");
}

static void
test_group_init(struct test_group *group)
{
    list_init(&group->events);
}

static void
test_group_add(struct test_group *group, struct test_event *event)
{
    list_insert_tail(&group->events, &event->node);
}

static void
test_group_attach_cpu(struct test_group *group, unsigned int cpu)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_attach_cpu(event, cpu);
    }
}

static void
test_group_detach(struct test_group *group)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_detach(event);
    }
}

static void
test_group_report(struct test_group *group)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_report(event);
    }
}

static void
test_run(void *arg)
{
    unsigned int stop;

    (void)arg;

    do {
        stop = atomic_load(&test_run_stop, ATOMIC_RELAXED);
    } while (!stop);
}

static void
test_control(void *arg)
{
    struct test_event cycle, instruction;
    struct test_group group;
    struct thread *thread;

    thread = arg;

    test_event_init(&cycle, PERFMON_EV_CYCLE, "cycle");
    test_event_init(&instruction, PERFMON_EV_INSTRUCTION, "instruction");
    test_group_init(&group);
    test_group_add(&group, &cycle);
    test_group_add(&group, &instruction);
    test_group_attach_cpu(&group, TEST_MONITORED_CPU);
    test_wait();
    test_group_report(&group);
    test_wait();
    test_group_detach(&group);
    test_group_report(&group);

    atomic_store(&test_run_stop, 1, ATOMIC_RELAXED);
    thread_join(thread);
    log_info("test: done");
}

void
test_setup(void)
{
    struct thread *thread;
    struct thread_attr attr;
    struct cpumap *cpumap;
    int error;

    if (cpu_count() < TEST_MIN_CPUS) {
        panic("test: %u processors required", TEST_MIN_CPUS);
    }

    error = cpumap_create(&cpumap);
    error_check(error, "cpumap_create");

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run");
    cpumap_zero(cpumap);
    cpumap_set(cpumap, TEST_MONITORED_CPU);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_run, NULL);
    error_check(error, "thread_create");

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_control");
    thread_attr_set_detached(&attr);
    cpumap_zero(cpumap);
    cpumap_set(cpumap, TEST_CONTROL_CPU);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(NULL, &attr, test_control, thread);
    error_check(error, "thread_create");

    cpumap_destroy(cpumap);
}

license: mit


code:
/*
 * Copyright (c) 2014-2018 Remy Noel.
 * 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 checks the behavior of performance monitoring on a thread.
 * It creates a group with a single event, cycle, and attaches that group to
 * a runner thread. Two checks are then performed :
 *  - the first makes sure the number of cycles changes when the runner
 *    thread is running
 *  - the second makes sure the number of cycles doesn't change when the
 *    runner thread is sleeping
 *
 * Another group with a cycle event is created and attached to CPU0 to make
 * sure that a shared event is correctly handled, and the runner thread is
 * bound to CPU0 to force sharing. A third thread is created to fill CPU0
 * time with cycles so that the cycle counter of the CPU-attached group
 * changes while the runner thread is sleeping.
 */

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <string.h>

#include <kern/atomic.h>
#include <kern/clock.h>
#include <kern/condition.h>
#include <kern/cpumap.h>
#include <kern/error.h>
#include <kern/kmem.h>
#include <kern/list.h>
#include <kern/log.h>
#include <kern/mutex.h>
#include <kern/panic.h>
#include <kern/perfmon.h>
#include <kern/thread.h>
#include <test/test.h>

#define TEST_WAIT_DELAY_MS 1000

#define TEST_EVENT_NAME_MAX_SIZE 32

struct test_event {
    struct list node;
    struct perfmon_event pm_event;
    uint64_t last_value;
    char name[TEST_EVENT_NAME_MAX_SIZE];
};

struct test_group {
    struct list events;
};

enum test_state {
    TEST_STATE_RUNNING,
    TEST_STATE_SUSPENDED,
    TEST_STATE_TERMINATED,
};

static struct condition test_condition;
static struct mutex test_mutex;
static enum test_state test_state;

static void
test_wait(void)
{
    log_info("test: controller waiting");
    thread_delay(clock_ticks_from_ms(TEST_WAIT_DELAY_MS), false);
    log_info("test: controller resuming");
}

static void
test_event_init(struct test_event *event, unsigned int id, const char *name)
{
    int error;

    error = perfmon_event_init(&event->pm_event, id, PERFMON_EF_KERN);
    error_check(error, "perfmon_event_init");
    strlcpy(event->name, name, sizeof(event->name));
}

static void
test_event_attach(struct test_event *event, struct thread *thread)
{
    int error;

    error = perfmon_event_attach(&event->pm_event, thread);
    error_check(error, "perfmon_event_attach");
}

static void
test_event_attach_cpu(struct test_event *event, unsigned int cpu)
{
    int error;

    error = perfmon_event_attach_cpu(&event->pm_event, cpu);
    error_check(error, "perfmon_event_attach_cpu");
}

static void
test_event_detach(struct test_event *event)
{
    int error;

    error = perfmon_event_detach(&event->pm_event);
    error_check(error, "perfmon_event_detach");
}

static uint64_t
test_event_read(struct test_event *event)
{
    uint64_t value;

    value = perfmon_event_read(&event->pm_event);
    log_info("test: %s: %llu", event->name, (unsigned long long)value);
    return value;
}

static void
test_event_save(struct test_event *event)
{
    event->last_value = test_event_read(event);
}

static void
test_event_check(struct test_event *event, bool change_expected)
{
    uint64_t value;
    bool changed;

    value = test_event_read(event);
    changed = (value != event->last_value);

    if (changed != change_expected) {
        panic("test: invalid value");
    }

    event->last_value = value;
}

static void
test_group_init(struct test_group *group)
{
    list_init(&group->events);
}

static void
test_group_add(struct test_group *group, struct test_event *event)
{
    list_insert_tail(&group->events, &event->node);
}

static void
test_group_attach(struct test_group *group, struct thread *thread)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_attach(event, thread);
    }
}

static void
test_group_attach_cpu(struct test_group *group, unsigned int cpu)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_attach_cpu(event, cpu);
    }
}

static void
test_group_detach(struct test_group *group)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_detach(event);
    }
}

static void
test_group_save(struct test_group *group)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_save(event);
    }
}

static void
test_group_check(struct test_group *group, bool change_expected)
{
    struct test_event *event;

    list_for_each_entry(&group->events, event, node) {
        test_event_check(event, change_expected);
    }
}

static void
test_run(void *arg)
{
    bool report;

    (void)arg;

    report = true;

    mutex_lock(&test_mutex);

    while (test_state != TEST_STATE_TERMINATED) {
        if (test_state == TEST_STATE_SUSPENDED) {
            log_info("test: runner suspended");
            report = true;
            condition_wait(&test_condition, &test_mutex);
        } else {
            mutex_unlock(&test_mutex);

            if (report) {
                log_info("test: runner running");
                report = false;
            }

            mutex_lock(&test_mutex);
        }
    }

    mutex_unlock(&test_mutex);
}

static void
test_fill(void *arg)
{
    enum test_state state;

    (void)arg;

    do {
        state = atomic_load(&test_state, ATOMIC_RELAXED);
    } while (state != TEST_STATE_TERMINATED);
}

static void
test_wait_state(const struct thread *thread, unsigned short state)
{
    for (;;) {
        if (thread_state(thread) == state) {
            break;
        }

        thread_delay(1, false);
    }
}

static void
test_resume(struct thread *thread)
{
    test_wait_state(thread, THREAD_SLEEPING);

    mutex_lock(&test_mutex);
    assert(test_state == TEST_STATE_SUSPENDED);
    atomic_store(&test_state, TEST_STATE_RUNNING, ATOMIC_RELAXED);
    condition_signal(&test_condition);
    mutex_unlock(&test_mutex);

    test_wait_state(thread, THREAD_RUNNING);
}

static void
test_suspend(struct thread *thread)
{
    test_wait_state(thread, THREAD_RUNNING);

    mutex_lock(&test_mutex);
    assert(test_state == TEST_STATE_RUNNING);
    atomic_store(&test_state, TEST_STATE_SUSPENDED, ATOMIC_RELAXED);
    mutex_unlock(&test_mutex);

    test_wait_state(thread, THREAD_SLEEPING);
}

static void
test_terminate(void)
{
    mutex_lock(&test_mutex);
    test_state = TEST_STATE_TERMINATED;
    condition_signal(&test_condition);
    mutex_unlock(&test_mutex);
}

static void
test_control(void *arg)
{
    struct test_event thread_cycle, cpu_cycle;
    struct test_group thread_group, cpu_group;
    struct thread *runner;

    runner = arg;

    test_event_init(&thread_cycle, PERFMON_EV_CYCLE, "thread_cycle");
    test_group_init(&thread_group);
    test_group_add(&thread_group, &thread_cycle);

    test_event_init(&cpu_cycle, PERFMON_EV_CYCLE, "cpu_cycle");
    test_group_init(&cpu_group);
    test_group_add(&cpu_group, &cpu_cycle);

    test_group_attach(&thread_group, runner);
    test_group_attach_cpu(&cpu_group, 0);

    test_group_save(&thread_group);
    test_group_save(&cpu_group);
    test_resume(runner);
    test_wait();
    test_suspend(runner);
    test_group_check(&thread_group, true);
    test_group_check(&cpu_group, true);
    test_wait();
    test_group_check(&thread_group, false);
    test_group_check(&cpu_group, true);
    test_terminate();

    test_group_detach(&cpu_group);
    test_group_detach(&thread_group);

    thread_join(runner);
    log_info("test: done");
}

void
test_setup(void)
{
    struct thread_attr attr;
    struct thread *runner;
    struct cpumap *cpumap;
    int error;

    condition_init(&test_condition);
    mutex_init(&test_mutex);
    test_state = TEST_STATE_SUSPENDED;

    error = cpumap_create(&cpumap);
    error_check(error, "cpumap_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 0);

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run");
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&runner, &attr, test_run, NULL);
    error_check(error, "thread_create");

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_fill");
    thread_attr_set_detached(&attr);
    thread_attr_set_cpumap(&attr, cpumap);
    thread_attr_set_priority(&attr, THREAD_SCHED_FS_PRIO_MIN);
    error = thread_create(NULL, &attr, test_fill, NULL);
    error_check(error, "thread_create");

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_control");
    thread_attr_set_detached(&attr);
    error = thread_create(NULL, &attr, test_control, runner);
    error_check(error, "thread_create");

    cpumap_destroy(cpumap);
}


code:
/*
 * Copyright (c) 2014-2018 Remy Noel.
 * 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 module is a stress test, expected to never terminate, of the
 * performance monitoring module. It creates a control thread which
 * maintains a couple of test threads running while toggling performance
 * monitoring on them, attempting to produce many regular and corner
 * cases. In particular, the thread pool is randomly resized by destroying
 * and creating the underlying kernel threads.
 *
 * The control thread regularly prints some stats about the thread pool
 * and the associated performance monitoring events to report that it's
 * making progress.
 */

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

#include <kern/atomic.h>
#include <kern/clock.h>
#include <kern/error.h>
#include <kern/kmem.h>
#include <kern/log.h>
#include <kern/panic.h>
#include <kern/perfmon.h>
#include <kern/thread.h>
#include <test/test.h>

struct test_thread {
    unsigned int id;
    struct thread *thread;
    struct perfmon_event event;
    unsigned int must_stop;
    bool monitored;
    unsigned long long count;
};

struct test_controller {
    struct test_thread **threads;
    unsigned int nr_threads;
    unsigned int monitoring_lid;
    unsigned int state_lid;
    unsigned long nr_current_events;
    unsigned long nr_total_events;
    unsigned long nr_current_threads;
    unsigned long nr_total_threads;
};

#define TEST_WAIT_DELAY_MS      100
#define TEST_LOOPS_PER_PRINT    20

#define TEST_MONITORING_SEED    12345
#define TEST_STATE_SEED         23456

static void
test_wait(void)
{
    thread_delay(clock_ticks_from_ms(TEST_WAIT_DELAY_MS), false);
}

static unsigned int
test_rand(unsigned int x)
{
    /* Basic 32-bit xorshift PRNG */
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

static bool
test_thread_monitored(const struct test_thread *thread)
{
    return thread->monitored;
}

static void
test_thread_start_monitoring(struct test_thread *thread)
{
    int error;

    error = perfmon_event_attach(&thread->event, thread->thread);
    error_check(error, __func__);
    thread->monitored = true;
}

static void
test_thread_stop_monitoring(struct test_thread *thread)
{
    int error;

    thread->count += perfmon_event_read(&thread->event);
    error = perfmon_event_detach(&thread->event);
    error_check(error, __func__);
    thread->monitored = false;
}

static void
test_thread_report(const struct test_thread *thread)
{
    log_info("test: thread:%u count:%llu", thread->id, thread->count);
}

static void
test_run(void *arg)
{
    struct test_thread *thread;

    thread = arg;

    for (;;) {
        if (atomic_load(&thread->must_stop, ATOMIC_RELAXED)) {
            break;
        }
    }
}

static bool
test_thread_started(const struct test_thread *thread)
{
    return thread->thread;
}

static void
test_thread_start(struct test_thread *thread)
{
    char name[THREAD_NAME_SIZE];
    struct thread_attr attr;
    int error;

    assert(!thread->monitored);

    if (test_thread_started(thread)) {
        return;
    }

    thread->must_stop = 0;

    snprintf(name, sizeof(name),
             THREAD_KERNEL_PREFIX "test_run:%u", thread->id);
    thread_attr_init(&attr, name);
    error = thread_create(&thread->thread, &attr, test_run, thread);
    error_check(error, "thread_create");
}

static void
test_thread_request_stop(struct test_thread *thread)
{
    atomic_store(&thread->must_stop, 1, ATOMIC_RELAXED);
}

static void
test_thread_join(struct test_thread *thread)
{
    assert(test_thread_started(thread));
    assert(!test_thread_monitored(thread));

    thread_join(thread->thread);
    thread->thread = NULL;
}

static struct test_thread *
test_thread_create(unsigned int id)
{
    struct test_thread *thread;

    thread = kmem_alloc(sizeof(*thread));

    if (thread == NULL) {
        panic("thread allocation failed");
    }

    thread->id = id;
    thread->thread = NULL;
    thread->must_stop = 0;
    thread->monitored = false;
    thread->count = 0;

    perfmon_event_init(&thread->event, PERFMON_EV_CYCLE, PERFMON_EF_KERN);
    test_thread_start(thread);

    return thread;
}

static struct test_thread *
test_controller_get(struct test_controller *controller, unsigned int id)
{
    assert(id < controller->nr_threads);
    return controller->threads[id];
}

static struct test_thread *
test_controller_get_by_lid(struct test_controller *controller, unsigned int lid)
{
    return test_controller_get(controller, lid % controller->nr_threads);
}

static void
test_toggle_monitoring(struct test_controller *controller,
                       struct test_thread *thread)
{
    if (!test_thread_started(thread)) {
        return;
    }

    if (thread->monitored) {
        test_thread_stop_monitoring(thread);
        controller->nr_current_events--;
    } else {
        test_thread_start_monitoring(thread);
        controller->nr_total_events++;
        controller->nr_current_events++;
    }
}

static void
test_toggle_state(struct test_controller *controller,
                  struct test_thread *thread)
{
    if (test_thread_started(thread)) {
        /*
         * Make the thread stop asynchronously with monitoring to test
         * thread referencing.
         */
        test_thread_request_stop(thread);

        if (test_thread_monitored(thread)) {
            test_thread_stop_monitoring(thread);
            controller->nr_current_events--;
        }

        test_thread_join(thread);
        controller->nr_current_threads--;
    } else {
        test_thread_start(thread);
        controller->nr_total_threads++;
        controller->nr_current_threads++;
    }
}

static void
test_controller_report(struct test_controller *controller)
{
    log_info("test: events:%lu total:%lu threads:%lu total:%lu",
             controller->nr_current_events, controller->nr_total_events,
             controller->nr_current_threads, controller->nr_total_threads);

    for (unsigned int i = 0; i < controller->nr_threads; i++) {
        test_thread_report(test_controller_get(controller, i));
    }
}

static void
test_control(void *arg)
{
    struct test_controller *controller;
    struct test_thread *thread;

    controller = arg;

    log_info("test: %u threads", controller->nr_threads);

    for (unsigned long nr_loops = 1; /* no condition */; nr_loops++) {
        controller->monitoring_lid = test_rand(controller->monitoring_lid);
        thread = test_controller_get_by_lid(controller,
                                            controller->monitoring_lid);
        test_toggle_monitoring(controller, thread);

        controller->state_lid = test_rand(controller->state_lid);
        thread = test_controller_get_by_lid(controller,
                                            controller->state_lid);
        test_toggle_state(controller, thread);

        test_wait();

        if ((nr_loops % TEST_LOOPS_PER_PRINT) == 0) {
            test_controller_report(controller);
        }
    }
}

static void
test_controller_create(void)
{
    struct test_controller *controller;
    struct thread_attr attr;
    int error;

    controller = kmem_alloc(sizeof(*controller));

    if (!controller) {
        panic("test: unable to create controller");
    }

    /*
     * At least two threads are required by the monitoring/state toggling
     * operations, otherwise they always apply to the same thread, severely
     * restricting their usefulness.
     */
    controller->nr_threads = MAX(cpu_count() - 1, 2);
    controller->threads = kmem_alloc(controller->nr_threads
                                     * sizeof(*controller->threads));

    if (!controller->threads) {
        panic("test: unable to allocate thread array");
    }

    for (unsigned int i = 0; i < controller->nr_threads; i++) {
        controller->threads[i] = test_thread_create(i);
    }

    controller->monitoring_lid = TEST_MONITORING_SEED;
    controller->state_lid = TEST_STATE_SEED;
    controller->nr_current_events = 0;
    controller->nr_total_events = 0;
    controller->nr_current_threads = controller->nr_threads;
    controller->nr_total_threads = controller->nr_threads;

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_control");
    thread_attr_set_detached(&attr);
    error = thread_create(NULL, &attr, test_control, controller);
    error_check(error, "thread_create");
}

void
test_setup(void)
{
    test_controller_create();
}


code:
/*
 * Copyright (c) 2014 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/>.
 *
 *
 * The purpose of this test module is to check that the pmap module properly
 * synchronizes page tables across processors. Two threads are created and
 * bound to processors 0 and 1 respectively. The first thread allocates a
 * page and writes it, making sure physical mappings are up-to-date locally.
 * It then transfers the page address to the second thread which validates
 * the content of the page, an operation that can only be done if the page
 * tables of the current processor have been updated.
 */

#include <stddef.h>
#include <stdio.h>
#include <string.h>

#include <kern/condition.h>
#include <kern/cpumap.h>
#include <kern/error.h>
#include <kern/init.h>
#include <kern/mutex.h>
#include <kern/panic.h>
#include <kern/thread.h>
#include <machine/page.h>
#include <test/test.h>
#include <vm/vm_kmem.h>

static struct condition test_condition;
static struct mutex test_lock;
static void *test_va;

static void
test_run1(void *arg)
{
    void *ptr;

    (void)arg;

    printf("allocating page\n");
    ptr = vm_kmem_alloc(PAGE_SIZE);
    printf("writing page\n");
    memset(ptr, 'a', PAGE_SIZE);

    printf("passing page to second thread (%p)\n", ptr);

    mutex_lock(&test_lock);
    test_va = ptr;
    condition_signal(&test_condition);
    mutex_unlock(&test_lock);
}

static void
test_run2(void *arg)
{
    char *ptr;
    unsigned int i;

    (void)arg;

    printf("waiting for page\n");

    mutex_lock(&test_lock);

    while (test_va == NULL) {
        condition_wait(&test_condition, &test_lock);
    }

    ptr = test_va;

    mutex_unlock(&test_lock);

    printf("page received (%p), checking page\n", ptr);

    for (i = 0; i < PAGE_SIZE; i++) {
        if (ptr[i] != 'a') {
            panic("invalid content");
        }
    }

    vm_kmem_free(ptr, PAGE_SIZE);
    printf("done\n");
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    struct thread *thread;
    struct cpumap *cpumap;
    int error;

    condition_init(&test_condition);
    mutex_init(&test_lock);
    test_va = NULL;

    error = cpumap_create(&cpumap);
    error_check(error, "cpumap_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 0);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run1");
    thread_attr_set_detached(&attr);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_run1, NULL);
    error_check(error, "thread_create");

    cpumap_zero(cpumap);
    cpumap_set(cpumap, 1);
    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run2");
    thread_attr_set_detached(&attr);
    thread_attr_set_cpumap(&attr, cpumap);
    error = thread_create(&thread, &attr, test_run2, NULL);
    error_check(error, "thread_create");

    cpumap_destroy(cpumap);
}


code:
/*
 * 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/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;
    int error;

    condition_init(&test_condition);
    mutex_init(&test_lock);

    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);
    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);
    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);
    error = thread_create(&thread, &attr, test_read, NULL);
    error_check(error, "thread_create");
}


code:
/*
 * Copyright (c) 2014 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/>.
 *
 *
 * The purpose of this test module is to produce dirty zeroes and make
 * sure they're correctly processed. It is a stress test that never ends,
 * except on failure. Two threads are created. The first increments a
 * scalable reference counter, then signals the second that it can decrement
 * it. Since these threads are likely to run on different processors, a
 * good amount of dirty zeroes should be produced, as reported by regularly
 * printing the relevant event counters. Since the true number of references
 * can never drop to 0, the no-reference function should never be called,
 * and panics if it is.
 */

#include <stddef.h>
#include <stdio.h>

#include <kern/condition.h>
#include <kern/error.h>
#include <kern/init.h>
#include <kern/kmem.h>
#include <kern/macros.h>
#include <kern/mutex.h>
#include <kern/panic.h>
#include <kern/sref.h>
#include <kern/syscnt.h>
#include <kern/thread.h>
#include <test/test.h>
#include <vm/vm_kmem.h>

static struct condition test_condition;
static struct mutex test_lock;
static struct sref_counter test_counter;
static unsigned long test_transient_ref;

static void
test_inc(void *arg)
{
    volatile unsigned long i;
    (void)arg;

    for (;;) {
        for (i = 0; i < 1000000; i++) {
            sref_counter_inc(&test_counter);

            mutex_lock(&test_lock);
            test_transient_ref++;
            condition_signal(&test_condition);

            while (test_transient_ref != 0) {
                condition_wait(&test_condition, &test_lock);
            }

            mutex_unlock(&test_lock);
        }

        printf("counter global value: %lu\n", test_counter.value);
        syscnt_info("sref_epoch");
        syscnt_info("sref_dirty_zero");
        syscnt_info("sref_true_zero");
    }
}

static void
test_dec(void *arg)
{
    (void)arg;

    for (;;) {
        mutex_lock(&test_lock);

        while (test_transient_ref == 0) {
            condition_wait(&test_condition, &test_lock);
        }

        test_transient_ref--;
        condition_signal(&test_condition);
        mutex_unlock(&test_lock);

        sref_counter_dec(&test_counter);
    }
}

static void
test_noref(struct sref_counter *counter)
{
    (void)counter;
    panic("0 references, page released\n");
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    struct thread *thread;
    int error;

    condition_init(&test_condition);
    mutex_init(&test_lock);

    sref_counter_init(&test_counter, 1, NULL, test_noref);
    test_transient_ref = 0;

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_inc");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, test_inc, NULL);
    error_check(error, "thread_create");

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_dec");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, test_dec, NULL);
    error_check(error, "thread_create");
}


code:
/*
 * Copyright (c) 2014 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 checks that the no-reference function of a scalable
 * reference counter is actually called when the number of references drops
 * to 0. An initial master thread creates a bunch of slave threads, more
 * than the number of processors to enforce migrations. These slaves wait
 * for the master to allocate a page for a test object with a scalable
 * reference counter. Once they receive the page, they manipulate the
 * counter until the master thread tells them to stop. The master thread
 * also manipulates the counter for a fixed number of iterations before
 * stopping the slaves. The master thread then joins all slaves to make
 * sure all of them have released their reference on the test object.
 * Finally, it releases the initial reference, at which point, the
 * no-reference function should be called.
 *
 * Notes: the number of loops must be large enough to allow many epochs
 * to occur.
 */

#include <errno.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>

#include <kern/condition.h>
#include <kern/init.h>
#include <kern/error.h>
#include <kern/kmem.h>
#include <kern/macros.h>
#include <kern/mutex.h>
#include <kern/panic.h>
#include <kern/sref.h>
#include <kern/syscnt.h>
#include <kern/thread.h>
#include <test/test.h>
#include <vm/vm_kmem.h>

#define NR_LOOPS (100UL * 1000 * 1000)

struct test_obj {
    struct sref_counter ref_counter;
};

static struct condition test_condition;
static struct mutex test_lock;
static struct test_obj *test_obj;
static volatile int test_stop;

static void
test_manipulate_counter(struct test_obj *obj)
{
    sref_counter_inc(&obj->ref_counter);
    thread_yield();
    sref_counter_dec(&obj->ref_counter);
    thread_yield();
}

static void
test_ref(void *arg)
{
    struct test_obj *obj;

    (void)arg;

    mutex_lock(&test_lock);

    printf("waiting for page\n");

    while (test_obj == NULL) {
        condition_wait(&test_condition, &test_lock);
    }

    obj = test_obj;

    mutex_unlock(&test_lock);

    printf("page received, manipulate reference counter\n");

    while (!test_stop) {
        test_manipulate_counter(obj);
    }

    printf("thread exiting\n");
}

static void
test_obj_noref(struct sref_counter *counter)
{
    struct test_obj *obj;

    obj = structof(counter, struct test_obj, ref_counter);
    vm_kmem_free(obj, sizeof(*obj));
    printf("0 references, page released\n");
    syscnt_info("sref_epoch");
    syscnt_info("sref_dirty_zero");
    syscnt_info("sref_true_zero");
}

static void
test_run(void *arg)
{
    char name[THREAD_NAME_SIZE];
    struct thread_attr attr;
    struct thread **threads;
    struct test_obj *obj;
    volatile unsigned long loop;
    unsigned int i, nr_threads;
    int error;

    (void)arg;

    nr_threads = cpu_count() + 1;
    threads = kmem_alloc(sizeof(*threads) * nr_threads);

    if (threads == NULL) {
        panic("kmem_alloc: %s", strerror(ENOMEM));
    }

    for (i = 0; i < nr_threads; i++) {
        snprintf(name, sizeof(name), THREAD_KERNEL_PREFIX "test_ref/%u", i);
        thread_attr_init(&attr, name);
        error = thread_create(&threads[i], &attr, test_ref, NULL);
        error_check(error, "thread_create");
    }

    printf("allocating page\n");
    obj = vm_kmem_alloc(sizeof(*obj));

    if (obj == NULL) {
        panic("vm_kmem_alloc: %s", strerror(ENOMEM));
    }

    sref_counter_init(&obj->ref_counter, 1, NULL, test_obj_noref);

    printf("page allocated, 1 reference, publishing\n");

    mutex_lock(&test_lock);
    test_obj = obj;
    condition_broadcast(&test_condition);
    mutex_unlock(&test_lock);

    for (loop = 0; loop < NR_LOOPS; loop++) {
        test_manipulate_counter(obj);
    }

    printf("stopping test, wait for threads\n");
    test_stop = 1;

    for (i = 0; i < nr_threads; i++) {
        thread_join(threads[i]);
    }

    printf("releasing initial reference\n");
    sref_counter_dec(&obj->ref_counter);

    kmem_free(threads, sizeof(*threads) * nr_threads);
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    struct thread *thread;
    int error;

    condition_init(&test_condition);
    mutex_init(&test_lock);

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, test_run, NULL);
    error_check(error, "thread_create");
}


code:
/*
 * Copyright (c) 2017 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 module is a stress test of the weak reference implementation
 * of scalable reference counters. Two threads are created. The first
 * periodically allocates a page and initializes a counter inside the
 * page, then immediately decrements the counter. The intended effect
 * is to mark the counter as dying as soon as possible. The second
 * thread continually attempts to obtain a reference, i.e. increment
 * the counter, through a weak reference. Counters are regularly
 * printed to monitor activity. There should be almost as many noref
 * calls as there are iterations in the first thread (a bit lower
 * because of the review delay) and a good amount of revives (at least
 * on multiprocessor machines) caused by successfully getting the counter
 * from the weak reference while it is marked dying but still in review.
 * Iterations in the second thread may spike when obtaining a reference
 * fails, because the error case is much faster and continues until the
 * first thread reinitializes the weak reference.
 */

#include <stddef.h>
#include <stdio.h>

#include <kern/error.h>
#include <kern/init.h>
#include <kern/macros.h>
#include <kern/sref.h>
#include <kern/syscnt.h>
#include <kern/thread.h>
#include <test/test.h>
#include <vm/vm_kmem.h>

static struct sref_weakref test_weakref;

static void
test_noref(struct sref_counter *counter)
{
    vm_kmem_free(counter, sizeof(*counter));
}

static void
test_run(void *arg)
{
    struct sref_counter *counter;
    volatile unsigned long j;
    unsigned long i;

    (void)arg;

    for (i = 1; /* no condition */; i++) {
        counter = vm_kmem_alloc(sizeof(*counter));

        if (counter == NULL) {
            continue;
        }

        sref_counter_init(counter, 1, &test_weakref, test_noref);
        sref_counter_dec(counter);

        for (j = 0; j < 0x20000000; j++);

        printf("run: iterations: %lu\n", i);
        syscnt_info("sref_epoch");
        syscnt_info("sref_dirty_zero");
        syscnt_info("sref_revive");
        syscnt_info("sref_true_zero");
    }
}

static void
test_ref(void *arg)
{
    struct sref_counter *counter;
    unsigned long i;

    (void)arg;

    for (i = 1; /* no condition */; i++) {
        counter = sref_weakref_get(&test_weakref);

        if (counter != NULL) {
            sref_counter_dec(counter);
        }

        if ((i % 100000000) == 0) {
            printf("ref: iterations: %lu\n", i);
        }
    }
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    struct thread *thread;
    int error;

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, test_run, NULL);
    error_check(error, "thread_create");

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_ref");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, test_ref, NULL);
    error_check(error, "thread_create");
}


code:
/*
 * Copyright (c) 2018 Agustina Arzille.
 *
 * 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 checks that thread state transitions are correctly performed
 * when a thread is suspended and resumed. It does so by creating three
 * threads :
 *
 *  - The first thread spins on an atomic integer used as a lock, which
 *    puts it in the running state. The lock is released while the thread
 *    is suspended, and the thread is then resumed.
 *
 *  - The second thread waits on a zero-valued semaphore, which puts it
 *    in the sleeping state. The semaphore is signalled while the thread
 *    is suspended, and the thread is then resumed.
 *
 *  - The third suspends itself and is then resumed.
 *
 * As a result, the following transitions are tested :
 *  o CREATED -> RUNNING (*) -> SUSPENDED -> RUNNING
 *  o CREATED -> RUNNING -> SLEEPING (*) -> SUSPENDED -> RUNNING.
 *
 * (*) Step where a suspend request is made
 */

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

#include <kern/atomic.h>
#include <kern/error.h>
#include <kern/init.h>
#include <kern/log.h>
#include <kern/panic.h>
#include <kern/semaphore.h>
#include <kern/thread.h>
#include <machine/cpu.h>
#include <test/test.h>

static void
test_wait_for_state(const struct thread *thread, unsigned int state)
{
    while (thread_state(thread) != state) {
        cpu_pause();
    }
}

static void
test_spin(void *arg)
{
    unsigned long *lock;

    lock = arg;

    while (atomic_cas(lock, 0UL, 1UL, ATOMIC_ACQ_REL) != 0) {
        cpu_pause();
    }
}

static void
test_sleep(void *arg)
{
    struct semaphore *sem;

    sem = arg;
    semaphore_wait(sem);
}

static void
test_suspend_self(void *arg)
{
    (void)arg;
    thread_suspend(thread_self());
}

static void
test_run(void *arg)
{
    struct thread *thread;
    struct thread_attr attr;
    unsigned long lock;
    struct semaphore sem;
    int error;

    (void)arg;

    lock = 1;
    thread_attr_init(&attr, "test_spin");
    error = thread_create(&thread, &attr, test_spin, &lock);
    error_check(error, "thread_create");

    test_wait_for_state(thread, THREAD_RUNNING);
    thread_suspend(thread);
    test_wait_for_state(thread, THREAD_SUSPENDED);

    atomic_store(&lock, 0, ATOMIC_RELEASE);
    thread_resume(thread);
    thread_join(thread);

    semaphore_init(&sem, 0);
    thread_attr_init(&attr, "test_sleep");
    error = thread_create(&thread, &attr, test_sleep, &sem);
    error_check(error, "thread_create");

    test_wait_for_state(thread, THREAD_SLEEPING);
    thread_suspend(thread);
    test_wait_for_state(thread, THREAD_SUSPENDED);
    thread_wakeup(thread);

    if (thread_state(thread) != THREAD_SUSPENDED) {
        panic("test: unexpected thread state");
    }

    semaphore_post(&sem);
    thread_resume(thread);
    thread_join(thread);

    thread_attr_init(&attr, "test_suspend_self");
    error = thread_create(&thread, &attr, test_suspend_self, NULL);
    test_wait_for_state(thread, THREAD_SUSPENDED);
    thread_resume(thread);
    thread_join(thread);

    log_info("done");
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    int error;

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run");
    thread_attr_set_detached(&attr);
    error = thread_create(NULL, &attr, test_run, NULL);
    error_check(error, "thread_create");
}


code:
/*
 * Copyright (c) 2016-2017 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/>.
 *
 *
 * The purpose of this test module is to show whether allocating and
 * modifying all available physical pages leads to unexpected problems.
 * In particular, if the early allocation code misbehaves, important
 * data structures such as kernel page tables may be considered free,
 * in which case this test will catch the error.
 */

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#include <kern/cpumap.h>
#include <kern/error.h>
#include <kern/init.h>
#include <kern/list.h>
#include <kern/thread.h>
#include <machine/page.h>
#include <machine/pmap.h>
#include <test/test.h>
#include <vm/vm_kmem.h>
#include <vm/vm_map.h>
#include <vm/vm_page.h>

static struct list test_pages;
static struct cpumap test_cpumap;

static unsigned char test_pattern = 1;

static void
test_write_pages(void)
{
    struct vm_map *kernel_map;
    struct pmap *kernel_pmap;
    struct vm_page *page;
    int error, flags;
    uintptr_t va;

    kernel_map = vm_map_get_kernel_map();
    kernel_pmap = pmap_get_kernel_pmap();

    for (;;) {
        page = vm_page_alloc(0, VM_PAGE_SEL_HIGHMEM, VM_PAGE_KERNEL);

        if (page == NULL) {
            break;
        }

        va = 0;
        flags = VM_MAP_FLAGS(VM_PROT_ALL, VM_PROT_ALL, VM_INHERIT_NONE,
                             VM_ADV_DEFAULT, 0);
        error = vm_map_enter(kernel_map, &va, PAGE_SIZE, 0, flags, NULL, 0);
        error_check(error, __func__);
        error = pmap_enter(kernel_pmap, va, vm_page_to_pa(page),
                           VM_PROT_READ | VM_PROT_WRITE, 0);
        error_check(error, __func__);
        error = pmap_update(kernel_pmap);
        error_check(error, __func__);
        memset((void *)va, test_pattern, PAGE_SIZE);
        error = pmap_remove(kernel_pmap, va, &test_cpumap);
        error_check(error, __func__);
        error = pmap_update(kernel_pmap);
        error_check(error, __func__);
        vm_map_remove(kernel_map, va, va + PAGE_SIZE);

        list_insert_tail(&test_pages, &page->node);
    }
}

static void
test_reset_pages(void)
{
    struct vm_map *kernel_map;
    struct pmap *kernel_pmap;
    struct vm_page *page;
    int error, flags;
    uintptr_t va;

    kernel_map = vm_map_get_kernel_map();
    kernel_pmap = pmap_get_kernel_pmap();

    while (!list_empty(&test_pages)) {
        page = list_first_entry(&test_pages, struct vm_page, node);
        list_remove(&page->node);

        va = 0;
        flags = VM_MAP_FLAGS(VM_PROT_ALL, VM_PROT_ALL, VM_INHERIT_NONE,
                             VM_ADV_DEFAULT, 0);
        error = vm_map_enter(kernel_map, &va, PAGE_SIZE, 0, flags, NULL, 0);
        error_check(error, __func__);
        error = pmap_enter(kernel_pmap, va, vm_page_to_pa(page),
                           VM_PROT_READ | VM_PROT_WRITE, 0);
        error_check(error, __func__);
        error = pmap_update(kernel_pmap);
        error_check(error, __func__);
        memset((void *)va, 0, PAGE_SIZE);
        error = pmap_remove(kernel_pmap, va, &test_cpumap);
        error_check(error, __func__);
        error = pmap_update(kernel_pmap);
        error_check(error, __func__);
        vm_map_remove(kernel_map, va, va + PAGE_SIZE);

        vm_page_free(page, 0);
    }
}

static void
test_run(void *arg)
{
    unsigned int i;

    (void)arg;

    for (i = 0; /* no condition */; i++) {
        printf("test: pass:%u pattern:%hhx\n", i, test_pattern);
        test_write_pages();
        test_reset_pages();
        test_pattern++;
    }
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    struct thread *thread;
    int error;

    list_init(&test_pages);
    cpumap_zero(&test_cpumap);
    cpumap_set(&test_cpumap, cpu_id());

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run");
    thread_attr_set_detached(&attr);
    thread_attr_set_cpumap(&attr, &test_cpumap);
    error = thread_create(&thread, &attr, test_run, NULL);
    error_check(error, "thread_create");
}


code:
/*
 * 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 creates a thread that tests cross-calls for all combinations
 * of processors. This thread sequentially creates other threads that are
 * bound to a single processor, and perform cross-calls to all processors,
 * including the local one.
 */

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

#include <kern/cpumap.h>
#include <kern/error.h>
#include <kern/init.h>
#include <kern/log.h>
#include <kern/panic.h>
#include <kern/thread.h>
#include <kern/xcall.h>
#include <test/test.h>

struct test_data {
    unsigned int cpu;
    bool done;
};

static void
test_fn(void *arg)
{
    struct test_data *data;

    assert(thread_interrupted());

    data = arg;

    if (data->cpu != cpu_id()) {
        panic("test: invalid cpu");
    }

    log_info("function called, running on cpu%u\n", cpu_id());
    data->done = true;
}

static void
test_once(unsigned int cpu)
{
    struct test_data data;

    data.cpu = cpu;
    data.done = false;

    log_info("cross-call: cpu%u -> cpu%u:\n", cpu_id(), cpu);
    xcall_call(test_fn, &data, cpu);

    if (!data.done) {
        panic("test: xcall failed");
    }
}

static void
test_run_cpu(void *arg)
{
    (void)arg;

    for (unsigned int i = (cpu_count() - 1); i < cpu_count(); i--) {
        test_once(i);
    }
}

static void
test_run(void *arg)
{
    char name[THREAD_NAME_SIZE];
    struct thread_attr attr;
    struct thread *thread;
    struct cpumap *cpumap;
    unsigned int cpu;
    int error;

    (void)arg;

    error = cpumap_create(&cpumap);
    error_check(error, "cpumap_create");

    for (unsigned int i = 0; i < cpu_count(); i++) {
        /*
         * Send IPIs from CPU 1 first, in order to better trigger any
         * initialization race that may prevent correct IPI transmission.
         * This assumes CPUs are initialized sequentially, and that CPU 1
         * may have finished initialization much earlier than the last CPU.
         * CPU 0 isn't used since it's the one normally initializing remote
         * CPUs.
         */
        cpu = (1 + i) % cpu_count();

        cpumap_zero(cpumap);
        cpumap_set(cpumap, cpu);
        snprintf(name, sizeof(name), THREAD_KERNEL_PREFIX "test_run/%u", cpu);
        thread_attr_init(&attr, name);
        thread_attr_set_cpumap(&attr, cpumap);
        error = thread_create(&thread, &attr, test_run_cpu, NULL);
        error_check(error, "thread_create");
        thread_join(thread);
    }

    cpumap_destroy(cpumap);

    log_info("done\n");
}

void __init
test_setup(void)
{
    struct thread_attr attr;
    struct thread *thread;
    int error;

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "test_run");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, test_run, NULL);
    error_check(error, "thread_create");
}


code:
#!/usr/bin/env python3
'''
Configuration builder.

Generate a large number of valid configurations, build them concurrently,
and report.
'''

import argparse
import itertools
import multiprocessing
import os
import re
import shutil
import subprocess
import sys
import tempfile
import pathlib

def quote_if_needed(value):
    if not value.isdigit() and value != 'y' and value != 'n':
        value = '"%s"' % value

    return value

def gen_configs_list(options_dict):
    'Generate a list of all possible combinations of options.'
    names = options_dict.keys()
    product = itertools.product(*options_dict.values())
    return [dict(zip(names, x)) for x in product]

def gen_configs_values_str(options_dict):
    'Generate a list of all possible combinations of options as strings.'
    return [' '.join(x.values()) for x in gen_configs_list(options_dict)]

def gen_cc_options_list(options_dict):
    '''
    Does the same as gen_configs_values_str() but adds the -Werror option
    to all generated strings.
    '''
    return ['{} -Werror'.format(x) for x in gen_configs_values_str(options_dict)]

def gen_exclusive_boolean_filter(args):
    enabled_option, options_list = args
    option_filter = dict()

    for option in options_list:
        if option == enabled_option:
            value = [True, 'y']
        else:
            value = [True, 'n']

        option_filter.update({option: value})

    return option_filter

def gen_exclusive_boolean_filters_list(options_list, all_disabled=False):
    '''
    Generate a list of passing filters on a list of boolean options.

    The resulting filters match configurations that have only one of the given
    options enabled, unless all_disabled is true, in which case an additional
    filter is generated to match configurations where none of the options
    are enabled.
    '''
    option_and_options = [(x, options_list) for x in options_list]

    if all_disabled:
        option_and_options.append((None, options_list))

    return list(map(gen_exclusive_boolean_filter, option_and_options))

# Dictionary of compiler options.
#
# Each entry describes a single compiler option. The key is mostly ignored
# and serves as description, but must be present in order to reuse the
# gen_configs_list() function. The value is a list of all values that may
# be used for this compiler option when building a configuration.
all_cc_options_dict = {
    'O'             : ['-O0', '-O2', '-Os'],
    'LTO'           : ['-flto', '-fno-lto'],
    'SSP'           : ['-fno-stack-protector', '-fstack-protector'],
}

# Dictionaries of options.
#
# Each entry describes a single option. The key matches an option name
# whereas the value is a list of all values that may be used for this
# option when building a configuration.

small_options_dict = {
    'CONFIG_CC_EXE'                 : ['gcc', 'clang'],
    'CONFIG_64BITS'                 : ['y', 'n'],
    'CONFIG_CC_OPTIONS'             : gen_cc_options_list(all_cc_options_dict),
    'CONFIG_SMP'                    : ['y', 'n'],
    'CONFIG_MAX_CPUS'               : ['1', '128'],
    'CONFIG_ASSERT'                 : ['y', 'n'],
}

large_options_dict = dict(small_options_dict)
large_options_dict.update({
    'CONFIG_X86_PAE'                : ['y', 'n'],
    'CONFIG_MUTEX_ADAPTIVE'         : ['y', 'n'],
    'CONFIG_MUTEX_PI'               : ['y', 'n'],
    'CONFIG_MUTEX_PLAIN'            : ['y', 'n'],
    'CONFIG_SHELL'                  : ['y', 'n'],
    'CONFIG_THREAD_STACK_GUARD'     : ['y', 'n'],
})

def gen_test_module_option(path):
    name = path.name
    root, ext = os.path.splitext(name)
    return 'CONFIG_' + root.upper()

test_path = pathlib.Path('test')
test_list = [gen_test_module_option(p) for p in test_path.glob('test_*.c')]

test_options_dict = dict(small_options_dict)

for test in test_list:
    test_options_dict.update({test: ['y', 'n']})

all_options_sets = {
    'small'     : small_options_dict,
    'large'     : large_options_dict,
    'test'      : test_options_dict,
}

# Filters.
#
# A filter is a list of dictionaries of options. For each dictionary, the
# key matches an option name whereas the value is a
# [match_flag, string/regular expression] list. The match flag is true if
# the matching expression must match, false otherwise.
#
# Passing filters are used to allow configurations that match the filters,
# whereras blocking filters allow configurations that do not match.

passing_filters_list = gen_exclusive_boolean_filters_list([
    'CONFIG_MUTEX_ADAPTIVE',
    'CONFIG_MUTEX_PI',
    'CONFIG_MUTEX_PLAIN',
])
passing_filters_list += gen_exclusive_boolean_filters_list(test_list,
                                                           all_disabled=True)

blocking_filters_list = [
    # XXX Clang currently cannot build the kernel with LTO.
    {
        'CONFIG_CC_EXE'         :   [True, 'clang'],
        'CONFIG_CC_OPTIONS'     :   [True, re.compile('-flto')],
    },
    {
        'CONFIG_SMP'            :   [True, 'y'],
        'CONFIG_MAX_CPUS'       :   [True, '1'],
    },
    {
        'CONFIG_SMP'            :   [True, 'n'],
        'CONFIG_MAX_CPUS'       :   [False, '1'],
    },
    {
        'CONFIG_64BITS'         :   [True, 'y'],
        'CONFIG_X86_PAE'        :   [True, 'y'],
    },
]

def gen_config_line(config_entry):
    name, value = config_entry
    return '%s=%s\n' % (name, quote_if_needed(value))

def gen_config_content(config_dict):
    return map(gen_config_line, config_dict.items())

def test_config_run(command, check, buildlog):
    buildlog.writelines(['$ %s\n' % command])
    buildlog.flush()

    if check:
        return subprocess.check_call(command.split(), stdout=buildlog,
                                     stderr=subprocess.STDOUT)
    else:
        return subprocess.call(command.split(), stdout=buildlog,
                               stderr=subprocess.STDOUT)

def test_config(args):
    'This function is run in multiprocessing.Pool workers.'
    topbuilddir, config_dict = args
    srctree = os.path.abspath(os.getcwd())
    buildtree = tempfile.mkdtemp(dir=topbuilddir)
    os.chdir(buildtree)
    buildlog = open('build.log', 'w')
    config_file = open('.testconfig', 'w')
    config_file.writelines(gen_config_content(config_dict))
    config_file.close()

    try:
        test_config_run('%s/tools/kconfig/merge_config.sh'
                        ' -m -f %s/Makefile .testconfig' % (srctree, srctree),
                        True, buildlog)
        test_config_run('make -f %s/Makefile V=1 olddefconfig' % srctree,
                        True, buildlog)
        retval = test_config_run('make -f %s/Makefile V=1 x15' % srctree,
                                 False, buildlog)
    except KeyboardInterrupt:
        buildlog.close()
        return
    except:
        retval = 1

    buildlog.close()
    os.chdir(srctree)

    if retval == 0:
        shutil.rmtree(buildtree)

    return [retval, buildtree]

def check_filter(config_dict, filter_dict):
    'Return true if a filter completely matches a configuration.'
    for name, value in filter_dict.items():
        if name not in config_dict:
            return False

        if isinstance(value[1], str):
            if value[0] != (config_dict[name] == value[1]):
                return False
        else:
            if value[0] != bool(value[1].search(config_dict[name])):
                return False

    return True

def check_filter_relevant(config_dict, filter_dict):
    for name in filter_dict.keys():
        if name in config_dict:
            return True

    return False

def check_filters_list_relevant(config_dict, filters_list):
    for filter_dict in filters_list:
        if check_filter_relevant(config_dict, filter_dict):
            return True

    return False

def check_passing_filters(args):
    '''
    If the given filters list is irrelevant, i.e. it applies to none of
    the options in the given configuration, the filters are considered
    to match.

    @return true if a configuration doesn't pass any given filter.
    '''
    config_dict, filters_list = args

    if not check_filters_list_relevant(config_dict, filters_list):
        return True

    for filter_dict in filters_list:
        if check_filter(config_dict, filter_dict):
            return True

    return False

def check_blocking_filters(args):
    'Return true if a configuration passes all the given filters.'
    config_dict, filters_list = args

    for filter_dict in filters_list:
        if check_filter(config_dict, filter_dict):
            return False

    return True

def filter_configs_list(configs_list, passing_filters, blocking_filters):
    configs_and_filters = [(x, passing_filters) for x in configs_list]
    configs_list = [x[0] for x in filter(check_passing_filters,
                                         configs_and_filters)]
    configs_and_filters = [(x, blocking_filters) for x in configs_list]
    configs_list = [x[0] for x in filter(check_blocking_filters,
                                         configs_and_filters)]
    return configs_list

def find_options_dict(options_sets, name):
    if name not in options_sets:
        return None

    return options_sets[name]

class BuildConfigListSetsAction(argparse.Action):
    def __init__(self, nargs=0, **kwargs):
        if nargs != 0:
            raise ValueError("nargs not allowed")

        super(BuildConfigListSetsAction, self).__init__(nargs=nargs, **kwargs)

    def __call__(self, parser, namespace, values, option_string=None):
        for key in sorted(all_options_sets.keys()):
            print(key)

            for option in sorted(all_options_sets[key]):
                print('  ' + option)

        sys.exit(0)

def main():
    parser = argparse.ArgumentParser(description=__doc__,
                                     formatter_class=argparse.RawDescriptionHelpFormatter)
    parser.add_argument('-s', '--set', default='small',
                        help='select a set of options (default=small)')
    parser.add_argument('-l', '--list-sets', action=BuildConfigListSetsAction,
                        help='print the list of options sets')
    args = parser.parse_args()

    options_dict = find_options_dict(all_options_sets, args.set)

    if not options_dict:
        print('error: invalid set')
        sys.exit(2)

    print('set: {}'.format(args.set))
    configs_list = filter_configs_list(gen_configs_list(options_dict),
                                       passing_filters_list,
                                       blocking_filters_list)
    nr_configs = len(configs_list)
    print('total: {:d}'.format(nr_configs))

    # This tool performs out-of-tree builds and requires a clean source tree
    print('cleaning source tree...')
    subprocess.check_call(['make', 'distclean'])
    topbuilddir = os.path.abspath(tempfile.mkdtemp(prefix='build', dir='.'))
    print('top build directory: {}'.format(topbuilddir))

    pool = multiprocessing.Pool()
    worker_args = [(topbuilddir, x) for x in configs_list]

    try:
        results = pool.map(test_config, worker_args)
    except KeyboardInterrupt:
        pool.terminate()
        pool.join()
        shutil.rmtree(topbuilddir)
        raise

    failures = [x[1] for x in results if x[0] != 0]
    for buildtree in failures:
        print('failed: {0}/.config ({0}/build.log)'.format(buildtree))
    print('passed: {:d}'.format(nr_configs - len(failures)))
    print('failed: {:d}'.format(len(failures)))

    try:
        os.rmdir(topbuilddir)
    finally:
        sys.exit(len(failures) != 0)

if __name__ == '__main__':
    main()


code:
#!/usr/bin/env python3
'''
Embedded symbol table generator.
'''

import sys

symtab = []

for line in sys.stdin:
    line = line.strip()
    parts = line.split(' ')

    if len(parts) != 4 or parts[3].startswith("__func__."):
        continue

    del parts[2]
    sym = {'addr': parts[0], 'size': parts[1], 'name': parts[2]}
    symtab.append(sym)

print("#include <kern/symbol.h>")

for index, sym in enumerate(symtab):
    print("static const char symbol_name_%u[] __symbol_table = \"%s\";" % (index, sym['name']))

print("const struct symbol symbol_table[] __symbol_table = {")

for index, sym in enumerate(symtab):
    print("    { 0x%s, 0x%s, symbol_name_%u }," % (sym['addr'], sym['size'], index))

print("};")
print("const size_t symbol_table_size = %d;" % len(symtab))
print("const struct symbol *symbol_table_ptr = symbol_table;")


code:
#
# Generated files
#
config*
*.lex.c
*.tab.c
*.tab.h
zconf.hash.c
*.moc
gconf.glade.h
*.pot
*.mo

#
# configuration programs
#
conf
mconf
nconf
qconf
gconf
kxgettext


code:
# ===========================================================================
# Kernel configuration targets
# These targets are used from top-level makefile

PHONY += xconfig gconfig menuconfig config

# We need this, in case the user has it in its environment
unexport CONFIG_

ifneq ($(Q),)
# $(call kconfig_action,<action>,<target>)
define kconfig_action
@printf "  %-7s %s\n" $(1) $(2)
@
endef
endif

srctree := $(SRCDIR)
obj := $(KCONFIG_PATH)
src := $(obj)
kecho := echo

# This environment variable is used by the conf tools to locate Kconfig files.
export srctree

Kconfig := $(srctree)/Kconfig

xconfig: $(obj)/qconf
	$< $(Kconfig)

gconfig: $(obj)/gconf
	$< $(Kconfig)

menuconfig: $(obj)/mconf
	$< $(Kconfig)

config: $(obj)/conf
	$< --oldaskconfig $(Kconfig)

nconfig: $(obj)/nconf
	$< $(Kconfig)

# These targets map 1:1 to the commandline options of 'conf'
simple-targets := oldconfig allnoconfig allyesconfig \
	alldefconfig randconfig listnewconfig olddefconfig
PHONY += $(simple-targets)

$(simple-targets): $(obj)/conf
	$< --$@ $(Kconfig)

PHONY += savedefconfig defconfig

savedefconfig: $(obj)/conf
	$< --$@=defconfig $(Kconfig)

defconfig: $(obj)/conf
	@$(kecho) "*** Default configuration is based on '$(KCONFIG_DEFCONFIG)'"
	$(Q)$< --defconfig=arch/$(ARCH)/configs/$(KCONFIG_DEFCONFIG) $(Kconfig)

%_defconfig: $(obj)/conf
	$(Q)$< --defconfig=arch/$(ARCH)/configs/$@ $(Kconfig)

# Help text used by make help
help:
	@echo  '  config                   - Set configuration - line-oriented program'
	@echo  '  nconfig                  - Set configuration - ncurses menu based program'
	@echo  '  menuconfig               - Set configuration - menu based program'
	@echo  '  xconfig                  - Set configuration - Qt based front-end'
	@echo  '  gconfig                  - Set configuration - GTK+ based front-end'
	@echo  '  allnoconfig              - New configuration - all options disabled'
	@echo  '  allyesconfig             - New configuration - all options enabled'
	@echo  '  alldefconfig             - New configuration - default values'
	@echo  '  randconfig               - New configuration - random values'
	@echo  '  oldconfig                - Reuse existing .config for configuration'
	@echo  '  olddefconfig             - Same as oldconfig but sets new symbols to their'
	@echo  '                             default value'
	@echo  '  defconfig                - Default architecture-specific configuration'
	@echo  '  savedefconfig            - Save configuration as ./defconfig (minimal config)'
	@echo  '  listnewconfig            - List new options'

# lxdialog stuff
check-lxdialog  := $(srctree)/$(src)/lxdialog/check-lxdialog.sh

# Use recursively expanded variables so we do not call gcc unless
# we really need to do so. (Do not call gcc as part of make mrproper)
HOST_EXTRACFLAGS += $(shell $(CONFIG_HOST_SHELL) $(check-lxdialog) -ccflags) \
                    -DLOCALE

# ===========================================================================
# Shared Makefile for the various kconfig executables:
# conf:	  Used for defconfig, oldconfig and related targets
# nconf:  Used for the nconfig target.
#         Utilizes ncurses
# mconf:  Used for the menuconfig target
#         Utilizes the lxdialog package
# qconf:  Used for the xconfig target
#         Based on Qt which needs to be installed to compile it
# gconf:  Used for the gconfig target
#         Based on GTK+ which needs to be installed to compile it
# object files used by all kconfig flavours

lxdialog := lxdialog/checklist.o lxdialog/util.o lxdialog/inputbox.o
lxdialog += lxdialog/textbox.o lxdialog/yesno.o lxdialog/menubox.o

conf-objs	:= conf.o  zconf.tab.o
mconf-objs     := mconf.o zconf.tab.o $(lxdialog)
nconf-objs     := nconf.o zconf.tab.o nconf.gui.o
qconf-cxxobjs	:= qconf.o
qconf-objs	:= zconf.tab.o
gconf-objs	:= gconf.o zconf.tab.o

hostprogs-y := conf

ifeq ($(MAKECMDGOALS),nconfig)
	hostprogs-y += nconf
endif

ifeq ($(MAKECMDGOALS),menuconfig)
	hostprogs-y += mconf
endif

ifeq ($(MAKECMDGOALS),xconfig)
	qconf-target := 1
endif
ifeq ($(MAKECMDGOALS),gconfig)
	gconf-target := 1
endif

ifeq ($(qconf-target),1)
	hostprogs-y += qconf
endif

ifeq ($(gconf-target),1)
	hostprogs-y += gconf
endif

clean-files	:= qconf.moc .tmp_qtcheck .tmp_gtkcheck
clean-files	+= zconf.tab.c zconf.lex.c zconf.hash.c gconf.glade.h
clean-files     += config.pot linux.pot

# Check that we have the required ncurses stuff installed for lxdialog (menuconfig)
$(addprefix $(obj)/, mconf.o $(lxdialog)): $(obj)/.dochecklxdialog
$(obj)/.dochecklxdialog:
	$(Q)$(CONFIG_HOST_SHELL) $(check-lxdialog) -check $(HOSTCC) $(HOST_EXTRACFLAGS) $(HOSTLOADLIBES_mconf)
	$(Q)touch $@

# Add environment specific flags
HOST_EXTRACFLAGS += $(shell $(CONFIG_HOST_SHELL) $(srctree)/$(src)/check.sh $(HOSTCC) $(HOSTCFLAGS))

# generated files seem to need this to find local include files
HOSTCFLAGS_zconf.lex.o	:= -I$(srctree)/$(src)
HOSTCFLAGS_zconf.tab.o	:= -I$(srctree)/$(src)

LEX_PREFIX_zconf	:= zconf
YACC_PREFIX_zconf	:= zconf

HOSTLOADLIBES_qconf	= $(KC_QT_LIBS)
HOSTCXXFLAGS_qconf.o	= $(KC_QT_CFLAGS)

HOSTLOADLIBES_gconf	= `pkg-config --libs gtk+-2.0 gmodule-2.0 libglade-2.0`
HOSTCFLAGS_gconf.o	= `pkg-config --cflags gtk+-2.0 gmodule-2.0 libglade-2.0` \
                          -Wno-missing-prototypes

HOSTLOADLIBES_mconf   = $(shell $(CONFIG_HOST_SHELL) $(check-lxdialog) -ldflags $(HOSTCC))

HOSTLOADLIBES_nconf	= $(shell \
				pkg-config --libs menuw panelw ncursesw 2>/dev/null \
				|| pkg-config --libs menu panel ncurses 2>/dev/null \
				|| echo "-lmenu -lpanel -lncurses"  )
$(obj)/qconf.o: $(obj)/.tmp_qtcheck

ifeq ($(MAKECMDGOALS),xconfig)
$(obj)/.tmp_qtcheck: $(src)/Makefile
-include $(obj)/.tmp_qtcheck

# Qt needs some extra effort...
$(obj)/.tmp_qtcheck:
	@set -e; $(kecho) "  CHECK   qt"; \
	if pkg-config --exists Qt5Core; then \
	    cflags="-std=c++11 -fPIC `pkg-config --cflags Qt5Core Qt5Gui Qt5Widgets`"; \
	    libs=`pkg-config --libs Qt5Core Qt5Gui Qt5Widgets`; \
	    moc=`pkg-config --variable=host_bins Qt5Core`/moc; \
	elif pkg-config --exists QtCore; then \
	    cflags=`pkg-config --cflags QtCore QtGui`; \
	    libs=`pkg-config --libs QtCore QtGui`; \
	    moc=`pkg-config --variable=moc_location QtCore`; \
	else \
	    echo >&2 "*"; \
	    echo >&2 "* Could not find Qt via pkg-config."; \
	    echo >&2 "* Please install either Qt 4.8 or 5.x. and make sure it's in PKG_CONFIG_PATH"; \
	    echo >&2 "*"; \
	    exit 1; \
	fi; \
	echo "KC_QT_CFLAGS=$$cflags" > $@; \
	echo "KC_QT_LIBS=$$libs" >> $@; \
	echo "KC_QT_MOC=$$moc" >> $@
endif

$(obj)/gconf.o: $(obj)/.tmp_gtkcheck

ifeq ($(MAKECMDGOALS),gconfig)
-include $(obj)/.tmp_gtkcheck

# GTK+ needs some extra effort, too...
$(obj)/.tmp_gtkcheck:
	@if `pkg-config --exists gtk+-2.0 gmodule-2.0 libglade-2.0`; then		\
		if `pkg-config --atleast-version=2.0.0 gtk+-2.0`; then			\
			touch $@;								\
		else									\
			echo >&2 "*"; 							\
			echo >&2 "* GTK+ is present but version >= 2.0.0 is required.";	\
			echo >&2 "*";							\
			false;								\
		fi									\
	else										\
		echo >&2 "*"; 								\
		echo >&2 "* Unable to find the GTK+ installation. Please make sure that"; 	\
		echo >&2 "* the GTK+ 2.0 development package is correctly installed..."; 	\
		echo >&2 "* You need gtk+-2.0, glib-2.0 and libglade-2.0."; 		\
		echo >&2 "*"; 								\
		false;									\
	fi
endif

$(obj)/zconf.tab.o: $(obj)/zconf.lex.c $(obj)/zconf.hash.c

$(obj)/qconf.o: $(obj)/qconf.moc

$(obj)/%.moc: $(src)/%.h $(obj)/.tmp_qtcheck
	$(call kconfig_action,MOC,$@,)$(KC_QT_MOC) -i $< -o $@

# Extract gconf menu items for i18n support
$(obj)/gconf.glade.h: $(obj)/gconf.glade
	$(Q)intltool-extract --type=gettext/glade --srcdir=$(srctree) \
	$(obj)/gconf.glade

-include $(obj)/.depend
$(obj)/.depend: $(wildcard *.h *.c)
	$(Q)mkdir -p $(@D)
	$(Q)$(HOSTCC) $(HOST_EXTRACFLAGS) $(HOSTCFLAGS) -MM *.c > $@ 2>/dev/null || :

__hostprogs := $(sort $(hostprogs-y) $(hostprogs-m))
host-csingle := $(addprefix $(obj)/,$(foreach m,$(__hostprogs),$(if $($(m)-objs),,$(m))))
host-cmulti := $(addprefix $(obj)/,$(foreach m,$(__hostprogs),\
           $(if $($(m)-cxxobjs),,$(if $($(m)-objs),$(m)))))
host-cxxmulti := $(addprefix $(obj)/,$(foreach m,$(__hostprogs),\
           $(if $($(m)-cxxobjs),$(m),$(if $($(m)-objs),))))
host-cobjs := $(addprefix $(obj)/,$(sort $(foreach m,$(__hostprogs),$($(m)-objs))))
host-cxxobjs := $(addprefix $(obj)/,$(sort $(foreach m,$(__hostprogs),$($(m)-cxxobjs))))

HOST_EXTRACFLAGS += -I$(obj)

$(host-csingle): %: %.c
	$(Q)mkdir -p $(@D)
	$(call kconfig_action,CC,$@)$(HOSTCC) $(HOST_EXTRACFLAGS) $(HOSTCFLAGS) $(HOSTCFLAGS_$(@F)) $< -o $@

$(host-cmulti): %: $(host-cobjs) $(host-cshlib)
	$(Q)mkdir -p $(@D)
	$(call kconfig_action,CC,$@)$(HOSTCC) $(HOST_EXTRACFLAGS) $(HOSTCFLAGS) $(HOSTCFLAGS_$(@F)) $(addprefix $(obj)/,$($(@F)-objs)) $(HOSTLOADLIBES_$(@F)) -o $@

$(host-cxxmulti): %: $(host-cxxobjs) $(host-cobjs) $(host-cshlib)
	$(Q)mkdir -p $(@D)
	$(call kconfig_action,CXX,$@)$(HOSTCXX) $(HOST_EXTRACFLAGS) $(HOSTCFLAGS) $(HOSTCXXFLAGS_$(@F)) $(addprefix $(obj)/,$($(@F)-objs) $($(@F)-cxxobjs)) $(HOSTLOADLIBES_$(@F)) -o $@

$(obj)/%.o: $(obj)/%.c
	$(Q)mkdir -p $(@D)
	$(call kconfig_action,CC,$@)$(HOSTCC) $(HOST_EXTRACFLAGS) $(HOSTCFLAGS) $(HOSTCFLAGS_$(@F)) -c $< -o $@

$(obj)/%.o: $(obj)/%.cc
	$(Q)mkdir -p $(@D)
	$(call kconfig_action,CC,$@)$(HOSTCC) $(HOST_EXTRACFLAGS) $(HOSTCFLAGS) $(HOSTCXXFLAGS_$(@F)) -c $< -o $@

$(obj)/%:: $(src)/%_shipped
	$(Q)mkdir -p $(@D)
	$(Q)cat $< > $@

clean:
	$(Q)rm -f $(addprefix $(obj)/,$(clean-files))

distclean: clean
	$(Q)rm -f $(addprefix $(obj)/,$(lxdialog) $(conf-objs) $(mconf-objs) \
		$(qconf-cxxobjs) $(qconf-objs) $(gconf-objs) \
		conf nconf mconf qconf gconf .depend .dochecklxdialog)

.PHONY: clean distclean $(PHONY)

path: tools/kconfig/Makefile


code:
scripts/kconfig/lxdialog/checklist.c
scripts/kconfig/lxdialog/inputbox.c
scripts/kconfig/lxdialog/menubox.c
scripts/kconfig/lxdialog/textbox.c
scripts/kconfig/lxdialog/util.c
scripts/kconfig/lxdialog/yesno.c
scripts/kconfig/mconf.c
scripts/kconfig/conf.c
scripts/kconfig/confdata.c
scripts/kconfig/gconf.c
scripts/kconfig/gconf.glade.h
scripts/kconfig/qconf.cc


code:
#!/bin/sh
# Needed for systems without gettext
$* -x c -o /dev/null - > /dev/null 2>&1 << EOF
#include <libintl.h>
int main()
{
	gettext("");
	return 0;
}
EOF
if [ ! "$?" -eq "0"  ]; then
	echo -DKBUILD_NO_NLS;
fi