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

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

#include <kern/hash.h>
#include <kern/init.h>
#include <kern/log.h>
#include <kern/macros.h>
#include <kern/mutex.h>
#include <kern/printf.h>
#include <kern/shell.h>
#include <kern/shell_i.h>
#include <kern/thread.h>

#define SHELL_COMPLETION_MATCH_FMT              "-16s"
#define SHELL_COMPLETION_NR_MATCHES_PER_LINE    4

/*
 * Escape sequence states.
 *
 * Here is an incomplete description of escape sequences :
 * http://en.wikipedia.org/wiki/ANSI_escape_code
 *
 * These values must be different from 0.
 */
#define SHELL_ESC_STATE_START   1
#define SHELL_ESC_STATE_CSI     2

typedef void (*shell_esc_seq_fn)(struct shell *shell);

struct shell_esc_seq {
    const char *str;
    shell_esc_seq_fn fn;
};

#define SHELL_SEPARATOR ' '

/*
 * Commonly used backspace control characters.
 *
 * XXX Adjust for your needs.
 */
#define SHELL_ERASE_BS  '\b'
#define SHELL_ERASE_DEL '\x7f'

static const char *
shell_find_word(const char *str)
{
    for (;;) {
        if ((*str == '\0') || (*str != SHELL_SEPARATOR)) {
            break;
        }

        str++;
    }

    return str;
}

void
shell_cmd_init(struct shell_cmd *cmd, const char *name,
               shell_fn_t fn, const char *usage,
               const char *short_desc, const char *long_desc)
{
    cmd->ht_next = NULL;
    cmd->ls_next = NULL;
    cmd->name = name;
    cmd->fn = fn;
    cmd->usage = usage;
    cmd->short_desc = short_desc;
    cmd->long_desc = long_desc;
}

static const char *
shell_cmd_name(const struct shell_cmd *cmd)
{
    return cmd->name;
}

static int
shell_cmd_check_char(char c)
{
    if (((c >= 'a') && (c <= 'z'))
        || ((c >= 'A') && (c <= 'Z'))
        || ((c >= '0') && (c <= '9'))
        || (c == '-')
        || (c == '_')) {
        return 0;
    }

    return EINVAL;
}

static int
shell_cmd_check(const struct shell_cmd *cmd)
{
    size_t len;
    int error;

    len = strlen(cmd->name);

    if (len == 0) {
        return EINVAL;
    }

    for (size_t i = 0; i < len; i++) {
        error = shell_cmd_check_char(cmd->name[i]);

        if (error) {
            return error;
        }
    }

    return 0;
}

static const char *
shell_line_str(const struct shell_line *line)
{
    return line->str;
}

static size_t
shell_line_size(const struct shell_line *line)
{
    return line->size;
}

static void
shell_line_reset(struct shell_line *line)
{
    line->str[0] = '\0';
    line->size = 0;
}

static void
shell_line_copy(struct shell_line *dest, const struct shell_line *src)
{
    strcpy(dest->str, src->str);
    dest->size = src->size;
}

static int
shell_line_cmp(const struct shell_line *a, const struct shell_line *b)
{
    return strcmp(a->str, b->str);
}

static int
shell_line_insert(struct shell_line *line, size_t index, char c)
{
    size_t remaining_chars;

    if (index > line->size) {
        return EINVAL;
    }

    if ((line->size + 1) == sizeof(line->str)) {
        return ENOMEM;
    }

    remaining_chars = line->size - index;

    if (remaining_chars != 0) {
        memmove(&line->str[index + 1], &line->str[index], remaining_chars);
    }

    line->str[index] = c;
    line->size++;
    line->str[line->size] = '\0';
    return 0;
}

static int
shell_line_erase(struct shell_line *line, size_t index)
{
    size_t remaining_chars;

    if (index >= line->size) {
        return EINVAL;
    }

    remaining_chars = line->size - index - 1;

    if (remaining_chars != 0) {
        memmove(&line->str[index], &line->str[index + 1], remaining_chars);
    }

    line->size--;
    line->str[line->size] = '\0';
    return 0;
}

static struct shell_line *
shell_history_get(struct shell_history *history, size_t index)
{
    return &history->lines[index % ARRAY_SIZE(history->lines)];
}

static void
shell_history_init(struct shell_history *history)
{
    for (size_t i = 0; i < ARRAY_SIZE(history->lines); i++) {
        shell_line_reset(shell_history_get(history, i));
    }

    history->newest = 0;
    history->oldest = 0;
    history->index = 0;
}

static struct shell_line *
shell_history_get_newest(struct shell_history *history)
{
    return shell_history_get(history, history->newest);
}

static struct shell_line *
shell_history_get_index(struct shell_history *history)
{
    return shell_history_get(history, history->index);
}

static void
shell_history_reset_index(struct shell_history *history)
{
    history->index = history->newest;
}

static int
shell_history_same_newest(struct shell_history *history)
{
    return (history->newest != history->oldest)
           && (shell_line_cmp(shell_history_get_newest(history),
                              shell_history_get(history, history->newest - 1))
               == 0);
}

static void
shell_history_push(struct shell_history *history)
{
    if ((shell_line_size(shell_history_get_newest(history)) == 0)
        || shell_history_same_newest(history)) {
        shell_history_reset_index(history);
        return;
    }

    history->newest++;
    shell_history_reset_index(history);

    /* Mind integer overflows */
    if ((history->newest - history->oldest) >= ARRAY_SIZE(history->lines)) {
        history->oldest = history->newest - ARRAY_SIZE(history->lines) + 1;
    }
}

static void
shell_history_back(struct shell_history *history)
{
    if (history->index == history->oldest) {
        return;
    }

    history->index--;
    shell_line_copy(shell_history_get_newest(history),
                    shell_history_get_index(history));
}

static void
shell_history_forward(struct shell_history *history)
{
    if (history->index == history->newest) {
        return;
    }

    history->index++;

    if (history->index == history->newest) {
        shell_line_reset(shell_history_get_newest(history));
    } else {
        shell_line_copy(shell_history_get_newest(history),
                        shell_history_get_index(history));
    }
}

static void
shell_history_print(struct shell_history *history, struct shell *shell)
{
    const struct shell_line *line;

    /* Mind integer overflows */
    for (size_t i = history->oldest; i != history->newest; i++) {
        line = shell_history_get(history, i);
        shell_printf(shell, "%6lu  %s\n",
                     (unsigned long)(i - history->oldest),
                     shell_line_str(line));
    }
}

static void
shell_cmd_set_lock(struct shell_cmd_set *cmd_set)
{
    mutex_lock(&cmd_set->lock);
}

static void
shell_cmd_set_unlock(struct shell_cmd_set *cmd_set)
{
    mutex_unlock(&cmd_set->lock);
}

static struct shell_bucket *
shell_cmd_set_get_bucket(struct shell_cmd_set *cmd_set, const char *name)
{
    size_t index;

    index = hash_str(name, SHELL_HTABLE_BITS);
    assert(index < ARRAY_SIZE(cmd_set->htable));
    return &cmd_set->htable[index];
}

static const struct shell_cmd *
shell_cmd_set_lookup(struct shell_cmd_set *cmd_set, const char *name)
{
    const struct shell_bucket *bucket;
    const struct shell_cmd *cmd;

    shell_cmd_set_lock(cmd_set);

    bucket = shell_cmd_set_get_bucket(cmd_set, name);

    for (cmd = bucket->cmd; cmd != NULL; cmd = cmd->ht_next) {
        if (strcmp(cmd->name, name) == 0) {
            break;
        }
    }

    shell_cmd_set_unlock(cmd_set);

    return cmd;
}

/*
 * Look up the first command that matches a given string.
 *
 * The input string is defined by the given string pointer and size.
 *
 * The global lock must be acquired before calling this function.
 */
static const struct shell_cmd *
shell_cmd_set_match(const struct shell_cmd_set *cmd_set, const char *str,
                    size_t size)
{
    const struct shell_cmd *cmd;

    cmd = cmd_set->cmd_list;

    while (cmd != NULL) {
        if (strncmp(cmd->name, str, size) == 0) {
            return cmd;
        }

        cmd = cmd->ls_next;
    }

    return NULL;
}

/*
 * Attempt command auto-completion.
 *
 * The given string is the beginning of a command, or the empty string.
 * The sizep parameter initially points to the size of the given string.
 * If the string matches any registered command, the cmdp pointer is
 * updated to point to the first matching command in the sorted list of
 * commands, and sizep is updated to the number of characters in the
 * command name that are common in subsequent commands. The command
 * pointer and the returned size can be used to print a list of commands
 * eligible for completion.
 *
 * If there is a single match for the given string, return 0. If there
 * are more than one match, return EAGAIN. If there is no match,
 * return EINVAL.
 */
static int
shell_cmd_set_complete(struct shell_cmd_set *cmd_set, const char *str,
                       size_t *sizep, const struct shell_cmd **cmdp)
{
    const struct shell_cmd *cmd, *next;
    size_t size;

    size = *sizep;

    /*
     * Start with looking up a command that matches the given argument.
     * If there is no match, return an error.
     */
    cmd = shell_cmd_set_match(cmd_set, str, size);

    if (cmd == NULL) {
        return EINVAL;
    }

    *cmdp = cmd;

    /*
     * If at least one command matches, try to complete it.
     * There can be two cases :
     * 1/ There is one and only one match, which is directly returned.
     * 2/ There are several matches, in which case the common length is
     *    computed.
     */
    next = cmd->ls_next;

    if ((next == NULL) || (strncmp(cmd->name, next->name, size) != 0)) {
        *sizep = strlen(cmd->name);
        return 0;
    }

    /*
     * When computing the common length, all the commands that can match
     * must be evaluated. Considering the current command is the first
     * that can match, the only other variable missing is the last
     * command that can match.
     */
    while (next->ls_next != NULL) {
        if (strncmp(cmd->name, next->ls_next->name, size) != 0) {
            break;
        }

        next = next->ls_next;
    }

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

    while ((cmd->name[size - 1] != '\0')
           && (cmd->name[size - 1] == next->name[size - 1])) {
        size++;
    }

    size--;
    *sizep = size;
    return EAGAIN;
}

struct shell_cmd_set *
shell_get_cmd_set(struct shell *shell)
{
    return shell->cmd_set;
}

static struct shell_history *
shell_get_history(struct shell *shell)
{
    return &shell->history;
}

static void
shell_cb_help(struct shell *shell, int argc, char *argv[])
{
    struct shell_cmd_set *cmd_set;
    const struct shell_cmd *cmd;

    cmd_set = shell_get_cmd_set(shell);

    if (argc > 2) {
        argc = 2;
        argv[1] = "help";
    }

    if (argc == 2) {
        cmd = shell_cmd_set_lookup(cmd_set, argv[1]);

        if (cmd == NULL) {
            shell_printf(shell, "shell: help: %s: command not found\n",
                         argv[1]);
            return;
        }

        shell_printf(shell, "usage: %s\n%s\n", cmd->usage, cmd->short_desc);

        if (cmd->long_desc != NULL) {
            shell_printf(shell, "\n%s\n", cmd->long_desc);
        }

        return;
    }

    shell_cmd_set_lock(cmd_set);

    for (cmd = cmd_set->cmd_list; cmd != NULL; cmd = cmd->ls_next) {
        shell_printf(shell, "%19s  %s\n", cmd->name, cmd->short_desc);
    }

    shell_cmd_set_unlock(cmd_set);
}

static void
shell_cb_history(struct shell *shell, int argc, char *argv[])
{
    (void)argc;
    (void)argv;

    shell_history_print(shell_get_history(shell), shell);
}

static struct shell_cmd shell_default_cmds[] = {
    SHELL_CMD_INITIALIZER("help", shell_cb_help,
                          "help [command]",
                          "obtain help about shell commands"),
    SHELL_CMD_INITIALIZER("history", shell_cb_history,
                          "history",
                          "display history list"),
};

void
shell_cmd_set_init(struct shell_cmd_set *cmd_set)
{
    mutex_init(&cmd_set->lock);
    memset(cmd_set->htable, 0, sizeof(cmd_set->htable));
    cmd_set->cmd_list = NULL;
    SHELL_REGISTER_CMDS(shell_default_cmds, cmd_set);
}

static int
shell_cmd_set_add_htable(struct shell_cmd_set *cmd_set, struct shell_cmd *cmd)
{
    struct shell_bucket *bucket;
    struct shell_cmd *tmp;

    bucket = shell_cmd_set_get_bucket(cmd_set, cmd->name);
    tmp = bucket->cmd;

    if (tmp == NULL) {
        bucket->cmd = cmd;
        return 0;
    }

    for (;;) {
        if (strcmp(cmd->name, tmp->name) == 0) {
            return EEXIST;
        }

        if (tmp->ht_next == NULL) {
            break;
        }

        tmp = tmp->ht_next;
    }

    tmp->ht_next = cmd;
    return 0;
}

static void
shell_cmd_set_add_list(struct shell_cmd_set *cmd_set, struct shell_cmd *cmd)
{
    struct shell_cmd *prev, *next;

    prev = cmd_set->cmd_list;

    if ((prev == NULL) || (strcmp(cmd->name, prev->name) < 0)) {
        cmd_set->cmd_list = cmd;
        cmd->ls_next = prev;
        return;
    }

    for (;;) {
        next = prev->ls_next;

        if ((next == NULL) || (strcmp(cmd->name, next->name) < 0)) {
            break;
        }

        prev = next;
    }

    prev->ls_next = cmd;
    cmd->ls_next = next;
}

static int
shell_cmd_set_add(struct shell_cmd_set *cmd_set, struct shell_cmd *cmd)
{
    int error;

    error = shell_cmd_set_add_htable(cmd_set, cmd);

    if (error) {
        return error;
    }

    shell_cmd_set_add_list(cmd_set, cmd);
    return 0;
}

int
shell_cmd_set_register(struct shell_cmd_set *cmd_set, struct shell_cmd *cmd)
{
    int error;

    error = shell_cmd_check(cmd);

    if (error) {
        return error;
    }

    shell_cmd_set_lock(cmd_set);
    error = shell_cmd_set_add(cmd_set, cmd);
    shell_cmd_set_unlock(cmd_set);

    return error;
}

void
shell_init(struct shell *shell, struct shell_cmd_set *cmd_set,
           shell_getc_fn_t getc_fn, shell_vfprintf_fn_t vfprintf_fn,
           void *io_object)
{
    shell->cmd_set = cmd_set;
    shell->getc_fn = getc_fn;
    shell->vfprintf_fn = vfprintf_fn;
    shell->io_object = io_object;
    shell_history_init(&shell->history);
    shell->esc_seq_index = 0;
}

static void
shell_prompt(struct shell *shell)
{
    shell_printf(shell, "shell> ");
}

static void
shell_reset(struct shell *shell)
{
    shell_line_reset(shell_history_get_newest(&shell->history));
    shell->cursor = 0;
    shell_prompt(shell);
}

static void
shell_erase(struct shell *shell)
{
    struct shell_line *current_line;
    size_t remaining_chars;

    current_line = shell_history_get_newest(&shell->history);
    remaining_chars = shell_line_size(current_line);

    while (shell->cursor != remaining_chars) {
        shell_printf(shell, " ");
        shell->cursor++;
    }

    while (remaining_chars != 0) {
        shell_printf(shell, "\b \b");
        remaining_chars--;
    }

    shell->cursor = 0;
}

static void
shell_restore(struct shell *shell)
{
    struct shell_line *current_line;

    current_line = shell_history_get_newest(&shell->history);
    shell_printf(shell, "%s", shell_line_str(current_line));
    shell->cursor = shell_line_size(current_line);
}

static int
shell_is_ctrl_char(char c)
{
    return ((c < ' ') || (c >= 0x7f));
}

static void
shell_process_left(struct shell *shell)
{
    if (shell->cursor == 0) {
        return;
    }

    shell->cursor--;
    shell_printf(shell, "\e[1D");
}

static int
shell_process_right(struct shell *shell)
{
    size_t size;

    size = shell_line_size(shell_history_get_newest(&shell->history));

    if (shell->cursor >= size) {
        return EAGAIN;
    }

    shell->cursor++;
    shell_printf(shell, "\e[1C");
    return 0;
}

static void
shell_process_up(struct shell *shell)
{
    shell_erase(shell);
    shell_history_back(&shell->history);
    shell_restore(shell);
}

static void
shell_process_down(struct shell *shell)
{
    shell_erase(shell);
    shell_history_forward(&shell->history);
    shell_restore(shell);
}

static void
shell_process_backspace(struct shell *shell)
{
    struct shell_line *current_line;
    size_t remaining_chars;
    int error;

    current_line = shell_history_get_newest(&shell->history);
    error = shell_line_erase(current_line, shell->cursor - 1);

    if (error) {
        return;
    }

    shell->cursor--;
    shell_printf(shell, "\b%s ", shell_line_str(current_line) + shell->cursor);
    remaining_chars = shell_line_size(current_line) - shell->cursor + 1;

    while (remaining_chars != 0) {
        shell_printf(shell, "\b");
        remaining_chars--;
    }
}

static int
shell_process_raw_char(struct shell *shell, char c)
{
    struct shell_line *current_line;
    size_t remaining_chars;
    int error;

    current_line = shell_history_get_newest(&shell->history);
    error = shell_line_insert(current_line, shell->cursor, c);

    if (error) {
        shell_printf(shell, "\nshell: line too long\n");
        return error;
    }

    shell->cursor++;

    if (shell->cursor == shell_line_size(current_line)) {
        shell_printf(shell, "%c", c);
        goto out;
    }

    /*
     * This assumes that the backspace character only moves the cursor
     * without erasing characters.
     */
    shell_printf(shell, "%s", shell_line_str(current_line) + shell->cursor - 1);
    remaining_chars = shell_line_size(current_line) - shell->cursor;

    while (remaining_chars != 0) {
        shell_printf(shell, "\b");
        remaining_chars--;
    }

out:
    return 0;
}

/*
 * Print a list of commands eligible for completion, starting at the
 * given command. Other eligible commands share the same prefix, as
 * defined by the size argument.
 *
 * The global lock must be acquired before calling this function.
 */
static void
shell_print_cmd_matches(struct shell *shell, const struct shell_cmd *cmd,
                        unsigned long size)
{
    const struct shell_cmd *tmp;
    unsigned int i;

    shell_printf(shell, "\n");

    for (tmp = cmd, i = 1; tmp != NULL; tmp = tmp->ls_next, i++) {
        if (strncmp(cmd->name, tmp->name, size) != 0) {
            break;
        }

        shell_printf(shell, "%" SHELL_COMPLETION_MATCH_FMT, tmp->name);

        if ((i % SHELL_COMPLETION_NR_MATCHES_PER_LINE) == 0) {
            shell_printf(shell, "\n");
        }
    }

    if ((i % SHELL_COMPLETION_NR_MATCHES_PER_LINE) != 1) {
        shell_printf(shell, "\n");
    }
}

static int
shell_process_tabulation(struct shell *shell)
{
    struct shell_cmd_set *cmd_set;
    const struct shell_cmd *cmd = NULL; /* GCC */
    const char *name, *str, *word;
    size_t size, cmd_cursor;
    int error;

    cmd_set = shell->cmd_set;

    shell_cmd_set_lock(cmd_set);

    str = shell_line_str(shell_history_get_newest(&shell->history));
    word = shell_find_word(str);
    size = shell->cursor - (word - str);
    cmd_cursor = shell->cursor - size;

    error = shell_cmd_set_complete(cmd_set, word, &size, &cmd);

    if (error && (error != EAGAIN)) {
        error = 0;
        goto out;
    }

    if (error == EAGAIN) {
        size_t cursor;

        cursor = shell->cursor;
        shell_print_cmd_matches(shell, cmd, size);
        shell_prompt(shell);
        shell_restore(shell);

        /* Keep existing arguments as they are */
        while (shell->cursor != cursor) {
            shell_process_left(shell);
        }
    }

    name = shell_cmd_name(cmd);

    while (shell->cursor != cmd_cursor) {
        shell_process_backspace(shell);
    }

    for (size_t i = 0; i < size; i++) {
        error = shell_process_raw_char(shell, name[i]);

        if (error) {
            goto out;
        }
    }

    error = 0;

out:
    shell_cmd_set_unlock(cmd_set);
    return error;
}

static void
shell_esc_seq_up(struct shell *shell)
{
    shell_process_up(shell);
}

static void
shell_esc_seq_down(struct shell *shell)
{
    shell_process_down(shell);
}

static void
shell_esc_seq_next(struct shell *shell)
{
    shell_process_right(shell);
}

static void
shell_esc_seq_prev(struct shell *shell)
{
    shell_process_left(shell);
}

static void
shell_esc_seq_home(struct shell *shell)
{
    while (shell->cursor != 0) {
        shell_process_left(shell);
    }
}

static void
shell_esc_seq_del(struct shell *shell)
{
    int error;

    error = shell_process_right(shell);

    if (error) {
        return;
    }

    shell_process_backspace(shell);
}

static void
shell_esc_seq_end(struct shell *shell)
{
    size_t size;

    size = shell_line_size(shell_history_get_newest(&shell->history));

    while (shell->cursor < size) {
        shell_process_right(shell);
    }
}

static const struct shell_esc_seq shell_esc_seqs[] = {
    {  "A", shell_esc_seq_up    },
    {  "B", shell_esc_seq_down  },
    {  "C", shell_esc_seq_next  },
    {  "D", shell_esc_seq_prev  },
    {  "H", shell_esc_seq_home  },
    { "1~", shell_esc_seq_home  },
    { "3~", shell_esc_seq_del   },
    {  "F", shell_esc_seq_end   },
    { "4~", shell_esc_seq_end   },
};

static const struct shell_esc_seq *
shell_esc_seq_lookup(const char *str)
{
    for (size_t i = 0; i < ARRAY_SIZE(shell_esc_seqs); i++) {
        if (strcmp(shell_esc_seqs[i].str, str) == 0) {
            return &shell_esc_seqs[i];
        }
    }

    return NULL;
}

/*
 * Process a single escape sequence character.
 *
 * Return the next escape state or 0 if the sequence is complete.
 */
static int
shell_process_esc_sequence(struct shell *shell, char c)
{
    const struct shell_esc_seq *seq;

    if (shell->esc_seq_index >= (ARRAY_SIZE(shell->esc_seq) - 1)) {
        shell_printf(shell, "shell: escape sequence too long\n");
        goto reset;
    }

    shell->esc_seq[shell->esc_seq_index] = c;
    shell->esc_seq_index++;
    shell->esc_seq[shell->esc_seq_index] = '\0';

    if ((c >= '@') && (c <= '~')) {
        seq = shell_esc_seq_lookup(shell->esc_seq);

        if (seq != NULL) {
            seq->fn(shell);
        }

        goto reset;
    }

    return SHELL_ESC_STATE_CSI;

reset:
    shell->esc_seq_index = 0;
    return 0;
}

static int
shell_process_args(struct shell *shell)
{
    char c, prev;
    size_t i;
    int j;

    snprintf(shell->tmp_line, sizeof(shell->tmp_line), "%s",
             shell_line_str(shell_history_get_newest(&shell->history)));

    for (i = 0, j = 0, prev = SHELL_SEPARATOR;
         (c = shell->tmp_line[i]) != '\0';
         i++, prev = c) {
        if (c == SHELL_SEPARATOR) {
            if (prev != SHELL_SEPARATOR) {
                shell->tmp_line[i] = '\0';
            }
        } else {
            if (prev == SHELL_SEPARATOR) {
                shell->argv[j] = &shell->tmp_line[i];
                j++;

                if (j == ARRAY_SIZE(shell->argv)) {
                    shell_printf(shell, "shell: too many arguments\n");
                    return EINVAL;
                }

                shell->argv[j] = NULL;
            }
        }
    }

    shell->argc = j;
    return 0;
}

static void
shell_process_line(struct shell *shell)
{
    const struct shell_cmd *cmd;
    int error;

    cmd = NULL;
    error = shell_process_args(shell);

    if (error) {
        goto out;
    }

    if (shell->argc == 0) {
        goto out;
    }

    cmd = shell_cmd_set_lookup(shell->cmd_set, shell->argv[0]);

    if (cmd == NULL) {
        shell_printf(shell, "shell: %s: command not found\n", shell->argv[0]);
        goto out;
    }

out:
    shell_history_push(&shell->history);

    if (cmd != NULL) {
        cmd->fn(shell, shell->argc, shell->argv);
    }
}

/*
 * Process a single control character.
 *
 * Return an error if the caller should reset the current line state.
 */
static int
shell_process_ctrl_char(struct shell *shell, char c)
{
    switch (c) {
    case SHELL_ERASE_BS:
    case SHELL_ERASE_DEL:
        shell_process_backspace(shell);
        break;
    case '\t':
        return shell_process_tabulation(shell);
    case '\n':
    case '\r':
        shell_printf(shell, "\n");
        shell_process_line(shell);
        return EAGAIN;
    default:
        return 0;
    }

    return 0;
}

void
shell_run(struct shell *shell)
{
    int c, error, escape;

    for (;;) {
        shell_reset(shell);
        escape = 0;

        for (;;) {
            c = shell->getc_fn(shell->io_object);

            if (escape) {
                switch (escape) {
                case SHELL_ESC_STATE_START:
                    /* XXX CSI and SS3 sequence processing is the same */
                    if ((c == '[') || (c == 'O')) {
                        escape = SHELL_ESC_STATE_CSI;
                    } else {
                        escape = 0;
                    }

                    break;
                case SHELL_ESC_STATE_CSI:
                    escape = shell_process_esc_sequence(shell, c);
                    break;
                default:
                    escape = 0;
                }

                error = 0;
            } else if (shell_is_ctrl_char(c)) {
                if (c == '\e') {
                    escape = SHELL_ESC_STATE_START;
                    error = 0;
                } else {
                    error = shell_process_ctrl_char(shell, c);

                    if (error) {
                        break;
                    }
                }
            } else {
                error = shell_process_raw_char(shell, c);
            }

            if (error) {
                break;
            }
        }
    }
}

void
shell_printf(struct shell *shell, const char *format, ...)
{
    va_list ap;

    va_start(ap, format);
    shell_vprintf(shell, format, ap);
    va_end(ap);
}

void
shell_vprintf(struct shell *shell, const char *format, va_list ap)
{
    shell->vfprintf_fn(shell->io_object, format, ap);
}

/*
 * XXX Temporary glue until the console module is reworked.
 */

static struct shell_cmd_set shell_main_cmd_set;
static struct shell shell_main;

static int
shell_main_getc(void *io_object)
{
    (void)io_object;
    return getchar();
}

static void
shell_main_vfprintf(void *io_object, const char *format, va_list ap)
{
    (void)io_object;
    vprintf(format, ap);
}

static int __init
shell_setup(void)
{
    shell_cmd_set_init(&shell_main_cmd_set);
    shell_init(&shell_main, &shell_main_cmd_set,
               shell_main_getc, shell_main_vfprintf, NULL);
    return 0;
}

INIT_OP_DEFINE(shell_setup,
               INIT_OP_DEP(log_setup, true),
               INIT_OP_DEP(mutex_setup, true),
               INIT_OP_DEP(printf_setup, true));

struct shell_cmd_set * __init
shell_get_main_cmd_set(void)
{
    return &shell_main_cmd_set;
}

static void
shell_main_run(void *arg)
{
    shell_run(arg);
}

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

    thread_attr_init(&attr, THREAD_KERNEL_PREFIX "shell");
    thread_attr_set_detached(&attr);
    error = thread_create(&thread, &attr, shell_main_run, &shell_main);
    error_check(error, "thread_create");
}


code:
/*
 * Copyright (c) 2015-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/
 *
 *
 * Minimalist shell for embedded systems.
 */

#ifndef KERN_SHELL_H
#define KERN_SHELL_H

#include <stdarg.h>
#include <stddef.h>

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

/*
 * Types for I/O functions.
 */
typedef int (*shell_getc_fn_t)(void *io_object);
typedef void (*shell_vfprintf_fn_t)(void *io_object,
                                    const char *format, va_list ap);

/*
 * Shell structure, statically allocatable.
 */
struct shell;

/*
 * Shell command structure.
 */
struct shell_cmd;

/*
 * Command container, shareable across multiple shell instances.
 */
struct shell_cmd_set;

/*
 * Type for command implementation callbacks.
 */
typedef void (*shell_fn_t)(struct shell *shell, int argc, char **argv);

#include <kern/shell_i.h>

#define SHELL_REGISTER_CMDS(cmds, cmd_set)                              \
MACRO_BEGIN                                                             \
    size_t i_;                                                          \
    int error_;                                                         \
                                                                        \
    for (i_ = 0; i_ < ARRAY_SIZE(cmds); i_++) {                         \
        error_ = shell_cmd_set_register(cmd_set, &(cmds)[i_]);          \
        error_check(error_, __func__);                                  \
    }                                                                   \
MACRO_END

/*
 * Static shell command initializers.
 */
#define SHELL_CMD_INITIALIZER(name, fn, usage, short_desc) \
    { NULL, NULL, name, fn, usage, short_desc, NULL }
#define SHELL_CMD_INITIALIZER2(name, fn, usage, short_desc, long_desc) \
    { NULL, NULL, name, fn, usage, short_desc, long_desc }

/*
 * Initialize a shell command structure.
 */
void shell_cmd_init(struct shell_cmd *cmd, const char *name,
                    shell_fn_t fn, const char *usage,
                    const char *short_desc, const char *long_desc);

/*
 * Initialize a command set.
 */
void shell_cmd_set_init(struct shell_cmd_set *cmd_set);

/*
 * Register a shell command.
 *
 * The command name must be unique. It must not include characters outside
 * the [a-zA-Z0-9-_] class.
 *
 * Commands may safely be registered while the command set is used.
 *
 * The command structure must persist in memory as long as the command set
 * is used.
 */
int shell_cmd_set_register(struct shell_cmd_set *cmd_set,
                           struct shell_cmd *cmd);

/*
 * Initialize a shell instance.
 *
 * On return, shell commands can be registered.
 */
void shell_init(struct shell *shell, struct shell_cmd_set *cmd_set,
                shell_getc_fn_t getc_fn, shell_vfprintf_fn_t vfprintf_fn,
                void *io_object);

/*
 * Run the shell.
 *
 * This function doesn't return.
 */
void shell_run(struct shell *shell);

/*
 * Obtain the command set associated with a shell.
 */
struct shell_cmd_set * shell_get_cmd_set(struct shell *shell);

/*
 * Printf-like functions specific to the given shell instance.
 */
void shell_printf(struct shell *shell, const char *format, ...)
    __attribute__((format(printf, 2, 3)));
void shell_vprintf(struct shell *shell, const char *format, va_list ap)
    __attribute__((format(printf, 2, 0)));

/*
 * This init operation provides :
 *  - main shell command registration
 */
INIT_OP_DECLARE(shell_setup);

struct shell_cmd_set * shell_get_main_cmd_set(void);
void shell_start(void);

#endif /* KERN_SHELL_H */

license: mit


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

#ifndef KERN_SHELL_I_H
#define KERN_SHELL_I_H

#include <stddef.h>

#include <kern/macros.h>
#include <kern/mutex.h>

struct shell_cmd {
    struct shell_cmd *ht_next;
    struct shell_cmd *ls_next;
    const char *name;
    shell_fn_t fn;
    const char *usage;
    const char *short_desc;
    const char *long_desc;
};

struct shell_bucket {
    struct shell_cmd *cmd;
};

/*
 * Binary exponent and size of the hash table used to store commands.
 */
#define SHELL_HTABLE_BITS   6
#define SHELL_HTABLE_SIZE   (1 << SHELL_HTABLE_BITS)

/*
 * The command list is sorted.
 */
struct shell_cmd_set {
    struct mutex lock;
    struct shell_bucket htable[SHELL_HTABLE_SIZE];
    struct shell_cmd *cmd_list;
};

#define SHELL_LINE_MAX_SIZE 64

/*
 * Line containing a shell entry.
 *
 * The string must be nul-terminated. The size doesn't include this
 * additional nul character, the same way strlen() doesn't account for it.
 */
struct shell_line {
    char str[SHELL_LINE_MAX_SIZE];
    size_t size;
};

/*
 * Number of entries in the history.
 *
 * One of these entryes is used as the current line.
 */
#define SHELL_HISTORY_SIZE 21

#if SHELL_HISTORY_SIZE == 0
#error "shell history size must be non-zero"
#endif /* SHELL_HISTORY_SIZE == 0 */

/*
 * Shell history.
 *
 * The history is never empty. There is always at least one entry, the
 * current line, referenced by the newest (most recent) index. The array
 * is used like a circular buffer, i.e. old entries are implicitely
 * erased by new ones. The index references the entry used as a template
 * for the current line.
 */
struct shell_history {
    struct shell_line lines[SHELL_HISTORY_SIZE];
    size_t newest;
    size_t oldest;
    size_t index;
};

/*
 * This value changes depending on the standard used and was chosen arbitrarily.
 */
#define SHELL_ESC_SEQ_MAX_SIZE 8

#define SHELL_MAX_ARGS 16

/*
 * Shell structure.
 *
 * A shell instance can include temporary variables to minimize stack usage.
 */
struct shell {
    struct shell_cmd_set *cmd_set;

    shell_getc_fn_t getc_fn;
    shell_vfprintf_fn_t vfprintf_fn;
    void *io_object;

    struct shell_history history;

    /* Cursor within the current line */
    size_t cursor;

    /* Members used for escape sequence parsing */
    char esc_seq[SHELL_ESC_SEQ_MAX_SIZE];
    size_t esc_seq_index;

    /*
     * Buffer used to store the current line during argument processing.
     *
     * The pointers in the argv array point inside this buffer. The
     * separators immediately following the arguments are replaced with
     * null characters.
     */
    char tmp_line[SHELL_LINE_MAX_SIZE];

    int argc;
    char *argv[SHELL_MAX_ARGS];
};

#endif /* KERN_SHELL_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/>.
 */

#include <stdio.h>

#include <kern/init.h>
#include <kern/plist.h>
#include <kern/shell.h>
#include <kern/shutdown.h>
#include <machine/boot.h>
#include <machine/cpu.h>

static struct plist shutdown_ops_list;

#ifdef CONFIG_SHELL

static void
shutdown_shell_halt(struct shell *shell, int argc, char **argv)
{
    (void)shell;
    (void)argc;
    (void)argv;

    shutdown_halt();
}

static void
shutdown_shell_reboot(struct shell *shell, int argc, char **argv)
{
    (void)shell;
    (void)argc;
    (void)argv;

    shutdown_reboot();
}

static struct shell_cmd shutdown_shell_cmds[] = {
    SHELL_CMD_INITIALIZER("shutdown_halt", shutdown_shell_halt,
        "shutdown_halt",
        "halt the system"),
    SHELL_CMD_INITIALIZER("shutdown_reboot", shutdown_shell_reboot,
        "shutdown_reboot",
        "reboot the system"),
};

static int __init
shutdown_setup_shell(void)
{
    SHELL_REGISTER_CMDS(shutdown_shell_cmds, shell_get_main_cmd_set());
    return 0;
}

INIT_OP_DEFINE(shutdown_setup_shell,
               INIT_OP_DEP(shell_setup, true),
               INIT_OP_DEP(shutdown_setup, true));

#endif /* CONFIG_SHELL */

static int __init
shutdown_bootstrap(void)
{
    plist_init(&shutdown_ops_list);
    return 0;
}

INIT_OP_DEFINE(shutdown_bootstrap);

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

INIT_OP_DEFINE(shutdown_setup,
               INIT_OP_DEP(boot_setup_shutdown, true),
               INIT_OP_DEP(cpu_setup, true),
               INIT_OP_DEP(printf_setup, true),
               INIT_OP_DEP(shutdown_bootstrap, true));

void __init
shutdown_register(struct shutdown_ops *ops, unsigned int priority)
{
    plist_node_init(&ops->node, priority);
    plist_add(&shutdown_ops_list, &ops->node);
}

static void
shutdown_halt_other_cpus(void)
{
    cpu_intr_disable();
    cpu_halt_broadcast();
}

void
shutdown_halt(void)
{
    shutdown_halt_other_cpus();
    printf("shutdown: system halted\n");
    cpu_halt();
}

void
shutdown_reboot(void)
{
    struct shutdown_ops *ops;

    if (plist_empty(&shutdown_ops_list)) {
        printf("shutdown: no reset operation available, halting\n");
        shutdown_halt();
    }

    shutdown_halt_other_cpus();
    printf("shutdown: rebooting...\n");

    plist_for_each_entry_reverse(&shutdown_ops_list, ops, node) {
        ops->reset();
    }

    cpu_halt();
}


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_SHUTDOWN_H
#define KERN_SHUTDOWN_H

#include <stdnoreturn.h>

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

struct shutdown_ops {
    struct plist_node node;
    void (*reset)(void);
};

void shutdown_register(struct shutdown_ops *ops, unsigned int priority);

noreturn void shutdown_halt(void);
noreturn void shutdown_reboot(void);

/*
 * This init operation provides :
 *  - registration of shutdown operations
 */
INIT_OP_DECLARE(shutdown_bootstrap);

/*
 * This init operation provides :
 *  - all shutdown operations have been registered
 *  - module fully initialized
 */
INIT_OP_DECLARE(shutdown_setup);

#endif /* KERN_SHUTDOWN_H */


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

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

#include <kern/hlist.h>
#include <kern/init.h>
#include <kern/kmem.h>
#include <kern/list.h>
#include <kern/macros.h>
#include <kern/sleepq.h>
#include <kern/spinlock.h>
#include <kern/thread.h>
#include <machine/cpu.h>

struct sleepq_bucket {
    alignas(CPU_L1_SIZE) struct spinlock lock;
    struct hlist sleepqs;
};

struct sleepq_waiter {
    struct list node;
    struct thread *thread;
    bool pending_wakeup;
};

/*
 * Waiters are queued in FIFO order and inserted at the head of the
 * list of waiters. The pointer to the "oldest" waiter is used as
 * a marker between threads waiting for a signal/broadcast (from the
 * beginning up to and including the oldest waiter) and threads pending
 * for wake-up (all the following threads up to the end of the list).
 */
struct sleepq {
    alignas(CPU_L1_SIZE) struct sleepq_bucket *bucket;
    struct hlist_node node;
    const void *sync_obj;
    struct list waiters;
    struct sleepq_waiter *oldest_waiter;
    struct sleepq *next_free;
};

#define SLEEPQ_HTABLE_SIZE      128
#define SLEEPQ_COND_HTABLE_SIZE 64

#if !ISP2(SLEEPQ_HTABLE_SIZE) || !ISP2(SLEEPQ_COND_HTABLE_SIZE)
#error "hash table size must be a power of two"
#endif /* !ISP2(SLEEPQ_HTABLE_SIZE) */

#define SLEEPQ_HTABLE_MASK      (SLEEPQ_HTABLE_SIZE - 1)
#define SLEEPQ_COND_HTABLE_MASK (SLEEPQ_COND_HTABLE_SIZE - 1)

static struct sleepq_bucket sleepq_htable[SLEEPQ_HTABLE_SIZE];
static struct sleepq_bucket sleepq_cond_htable[SLEEPQ_COND_HTABLE_SIZE];

static struct kmem_cache sleepq_cache;

static uintptr_t
sleepq_hash(const void *addr)
{
    return ((uintptr_t)addr >> 8) ^ (uintptr_t)addr;
}

static void
sleepq_waiter_init(struct sleepq_waiter *waiter, struct thread *thread)
{
    waiter->thread = thread;
    waiter->pending_wakeup = false;
}

static bool
sleepq_waiter_pending_wakeup(const struct sleepq_waiter *waiter)
{
    return waiter->pending_wakeup;
}

static void
sleepq_waiter_set_pending_wakeup(struct sleepq_waiter *waiter)
{
    waiter->pending_wakeup = true;
}

static void
sleepq_waiter_wakeup(struct sleepq_waiter *waiter)
{
    if (!sleepq_waiter_pending_wakeup(waiter)) {
        return;
    }

    thread_wakeup(waiter->thread);
}

static bool
sleepq_init_state_valid(const struct sleepq *sleepq)
{
    return (sleepq->bucket == NULL)
           && (sleepq->sync_obj == NULL)
           && (list_empty(&sleepq->waiters))
           && (sleepq->oldest_waiter == NULL)
           && (sleepq->next_free == NULL);
}

static void
sleepq_use(struct sleepq *sleepq, const void *sync_obj)
{
    assert(sleepq->sync_obj == NULL);
    sleepq->sync_obj = sync_obj;
}

static void
sleepq_unuse(struct sleepq *sleepq)
{
    assert(sleepq->sync_obj != NULL);
    sleepq->sync_obj = NULL;
}

static bool
sleepq_in_use(const struct sleepq *sleepq)
{
    return sleepq->sync_obj != NULL;
}

static bool
sleepq_in_use_by(const struct sleepq *sleepq, const void *sync_obj)
{
    return sleepq->sync_obj == sync_obj;
}

static void
sleepq_bucket_init(struct sleepq_bucket *bucket)
{
    spinlock_init(&bucket->lock);
    hlist_init(&bucket->sleepqs);
}

static struct sleepq_bucket *
sleepq_bucket_get_cond(const void *sync_obj)
{
    uintptr_t index;

    index = sleepq_hash(sync_obj) & SLEEPQ_COND_HTABLE_MASK;
    assert(index < ARRAY_SIZE(sleepq_cond_htable));
    return &sleepq_cond_htable[index];
}

static struct sleepq_bucket *
sleepq_bucket_get(const void *sync_obj, bool condition)
{
    uintptr_t index;

    if (condition) {
        return sleepq_bucket_get_cond(sync_obj);
    }

    index = sleepq_hash(sync_obj) & SLEEPQ_HTABLE_MASK;
    assert(index < ARRAY_SIZE(sleepq_htable));
    return &sleepq_htable[index];
}

static void
sleepq_bucket_add(struct sleepq_bucket *bucket, struct sleepq *sleepq)
{
    assert(sleepq->bucket == NULL);
    sleepq->bucket = bucket;
    hlist_insert_head(&bucket->sleepqs, &sleepq->node);
}

static void
sleepq_bucket_remove(struct sleepq_bucket *bucket, struct sleepq *sleepq)
{
    assert(sleepq->bucket == bucket);
    sleepq->bucket = NULL;
    hlist_remove(&sleepq->node);
}

static struct sleepq *
sleepq_bucket_lookup(const struct sleepq_bucket *bucket, const void *sync_obj)
{
    struct sleepq *sleepq;

    hlist_for_each_entry(&bucket->sleepqs, sleepq, node) {
        if (sleepq_in_use_by(sleepq, sync_obj)) {
            assert(sleepq->bucket == bucket);
            return sleepq;
        }
    }

    return NULL;
}

static void
sleepq_ctor(void *ptr)
{
    struct sleepq *sleepq;

    sleepq = ptr;
    sleepq->bucket = NULL;
    sleepq->sync_obj = NULL;
    list_init(&sleepq->waiters);
    sleepq->oldest_waiter = NULL;
    sleepq->next_free = NULL;
}

static int __init
sleepq_setup(void)
{
    unsigned int i;

    for (i = 0; i < ARRAY_SIZE(sleepq_htable); i++) {
        sleepq_bucket_init(&sleepq_htable[i]);
    }

    for (i = 0; i < ARRAY_SIZE(sleepq_cond_htable); i++) {
        sleepq_bucket_init(&sleepq_cond_htable[i]);
    }

    kmem_cache_init(&sleepq_cache, "sleepq", sizeof(struct sleepq),
                    CPU_L1_SIZE, sleepq_ctor, 0);
    return 0;
}

INIT_OP_DEFINE(sleepq_setup,
               INIT_OP_DEP(kmem_setup, true));

struct sleepq *
sleepq_create(void)
{
    struct sleepq *sleepq;

    sleepq = kmem_cache_alloc(&sleepq_cache);

    if (sleepq == NULL) {
        return NULL;
    }

    assert(sleepq_init_state_valid(sleepq));
    return sleepq;
}

void
sleepq_destroy(struct sleepq *sleepq)
{
    assert(sleepq_init_state_valid(sleepq));
    kmem_cache_free(&sleepq_cache, sleepq);
}

static struct sleepq *
sleepq_acquire_common(const void *sync_obj, bool condition, unsigned long *flags)
{
    struct sleepq_bucket *bucket;
    struct sleepq *sleepq;

    assert(sync_obj != NULL);

    bucket = sleepq_bucket_get(sync_obj, condition);

    if (flags) {
        spinlock_lock_intr_save(&bucket->lock, flags);
    } else {
        spinlock_lock(&bucket->lock);
    }

    sleepq = sleepq_bucket_lookup(bucket, sync_obj);

    if (sleepq == NULL) {
        if (flags) {
            spinlock_unlock_intr_restore(&bucket->lock, *flags);
        } else {
            spinlock_unlock(&bucket->lock);
        }

        return NULL;
    }

    return sleepq;
}

static struct sleepq *
sleepq_tryacquire_common(const void *sync_obj, bool condition,
                         unsigned long *flags)
{
    struct sleepq_bucket *bucket;
    struct sleepq *sleepq;
    int error;

    assert(sync_obj != NULL);

    bucket = sleepq_bucket_get(sync_obj, condition);

    if (flags) {
        error = spinlock_trylock_intr_save(&bucket->lock, flags);
    } else {
        error = spinlock_trylock(&bucket->lock);
    }

    if (error) {
        return NULL;
    }

    sleepq = sleepq_bucket_lookup(bucket, sync_obj);

    if (sleepq == NULL) {
        if (flags) {
            spinlock_unlock_intr_restore(&bucket->lock, *flags);
        } else {
            spinlock_unlock(&bucket->lock);
        }

        return NULL;
    }

    return sleepq;
}

struct sleepq *
sleepq_acquire(const void *sync_obj, bool condition)
{
    return sleepq_acquire_common(sync_obj, condition, NULL);
}

struct sleepq *
sleepq_tryacquire(const void *sync_obj, bool condition)
{
    return sleepq_tryacquire_common(sync_obj, condition, NULL);
}

void
sleepq_release(struct sleepq *sleepq)
{
    spinlock_unlock(&sleepq->bucket->lock);
}

struct sleepq *
sleepq_acquire_intr_save(const void *sync_obj, bool condition,
                         unsigned long *flags)
{
    return sleepq_acquire_common(sync_obj, condition, flags);
}

struct sleepq *
sleepq_tryacquire_intr_save(const void *sync_obj, bool condition,
                            unsigned long *flags)
{
    return sleepq_tryacquire_common(sync_obj, condition, flags);
}

void
sleepq_release_intr_restore(struct sleepq *sleepq, unsigned long flags)
{
    spinlock_unlock_intr_restore(&sleepq->bucket->lock, flags);
}

static void
sleepq_push_free(struct sleepq *sleepq, struct sleepq *free_sleepq)
{
    assert(free_sleepq->next_free == NULL);
    free_sleepq->next_free = sleepq->next_free;
    sleepq->next_free = free_sleepq;
}

static struct sleepq *
sleepq_pop_free(struct sleepq *sleepq)
{
    struct sleepq *free_sleepq;

    free_sleepq = sleepq->next_free;

    if (free_sleepq == NULL) {
        return NULL;
    }

    sleepq->next_free = free_sleepq->next_free;
    free_sleepq->next_free = NULL;
    return free_sleepq;
}

static struct sleepq *
sleepq_lend_common(const void *sync_obj, bool condition, unsigned long *flags)
{
    struct sleepq_bucket *bucket;
    struct sleepq *sleepq, *prev;

    assert(sync_obj != NULL);

    sleepq = thread_sleepq_lend();
    assert(sleepq_init_state_valid(sleepq));

    bucket = sleepq_bucket_get(sync_obj, condition);

    if (flags) {
        spinlock_lock_intr_save(&bucket->lock, flags);
    } else {
        spinlock_lock(&bucket->lock);
    }

    prev = sleepq_bucket_lookup(bucket, sync_obj);

    if (prev == NULL) {
        sleepq_use(sleepq, sync_obj);
        sleepq_bucket_add(bucket, sleepq);
    } else {
        sleepq_push_free(prev, sleepq);
        sleepq = prev;
    }

    return sleepq;
}

static void
sleepq_return_common(struct sleepq *sleepq, unsigned long *flags)
{
    struct sleepq_bucket *bucket;
    struct sleepq *free_sleepq;

    assert(sleepq_in_use(sleepq));

    bucket = sleepq->bucket;
    free_sleepq = sleepq_pop_free(sleepq);

    if (free_sleepq == NULL) {
        sleepq_bucket_remove(bucket, sleepq);
        sleepq_unuse(sleepq);
        free_sleepq = sleepq;
    }

    if (flags) {
        spinlock_unlock_intr_restore(&bucket->lock, *flags);
    } else {
        spinlock_unlock(&bucket->lock);
    }

    assert(sleepq_init_state_valid(free_sleepq));
    thread_sleepq_return(free_sleepq);
}

struct sleepq *
sleepq_lend(const void *sync_obj, bool condition)
{
    return sleepq_lend_common(sync_obj, condition, NULL);
}

void
sleepq_return(struct sleepq *sleepq)
{
    sleepq_return_common(sleepq, NULL);
}

struct sleepq *
sleepq_lend_intr_save(const void *sync_obj, bool condition,
                      unsigned long *flags)
{
    return sleepq_lend_common(sync_obj, condition, flags);
}

void
sleepq_return_intr_restore(struct sleepq *sleepq, unsigned long flags)
{
    sleepq_return_common(sleepq, &flags);
}

static void
sleepq_shift_oldest_waiter(struct sleepq *sleepq)
{
    struct list *node;

    assert(sleepq->oldest_waiter != NULL);

    node = list_prev(&sleepq->oldest_waiter->node);

    if (list_end(&sleepq->waiters, node)) {
        sleepq->oldest_waiter = NULL;
    } else {
        sleepq->oldest_waiter = list_entry(node, struct sleepq_waiter, node);
    }
}

static void
sleepq_add_waiter(struct sleepq *sleepq, struct sleepq_waiter *waiter)
{
    list_insert_head(&sleepq->waiters, &waiter->node);

    if (sleepq->oldest_waiter == NULL) {
        sleepq->oldest_waiter = waiter;
    }
}

static void
sleepq_remove_waiter(struct sleepq *sleepq, struct sleepq_waiter *waiter)
{
    if (sleepq->oldest_waiter == waiter) {
        sleepq_shift_oldest_waiter(sleepq);
    }

    list_remove(&waiter->node);
}

static struct sleepq_waiter *
sleepq_get_last_waiter(struct sleepq *sleepq)
{
    if (list_empty(&sleepq->waiters)) {
        return NULL;
    }

    return list_last_entry(&sleepq->waiters, struct sleepq_waiter, node);
}

bool
sleepq_empty(const struct sleepq *sleepq)
{
    return list_empty(&sleepq->waiters);
}

static int
sleepq_wait_common(struct sleepq *sleepq, const char *wchan,
                   bool timed, uint64_t ticks)
{
    struct sleepq_waiter waiter, *next;
    struct thread *thread;
    int error;

    thread = thread_self();
    sleepq_waiter_init(&waiter, thread);
    sleepq_add_waiter(sleepq, &waiter);

    do {
        if (!timed) {
            thread_sleep(&sleepq->bucket->lock, sleepq->sync_obj, wchan);
            error = 0;
        } else {
            error = thread_timedsleep(&sleepq->bucket->lock, sleepq->sync_obj,
                                      wchan, ticks);

            if (error) {
                if (sleepq_waiter_pending_wakeup(&waiter)) {
                    error = 0;
                } else {
                    break;
                }
            }
        }
    } while (!sleepq_waiter_pending_wakeup(&waiter));

    sleepq_remove_waiter(sleepq, &waiter);

    /*
     * Chain wake-ups here to prevent broadacasting from walking a list
     * with preemption disabled. Note that this doesn't guard against
     * the thundering herd effect for condition variables.
     */
    next = sleepq_get_last_waiter(sleepq);

    if (next) {
        sleepq_waiter_wakeup(next);
    }

    return error;
}

void
sleepq_wait(struct sleepq *sleepq, const char *wchan)
{
    int error;

    error = sleepq_wait_common(sleepq, wchan, false, 0);
    assert(!error);
}

int
sleepq_timedwait(struct sleepq *sleepq, const char *wchan, uint64_t ticks)
{
    return sleepq_wait_common(sleepq, wchan, true, ticks);
}

void
sleepq_signal(struct sleepq *sleepq)
{
    struct sleepq_waiter *waiter;

    waiter = sleepq->oldest_waiter;

    if (!waiter) {
        return;
    }

    sleepq_shift_oldest_waiter(sleepq);
    sleepq_waiter_set_pending_wakeup(waiter);
    sleepq_waiter_wakeup(waiter);
}

void
sleepq_broadcast(struct sleepq *sleepq)
{
    struct sleepq_waiter *waiter;

    waiter = sleepq->oldest_waiter;

    if (!waiter) {
        return;
    }

    sleepq->oldest_waiter = NULL;
    sleepq_waiter_set_pending_wakeup(waiter);
    sleepq_waiter_wakeup(waiter);
}


code:
/*
 * Copyright (c) 2017-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/>.
 *
 *
 * Generic sleep queues.
 *
 * Sleep queues are used to build sleeping synchronization primitives
 * such as mutexes and condition variables.
 *
 * Although the sleep queues are mostly generic, this implementation
 * relies on knowing whether a synchronization object is a condition
 * variable or not, because waiting on a condition variable unlocks
 * the associated mutex, at which point two sleep queues are locked.
 * Handling condition variable sleep queues slightly differently
 * allows preventing deadlocks while keeping overall complexity low.
 */

#ifndef KERN_SLEEPQ_H
#define KERN_SLEEPQ_H

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

#include <kern/init.h>

struct sleepq;

/*
 * Create/destroy a sleep queue.
 */
struct sleepq * sleepq_create(void);
void sleepq_destroy(struct sleepq *sleepq);

/*
 * Acquire/release a sleep queue.
 *
 * Acquiring a sleep queue serializes all access and disables preemption.
 *
 * The condition argument must be true if the synchronization object
 * is a condition variable.
 *
 * Note that, in the case of the non-blocking variant, the call may also
 * return NULL if internal state shared by unrelated synchronization
 * objects is locked.
 */
struct sleepq * sleepq_acquire(const void *sync_obj, bool condition);
struct sleepq * sleepq_tryacquire(const void *sync_obj, bool condition);
void sleepq_release(struct sleepq *sleepq);

/*
 * Versions of the sleep queue acquisition functions that also disable
 * interrupts.
 */
struct sleepq * sleepq_acquire_intr_save(const void *sync_obj,
                                         bool condition,
                                         unsigned long *flags);
struct sleepq * sleepq_tryacquire_intr_save(const void *sync_obj,
                                            bool condition,
                                            unsigned long *flags);
void sleepq_release_intr_restore(struct sleepq *sleepq,
                                 unsigned long flags);

/*
 * Lend/return a sleep queue.
 *
 * A thread lends its private sleep queue to the sleepq module in
 * order to prepare its sleep. The sleep queue obtained on lending
 * is either the thread's queue, or an already existing queue for
 * this synchronization object if another thread is waiting.
 *
 * When multiple threads are waiting on the same queue, the extra
 * queues lent are kept in an internal free list, used when threads
 * are awaken to return a queue to them.
 *
 * Note that the sleep queue returned may not be the one lent.
 *
 * The sleep queue obtained when lending is automatically acquired.
 *
 * The condition argument must be true if the synchronization object
 * is a condition variable.
 */
struct sleepq * sleepq_lend(const void *sync_obj, bool condition);
void sleepq_return(struct sleepq *sleepq);

/*
 * Versions of the sleep queue lending functions that also disable
 * interrupts.
 */
struct sleepq * sleepq_lend_intr_save(const void *sync_obj, bool condition,
                                      unsigned long *flags);
void sleepq_return_intr_restore(struct sleepq *sleepq, unsigned long flags);

/*
 * Return true if the given sleep queue has no waiters.
 *
 * The sleep queue must be acquired when calling this function.
 */
bool sleepq_empty(const struct sleepq *sleepq);

/*
 * Wait for a wake-up on the given sleep queue.
 *
 * The sleep queue must be lent when calling this function. It is
 * released and later reacquired before returning from this function.
 *
 * The calling thread is considered a waiter as long as it didn't
 * reacquire the sleep queue. This means that signalling a sleep queue
 * has no visible effect on the number of waiters until the queue is
 * released, e.g. if a single thread is waiting and another signals
 * the queue, the queue is not immediately considered empty.
 *
 * When bounding the duration of the wait, the caller must pass an absolute
 * time in ticks, and ETIMEDOUT is returned if that time is reached before
 * the sleep queue is signalled.
 */
void sleepq_wait(struct sleepq *sleepq, const char *wchan);
int sleepq_timedwait(struct sleepq *sleepq, const char *wchan, uint64_t ticks);

/*
 * Wake up a thread waiting on the given sleep queue, if any.
 *
 * The sleep queue must be acquired when calling this function.
 * A sleep queue may be signalled from interrupt context.
 *
 * Since a sleep queue must be lent (and in turn is automatically
 * acquired) when waiting, and acquired in order to signal it,
 * wake-ups are serialized and cannot be missed.
 *
 * At least one thread is awaken if any threads are waiting on the sleep
 * queue.
 *
 * Broadcasting a sleep queue wakes up all waiting threads.
 */
void sleepq_signal(struct sleepq *sleepq);
void sleepq_broadcast(struct sleepq *sleepq);

/*
 * This init operation provides :
 *  - sleepq creation
 *  - module fully initialized
 */
INIT_OP_DECLARE(sleepq_setup);

#endif /* KERN_SLEEPQ_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/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 *
 *
 * Singly-linked list.
 */

#ifndef KERN_SLIST_H
#define KERN_SLIST_H

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

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

struct slist;

struct slist_node;

/*
 * Static list initializer.
 */
#define SLIST_INITIALIZER(list) { NULL, NULL }

/*
 * Initialize a list.
 */
static inline void
slist_init(struct slist *list)
{
    list->first = NULL;
    list->last = NULL;
}

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

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

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

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

/*
 * Return true if list is empty.
 */
static inline bool
slist_empty(const struct slist *list)
{
    return list->first == NULL;
}

/*
 * Return true if list contains exactly one node.
 */
static inline bool
slist_singular(const struct slist *list)
{
    return !slist_empty(list) && (list->first == list->last);
}

/*
 * Append the nodes of list2 at the end of list1.
 *
 * After completion, list2 is stale.
 */
static inline void
slist_concat(struct slist *list1, const struct slist *list2)
{
    if (slist_empty(list2)) {
        return;
    }

    if (slist_empty(list1)) {
        list1->first = list2->first;
    } else {
        list1->last->next = list2->first;
    }

    list1->last = list2->last;
}

/*
 * Set the new head of a list.
 *
 * This function is an optimized version of :
 * list_init(&new_list);
 * list_concat(&new_list, &old_list);
 */
static inline void
slist_set_head(struct slist *new_head, const struct slist *old_head)
{
    *new_head = *old_head;
}

/*
 * Insert a node at the head of a list.
 */
static inline void
slist_insert_head(struct slist *list, struct slist_node *node)
{
    if (slist_empty(list)) {
        list->last = node;
    }

    node->next = list->first;
    list->first = node;
}

/*
 * Insert a node at the tail of a list.
 */
static inline void
slist_insert_tail(struct slist *list, struct slist_node *node)
{
    node->next = NULL;

    if (slist_empty(list)) {
        list->first = node;
    } else {
        list->last->next = node;
    }

    list->last = node;
}

/*
 * Insert a node after another node.
 *
 * The prev node must be valid.
 */
static inline void
slist_insert_after(struct slist *list, struct slist_node *node,
                   struct slist_node *prev)
{
    node->next = prev->next;
    prev->next = node;

    if (list->last == prev) {
        list->last = node;
    }
}

/*
 * Remove a node from a list.
 *
 * The prev argument must point to the node immediately preceding the target
 * node. It may safely denote the end of the given list (NULL), in which case
 * the first node is removed.
 */
static inline void
slist_remove(struct slist *list, struct slist_node *prev)
{
    struct slist_node *node;

    if (slist_end(prev)) {
        node = list->first;
        list->first = node->next;

        if (list->last == node) {
            list->last = NULL;
        }
    } else {
        node = prev->next;
        prev->next = node->next;

        if (list->last == node) {
            list->last = prev;
        }
    }
}

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

/*
 * Get the first entry of a list.
 */
#define slist_first_entry(list, type, member)                           \
MACRO_BEGIN                                                             \
    struct slist_node *first_;                                          \
                                                                        \
    first_ = (list)->first;                                             \
    slist_end(first_) ? NULL : slist_entry(first_, type, member);       \
MACRO_END

/*
 * Get the last entry of a list.
 */
#define slist_last_entry(list, type, member)                            \
MACRO_BEGIN                                                             \
    struct slist_node *last_;                                           \
                                                                        \
    last_ = (list)->last;                                               \
    slist_end(last_) ? NULL : slist_entry(last_, type, member);         \
MACRO_END

/*
 * Get the entry next to the given entry.
 */
#define slist_next_entry(entry, member)                                 \
MACRO_BEGIN                                                             \
    struct slist_node *next_;                                           \
                                                                        \
    next_ = (entry)->member.next;                                       \
    slist_end(next_)                                                    \
        ? NULL                                                          \
        : slist_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 slist_for_each(list, node)  \
for (node = slist_first(list);      \
     !slist_end(node);              \
     node = slist_next(node))

/*
 * Forge a loop to process all nodes of a list.
 */
#define slist_for_each_safe(list, node, tmp)            \
for (node = slist_first(list),                          \
     tmp = slist_end(node) ? NULL : slist_next(node);   \
     !slist_end(node);                                  \
     node = tmp,                                        \
     tmp = slist_end(node) ? NULL : slist_next(node))

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

/*
 * Forge a loop to process all entries of a list.
 */
#define slist_for_each_entry_safe(list, entry, tmp, member)             \
for (entry = slist_first_entry(list, typeof(*entry), member),           \
     tmp = (entry == NULL) ? NULL : slist_next_entry(entry, member);    \
     entry != NULL;                                                     \
     entry = tmp,                                                       \
     tmp = (entry == NULL) ? NULL : slist_next_entry(entry, member))    \

/*
 * Lockless variants
 *
 * The slist_end() function may be used from read-side critical sections.
 */

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

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

/*
 * Insert a node at the head of a list.
 */
static inline void
slist_rcu_insert_head(struct slist *list, struct slist_node *node)
{
    if (slist_empty(list)) {
        list->last = node;
    }

    node->next = list->first;
    rcu_store_ptr(list->first, node);
}

/*
 * Insert a node at the tail of a list.
 */
static inline void
slist_rcu_insert_tail(struct slist *list, struct slist_node *node)
{
    node->next = NULL;

    if (slist_empty(list)) {
        rcu_store_ptr(list->first, node);
    } else {
        rcu_store_ptr(list->last->next, node);
    }

    list->last = node;
}

/*
 * Insert a node after another node.
 *
 * The prev node must be valid.
 */
static inline void
slist_rcu_insert_after(struct slist *list, struct slist_node *node,
                          struct slist_node *prev)
{
    node->next = prev->next;
    rcu_store_ptr(prev->next, node);

    if (list->last == prev) {
        list->last = node;
    }
}

/*
 * Remove a node from a list.
 *
 * The prev argument must point to the node immediately preceding the target
 * node. It may safely denote the end of the given list, in which case the
 * first node is removed.
 */
static inline void
slist_rcu_remove(struct slist *list, struct slist_node *prev)
{
    struct slist_node *node;

    if (slist_end(prev)) {
        node = list->first;
        rcu_store_ptr(list->first, node->next);

        if (list->last == node) {
            list->last = NULL;
        }
    } else {
        node = prev->next;
        rcu_store_ptr(prev->next, node->next);

        if (list->last == node) {
            list->last = prev;
        }
    }
}

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

/*
 * Get the first entry of a list.
 */
#define slist_rcu_first_entry(list, type, member)                       \
MACRO_BEGIN                                                             \
    struct slist_node *first_;                                          \
                                                                        \
    first_ = slist_rcu_first(list);                                     \
    slist_end(first_) ? NULL : slist_entry(first_, type, member);       \
MACRO_END

/*
 * Get the entry next to the given entry.
 */
#define slist_rcu_next_entry(entry, member)                             \
MACRO_BEGIN                                                             \
    struct slist_node *next_;                                           \
                                                                        \
    next_ = slist_rcu_next(&entry->member);                             \
    slist_end(next_)                                                    \
        ? NULL                                                          \
        : slist_entry(next_, typeof(*entry), member);                   \
MACRO_END

/*
 * Forge a loop to process all nodes of a list.
 */
#define slist_rcu_for_each(list, node)      \
for (node = slist_rcu_first(list);          \
     !slist_end(node);                      \
     node = slist_rcu_next(node))

/*
 * Forge a loop to process all entries of a list.
 */
#define slist_rcu_for_each_entry(list, entry, member)                   \
for (entry = slist_rcu_first_entry(list, typeof(*entry), member);       \
     entry != NULL;                                                     \
     entry = slist_rcu_next_entry(entry, member))

#endif /* KERN_SLIST_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_SLIST_TYPES_H
#define KERN_SLIST_TYPES_H

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

#include "macros.h"

struct slist_node {
    struct slist_node *next;
};

struct slist {
    struct slist_node *first;
    struct slist_node *last;
};

#endif /* KERN_SLIST_TYPES_H */


code:
/*
 * Copyright (c) 2017-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 implementation is based on the paper "Algorithms for Scalable
 * Synchronization on Shared-Memory Multiprocessors" by John M. Mellor-Crummey
 * and Michael L. Scott, which describes MCS locks, among other algorithms.
 *
 * Here are additional issues this module solves that require modifications
 * to the original MCS algorithm :
 *  - There must not be any limit on the number of spin locks a thread may
 *    hold, and spinlocks must not need dynamic memory allocation.
 *  - Unlocking a spin lock must be a non-blocking operation. Without
 *    this requirement, a locking operation may be interrupted in the
 *    middle of a hand-off sequence, preventing the unlock operation
 *    from completing, potentially causing tricky deadlocks.
 *  - Spin lock storage must not exceed 32 bits.
 *
 * In order to solve these issues, the lock owner is never part of the
 * lock queue. This makes it possible to use a qnode only during the lock
 * operation, not after. This means a single qnode per execution context
 * is required even when holding multiple spin locks simultaneously.
 *
 * In addition, instead of making the owner perform a hand-off sequence
 * to unblock the first waiter when unlocking, the latter directly spins
 * on the lock word, and is the one performing the hand-off sequence with
 * the second waiter. As a side effect, this also optimizes spinning for
 * the common case of a single waiter.
 *
 * When a lock is held, the lock bit is set, and when a lock is contended
 * the contended bit is set. When contended, the lock word also contains
 * a compressed reference to the last waiter. That reference is called a
 * QID (for qnode ID). It is structured into two parts :
 *  - the execution context
 *  - the CPU ID
 *
 * The QID is used to uniquely identify a statically allocated qnode.
 *
 * The lock operation must make sure that the lock value is restored
 * to SPINLOCK_LOCKED if there is no more contention, an operation
 * called downgrading.
 */

#include <assert.h>
#include <errno.h>
#include <limits.h>
#include <stdalign.h>
#include <stddef.h>
#include <stdint.h>

#include <kern/atomic.h>
#include <kern/init.h>
#include <kern/macros.h>
#include <kern/percpu.h>
#include <kern/spinlock.h>
#include <kern/spinlock_i.h>
#include <kern/spinlock_types.h>
#include <kern/thread.h>
#include <machine/cpu.h>

#define SPINLOCK_CONTENDED          0x2

#define SPINLOCK_LOCKED_BITS        1
#define SPINLOCK_CONTENDED_BITS     1

#define SPINLOCK_QID_SHIFT          (SPINLOCK_CONTENDED_BITS \
                                     + SPINLOCK_LOCKED_BITS)

#define SPINLOCK_QID_CTX_BITS       1
#define SPINLOCK_QID_CTX_SHIFT      0
#define SPINLOCK_QID_CTX_MASK       ((1U << SPINLOCK_QID_CTX_BITS) - 1)

#define SPINLOCK_QID_CPU_BITS       29
#define SPINLOCK_QID_CPU_SHIFT      (SPINLOCK_QID_CTX_SHIFT \
                                     + SPINLOCK_QID_CTX_BITS)
#define SPINLOCK_QID_CPU_MASK       ((1U << SPINLOCK_QID_CPU_BITS) - 1)

#define SPINLOCK_BITS               (SPINLOCK_QID_CPU_BITS      \
                                     + SPINLOCK_QID_CTX_BITS    \
                                     + SPINLOCK_CONTENDED_BITS  \
                                     + SPINLOCK_LOCKED_BITS)

#if CONFIG_MAX_CPUS > (1U << SPINLOCK_QID_CPU_BITS)
#error "maximum number of supported processors too large"
#endif

static_assert(SPINLOCK_BITS <= (CHAR_BIT * sizeof(uint32_t)),
              "spinlock too large");

struct spinlock_qnode {
    alignas(CPU_L1_SIZE) struct spinlock_qnode *next;
    int locked;
};

/* TODO NMI support */
enum {
    SPINLOCK_CTX_THREAD,
    SPINLOCK_CTX_INTR,
    SPINLOCK_NR_CTXS
};

static_assert(SPINLOCK_NR_CTXS <= (SPINLOCK_QID_CTX_MASK + 1),
              "maximum number of contexts too large");

struct spinlock_cpu_data {
    struct spinlock_qnode qnodes[SPINLOCK_NR_CTXS];
};

static struct spinlock_cpu_data spinlock_cpu_data __percpu;

static struct spinlock_qnode *
spinlock_cpu_data_get_qnode(struct spinlock_cpu_data *cpu_data,
                            unsigned int ctx)
{
    assert(ctx < ARRAY_SIZE(cpu_data->qnodes));
    return &cpu_data->qnodes[ctx];
}

static uint32_t
spinlock_qid_build(unsigned int ctx, unsigned int cpu)
{
    assert(ctx <= SPINLOCK_QID_CTX_MASK);
    assert(cpu <= SPINLOCK_QID_CPU_MASK);

    return (cpu << SPINLOCK_QID_CPU_SHIFT) | (ctx << SPINLOCK_QID_CTX_SHIFT);
}

static unsigned int
spinlock_qid_ctx(uint32_t qid)
{
    return (qid >> SPINLOCK_QID_CTX_SHIFT) & SPINLOCK_QID_CTX_MASK;
}

static unsigned int
spinlock_qid_cpu(uint32_t qid)
{
    return (qid >> SPINLOCK_QID_CPU_SHIFT) & SPINLOCK_QID_CPU_MASK;
}

void
spinlock_init(struct spinlock *lock)
{
    lock->value = SPINLOCK_UNLOCKED;

#ifdef SPINLOCK_TRACK_OWNER
    lock->owner = NULL;
#endif /* SPINLOCK_TRACK_OWNER */
}

static void
spinlock_qnode_init(struct spinlock_qnode *qnode)
{
    qnode->next = NULL;
}

static struct spinlock_qnode *
spinlock_qnode_wait_next(const struct spinlock_qnode *qnode)
{
    struct spinlock_qnode *next;

    for (;;) {
        next = atomic_load(&qnode->next, ATOMIC_ACQUIRE);

        if (next) {
            break;
        }

        cpu_pause();
    }

    return next;
}

static void
spinlock_qnode_set_next(struct spinlock_qnode *qnode, struct spinlock_qnode *next)
{
    assert(next);
    atomic_store(&qnode->next, next, ATOMIC_RELEASE);
}

static void
spinlock_qnode_set_locked(struct spinlock_qnode *qnode)
{
    qnode->locked = 1;
}

static void
spinlock_qnode_wait_locked(const struct spinlock_qnode *qnode)
{
    int locked;

    for (;;) {
        locked = atomic_load(&qnode->locked, ATOMIC_ACQUIRE);

        if (!locked) {
            break;
        }

        cpu_pause();
    }
}

static void
spinlock_qnode_clear_locked(struct spinlock_qnode *qnode)
{
    atomic_store(&qnode->locked, 0, ATOMIC_RELEASE);
}

static void
spinlock_get_local_qnode(struct spinlock_qnode **qnode, uint32_t *qid)
{
    struct spinlock_cpu_data *cpu_data;
    unsigned int ctx;

    cpu_data = cpu_local_ptr(spinlock_cpu_data);
    ctx = thread_interrupted() ? SPINLOCK_CTX_INTR : SPINLOCK_CTX_THREAD;
    *qnode = spinlock_cpu_data_get_qnode(cpu_data, ctx);
    *qid = spinlock_qid_build(ctx, cpu_id());
}

static uint32_t
spinlock_enqueue(struct spinlock *lock, uint32_t qid)
{
    uint32_t old_value, new_value, prev, next;

    next = (qid << SPINLOCK_QID_SHIFT) | SPINLOCK_CONTENDED;

    for (;;) {
        old_value = atomic_load(&lock->value, ATOMIC_RELAXED);
        new_value = next | (old_value & SPINLOCK_LOCKED);
        prev = atomic_cas(&lock->value, old_value, new_value, ATOMIC_RELEASE);

        if (prev == old_value) {
            break;
        }

        cpu_pause();
    }

    return prev;
}

static struct spinlock_qnode *
spinlock_get_remote_qnode(uint32_t qid)
{
    struct spinlock_cpu_data *cpu_data;
    unsigned int ctx, cpu;

    /* This fence synchronizes with queueing */
    atomic_fence(ATOMIC_ACQUIRE);

    ctx = spinlock_qid_ctx(qid);
    cpu = spinlock_qid_cpu(qid);
    cpu_data = percpu_ptr(spinlock_cpu_data, cpu);
    return spinlock_cpu_data_get_qnode(cpu_data, ctx);
}

static void
spinlock_set_locked(struct spinlock *lock)
{
    atomic_or(&lock->value, SPINLOCK_LOCKED, ATOMIC_RELAXED);
}

static void
spinlock_wait_locked(const struct spinlock *lock)
{
    uint32_t value;

    for (;;) {
        value = atomic_load(&lock->value, ATOMIC_ACQUIRE);

        if (!(value & SPINLOCK_LOCKED)) {
            break;
        }

        cpu_pause();
    }
}

static int
spinlock_downgrade(struct spinlock *lock, uint32_t qid)
{
    uint32_t value, prev;

    value = (qid << SPINLOCK_QID_SHIFT) | SPINLOCK_CONTENDED;
    prev = atomic_cas(&lock->value, value, SPINLOCK_LOCKED, ATOMIC_RELAXED);
    assert(prev & SPINLOCK_CONTENDED);

    if (prev != value) {
        return EBUSY;
    }

    return 0;
}

void
spinlock_lock_slow(struct spinlock *lock)
{
    struct spinlock_qnode *qnode, *prev_qnode, *next_qnode;
    uint32_t prev, qid;
    int error;

    spinlock_get_local_qnode(&qnode, &qid);
    spinlock_qnode_init(qnode);

    prev = spinlock_enqueue(lock, qid);

    if (prev & SPINLOCK_CONTENDED) {
        prev_qnode = spinlock_get_remote_qnode(prev >> SPINLOCK_QID_SHIFT);
        spinlock_qnode_set_locked(qnode);
        spinlock_qnode_set_next(prev_qnode, qnode);
        spinlock_qnode_wait_locked(qnode);
    }

    /*
     * If uncontended, the previous lock value could be used to check whether
     * the lock bit was also cleared, but this wait operation also enforces
     * acquire ordering.
     */
    spinlock_wait_locked(lock);

    spinlock_own(lock);
    error = spinlock_downgrade(lock, qid);

    if (!error) {
        return;
    }

    spinlock_set_locked(lock);
    next_qnode = spinlock_qnode_wait_next(qnode);
    spinlock_qnode_clear_locked(next_qnode);
}

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

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


code:
/*
 * Copyright (c) 2012-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/>.
 *
 *
 * Spin locks.
 *
 * Critical sections built with spin locks run with preemption disabled.
 *
 * This module provides fair spin locks which guarantee time-bounded lock
 * acquisition depending only on the number of contending processors.
 */

#ifndef KERN_SPINLOCK_H
#define KERN_SPINLOCK_H

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

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

struct spinlock;

static inline bool
spinlock_locked(const struct spinlock *lock)
{
    uint32_t value;

    value = atomic_load(&lock->value, ATOMIC_RELAXED);
    return value != SPINLOCK_UNLOCKED;
}

#ifdef SPINLOCK_TRACK_OWNER

static inline void
spinlock_transfer_owner(struct spinlock *lock, struct thread *owner)
{
    assert(lock->owner == thread_self());
    lock->owner = owner;
}

#else /* SPINLOCK_TRACK_OWNER */

#define spinlock_transfer_owner(lock, owner)

#endif /* SPINLOCK_TRACK_OWNER */

/*
 * Initialize a spin lock.
 */
void spinlock_init(struct spinlock *lock);

/*
 * Attempt to lock the given spin lock.
 *
 * Return 0 on success, EBUSY if the spin lock is already locked.
 *
 * Preemption is disabled on success.
 */
static inline int
spinlock_trylock(struct spinlock *lock)
{
    int error;

    thread_preempt_disable();
    error = spinlock_lock_fast(lock);

    if (unlikely(error)) {
        thread_preempt_enable();
    }

    return error;
}

/*
 * Lock a spin lock.
 *
 * If the spin lock is already locked, the calling thread spins until the
 * spin lock is unlocked.
 *
 * A spin lock can only be locked once.
 *
 * This function disables preemption.
 */
static inline void
spinlock_lock(struct spinlock *lock)
{
    thread_preempt_disable();
    spinlock_lock_common(lock);
}

/*
 * Unlock a spin lock.
 *
 * The spin lock must be locked, and must have been locked on the same
 * processor it is unlocked on.
 *
 * This function may reenable preemption.
 */
static inline void
spinlock_unlock(struct spinlock *lock)
{
    spinlock_unlock_common(lock);
    thread_preempt_enable();
}

/*
 * Versions of the spinlock functions that also disable interrupts during
 * critical sections.
 */

/*
 * Attempt to lock the given spin lock.
 *
 * Return 0 on success, EBUSY if the spin lock is already locked.
 *
 * Preemption and interrupts are disabled on success, in which case the
 * flags passed by the caller are filled with the previous value of the
 * CPU flags.
 */
static inline int
spinlock_trylock_intr_save(struct spinlock *lock, unsigned long *flags)
{
    int error;

    thread_preempt_disable_intr_save(flags);
    error = spinlock_lock_fast(lock);

    if (unlikely(error)) {
        thread_preempt_enable_intr_restore(*flags);
    }

    return error;
}

/*
 * Lock a spin lock.
 *
 * If the spin lock is already locked, the calling thread spins until the
 * spin lock is unlocked.
 *
 * A spin lock can only be locked once.
 *
 * This function disables preemption and interrupts. The flags passed by
 * the caller are filled with the previous value of the CPU flags.
 */
static inline void
spinlock_lock_intr_save(struct spinlock *lock, unsigned long *flags)
{
    thread_preempt_disable_intr_save(flags);
    spinlock_lock_common(lock);
}

/*
 * Unlock a spin lock.
 *
 * The spin lock must be locked, and must have been locked on the same
 * processor it is unlocked on.
 *
 * This function may reenable preemption and interrupts, using the given
 * flags which must have been obtained with a lock or trylock operation.
 */
static inline void
spinlock_unlock_intr_restore(struct spinlock *lock, unsigned long flags)
{
    spinlock_unlock_common(lock);
    thread_preempt_enable_intr_restore(flags);
}

/*
 * This init operation provides :
 *  - uncontended spinlock locking
 *
 * Contended locking may only occur after starting APs.
 */
INIT_OP_DECLARE(spinlock_setup);

#endif /* KERN_SPINLOCK_H */


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

#ifndef KERN_SPINLOCK_I_H
#define KERN_SPINLOCK_I_H

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

#include <kern/atomic.h>
#include <kern/macros.h>
#include <kern/spinlock_types.h>
#include <kern/thread.h>
#include <machine/cpu.h>

/*
 * Uncontended lock values.
 *
 * Any other value implies a contended lock.
 */
#define SPINLOCK_UNLOCKED   0x0
#define SPINLOCK_LOCKED     0x1

#ifdef SPINLOCK_TRACK_OWNER

static inline void
spinlock_own(struct spinlock *lock)
{
    assert(!lock->owner);
    lock->owner = thread_self();
}

static inline void
spinlock_disown(struct spinlock *lock)
{
    assert(lock->owner == thread_self());
    lock->owner = NULL;
}

#else /* SPINLOCK_TRACK_OWNER */

#define spinlock_own(lock)
#define spinlock_disown(lock)

#endif /* SPINLOCK_TRACK_OWNER */

static inline int
spinlock_lock_fast(struct spinlock *lock)
{
    uint32_t prev;

    prev = atomic_cas(&lock->value, SPINLOCK_UNLOCKED,
                      SPINLOCK_LOCKED, ATOMIC_ACQUIRE);

    if (unlikely(prev != SPINLOCK_UNLOCKED)) {
        return EBUSY;
    }

    spinlock_own(lock);
    return 0;
}

void spinlock_lock_slow(struct spinlock *lock);

static inline void
spinlock_lock_common(struct spinlock *lock)
{
    int error;

    error = spinlock_lock_fast(lock);

    if (unlikely(error)) {
        spinlock_lock_slow(lock);
    }
}

static inline void
spinlock_unlock_common(struct spinlock *lock)
{
    spinlock_disown(lock);
    atomic_and(&lock->value, ~SPINLOCK_LOCKED, ATOMIC_RELEASE);
}

#endif /* KERN_SPINLOCK_I_H */


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

#ifndef KERN_SPINLOCK_TYPES_H
#define KERN_SPINLOCK_TYPES_H

#include <stdint.h>

#ifdef CONFIG_SPINLOCK_DEBUG
#define SPINLOCK_TRACK_OWNER
#endif

struct thread;

struct spinlock {
    uint32_t value;

#ifdef SPINLOCK_TRACK_OWNER
    struct thread *owner;
#endif /* SPINLOCK_TRACK_OWNER */
};

#endif /* KERN_SPINLOCK_TYPES_H */