/*
 * coroutine queues and locks
 *
 * Copyright (c) 2011 Kevin Wolf <kwolf@redhat.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 * The lock-free mutex implementation is based on OSv
 * (core/lfmutex.cc, include/lockfree/mutex.hh).
 * Copyright (C) 2013 Cloudius Systems, Ltd.
 */

#include "qemu/osdep.h"
#include "qemu-common.h"
#include "qemu/coroutine.h"
#include "qemu/coroutine_int.h"
#include "qemu/processor.h"
#include "qemu/queue.h"
#include "block/aio.h"
#include "trace.h"

void qemu_co_queue_init(CoQueue *queue)
{
    QSIMPLEQ_INIT(&queue->entries);
}

void coroutine_fn qemu_co_queue_wait(CoQueue *queue, CoMutex *mutex)
{
    Coroutine *self = qemu_coroutine_self();
    QSIMPLEQ_INSERT_TAIL(&queue->entries, self, co_queue_next);

    if (mutex) {
        qemu_co_mutex_unlock(mutex);
    }

    /* There is no race condition here.  Other threads will call
     * aio_co_schedule on our AioContext, which can reenter this
     * coroutine but only after this yield and after the main loop
     * has gone through the next iteration.
     */
    qemu_coroutine_yield();
    assert(qemu_in_coroutine());

    /* TODO: OSv implements wait morphing here, where the wakeup
     * primitive automatically places the woken coroutine on the
     * mutex's queue.  This avoids the thundering herd effect.
     */
    if (mutex) {
        qemu_co_mutex_lock(mutex);
    }
}

/**
 * qemu_co_queue_run_restart:
 *
 * Enter each coroutine that was previously marked for restart by
 * qemu_co_queue_next() or qemu_co_queue_restart_all().  This function is
 * invoked by the core coroutine code when the current coroutine yields or
 * terminates.
 */
void qemu_co_queue_run_restart(Coroutine *co)
{
    Coroutine *next;
    QSIMPLEQ_HEAD(, Coroutine) tmp_queue_wakeup =
        QSIMPLEQ_HEAD_INITIALIZER(tmp_queue_wakeup);

    trace_qemu_co_queue_run_restart(co);

    /* Because "co" has yielded, any coroutine that we wakeup can resume it.
     * If this happens and "co" terminates, co->co_queue_wakeup becomes
     * invalid memory.  Therefore, use a temporary queue and do not touch
     * the "co" coroutine as soon as you enter another one.
     *
     * In its turn resumed "co" can pupulate "co_queue_wakeup" queue with
     * new coroutines to be woken up.  The caller, who has resumed "co",
     * will be responsible for traversing the same queue, which may cause
     * a different wakeup order but not any missing wakeups.
     */
    QSIMPLEQ_CONCAT(&tmp_queue_wakeup, &co->co_queue_wakeup);

    while ((next = QSIMPLEQ_FIRST(&tmp_queue_wakeup))) {
        QSIMPLEQ_REMOVE_HEAD(&tmp_queue_wakeup, co_queue_next);
        qemu_coroutine_enter(next);
    }
}

static bool qemu_co_queue_do_restart(CoQueue *queue, bool single)
{
    Coroutine *next;

    if (QSIMPLEQ_EMPTY(&queue->entries)) {
        return false;
    }

    while ((next = QSIMPLEQ_FIRST(&queue->entries)) != NULL) {
        QSIMPLEQ_REMOVE_HEAD(&queue->entries, co_queue_next);
        aio_co_wake(next);
        if (single) {
            break;
        }
    }
    return true;
}

bool coroutine_fn qemu_co_queue_next(CoQueue *queue)
{
    assert(qemu_in_coroutine());
    return qemu_co_queue_do_restart(queue, true);
}

void coroutine_fn qemu_co_queue_restart_all(CoQueue *queue)
{
    assert(qemu_in_coroutine());
    qemu_co_queue_do_restart(queue, false);
}

bool qemu_co_enter_next(CoQueue *queue)
{
    Coroutine *next;

    next = QSIMPLEQ_FIRST(&queue->entries);
    if (!next) {
        return false;
    }

    QSIMPLEQ_REMOVE_HEAD(&queue->entries, co_queue_next);
    qemu_coroutine_enter(next);
    return true;
}

bool qemu_co_queue_empty(CoQueue *queue)
{
    return QSIMPLEQ_FIRST(&queue->entries) == NULL;
}

/* The wait records are handled with a multiple-producer, single-consumer
 * lock-free queue.  There cannot be two concurrent pop_waiter() calls
 * because pop_waiter() can only be called while mutex->handoff is zero.
 * This can happen in three cases:
 * - in qemu_co_mutex_unlock, before the hand-off protocol has started.
 *   In this case, qemu_co_mutex_lock will see mutex->handoff == 0 and
 *   not take part in the handoff.
 * - in qemu_co_mutex_lock, if it steals the hand-off responsibility from
 *   qemu_co_mutex_unlock.  In this case, qemu_co_mutex_unlock will fail
 *   the cmpxchg (it will see either 0 or the next sequence value) and
 *   exit.  The next hand-off cannot begin until qemu_co_mutex_lock has
 *   woken up someone.
 * - in qemu_co_mutex_unlock, if it takes the hand-off token itself.
 *   In this case another iteration starts with mutex->handoff == 0;
 *   a concurrent qemu_co_mutex_lock will fail the cmpxchg, and
 *   qemu_co_mutex_unlock will go back to case (1).
 *
 * The following functions manage this queue.
 */
typedef struct CoWaitRecord {
    Coroutine *co;
    QSLIST_ENTRY(CoWaitRecord) next;
} CoWaitRecord;

static void push_waiter(CoMutex *mutex, CoWaitRecord *w)
{
    w->co = qemu_coroutine_self();
    QSLIST_INSERT_HEAD_ATOMIC(&mutex->from_push, w, next);
}

static void move_waiters(CoMutex *mutex)
{
    QSLIST_HEAD(, CoWaitRecord) reversed;
    QSLIST_MOVE_ATOMIC(&reversed, &mutex->from_push);
    while (!QSLIST_EMPTY(&reversed)) {
        CoWaitRecord *w = QSLIST_FIRST(&reversed);
        QSLIST_REMOVE_HEAD(&reversed, next);
        QSLIST_INSERT_HEAD(&mutex->to_pop, w, next);
    }
}

static CoWaitRecord *pop_waiter(CoMutex *mutex)
{
    CoWaitRecord *w;

    if (QSLIST_EMPTY(&mutex->to_pop)) {
        move_waiters(mutex);
        if (QSLIST_EMPTY(&mutex->to_pop)) {
            return NULL;
        }
    }
    w = QSLIST_FIRST(&mutex->to_pop);
    QSLIST_REMOVE_HEAD(&mutex->to_pop, next);
    return w;
}

static bool has_waiters(CoMutex *mutex)
{
    return QSLIST_EMPTY(&mutex->to_pop) || QSLIST_EMPTY(&mutex->from_push);
}

void qemu_co_mutex_init(CoMutex *mutex)
{
    memset(mutex, 0, sizeof(*mutex));
}

static void coroutine_fn qemu_co_mutex_wake(CoMutex *mutex, Coroutine *co)
{
    /* Read co before co->ctx; pairs with smp_wmb() in
     * qemu_coroutine_enter().
     */
    smp_read_barrier_depends();
    mutex->ctx = co->ctx;
    aio_co_wake(co);
}

static void coroutine_fn qemu_co_mutex_lock_slowpath(AioContext *ctx,
                                                     CoMutex *mutex)
{
    Coroutine *self = qemu_coroutine_self();
    CoWaitRecord w;
    unsigned old_handoff;

    trace_qemu_co_mutex_lock_entry(mutex, self);
    w.co = self;
    push_waiter(mutex, &w);

    /* This is the "Responsibility Hand-Off" protocol; a lock() picks from
     * a concurrent unlock() the responsibility of waking somebody up.
     */
    old_handoff = atomic_mb_read(&mutex->handoff);
    if (old_handoff &&
        has_waiters(mutex) &&
        atomic_cmpxchg(&mutex->handoff, old_handoff, 0) == old_handoff) {
        /* There can be no concurrent pops, because there can be only
         * one active handoff at a time.
         */
        CoWaitRecord *to_wake = pop_waiter(mutex);
        Coroutine *co = to_wake->co;
        if (co == self) {
            /* We got the lock ourselves!  */
            assert(to_wake == &w);
            mutex->ctx = ctx;
            return;
        }

        qemu_co_mutex_wake(mutex, co);
    }

    qemu_coroutine_yield();
    trace_qemu_co_mutex_lock_return(mutex, self);
}

void coroutine_fn qemu_co_mutex_lock(CoMutex *mutex)
{
    AioContext *ctx = qemu_get_current_aio_context();
    Coroutine *self = qemu_coroutine_self();
    int waiters, i;

    /* Running a very small critical section on pthread_mutex_t and CoMutex
     * shows that pthread_mutex_t is much faster because it doesn't actually
     * go to sleep.  What happens is that the critical section is shorter
     * than the latency of entering the kernel and thus FUTEX_WAIT always
     * fails.  With CoMutex there is no such latency but you still want to
     * avoid wait and wakeup.  So introduce it artificially.
     */
    i = 0;
retry_fast_path:
    waiters = atomic_cmpxchg(&mutex->locked, 0, 1);
    if (waiters != 0) {
        while (waiters == 1 && ++i < 1000) {
            if (atomic_read(&mutex->ctx) == ctx) {
                break;
            }
            if (atomic_read(&mutex->locked) == 0) {
                goto retry_fast_path;
            }
            cpu_relax();
        }
        waiters = atomic_fetch_inc(&mutex->locked);
    }

    if (waiters == 0) {
        /* Uncontended.  */
        trace_qemu_co_mutex_lock_uncontended(mutex, self);
        mutex->ctx = ctx;
    } else {
        qemu_co_mutex_lock_slowpath(ctx, mutex);
    }
    mutex->holder = self;
    self->locks_held++;
}

void coroutine_fn qemu_co_mutex_unlock(CoMutex *mutex)
{
    Coroutine *self = qemu_coroutine_self();

    trace_qemu_co_mutex_unlock_entry(mutex, self);

    assert(mutex->locked);
    assert(mutex->holder == self);
    assert(qemu_in_coroutine());

    mutex->ctx = NULL;
    mutex->holder = NULL;
    self->locks_held--;
    if (atomic_fetch_dec(&mutex->locked) == 1) {
        /* No waiting qemu_co_mutex_lock().  Pfew, that was easy!  */
        return;
    }

    for (;;) {
        CoWaitRecord *to_wake = pop_waiter(mutex);
        unsigned our_handoff;

        if (to_wake) {
            qemu_co_mutex_wake(mutex, to_wake->co);
            break;
        }

        /* Some concurrent lock() is in progress (we know this because
         * mutex->locked was >1) but it hasn't yet put itself on the wait
         * queue.  Pick a sequence number for the handoff protocol (not 0).
         */
        if (++mutex->sequence == 0) {
            mutex->sequence = 1;
        }

        our_handoff = mutex->sequence;
        atomic_mb_set(&mutex->handoff, our_handoff);
        if (!has_waiters(mutex)) {
            /* The concurrent lock has not added itself yet, so it
             * will be able to pick our handoff.
             */
            break;
        }

        /* Try to do the handoff protocol ourselves; if somebody else has
         * already taken it, however, we're done and they're responsible.
         */
        if (atomic_cmpxchg(&mutex->handoff, our_handoff, 0) != our_handoff) {
            break;
        }
    }

    trace_qemu_co_mutex_unlock_return(mutex, self);
}

void qemu_co_rwlock_init(CoRwlock *lock)
{
    memset(lock, 0, sizeof(*lock));
    qemu_co_queue_init(&lock->queue);
    qemu_co_mutex_init(&lock->mutex);
}

void qemu_co_rwlock_rdlock(CoRwlock *lock)
{
    Coroutine *self = qemu_coroutine_self();

    qemu_co_mutex_lock(&lock->mutex);
    /* For fairness, wait if a writer is in line.  */
    while (lock->pending_writer) {
        qemu_co_queue_wait(&lock->queue, &lock->mutex);
    }
    lock->reader++;
    qemu_co_mutex_unlock(&lock->mutex);

    /* The rest of the read-side critical section is run without the mutex.  */
    self->locks_held++;
}

void qemu_co_rwlock_unlock(CoRwlock *lock)
{
    Coroutine *self = qemu_coroutine_self();

    assert(qemu_in_coroutine());
    if (!lock->reader) {
        /* The critical section started in qemu_co_rwlock_wrlock.  */
        qemu_co_queue_restart_all(&lock->queue);
    } else {
        self->locks_held--;

        qemu_co_mutex_lock(&lock->mutex);
        lock->reader--;
        assert(lock->reader >= 0);
        /* Wakeup only one waiting writer */
        if (!lock->reader) {
            qemu_co_queue_next(&lock->queue);
        }
    }
    qemu_co_mutex_unlock(&lock->mutex);
}

void qemu_co_rwlock_downgrade(CoRwlock *lock)
{
    Coroutine *self = qemu_coroutine_self();

    /* lock->mutex critical section started in qemu_co_rwlock_wrlock or
     * qemu_co_rwlock_upgrade.
     */
    assert(lock->reader == 0);
    lock->reader++;
    qemu_co_mutex_unlock(&lock->mutex);

    /* The rest of the read-side critical section is run without the mutex.  */
    self->locks_held++;
}

void qemu_co_rwlock_wrlock(CoRwlock *lock)
{
    qemu_co_mutex_lock(&lock->mutex);
    lock->pending_writer++;
    while (lock->reader) {
        qemu_co_queue_wait(&lock->queue, &lock->mutex);
    }
    lock->pending_writer--;

    /* The rest of the write-side critical section is run with
     * the mutex taken, so that lock->reader remains zero.
     * There is no need to update self->locks_held.
     */
}

void qemu_co_rwlock_upgrade(CoRwlock *lock)
{
    Coroutine *self = qemu_coroutine_self();

    qemu_co_mutex_lock(&lock->mutex);
    assert(lock->reader > 0);
    lock->reader--;
    lock->pending_writer++;
    while (lock->reader) {
        qemu_co_queue_wait(&lock->queue, &lock->mutex);
    }
    lock->pending_writer--;

    /* The rest of the write-side critical section is run with
     * the mutex taken, similar to qemu_co_rwlock_wrlock.  Do
     * not account for the lock twice in self->locks_held.
     */
    self->locks_held--;
}