code:
/*
 * Copyright (c) 2014-2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * This implementation is based on the paper "RadixVM: Scalable address
 * spaces for multithreaded applications" by Austin T. Clements,
 * M. Frans Kaashoek, and Nickolai Zeldovich. Specifically, it implements
 * the Refcache component described in the paper, with a few differences
 * outlined below.
 *
 * Refcache flushes delta caches directly from an interrupt handler, and
 * disables interrupts and preemption on cache access. That behaviour is
 * realtime-unfriendly because of the potentially large number of deltas
 * in a cache. This module uses dedicated manager threads to perform
 * cache flushes and review queue processing, and only disables preemption
 * on individual delta access.
 *
 * In addition, Refcache normally requires all processors to regularly
 * process their local data. That behaviour is dyntick-unfriendly. As a
 * result, this module handles processor registration so that processors
 * that aren't participating in reference counting (e.g. because they're
 * idling) don't prevent others from progressing. Instead of per-processor
 * review queues, there is one global review queue which can be managed
 * from any processor. Review queue access should still be considerably
 * infrequent in practice, keeping the impact on contention low.
 *
 * Locking protocol : cache -> counter -> global data
 *
 * TODO Reconsider whether it's possible to bring back local review queues.
 */

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

#include <kern/condition.h>
#include <kern/cpumap.h>
#include <kern/init.h>
#include <kern/list.h>
#include <kern/log.h>
#include <kern/macros.h>
#include <kern/panic.h>
#include <kern/percpu.h>
#include <kern/slist.h>
#include <kern/spinlock.h>
#include <kern/sref.h>
#include <kern/sref_i.h>
#include <kern/syscnt.h>
#include <kern/thread.h>
#include <machine/cpu.h>

/*
 * Maximum number of deltas per cache.
 */
#define SREF_MAX_DELTAS 4096

#ifdef __LP64__
#define SREF_HASH_SHIFT 3
#else /* __LP64__ */
#define SREF_HASH_SHIFT 2
#endif /* __LP64__ */

/*
 * Number of counters in review queue beyond which to issue a warning.
 */
#define SREF_NR_COUNTERS_WARN 10000

struct sref_queue {
    struct slist counters;
    unsigned long size;
};

/*
 * Global data.
 *
 * If there is a pending flush, its associated CPU must be registered.
 * Notwithstanding transient states, the number of pending flushes is 0
 * if and only if no processor is registered, in which case the sref
 * module, and probably the whole system, is completely idle.
 *
 * The review queue is implemented with two queues of counters, one for
 * each of the last two epochs. The current queue ID is updated when a
 * new epoch starts, and the queues are flipped.
 */
struct sref_data {
    struct spinlock lock;
    struct cpumap registered_cpus;      /* TODO Review usage */
    unsigned int nr_registered_cpus;
    struct cpumap pending_flushes;      /* TODO Review usage */
    unsigned int nr_pending_flushes;
    unsigned int current_queue_id;
    struct sref_queue queues[2];
    struct syscnt sc_epochs;
    struct syscnt sc_dirty_zeroes;
    struct syscnt sc_revives;
    struct syscnt sc_true_zeroes;
    bool no_warning;
};

/*
 * Temporary difference to apply on a reference counter.
 *
 * Deltas are stored in per-processor caches and added to their global
 * counter when flushed. A delta is valid if and only if the counter it
 * points to isn't NULL.
 *
 * On cache flush, if a delta is valid, it must be flushed whatever its
 * value because a delta can be a dirty zero too. By flushing all valid
 * deltas, and clearing them all after a flush, activity on a counter is
 * reliably reported.
 */
struct sref_delta {
    struct list node;
    struct sref_counter *counter;
    unsigned long value;
};

/*
 * Per-processor cache of deltas.
 *
 * Delta caches are implemented with hash tables for quick ref count to
 * delta lookups. For now, a very simple replacement policy, similar to
 * that described in the RadixVM paper, is used. Improve with an LRU-like
 * algorithm if this turns out to be a problem.
 *
 * Manager threads periodically flush deltas and process the review queue.
 * Waking up a manager thread must be done with interrupts disabled to
 * prevent a race with the periodic event that drives regular flushes
 * (normally the periodic timer interrupt).
 *
 * Interrupts and preemption must be disabled when accessing a delta cache.
 */
struct sref_cache {
    struct sref_delta deltas[SREF_MAX_DELTAS];
    struct list valid_deltas;
    struct syscnt sc_collisions;
    struct syscnt sc_flushes;
    struct thread *manager;
    bool registered;
    bool dirty;
};

static struct sref_data sref_data;
static struct sref_cache sref_cache __percpu;

static struct sref_queue *
sref_prev_queue(void)
{
    return &sref_data.queues[!sref_data.current_queue_id];
}

static struct sref_queue *
sref_current_queue(void)
{
    return &sref_data.queues[sref_data.current_queue_id];
}

static void __init
sref_queue_init(struct sref_queue *queue)
{
    slist_init(&queue->counters);
    queue->size = 0;
}

static unsigned long
sref_queue_size(const struct sref_queue *queue)
{
    return queue->size;
}

static bool
sref_queue_empty(const struct sref_queue *queue)
{
    return queue->size == 0;
}

static void
sref_queue_push(struct sref_queue *queue, struct sref_counter *counter)
{
    slist_insert_tail(&queue->counters, &counter->node);
    queue->size++;
}

static struct sref_counter *
sref_queue_pop(struct sref_queue *queue)
{
    struct sref_counter *counter;

    counter = slist_first_entry(&queue->counters, typeof(*counter), node);
    slist_remove(&queue->counters, NULL);
    queue->size--;
    return counter;
}

static void
sref_queue_transfer(struct sref_queue *dest, struct sref_queue *src)
{
    slist_set_head(&dest->counters, &src->counters);
    dest->size = src->size;
}

static void
sref_queue_concat(struct sref_queue *queue1, struct sref_queue *queue2)
{
    slist_concat(&queue1->counters, &queue2->counters);
    queue1->size += queue2->size;
}

static bool
sref_counter_aligned(const struct sref_counter *counter)
{
    return ((uintptr_t)counter & (~SREF_WEAKREF_MASK)) == 0;
}

static void
sref_weakref_init(struct sref_weakref *weakref, struct sref_counter *counter)
{
    assert(sref_counter_aligned(counter));
    weakref->addr = (uintptr_t)counter;
}

static void
sref_weakref_mark_dying(struct sref_weakref *weakref)
{
    atomic_or(&weakref->addr, SREF_WEAKREF_DYING, ATOMIC_RELAXED);
}

static void
sref_weakref_clear_dying(struct sref_weakref *weakref)
{
    atomic_and(&weakref->addr, SREF_WEAKREF_MASK, ATOMIC_RELAXED);
}

static int
sref_weakref_kill(struct sref_weakref *weakref)
{
    uintptr_t addr, oldval;

    addr = atomic_load(&weakref->addr, ATOMIC_RELAXED) | SREF_WEAKREF_DYING;
    oldval = atomic_cas(&weakref->addr, addr, (uintptr_t)NULL, ATOMIC_RELAXED);

    if (oldval != addr) {
        assert((oldval & SREF_WEAKREF_MASK) == (addr & SREF_WEAKREF_MASK));
        return EBUSY;
    }

    return 0;
}

static struct sref_counter *
sref_weakref_tryget(struct sref_weakref *weakref)
{
    uintptr_t addr, oldval, newval;

    do {
        addr = atomic_load(&weakref->addr, ATOMIC_RELAXED);
        newval = addr & SREF_WEAKREF_MASK;
        oldval = atomic_cas(&weakref->addr, addr, newval, ATOMIC_RELAXED);
    } while (oldval != addr);

    return (struct sref_counter *)newval;
}

static uintptr_t
sref_counter_hash(const struct sref_counter *counter)
{
    uintptr_t va;

    va = (uintptr_t)counter;

    assert(P2ALIGNED(va, 1UL << SREF_HASH_SHIFT));
    return va >> SREF_HASH_SHIFT;
}

static uintptr_t
sref_counter_index(const struct sref_counter *counter)
{
    return sref_counter_hash(counter) & (SREF_MAX_DELTAS - 1);
}

static bool
sref_counter_is_queued(const struct sref_counter *counter)
{
    return counter->flags & SREF_QUEUED;
}

static void
sref_counter_mark_queued(struct sref_counter *counter)
{
    counter->flags |= SREF_QUEUED;
}

static void
sref_counter_clear_queued(struct sref_counter *counter)
{
    counter->flags &= ~SREF_QUEUED;
}

static bool
sref_counter_is_dirty(const struct sref_counter *counter)
{
    return counter->flags & SREF_DIRTY;
}

static void
sref_counter_mark_dirty(struct sref_counter *counter)
{
    counter->flags |= SREF_DIRTY;
}

static void
sref_counter_clear_dirty(struct sref_counter *counter)
{
    counter->flags &= ~SREF_DIRTY;
}

static void
sref_counter_mark_dying(struct sref_counter *counter)
{
    if (counter->weakref == NULL) {
        return;
    }

    sref_weakref_mark_dying(counter->weakref);
}

static void
sref_counter_clear_dying(struct sref_counter *counter)
{
    if (counter->weakref == NULL) {
        return;
    }

    sref_weakref_clear_dying(counter->weakref);
}

static int
sref_counter_kill_weakref(struct sref_counter *counter)
{
    if (counter->weakref == NULL) {
        return 0;
    }

    return sref_weakref_kill(counter->weakref);
}

static void
sref_counter_schedule_review(struct sref_counter *counter)
{
    assert(!sref_counter_is_queued(counter));
    assert(!sref_counter_is_dirty(counter));

    sref_counter_mark_queued(counter);
    sref_counter_mark_dying(counter);

    spinlock_lock(&sref_data.lock);
    sref_queue_push(sref_current_queue(), counter);
    spinlock_unlock(&sref_data.lock);
}

static void
sref_counter_add(struct sref_counter *counter, unsigned long delta)
{
    assert(!cpu_intr_enabled());

    spinlock_lock(&counter->lock);

    counter->value += delta;

    if (counter->value == 0) {
        if (sref_counter_is_queued(counter)) {
            sref_counter_mark_dirty(counter);
        } else {
            sref_counter_schedule_review(counter);
        }
    }

    spinlock_unlock(&counter->lock);
}

static void __init
sref_delta_init(struct sref_delta *delta)
{
    delta->counter = NULL;
    delta->value = 0;
}

static struct sref_counter *
sref_delta_counter(struct sref_delta *delta)
{
    return delta->counter;
}

static void
sref_delta_set_counter(struct sref_delta *delta, struct sref_counter *counter)
{
    assert(delta->value == 0);
    delta->counter = counter;
}

static void
sref_delta_clear(struct sref_delta *delta)
{
    assert(delta->value == 0);
    delta->counter = NULL;
}

static void
sref_delta_inc(struct sref_delta *delta)
{
    delta->value++;
}

static void
sref_delta_dec(struct sref_delta *delta)
{
    delta->value--;
}

static bool
sref_delta_is_valid(const struct sref_delta *delta)
{
    return delta->counter;
}

static void
sref_delta_flush(struct sref_delta *delta)
{
    sref_counter_add(delta->counter, delta->value);
    delta->value = 0;
}

static void
sref_delta_evict(struct sref_delta *delta)
{
    sref_delta_flush(delta);
    sref_delta_clear(delta);
}

static unsigned long
sref_review_queue_size(void)
{
    return sref_queue_size(&sref_data.queues[0])
           + sref_queue_size(&sref_data.queues[1]);
}

static bool
sref_review_queue_empty(void)
{
    return sref_review_queue_size() == 0;
}

static void
sref_reset_pending_flushes(void)
{
    cpumap_copy(&sref_data.pending_flushes, &sref_data.registered_cpus);
    sref_data.nr_pending_flushes = sref_data.nr_registered_cpus;
}

static void
sref_end_epoch(struct sref_queue *queue)
{
    struct sref_queue *prev_queue, *current_queue;

    assert(cpumap_find_first(&sref_data.registered_cpus) != -1);
    assert(sref_data.nr_registered_cpus != 0);
    assert(cpumap_find_first(&sref_data.pending_flushes) == -1);
    assert(sref_data.nr_pending_flushes == 0);

    if (!sref_data.no_warning
        && (sref_review_queue_size() >= SREF_NR_COUNTERS_WARN)) {
        sref_data.no_warning = 1;
        log_warning("sref: large number of counters in review queue");
    }

    prev_queue = sref_prev_queue();
    current_queue = sref_current_queue();

    if (sref_data.nr_registered_cpus == 1) {
        sref_queue_concat(prev_queue, current_queue);
        sref_queue_init(current_queue);
    }

    sref_queue_transfer(queue, prev_queue);
    sref_queue_init(prev_queue);
    sref_data.current_queue_id = !sref_data.current_queue_id;
    syscnt_inc(&sref_data.sc_epochs);
    sref_reset_pending_flushes();
}

static struct sref_delta *
sref_cache_delta(struct sref_cache *cache, size_t i)
{
    assert(i < ARRAY_SIZE(cache->deltas));
    return &cache->deltas[i];
}

static void __init
sref_cache_init(struct sref_cache *cache, unsigned int cpu)
{
    char name[SYSCNT_NAME_SIZE];
    struct sref_delta *delta;

    for (size_t i = 0; i < ARRAY_SIZE(cache->deltas); i++) {
        delta = sref_cache_delta(cache, i);
        sref_delta_init(delta);
    }

    list_init(&cache->valid_deltas);
    snprintf(name, sizeof(name), "sref_collisions/%u", cpu);
    syscnt_register(&cache->sc_collisions, name);
    snprintf(name, sizeof(name), "sref_flushes/%u", cpu);
    syscnt_register(&cache->sc_flushes, name);
    cache->manager = NULL;
    cache->registered = false;
    cache->dirty = false;
}

static struct sref_cache *
sref_cache_get(void)
{
    return cpu_local_ptr(sref_cache);
}

static struct sref_cache *
sref_cache_acquire(unsigned long *flags)
{
    struct sref_cache *cache;

    thread_preempt_disable_intr_save(flags);
    cache = sref_cache_get();
    return cache;
}

static void
sref_cache_release(unsigned long flags)
{
    thread_preempt_enable_intr_restore(flags);
}

static bool
sref_cache_is_registered(const struct sref_cache *cache)
{
    return cache->registered;
}

static void
sref_cache_mark_registered(struct sref_cache *cache)
{
    cache->registered = true;
}

static void
sref_cache_clear_registered(struct sref_cache *cache)
{
    cache->registered = false;
}

static bool
sref_cache_is_dirty(const struct sref_cache *cache)
{
    return cache->dirty;
}

static void
sref_cache_mark_dirty(struct sref_cache *cache)
{
    cache->dirty = true;
}

static void
sref_cache_clear_dirty(struct sref_cache *cache)
{
    cache->dirty = false;
}

static void
sref_cache_add_delta(struct sref_cache *cache, struct sref_delta *delta,
                     struct sref_counter *counter)
{
    assert(!sref_delta_is_valid(delta));
    assert(counter);

    sref_delta_set_counter(delta, counter);
    list_insert_tail(&cache->valid_deltas, &delta->node);
}

static void
sref_cache_remove_delta(struct sref_delta *delta)
{
    assert(sref_delta_is_valid(delta));

    sref_delta_evict(delta);
    list_remove(&delta->node);
}

static struct sref_delta *
sref_cache_get_delta(struct sref_cache *cache, struct sref_counter *counter)
{
    struct sref_delta *delta;

    delta = sref_cache_delta(cache, sref_counter_index(counter));

    if (!sref_delta_is_valid(delta)) {
        sref_cache_add_delta(cache, delta, counter);
    } else if (sref_delta_counter(delta) != counter) {
        sref_cache_remove_delta(delta);
        sref_cache_add_delta(cache, delta, counter);
        syscnt_inc(&cache->sc_collisions);
    }

    return delta;
}

static void
sref_cache_flush(struct sref_cache *cache, struct sref_queue *queue)
{
    struct sref_delta *delta;
    unsigned long flags;
    unsigned int cpu;

    for (;;) {
        thread_preempt_disable_intr_save(&flags);

        if (list_empty(&cache->valid_deltas)) {
            break;
        }

        delta = list_first_entry(&cache->valid_deltas, typeof(*delta), node);
        sref_cache_remove_delta(delta);

        thread_preempt_enable_intr_restore(flags);
    }

    cpu_intr_restore(flags);

    cpu = cpu_id();

    spinlock_lock(&sref_data.lock);

    assert(sref_cache_is_registered(cache));
    assert(cpumap_test(&sref_data.registered_cpus, cpu));

    if (!cpumap_test(&sref_data.pending_flushes, cpu)) {
        sref_queue_init(queue);
    } else {
        cpumap_clear(&sref_data.pending_flushes, cpu);
        sref_data.nr_pending_flushes--;

        if (sref_data.nr_pending_flushes != 0) {
            sref_queue_init(queue);
        } else {
            sref_end_epoch(queue);
        }
    }

    spinlock_unlock(&sref_data.lock);

    sref_cache_clear_dirty(cache);
    syscnt_inc(&cache->sc_flushes);

    thread_preempt_enable();
}

static void
sref_cache_manage(struct sref_cache *cache)
{
    assert(!cpu_intr_enabled());
    assert(!thread_preempt_enabled());

    sref_cache_mark_dirty(cache);
    thread_wakeup(cache->manager);
}

static bool
sref_cache_check(struct sref_cache *cache)
{
    if (!sref_cache_is_dirty(cache)) {
        return false;
    }

    sref_cache_manage(cache);
    return true;
}

static void
sref_noref(struct work *work)
{
    struct sref_counter *counter;

    counter = structof(work, struct sref_counter, work);
    counter->noref_fn(counter);
}

static void
sref_review(struct sref_queue *queue)
{
    int64_t nr_dirty, nr_revive, nr_true;
    struct sref_counter *counter;
    struct work_queue works;
    unsigned long flags;
    bool requeue;
    int error;

    nr_dirty = 0;
    nr_revive = 0;
    nr_true = 0;
    work_queue_init(&works);

    while (!sref_queue_empty(queue)) {
        counter = sref_queue_pop(queue);

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

        assert(sref_counter_is_queued(counter));
        sref_counter_clear_queued(counter);

        if (counter->value != 0) {
            sref_counter_clear_dirty(counter);
            sref_counter_clear_dying(counter);
            spinlock_unlock_intr_restore(&counter->lock, flags);
        } else {
            if (sref_counter_is_dirty(counter)) {
                requeue = true;
                nr_dirty++;
                sref_counter_clear_dirty(counter);
            } else {
                error = sref_counter_kill_weakref(counter);

                if (!error) {
                    requeue = false;
                } else {
                    requeue = true;
                    nr_revive++;
                }
            }

            if (requeue) {
                sref_counter_schedule_review(counter);
                spinlock_unlock_intr_restore(&counter->lock, flags);
            } else {
                /*
                 * Keep in mind that the work structure shares memory with
                 * the counter data. Unlocking isn't needed here, since this
                 * counter is now really at 0, but do it for consistency.
                 */
                spinlock_unlock_intr_restore(&counter->lock, flags);
                nr_true++;
                work_init(&counter->work, sref_noref);
                work_queue_push(&works, &counter->work);
            }
        }
    }

    if (work_queue_nr_works(&works) != 0) {
        work_queue_schedule(&works, 0);
    }

    if ((nr_dirty + nr_revive + nr_true) != 0) {
        spinlock_lock(&sref_data.lock);
        syscnt_add(&sref_data.sc_dirty_zeroes, nr_dirty);
        syscnt_add(&sref_data.sc_revives, nr_revive);
        syscnt_add(&sref_data.sc_true_zeroes, nr_true);
        spinlock_unlock(&sref_data.lock);
    }
}

static void
sref_manage(void *arg)
{
    struct sref_cache *cache;
    struct sref_queue queue;
    unsigned long flags;

    cache = arg;

    for (;;) {
        thread_preempt_disable_intr_save(&flags);

        while (!sref_cache_is_dirty(cache)) {
            thread_sleep(NULL, cache, "sref");
        }

        thread_preempt_enable_intr_restore(flags);

        sref_cache_flush(cache, &queue);
        sref_review(&queue);
    }

    /* Never reached */
}

static int __init
sref_bootstrap(void)
{
    spinlock_init(&sref_data.lock);

    sref_data.current_queue_id = 0;

    for (size_t i = 0; i < ARRAY_SIZE(sref_data.queues); i++) {
        sref_queue_init(&sref_data.queues[i]);
    }

    syscnt_register(&sref_data.sc_epochs, "sref_epochs");
    syscnt_register(&sref_data.sc_dirty_zeroes, "sref_dirty_zeroes");
    syscnt_register(&sref_data.sc_revives, "sref_revives");
    syscnt_register(&sref_data.sc_true_zeroes, "sref_true_zeroes");

    sref_cache_init(sref_cache_get(), 0);

    return 0;
}

INIT_OP_DEFINE(sref_bootstrap,
               INIT_OP_DEP(cpu_setup, true),
               INIT_OP_DEP(spinlock_setup, true),
               INIT_OP_DEP(syscnt_setup, true));

static void __init
sref_setup_manager(struct sref_cache *cache, unsigned int cpu)
{
    char name[THREAD_NAME_SIZE];
    struct thread_attr attr;
    struct thread *manager;
    struct cpumap *cpumap;
    int error;

    error = cpumap_create(&cpumap);

    if (error) {
        panic("sref: unable to create manager thread CPU map");
    }

    cpumap_zero(cpumap);
    cpumap_set(cpumap, cpu);
    snprintf(name, sizeof(name), THREAD_KERNEL_PREFIX "sref_manage/%u", cpu);
    thread_attr_init(&attr, name);
    thread_attr_set_cpumap(&attr, cpumap);
    thread_attr_set_priority(&attr, THREAD_SCHED_FS_PRIO_MAX);
    error = thread_create(&manager, &attr, sref_manage, cache);
    cpumap_destroy(cpumap);

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

    cache->manager = manager;
}

static int __init
sref_setup(void)
{
    for (unsigned int i = 1; i < cpu_count(); i++) {
        sref_cache_init(percpu_ptr(sref_cache, i), i);
    }

    for (unsigned int i = 0; i < cpu_count(); i++) {
        sref_setup_manager(percpu_ptr(sref_cache, i), i);
    }

    return 0;
}

INIT_OP_DEFINE(sref_setup,
               INIT_OP_DEP(cpu_mp_probe, true),
               INIT_OP_DEP(cpumap_setup, true),
               INIT_OP_DEP(log_setup, true),
               INIT_OP_DEP(sref_bootstrap, true),
               INIT_OP_DEP(thread_setup, true));

void
sref_register(void)
{
    struct sref_cache *cache;
    unsigned int cpu;

    assert(!thread_preempt_enabled());

    cache = sref_cache_get();
    assert(!sref_cache_is_registered(cache));
    assert(!sref_cache_is_dirty(cache));

    cpu = cpu_id();

    spinlock_lock(&sref_data.lock);

    assert(!cpumap_test(&sref_data.registered_cpus, cpu));
    cpumap_set(&sref_data.registered_cpus, cpu);
    sref_data.nr_registered_cpus++;

    if ((sref_data.nr_registered_cpus == 1)
        && (sref_data.nr_pending_flushes == 0)) {
        assert(sref_review_queue_empty());
        sref_reset_pending_flushes();
    }

    spinlock_unlock(&sref_data.lock);

    sref_cache_mark_registered(cache);
}

int
sref_unregister(void)
{
    struct sref_cache *cache;
    unsigned long flags;
    unsigned int cpu;
    bool dirty;
    int error;

    assert(!thread_preempt_enabled());

    cache = sref_cache_get();

    cpu_intr_save(&flags);

    assert(sref_cache_is_registered(cache));
    sref_cache_clear_registered(cache);
    dirty = sref_cache_check(cache);

    if (dirty) {
        sref_cache_mark_registered(cache);
        error = EBUSY;
        goto out;
    }

    cpu = cpu_id();

    spinlock_lock(&sref_data.lock);

    assert(cpumap_test(&sref_data.registered_cpus, cpu));

    if (!cpumap_test(&sref_data.pending_flushes, cpu)) {
        assert(sref_data.nr_pending_flushes != 0);
        error = 0;
    } else if ((sref_data.nr_registered_cpus == 1)
               && (sref_data.nr_pending_flushes == 1)
               && sref_review_queue_empty()) {
        cpumap_clear(&sref_data.pending_flushes, cpu);
        sref_data.nr_pending_flushes--;
        error = 0;
    } else {
        sref_cache_manage(cache);
        error = EBUSY;
    }

    if (error) {
        sref_cache_mark_registered(cache);
    } else {
        cpumap_clear(&sref_data.registered_cpus, cpu);
        sref_data.nr_registered_cpus--;
    }

    spinlock_unlock(&sref_data.lock);

out:
    cpu_intr_restore(flags);

    return error;
}

void
sref_report_periodic_event(void)
{
    struct sref_cache *cache;

    assert(thread_check_intr_context());

    cache = sref_cache_get();

    if (!sref_cache_is_registered(cache)) {
        return;
    }

    sref_cache_manage(cache);
}

void
sref_counter_init(struct sref_counter *counter,
                  unsigned long init_value,
                  struct sref_weakref *weakref,
                  sref_noref_fn_t noref_fn)
{
    assert(init_value != 0);

    counter->noref_fn = noref_fn;
    spinlock_init(&counter->lock);
    counter->flags = 0;
    counter->value = init_value;
    counter->weakref = weakref;

    if (weakref) {
        sref_weakref_init(weakref, counter);
    }
}

static void
sref_counter_inc_common(struct sref_counter *counter, struct sref_cache *cache)
{
    struct sref_delta *delta;

    sref_cache_mark_dirty(cache);
    delta = sref_cache_get_delta(cache, counter);
    sref_delta_inc(delta);
}

void
sref_counter_inc(struct sref_counter *counter)
{
    struct sref_cache *cache;
    unsigned long flags;

    cache = sref_cache_acquire(&flags);
    sref_counter_inc_common(counter, cache);
    sref_cache_release(flags);
}

void
sref_counter_dec(struct sref_counter *counter)
{
    struct sref_cache *cache;
    struct sref_delta *delta;
    unsigned long flags;

    cache = sref_cache_acquire(&flags);
    sref_cache_mark_dirty(cache);
    delta = sref_cache_get_delta(cache, counter);
    sref_delta_dec(delta);
    sref_cache_release(flags);
}

struct sref_counter *
sref_weakref_get(struct sref_weakref *weakref)
{
    struct sref_counter *counter;
    struct sref_cache *cache;
    unsigned long flags;

    cache = sref_cache_acquire(&flags);

    counter = sref_weakref_tryget(weakref);

    if (counter) {
        sref_counter_inc_common(counter, cache);
    }

    sref_cache_release(flags);

    return counter;
}


code:
/*
 * Copyright (c) 2014-2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Scalable reference counting.
 *
 * The purpose of this module is to reduce the amount of inter-processor
 * communication usually involved with reference counting. Scalable
 * reference counters should only be used when multiprocessor scalability
 * is important because of the costs they imply (increased memory usage
 * and latencies).
 *
 * When a counter drops to 0, the no-reference function associated with it
 * is called in work context. As a result, special care must be taken if
 * using sref counters in the work module itself.
 */

#ifndef KERN_SREF_H
#define KERN_SREF_H

#include <kern/init.h>

/*
 * Scalable reference counter.
 */
struct sref_counter;

/*
 * Weak reference.
 */
struct sref_weakref;

/*
 * Type for no-reference functions.
 */
typedef void (*sref_noref_fn_t)(struct sref_counter *);

#include <kern/sref_i.h>

/*
 * Manage registration of the current processor.
 *
 * Registering tells the sref module that the current processor reports
 * periodic events. When a processor enters a state in which reporting
 * periodic events becomes irrelevant, it unregisters itself so that the
 * other registered processors don't need to wait for it to make progress.
 * For example, this is done inside the idle loop since it is obviously
 * impossible to obtain or release references while idling.
 *
 * Unregistration can fail if internal data still require processing, in
 * which case a maintenance thread is awaken and EBUSY is returned.
 *
 * Preemption must be disabled when calling these functions.
 */
void sref_register(void);
int sref_unregister(void);

/*
 * Report a periodic event (normally the periodic timer interrupt) on the
 * current processor.
 *
 * Interrupts and preemption must be disabled when calling this function.
 */
void sref_report_periodic_event(void);

/*
 * Initialize a scalable reference counter.
 *
 * The no-reference function is called (from thread context) when it is
 * certain that the true number of references is 0.
 */
void sref_counter_init(struct sref_counter *counter,
                       unsigned long init_value,
                       struct sref_weakref *weakref,
                       sref_noref_fn_t noref_fn);

/*
 * Counter operations.
 *
 * These functions may safely be called in interrupt context.
 *
 * These functions imply a compiler barrier.
 */
void sref_counter_inc(struct sref_counter *counter);
void sref_counter_dec(struct sref_counter *counter);

/*
 * Attempt to get a reference from a weak reference.
 *
 * If successful, increment the reference counter before returning it.
 * Otherwise return NULL.
 *
 * This function may safely be called in interrupt context.
 */
struct sref_counter * sref_weakref_get(struct sref_weakref *weakref);

/*
 * This init operation provides :
 *  - sref counter and weakref initialization and usage
 */
INIT_OP_DECLARE(sref_bootstrap);

#endif /* KERN_SREF_H */

license: mit


code:
/*
 * Copyright (c) 2014-2018 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef KERN_SREF_I_H
#define KERN_SREF_I_H

#include <stdint.h>

#include <kern/slist.h>
#include <kern/spinlock.h>
#include <kern/work.h>

#define SREF_WEAKREF_DYING  ((uintptr_t)1)
#define SREF_WEAKREF_MASK   (~SREF_WEAKREF_DYING)

/*
 * Weak reference.
 *
 * A weak reference is a pointer to a reference counter in which the
 * least-significant bit is used to indicate whether the counter is
 * "dying", i.e. about to be destroyed.
 *
 * It must be accessed with atomic instructions. There is no need to
 * enforce memory order on access since the only data that depends on
 * the weak reference are cpu-local deltas.
 */
struct sref_weakref {
    uintptr_t addr;
};

#define SREF_QUEUED 0x1
#define SREF_DIRTY  0x2

/*
 * Scalable reference counter.
 *
 * It's tempting to merge the flags into the node member, but since they're
 * not protected by the same lock, store them separately.
 *
 * Locking keys :
 * (c) sref_counter
 * (g) sref_data
 *
 * Interrupts must be disabled when accessing a global counter.
 */
struct sref_counter {
    sref_noref_fn_t noref_fn;

    union {
        struct {
            struct slist_node node;         /* (g) */
            struct spinlock lock;
            int flags;                      /* (c) */
            unsigned long value;            /* (c) */
            struct sref_weakref *weakref;
        };

        struct work work;
    };
};

#endif /* KERN_SREF_I_H */


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/>.
 *
 *
 * Trivial, portable implementations.
 */

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

#include <kern/macros.h>
#include <machine/string.h>

#ifndef STRING_ARCH_MEMCPY
void *
memcpy(void *dest, const void *src, size_t n)
{
    const char *src_ptr;
    char *dest_ptr;
    size_t i;

    dest_ptr = dest;
    src_ptr = src;

    for (i = 0; i < n; i++) {
        *dest_ptr = *src_ptr;
        dest_ptr++;
        src_ptr++;
    }

    return dest;
}
#endif /* STRING_ARCH_MEMCPY */

#ifndef STRING_ARCH_MEMMOVE
void *
memmove(void *dest, const void *src, size_t n)
{
    const char *src_ptr;
    char *dest_ptr;
    size_t i;

    if (dest <= src) {
        dest_ptr = dest;
        src_ptr = src;

        for (i = 0; i < n; i++) {
            *dest_ptr = *src_ptr;
            dest_ptr++;
            src_ptr++;
        }
    } else {
        dest_ptr = dest + n - 1;
        src_ptr = src + n - 1;

        for (i = 0; i < n; i++) {
            *dest_ptr = *src_ptr;
            dest_ptr--;
            src_ptr--;
        }
    }

    return dest;
}
#endif /* STRING_ARCH_MEMMOVE */

#ifndef STRING_ARCH_MEMSET
void *
memset(void *s, int c, size_t n)
{
    char *buffer;
    size_t i;

    buffer = s;

    for (i = 0; i < n; i++) {
        buffer[i] = c;
    }

    return s;
}
#endif /* STRING_ARCH_MEMSET */

#ifndef STRING_ARCH_MEMCMP
int
memcmp(const void *s1, const void *s2, size_t n)
{
    const unsigned char *a1, *a2;
    size_t i;

    a1 = s1;
    a2 = s2;

    for (i = 0; i < n; i++) {
        if (a1[i] != a2[i]) {
            return (int)a1[i] - (int)a2[i];
        }
    }

    return 0;
}
#endif /* STRING_ARCH_MEMCMP */

#ifndef STRING_ARCH_STRLEN
size_t
strlen(const char *s)
{
    const char *start;

    start = s;

    while (*s != '\0') {
        s++;
    }

    return (s - start);
}
#endif /* STRING_ARCH_STRLEN */

#ifndef STRING_ARCH_STRCPY
char *
strcpy(char *dest, const char *src)
{
    char *tmp;

    tmp = dest;

    while ((*dest = *src) != '\0') {
        dest++;
        src++;
    }

    return tmp;
}
#endif /* STRING_ARCH_STRCPY */

size_t
strlcpy(char *dest, const char *src, size_t n)
{
    size_t len;

    len = strlen(src);

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

    n = (len < n) ? len : n - 1;
    memcpy(dest, src, n);
    dest[n] = '\0';

out:
    return len;
}

#ifndef STRING_ARCH_STRCMP
int
strcmp(const char *s1, const char *s2)
{
    char c1, c2;

    while ((c1 = *s1) == (c2 = *s2)) {
        if (c1 == '\0') {
            return 0;
        }

        s1++;
        s2++;
    }

    /* See C11 7.24.4 Comparison functions */
    return (int)(unsigned char)c1 - (int)(unsigned char)c2;
}
#endif /* STRING_ARCH_STRCMP */

#ifndef STRING_ARCH_STRNCMP
int
strncmp(const char *s1, const char *s2, size_t n)
{
    char c1, c2;

    if (unlikely(n == 0)) {
        return 0;
    }

    while ((n != 0) && (c1 = *s1) == (c2 = *s2)) {
        if (c1 == '\0') {
            return 0;
        }

        n--;
        s1++;
        s2++;
    }

    /* See C11 7.24.4 Comparison functions */
    return (int)(unsigned char)c1 - (int)(unsigned char)c2;
}
#endif /* STRING_ARCH_STRNCMP */

#ifndef STRING_ARCH_STRCHR
char *
strchr(const char *s, int c)
{
    for (;;) {
        if (*s == c) {
            return (char *)s;
        } else if (*s == '\0') {
            return NULL;
        }

        s++;
    }
}
#endif /* STRING_ARCH_STRCHR */

const char *
strerror(int error)
{
    switch (error) {
    case 0:
        return "success";
    case ENOMEM:
        return "out of memory";
    case EAGAIN:
        return "resource temporarily unavailable";
    case EINVAL:
        return "invalid argument";
    case EBUSY:
        return "device or resource busy";
    case EFAULT:
        return "bad address";
    case ENODEV:
        return "no such device";
    case EEXIST:
        return "entry exists";
    case EIO:
        return "input/output error";
    case ESRCH:
        return "no such process";
    case ETIMEDOUT:
        return "timeout error";
    case ENOENT:
        return "no such file or directory";
    default:
        return "unknown 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_STRING_H
#define KERN_STRING_H

#include <stddef.h>

void * memcpy(void * restrict dest, const void * restrict src, size_t n);
void * memmove(void *dest, const void *src, size_t n);
void * memset(void *s, int c, size_t n);
int memcmp(const void *s1, const void *s2, size_t n);
size_t strlen(const char *s);
char * strcpy(char * restrict dest, const char *restrict src);
size_t strlcpy(char * restrict dest, const char * restrict src, size_t n);
int strcmp(const char *s1, const char *s2);
int strncmp(const char *s1, const char *s2, size_t n);
char * strchr(const char *s, int c);
const char * strerror(int error);

#endif /* KERN_STRING_H */


code:
/*
 * Copyright (c) 2018 Agustina Arzille.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

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

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

/*
 * XXX Clang doesn't consider that weak symbols may change at link time
 * by default, which turns the lookup into a no-op when optimizations
 * are enabled. Make these variables volatile to work around this issue.
 */
const volatile size_t symbol_table_size __weak;
const struct symbol * volatile symbol_table_ptr __weak;

const struct symbol *
symbol_lookup(uintptr_t addr)
{
    const struct symbol *table, *symbol;
    uintptr_t start, end;
    size_t size;

    table = symbol_table_ptr;
    size = symbol_table_size;

    for (size_t i = 0; i < size; i++) {
        symbol = &table[i];

        if (!symbol->name || (symbol->size == 0)) {
            continue;
        }

        start = symbol->addr;
        end = symbol->addr + symbol->size;

        if ((addr >= start) && (addr < end)) {
            return symbol;
        }
    }

    return NULL;
}


code:
/*
 * Copyright (c) 2018 Agustina Arzille.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef KERN_SYMBOL_H
#define KERN_SYMBOL_H

#include <stdint.h>

#include <kern/macros.h>

#define __symbol_table __section(".symbol")

/*
 * Symbol structure.
 *
 * This structure is public.
 */
struct symbol {
    uintptr_t addr;
    uintptr_t size;
    const char *name;
};

/*
 * Look up a symbol from an address.
 *
 * NULL is returned if no symbol was found for the given address.
 */
const struct symbol * symbol_lookup(uintptr_t addr);

#endif /* KERN_SYMBOL_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 <stdio.h>
#include <string.h>

#include <kern/atomic.h>
#include <kern/init.h>
#include <kern/list.h>
#include <kern/mutex.h>
#include <kern/shell.h>
#include <kern/spinlock.h>
#include <kern/syscnt.h>
#include <kern/thread.h>

/*
 * Global list of all registered counters.
 */
static struct list syscnt_list;
static struct mutex syscnt_lock;

#ifdef CONFIG_SHELL

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

    (void)shell;

    prefix = (argc >= 2) ? argv[1] : NULL;
    syscnt_info(prefix);
}

static struct shell_cmd syscnt_shell_cmds[] = {
    SHELL_CMD_INITIALIZER("syscnt_info", syscnt_shell_info,
                          "syscnt_info [<prefix>]",
                          "display information about system counters"),
};

static int __init
syscnt_setup_shell(void)
{
    SHELL_REGISTER_CMDS(syscnt_shell_cmds, shell_get_main_cmd_set());
    return 0;
}

INIT_OP_DEFINE(syscnt_setup_shell,
               INIT_OP_DEP(shell_setup, true),
               INIT_OP_DEP(syscnt_setup, true));

#endif /* CONFIG_SHELL */

static int __init
syscnt_setup(void)
{
    list_init(&syscnt_list);
    mutex_init(&syscnt_lock);
    return 0;
}

/*
 * Do not make initialization depend on mutex_setup, since mutex
 * modules may use system counters for debugging.
 */
INIT_OP_DEFINE(syscnt_setup,
               INIT_OP_DEP(mutex_bootstrap, true),
               INIT_OP_DEP(spinlock_setup, true));

void __init
syscnt_register(struct syscnt *syscnt, const char *name)
{
#ifndef ATOMIC_HAVE_64B_OPS
    spinlock_init(&syscnt->lock);
#endif
    syscnt->value = 0;
    strlcpy(syscnt->name, name, sizeof(syscnt->name));

    mutex_lock(&syscnt_lock);
    list_insert_tail(&syscnt_list, &syscnt->node);
    mutex_unlock(&syscnt_lock);
}

void
syscnt_info(const char *prefix)
{
    struct syscnt *syscnt;
    size_t length, prefix_length;
    uint64_t value;

    prefix_length = (prefix == NULL) ? 0 : strlen(prefix);

    mutex_lock(&syscnt_lock);

    list_for_each_entry(&syscnt_list, syscnt, node) {
        if (prefix_length != 0) {
            length = strlen(syscnt->name);

            if ((length < prefix_length)
                || (memcmp(syscnt->name, prefix, prefix_length) != 0)) {
                continue;
            }
        }

        value = syscnt_read(syscnt);

        printf("syscnt: %40s %20llu\n", syscnt->name,
               (unsigned long long)value);
    }

    mutex_unlock(&syscnt_lock);
}


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/>.
 *
 *
 * System counters.
 *
 * This module provides 64-bits general-purpose counters that can be
 * accessed and modified atomically from any context.
 */

#ifndef KERN_SYSCNT_H
#define KERN_SYSCNT_H

#include <stdint.h>

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

/*
 * Size of the buffer storing a system counter name.
 */
#define SYSCNT_NAME_SIZE 32

#include <kern/syscnt_types.h>

/*
 * System counter.
 */
struct syscnt;

/*
 * Initialize and register the given counter.
 *
 * The counter is set to 0.
 */
void syscnt_register(struct syscnt *syscnt, const char *name);

#ifdef ATOMIC_HAVE_64B_OPS

static inline void
syscnt_set(struct syscnt *syscnt, uint64_t value)
{
    atomic_store(&syscnt->value, value, ATOMIC_RELAXED);
}

static inline void
syscnt_add(struct syscnt *syscnt, int64_t delta)
{
    atomic_add(&syscnt->value, delta, ATOMIC_RELAXED);
}

static inline uint64_t
syscnt_read(const struct syscnt *syscnt)
{
    return atomic_load((uint64_t *)&syscnt->value, ATOMIC_RELAXED);
}

#else /* ATOMIC_HAVE_64B_OPS */

static inline void
syscnt_set(struct syscnt *syscnt, uint64_t value)
{
    unsigned long flags;

    spinlock_lock_intr_save(&syscnt->lock, &flags);
    syscnt->value = value;
    spinlock_unlock_intr_restore(&syscnt->lock, flags);
}

static inline void
syscnt_add(struct syscnt *syscnt, int64_t delta)
{
    unsigned long flags;

    spinlock_lock_intr_save(&syscnt->lock, &flags);
    syscnt->value += delta;
    spinlock_unlock_intr_restore(&syscnt->lock, flags);
}

static inline uint64_t
syscnt_read(struct syscnt *syscnt)
{
    unsigned long flags;
    uint64_t value;

    spinlock_lock_intr_save(&syscnt->lock, &flags);
    value = syscnt->value;
    spinlock_unlock_intr_restore(&syscnt->lock, flags);

    return value;
}

#endif /* ATOMIC_HAVE_64B_OPS */

static inline void
syscnt_inc(struct syscnt *syscnt)
{
    syscnt_add(syscnt, 1);
}

static inline void
syscnt_dec(struct syscnt *syscnt)
{
    syscnt_add(syscnt, -1);
}

/*
 * Display system counters.
 *
 * A prefix can be used to filter the output, where only counters with the
 * given prefix are displayed. If NULL, all counters are reported.
 */
void syscnt_info(const char *prefix);

/*
 * This init operation provides :
 *  - registration of system counters
 *  - module fully initialized
 */
INIT_OP_DECLARE(syscnt_setup);

#endif /* KERN_SYSCNT_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_SYSCNT_TYPES_H
#define KERN_SYSCNT_TYPES_H

#include <stdint.h>

#include <kern/atomic.h>
#include <kern/list_types.h>
#include <kern/spinlock_types.h>

/*
 * Use atomic access on 64-bits systems, spinlock based critical sections
 * on 32-bits ones.
 */
struct syscnt {
#ifndef ATOMIC_HAVE_64B_OPS
    struct spinlock lock;
#endif /* __LP64__ */

    uint64_t value;
    struct list node;
    char name[SYSCNT_NAME_SIZE];
};

#endif /* KERN_SYSCNT_TYPES_H */


code:
/*
 * Copyright (c) 2012-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 <stdio.h>
#include <string.h>

#include <kern/init.h>
#include <kern/kmem.h>
#include <kern/list.h>
#include <kern/macros.h>
#include <kern/shell.h>
#include <kern/spinlock.h>
#include <kern/task.h>
#include <kern/thread.h>
#include <vm/vm_map.h>

#ifdef __LP64__
#define TASK_INFO_ADDR_FMT "%016lx"
#else /* __LP64__ */
#define TASK_INFO_ADDR_FMT "%08lx"
#endif /* __LP64__ */

struct task task_kernel_task;

/*
 * Cache for allocated tasks.
 */
static struct kmem_cache task_cache;

/*
 * Global list of tasks.
 */
static struct list task_list;
static struct spinlock task_list_lock;

static void
task_init(struct task *task, const char *name, struct vm_map *map)
{
    task->nr_refs = 1;
    spinlock_init(&task->lock);
    list_init(&task->threads);
    task->map = map;
    strlcpy(task->name, name, sizeof(task->name));
}

#ifdef CONFIG_SHELL

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

    (void)shell;

    if (argc == 1) {
        task_info(NULL);
        return;
    } else {
        task = task_lookup(argv[1]);

        if (task == NULL) {
            error = EINVAL;
            goto error;
        }

        task_info(task);
        task_unref(task);
    }

    return;

error:
    printf("task: info: %s\n", strerror(error));
}

static struct shell_cmd task_shell_cmds[] = {
    SHELL_CMD_INITIALIZER("task_info", task_shell_info,
                          "task_info [<task_name>]",
                          "display tasks and threads"),
};

static int __init
task_setup_shell(void)
{
    SHELL_REGISTER_CMDS(task_shell_cmds, shell_get_main_cmd_set());
    return 0;
}

INIT_OP_DEFINE(task_setup_shell,
               INIT_OP_DEP(printf_setup, true),
               INIT_OP_DEP(shell_setup, true),
               INIT_OP_DEP(task_setup, true),
               INIT_OP_DEP(thread_setup, true));

#endif /* CONFIG_SHELL */

static int __init
task_setup(void)
{
    struct task *kernel_task;

    kernel_task = task_get_kernel_task();
    kmem_cache_init(&task_cache, "task", sizeof(struct task), 0, NULL, 0);
    list_init(&task_list);
    spinlock_init(&task_list_lock);
    task_init(kernel_task, "x15", vm_map_get_kernel_map());
    list_insert_head(&task_list, &kernel_task->node);
    return 0;
}

INIT_OP_DEFINE(task_setup,
               INIT_OP_DEP(kmem_setup, true),
               INIT_OP_DEP(spinlock_setup, true),
               INIT_OP_DEP(vm_map_setup, true));

int
task_create(struct task **taskp, const char *name)
{
    struct vm_map *map;
    struct task *task;
    int error;

    task = kmem_cache_alloc(&task_cache);

    if (task == NULL) {
        error = ENOMEM;
        goto error_task;
    }

    error = vm_map_create(&map);

    if (error) {
        goto error_map;
    }

    task_init(task, name, map);

    spinlock_lock(&task_list_lock);
    list_insert_tail(&task_list, &task->node);
    spinlock_unlock(&task_list_lock);

    *taskp = task;
    return 0;

error_map:
    kmem_cache_free(&task_cache, task);
error_task:
    return error;
}

struct task *
task_lookup(const char *name)
{
    struct task *task;

    spinlock_lock(&task_list_lock);

    list_for_each_entry(&task_list, task, node) {
        spinlock_lock(&task->lock);

        if (strcmp(task->name, name) == 0) {
            task_ref(task);
            spinlock_unlock(&task->lock);
            spinlock_unlock(&task_list_lock);
            return task;
        }

        spinlock_unlock(&task->lock);
    }

    spinlock_unlock(&task_list_lock);

    return NULL;
}

void
task_add_thread(struct task *task, struct thread *thread)
{
    spinlock_lock(&task->lock);
    list_insert_tail(&task->threads, &thread->task_node);
    spinlock_unlock(&task->lock);
}

void
task_remove_thread(struct task *task, struct thread *thread)
{
    spinlock_lock(&task->lock);
    list_remove(&thread->task_node);
    spinlock_unlock(&task->lock);
}

struct thread *
task_lookup_thread(struct task *task, const char *name)
{
    struct thread *thread;

    spinlock_lock(&task->lock);

    list_for_each_entry(&task->threads, thread, task_node) {
        if (strcmp(thread_name(thread), name) == 0) {
            thread_ref(thread);
            spinlock_unlock(&task->lock);
            return thread;
        }
    }

    spinlock_unlock(&task->lock);

    return NULL;
}

void
task_info(struct task *task)
{
    struct thread *thread;

    if (task == NULL) {
        spinlock_lock(&task_list_lock);

        list_for_each_entry(&task_list, task, node) {
            task_info(task);
        }

        spinlock_unlock(&task_list_lock);

        return;
    }

    spinlock_lock(&task->lock);

    printf("task: name: %s, threads:\n", task->name);

    /*
     * Don't grab any lock when accessing threads, so that the function
     * can be used to debug in the middle of most critical sections.
     * Threads are only destroyed after being removed from their task
     * so holding the task lock is enough to guarantee existence.
     *
     * TODO Handle tasks and threads names modifications.
     */
    list_for_each_entry(&task->threads, thread, task_node) {
        printf(TASK_INFO_ADDR_FMT " %c %8s:" TASK_INFO_ADDR_FMT
               " %.2s:%02hu %02u %s\n",
               (unsigned long)thread,
               thread_state_to_chr(thread_state(thread)),
               thread_wchan_desc(thread),
               (unsigned long)thread_wchan_addr(thread),
               thread_sched_class_to_str(thread_user_sched_class(thread)),
               thread_user_priority(thread),
               thread_real_global_priority(thread),
               thread_name(thread));
    }

    spinlock_unlock(&task->lock);
}


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

#ifndef KERN_TASK_H
#define KERN_TASK_H

#include <kern/atomic.h>
#include <kern/init.h>
#include <kern/list.h>
#include <kern/spinlock.h>
#include <kern/thread.h>
#include <vm/vm_map.h>

/*
 * Task name buffer size.
 */
#define TASK_NAME_SIZE 32

/*
 * Task structure.
 */
struct task {
    unsigned long nr_refs;
    struct spinlock lock;
    struct list node;
    struct list threads;
    struct vm_map *map;
    char name[TASK_NAME_SIZE];
};

static inline struct task *
task_get_kernel_task(void)
{
    extern struct task task_kernel_task;

    return &task_kernel_task;
}

static inline void
task_ref(struct task *task)
{
    unsigned long nr_refs;

    nr_refs = atomic_fetch_add(&task->nr_refs, 1UL, ATOMIC_RELAXED);
    assert(nr_refs != (unsigned long)-1);
}

static inline void
task_unref(struct task *task)
{
    unsigned long nr_refs;

    nr_refs = atomic_fetch_sub(&task->nr_refs, 1UL, ATOMIC_ACQ_REL);
    assert(nr_refs != 0);

    if (nr_refs == 1) {
        /* TODO Task destruction */
    }
}

static inline struct vm_map *
task_get_vm_map(const struct task *task)
{
    return task->map;
}

/*
 * Create a task.
 */
int task_create(struct task **taskp, const char *name);

/*
 * Look up a task from its name.
 *
 * If a task is found, it gains a reference. Otherwise, NULL is returned.
 *
 * This function is meant for debugging only.
 */
struct task * task_lookup(const char *name);

/*
 * Add a thread to a task.
 */
void task_add_thread(struct task *task, struct thread *thread);

/*
 * Remove a thread from a task.
 */
void task_remove_thread(struct task *task, struct thread *thread);

/*
 * Look up a thread in a task from its name.
 *
 * If a thread is found, it gains a reference, Otherwise, NULL is returned.
 *
 * This function is meant for debugging only.
 */
struct thread * task_lookup_thread(struct task *task, const char *name);

/*
 * Display task information.
 *
 * If task is NULL, this function displays all tasks.
 */
void task_info(struct task *task);

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

#endif /* KERN_TASK_H */