Current progress on multi-waiter-enabled condition variables that can be exposed to rust.

rust_cond_lock.cpp

/****************************************************************************
 * A rust-scheduler-enabled concurrency primitive for mutual exclusion and
 * blocking/signalling.
 *
 * This code is intimately linked with task killing, so interacts with tasks'
 * kill_locks in a complicated way. Because killing a task also needs to punt
 * it off of cvar wait queues, it needs to take the cvar's lock too.
 *
 * NB: Rules for locking order & data ownership are as follows:
 *
 * (1) Locking a task's KILL_LOCK nests inside of locking CVARS.
 *     - Never take a CVAR's lock while holding a KILL_LOCK.
 *
 * (2) A task's cond_blocked_on is protected by its KILL_LOCK and also by its
 *     KILLED flag. To access the cvar pointer, you must either:
 *     - Hold KILL_LOCK and verify !KILLED, or
 *     - Take KILL_LOCK, verify !KILLED, set KILLED = true, and drop KILL_LOCK
 *     The second condition enables a killer to take ownership of cvar
 *     metadata without having to break rule 1.
 *
 * (3) The rest of tasks' cvar metadata (the waiter node) is protected by the
 *     CVAR's lock. TODO
 *
 * TODO(bblum): figure out interactions with the *other* conditions of
 * must_fail_from_being_killed.
 *
 ****************************************************************************/

#include "rust_cond_lock.h"

rust_cond_lock::rust_cond_lock()
    : count(1)
{
    Q_INIT_HEAD(&contenders);
    Q_INIT_HEAD(&waiters);
}

/* Helper functions, with the interface stylings of pthread primitives. */

static MUST_CHECK bool
rust_cond_lock::cond_wait(struct rust_cond_wait_list *cond, rust_task *me,
                          bool killable) {
    // Unlocked access. But this pointer will make helgrind angry already.
    assert(me->cond_blocked_on == NULL);

    // Enqueue as a waiter.
    {
        // Putting ourself on the cvar wait queue is protected by our own
        // lifecycle_lock. The killed flag is also protected, and also tells
        // us whether or not we're allowed to touch our cond links/pointers.
        scoped_lock with(me->lifecycle_lock);
        // First check if we're allowed to do anything.
        if (me->must_fail_from_being_killed_inner()) {
            return false;
        }
        // Made it in without needing to die.
        me->cond_blocked_on = this;
        Q_INSERT_TAIL(cond, me, cond_wait_link);
        // Shouldn't fail -- we already checked above.
        bool ret = me->block_locked(this, "Killable wait on rust_cond_lock");
        assert(ret && "block_locked told me to die after I already checked");
    } else {
        Q_INSERT_TAIL(cond, me, cond_wait_link);
        // Don't care if block tells us to die.
        bool ret = me->block(this, "Unkillable rust_cond_lock acquisition");
        if (!ret) {
            // XXX: I guess we're going to need to inform block() "no really".
            LOG(me, cond, "Kill detected during unkillable block; ignoring.");
        }
    }
    little_lock.unlock();

    bool was_killed = false;
    me->yield(&was_killed); // XXX: rust stack

    little_lock.lock();

    assert(me->cond_blocked_on == NULL);

    if (was_killed && !killable) {
        LOG(me, cond, "Woke up killed from unkillable block; ignoring.");
        return true;
    }
    return !was_killed;
}

static void rust_cond_lock::cond_signal(struct rust_cond_wait_list *cond) {
    // Iterate over the list looking for for somebody to wake up.
    for (rust_task *him_or_her = QUEUE_GET_FRONT(cond), him_or_her != NULL,
         him_or_her = QUEUE_GET_NEXT(him_or_her, cond_wait_link)) {
        // Accessing their task struct is safe even if there's a killer,
        // because we found them on the list, which means they are asleep.
        scoped_lock with(him_or_her->lifecycle_lock);
        assert(him_or_her->cond_blocked_on == this);
        if (them->must_fail_from_being_killed_inner()) { // XXX wrong
            // If we got here, the killer has dropped the lifecycle_lock but
            // not picked up the cond lock yet. Not our job to wake them up.
            continue;
        }
        // No kill in progress. Wake them up. (common path)
        them->cond_blocked_on = NULL;
        QUEUE_REMOVE(cond, him_or_her, cond_wait_link);
        them->wakeup_inner(this);
        // Only wake up one thread.
        return;
    }
    // Found nobody to wake up.
}

// TODO: have a punt_awake?

/* Other helpers */

#ifdef DEBUG_LOCKS
#define RECORD_OWNER(task) do { owner = task; } while (0)
#define ASSERT_OWNER(task, msg) \
    assert(owner == task && "Cannot " msg " a rust_cond_lock we don't own!")
#else
#define RECORD_OWNER(task)
#define ASSERT_OWNER(task,msg)
#endif

static void rust_cond_lock::acquire_inner(rust_task *me) {
    count--;
    if (count < 0) {
        bool ret = cond_wait(&contenders, me, false);
        assert(ret && "An unkillable cvar wait was killed!");
    }
    RECORD_OWNER(me);
    return true;
}
static void rust_cond_lock::release_inner(rust_task *me) {
    ASSERT_OWNER(me, "unlock");
    count++;
    if (count > 0) {
        cond_signal(&contenders);
    }
}

/* Interface */

void rust_cond_lock::acquire(rust_task *me) {
    little_lock.lock();
    acquire_inner(me);
    little_lock.unlock();
}

void rust_cond_lock::release(rust_task *me) {
    little_lock.lock();
    release_inner(me);
    little_lock.unlock();
}

// Returns with the rust_cond_lock held -- even if you were killed! In that
// case, you own the critical section, but must release it and die promptly.
MUST_CHECK bool rust_cond_lock::wait(rust_task *me) {
    little_lock.lock();
    release_inner(me);
    // Drops and re-acquires little_lock. Killable.
    bool ret = cond_wait(&waiters, me, true);
    // Reacquire, even if killed. Unkillable.
    acquire_inner(me);
    little_lock.unlock();
    return ret;
}

void rust_cond_lock::signal(rust_task *me) {
    ASSERT_OWNER(me, "signal");
    cond_signal(&waiters);
}

void rust_cond_lock::broadcast(rust_task *me) {
    ASSERT_OWNER(me, "broadcast");
    assert(false && "unimplemented"); // TODO
}