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

#ifndef KERN_CLOCK_H
#define KERN_CLOCK_H

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

#include <kern/atomic.h>
#include <kern/clock_i.h>
#include <kern/init.h>
#include <kern/macros.h>

/*
 * Clock frequency.
 */
#define CLOCK_FREQ CONFIG_CLOCK_FREQ

#if (CLOCK_FREQ < 100) || (CLOCK_FREQ > 1000) || (1000 % CLOCK_FREQ) != 0
#error "invalid clock frequency"
#endif /* (1000 % CLOCK_FREQ) != 0 */

/*
 * Arbitrary value used to determine if a time is in the past or the future.
 *
 * Time is represented as 64-bits unsigned integers counting ticks. The
 * global time currently starts from 0 but this isn't a strong assumption
 * users should rely on. Instead, all time checks involve a time reference
 * against which to compare. The result of that comparison, done by
 * substraction, is either in the future, i.e. the difference is less
 * than the expire threshold, or in the past, i.e. the difference is
 * greater (keep in mind the result is unsigned). The threshold must be
 * large enough to allow both a wide range of possible times in the future,
 * but also enough time in the past for reliable timeout detection. Note
 * that using signed integers would be equivalent to dividing the range
 * in two (almost) equal past and future halves.
 */
#define CLOCK_EXPIRE_THRESHOLD (-(1ULL << 60))

static inline uint64_t
clock_get_time(void)
{
    extern union clock_global_time clock_global_time;

#ifdef ATOMIC_HAVE_64B_OPS

    /*
     * Don't enforce a stronger memory order, since :
     *  1/ it's useless as long as the reader remains on the same processor
     *  2/ thread migration enforces sequential consistency
     */
    return atomic_load(&clock_global_time.ticks, ATOMIC_RELAXED);

#else /* ATOMIC_HAVE_64B_OPS */

    uint32_t high1, low, high2;

    /*
     * For machines with no 64-bits atomic accessors, this implementation uses
     * a variant of the two-digit monotonic-clock algorithm, described in the
     * paper "Concurrent Reading and Writing of Clocks" by Leslie Lamport.
     */

    do {
        high1 = atomic_load(&clock_global_time.high1, ATOMIC_ACQUIRE);
        low = atomic_load(&clock_global_time.low, ATOMIC_ACQUIRE);
        high2 = atomic_load(&clock_global_time.high2, ATOMIC_RELAXED);
    } while (high1 != high2);

    return ((uint64_t)high2 << 32) | low;

#endif /* ATOMIC_HAVE_64B_OPS */
}

static inline uint64_t
clock_ticks_to_ms(uint64_t ticks)
{
    return ticks * (1000 / CLOCK_FREQ);
}

static inline uint64_t
clock_ticks_from_ms(uint64_t ms)
{
    return DIV_CEIL(ms, (1000 / CLOCK_FREQ));
}

static inline bool
clock_time_expired(uint64_t t, uint64_t ref)
{
    return (t - ref) > CLOCK_EXPIRE_THRESHOLD;
}

static inline bool
clock_time_occurred(uint64_t t, uint64_t ref)
{
    return (t == ref) || clock_time_expired(t, ref);
}

void clock_tick_intr(void);

#endif /* KERN_CLOCK_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_CLOCK_I_H
#define KERN_CLOCK_I_H

#include <stdalign.h>
#include <stdint.h>

#include <machine/cpu.h>

union clock_global_time {
    alignas(CPU_L1_SIZE) uint64_t ticks;

#ifndef ATOMIC_HAVE_64B_OPS
    struct {
#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
        uint32_t high1;
        uint32_t low;
#else /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
        uint32_t low;
        uint32_t high1;
#endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
        uint32_t high2;
    };
#endif /* ATOMIC_HAVE_64B_OPS */
};

#endif /* KERN_CLOCK_I_H */

license: mit


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/>.
 *
 *
 * Locking order : mutex -> sleep queue
 */

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

#include <kern/condition.h>
#include <kern/condition_types.h>
#include <kern/mutex.h>
#include <kern/sleepq.h>

static int
condition_wait_common(struct condition *condition, struct mutex *mutex,
                      bool timed, uint64_t ticks)
{
    struct sleepq *sleepq;
    int error;

    assert(mutex_locked(mutex));

    sleepq = sleepq_lend(condition, true);

    mutex_unlock(mutex);

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

    sleepq_return(sleepq);

    mutex_lock(mutex);

    return error;
}

void
condition_wait(struct condition *condition, struct mutex *mutex)
{
    int error;

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

int
condition_timedwait(struct condition *condition,
                    struct mutex *mutex, uint64_t ticks)
{
    return condition_wait_common(condition, mutex, true, ticks);
}

void
condition_signal(struct condition *condition)
{
    struct sleepq *sleepq;

    sleepq = sleepq_acquire(condition, true);

    if (sleepq == NULL) {
        return;
    }

    sleepq_signal(sleepq);

    sleepq_release(sleepq);
}

void
condition_broadcast(struct condition *condition)
{
    struct sleepq *sleepq;

    sleepq = sleepq_acquire(condition, true);

    if (sleepq == NULL) {
        return;
    }

    sleepq_broadcast(sleepq);

    sleepq_release(sleepq);
}


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/>.
 *
 *
 * Condition variables.
 *
 * A condition variable is a synchronization primitive used to wait
 * until a predicate becomes true. Multiple threads can be waiting
 * for this condition. In order to synchronize changes on the predicate
 * with waiting and signalling, a condition variable must be associated
 * with a mutex.
 */

#ifndef KERN_CONDITION_H
#define KERN_CONDITION_H

#include <stdint.h>

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

struct condition;

/*
 * Initialize a condition variable.
 */
#define condition_init(c) ((void)(c))

/*
 * Wait for a signal on the given condition variable.
 *
 * The associated mutex must be locked when calling this function.
 * It is unlocked before waiting and relocked before returning.
 *
 * 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 condition_wait(struct condition *condition, struct mutex *mutex);
int condition_timedwait(struct condition *condition,
                        struct mutex *mutex, uint64_t ticks);

/*
 * Wake up one (signal) or all (broadcast) threads waiting on a
 * condition variable, if any.
 *
 * Although it is not necessary to hold the mutex associated to the
 * condition variable when calling these functions, doing so guarantees
 * that a wake-up done when changing the predicate cannot be missed by
 * waiting threads.
 */
void condition_signal(struct condition *condition);
void condition_broadcast(struct condition *condition);

#endif /* KERN_CONDITION_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_CONDITION_TYPES_H
#define KERN_CONDITION_TYPES_H

struct condition {
    unsigned int _unused;
};

#endif /* KERN_CONDITION_TYPES_H */


code:
/*
 * Copyright (c) 2012 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/>.
 *
 *
 * Additions to the build system config.h header.
 */

#include <machine/config.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 <errno.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>

#include <kern/arg.h>
#include <kern/init.h>
#include <kern/console.h>
#include <kern/list.h>
#include <kern/log.h>
#include <kern/mutex.h>
#include <kern/spinlock.h>
#include <kern/thread.h>
#include <machine/boot.h>
#include <machine/cpu.h>

/*
 * Registered consoles.
 */
static struct list console_devs;

/*
 * Active console device.
 */
static struct console *console_dev;

static const char *console_name __initdata;

static bool __init
console_name_match(const char *name)
{
    if (console_name == NULL) {
        return true;
    }

    return (strcmp(console_name, name) == 0);
}

void __init
console_init(struct console *console, const char *name,
             const struct console_ops *ops)
{
    assert(ops != NULL);

    spinlock_init(&console->lock);
    console->ops = ops;
    cbuf_init(&console->recvbuf, console->buffer, sizeof(console->buffer));
    console->waiter = NULL;
    strlcpy(console->name, name, sizeof(console->name));
}

static int
console_process_ctrl_char(struct console *console, char c)
{
    switch (c) {
    case CONSOLE_SCROLL_UP:
    case CONSOLE_SCROLL_DOWN:
        break;
    default:
        return EINVAL;
    }

    console->ops->putc(console, c);
    return 0;
}

static void
console_putc(struct console *console, char c)
{
    unsigned long flags;

    spinlock_lock_intr_save(&console->lock, &flags);
    console->ops->putc(console, c);
    spinlock_unlock_intr_restore(&console->lock, flags);
}

static char
console_getc(struct console *console)
{
    unsigned long flags;
    int error;
    char c;

    spinlock_lock_intr_save(&console->lock, &flags);

    if (console->waiter != NULL) {
        c = EOF;
        goto out;
    }

    console->waiter = thread_self();

    for (;;) {
        error = cbuf_popb(&console->recvbuf, &c);

        if (!error) {
            error = console_process_ctrl_char(console, c);

            if (error) {
                break;
            }
        }

        thread_sleep(&console->lock, console, "consgetc");
    }

    console->waiter = NULL;

out:
    spinlock_unlock_intr_restore(&console->lock, flags);

    return c;
}

static int __init
console_bootstrap(void)
{
    list_init(&console_devs);
    console_name = arg_value("console");
    return 0;
}

INIT_OP_DEFINE(console_bootstrap,
               INIT_OP_DEP(arg_setup, true),
               INIT_OP_DEP(log_setup, true));

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

INIT_OP_DEFINE(console_setup,
               INIT_OP_DEP(boot_setup_console, true),
               INIT_OP_DEP(thread_setup, true));

void __init
console_register(struct console *console)
{
    assert(console->ops != NULL);

    list_insert_tail(&console_devs, &console->node);

    if ((console_dev == NULL) && console_name_match(console->name)) {
        console_dev = console;
    }

    log_info("console: %s registered", console->name);

    if (console == console_dev) {
        log_info("console: %s selected as active console", console->name);
    }
}

void
console_intr(struct console *console, const char *s)
{
    assert(thread_check_intr_context());

    if (*s == '\0') {
        return;
    }

    spinlock_lock(&console->lock);

    while (*s != '\0') {
        if (cbuf_size(&console->recvbuf) == cbuf_capacity(&console->recvbuf)) {
            goto out;
        }

        cbuf_pushb(&console->recvbuf, *s, false);
        s++;
    }

    thread_wakeup(console->waiter);

out:
    spinlock_unlock(&console->lock);
}

void
console_putchar(char c)
{
    if (console_dev == NULL) {
        return;
    }

    console_putc(console_dev, c);
}

char
console_getchar(void)
{
    char c;

    if (console_dev == NULL) {
        c = EOF;
        goto out;
    }

    c = console_getc(console_dev);

out:
    return c;
}


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/>.
 *
 *
 * Device-independent console interface.
 */

#ifndef KERN_CONSOLE_H
#define KERN_CONSOLE_H

#include <kern/cbuf.h>
#include <kern/init.h>
#include <kern/list.h>
#include <kern/spinlock.h>
#include <kern/thread.h>

#define CONSOLE_SCROLL_UP   0x12    /* DC2 */
#define CONSOLE_SCROLL_DOWN 0x14    /* DC4 */

struct console;

struct console_ops {
    void (*putc)(struct console *console, char c);
};

#define CONSOLE_BUF_SIZE    64
#define CONSOLE_NAME_SIZE   16

/*
 * Console device.
 *
 * This structure should be embedded in the hardware-specific console
 * objects. Calls to console operations are all serialized by this module
 * for each device. Interrupts are disabled when calling operations.
 */
struct console {
    struct spinlock lock;
    const struct console_ops *ops;
    char buffer[CONSOLE_BUF_SIZE];
    struct cbuf recvbuf;
    struct thread *waiter;
    struct list node;
    char name[CONSOLE_NAME_SIZE];
};

/*
 * Console initialization.
 */
void console_init(struct console *console, const char *name,
                  const struct console_ops *ops);

/*
 * Register a console device.
 *
 * The given console must be initialized before calling this function.
 *
 * This function isn't thread-safe and can only be called during system
 * initialization.
 */
void console_register(struct console *console);

/*
 * Console interrupt handler.
 *
 * This function is meant to be used by low-level drivers to fill the
 * receive buffer.
 *
 * Interrupts must be disabled when calling this function.
 */
void console_intr(struct console *console, const char *s);

/*
 * Write/read a single character to all registered console devices.
 *
 * Writing may not block in order to allow printf functions to be used in any
 * context. Reading may block waiting for input.
 */
void console_putchar(char c);
char console_getchar(void);

/*
 * This init operation provides :
 *  - registration of consoles
 */
INIT_OP_DECLARE(console_bootstrap);

/*
 * This init operation provides :
 *  - all consoles have been registered
 *  - module fully initialized
 */
INIT_OP_DECLARE(console_setup);

#endif /* KERN_CONSOLE_H */


code:
/*
 * Copyright (c) 2013-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 <errno.h>
#include <stddef.h>

#include <kern/bitmap.h>
#include <kern/cpumap.h>
#include <kern/init.h>
#include <kern/kmem.h>
#include <kern/macros.h>
#include <machine/cpu.h>

static struct cpumap cpumap_active_cpus __read_mostly = { { 1 } };

static struct kmem_cache cpumap_cache;

static int __init
cpumap_setup(void)
{
    unsigned int i, nr_cpus;

    kmem_cache_init(&cpumap_cache, "cpumap", sizeof(struct cpumap), 0, NULL, 0);
    cpumap_zero(&cpumap_active_cpus);
    nr_cpus = cpu_count();

    for (i = 0; i < nr_cpus; i++) {
        cpumap_set(&cpumap_active_cpus, i);
    }

    return 0;
}

INIT_OP_DEFINE(cpumap_setup,
               INIT_OP_DEP(kmem_setup, true),
               INIT_OP_DEP(cpu_mp_probe, true));

const struct cpumap *
cpumap_all(void)
{
    return &cpumap_active_cpus;
}

int
cpumap_create(struct cpumap **cpumapp)
{
    struct cpumap *cpumap;

    cpumap = kmem_cache_alloc(&cpumap_cache);

    if (cpumap == NULL) {
        return ENOMEM;
    }

    *cpumapp = cpumap;
    return 0;
}

void
cpumap_destroy(struct cpumap *cpumap)
{
    kmem_cache_free(&cpumap_cache, cpumap);
}

int
cpumap_check(const struct cpumap *cpumap)
{
    int index;

    index = bitmap_find_first(cpumap->cpus, cpu_count());

    if (index == -1) {
        return EINVAL;
    }

    return 0;
}


code:
/*
 * Copyright (c) 2013-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/>.
 *
 *
 * Processors represented as bit maps.
 *
 * This module acts as a convenient frontend for the bitmap and kmem modules.
 * Since the size of a CPU map varies with the maximum number of processors
 * that can be managed by the system, maps must not be allocated from the
 * stack.
 */

#ifndef KERN_CPUMAP_H
#define KERN_CPUMAP_H

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

struct cpumap {
    BITMAP_DECLARE(cpus, CONFIG_MAX_CPUS);
};

static inline void
cpumap_zero(struct cpumap *cpumap)
{
    bitmap_zero(cpumap->cpus, CONFIG_MAX_CPUS);
}

static inline void
cpumap_fill(struct cpumap *cpumap)
{
    bitmap_fill(cpumap->cpus, CONFIG_MAX_CPUS);
}

static inline void
cpumap_copy(struct cpumap *dest, const struct cpumap *src)
{
    bitmap_copy(dest->cpus, src->cpus, CONFIG_MAX_CPUS);
}

static inline int
cpumap_cmp(const struct cpumap *a, const struct cpumap *b)
{
    return bitmap_cmp(a->cpus, b->cpus, CONFIG_MAX_CPUS);
}

static inline void
cpumap_set(struct cpumap *cpumap, int index)
{
    bitmap_set(cpumap->cpus, index);
}

static inline void
cpumap_set_atomic(struct cpumap *cpumap, int index)
{
    bitmap_set_atomic(cpumap->cpus, index);
}

static inline void
cpumap_clear(struct cpumap *cpumap, int index)
{
    bitmap_clear(cpumap->cpus, index);
}

static inline void
cpumap_clear_atomic(struct cpumap *cpumap, int index)
{
    bitmap_clear_atomic(cpumap->cpus, index);
}

static inline int
cpumap_test(const struct cpumap *cpumap, int index)
{
    return bitmap_test(cpumap->cpus, index);
}

static inline void
cpumap_and(struct cpumap *a, const struct cpumap *b)
{
    bitmap_and(a->cpus, b->cpus, CONFIG_MAX_CPUS);
}

static inline void
cpumap_or(struct cpumap *a, const struct cpumap *b)
{
    bitmap_or(a->cpus, b->cpus, CONFIG_MAX_CPUS);
}

static inline void
cpumap_xor(struct cpumap *a, const struct cpumap *b)
{
    bitmap_xor(a->cpus, b->cpus, CONFIG_MAX_CPUS);
}

static inline int
cpumap_find_next(const struct cpumap *cpumap, int index)
{
    return bitmap_find_next(cpumap->cpus, CONFIG_MAX_CPUS, index);
}

static inline int
cpumap_find_first(const struct cpumap *cpumap)
{
    return bitmap_find_first(cpumap->cpus, CONFIG_MAX_CPUS);
}

static inline int
cpumap_find_next_zero(const struct cpumap *cpumap, int index)
{
    return bitmap_find_next_zero(cpumap->cpus, CONFIG_MAX_CPUS, index);
}

static inline int
cpumap_find_first_zero(const struct cpumap *cpumap)
{
    return bitmap_find_first_zero(cpumap->cpus, CONFIG_MAX_CPUS);
}

#define cpumap_for_each(cpumap, index) \
    bitmap_for_each((cpumap)->cpus, CONFIG_MAX_CPUS, index)

#define cpumap_for_each_zero(cpumap, index) \
    bitmap_for_each_zero((cpumap)->cpus, CONFIG_MAX_CPUS, index)

/*
 * Return a cpumap representing all active processors.
 *
 * Until the cpumap module is initialized, the cpumap returned by this
 * function describes the BSP only.
 */
const struct cpumap * cpumap_all(void);

/*
 * Allocate a CPU map.
 *
 * The new map is uninitialized.
 */
int cpumap_create(struct cpumap **cpumapp);

/*
 * Release a CPU map.
 */
void cpumap_destroy(struct cpumap *cpumap);

/*
 * Check the validity of a CPU map.
 *
 * If the map doesn't identify at least one managed processor, return
 * EINVAL.
 */
int cpumap_check(const struct cpumap *cpumap);

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

#endif /* KERN_CPUMAP_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 <errno.h>
#include <stddef.h>
#include <string.h>

#include <kern/error.h>
#include <kern/panic.h>

void
error_check(int error, const char *prefix)
{
    if (!error) {
        return;
    }

    panic("%s%s%s",
          (prefix == NULL) ? "" : prefix,
          (prefix == NULL) ? "" : ": ",
          strerror(error));
}


code:
/*
 * Copyright (c) 2012-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_ERROR_H
#define KERN_ERROR_H

/*
 * If error denotes an actual error (i.e. is not 0), panic, using the given
 * string as a prefix for the error message. A NULL prefix is allowed.
 */
void error_check(int error, const char *prefix);

#endif /* KERN_ERROR_H */


code:
/*
 * Copyright (c) 2010-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 <limits.h>
#include <stdbool.h>
#include <stdarg.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#include <kern/fmt.h>
#include <kern/macros.h>
#include <kern/types.h>

/*
 * Size for the temporary number buffer. The minimum base is 8 so 3 bits
 * are consumed per digit. Add one to round up. The conversion algorithm
 * doesn't use the null byte.
 */
#define FMT_MAX_NUM_SIZE (((sizeof(unsigned long long) * CHAR_BIT) / 3) + 1)

/*
 * Special size for fmt_vsnprintf(), used when the buffer size is unknown.
 */
#define FMT_NOLIMIT ((size_t)-1)

/*
 * Formatting flags.
 *
 * FMT_FORMAT_LOWER must be 0x20 as it is OR'd with fmt_digits, eg.
 * '0': 0x30 | 0x20 => 0x30 ('0')
 * 'A': 0x41 | 0x20 => 0x61 ('a')
 */
#define FMT_FORMAT_ALT_FORM     0x0001 /* "Alternate form"                    */
#define FMT_FORMAT_ZERO_PAD     0x0002 /* Zero padding on the left            */
#define FMT_FORMAT_LEFT_JUSTIFY 0x0004 /* Align text on the left              */
#define FMT_FORMAT_BLANK        0x0008 /* Blank space before positive number  */
#define FMT_FORMAT_SIGN         0x0010 /* Always place a sign (either + or -) */
#define FMT_FORMAT_LOWER        0x0020 /* To lowercase (for %x)               */
#define FMT_FORMAT_CONV_SIGNED  0x0040 /* Format specifies signed conversion  */
#define FMT_FORMAT_DISCARD      0x0080 /* Discard output (scanf)              */
#define FMT_FORMAT_CHECK_WIDTH  0x0100 /* Check field width (scanf)           */

enum {
    FMT_MODIFIER_NONE,
    FMT_MODIFIER_CHAR,
    FMT_MODIFIER_SHORT,
    FMT_MODIFIER_LONG,
    FMT_MODIFIER_LONGLONG,
    FMT_MODIFIER_PTR,       /* Used only for %p */
    FMT_MODIFIER_SIZE,
    FMT_MODIFIER_PTRDIFF,
};

enum {
    FMT_SPECIFIER_INVALID,
    FMT_SPECIFIER_INT,
    FMT_SPECIFIER_CHAR,
    FMT_SPECIFIER_STR,
    FMT_SPECIFIER_NRCHARS,
    FMT_SPECIFIER_PERCENT,
};

/*
 * Note that copies of the original va_list object are made, because va_arg()
 * may not reliably be used by different callee functions, and despite the
 * standard explicitely allowing pointers to va_list objects, it's apparently
 * very difficult for implementations to provide and is best avoided.
 */

struct fmt_sprintf_state {
    const char *format;
    va_list ap;
    unsigned int flags;
    int width;
    int precision;
    unsigned int modifier;
    unsigned int specifier;
    unsigned int base;
    char *str;
    char *start;
    char *end;
};

struct fmt_sscanf_state {
    const char *str;
    const char *start;
    const char *format;
    va_list ap;
    unsigned int flags;
    int width;
    unsigned int modifier;
    unsigned int specifier;
    unsigned int base;
    int nr_convs;
};

static const char fmt_digits[] = "0123456789ABCDEF";

static char
fmt_consume(const char **strp)
{
    char c;

    c = **strp;
    (*strp)++;
    return c;
}

static void
fmt_restore(const char **strp)
{
    (*strp)--;
}

static void
fmt_vsnprintf_produce(char **strp, char *end, char c)
{
    if (*strp < end) {
        **strp = c;
    }

    (*strp)++;
}

static bool
fmt_isdigit(char c)
{
    return (c >= '0') && (c <= '9');
}

static bool
fmt_isxdigit(char c)
{
    return fmt_isdigit(c)
           || ((c >= 'a') && (c <= 'f'))
           || ((c >= 'A') && (c <= 'F'));
}

static void
fmt_sprintf_state_init(struct fmt_sprintf_state *state,
                       char *str, size_t size,
                       const char *format, va_list ap)
{
    state->format = format;
    va_copy(state->ap, ap);
    state->str = str;
    state->start = str;

    if (size == 0) {
        state->end = NULL;
    } else if (size == FMT_NOLIMIT) {
        state->end = (char *)-1;
    } else {
        state->end = state->start + size - 1;
    }
}

static int
fmt_sprintf_state_finalize(struct fmt_sprintf_state *state)
{
    va_end(state->ap);

    if (state->str < state->end) {
        *state->str = '\0';
    } else if (state->end != NULL) {
        *state->end = '\0';
    }

    return state->str - state->start;
}

static char
fmt_sprintf_state_consume_format(struct fmt_sprintf_state *state)
{
    return fmt_consume(&state->format);
}

static void
fmt_sprintf_state_restore_format(struct fmt_sprintf_state *state)
{
    fmt_restore(&state->format);
}

static void
fmt_sprintf_state_consume_flags(struct fmt_sprintf_state *state)
{
    bool found;
    char c;

    found = true;
    state->flags = 0;

    do {
        c = fmt_sprintf_state_consume_format(state);

        switch (c) {
        case '#':
            state->flags |= FMT_FORMAT_ALT_FORM;
            break;
        case '0':
            state->flags |= FMT_FORMAT_ZERO_PAD;
            break;
        case '-':
            state->flags |= FMT_FORMAT_LEFT_JUSTIFY;
            break;
        case ' ':
            state->flags |= FMT_FORMAT_BLANK;
            break;
        case '+':
            state->flags |= FMT_FORMAT_SIGN;
            break;
        default:
            found = false;
            break;
        }
    } while (found);

    fmt_sprintf_state_restore_format(state);
}

static void
fmt_sprintf_state_consume_width(struct fmt_sprintf_state *state)
{
    char c;

    c = fmt_sprintf_state_consume_format(state);

    if (fmt_isdigit(c)) {
        state->width = 0;

        do {
            state->width = state->width * 10 + (c - '0');
            c = fmt_sprintf_state_consume_format(state);
        } while (fmt_isdigit(c));

        fmt_sprintf_state_restore_format(state);
    } else if (c == '*') {
        state->width = va_arg(state->ap, int);

        if (state->width < 0) {
            state->flags |= FMT_FORMAT_LEFT_JUSTIFY;
            state->width = -state->width;
        }
    } else {
        state->width = 0;
        fmt_sprintf_state_restore_format(state);
    }
}

static void
fmt_sprintf_state_consume_precision(struct fmt_sprintf_state *state)
{
    char c;

    c = fmt_sprintf_state_consume_format(state);

    if (c == '.') {
        c = fmt_sprintf_state_consume_format(state);

        if (fmt_isdigit(c)) {
            state->precision = 0;

            do {
                state->precision = state->precision * 10 + (c - '0');
                c = fmt_sprintf_state_consume_format(state);
            } while (fmt_isdigit(c));

            fmt_sprintf_state_restore_format(state);
        } else if (c == '*') {
            state->precision = va_arg(state->ap, int);

            if (state->precision < 0) {
                state->precision = 0;
            }
        } else {
            state->precision = 0;
            fmt_sprintf_state_restore_format(state);
        }
    } else {
        /* precision is >= 0 only if explicit */
        state->precision = -1;
        fmt_sprintf_state_restore_format(state);
    }
}

static void
fmt_sprintf_state_consume_modifier(struct fmt_sprintf_state *state)
{
    char c, c2;

    c = fmt_sprintf_state_consume_format(state);

    switch (c) {
    case 'h':
    case 'l':
        c2 = fmt_sprintf_state_consume_format(state);

        if (c == c2) {
            state->modifier = (c == 'h') ? FMT_MODIFIER_CHAR
                                         : FMT_MODIFIER_LONGLONG;
        } else {
            state->modifier = (c == 'h') ? FMT_MODIFIER_SHORT
                                         : FMT_MODIFIER_LONG;
            fmt_sprintf_state_restore_format(state);
        }

        break;
    case 'z':
        state->modifier = FMT_MODIFIER_SIZE;
        __fallthrough;
    case 't':
        state->modifier = FMT_MODIFIER_PTRDIFF;
        break;
    default:
        state->modifier = FMT_MODIFIER_NONE;
        fmt_sprintf_state_restore_format(state);
        break;
    }
}

static void
fmt_sprintf_state_consume_specifier(struct fmt_sprintf_state *state)
{
    char c;

    c = fmt_sprintf_state_consume_format(state);

    switch (c) {
    case 'd':
    case 'i':
        state->flags |= FMT_FORMAT_CONV_SIGNED;
        __fallthrough;
    case 'u':
        state->base = 10;
        state->specifier = FMT_SPECIFIER_INT;
        break;
    case 'o':
        state->base = 8;
        state->specifier = FMT_SPECIFIER_INT;
        break;
    case 'p':
        state->flags |= FMT_FORMAT_ALT_FORM;
        state->modifier = FMT_MODIFIER_PTR;
        __fallthrough;
    case 'x':
        state->flags |= FMT_FORMAT_LOWER;
        __fallthrough;
    case 'X':
        state->base = 16;
        state->specifier = FMT_SPECIFIER_INT;
        break;
    case 'c':
        state->specifier = FMT_SPECIFIER_CHAR;
        break;
    case 's':
        state->specifier = FMT_SPECIFIER_STR;
        break;
    case 'n':
        state->specifier = FMT_SPECIFIER_NRCHARS;
        break;
    case '%':
        state->specifier = FMT_SPECIFIER_PERCENT;
        break;
    default:
        state->specifier = FMT_SPECIFIER_INVALID;
        fmt_sprintf_state_restore_format(state);
        break;
    }
}

static void
fmt_sprintf_state_produce_raw_char(struct fmt_sprintf_state *state, char c)
{
    fmt_vsnprintf_produce(&state->str, state->end, c);
}

static int
fmt_sprintf_state_consume(struct fmt_sprintf_state *state)
{
    char c;

    c = fmt_consume(&state->format);

    if (c == '\0') {
        return ENOENT;
    }

    if (c != '%') {
        fmt_sprintf_state_produce_raw_char(state, c);
        return EAGAIN;
    }

    fmt_sprintf_state_consume_flags(state);
    fmt_sprintf_state_consume_width(state);
    fmt_sprintf_state_consume_precision(state);
    fmt_sprintf_state_consume_modifier(state);
    fmt_sprintf_state_consume_specifier(state);
    return 0;
}

static void
fmt_sprintf_state_produce_int(struct fmt_sprintf_state *state)
{
    char c, sign, tmp[FMT_MAX_NUM_SIZE];
    unsigned int r, mask, shift;
    unsigned long long n;
    int i;

    switch (state->modifier) {
    case FMT_MODIFIER_CHAR:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            n = (signed char)va_arg(state->ap, int);
        } else {
            n = (unsigned char)va_arg(state->ap, int);
        }

        break;
    case FMT_MODIFIER_SHORT:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            n = (short)va_arg(state->ap, int);
        } else {
            n = (unsigned short)va_arg(state->ap, int);
        }

        break;
    case FMT_MODIFIER_LONG:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            n = va_arg(state->ap, long);
        } else {
            n = va_arg(state->ap, unsigned long);
        }

        break;
    case FMT_MODIFIER_LONGLONG:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            n = va_arg(state->ap, long long);
        } else {
            n = va_arg(state->ap, unsigned long long);
        }

        break;
    case FMT_MODIFIER_PTR:
        n = (uintptr_t)va_arg(state->ap, void *);
        break;
    case FMT_MODIFIER_SIZE:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            n = va_arg(state->ap, ssize_t);
        } else {
            n = va_arg(state->ap, size_t);
        }

        break;
    case FMT_MODIFIER_PTRDIFF:
        n = va_arg(state->ap, ptrdiff_t);
        break;
    default:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            n = va_arg(state->ap, int);
        } else {
            n = va_arg(state->ap, unsigned int);
        }

        break;
    }

    if ((state->flags & FMT_FORMAT_LEFT_JUSTIFY) || (state->precision >= 0)) {
        state->flags &= ~FMT_FORMAT_ZERO_PAD;
    }

    sign = '\0';

    if (state->flags & FMT_FORMAT_ALT_FORM) {
        /* '0' for octal */
        state->width--;

        /* '0x' or '0X' for hexadecimal */
        if (state->base == 16) {
            state->width--;
        }
    } else if (state->flags & FMT_FORMAT_CONV_SIGNED) {
        if ((long long)n < 0) {
            sign = '-';
            state->width--;
            n = -(long long)n;
        } else if (state->flags & FMT_FORMAT_SIGN) {
            /* FMT_FORMAT_SIGN must precede FMT_FORMAT_BLANK. */
            sign = '+';
            state->width--;
        } else if (state->flags & FMT_FORMAT_BLANK) {
            sign = ' ';
            state->width--;
        }
    }

    /* Conversion, in reverse order */

    i = 0;

    if (n == 0) {
        if (state->precision != 0) {
            tmp[i] = '0';
            i++;
        }
    } else if (state->base == 10) {
        /*
         * Try to avoid 64 bits operations if the processor doesn't
         * support them. Note that even when using modulus and
         * division operators close to each other, the compiler may
         * forge two functions calls to compute the quotient and the
         * remainder, whereas processor instructions are generally
         * correctly used once, giving both results at once, through
         * plain or reciprocal division.
         */
#ifndef __LP64__
        if (state->modifier == FMT_MODIFIER_LONGLONG) {
#endif /* __LP64__ */
            do {
                r = n % 10;
                n /= 10;
                tmp[i] = fmt_digits[r];
                i++;
            } while (n != 0);
#ifndef __LP64__
        } else {
            unsigned long m;

            m = (unsigned long)n;

            do {
                r = m % 10;
                m /= 10;
                tmp[i] = fmt_digits[r];
                i++;
            } while (m != 0);
        }
#endif /* __LP64__ */
    } else {
        mask = state->base - 1;
        shift = (state->base == 8) ? 3 : 4;

        do {
            r = n & mask;
            n >>= shift;
            tmp[i] = fmt_digits[r] | (state->flags & FMT_FORMAT_LOWER);
            i++;
        } while (n != 0);
    }

    if (i > state->precision) {
        state->precision = i;
    }

    state->width -= state->precision;

    if (!(state->flags & (FMT_FORMAT_LEFT_JUSTIFY | FMT_FORMAT_ZERO_PAD))) {
        while (state->width > 0) {
            state->width--;
            fmt_sprintf_state_produce_raw_char(state, ' ');
        }

        state->width--;
    }

    if (state->flags & FMT_FORMAT_ALT_FORM) {
        fmt_sprintf_state_produce_raw_char(state, '0');

        if (state->base == 16) {
            c = 'X' | (state->flags & FMT_FORMAT_LOWER);
            fmt_sprintf_state_produce_raw_char(state, c);
        }
    } else if (sign != '\0') {
        fmt_sprintf_state_produce_raw_char(state, sign);
    }

    if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) {
        c = (state->flags & FMT_FORMAT_ZERO_PAD) ? '0' : ' ';

        while (state->width > 0) {
            state->width--;
            fmt_sprintf_state_produce_raw_char(state, c);
        }

        state->width--;
    }

    while (i < state->precision) {
        state->precision--;
        fmt_sprintf_state_produce_raw_char(state, '0');
    }

    state->precision--;

    while (i > 0) {
        i--;
        fmt_sprintf_state_produce_raw_char(state, tmp[i]);
    }

    while (state->width > 0) {
        state->width--;
        fmt_sprintf_state_produce_raw_char(state, ' ');
    }

    state->width--;
}

static void
fmt_sprintf_state_produce_char(struct fmt_sprintf_state *state)
{
    char c;

    c = va_arg(state->ap, int);

    if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) {
        for (;;) {
            state->width--;

            if (state->width <= 0) {
                break;
            }

            fmt_sprintf_state_produce_raw_char(state, ' ');
        }
    }

    fmt_sprintf_state_produce_raw_char(state, c);

    for (;;) {
        state->width--;

        if (state->width <= 0) {
            break;
        }

        fmt_sprintf_state_produce_raw_char(state, ' ');
    }
}

static void
fmt_sprintf_state_produce_str(struct fmt_sprintf_state *state)
{
    int i, len;
    char *s;

    s = va_arg(state->ap, char *);

    if (s == NULL) {
        s = "(null)";
    }

    for (len = 0; s[len] != '\0'; len++) {
        if (len == state->precision) {
            break;
        }
    }

    if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) {
        while (len < state->width) {
            state->width--;
            fmt_sprintf_state_produce_raw_char(state, ' ');
        }
    }

    for (i = 0; i < len; i++) {
        fmt_sprintf_state_produce_raw_char(state, *s);
        s++;
    }

    while (len < state->width) {
        state->width--;
        fmt_sprintf_state_produce_raw_char(state, ' ');
    }
}

static void
fmt_sprintf_state_produce_nrchars(struct fmt_sprintf_state *state)
{
    if (state->modifier == FMT_MODIFIER_CHAR) {
        signed char *ptr = va_arg(state->ap, signed char *);
        *ptr = state->str - state->start;
    } else if (state->modifier == FMT_MODIFIER_SHORT) {
        short *ptr = va_arg(state->ap, short *);
        *ptr = state->str - state->start;
    } else if (state->modifier == FMT_MODIFIER_LONG) {
        long *ptr = va_arg(state->ap, long *);
        *ptr = state->str - state->start;
    } else if (state->modifier == FMT_MODIFIER_LONGLONG) {
        long long *ptr = va_arg(state->ap, long long *);
        *ptr = state->str - state->start;
    } else if (state->modifier == FMT_MODIFIER_SIZE) {
        ssize_t *ptr = va_arg(state->ap, ssize_t *);
        *ptr = state->str - state->start;
    } else if (state->modifier == FMT_MODIFIER_PTRDIFF) {
        ptrdiff_t *ptr = va_arg(state->ap, ptrdiff_t *);
        *ptr = state->str - state->start;
    } else {
        int *ptr = va_arg(state->ap, int *);
        *ptr = state->str - state->start;
    }
}

static void
fmt_sprintf_state_produce(struct fmt_sprintf_state *state)
{
    switch (state->specifier) {
    case FMT_SPECIFIER_INT:
        fmt_sprintf_state_produce_int(state);
        break;
    case FMT_SPECIFIER_CHAR:
        fmt_sprintf_state_produce_char(state);
        break;
    case FMT_SPECIFIER_STR:
        fmt_sprintf_state_produce_str(state);
        break;
    case FMT_SPECIFIER_NRCHARS:
        fmt_sprintf_state_produce_nrchars(state);
        break;
    case FMT_SPECIFIER_PERCENT:
    case FMT_SPECIFIER_INVALID:
        fmt_sprintf_state_produce_raw_char(state, '%');
        break;
    }
}

int
fmt_sprintf(char *str, const char *format, ...)
{
    va_list ap;
    int length;

    va_start(ap, format);
    length = fmt_vsprintf(str, format, ap);
    va_end(ap);

    return length;
}

int
fmt_vsprintf(char *str, const char *format, va_list ap)
{
    return fmt_vsnprintf(str, FMT_NOLIMIT, format, ap);
}

int
fmt_snprintf(char *str, size_t size, const char *format, ...)
{
    va_list ap;
    int length;

    va_start(ap, format);
    length = fmt_vsnprintf(str, size, format, ap);
    va_end(ap);

    return length;
}

int
fmt_vsnprintf(char *str, size_t size, const char *format, va_list ap)
{
    struct fmt_sprintf_state state;
    int error;

    fmt_sprintf_state_init(&state, str, size, format, ap);

    for (;;) {
        error = fmt_sprintf_state_consume(&state);

        if (error == EAGAIN) {
            continue;
        } else if (error) {
            break;
        }

        fmt_sprintf_state_produce(&state);
    }

    return fmt_sprintf_state_finalize(&state);
}

static char
fmt_atoi(char c)
{
    assert(fmt_isxdigit(c));

    if (fmt_isdigit(c)) {
        return c - '0';
    } else if (c >= 'a' && c <= 'f') {
        return 10 + (c - 'a');
    } else {
        return 10 + (c - 'A');
    }
}

static bool
fmt_isspace(char c)
{
    if (c == ' ') {
        return true;
    }

    if ((c >= '\t') && (c <= '\f')) {
        return true;
    }

    return false;
}

static void
fmt_skip(const char **strp)
{
    while (fmt_isspace(**strp)) {
        (*strp)++;
    }
}

static void
fmt_sscanf_state_init(struct fmt_sscanf_state *state, const char *str,
                      const char *format, va_list ap)
{
    state->str = str;
    state->start = str;
    state->format = format;
    state->flags = 0;
    state->width = 0;
    va_copy(state->ap, ap);
    state->nr_convs = 0;
}

static int
fmt_sscanf_state_finalize(struct fmt_sscanf_state *state)
{
    va_end(state->ap);
    return state->nr_convs;
}

static void
fmt_sscanf_state_report_conv(struct fmt_sscanf_state *state)
{
    if (state->nr_convs == EOF) {
        state->nr_convs = 1;
        return;
    }

    state->nr_convs++;
}

static void
fmt_sscanf_state_report_error(struct fmt_sscanf_state *state)
{
    if (state->nr_convs != 0) {
        return;
    }

    state->nr_convs = EOF;
}

static void
fmt_sscanf_state_skip_space(struct fmt_sscanf_state *state)
{
    fmt_skip(&state->str);
}

static char
fmt_sscanf_state_consume_string(struct fmt_sscanf_state *state)
{
    char c;

    c = fmt_consume(&state->str);

    if (state->flags & FMT_FORMAT_CHECK_WIDTH) {
        if (state->width == 0) {
            c = EOF;
        } else {
            state->width--;
        }
    }

    return c;
}

static void
fmt_sscanf_state_restore_string(struct fmt_sscanf_state *state)
{
    fmt_restore(&state->str);
}

static char
fmt_sscanf_state_consume_format(struct fmt_sscanf_state *state)
{
    return fmt_consume(&state->format);
}

static void
fmt_sscanf_state_restore_format(struct fmt_sscanf_state *state)
{
    fmt_restore(&state->format);
}

static void
fmt_sscanf_state_consume_flags(struct fmt_sscanf_state *state)
{
    bool found;
    char c;

    found = true;
    state->flags = 0;

    do {
        c = fmt_sscanf_state_consume_format(state);

        switch (c) {
        case '*':
            state->flags |= FMT_FORMAT_DISCARD;
            break;
        default:
            found = false;
            break;
        }
    } while (found);

    fmt_sscanf_state_restore_format(state);
}

static void
fmt_sscanf_state_consume_width(struct fmt_sscanf_state *state)
{
    char c;

    state->width = 0;

    for (;;) {
        c = fmt_sscanf_state_consume_format(state);

        if (!fmt_isdigit(c)) {
            break;
        }

        state->width = state->width * 10 + (c - '0');
    }

    if (state->width != 0) {
        state->flags |= FMT_FORMAT_CHECK_WIDTH;
    }

    fmt_sscanf_state_restore_format(state);
}

static void
fmt_sscanf_state_consume_modifier(struct fmt_sscanf_state *state)
{
    char c, c2;

    c = fmt_sscanf_state_consume_format(state);

    switch (c) {
    case 'h':
    case 'l':
        c2 = fmt_sscanf_state_consume_format(state);

        if (c == c2) {
            state->modifier = (c == 'h') ? FMT_MODIFIER_CHAR
                                         : FMT_MODIFIER_LONGLONG;
        } else {
            state->modifier = (c == 'h') ? FMT_MODIFIER_SHORT
                                         : FMT_MODIFIER_LONG;
            fmt_sscanf_state_restore_format(state);
        }

        break;
    case 'z':
        state->modifier = FMT_MODIFIER_SIZE;
        break;
    case 't':
        state->modifier = FMT_MODIFIER_PTRDIFF;
        break;
    default:
        state->modifier = FMT_MODIFIER_NONE;
        fmt_sscanf_state_restore_format(state);
        break;
    }
}

static void
fmt_sscanf_state_consume_specifier(struct fmt_sscanf_state *state)
{
    char c;

    c = fmt_sscanf_state_consume_format(state);

    switch (c) {
    case 'i':
        state->base = 0;
        state->flags |= FMT_FORMAT_CONV_SIGNED;
        state->specifier = FMT_SPECIFIER_INT;
        break;
    case 'd':
        state->flags |= FMT_FORMAT_CONV_SIGNED;
        __fallthrough;
    case 'u':
        state->base = 10;
        state->specifier = FMT_SPECIFIER_INT;
        break;
    case 'o':
        state->base = 8;
        state->specifier = FMT_SPECIFIER_INT;
        break;
    case 'p':
        state->modifier = FMT_MODIFIER_PTR;
        __fallthrough;
    case 'x':
    case 'X':
        state->base = 16;
        state->specifier = FMT_SPECIFIER_INT;
        break;
    case 'c':
        state->specifier = FMT_SPECIFIER_CHAR;
        break;
    case 's':
        state->specifier = FMT_SPECIFIER_STR;
        break;
    case 'n':
        state->specifier = FMT_SPECIFIER_NRCHARS;
        break;
    case '%':
        state->specifier = FMT_SPECIFIER_PERCENT;
        break;
    default:
        state->specifier = FMT_SPECIFIER_INVALID;
        fmt_sscanf_state_restore_format(state);
        break;
    }
}

static int
fmt_sscanf_state_discard_char(struct fmt_sscanf_state *state, char c)
{
    char c2;

    if (fmt_isspace(c)) {
        fmt_sscanf_state_skip_space(state);
        return 0;
    }

    c2 = fmt_sscanf_state_consume_string(state);

    if (c != c2) {
        if ((c2 == '\0') && (state->nr_convs == 0)) {
            state->nr_convs = EOF;
        }

        return EINVAL;
    }

    return 0;
}

static int
fmt_sscanf_state_consume(struct fmt_sscanf_state *state)
{
    int error;
    char c;

    state->flags = 0;

    c = fmt_consume(&state->format);

    if (c == '\0') {
        return ENOENT;
    }

    if (c != '%') {
        error = fmt_sscanf_state_discard_char(state, c);

        if (error) {
            return error;
        }

        return EAGAIN;
    }

    fmt_sscanf_state_consume_flags(state);
    fmt_sscanf_state_consume_width(state);
    fmt_sscanf_state_consume_modifier(state);
    fmt_sscanf_state_consume_specifier(state);
    return 0;
}

static int
fmt_sscanf_state_produce_int(struct fmt_sscanf_state *state)
{
    unsigned long long n, m, tmp;
    char c, buf[FMT_MAX_NUM_SIZE];
    bool negative;
    size_t i;

    negative = 0;

    fmt_sscanf_state_skip_space(state);
    c = fmt_sscanf_state_consume_string(state);

    if (c == '-') {
        negative = true;
        c = fmt_sscanf_state_consume_string(state);
    }

    if (c == '0') {
        c = fmt_sscanf_state_consume_string(state);

        if ((c == 'x') || (c == 'X')) {
            if (state->base == 0) {
                state->base = 16;
            }

            if (state->base == 16) {
                c = fmt_sscanf_state_consume_string(state);
            } else {
                fmt_sscanf_state_restore_string(state);
                c = '0';
            }
        } else {
            if (state->base == 0) {
                state->base = 8;
            }

            if (state->base != 8) {
                fmt_sscanf_state_restore_string(state);
                c = '0';
            }
        }
    }

    i = 0;

    while (c != '\0') {
        if (state->base == 8) {
            if (!((c >= '0') && (c <= '7'))) {
                break;
            }
        } else if (state->base == 16) {
            if (!fmt_isxdigit(c)) {
                break;
            }
        } else {
            if (!fmt_isdigit(c)) {
                break;
            }
        }

        /* XXX Standard sscanf provides no way to cleanly handle overflows */
        if (i < (ARRAY_SIZE(buf) - 1)) {
            buf[i] = c;
        } else if (i == (ARRAY_SIZE(buf) - 1)) {
            strcpy(buf, "1");
            negative = true;
        }

        i++;
        c = fmt_sscanf_state_consume_string(state);
    }

    fmt_sscanf_state_restore_string(state);

    if (state->flags & FMT_FORMAT_DISCARD) {
        return 0;
    }

    if (i == 0) {
        if (c == '\0') {
            fmt_sscanf_state_report_error(state);
            return EINVAL;
        }

        buf[0] = '0';
        i = 1;
    }

    if (i < ARRAY_SIZE(buf)) {
        buf[i] = '\0';
        i--;
    } else {
        i = strlen(buf) - 1;
    }

    n = 0;

#ifndef __LP64__
    if (state->modifier == FMT_MODIFIER_LONGLONG) {
#endif /* __LP64__ */
        m = 1;
        tmp = 0;

        while (&buf[i] >= buf) {
            tmp += fmt_atoi(buf[i]) * m;

            if (tmp < n) {
                n = 1;
                negative = true;
                break;
            }

            n = tmp;
            m *= state->base;
            i--;
        }
#ifndef __LP64__
    } else {
        unsigned long _n, _m, _tmp;

        _n = 0;
        _m = 1;
        _tmp = 0;

        while (&buf[i] >= buf) {
            _tmp += fmt_atoi(buf[i]) * _m;

            if (_tmp < _n) {
                _n = 1;
                negative = true;
                break;
            }

            _n = _tmp;
            _m *= state->base;
            i--;
        }

        n = _n;
    }
#endif /* __LP64__ */

    if (negative) {
        n = -n;
    }

    switch (state->modifier) {
    case FMT_MODIFIER_CHAR:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            *va_arg(state->ap, char *) = n;
        } else {
            *va_arg(state->ap, unsigned char *) = n;
        }

        break;
    case FMT_MODIFIER_SHORT:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            *va_arg(state->ap, short *) = n;
        } else {
            *va_arg(state->ap, unsigned short *) = n;
        }

        break;
    case FMT_MODIFIER_LONG:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            *va_arg(state->ap, long *) = n;
        } else {
            *va_arg(state->ap, unsigned long *) = n;
        }

        break;
    case FMT_MODIFIER_LONGLONG:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            *va_arg(state->ap, long long *) = n;
        } else {
            *va_arg(state->ap, unsigned long long *) = n;
        }

        break;
    case FMT_MODIFIER_PTR:
        *va_arg(state->ap, uintptr_t *) = n;
        break;
    case FMT_MODIFIER_SIZE:
        *va_arg(state->ap, size_t *) = n;
        break;
    case FMT_MODIFIER_PTRDIFF:
        *va_arg(state->ap, ptrdiff_t *) = n;
        break;
    default:
        if (state->flags & FMT_FORMAT_CONV_SIGNED) {
            *va_arg(state->ap, int *) = n;
        } else {
            *va_arg(state->ap, unsigned int *) = n;
        }
    }

    fmt_sscanf_state_report_conv(state);
    return 0;
}

static int
fmt_sscanf_state_produce_char(struct fmt_sscanf_state *state)
{
    char c, *dest;
    int i, width;

    if (state->flags & FMT_FORMAT_DISCARD) {
        dest = NULL;
    } else {
        dest = va_arg(state->ap, char *);
    }

    if (state->flags & FMT_FORMAT_CHECK_WIDTH) {
        width = state->width;
    } else {
        width = 1;
    }

    for (i = 0; i < width; i++) {
        c = fmt_sscanf_state_consume_string(state);

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

        if (dest != NULL) {
            *dest = c;
            dest++;
        }
    }

    if (i < width) {
        fmt_sscanf_state_restore_string(state);
    }

    if ((dest != NULL) && (i != 0)) {
        fmt_sscanf_state_report_conv(state);
    }

    return 0;
}

static int
fmt_sscanf_state_produce_str(struct fmt_sscanf_state *state)
{
    const char *orig;
    char c, *dest;

    orig = state->str;

    fmt_sscanf_state_skip_space(state);

    if (state->flags & FMT_FORMAT_DISCARD) {
        dest = NULL;
    } else {
        dest = va_arg(state->ap, char *);
    }

    for (;;) {
        c = fmt_sscanf_state_consume_string(state);

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

        if (dest != NULL) {
            *dest = c;
            dest++;
        }
    }

    fmt_sscanf_state_restore_string(state);

    if (state->str == orig) {
        fmt_sscanf_state_report_error(state);
        return EINVAL;
    }

    if (dest != NULL) {
        *dest = '\0';
        fmt_sscanf_state_report_conv(state);
    }

    return 0;
}

static int
fmt_sscanf_state_produce_nrchars(struct fmt_sscanf_state *state)
{
    *va_arg(state->ap, int *) = state->str - state->start;
    return 0;
}

static int
fmt_sscanf_state_produce(struct fmt_sscanf_state *state)
{
    switch (state->specifier) {
    case FMT_SPECIFIER_INT:
        return fmt_sscanf_state_produce_int(state);
    case FMT_SPECIFIER_CHAR:
        return fmt_sscanf_state_produce_char(state);
    case FMT_SPECIFIER_STR:
        return fmt_sscanf_state_produce_str(state);
    case FMT_SPECIFIER_NRCHARS:
        return fmt_sscanf_state_produce_nrchars(state);
    case FMT_SPECIFIER_PERCENT:
        fmt_sscanf_state_skip_space(state);
        return fmt_sscanf_state_discard_char(state, '%');
    default:
        fmt_sscanf_state_report_error(state);
        return EINVAL;
    }
}

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

    va_start(ap, format);
    ret = fmt_vsscanf(str, format, ap);
    va_end(ap);

    return ret;
}

int
fmt_vsscanf(const char *str, const char *format, va_list ap)
{
    struct fmt_sscanf_state state;
    int error;

    fmt_sscanf_state_init(&state, str, format, ap);

    for (;;) {
        error = fmt_sscanf_state_consume(&state);

        if (error == EAGAIN) {
            continue;
        } else if (error) {
            break;
        }

        error = fmt_sscanf_state_produce(&state);

        if (error) {
            break;
        }
    }

    return fmt_sscanf_state_finalize(&state);
}


code:
/*
 * Copyright (c) 2010-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/
 *
 *
 * Formatted string functions.
 *
 * The functions provided by this module implement a subset of the standard
 * sprintf- and sscanf-like functions.
 *
 * sprintf:
 *  - flags: # 0 - ' ' (space) +
 *  - field width is supported
 *  - precision is supported
 *
 * sscanf:
 *  - flags: *
 *  - field width is supported
 *
 * common:
 *  - modifiers: hh h l ll z t
 *  - specifiers: d i o u x X c s p n %
 */

#ifndef KERN_FMT_H
#define KERN_FMT_H

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

int fmt_sprintf(char *str, const char *format, ...)
    __attribute__((format(printf, 2, 3)));

int fmt_vsprintf(char *str, const char *format, va_list ap)
    __attribute__((format(printf, 2, 0)));

int fmt_snprintf(char *str, size_t size, const char *format, ...)
    __attribute__((format(printf, 3, 4)));

int fmt_vsnprintf(char *str, size_t size, const char *format, va_list ap)
    __attribute__((format(printf, 3, 0)));

int fmt_sscanf(const char *str, const char *format, ...)
    __attribute__((format(scanf, 2, 3)));

int fmt_vsscanf(const char *str, const char *format, va_list ap)
    __attribute__((format(scanf, 2, 0)));

#endif /* KERN_FMT_H */


code:
/*
 * Copyright (c) 2010-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/
 *
 *
 * Hash functions for integers and strings.
 *
 * Integer hashing follows Thomas Wang's paper about his 32/64-bits mix
 * functions :
 * - https://gist.github.com/badboy/6267743
 *
 * String hashing uses a variant of the djb2 algorithm with k=31, as in
 * the implementation of the hashCode() method of the Java String class :
 * - http://www.javamex.com/tutorials/collections/hash_function_technical.shtml
 *
 * Note that this algorithm isn't suitable to obtain usable 64-bits hashes
 * and is expected to only serve as an array index producer.
 *
 * These functions all have a bits parameter that indicates the number of
 * relevant bits the caller is interested in. When returning a hash, its
 * value must be truncated so that it can fit in the requested bit size.
 * It can be used by the implementation to select high or low bits, depending
 * on their relative randomness. To get complete, unmasked hashes, use the
 * HASH_ALLBITS macro.
 */

#ifndef KERN_HASH_H
#define KERN_HASH_H

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

#ifdef __LP64__
#define HASH_ALLBITS 64
#define hash_long(n, bits) hash_int64(n, bits)
#else /* __LP64__ */
static_assert(sizeof(long) == 4, "unsupported data model");
#define HASH_ALLBITS 32
#define hash_long(n, bits) hash_int32(n, bits)
#endif

static inline bool
hash_bits_valid(unsigned int bits)
{
    return (bits != 0) && (bits <= HASH_ALLBITS);
}

static inline uint32_t
hash_int32(uint32_t n, unsigned int bits)
{
    uint32_t hash;

    assert(hash_bits_valid(bits));

    hash = n;
    hash = ~hash + (hash << 15);
    hash ^= (hash >> 12);
    hash += (hash << 2);
    hash ^= (hash >> 4);
    hash += (hash << 3) + (hash << 11);
    hash ^= (hash >> 16);

    return hash >> (32 - bits);
}

static inline uint64_t
hash_int64(uint64_t n, unsigned int bits)
{
    uint64_t hash;

    assert(hash_bits_valid(bits));

    hash = n;
    hash = ~hash + (hash << 21);
    hash ^= (hash >> 24);
    hash += (hash << 3) + (hash << 8);
    hash ^= (hash >> 14);
    hash += (hash << 2) + (hash << 4);
    hash ^= (hash >> 28);
    hash += (hash << 31);

    return hash >> (64 - bits);
}

static inline uintptr_t
hash_ptr(const void *ptr, unsigned int bits)
{
    if (sizeof(uintptr_t) == 8) {
        return hash_int64((uintptr_t)ptr, bits);
    } else {
        return hash_int32((uintptr_t)ptr, bits);
    }
}

static inline unsigned long
hash_str(const char *str, unsigned int bits)
{
    unsigned long hash, mask;
    char c;

    assert(hash_bits_valid(bits));

    for (hash = 0; /* no condition */; str++) {
        c = *str;

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

        hash = ((hash << 5) - hash) + c;
    }

    /*
     * This mask construction avoids the undefined behavior that would
     * result from directly shifting by the number of bits, if that number
     * is equal to the width of the hash.
     */
    mask = (~0UL >> (HASH_ALLBITS - bits));
    return hash & mask;
}

#endif /* KERN_HASH_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/
 *
 *
 * Doubly-linked list specialized for forward traversals and O(1) removals.
 */

#ifndef KERN_HLIST_H
#define KERN_HLIST_H

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

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

struct hlist;

struct hlist_node;

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

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

/*
 * Initialize a list node.
 *
 * A node is in no list when its pprev member points to NULL.
 */
static inline void
hlist_node_init(struct hlist_node *node)
{
    node->pprev = NULL;
}

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

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

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

/*
 * Return true if node is invalid and denotes the end of the list.
 */
static inline bool
hlist_end(const struct hlist_node *node)
{
    return node == NULL;
}

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

/*
 * Return true if list contains exactly one node.
 */
static inline bool
hlist_singular(const struct hlist *list)
{
    return !hlist_empty(list) && hlist_end(list->first->next);
}

/*
 * Set the new head of a list.
 *
 * After completion, old_head is stale.
 */
static inline void
hlist_set_head(struct hlist *new_head, const struct hlist *old_head)
{
    *new_head = *old_head;

    if (!hlist_empty(new_head)) {
        new_head->first->pprev = &new_head->first;
    }
}

/*
 * Insert a node at the head of a list.
 */
static inline void
hlist_insert_head(struct hlist *list, struct hlist_node *node)
{
    struct hlist_node *first;

    first = list->first;
    node->next = first;
    node->pprev = &list->first;

    if (first != NULL) {
        first->pprev = &node->next;
    }

    list->first = node;
}

/*
 * Insert a node before another node.
 */
static inline void
hlist_insert_before(struct hlist_node *node, struct hlist_node *next)
{
    node->next = next;
    node->pprev = next->pprev;
    next->pprev = &node->next;
    *node->pprev = node;
}

/*
 * Insert a node after another node.
 */
static inline void
hlist_insert_after(struct hlist_node *node, struct hlist_node *prev)
{
    node->next = prev->next;
    node->pprev = &prev->next;

    if (node->next != NULL) {
        node->next->pprev = &node->next;
    }

    prev->next = node;
}

/*
 * Remove a node from a list.
 */
static inline void
hlist_remove(struct hlist_node *node)
{
    if (node->next != NULL) {
        node->next->pprev = node->pprev;
    }

    *node->pprev = node->next;
}

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

/*
 * Get the first entry of a list.
 */
#define hlist_first_entry(list, type, member)                           \
MACRO_BEGIN                                                             \
    struct hlist_node *first_;                                          \
                                                                        \
    first_ = (list)->first;                                             \
    hlist_end(first_) ? NULL : hlist_entry(first_, type, member);       \
MACRO_END

/*
 * Get the entry next to the given entry.
 */
#define hlist_next_entry(entry, member)                                 \
MACRO_BEGIN                                                             \
    struct hlist_node *next_;                                           \
                                                                        \
    next_ = (entry)->member.next;                                       \
    hlist_end(next_)                                                    \
        ? NULL                                                          \
        : hlist_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 hlist_for_each(list, node)  \
for (node = hlist_first(list);      \
     !hlist_end(node);              \
     node = hlist_next(node))

/*
 * Forge a loop to process all nodes of a list.
 */
#define hlist_for_each_safe(list, node, tmp)            \
for (node = hlist_first(list),                          \
     tmp = hlist_end(node) ? NULL : hlist_next(node);   \
     !hlist_end(node);                                  \
     node = tmp,                                        \
     tmp = hlist_end(node) ? NULL : hlist_next(node))

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

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

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

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

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

/*
 * Insert a node at the head of a list.
 */
static inline void
hlist_rcu_insert_head(struct hlist *list, struct hlist_node *node)
{
    struct hlist_node *first;

    first = list->first;
    node->next = first;
    node->pprev = &list->first;

    if (first != NULL) {
        first->pprev = &node->next;
    }

    rcu_store_ptr(list->first, node);
}

/*
 * Insert a node before another node.
 */
static inline void
hlist_rcu_insert_before(struct hlist_node *node, struct hlist_node *next)
{
    node->next = next;
    node->pprev = next->pprev;
    next->pprev = &node->next;
    rcu_store_ptr(*node->pprev, node);
}

/*
 * Insert a node after another node.
 */
static inline void
hlist_rcu_insert_after(struct hlist_node *node, struct hlist_node *prev)
{
    node->next = prev->next;
    node->pprev = &prev->next;

    if (node->next != NULL) {
        node->next->pprev = &node->next;
    }

    rcu_store_ptr(prev->next, node);
}

/*
 * Remove a node from a list.
 */
static inline void
hlist_rcu_remove(struct hlist_node *node)
{
    if (node->next != NULL) {
        node->next->pprev = node->pprev;
    }

    rcu_store_ptr(*node->pprev, node->next);
}

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

/*
 * Get the first entry of a list.
 */
#define hlist_rcu_first_entry(list, type, member)                       \
MACRO_BEGIN                                                             \
    struct hlist_node *first_;                                          \
                                                                        \
    first_ = hlist_rcu_first(list);                                     \
    hlist_end(first_) ? NULL : hlist_entry(first_, type, member);       \
MACRO_END

/*
 * Get the entry next to the given entry.
 */
#define hlist_rcu_next_entry(entry, member)                             \
MACRO_BEGIN                                                             \
    struct hlist_node *next_;                                           \
                                                                        \
    next_ = hlist_rcu_next(&entry->member);                             \
    hlist_end(next_)                                                    \
        ? NULL                                                          \
        : hlist_entry(next_, typeof(*entry), member);                   \
MACRO_END

/*
 * Forge a loop to process all nodes of a list.
 */
#define hlist_rcu_for_each(list, node)      \
for (node = hlist_rcu_first(list);          \
     !hlist_end(node);                      \
     node = hlist_rcu_next(node))

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

#endif /* KERN_HLIST_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_HLIST_TYPES_H
#define KERN_HLIST_TYPES_H

/*
 * List node.
 *
 * The pprev member points to another node member instead of another node,
 * so that it may safely refer to the first member of the list head. Its
 * main purpose is to allow O(1) removal.
 */
struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;
};

struct hlist {
    struct hlist_node *first;
};

#endif /* KERN_HLIST_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/>.
 *
 *
 * The main purpose of the init module is to provide a convenient interface
 * to declare initialization operations and their dependency, infer an order
 * of execution based on the resulting graph (which must be acyclic), and
 * run the operations in that order. Topological sorting is achieved using
 * Kahn's algorithm.
 */

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

#include <kern/init.h>
#include <kern/slist.h>
#include <kern/macros.h>
#include <machine/cpu.h>

extern struct init_op _init_ops;
extern struct init_op _init_ops_end;

static_assert(sizeof(struct init_op) == INIT_OP_ALIGN, "invalid init_op size");

/*
 * List of initialization operations.
 *
 * This type is used for the output of the topological sort.
 */
struct init_ops_list {
    struct slist ops;
    size_t size;
};

static void __init
init_ops_list_init(struct init_ops_list *list)
{
    slist_init(&list->ops);
    list->size = 0;
}

static size_t __init
init_ops_list_size(const struct init_ops_list *list)
{
    return list->size;
}

static void __init
init_ops_list_push(struct init_ops_list *list, struct init_op *op)
{
    slist_insert_head(&list->ops, &op->list_node);
    list->size++;
}

static struct init_op * __init
init_ops_list_pop(struct init_ops_list *list)
{
    struct init_op *op;

    if (list->size == 0) {
        return NULL;
    }

    op = slist_first_entry(&list->ops, struct init_op, list_node);
    slist_remove(&list->ops, NULL);
    list->size--;
    return op;
}

/*
 * Stack of initialization operations.
 *
 * This type is used internally by the topological sort algorithm.
 */
struct init_ops_stack {
    struct slist ops;
};

static void __init
init_ops_stack_init(struct init_ops_stack *stack)
{
    slist_init(&stack->ops);
}

static void __init
init_ops_stack_push(struct init_ops_stack *stack, struct init_op *op)
{
    slist_insert_head(&stack->ops, &op->stack_node);
}

static struct init_op * __init
init_ops_stack_pop(struct init_ops_stack *stack)
{
    struct init_op *op;

    if (slist_empty(&stack->ops)) {
        return NULL;
    }

    op = slist_first_entry(&stack->ops, struct init_op, stack_node);
    slist_remove(&stack->ops, NULL);
    return op;
}

static struct init_op_dep * __init
init_op_get_dep(const struct init_op *op, size_t index)
{
    assert(index < op->nr_deps);
    return &op->deps[index];
}

static void __init
init_op_init(struct init_op *op)
{
    struct init_op_dep *dep;

    for (size_t i = 0; i < op->nr_deps; i++) {
        dep = init_op_get_dep(op, i);
        dep->op->nr_parents++;
        assert(dep->op->nr_parents != 0);
    }
}

static bool __init
init_op_orphan(const struct init_op *op)
{
    return (op->nr_parents == 0);
}

static bool __init
init_op_pending(const struct init_op *op)
{
    return op->state == INIT_OP_STATE_PENDING;
}

static void __init
init_op_set_pending(struct init_op *op)
{
    assert(op->state == INIT_OP_STATE_UNLINKED);
    op->state = INIT_OP_STATE_PENDING;
}

static bool __init
init_op_complete(const struct init_op *op)
{
    return op->state == INIT_OP_STATE_COMPLETE;
}

static void __init
init_op_set_complete(struct init_op *op)
{
    assert(init_op_pending(op));
    op->state = INIT_OP_STATE_COMPLETE;
}

static bool __init
init_op_ready(const struct init_op *op)
{
    const struct init_op_dep *dep;
    size_t i;

    for (i = 0; i < op->nr_deps; i++) {
        dep = init_op_get_dep(op, i);

        if (!init_op_complete(dep->op)
            || (dep->required && dep->op->error)) {
            return false;
        }
    }

    return true;
}

static void __init
init_op_run(struct init_op *op)
{
    if (init_op_ready(op)) {
        op->error = op->fn();
    }

    init_op_set_complete(op);
}

#ifdef CONFIG_INIT_DEBUG

#define INIT_DEBUG_LOG_BUFFER_SIZE 8192

struct init_debug_log {
    char buffer[INIT_DEBUG_LOG_BUFFER_SIZE];
    size_t index;
};

/*
 * Buffers used to store an easy-to-dump text representation of init operations.
 *
 * These buffers are meant to be retrieved through a debugging interface such
 * as JTAG.
 */
struct init_debug_logs {
    struct init_debug_log roots;    /* graph roots */
    struct init_debug_log cycles;   /* operations with dependency cycles */
    struct init_debug_log pending;  /* operations successfully sorted */
    struct init_debug_log complete; /* executed operations */
};

static struct init_debug_logs init_debug_logs;

static void __init
init_debug_log_append(struct init_debug_log *log, const char *name)
{
    size_t size;

    if (log->index == sizeof(log->buffer)) {
        return;
    }

    size = sizeof(log->buffer) - log->index;
    log->index += snprintf(log->buffer + log->index, size, "%s ", name);

    if (log->index >= sizeof(log->buffer)) {
        log->index = sizeof(log->buffer);
    }
}

static void __init
init_debug_append_root(const struct init_op *op)
{
    init_debug_log_append(&init_debug_logs.roots, op->name);
}

static void __init
init_debug_append_cycle(const struct init_op *op)
{
    init_debug_log_append(&init_debug_logs.cycles, op->name);
}

static void __init
init_debug_append_pending(const struct init_op *op)
{
    init_debug_log_append(&init_debug_logs.pending, op->name);
}

static void __init
init_debug_append_complete(const struct init_op *op)
{
    init_debug_log_append(&init_debug_logs.complete, op->name);
}

static void __init
init_debug_scan_not_pending(void)
{
    const struct init_op *op;

    for (op = &_init_ops; op < &_init_ops_end; op++) {
        if (!init_op_pending(op)) {
            init_debug_append_cycle(op);
        }
    }
}

#else /* CONFIG_INIT_DEBUG */
#define init_debug_append_root(roots)
#define init_debug_append_pending(op)
#define init_debug_append_complete(op)
#define init_debug_scan_not_pending()
#endif /* CONFIG_INIT_DEBUG */

static void __init
init_add_pending_op(struct init_ops_list *pending_ops, struct init_op *op)
{
    assert(!init_op_pending(op));

    init_op_set_pending(op);
    init_ops_list_push(pending_ops, op);
    init_debug_append_pending(op);
}

static void __init
init_op_visit(struct init_op *op, struct init_ops_stack *stack)
{
    struct init_op_dep *dep;

    for (size_t i = 0; i < op->nr_deps; i++) {
        dep = init_op_get_dep(op, i);
        assert(dep->op->nr_parents != 0);
        dep->op->nr_parents--;

        if (init_op_orphan(dep->op)) {
            init_ops_stack_push(stack, dep->op);
        }
    }
}

static void __init
init_check_ops_alignment(void)
{
    uintptr_t start, end;

    start = (uintptr_t)&_init_ops;
    end = (uintptr_t)&_init_ops_end;

    if (((end - start) % INIT_OP_ALIGN) != 0) {
        cpu_halt();
    }
}

static void __init
init_bootstrap(void)
{
    struct init_op *op;

    init_check_ops_alignment();

    for (op = &_init_ops; op < &_init_ops_end; op++) {
        init_op_init(op);
    }
}

static void __init
init_scan_roots(struct init_ops_stack *stack)
{
    struct init_op *op;

    init_ops_stack_init(stack);

    for (op = &_init_ops; op < &_init_ops_end; op++) {
        if (init_op_orphan(op)) {
            init_ops_stack_push(stack, op);
            init_debug_append_root(op);
        }
    }
}

static void __init
init_scan_ops(struct init_ops_list *pending_ops)
{
    struct init_ops_stack stack;
    struct init_op *op;
    size_t nr_ops;

    init_scan_roots(&stack);

    for (;;) {
        op = init_ops_stack_pop(&stack);

        if (op == NULL) {
            break;
        }

        init_add_pending_op(pending_ops, op);
        init_op_visit(op, &stack);
    }

    init_debug_scan_not_pending();

    nr_ops = &_init_ops_end - &_init_ops;

    if (init_ops_list_size(pending_ops) != nr_ops) {
        cpu_halt();
    }
}

static void __init
init_run_ops(struct init_ops_list *pending_ops)
{
    struct init_op *op;

    for (;;) {
        op = init_ops_list_pop(pending_ops);

        if (op == NULL) {
            break;
        }

        init_op_run(op);
        init_debug_append_complete(op);
    }
}

void __init
init_setup(void)
{
    struct init_ops_list pending_ops;

    init_ops_list_init(&pending_ops);

    init_bootstrap();
    init_scan_ops(&pending_ops);
    init_run_ops(&pending_ops);
}


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

#ifndef KERN_INIT_H
#define KERN_INIT_H

/*
 * These sections should contain code and data which can be discarded once
 * kernel initialization is done.
 */
#define INIT_SECTION        .init.text
#define INIT_DATA_SECTION   .init.data

/*
 * This section must only contain init operation structures, and must be
 * located inside the .init section.
 */
#define INIT_OPS_SECTION    .init.ops

/*
 * Alignment is important to make sure initialization operations are
 * stored as a C array in the reserved init op section.
 */
#define INIT_OP_ALIGN 64

#ifndef __ASSEMBLER__

#include <errno.h>

#include <kern/macros.h>

#define __init __section(QUOTE(INIT_SECTION))
#define __initdata __section(QUOTE(INIT_DATA_SECTION))

/*
 * Boundaries of the .init section.
 */
extern char _init;
extern char _init_end;

/*
 * Type for initialization operation functions.
 */
typedef int (*init_op_fn_t)(void);

#include <kern/init_i.h>

/*
 * Forge an init operation declaration.
 */
#define INIT_OP_DECLARE(fn) extern struct init_op INIT_OP(fn)

/*
 * Foge an entry suitable as an init operation dependency.
 *
 * If a dependency isn't required, it's still used to determine run
 * order, but its result is ignored, and the operation depending on it
 * behaves as if that dependency succeeded.
 */
#define INIT_OP_DEP(fn, required) { &INIT_OP(fn), required }

/*
 * Init operation definition macro.
 *
 * This macro is used to define a structure named after the given function.
 * Init operations are placed in a specific section which doesn't contain
 * any other object type, making it a system-wide array of init operations.
 * There is no need to actively register init operations; this module finds
 * them all from their section. Dependencies are given as a variable-length
 * argument list of entries built with the INIT_OP_DEP() macro.
 */
#define INIT_OP_DEFINE(_fn, ...)                                    \
    static struct init_op_dep INIT_OP_DEPS(_fn)[] __initdata = {    \
        __VA_ARGS__                                                 \
    };                                                              \
                                                                    \
    struct init_op INIT_OP(_fn) __initop __used = {                 \
        .name = QUOTE(_fn),                                         \
        .fn = _fn,                                                  \
        .deps = INIT_OP_DEPS(_fn),                                  \
        .error = EAGAIN,                                            \
        .state = INIT_OP_STATE_UNLINKED,                            \
        .nr_deps = ARRAY_SIZE(INIT_OP_DEPS(_fn)),                   \
        .nr_parents = 0,                                            \
    }

/*
 * Initialize the init module.
 *
 * Scan the section containing init operations, resolve all dependencies,
 * and run operations in an appropriate order.
 */
void init_setup(void);

#endif /* __ASSEMBLER__ */

#endif /* KERN_INIT_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_INIT_I_H
#define KERN_INIT_I_H

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

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

#define __initop __section(QUOTE(INIT_OPS_SECTION))

#define INIT_OP_STATE_UNLINKED      0
#define INIT_OP_STATE_PENDING       1
#define INIT_OP_STATE_COMPLETE      2

struct init_op {
    alignas(INIT_OP_ALIGN) struct slist_node list_node;
    struct slist_node stack_node;
    const char *name;
    init_op_fn_t fn;
    struct init_op_dep *deps;
    int error;
    unsigned char state;
    unsigned char nr_deps;
    unsigned char nr_parents;
};

struct init_op_dep {
    struct init_op *op;
    bool required;
};

#define __INIT_OP_DEPS(fn)  fn ## _init_op_deps
#define INIT_OP_DEPS(fn)    __INIT_OP_DEPS(fn)

#define __INIT_OP(fn)       fn ## _init_op
#define INIT_OP(fn)         __INIT_OP(fn)

#endif /* KERN_INIT_I_H */