scheduling_lock_free_tests.cpp

#include <catch.hpp>

#include <atomic>

#include "pls/pls.h"
#include "pls/internal/scheduling/task_manager.h"
#include "pls/internal/scheduling/thread_state.h"

#if PLS_DEQUE_VARIANT == PLS_DEQUE_LOCK_FREE
#include "pls/internal/scheduling/lock_free/traded_cas_field.h"
#include "pls/internal/scheduling/lock_free/external_trading_deque.h"

using namespace pls::internal::scheduling::lock_free;

TEST_CASE("traded cas field bitmaps correctly", "[internal/scheduling/lock_free/traded_cas_field]") {
  traded_cas_field empty_field;
  REQUIRE(empty_field.is_empty());
  REQUIRE(!empty_field.is_filled_with_stamp());
  REQUIRE(!empty_field.is_filled_with_object());

  const int stamp = 42;
  const int ID = 10;
  traded_cas_field tag_field;
  tag_field.fill_with_stamp_and_deque(stamp, ID);
  REQUIRE(tag_field.is_filled_with_stamp());
  REQUIRE(!tag_field.is_empty());
  REQUIRE(!tag_field.is_filled_with_object());
  REQUIRE(tag_field.get_stamp() == stamp);
  REQUIRE(tag_field.get_deque_id() == ID);

  alignas(64) task obj{nullptr, 0, 0, 0};
  traded_cas_field obj_field;
  obj_field.fill_with_trade_object(&obj);
  REQUIRE(obj_field.is_filled_with_object());
  REQUIRE(!obj_field.is_empty());
  REQUIRE(!obj_field.is_filled_with_stamp());
}

TEST_CASE("task resource stack", "[internal/scheduling/lock_free/task]") {
  // simulate scheduler with four threads and depth 1. We are thread 0.
  pls::scheduler scheduler{4, 1, 4096, false};
  pls::internal::scheduling::thread_state::set(&scheduler.thread_state_for(0));

  task *tasks[] = {scheduler.task_manager_for(0).get_task(0),
                   scheduler.task_manager_for(1).get_task(0),
                   scheduler.task_manager_for(2).get_task(0),
                   scheduler.task_manager_for(3).get_task(0)};

  SECTION("simple push/pop") {
    tasks[0]->push_task_chain(tasks[1]);

    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);
    REQUIRE(tasks[0]->pop_task_chain() == nullptr);
  }

  SECTION("propose/pop") {
    tasks[0]->propose_push_task_chain(tasks[1]);

    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);
    REQUIRE(tasks[0]->pop_task_chain() == nullptr);
  }

  SECTION("propose/accept/pop") {
    tasks[0]->propose_push_task_chain(tasks[1]);
    tasks[0]->accept_proposed();

    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);
    REQUIRE(tasks[0]->pop_task_chain() == nullptr);
  }

  SECTION("propose/decline/pop") {
    tasks[0]->propose_push_task_chain(tasks[1]);
    tasks[0]->decline_proposed();

    REQUIRE(tasks[0]->pop_task_chain() == nullptr);
    REQUIRE(tasks[0]->pop_task_chain() == nullptr);
  }

  SECTION("propose intertwined normal ops") {
    tasks[0]->push_task_chain(tasks[1]);
    tasks[0]->propose_push_task_chain(tasks[2]);

    REQUIRE(tasks[0]->pop_task_chain() == tasks[2]);
    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);

    tasks[0]->push_task_chain(tasks[1]);
    tasks[0]->propose_push_task_chain(tasks[2]);

    REQUIRE(tasks[0]->pop_task_chain() == tasks[2]);
    tasks[0]->accept_proposed();
    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);

    tasks[0]->push_task_chain(tasks[1]);
    tasks[0]->propose_push_task_chain(tasks[2]);
    tasks[0]->decline_proposed();

    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);
    REQUIRE(tasks[0]->pop_task_chain() == nullptr);

    tasks[0]->push_task_chain(tasks[1]);
    tasks[0]->propose_push_task_chain(tasks[2]);
    tasks[0]->accept_proposed();

    REQUIRE(tasks[0]->pop_task_chain() == tasks[2]);
    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);
  }

  SECTION("multiple pushes") {
    tasks[0]->push_task_chain(tasks[1]);
    tasks[0]->push_task_chain(tasks[2]);
    tasks[0]->push_task_chain(tasks[3]);

    REQUIRE(tasks[0]->pop_task_chain() == tasks[3]);
    REQUIRE(tasks[0]->pop_task_chain() == tasks[2]);
    REQUIRE(tasks[0]->pop_task_chain() == tasks[1]);
    REQUIRE(tasks[0]->pop_task_chain() == nullptr);
  }
}

TEST_CASE("external trading deque", "[internal/scheduling/lock_free/external_trading_deque]") {
  external_trading_deque deque_1{1, 16};
  external_trading_deque deque_2{2, 16};

  task tasks[4] = {{nullptr, 0, 0, 0},
                   {nullptr, 0, 1, 0},
                   {nullptr, 0, 2, 0},
                   {nullptr, 0, 3, 0}};

  SECTION("basic operations") {
    // Must start empty
    REQUIRE(!deque_1.pop_bot());
    REQUIRE(!deque_2.pop_bot());

    // Local push/pop
    deque_1.push_bot(&tasks[0]);
    REQUIRE(deque_1.pop_bot() == &tasks[0]);
    REQUIRE(!deque_1.pop_bot());

    // Local push, external pop
    deque_1.push_bot(&tasks[0]);
    auto peek = deque_1.peek_top();
    REQUIRE(deque_1.pop_top(&tasks[1], peek) == &tasks[0]);
    auto trade_peek = deque_1.peek_traded_object(&tasks[0]);
    REQUIRE(external_trading_deque::get_trade_object(&tasks[0], trade_peek, deque_1) == &tasks[1]);
    REQUIRE(!deque_1.pop_top(&tasks[1], peek));
    REQUIRE(!deque_1.pop_bot());

    // Keeps push/pop order
    deque_1.push_bot(&tasks[0]);
    deque_1.push_bot(&tasks[1]);
    REQUIRE(deque_1.pop_bot() == &tasks[1]);
    REQUIRE(deque_1.pop_bot() == &tasks[0]);
    REQUIRE(!deque_1.pop_bot());

    deque_1.push_bot(&tasks[0]);
    deque_1.push_bot(&tasks[1]);
    auto peek1 = deque_1.peek_top();
    REQUIRE(deque_1.pop_top(&tasks[2], peek1) == &tasks[0]);
    auto peek2 = deque_1.peek_top();
    REQUIRE(deque_1.pop_top(&tasks[3], peek2) == &tasks[1]);
  }

  SECTION("Interwined execution #1") {
    // Two top poppers
    deque_1.push_bot(&tasks[0]);
    auto peek1 = deque_1.peek_top();
    auto peek2 = deque_1.peek_top();
    REQUIRE(deque_1.pop_top(&tasks[1], peek1) == &tasks[0]);
    REQUIRE(!deque_1.pop_top(&tasks[2], peek2));
  }

  SECTION("Interwined execution #2") {
    // Top and bottom access
    deque_1.push_bot(&tasks[0]);
    auto peek1 = deque_1.peek_top();
    REQUIRE(deque_1.pop_bot() == &tasks[0]);
    REQUIRE(!deque_1.pop_top(&tasks[2], peek1));
  }
}
#endif // PLS_DEQUE_VARIANT == PLS_DEQUE_LOCK_FREE