code:
/*
 * Copyright (c) 2009-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/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 *
 *
 * Doubly-linked list.
 */

#ifndef KERN_LIST_H
#define KERN_LIST_H

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

#include <kern/list_types.h>
#include <kern/macros.h>
#include <kern/rcu.h>

/*
 * Structure used as both head and node.
 *
 * This implementation relies on using the same type for both heads and nodes.
 *
 * It is recommended to encode the use of struct list variables in their names,
 * e.g. struct list free_list or struct list free_objects is a good hint for a
 * list of free objects. A declaration like struct list free_node clearly
 * indicates it is used as part of a node in the free list.
 */
struct list;

/*
 * Static list initializer.
 */
#define LIST_INITIALIZER(list) { &(list), &(list) }

/*
 * Initialize a list.
 */
static inline void
list_init(struct list *list)
{
    list->prev = list;
    list->next = list;
}

/*
 * Initialize a list node.
 *
 * A node is in no list when its node members point to NULL.
 */
static inline void
list_node_init(struct list *node)
{
    node->prev = NULL;
    node->next = NULL;
}

/*
 * Return true if node is in no list.
 */
static inline bool
list_node_unlinked(const struct list *node)
{
    return node->prev == NULL;
}

/*
 * Return the first node of a list.
 */
static inline struct list *
list_first(const struct list *list)
{
    return list->next;
}

/*
 * Return the last node of a list.
 */
static inline struct list *
list_last(const struct list *list)
{
    return list->prev;
}

/*
 * Return the node next to the given node.
 */
static inline struct list *
list_next(const struct list *node)
{
    return node->next;
}

/*
 * Return the node previous to the given node.
 */
static inline struct list *
list_prev(const struct list *node)
{
    return node->prev;
}

/*
 * Return true if node is invalid and denotes one of the ends of the list.
 */
static inline bool
list_end(const struct list *list, const struct list *node)
{
    return list == node;
}

/*
 * Return true if list is empty.
 */
static inline bool
list_empty(const struct list *list)
{
    return list == list->next;
}

/*
 * Return true if list contains exactly one node.
 */
static inline bool
list_singular(const struct list *list)
{
    return !list_empty(list) && (list->next == list->prev);
}

/*
 * Split list2 by moving its nodes up to, but not including, the given
 * node into list1, which can be in a stale state.
 *
 * If list2 is empty, or node is list2 or list2->next, list1 is merely
 * initialized.
 */
static inline void
list_split(struct list *list1, struct list *list2, struct list *node)
{
    if (list_empty(list2) || (list2->next == node) || list_end(list2, node)) {
        list_init(list1);
        return;
    }

    list1->next = list2->next;
    list1->next->prev = list1;

    list1->prev = node->prev;
    node->prev->next = list1;

    list2->next = node;
    node->prev = list2;
}

/*
 * Append the nodes of list2 at the end of list1.
 *
 * After completion, list2 is stale.
 */
static inline void
list_concat(struct list *list1, const struct list *list2)
{
    struct list *last1, *first2, *last2;

    if (list_empty(list2)) {
        return;
    }

    last1 = list1->prev;
    first2 = list2->next;
    last2 = list2->prev;

    last1->next = first2;
    first2->prev = last1;

    last2->next = list1;
    list1->prev = last2;
}

/*
 * Set the new head of a list.
 *
 * This function is an optimized version of :
 * list_init(&new_list);
 * list_concat(&new_list, &old_list);
 *
 * After completion, old_head is stale.
 */
static inline void
list_set_head(struct list *new_head, const struct list *old_head)
{
    if (list_empty(old_head)) {
        list_init(new_head);
        return;
    }

    *new_head = *old_head;
    new_head->next->prev = new_head;
    new_head->prev->next = new_head;
}

/*
 * Add a node between two nodes.
 *
 * This function is private.
 */
static inline void
list_add(struct list *prev, struct list *next, struct list *node)
{
    next->prev = node;
    node->next = next;

    prev->next = node;
    node->prev = prev;
}

/*
 * Insert a node at the head of a list.
 */
static inline void
list_insert_head(struct list *list, struct list *node)
{
    list_add(list, list->next, node);
}

/*
 * Insert a node at the tail of a list.
 */
static inline void
list_insert_tail(struct list *list, struct list *node)
{
    list_add(list->prev, list, node);
}

/*
 * Insert a node before another node.
 */
static inline void
list_insert_before(struct list *node, struct list *next)
{
    list_add(next->prev, next, node);
}

/*
 * Insert a node after another node.
 */
static inline void
list_insert_after(struct list *node, struct list *prev)
{
    list_add(prev, prev->next, node);
}

/*
 * Remove a node from a list.
 *
 * After completion, the node is stale.
 */
static inline void
list_remove(struct list *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

/*
 * Macro that evaluates to the address of the structure containing the
 * given node based on the given type and member.
 */
#define list_entry(node, type, member) structof(node, type, member)

/*
 * Get the first entry of a list.
 */
#define list_first_entry(list, type, member) \
    list_entry(list_first(list), type, member)

/*
 * Get the last entry of a list.
 */
#define list_last_entry(list, type, member) \
    list_entry(list_last(list), type, member)

/*
 * Get the entry next to the given entry.
 */
#define list_next_entry(entry, member) \
    list_entry(list_next(&(entry)->member), typeof(*(entry)), member)

/*
 * Get the entry previous to the given entry.
 */
#define list_prev_entry(entry, member) \
    list_entry(list_prev(&(entry)->member), typeof(*(entry)), member)

/*
 * Forge a loop to process all nodes of a list.
 *
 * The node must not be altered during the loop.
 */
#define list_for_each(list, node)   \
for (node = list_first(list);       \
     !list_end(list, node);         \
     node = list_next(node))

/*
 * Forge a loop to process all nodes of a list.
 */
#define list_for_each_safe(list, node, tmp)             \
for (node = list_first(list), tmp = list_next(node);    \
     !list_end(list, node);                             \
     node = tmp, tmp = list_next(node))

/*
 * Version of list_for_each() that processes nodes backward.
 */
#define list_for_each_reverse(list, node)   \
for (node = list_last(list);                \
     !list_end(list, node);                 \
     node = list_prev(node))

/*
 * Version of list_for_each_safe() that processes nodes backward.
 */
#define list_for_each_reverse_safe(list, node, tmp) \
for (node = list_last(list), tmp = list_prev(node); \
     !list_end(list, node);                         \
     node = tmp, tmp = list_prev(node))

/*
 * Forge a loop to process all entries of a list.
 *
 * The entry node must not be altered during the loop.
 */
#define list_for_each_entry(list, entry, member)                    \
for (entry = list_first_entry(list, typeof(*entry), member);        \
     !list_end(list, &entry->member);                               \
     entry = list_next_entry(entry, member))

/*
 * Forge a loop to process all entries of a list.
 */
#define list_for_each_entry_safe(list, entry, tmp, member)          \
for (entry = list_first_entry(list, typeof(*entry), member),        \
       tmp = list_next_entry(entry, member);                        \
     !list_end(list, &entry->member);                               \
     entry = tmp, tmp = list_next_entry(entry, member))

/*
 * Version of list_for_each_entry() that processes entries backward.
 */
#define list_for_each_entry_reverse(list, entry, member)            \
for (entry = list_last_entry(list, typeof(*entry), member);         \
     !list_end(list, &entry->member);                               \
     entry = list_prev_entry(entry, member))

/*
 * Version of list_for_each_entry_safe() that processes entries backward.
 */
#define list_for_each_entry_reverse_safe(list, entry, tmp, member)  \
for (entry = list_last_entry(list, typeof(*entry), member),         \
       tmp = list_prev_entry(entry, member);                        \
     !list_end(list, &entry->member);                               \
     entry = tmp, tmp = list_prev_entry(entry, member))

/*
 * Lockless variants
 *
 * This is a subset of the main interface that only supports forward traversal.
 * In addition, list_end() is also allowed in read-side critical sections.
 */

/*
 * Return the first node of a list.
 */
static inline struct list *
list_rcu_first(const struct list *list)
{
    return rcu_load_ptr(list->next);
}

/*
 * Return the node next to the given node.
 */
static inline struct list *
list_rcu_next(const struct list *node)
{
    return rcu_load_ptr(node->next);
}

/*
 * Add a node between two nodes.
 *
 * This function is private.
 */
static inline void
list_rcu_add(struct list *prev, struct list *next, struct list *node)
{
    node->next = next;
    node->prev = prev;
    rcu_store_ptr(prev->next, node);
    next->prev = node;
}

/*
 * Insert a node at the head of a list.
 */
static inline void
list_rcu_insert_head(struct list *list, struct list *node)
{
    list_rcu_add(list, list->next, node);
}

/*
 * Insert a node at the tail of a list.
 */
static inline void
list_rcu_insert_tail(struct list *list, struct list *node)
{
    list_rcu_add(list->prev, list, node);
}

/*
 * Insert a node before another node.
 */
static inline void
list_rcu_insert_before(struct list *node, struct list *next)
{
    list_rcu_add(next->prev, next, node);
}

/*
 * Insert a node after another node.
 */
static inline void
list_rcu_insert_after(struct list *node, struct list *prev)
{
    list_rcu_add(prev, prev->next, node);
}

/*
 * Remove a node from a list.
 *
 * After completion, the node is stale.
 */
static inline void
list_rcu_remove(struct list *node)
{
    node->next->prev = node->prev;
    rcu_store_ptr(node->prev->next, node->next);
}

/*
 * Macro that evaluates to the address of the structure containing the
 * given node based on the given type and member.
 */
#define list_rcu_entry(node, type, member) \
    structof(rcu_load_ptr(node), type, member)

/*
 * Get the first entry of a list.
 *
 * Unlike list_first_entry(), this macro may evaluate to NULL, because
 * the node pointer can only be read once, preventing the combination
 * of lockless list_empty()/list_first_entry() variants.
 */
#define list_rcu_first_entry(head, type, member)            \
MACRO_BEGIN                                                 \
    struct list *list_;                                     \
    struct list *first_;                                    \
                                                            \
    list_ = (head);                                         \
    first_ = list_rcu_first(list_);                         \
    list_end(list_, first_)                                 \
        ? NULL                                              \
        : list_entry(first_, type, member);                 \
MACRO_END

/*
 * Get the entry next to the given entry.
 *
 * Unlike list_next_entry(), this macro may evaluate to NULL, because
 * the node pointer can only be read once, preventing the combination
 * of lockless list_empty()/list_next_entry() variants.
 */
#define list_rcu_next_entry(head, entry, member)            \
MACRO_BEGIN                                                 \
    struct list *list_;                                     \
    struct list *next_;                                     \
                                                            \
    list_ = (head);                                         \
    next_ = list_rcu_next(&entry->member);                  \
    list_end(list_, next_)                                  \
        ? NULL                                              \
        : list_entry(next_, typeof(*entry), member);        \
MACRO_END

/*
 * Forge a loop to process all nodes of a list.
 *
 * The node must not be altered during the loop.
 */
#define list_rcu_for_each(list, node)       \
for (node = list_rcu_first(list);           \
     !list_end(list, node);                 \
     node = list_rcu_next(node))

/*
 * Forge a loop to process all entries of a list.
 *
 * The entry node must not be altered during the loop.
 */
#define list_rcu_for_each_entry(list, entry, member)                \
for (entry = list_rcu_first_entry(list, typeof(*entry), member);    \
     entry != NULL;                                                 \
     entry = list_rcu_next_entry(list, entry, member))

#endif /* KERN_LIST_H */


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/>.
 *
 *
 * Isolated type definition used to avoid inclusion circular dependencies.
 */

#ifndef KERN_LIST_TYPES_H
#define KERN_LIST_TYPES_H

struct list {
    struct list *prev;
    struct list *next;
};

#endif /* KERN_LIST_TYPES_H */

license: mit


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/>.
 */

#include <assert.h>
#include <errno.h>
#include <limits.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

#include <kern/arg.h>
#include <kern/cbuf.h>
#include <kern/init.h>
#include <kern/log.h>
#include <kern/macros.h>
#include <kern/panic.h>
#include <kern/shell.h>
#include <kern/spinlock.h>
#include <kern/thread.h>
#include <machine/boot.h>
#include <machine/cpu.h>

#define LOG_BUFFER_SIZE 16384

#if !ISP2(LOG_BUFFER_SIZE)
#error "log buffer size must be a power-of-two"
#endif

#define LOG_MSG_SIZE 128

#define LOG_MARKER 0x1

static struct thread *log_thread;

static struct cbuf log_cbuf;
static char log_buffer[LOG_BUFFER_SIZE];

/*
 * This index is used by the log thread to report what it has consumed
 * so that producers can detect overruns.
 */
static size_t log_index;

static size_t log_nr_overruns;

static unsigned int log_print_level;

/*
 * Global lock.
 *
 * Interrupts must be disabled when holding this lock.
 */
static struct spinlock log_lock;

/*
 * A record starts with a marker byte and ends with a null terminating byte.
 *
 * There must be no null byte inside the header, and the buffer is expected
 * to be a standard null-terminated string.
 */
struct log_record {
    uint8_t mark;
    uint8_t level;
    char buffer[LOG_MSG_SIZE];
};

/*
 * A consumer context allows faster, buffered reads of the circular buffer,
 * by retaining bytes that weren't consumed in case a read spans multiple
 * records.
 */
struct log_consume_ctx {
    struct cbuf *cbuf;
    size_t cbuf_index;
    char buf[LOG_MSG_SIZE];
    size_t index;
    size_t size;
};

static void
log_consume_ctx_init(struct log_consume_ctx *ctx, struct cbuf *cbuf)
{
    ctx->cbuf = cbuf;
    ctx->cbuf_index = cbuf_start(cbuf);
    ctx->index = 0;
    ctx->size = 0;
}

static size_t
log_consume_ctx_index(const struct log_consume_ctx *ctx)
{
    return ctx->cbuf_index;
}

static void
log_consume_ctx_set_index(struct log_consume_ctx *ctx, size_t index)
{
    ctx->cbuf_index = index;
}

static bool
log_consume_ctx_empty(const struct log_consume_ctx *ctx)
{
    return ctx->cbuf_index == cbuf_end(ctx->cbuf);
}

static int
log_consume_ctx_pop(struct log_consume_ctx *ctx, char *byte)
{
    int error;

    if (ctx->index >= ctx->size) {
        ctx->index = 0;
        ctx->size = sizeof(ctx->buf);
        error = cbuf_read(ctx->cbuf, ctx->cbuf_index, ctx->buf, &ctx->size);

        if (error) {
            ctx->cbuf_index = cbuf_start(ctx->cbuf);
            return error;
        }
    }

    ctx->cbuf_index++;
    *byte = ctx->buf[ctx->index];
    ctx->index++;
    return 0;
}

static const char *
log_level2str(unsigned int level)
{
    switch (level) {
    case LOG_EMERG:
        return "emerg";
    case LOG_ALERT:
        return "alert";
    case LOG_CRIT:
        return "crit";
    case LOG_ERR:
        return "error";
    case LOG_WARNING:
        return "warning";
    case LOG_NOTICE:
        return "notice";
    case LOG_INFO:
        return "info";
    case LOG_DEBUG:
        return "debug";
    default:
        return NULL;
    }
}

static char
log_level2char(unsigned int level)
{
    assert(level < LOG_NR_LEVELS);
    return '0' + level;
}

static uint8_t
log_char2level(char c)
{
    uint8_t level;

    level = c - '0';
    assert(level < LOG_NR_LEVELS);
    return level;
}

static void
log_record_init_produce(struct log_record *record, unsigned int level)
{
    record->mark = LOG_MARKER;
    record->level = log_level2char(level);
}

static void
log_record_consume(struct log_record *record, char c, size_t *sizep)
{
    char *ptr;

    assert(*sizep < sizeof(*record));

    ptr = (char *)record;
    ptr[*sizep] = c;
    (*sizep)++;
}

static int
log_record_init_consume(struct log_record *record, struct log_consume_ctx *ctx)
{
    bool marker_found;
    size_t size;
    int error;
    char c;

    marker_found = false;
    size = 0;

    for (;;) {
        if (log_consume_ctx_empty(ctx)) {
            if (!marker_found) {
                return EINVAL;
            }

            break;
        }

        error = log_consume_ctx_pop(ctx, &c);

        if (error) {
            continue;
        }

        if (!marker_found) {
            if (c != LOG_MARKER) {
                continue;
            }

            marker_found = true;
            log_record_consume(record, c, &size);
            continue;
        } else if (size == offsetof(struct log_record, level)) {
            record->level = log_char2level(c);
            size++;
            continue;
        }

        log_record_consume(record, c, &size);

        if (c == '\0') {
            break;
        }
    }

    return 0;
}

static void
log_record_print(const struct log_record *record, unsigned int level)
{
    if (record->level > level) {
        return;
    }

    if (record->level <= LOG_WARNING) {
        printf("%7s %s\n", log_level2str(record->level), record->buffer);
    } else {
        printf("%s\n", record->buffer);
    }
}

#ifdef CONFIG_SHELL

static void
log_start_shell(unsigned long *flags)
{
    static bool shell_started = false;

    if (shell_started) {
        return;
    }

    spinlock_unlock_intr_restore(&log_lock, *flags);
    shell_start();
    spinlock_lock_intr_save(&log_lock, flags);
    shell_started = true;
}

#else /* CONFIG_SHELL */
#define log_start_shell(flags)
#endif /* CONFIG_SHELL*/

static void
log_run(void *arg)
{
    unsigned long flags, nr_overruns;
    struct log_consume_ctx ctx;
    struct log_record record;
    int error;

    (void)arg;

    nr_overruns = 0;

    spinlock_lock_intr_save(&log_lock, &flags);

    log_consume_ctx_init(&ctx, &log_cbuf);

    for (;;) {
        while (log_consume_ctx_empty(&ctx)) {
            /*
             * Starting the shell after the log thread sleeps for the first
             * time cleanly serializes log messages and shell prompt, making
             * a clean ordered output.
             */
            log_start_shell(&flags);
            log_index = log_consume_ctx_index(&ctx);

            thread_sleep(&log_lock, &log_cbuf, "log_cbuf");

            log_consume_ctx_set_index(&ctx, log_index);
        }

        error = log_record_init_consume(&record, &ctx);

        /* Drain the log buffer before reporting overruns */
        if (log_consume_ctx_empty(&ctx)) {
            nr_overruns = log_nr_overruns;
            log_nr_overruns = 0;
        }

        log_index = log_consume_ctx_index(&ctx);

        spinlock_unlock_intr_restore(&log_lock, flags);

        if (!error) {
            log_record_print(&record, log_print_level);
        }

        if (nr_overruns != 0) {
            log_msg(LOG_ERR, "log: buffer overruns, %lu bytes dropped",
                    nr_overruns);
            nr_overruns = 0;
        }

        spinlock_lock_intr_save(&log_lock, &flags);

        log_consume_ctx_set_index(&ctx, log_index);
    }
}

#ifdef CONFIG_SHELL

static void
log_dump(unsigned int level)
{
    struct log_consume_ctx ctx;
    struct log_record record;
    unsigned long flags;
    int error;

    spinlock_lock_intr_save(&log_lock, &flags);

    log_consume_ctx_init(&ctx, &log_cbuf);

    for (;;) {
        error = log_record_init_consume(&record, &ctx);

        if (error) {
            break;
        }

        spinlock_unlock_intr_restore(&log_lock, flags);

        log_record_print(&record, level);

        spinlock_lock_intr_save(&log_lock, &flags);
    }

    spinlock_unlock_intr_restore(&log_lock, flags);
}

static void
log_shell_dump(struct shell *shell, int argc, char **argv)
{
    unsigned int level;
    int ret;

    (void)shell;

    if (argc != 2) {
        level = log_print_level;
    } else {
        ret = sscanf(argv[1], "%u", &level);

        if ((ret != 1) || (level >= LOG_NR_LEVELS)) {
            printf("log: dump: invalid arguments\n");
            return;
        }
    }

    log_dump(level);
}

static struct shell_cmd log_shell_cmds[] = {
    SHELL_CMD_INITIALIZER2("log_dump", log_shell_dump,
        "log_dump [<level>]",
        "dump the log buffer",
        "Only records of level less than or equal to the given level"
        " are printed. Level may be one of :\n"
        " 0: emergency\n"
        " 1: alert\n"
        " 2: critical\n"
        " 3: error\n"
        " 4: warning\n"
        " 5: notice\n"
        " 6: info\n"
        " 7: debug"),
};

static int __init
log_setup_shell(void)
{
    SHELL_REGISTER_CMDS(log_shell_cmds, shell_get_main_cmd_set());
    return 0;
}

INIT_OP_DEFINE(log_setup_shell,
               INIT_OP_DEP(log_setup, true),
               INIT_OP_DEP(shell_setup, true));

#endif /* CONFIG_SHELL */

static int __init
log_setup(void)
{
    cbuf_init(&log_cbuf, log_buffer, sizeof(log_buffer));
    log_index = cbuf_start(&log_cbuf);
    spinlock_init(&log_lock);
    log_print_level = LOG_INFO;

    boot_log_info();
    arg_log_info();
    cpu_log_info(cpu_current());

    return 0;
}

INIT_OP_DEFINE(log_setup,
               INIT_OP_DEP(arg_setup, true),
               INIT_OP_DEP(cpu_setup, true),
               INIT_OP_DEP(spinlock_setup, true));

static int __init
log_start(void)
{
    struct thread_attr attr;
    int error;

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "log_run");
    thread_attr_set_detached(&attr);
    error = thread_create(&log_thread, &attr, log_run, NULL);

    if (error) {
        panic("log: unable to create thread");
    }

    return 0;
}

INIT_OP_DEFINE(log_start,
               INIT_OP_DEP(log_setup, true),
               INIT_OP_DEP(thread_setup, true));

static void
log_write(const void *s, size_t size)
{
    int error;

    error = cbuf_push(&log_cbuf, s, size, true);
    assert(!error);

    if (!cbuf_range_valid(&log_cbuf, log_index, log_index + 1)) {
        log_nr_overruns += cbuf_start(&log_cbuf) - log_index;
        log_index = cbuf_start(&log_cbuf);
    }
}

int
log_msg(unsigned int level, const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_vmsg(level, format, ap);
    va_end(ap);

    return ret;
}

int
log_vmsg(unsigned int level, const char *format, va_list ap)
{
    struct log_record record;
    unsigned long flags;
    int nr_chars;
    size_t size;
    char *ptr;

    log_record_init_produce(&record, level);
    nr_chars = vsnprintf(record.buffer, sizeof(record.buffer), format, ap);

    if ((unsigned int)nr_chars >= sizeof(record.buffer)) {
        log_msg(LOG_ERR, "log: message too large");
        goto out;
    }

    ptr = strchr(record.buffer, '\n');

    if (ptr != NULL) {
        *ptr = '\0';
        nr_chars = ptr - record.buffer;
    }

    assert(nr_chars >= 0);
    size = offsetof(struct log_record, buffer) + nr_chars + 1;

    spinlock_lock_intr_save(&log_lock, &flags);
    log_write(&record, size);
    thread_wakeup(log_thread);
    spinlock_unlock_intr_restore(&log_lock, flags);

out:
    return nr_chars;
}

int
log_emerg(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_vemerg(format, ap);
    va_end(ap);

    return ret;
}

int
log_alert(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_valert(format, ap);
    va_end(ap);

    return ret;
}

int
log_crit(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_vcrit(format, ap);
    va_end(ap);

    return ret;
}

int
log_err(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_verr(format, ap);
    va_end(ap);

    return ret;
}

int
log_warning(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_vwarning(format, ap);
    va_end(ap);

    return ret;
}

int
log_notice(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_vnotice(format, ap);
    va_end(ap);

    return ret;
}

int
log_info(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_vinfo(format, ap);
    va_end(ap);

    return ret;
}

int
log_debug(const char *format, ...)
{
    va_list ap;
    int ret;

    va_start(ap, format);
    ret = log_vdebug(format, ap);
    va_end(ap);

    return ret;
}

int
log_vemerg(const char *format, va_list ap)
{
    return log_vmsg(LOG_EMERG, format, ap);
}

int
log_valert(const char *format, va_list ap)
{
    return log_vmsg(LOG_ALERT, format, ap);
}

int
log_vcrit(const char *format, va_list ap)
{
    return log_vmsg(LOG_CRIT, format, ap);
}

int
log_verr(const char *format, va_list ap)
{
    return log_vmsg(LOG_ERR, format, ap);
}

int
log_vwarning(const char *format, va_list ap)
{
    return log_vmsg(LOG_WARNING, format, ap);
}

int
log_vnotice(const char *format, va_list ap)
{
    return log_vmsg(LOG_NOTICE, format, ap);
}

int
log_vinfo(const char *format, va_list ap)
{
    return log_vmsg(LOG_INFO, format, ap);
}

int
log_vdebug(const char *format, va_list ap)
{
    return log_vmsg(LOG_DEBUG, format, ap);
}


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/>.
 *
 *
 * System logging.
 */

#ifndef KERN_LOG_H
#define KERN_LOG_H

#include <stdarg.h>

#include <kern/init.h>

enum {
    LOG_EMERG,
    LOG_ALERT,
    LOG_CRIT,
    LOG_ERR,
    LOG_WARNING,
    LOG_NOTICE,
    LOG_INFO,
    LOG_DEBUG,
    LOG_NR_LEVELS,
};

/*
 * Generate a message and send it to the log thread.
 *
 * The arguments and return value are similar to printf(), with
 * these exceptions :
 *  - a level is associated to each log message
 *  - processing stops at the first terminating null byte or newline
 *    character, whichever occurs first
 *
 * This function may safely be called in interrupt context.
 */
int log_msg(unsigned int level, const char *format, ...)
    __attribute__((format(printf, 2, 3)));

int log_vmsg(unsigned int level, const char *format, va_list ap)
    __attribute__((format(printf, 2, 0)));

/*
 * Convenience wrappers.
 */

int log_emerg(const char *format, ...) __attribute__((format(printf, 1, 2)));
int log_alert(const char *format, ...) __attribute__((format(printf, 1, 2)));
int log_crit(const char *format, ...) __attribute__((format(printf, 1, 2)));
int log_err(const char *format, ...) __attribute__((format(printf, 1, 2)));
int log_warning(const char *format, ...) __attribute__((format(printf, 1, 2)));
int log_notice(const char *format, ...) __attribute__((format(printf, 1, 2)));
int log_info(const char *format, ...) __attribute__((format(printf, 1, 2)));
int log_debug(const char *format, ...) __attribute__((format(printf, 1, 2)));

int log_vemerg(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));
int log_valert(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));
int log_vcrit(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));
int log_verr(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));
int log_vwarning(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));
int log_vnotice(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));
int log_vinfo(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));
int log_vdebug(const char *format, va_list ap)
    __attribute__((format(printf, 1, 0)));

/*
 * This init operation provides :
 *  - message logging
 *
 * The log thread isn't yet started and messages are merely stored in an
 * internal buffer.
 */
INIT_OP_DECLARE(log_setup);

#endif /* KERN_LOG_H */


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/>.
 *
 *
 * Integer base 2 logarithm operations.
 */

#ifndef KERN_LOG2_H
#define KERN_LOG2_H

#include <assert.h>
#include <limits.h>

/*
 * Return the base-2 logarithm of the given value, or of the first
 * power-of-two below the given value if it's not a power-of-two.
 */
static inline unsigned int
log2(unsigned long x)
{
    assert(x != 0);
    return LONG_BIT - __builtin_clzl(x) - 1;
}

/*
 * Return the base-2 logarithm of the given value, or of the first
 * power-of-two above the given value if it's not a power-of-two.
 */
static inline unsigned int
log2_order(unsigned long size)
{
    assert(size != 0);

    if (size == 1) {
        return 0;
    }

    return log2(size - 1) + 1;
}

#endif /* KERN_LOG2_H */


code:
/*
 * Copyright (c) 2009-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/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 *
 *
 * Helper macros.
 *
 * This file is a top header in the inclusion hierarchy, and shouldn't include
 * other headers that may cause circular dependencies.
 *
 * TODO Improve documentation.
 */

#ifndef KERN_MACROS_H
#define KERN_MACROS_H

#if !defined(__GNUC__) || (__GNUC__ < 4)
#error "GCC 4+ required"
#endif

#ifndef __ASSEMBLER__
#include <stddef.h>
#endif

/*
 * Attributes for variables that are mostly read and seldom changed.
 */
#define __read_mostly       __section(".data.read_mostly")

#define MACRO_BEGIN         ({
#define MACRO_END           })

#define __QUOTE(x)          #x
#define QUOTE(x)            __QUOTE(x)

#ifdef __ASSEMBLER__
#define DECL_CONST(x, s)    x
#else /* __ASSEMBLER__ */
#define __DECL_CONST(x, s)  x##s
#define DECL_CONST(x, s)    __DECL_CONST(x, s)
#endif /* __ASSEMBLER__ */

#define STRLEN(x)           (sizeof(x) - 1)
#define ARRAY_SIZE(x)       (sizeof(x) / sizeof((x)[0]))

#define MIN(a, b)           ((a) < (b) ? (a) : (b))
#define MAX(a, b)           ((a) > (b) ? (a) : (b))

#define DIV_CEIL(n, d)      (((n) + (d) - 1) / (d))

#define P2ALIGNED(x, a)     (((x) & ((a) - 1)) == 0)
#define ISP2(x)             P2ALIGNED(x, x)
#define P2ALIGN(x, a)       ((x) & -(a))        /* decreases if not aligned */
#define P2ROUND(x, a)       (-(-(x) & -(a)))    /* increases if not aligned */
#define P2END(x, a)         (-(~(x) & -(a)))    /* always increases */

#define structof(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

#define likely(expr)        __builtin_expect(!!(expr), 1)
#define unlikely(expr)      __builtin_expect(!!(expr), 0)

#define barrier()           asm volatile("" : : : "memory")

/*
 * The following macros may be provided by the C environment.
 */

#ifndef __noinline
#define __noinline          __attribute__((noinline))
#endif

#ifndef __always_inline
#define __always_inline     inline __attribute__((always_inline))
#endif

#ifndef __section
#define __section(x)        __attribute__((section(x)))
#endif

#ifndef __packed
#define __packed            __attribute__((packed))
#endif

#ifndef __unused
#define __unused            __attribute__((unused))
#endif

#ifndef __used
#define __used              __attribute__((used))
#endif

#ifndef __weak
#define __weak              __attribute__((weak))
#endif

#ifndef __fallthrough
#if __GNUC__ >= 7
#define __fallthrough       __attribute__((fallthrough))
#else /* __GNUC__ >= 7 */
#define __fallthrough
#endif /* __GNUC__ >= 7 */
#endif

#endif /* KERN_MACROS_H */


code:
/*
 * Copyright (c) 2013-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/>.
 */

#include <kern/init.h>
#include <kern/mutex.h>
#include <kern/thread.h>

static int __init
mutex_bootstrap(void)
{
    return 0;
}

INIT_OP_DEFINE(mutex_bootstrap,
               INIT_OP_DEP(mutex_impl_bootstrap, true),
               INIT_OP_DEP(thread_setup_booter, true));

static int __init
mutex_setup(void)
{
    return 0;
}

INIT_OP_DEFINE(mutex_setup,
               INIT_OP_DEP(mutex_impl_setup, true));


code:
/*
 * Copyright (c) 2013-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/>.
 *
 *
 * Mutual exclusion sleep locks.
 *
 * Unlike spin locks, acquiring a mutex may make the calling thread sleep.
 */

#ifndef KERN_MUTEX_H
#define KERN_MUTEX_H

#include <stdbool.h>
#include <stdint.h>

#if defined(CONFIG_MUTEX_ADAPTIVE)
#include <kern/mutex/mutex_adaptive_i.h>
#elif defined(CONFIG_MUTEX_PI)
#include <kern/mutex/mutex_pi_i.h>
#elif defined(CONFIG_MUTEX_PLAIN)
#include <kern/mutex/mutex_plain_i.h>
#else
#error "unknown mutex implementation"
#endif

#include <kern/init.h>
#include <kern/mutex_types.h>

/*
 * Initialize a mutex.
 */
static inline void
mutex_init(struct mutex *mutex)
{
    mutex_impl_init(mutex);
}

static inline bool
mutex_locked(const struct mutex *mutex)
{
    return mutex_impl_locked(mutex);
}

/*
 * Attempt to lock the given mutex.
 *
 * This function may not sleep.
 *
 * Return 0 on success, EBUSY if the mutex is already locked.
 */
static inline int
mutex_trylock(struct mutex *mutex)
{
    return mutex_impl_trylock(mutex);
}

/*
 * Lock a mutex.
 *
 * On return, the mutex is locked. A mutex can only be locked once.
 *
 * This function may sleep.
 */
static inline void
mutex_lock(struct mutex *mutex)
{
    mutex_impl_lock(mutex);
}

/*
 * Lock a mutex, with a time boundary.
 *
 * The time boundary is an absolute time in ticks.
 *
 * If successful, the mutex is locked, otherwise an error is returned.
 * A mutex can only be locked once.
 *
 * This function may sleep.
 */
static inline int
mutex_timedlock(struct mutex *mutex, uint64_t ticks)
{
    return mutex_impl_timedlock(mutex, ticks);
}

/*
 * Unlock a mutex.
 *
 * The mutex must be locked, and must have been locked by the calling
 * thread.
 */
static inline void
mutex_unlock(struct mutex *mutex)
{
    mutex_impl_unlock(mutex);
}

/*
 * Special init operation for syscnt_setup.
 *
 * This init operation only exists to avoid a circular dependency between
 * syscnt_setup and mutex_setup, without giving syscnt_setup knowledge
 * about the dependencies of mutex_setup.
 */
INIT_OP_DECLARE(mutex_bootstrap);

/*
 * This init operation provides :
 *  - uncontended mutex locking
 *
 * Contended locking may only occur after starting the scheduler.
 */
INIT_OP_DECLARE(mutex_setup);

#endif /* KERN_MUTEX_H */


code:
/*
 * Copyright (c) 2017 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/>.
 */

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

#include <kern/atomic.h>
#include <kern/clock.h>
#include <kern/init.h>
#include <kern/mutex.h>
#include <kern/mutex_types.h>
#include <kern/sleepq.h>
#include <kern/syscnt.h>
#include <kern/thread.h>
#include <machine/cpu.h>

#ifdef CONFIG_MUTEX_DEBUG

enum {
    MUTEX_ADAPTIVE_SC_SPINS,
    MUTEX_ADAPTIVE_SC_WAIT_SUCCESSES,
    MUTEX_ADAPTIVE_SC_WAIT_ERRORS,
    MUTEX_ADAPTIVE_SC_DOWNGRADES,
    MUTEX_ADAPTIVE_SC_ERROR_DOWNGRADES,
    MUTEX_ADAPTIVE_SC_ERROR_CLEARCONT,
    MUTEX_ADAPTIVE_SC_ERROR_RESET,
    MUTEX_ADAPTIVE_SC_FAST_UNLOCKS,
    MUTEX_ADAPTIVE_SC_SLOW_UNLOCKS,
    MUTEX_ADAPTIVE_SC_EXTERNAL_UNLOCKS,
    MUTEX_ADAPTIVE_SC_SIGNALS,
    MUTEX_ADAPTIVE_NR_SCS
};

static struct syscnt mutex_adaptive_sc_array[MUTEX_ADAPTIVE_NR_SCS];

static void
mutex_adaptive_register_sc(unsigned int index, const char *name)
{
    assert(index < ARRAY_SIZE(mutex_adaptive_sc_array));
    syscnt_register(&mutex_adaptive_sc_array[index], name);
}

static void
mutex_adaptive_setup_debug(void)
{
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_SPINS,
                               "mutex_adaptive_spins");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_WAIT_SUCCESSES,
                               "mutex_adaptive_wait_successes");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_WAIT_ERRORS,
                               "mutex_adaptive_wait_errors");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_DOWNGRADES,
                               "mutex_adaptive_downgrades");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_ERROR_DOWNGRADES,
                               "mutex_adaptive_error_downgrades");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_ERROR_CLEARCONT,
                               "mutex_adaptive_error_clearcont");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_ERROR_RESET,
                               "mutex_adaptive_error_reset");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_FAST_UNLOCKS,
                               "mutex_adaptive_fast_unlocks");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_SLOW_UNLOCKS,
                               "mutex_adaptive_slow_unlocks");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_EXTERNAL_UNLOCKS,
                               "mutex_adaptive_external_unlocks");
    mutex_adaptive_register_sc(MUTEX_ADAPTIVE_SC_SIGNALS,
                               "mutex_adaptive_signals");
}

static void
mutex_adaptive_inc_sc(unsigned int index)
{
    assert(index < ARRAY_SIZE(mutex_adaptive_sc_array));
    syscnt_inc(&mutex_adaptive_sc_array[index]);
}

#else /* CONFIG_MUTEX_DEBUG */
#define mutex_adaptive_setup_debug()
#define mutex_adaptive_inc_sc(x)
#endif /* CONFIG_MUTEX_DEBUG */

static struct thread *
mutex_adaptive_get_thread(uintptr_t owner)
{
    return (struct thread *)(owner & ~MUTEX_ADAPTIVE_CONTENDED);
}

static void
mutex_adaptive_set_contended(struct mutex *mutex)
{
    atomic_or(&mutex->owner, MUTEX_ADAPTIVE_CONTENDED, ATOMIC_RELEASE);
}

static inline bool
mutex_adaptive_is_owner(struct mutex *mutex, uintptr_t owner)
{
    uintptr_t prev;

    prev = atomic_load(&mutex->owner, ATOMIC_RELAXED);
    return mutex_adaptive_get_thread(prev) == mutex_adaptive_get_thread(owner);
}

static int
mutex_adaptive_lock_slow_common(struct mutex *mutex, bool timed, uint64_t ticks)
{
    uintptr_t self, owner;
    struct sleepq *sleepq;
    struct thread *thread;
    int error;

    error = 0;
    self = (uintptr_t)thread_self();

    sleepq = sleepq_lend(mutex, false);

    mutex_adaptive_set_contended(mutex);

    do {
        owner = atomic_cas(&mutex->owner, MUTEX_ADAPTIVE_CONTENDED,
                           self | MUTEX_ADAPTIVE_CONTENDED, ATOMIC_ACQUIRE);
        assert(owner & MUTEX_ADAPTIVE_CONTENDED);

        if (mutex_adaptive_get_thread(owner) == NULL) {
            break;
        }

        /*
         * The owner may not return from the unlock function if a thread is
         * spinning on it.
         */
        while (mutex_adaptive_is_owner(mutex, owner)) {
            if (thread_is_running(mutex_adaptive_get_thread(owner))) {
                mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_SPINS);

                if (timed && clock_time_occurred(ticks, clock_get_time())) {
                    error = ETIMEDOUT;
                    break;
                }

                cpu_pause();
            } else {
                if (!timed) {
                    sleepq_wait(sleepq, "mutex");
                } else {
                    error = sleepq_timedwait(sleepq, "mutex", ticks);

                    if (error) {
                        break;
                    }
                }
            }
        }
    } while (!error);

    /*
     * Attempt to clear the contended bit.
     *
     * In case of success, the current thread becomes the new owner, and
     * simply checking if the sleep queue is empty is enough.
     *
     * Keep in mind accesses to the mutex word aren't synchronized by
     * the sleep queue, i.e. an unlock may occur completely concurrently
     * while attempting to clear the contended bit .
     */

    if (error) {
        mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_WAIT_ERRORS);

        if (sleepq_empty(sleepq)) {
            mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_ERROR_DOWNGRADES);
            owner = atomic_load(&mutex->owner, ATOMIC_RELAXED);
            assert(owner & MUTEX_ADAPTIVE_CONTENDED);
            thread = mutex_adaptive_get_thread(owner);

            /* If there is an owner, try to clear the contended bit */
            if (thread != NULL) {
                mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_ERROR_CLEARCONT);
                owner = atomic_cas(&mutex->owner, owner,
                                   (uintptr_t)thread, ATOMIC_RELAXED);
                assert(owner & MUTEX_ADAPTIVE_CONTENDED);
                thread = mutex_adaptive_get_thread(owner);
            }

            /*
             * If there is no owner, the previous owner is currently unlocking
             * the mutex, waiting for either a successful signal, or the
             * value of the mutex to become different from the contended bit.
             */
            if (thread == NULL) {
                mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_ERROR_RESET);
                owner = atomic_cas(&mutex->owner, owner, 0, ATOMIC_RELAXED);
                assert(owner == MUTEX_ADAPTIVE_CONTENDED);
            }
        }

        goto out;
    }

    mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_WAIT_SUCCESSES);

    if (sleepq_empty(sleepq)) {
        mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_DOWNGRADES);
        atomic_store(&mutex->owner, self, ATOMIC_RELAXED);
    }

out:
    sleepq_return(sleepq);

    return error;
}

void
mutex_adaptive_lock_slow(struct mutex *mutex)
{
    int error;

    error = mutex_adaptive_lock_slow_common(mutex, false, 0);
    assert(!error);
}

int
mutex_adaptive_timedlock_slow(struct mutex *mutex, uint64_t ticks)
{
    return mutex_adaptive_lock_slow_common(mutex, true, ticks);
}

void
mutex_adaptive_unlock_slow(struct mutex *mutex)
{
    uintptr_t self, owner;
    struct sleepq *sleepq;
    int error;

    self = (uintptr_t)thread_self() | MUTEX_ADAPTIVE_CONTENDED;

    for (;;) {
        owner = atomic_cas(&mutex->owner, self,
                           MUTEX_ADAPTIVE_CONTENDED, ATOMIC_RELEASE);

        if (owner == self) {
            break;
        } else {
            /*
             * The contended bit was cleared after the fast path failed,
             * but before the slow path (re)started.
             */
            assert(owner == (uintptr_t)thread_self());
            error = mutex_adaptive_unlock_fast(mutex);

            if (error) {
                continue;
            }

            mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_FAST_UNLOCKS);
            return;
        }
    }

    mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_SLOW_UNLOCKS);

    for (;;) {
        owner = atomic_load(&mutex->owner, ATOMIC_RELAXED);

        /*
         * This only happens if :
         *  1/ Another thread was able to become the new owner, in which
         *     case that thread isn't spinning on the current thread, i.e.
         *     there is no need for an additional reference.
         *  2/ A timeout cleared the contended bit.
         */
        if (owner != MUTEX_ADAPTIVE_CONTENDED) {
            mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_EXTERNAL_UNLOCKS);
            break;
        }

        /*
         * Avoid contending with incoming threads that are about to spin/wait
         * on the mutex. This is particularly expensive with queued locks.
         *
         * Also, this call returns NULL if another thread is currently spinning
         * on the current thread, in which case the latter doesn't return,
         * averting the need for an additional reference.
         */
        sleepq = sleepq_tryacquire(mutex, false);

        if (sleepq != NULL) {
            mutex_adaptive_inc_sc(MUTEX_ADAPTIVE_SC_SIGNALS);
            sleepq_signal(sleepq);
            sleepq_release(sleepq);
            break;
        }

        /*
         * Acquiring the sleep queue may fail because of contention on
         * unrelated objects. Retry.
         */
    }
}

static int
mutex_adaptive_bootstrap(void)
{
    return 0;
}

INIT_OP_DEFINE(mutex_adaptive_bootstrap,
               INIT_OP_DEP(thread_setup_booter, true));

static int
mutex_adaptive_setup(void)
{
    mutex_adaptive_setup_debug();
    return 0;
}

#ifdef CONFIG_MUTEX_DEBUG
#define MUTEX_ADAPTIVE_DEBUG_INIT_OP_DEPS       \
               INIT_OP_DEP(syscnt_setup, true),
#else /* CONFIG_MUTEX_DEBUG */
#define MUTEX_ADAPTIVE_DEBUG_INIT_OP_DEPS
#endif /* CONFIG_MUTEX_DEBUG */

INIT_OP_DEFINE(mutex_adaptive_setup,
               INIT_OP_DEP(mutex_adaptive_bootstrap, true),
               MUTEX_ADAPTIVE_DEBUG_INIT_OP_DEPS
);


code:
/*
 * Copyright (c) 2017 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/>.
 */

#ifndef KERN_MUTEX_ADAPTIVE_I_H
#define KERN_MUTEX_ADAPTIVE_I_H

#ifndef KERN_MUTEX_H
#error "don't include <kern/mutex/mutex_adaptive_i.h> directly," \
       " use <kern/mutex.h> instead"
#endif

#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdint.h>

#include <kern/atomic.h>
#include <kern/init.h>
#include <kern/macros.h>
#include <kern/mutex_types.h>
#include <kern/thread.h>

/*
 * Mutex flags.
 *
 * The "contended" flag indicates that threads are waiting for the mutex
 * to be unlocked, potentially spinning on the owner. It forces threads
 * trying to lock the mutex as well as the owner to take the slow path.
 */
#define MUTEX_ADAPTIVE_CONTENDED 0x1UL

static inline void
mutex_adaptive_init(struct mutex *mutex)
{
    mutex->owner = 0;
}

static inline bool
mutex_adaptive_locked(const struct mutex *mutex)
{
    uintptr_t owner;

    owner = atomic_load(&mutex->owner, ATOMIC_RELAXED);
    return (owner != 0);
}

static inline int
mutex_adaptive_lock_fast(struct mutex *mutex)
{
    uintptr_t owner;

    owner = atomic_cas(&mutex->owner, 0,
                       (uintptr_t)thread_self(), ATOMIC_ACQUIRE);

    if (unlikely(owner != 0)) {
        return EBUSY;
    }

    return 0;
}

static inline int
mutex_adaptive_unlock_fast(struct mutex *mutex)
{
    uintptr_t owner;

    owner = atomic_cas(&mutex->owner, (uintptr_t)thread_self(),
                       0, ATOMIC_RELEASE);

    if (unlikely(owner & MUTEX_ADAPTIVE_CONTENDED)) {
        return EBUSY;
    }

    return 0;
}

void mutex_adaptive_lock_slow(struct mutex *mutex);
int mutex_adaptive_timedlock_slow(struct mutex *mutex, uint64_t ticks);
void mutex_adaptive_unlock_slow(struct mutex *mutex);

/*
 * Interface exported to the public mutex header.
 */

#define mutex_impl_init             mutex_adaptive_init
#define mutex_impl_locked           mutex_adaptive_locked

static inline int
mutex_impl_trylock(struct mutex *mutex)
{
    return mutex_adaptive_lock_fast(mutex);
}

static inline void
mutex_impl_lock(struct mutex *mutex)
{
    int error;

    error = mutex_adaptive_lock_fast(mutex);

    if (unlikely(error)) {
        mutex_adaptive_lock_slow(mutex);
    }
}

static inline int
mutex_impl_timedlock(struct mutex *mutex, uint64_t ticks)
{
    int error;

    error = mutex_adaptive_lock_fast(mutex);

    if (unlikely(error)) {
        error = mutex_adaptive_timedlock_slow(mutex, ticks);
    }

    return error;
}

static inline void
mutex_impl_unlock(struct mutex *mutex)
{
    int error;

    error = mutex_adaptive_unlock_fast(mutex);

    if (unlikely(error)) {
        mutex_adaptive_unlock_slow(mutex);
    }
}

/*
 * Mutex init operations. See kern/mutex.h.
 */

#define mutex_impl_bootstrap mutex_adaptive_bootstrap
INIT_OP_DECLARE(mutex_adaptive_bootstrap);

#define mutex_impl_setup mutex_adaptive_setup
INIT_OP_DECLARE(mutex_adaptive_setup);

#endif /* KERN_MUTEX_ADAPTIVE_I_H */


code:
/*
 * Copyright (c) 2017 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/>.
 *
 *
 * Isolated type definition used to avoid inclusion circular dependencies.
 */

#ifndef KERN_MUTEX_ADAPTIVE_TYPES_H
#define KERN_MUTEX_ADAPTIVE_TYPES_H

#ifndef KERN_MUTEX_TYPES_H
#error "don't include <kern/mutex/mutex_adaptive_types.h> directly," \
       " use <kern/mutex_types.h> instead"
#endif

#include <stdint.h>

struct mutex {
    uintptr_t owner;
};

#endif /* KERN_MUTEX_ADAPTIVE_TYPES_H */


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/>.
 */

#ifndef KERN_MUTEX_PI_I_H
#define KERN_MUTEX_PI_I_H

#ifndef KERN_MUTEX_H
#error "don't include <kern/mutex/mutex_pi_i.h> directly," \
       " use <kern/mutex.h> instead"
#endif

#include <stdbool.h>
#include <stdint.h>

#include <kern/mutex_types.h>
#include <kern/rtmutex.h>

/*
 * Interface exported to the public mutex header.
 */

static inline void
mutex_impl_init(struct mutex *mutex)
{
    rtmutex_init(&mutex->rtmutex);
}

static inline bool
mutex_impl_locked(const struct mutex *mutex)
{
    return rtmutex_locked(&mutex->rtmutex);
}

static inline int
mutex_impl_trylock(struct mutex *mutex)
{
    return rtmutex_trylock(&mutex->rtmutex);
}

static inline void
mutex_impl_lock(struct mutex *mutex)
{
    rtmutex_lock(&mutex->rtmutex);
}

static inline int
mutex_impl_timedlock(struct mutex *mutex, uint64_t ticks)
{
    return rtmutex_timedlock(&mutex->rtmutex, ticks);
}

static inline void
mutex_impl_unlock(struct mutex *mutex)
{
    rtmutex_unlock(&mutex->rtmutex);
}

/*
 * Mutex init operations. See kern/mutex.h.
 */

#define mutex_impl_bootstrap    rtmutex_bootstrap
#define mutex_impl_setup        rtmutex_setup

#endif /* KERN_MUTEX_PI_I_H */


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/>.
 *
 *
 * Isolated type definition used to avoid inclusion circular dependencies.
 */

#ifndef KERN_MUTEX_PI_TYPES_H
#define KERN_MUTEX_PI_TYPES_H

#ifndef KERN_MUTEX_TYPES_H
#error "don't include <kern/mutex/mutex_pi_types.h> directly," \
       " use <kern/mutex_types.h> instead"
#endif

#include <kern/rtmutex_types.h>

/*
 * Do not directly alias rtmutex to make sure they cannot be used
 * with condition variables by mistake.
 */
struct mutex {
    struct rtmutex rtmutex;
};

#endif /* KERN_MUTEX_PI_TYPES_H */


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/>.
 */

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

#include <kern/atomic.h>
#include <kern/init.h>
#include <kern/mutex.h>
#include <kern/mutex_types.h>
#include <kern/sleepq.h>
#include <kern/syscnt.h>

#ifdef CONFIG_MUTEX_DEBUG

enum {
    MUTEX_PLAIN_SC_WAIT_SUCCESSES,
    MUTEX_PLAIN_SC_WAIT_ERRORS,
    MUTEX_PLAIN_SC_DOWNGRADES,
    MUTEX_PLAIN_SC_ERROR_DOWNGRADES,
    MUTEX_PLAIN_NR_SCS
};

static struct syscnt mutex_plain_sc_array[MUTEX_PLAIN_NR_SCS];

static void
mutex_plain_register_sc(unsigned int index, const char *name)
{
    assert(index < ARRAY_SIZE(mutex_plain_sc_array));
    syscnt_register(&mutex_plain_sc_array[index], name);
}

static void
mutex_plain_setup_debug(void)
{
    mutex_plain_register_sc(MUTEX_PLAIN_SC_WAIT_SUCCESSES,
                            "mutex_plain_wait_successes");
    mutex_plain_register_sc(MUTEX_PLAIN_SC_WAIT_ERRORS,
                            "mutex_plain_wait_errors");
    mutex_plain_register_sc(MUTEX_PLAIN_SC_DOWNGRADES,
                            "mutex_plain_downgrades");
    mutex_plain_register_sc(MUTEX_PLAIN_SC_ERROR_DOWNGRADES,
                            "mutex_plain_error_downgrades");
}

static void
mutex_plain_inc_sc(unsigned int index)
{
    assert(index < ARRAY_SIZE(mutex_plain_sc_array));
    syscnt_inc(&mutex_plain_sc_array[index]);
}

#else /* CONFIG_MUTEX_DEBUG */
#define mutex_plain_setup_debug()
#define mutex_plain_inc_sc(x)
#endif /* CONFIG_MUTEX_DEBUG */

static int
mutex_plain_lock_slow_common(struct mutex *mutex, bool timed, uint64_t ticks)
{
    unsigned int state;
    struct sleepq *sleepq;
    int error;

    error = 0;

    sleepq = sleepq_lend(mutex, false);

    for (;;) {
        state = atomic_swap(&mutex->state, MUTEX_PLAIN_CONTENDED,
                            ATOMIC_RELEASE);

        if (state == MUTEX_PLAIN_UNLOCKED) {
            break;
        }

        if (!timed) {
            sleepq_wait(sleepq, "mutex");
        } else {
            error = sleepq_timedwait(sleepq, "mutex", ticks);

            if (error) {
                break;
            }
        }
    }

    if (error) {
        mutex_plain_inc_sc(MUTEX_PLAIN_SC_WAIT_ERRORS);

        if (sleepq_empty(sleepq)) {
            mutex_plain_inc_sc(MUTEX_PLAIN_SC_ERROR_DOWNGRADES);
            atomic_cas(&mutex->state, MUTEX_PLAIN_CONTENDED,
                       MUTEX_PLAIN_LOCKED, ATOMIC_RELAXED);
        }

        goto out;
    }

    mutex_plain_inc_sc(MUTEX_PLAIN_SC_WAIT_SUCCESSES);

    if (sleepq_empty(sleepq)) {
        mutex_plain_inc_sc(MUTEX_PLAIN_SC_DOWNGRADES);
        atomic_store(&mutex->state, MUTEX_PLAIN_LOCKED, ATOMIC_RELAXED);
    }

out:
    sleepq_return(sleepq);

    return error;
}

void
mutex_plain_lock_slow(struct mutex *mutex)
{
    int error;

    error = mutex_plain_lock_slow_common(mutex, false, 0);
    assert(!error);
}

int
mutex_plain_timedlock_slow(struct mutex *mutex, uint64_t ticks)
{
    return mutex_plain_lock_slow_common(mutex, true, ticks);
}

void
mutex_plain_unlock_slow(struct mutex *mutex)
{
    struct sleepq *sleepq;

    sleepq = sleepq_acquire(mutex, false);

    if (sleepq == NULL) {
        return;
    }

    sleepq_signal(sleepq);

    sleepq_release(sleepq);
}

static int
mutex_plain_bootstrap(void)
{
    return 0;
}

INIT_OP_DEFINE(mutex_plain_bootstrap);

static int
mutex_plain_setup(void)
{
    mutex_plain_setup_debug();
    return 0;
}

#ifdef CONFIG_MUTEX_DEBUG
#define MUTEX_PLAIN_DEBUG_INIT_OP_DEPS          \
               INIT_OP_DEP(syscnt_setup, true),
#else /* CONFIG_MUTEX_DEBUG */
#define MUTEX_PLAIN_DEBUG_INIT_OP_DEPS
#endif /* CONFIG_MUTEX_DEBUG */

INIT_OP_DEFINE(mutex_plain_setup,
               INIT_OP_DEP(mutex_plain_bootstrap, true),
               MUTEX_PLAIN_DEBUG_INIT_OP_DEPS
);


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/>.
 */

#ifndef KERN_MUTEX_PLAIN_I_H
#define KERN_MUTEX_PLAIN_I_H

#ifndef KERN_MUTEX_H
#error "don't include <kern/mutex/mutex_plain_i.h> directly," \
       " use <kern/mutex.h> instead"
#endif

#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdint.h>

#include <kern/atomic.h>
#include <kern/init.h>
#include <kern/mutex_types.h>

#define MUTEX_PLAIN_UNLOCKED    0
#define MUTEX_PLAIN_LOCKED      1
#define MUTEX_PLAIN_CONTENDED   2

static inline void
mutex_plain_init(struct mutex *mutex)
{
    mutex->state = MUTEX_PLAIN_UNLOCKED;
}

static inline bool
mutex_plain_locked(const struct mutex *mutex)
{
    unsigned int state;

    state = atomic_load(&mutex->state, ATOMIC_RELAXED);
    return (state != MUTEX_PLAIN_UNLOCKED);
}

static inline int
mutex_plain_lock_fast(struct mutex *mutex)
{
    unsigned int state;

    state = atomic_cas(&mutex->state, MUTEX_PLAIN_UNLOCKED,
                       MUTEX_PLAIN_LOCKED, ATOMIC_ACQUIRE);

    if (unlikely(state != MUTEX_PLAIN_UNLOCKED)) {
        return EBUSY;
    }

    return 0;
}

static inline int
mutex_plain_unlock_fast(struct mutex *mutex)
{
    unsigned int state;

    state = atomic_swap(&mutex->state, MUTEX_PLAIN_UNLOCKED, ATOMIC_RELEASE);

    if (unlikely(state == MUTEX_PLAIN_CONTENDED)) {
        return EBUSY;
    }

    return 0;
}

void mutex_plain_lock_slow(struct mutex *mutex);
int mutex_plain_timedlock_slow(struct mutex *mutex, uint64_t ticks);
void mutex_plain_unlock_slow(struct mutex *mutex);

/*
 * Interface exported to the public mutex header.
 */

#define mutex_impl_init             mutex_plain_init
#define mutex_impl_locked           mutex_plain_locked

static inline int
mutex_impl_trylock(struct mutex *mutex)
{
    return mutex_plain_lock_fast(mutex);
}

static inline void
mutex_impl_lock(struct mutex *mutex)
{
    int error;

    error = mutex_plain_lock_fast(mutex);

    if (unlikely(error)) {
        mutex_plain_lock_slow(mutex);
    }
}

static inline int
mutex_impl_timedlock(struct mutex *mutex, uint64_t ticks)
{
    int error;

    error = mutex_plain_lock_fast(mutex);

    if (unlikely(error)) {
        error = mutex_plain_timedlock_slow(mutex, ticks);
    }

    return error;
}

static inline void
mutex_impl_unlock(struct mutex *mutex)
{
    int error;

    error = mutex_plain_unlock_fast(mutex);

    if (unlikely(error)) {
        mutex_plain_unlock_slow(mutex);
    }
}

/*
 * Mutex init operations. See kern/mutex.h.
 */

#define mutex_impl_bootstrap mutex_plain_bootstrap
INIT_OP_DECLARE(mutex_plain_bootstrap);

#define mutex_impl_setup mutex_plain_setup
INIT_OP_DECLARE(mutex_plain_setup);

#endif /* KERN_MUTEX_PLAIN_I_H */


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/>.
 *
 *
 * Isolated type definition used to avoid inclusion circular dependencies.
 */

#ifndef KERN_MUTEX_PLAIN_TYPES_H
#define KERN_MUTEX_PLAIN_TYPES_H

#ifndef KERN_MUTEX_TYPES_H
#error "don't include <kern/mutex/mutex_plain_types.h> directly," \
       " use <kern/mutex_types.h> instead"
#endif

struct mutex {
    unsigned int state;
};

#endif /* KERN_MUTEX_PLAIN_TYPES_H */


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/>.
 *
 *
 * Isolated type definition used to avoid inclusion circular dependencies.
 */

#ifndef KERN_MUTEX_TYPES_H
#define KERN_MUTEX_TYPES_H

#if defined(CONFIG_MUTEX_ADAPTIVE)
#include <kern/mutex/mutex_adaptive_types.h>
#elif defined(CONFIG_MUTEX_PI)
#include <kern/mutex/mutex_pi_types.h>
#elif defined(CONFIG_MUTEX_PLAIN)
#include <kern/mutex/mutex_plain_types.h>
#else
#error "unknown mutex implementation"
#endif

#endif /* KERN_MUTEX_TYPES_H */


code:
/*
 * Copyright (c) 2010-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/>.
 */

#include <stdarg.h>
#include <stdio.h>

#include <kern/atomic.h>
#include <kern/panic.h>
#include <machine/cpu.h>
#include <machine/strace.h>

static unsigned int panic_done;

void
panic(const char *format, ...)
{
    va_list list;
    unsigned long already_done;

    already_done = atomic_swap(&panic_done, 1, ATOMIC_SEQ_CST);

    if (already_done) {
        for (;;) {
            cpu_idle();
        }
    }

    cpu_intr_disable();
    cpu_halt_broadcast();

    printf("\npanic: ");
    va_start(list, format);
    vprintf(format, list);
    printf("\n");
    strace_dump();

    cpu_halt();

    /*
     * Never reached.
     */
}


code:
/*
 * Copyright (c) 2010 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/>.
 */

#ifndef KERN_PANIC_H
#define KERN_PANIC_H

#include <stdnoreturn.h>

/*
 * Print the given message and halt the system immediately.
 *
 * If in doubt whether to call this function or not because of dependency
 * issues, users are encouraged to call this function, even if it results
 * in undefined behavior, because it should most likely cause a freeze or
 * reset, which is considered better than a silent failure.
 */
noreturn void panic(const char *format, ...)
    __attribute__((format(printf, 1, 2)));

#endif /* KERN_PANIC_H */


code:
/*
 * Copyright (c) 2014-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/>.
 */

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

#include <kern/init.h>
#include <kern/log.h>
#include <kern/macros.h>
#include <kern/panic.h>
#include <kern/percpu.h>
#include <kern/slist.h>
#include <machine/cpu.h>
#include <vm/vm_kmem.h>
#include <vm/vm_page.h>

void *percpu_areas[CONFIG_MAX_CPUS] __read_mostly;

static void *percpu_area_content __initdata;
static size_t percpu_area_size __initdata;
static int percpu_skip_warning __initdata;

static struct slist percpu_ops __initdata;

static void __init
percpu_op_run(const struct percpu_op *op)
{
    op->fn();
}

static int __init
percpu_bootstrap(void)
{
    percpu_areas[0] = &_percpu;
    return 0;
}

INIT_OP_DEFINE(percpu_bootstrap);

static int __init
percpu_setup(void)
{
    struct vm_page *page;
    unsigned int order;

    slist_init(&percpu_ops);

    percpu_area_size = &_percpu_end - &_percpu;
    log_info("percpu: max_cpus: %u, section size: %zuk", CONFIG_MAX_CPUS,
             percpu_area_size >> 10);
    assert(vm_page_aligned(percpu_area_size));

    if (percpu_area_size == 0) {
        return 0;
    }

    order = vm_page_order(percpu_area_size);
    page = vm_page_alloc(order, VM_PAGE_SEL_DIRECTMAP, VM_PAGE_KERNEL);

    if (page == NULL) {
        panic("percpu: unable to allocate memory for percpu area content");
    }

    percpu_area_content = vm_page_direct_ptr(page);
    memcpy(percpu_area_content, &_percpu, percpu_area_size);
    return 0;
}

INIT_OP_DEFINE(percpu_setup,
               INIT_OP_DEP(percpu_bootstrap, true),
               INIT_OP_DEP(vm_page_setup, true));

void __init
percpu_register_op(struct percpu_op *op)
{
    slist_insert_tail(&percpu_ops, &op->node);

    /* Run on BSP */
    percpu_op_run(op);
}

int __init
percpu_add(unsigned int cpu)
{
    struct vm_page *page;
    unsigned int order;

    if (cpu >= ARRAY_SIZE(percpu_areas)) {
        if (!percpu_skip_warning) {
            log_warning("percpu: ignoring processor beyond id %zu",
                        ARRAY_SIZE(percpu_areas) - 1);
            percpu_skip_warning = 1;
        }

        return EINVAL;
    }

    if (percpu_areas[cpu] != NULL) {
        log_err("percpu: id %u ignored, already registered", cpu);
        return EINVAL;
    }

    if (percpu_area_size == 0) {
        goto out;
    }

    order = vm_page_order(percpu_area_size);
    page = vm_page_alloc(order, VM_PAGE_SEL_DIRECTMAP, VM_PAGE_KERNEL);

    if (page == NULL) {
        log_err("percpu: unable to allocate percpu area");
        return ENOMEM;
    }

    percpu_areas[cpu] = vm_page_direct_ptr(page);
    memcpy(percpu_area(cpu), percpu_area_content, percpu_area_size);

out:
    return 0;
}

void __init
percpu_ap_setup(void)
{
    struct percpu_op *op;

    slist_for_each_entry(&percpu_ops, op, node) {
        percpu_op_run(op);
    }
}

static int __init
percpu_cleanup(void)
{
    struct vm_page *page;
    uintptr_t va;

    va = (uintptr_t)percpu_area_content;
    page = vm_page_lookup(vm_page_direct_pa(va));
    vm_page_free(page, vm_page_order(percpu_area_size));
    return 0;
}

INIT_OP_DEFINE(percpu_cleanup,
               INIT_OP_DEP(cpu_mp_probe, true),
               INIT_OP_DEP(percpu_setup, true),
               INIT_OP_DEP(vm_page_setup, true));


code:
/*
 * Copyright (c) 2014-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/>.
 *
 *
 * Per-CPU variables.
 *
 * This module supports statically allocated per-CPU variables only. Each
 * active processor gets its own block of pages, called percpu area, where
 * percpu variables are stored. The offset of a percpu variable is fixed
 * and added to the base of the percpu area to obtain the real address of
 * the variable.
 *
 * A statically allocated percpu variable should be defined with the
 * __percpu macro, e.g. :
 *
 * struct s var __percpu;
 *
 * Obviously, the variable cannot be directly accessed. Instead, percpu
 * variables can be accessed with the following accessors :
 *  - percpu_ptr()
 *  - percpu_var()
 *
 * The cpu module is expected to provide the following accessors to access
 * percpu variables from the local processor :
 *  - cpu_local_ptr()
 *  - cpu_local_var()
 *
 * These accessors may generate optimized code.
 *
 * Architecture-specific code must enforce that the percpu section starts
 * at 0, thereby making the addresses of percpu variables offsets into the
 * percpu area. It must also make sure the _percpu and _percpu_end symbols
 * have valid virtual addresses, included between _init (but not part of
 * the init section) and _end.
 *
 * Unless otherwise specified, accessing a percpu variable is not
 * interrupt-safe.
 */

#ifndef KERN_PERCPU_H
#define KERN_PERCPU_H

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

#include <kern/init.h>
#include <kern/macros.h>
#include <kern/slist_types.h>

#define PERCPU_SECTION .percpu
#define __percpu __section(QUOTE(PERCPU_SECTION))

typedef void (*percpu_op_fn_t)(void);

/*
 * Per-CPU operation.
 *
 * These operations allow initialization code to register functions to be run
 * on APs when they're started.
 */
struct percpu_op {
    struct slist_node node;
    percpu_op_fn_t fn;
};

#define PERCPU_OP_INITIALIZER(op_fn) { .fn = op_fn }

/*
 * Boundaries of the percpu section.
 *
 * The addresses of these symbols must be valid, even if the percpu section
 * itself has different addresses.
 */
extern char _percpu;
extern char _percpu_end;

/*
 * Expands to the address of a percpu variable.
 */
#define percpu_ptr(var, cpu) \
    ((typeof(var) *)(percpu_area(cpu) + ((uintptr_t)(&(var)))))

/*
 * Expands to the lvalue of a percpu variable.
 */
#define percpu_var(var, cpu) (*(percpu_ptr(var, cpu)))

static inline void *
percpu_area(unsigned int cpu)
{
    extern void *percpu_areas[CONFIG_MAX_CPUS];
    void *area;

    assert(cpu < ARRAY_SIZE(percpu_areas));
    area = percpu_areas[cpu];
    assert(area != NULL);
    return area;
}

/*
 * Register a percpu operation to be run on all processors when
 * they're started.
 *
 * The operation is run on the BSP when it's registered. It's run as late as
 * possible on APs, normally right before scheduling is enabled.
 */
void percpu_register_op(struct percpu_op *op);

/*
 * Register a processor.
 *
 * This function creates a percpu area from kernel virtual memory for the
 * given processor. The created area is filled from the content of the
 * percpu section.
 */
int percpu_add(unsigned int cpu);

/*
 * Run registered percpu operations on an AP.
 */
void percpu_ap_setup(void);

/*
 * This init operation provides :
 *  - access to percpu variables on processor 0
 */
INIT_OP_DECLARE(percpu_bootstrap);

/*
 * This init operation provides :
 *  - percpu operations can be registered
 *  - new percpu areas can be created
 *
 * The dependency that provides access to percpu variables on all processors
 * is cpu_mp_probe.
 *
 * TODO Add percpu alias to cpu_mp_probe.
 */
INIT_OP_DECLARE(percpu_setup);

#endif /* KERN_PERCPU_H */