scheduling_tests.cpp

#include <catch.hpp>

#include <atomic>

#include "pls/internal/scheduling/lock_free/traded_cas_field.h"
#include "pls/internal/scheduling/lock_free/external_trading_deque.h"
#include "pls/pls.h"

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

constexpr int MAX_NUM_TASKS = 32;
constexpr int MAX_STACK_SIZE = 1024 * 8;

TEST_CASE("tasks distributed over workers (do not block)", "[internal/scheduling/scheduler.h]") {
  scheduler scheduler{3, MAX_NUM_TASKS, MAX_STACK_SIZE};

  std::atomic<int> num_run{0};
  scheduler.perform_work([&] {
    scheduler::spawn([&] {
      num_run++;
      while (num_run < 3);
    });
    scheduler::spawn([&] {
      while (num_run < 1);
      num_run++;
      while (num_run < 3);
    });
    scheduler::spawn([&] {
      while (num_run < 2);
      num_run++;
    });
    scheduler::sync();
  });
  REQUIRE(num_run == 3);
}

TEST_CASE("traded cas field bitmaps correctly", "[internal/scheduling/traded_cas_field.h]") {
  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(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("external trading deque", "[internal/scheduling/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]);
    REQUIRE(*external_trading_deque::get_trade_object(&tasks[0]) == &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));
  }
}