scheduling_lock_free_tests.cpp 5.79 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
#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());
18
  REQUIRE(!empty_field.is_filled_with_trade_request());
19 20 21 22 23
  REQUIRE(!empty_field.is_filled_with_object());

  const int stamp = 42;
  const int ID = 10;
  traded_cas_field tag_field;
24 25
  tag_field.fill_with_trade_request(stamp, ID);
  REQUIRE(tag_field.is_filled_with_trade_request());
26 27 28
  REQUIRE(!tag_field.is_empty());
  REQUIRE(!tag_field.is_filled_with_object());
  REQUIRE(tag_field.get_stamp() == stamp);
29
  REQUIRE(tag_field.get_trade_request_thread_id() == ID);
30 31

  alignas(64) task obj{nullptr, 0, 0, 0};
32 33
  traded_cas_field obj_field = tag_field;
  obj_field.fill_with_task(obj.thread_id_);
34 35
  REQUIRE(obj_field.is_filled_with_object());
  REQUIRE(!obj_field.is_empty());
36
  REQUIRE(!obj_field.is_filled_with_trade_request());
37 38 39 40 41 42 43 44 45 46 47 48 49
}

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") {
50 51
    tasks[1]->prepare_for_push(0);
    tasks[0]->push_task_chain(tasks[1], 0);
52 53 54 55 56

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

57 58 59 60 61
  SECTION("empty pop and multi push") {
    tasks[1]->prepare_for_push(0);
    tasks[0]->push_task_chain(tasks[1], 0);
    tasks[2]->prepare_for_push(0);
    tasks[0]->push_task_chain(tasks[2], 0);
62 63 64 65

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

66 67
    tasks[1]->prepare_for_push(0);
    tasks[0]->push_task_chain(tasks[1], 0);
68 69 70 71 72

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

73
  SECTION("multiple pushes") {
74 75 76 77 78 79
    tasks[1]->prepare_for_push(0);
    tasks[0]->push_task_chain(tasks[1], 0);
    tasks[2]->prepare_for_push(0);
    tasks[0]->push_task_chain(tasks[2], 0);
    tasks[3]->prepare_for_push(0);
    tasks[0]->push_task_chain(tasks[3], 0);
80 81 82 83 84 85 86 87 88

    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]") {
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
  // simulate scheduler with four threads and depth 1. We are thread 0.
  pls::scheduler scheduler{4, 4, 4096, false};
  pls::internal::scheduling::thread_state::set(&scheduler.thread_state_for(0));

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

  auto &thread_state_1 = scheduler.thread_state_for(0);
  auto &task_manager_1 = scheduler.thread_state_for(0).get_task_manager();
  auto &thread_state_2 = scheduler.thread_state_for(1);
  auto &task_manager_2 = scheduler.thread_state_for(1).get_task_manager();

  SECTION("Must start empty") {
    REQUIRE(!task_manager_1.pop_local_task());
    REQUIRE(!task_manager_1.pop_local_task());
  }

  SECTION("Local push/pop") {
    task_manager_1.push_local_task(tasks_1[0]);
    REQUIRE(task_manager_1.pop_local_task() == tasks_1[0]);
    REQUIRE(!task_manager_1.pop_local_task());
  }

  SECTION("Local push, external pop") {
    task_manager_1.push_local_task(tasks_1[0]);
    REQUIRE(std::get<0>(task_manager_1.steal_task(thread_state_2)) == tasks_1[0]);
    REQUIRE(task_manager_2.pop_clean_task_chain(tasks_1[0]) == tasks_2[0]);
    REQUIRE(task_manager_1.pop_local_task() == nullptr);
  }

  SECTION("Keeps push/pop order #1") {
    task_manager_1.push_local_task(tasks_1[0]);
    task_manager_1.push_local_task(tasks_1[1]);
    REQUIRE(task_manager_1.pop_local_task() == tasks_1[1]);
    REQUIRE(task_manager_1.pop_local_task() == tasks_1[0]);
    REQUIRE(!task_manager_1.pop_local_task());
  }

  SECTION("Keeps push/pop order #2") {
    task_manager_1.push_local_task(tasks_1[0]);
    task_manager_1.push_local_task(tasks_1[1]);
    REQUIRE(std::get<0>(task_manager_1.steal_task(thread_state_2)) == tasks_1[0]);
    REQUIRE(std::get<0>(task_manager_1.steal_task(thread_state_2)) == tasks_1[1]);
138 139 140 141
  }

  SECTION("Interwined execution #1") {
    // Two top poppers
142 143 144
    task_manager_1.push_local_task(tasks_1[0]);
    REQUIRE(std::get<0>(task_manager_1.steal_task(thread_state_2)) == tasks_1[0]);
    REQUIRE(std::get<0>(task_manager_1.steal_task(thread_state_2)) == nullptr);
145 146 147 148
  }

  SECTION("Interwined execution #2") {
    // Top and bottom access
149 150 151
    task_manager_1.push_local_task(tasks_1[0]);
    REQUIRE(task_manager_1.pop_local_task() == tasks_1[0]);
    REQUIRE(std::get<0>(task_manager_1.steal_task(thread_state_2)) == nullptr);
152 153 154
  }
}
#endif // PLS_DEQUE_VARIANT == PLS_DEQUE_LOCK_FREE