zircon/system/utest/fit/scheduler_tests.cpp

// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <lib/fit/scheduler.h>
#include <unittest/unittest.h>

#include "unittest_utils.h"

namespace {

class fake_context : public fit::context {
public:
    fit::executor* executor() const override {
        ASSERT_CRITICAL(false);
    }
    fit::suspended_task suspend_task() override {
        ASSERT_CRITICAL(false);
    }
};

fit::pending_task make_pending_task(uint64_t* counter) {
    return fit::make_promise([counter] { (*counter)++; });
}

bool initial_state() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());

    END_TEST;
}

bool schedule_task() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;
    fit::subtle::scheduler::task_queue tasks;
    fake_context context;
    uint64_t run_count[3] = {};

    // Initially there are no tasks.
    scheduler.take_runnable_tasks(&tasks);
    EXPECT_TRUE(tasks.empty());

    // Schedule and run one task.
    scheduler.schedule_task(make_pending_task(&run_count[0]));
    EXPECT_TRUE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());
    scheduler.take_runnable_tasks(&tasks);
    EXPECT_EQ(1, tasks.size());
    tasks.front()(context);
    EXPECT_EQ(1, run_count[0]);
    tasks.pop();

    // Run a couple more, ensure that they come out in queue order.
    scheduler.schedule_task(make_pending_task(&run_count[0]));
    scheduler.schedule_task(make_pending_task(&run_count[1]));
    scheduler.schedule_task(make_pending_task(&run_count[2]));
    EXPECT_TRUE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());
    scheduler.take_runnable_tasks(&tasks);
    EXPECT_EQ(3, tasks.size());
    tasks.front()(context);
    EXPECT_EQ(2, run_count[0]);
    EXPECT_EQ(0, run_count[1]);
    EXPECT_EQ(0, run_count[2]);
    tasks.pop();
    tasks.front()(context);
    EXPECT_EQ(2, run_count[0]);
    EXPECT_EQ(1, run_count[1]);
    EXPECT_EQ(0, run_count[2]);
    tasks.pop();
    tasks.front()(context);
    EXPECT_EQ(2, run_count[0]);
    EXPECT_EQ(1, run_count[1]);
    EXPECT_EQ(1, run_count[2]);
    tasks.pop();

    // Once we're done, no tasks are left.
    scheduler.take_runnable_tasks(&tasks);
    EXPECT_TRUE(tasks.empty());

    END_TEST;
}

bool ticket_obtain_finalize_without_task() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;

    fit::suspended_task::ticket t = scheduler.obtain_ticket();
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    fit::pending_task task;
    scheduler.finalize_ticket(t, &task);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());

    END_TEST;
}

bool ticket_obtain_finalize_with_task() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;

    fit::suspended_task::ticket t = scheduler.obtain_ticket();
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    uint64_t run_count = 0;
    fit::pending_task p = make_pending_task(&run_count);
    scheduler.finalize_ticket(t, &p);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());
    EXPECT_TRUE(p); // didn't take ownership

    END_TEST;
}

bool ticket_obtain2_duplicate_finalize_release() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;

    fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
    scheduler.duplicate_ticket(t);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    uint64_t run_count = 0;
    fit::pending_task p = make_pending_task(&run_count);
    scheduler.finalize_ticket(t, &p);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_TRUE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());
    EXPECT_FALSE(p); // took ownership

    p = scheduler.release_ticket(t);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_TRUE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());
    EXPECT_FALSE(p); // ticket still has one ref

    p = scheduler.release_ticket(t);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());
    EXPECT_TRUE(p); // ticket fully unref'd so task ownership returned

    END_TEST;
}

bool ticket_obtain2_duplicate_finalize_resume() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;

    fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
    scheduler.duplicate_ticket(t);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    uint64_t run_count = 0;
    fit::pending_task p = make_pending_task(&run_count);
    scheduler.finalize_ticket(t, &p);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_TRUE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());
    EXPECT_FALSE(p); // took ownership

    scheduler.resume_task_with_ticket(t);
    EXPECT_TRUE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    p = scheduler.release_ticket(t);
    EXPECT_TRUE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());
    EXPECT_FALSE(p); // ticket was already resumed, nothing to return

    fit::subtle::scheduler::task_queue tasks;
    scheduler.take_runnable_tasks(&tasks);
    EXPECT_EQ(1, tasks.size());

    fake_context context;
    tasks.front()(context);
    EXPECT_EQ(1, run_count);

    END_TEST;
}

bool ticket_obtain2_release_finalize() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;

    fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    fit::pending_task p = scheduler.release_ticket(t);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());
    EXPECT_FALSE(p); // ticket still has one ref

    uint64_t run_count = 0;
    p = make_pending_task(&run_count);
    scheduler.finalize_ticket(t, &p);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());
    EXPECT_TRUE(p); // ticket ref-count reached zero, so ownership not taken

    END_TEST;
}

bool ticket_obtain2_resume_finalize() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;

    fit::suspended_task::ticket t = scheduler.obtain_ticket(2 /*initial_refs*/);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    scheduler.resume_task_with_ticket(t);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    uint64_t run_count = 0;
    fit::pending_task p = make_pending_task(&run_count);
    scheduler.finalize_ticket(t, &p);
    EXPECT_TRUE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_FALSE(scheduler.has_outstanding_tickets());
    EXPECT_FALSE(p); // took ownership since task already resumed

    fit::subtle::scheduler::task_queue tasks;
    scheduler.take_runnable_tasks(&tasks);
    EXPECT_EQ(1, tasks.size());

    fake_context context;
    tasks.front()(context);
    EXPECT_EQ(1, run_count);

    END_TEST;
}

bool take_all_tasks() {
    BEGIN_TEST;

    fit::subtle::scheduler scheduler;
    fit::subtle::scheduler::task_queue tasks;
    fake_context context;
    uint64_t run_count[6] = {};

    // Initially there are no tasks.
    scheduler.take_all_tasks(&tasks);
    EXPECT_TRUE(tasks.empty());

    // Schedule a task.
    scheduler.schedule_task(make_pending_task(&run_count[0]));
    EXPECT_TRUE(scheduler.has_runnable_tasks());

    // Suspend a task and finalize it without resumption.
    // This does not leave an outstanding ticket.
    fit::suspended_task::ticket t1 = scheduler.obtain_ticket();
    fit::pending_task p1 = make_pending_task(&run_count[1]);
    scheduler.finalize_ticket(t1, &p1);
    EXPECT_TRUE(p1); // took ownership

    // Suspend a task and duplicate its ticket.
    // This leaves an outstanding ticket with an associated task.
    fit::suspended_task::ticket t2 = scheduler.obtain_ticket();
    fit::pending_task p2 = make_pending_task(&run_count[2]);
    scheduler.duplicate_ticket(t2);
    scheduler.finalize_ticket(t2, &p2);
    EXPECT_FALSE(p2); // didn't take ownership

    // Suspend a task, duplicate its ticket, then release it.
    // This does not leave an outstanding ticket.
    fit::suspended_task::ticket t3 = scheduler.obtain_ticket();
    fit::pending_task p3 = make_pending_task(&run_count[3]);
    scheduler.duplicate_ticket(t3);
    scheduler.finalize_ticket(t3, &p3);
    EXPECT_FALSE(p3); // didn't take ownership
    p3 = scheduler.release_ticket(t3);
    EXPECT_TRUE(p3);

    // Suspend a task, duplicate its ticket, then resume it.
    // This adds a runnable task but does not leave an outstanding ticket.
    fit::suspended_task::ticket t4 = scheduler.obtain_ticket();
    fit::pending_task p4 = make_pending_task(&run_count[4]);
    scheduler.duplicate_ticket(t4);
    scheduler.finalize_ticket(t4, &p4);
    EXPECT_FALSE(p4); // didn't take ownership
    EXPECT_TRUE(scheduler.resume_task_with_ticket(t4));

    // Suspend a task, duplicate its ticket twice, then resume it.
    // This adds a runnable task and leaves an outstanding ticket without an
    // associated task.
    fit::suspended_task::ticket t5 = scheduler.obtain_ticket();
    fit::pending_task p5 = make_pending_task(&run_count[5]);
    scheduler.duplicate_ticket(t5);
    scheduler.duplicate_ticket(t5);
    scheduler.finalize_ticket(t5, &p5);
    EXPECT_FALSE(p5); // didn't take ownership
    EXPECT_TRUE(scheduler.resume_task_with_ticket(t5));

    // Now take all tasks.
    // We expect to find tasks that were runnable or associated with
    // outstanding tickets.  Those outstanding tickets will remain, however they
    // no longer have an associated task (cannot subsequently be resumed).
    EXPECT_TRUE(scheduler.has_runnable_tasks());
    EXPECT_TRUE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());
    scheduler.take_all_tasks(&tasks);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());

    // Check that we obtained the tasks we expected to obtain, by running them.
    EXPECT_EQ(4, tasks.size());
    while (!tasks.empty()) {
        tasks.front()(context);
        tasks.pop();
    }
    EXPECT_EQ(1, run_count[0]);
    EXPECT_EQ(0, run_count[1]);
    EXPECT_EQ(1, run_count[2]);
    EXPECT_EQ(0, run_count[3]);
    EXPECT_EQ(1, run_count[4]);
    EXPECT_EQ(1, run_count[5]);

    // Now that everything is gone, taking all tasks should return an empty set.
    scheduler.take_all_tasks(&tasks);
    EXPECT_FALSE(scheduler.has_runnable_tasks());
    EXPECT_FALSE(scheduler.has_suspended_tasks());
    EXPECT_TRUE(scheduler.has_outstanding_tickets());
    EXPECT_TRUE(tasks.empty());

    END_TEST;
}

} // namespace

BEGIN_TEST_CASE(scheduler_tests)
RUN_TEST(initial_state)
RUN_TEST(schedule_task)
RUN_TEST(ticket_obtain_finalize_without_task)
RUN_TEST(ticket_obtain_finalize_with_task)
RUN_TEST(ticket_obtain2_duplicate_finalize_release)
RUN_TEST(ticket_obtain2_duplicate_finalize_resume)
RUN_TEST(ticket_obtain2_release_finalize)
RUN_TEST(ticket_obtain2_resume_finalize)
RUN_TEST(take_all_tasks)
END_TEST_CASE(scheduler_tests)