zircon/kernel/tests/cpu_search_tests.cc

// Copyright 2020 The Fuchsia Authors
//
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
// https://opensource.org/licenses/MIT

#include <lib/unittest/unittest.h>
#include <stddef.h>

#include <kernel/cpu.h>
#include <kernel/cpu_distance_map.h>
#include <kernel/cpu_search_set.h>
#include <ktl/algorithm.h>
#include <ktl/limits.h>
#include <ktl/optional.h>

namespace {

// Returns true if first count bits in the CPU mask are set.
bool CpuSetCheck(cpu_mask_t mask, size_t count) {
  size_t set = 0;
  for (cpu_num_t i = 0; i < count; i++) {
    if (mask & cpu_num_to_mask(i)) {
      set++;
    }
  }
  return set == count;
}

}  // anonymous namespace

// Define test types with friend access to CpuDistanceMap and CpuSearchSet.
struct CpuDistanceMapTestAccess {
  template <typename Callable>
  static ktl::optional<CpuDistanceMap> Create(size_t cpu_count, Callable&& callable) {
    return CpuDistanceMap::Create(cpu_count, std::forward<Callable>(callable));
  }
  static size_t EntryCountFromCpuCount(size_t cpu_count) {
    return CpuDistanceMap::EntryCountFromCpuCount(cpu_count);
  }
  static size_t LinearIndex(CpuDistanceMap::Index index, size_t cpu_count) {
    return CpuDistanceMap::LinearIndex(index, cpu_count);
  }
};

struct CpuSearchSetTestAccess {
  static CpuSearchSet::ClusterSet DoAutoCluster(size_t cpu_count, const CpuDistanceMap& map) {
    return CpuSearchSet::DoAutoCluster(cpu_count, map);
  }
  static void DoInitialize(CpuSearchSet* set, cpu_num_t this_cpu, size_t cpu_count,
                           const CpuSearchSet::ClusterSet& cluster_set, const CpuDistanceMap& map) {
    set->DoInitialize(this_cpu, cpu_count, cluster_set, map);
  }
};

static bool distance_map_linear_index_test() {
  BEGIN_TEST;

  // Test that the linear index function does not underflow over a large set of
  // values. The function is mathematically proven to never underflow, but we
  // test anyway in case someone changes the function.
  const size_t cpu_count = 8192;
  const size_t entry_count = CpuDistanceMapTestAccess::EntryCountFromCpuCount(cpu_count);
  for (cpu_num_t i = 0; i < cpu_count; i++) {
    for (cpu_num_t j = i + 1; j < cpu_count; j++) {
      if (i != j) {
        EXPECT_GT(entry_count, CpuDistanceMapTestAccess::LinearIndex({i, j}, cpu_count));
      }
    }
  }

  END_TEST;
}

static bool allocate_distance_map_tests() {
  BEGIN_TEST;

  {
    const size_t cpu_count = 0u;
    size_t invocations = 0;
    auto map = CpuDistanceMapTestAccess::Create(cpu_count, [&invocations](cpu_num_t, cpu_num_t) {
      invocations++;
      return 1u;
    });
    EXPECT_FALSE(map.has_value());
    EXPECT_EQ(0u, invocations);
  }

  {
    const size_t cpu_count = 1u;
    const size_t entry_count = CpuDistanceMapTestAccess::EntryCountFromCpuCount(cpu_count);
    size_t invocations = 0;
    auto map = CpuDistanceMapTestAccess::Create(cpu_count, [&invocations](cpu_num_t, cpu_num_t) {
      invocations++;
      return 1u;
    });
    ASSERT_TRUE(map.has_value());
    EXPECT_EQ(cpu_count, map->cpu_count());
    EXPECT_EQ(entry_count, map->entry_count());
    EXPECT_EQ(entry_count, invocations);
  }

  {
    const size_t cpu_count = 2u;
    const size_t entry_count = CpuDistanceMapTestAccess::EntryCountFromCpuCount(cpu_count);
    size_t invocations = 0;
    auto map = CpuDistanceMapTestAccess::Create(cpu_count, [&invocations](cpu_num_t, cpu_num_t) {
      invocations++;
      return 1u;
    });
    ASSERT_TRUE(map.has_value());
    EXPECT_EQ(cpu_count, map->cpu_count());
    EXPECT_EQ(entry_count, map->entry_count());
    EXPECT_EQ(entry_count, invocations);
  }

  {
    const size_t cpu_count = 32u;
    const size_t entry_count = CpuDistanceMapTestAccess::EntryCountFromCpuCount(cpu_count);
    size_t invocations = 0;
    auto map = CpuDistanceMapTestAccess::Create(cpu_count, [&invocations](cpu_num_t, cpu_num_t) {
      invocations++;
      return 1u;
    });
    ASSERT_TRUE(map.has_value());
    EXPECT_EQ(cpu_count, map->cpu_count());
    EXPECT_EQ(entry_count, map->entry_count());
    EXPECT_EQ(entry_count, invocations);
  }

  {
    // Request a large number of CPUs without triggering the integer overflow ASSERT.
    const size_t cpu_count = size_t{1} << 32;
    size_t invocations = 0;
    auto map = CpuDistanceMapTestAccess::Create(cpu_count, [&invocations](cpu_num_t, cpu_num_t) {
      invocations++;
      return 1u;
    });
    EXPECT_FALSE(map.has_value());
    EXPECT_EQ(0u, invocations);
  }

  END_TEST;
}

static bool distance_map_entry_tests() {
  BEGIN_TEST;

  {
    const size_t cpu_count = 1u;
    auto maybe_map =
        CpuDistanceMapTestAccess::Create(cpu_count, [](cpu_num_t, cpu_num_t) { return 1u; });
    ASSERT_TRUE(maybe_map.has_value());
    CpuDistanceMap& map = maybe_map.value();

    for (cpu_num_t i = 0; i < cpu_count; i++) {
      for (cpu_num_t j = 0; j < cpu_count; j++) {
        if (i == j) {
          EXPECT_EQ(0u, (map[{i, j}]));
        } else {
          EXPECT_EQ(1u, (map[{i, j}]));
        }
      }
    }
  }

  {
    const size_t cpu_count = 2u;
    auto maybe_map =
        CpuDistanceMapTestAccess::Create(cpu_count, [](cpu_num_t, cpu_num_t) { return 1u; });
    ASSERT_TRUE(maybe_map.has_value());
    CpuDistanceMap& map = maybe_map.value();

    for (cpu_num_t i = 0; i < cpu_count; i++) {
      for (cpu_num_t j = 0; j < cpu_count; j++) {
        if (i == j) {
          EXPECT_EQ(0u, (map[{i, j}]));
        } else {
          EXPECT_EQ(1u, (map[{i, j}]));
        }
      }
    }
  }

  {
    const size_t cpu_count = 32u;
    auto maybe_map =
        CpuDistanceMapTestAccess::Create(cpu_count, [](cpu_num_t, cpu_num_t) { return 1u; });
    ASSERT_TRUE(maybe_map.has_value());
    CpuDistanceMap& map = maybe_map.value();

    for (cpu_num_t i = 0; i < cpu_count; i++) {
      for (cpu_num_t j = 0; j < cpu_count; j++) {
        if (i == j) {
          EXPECT_EQ(0u, (map[{i, j}]));
        } else {
          EXPECT_EQ(1u, (map[{i, j}]));
        }
      }
    }
  }

  {
    const size_t cpu_count = 1u;
    auto maybe_map = CpuDistanceMapTestAccess::Create(
        cpu_count, [](cpu_num_t i, cpu_num_t j) { return ktl::max(i, j); });
    ASSERT_TRUE(maybe_map.has_value());
    CpuDistanceMap& map = maybe_map.value();

    for (cpu_num_t i = 0; i < cpu_count; i++) {
      for (cpu_num_t j = 0; j < cpu_count; j++) {
        if (i == j) {
          EXPECT_EQ(0u, (map[{i, j}]));
        } else {
          EXPECT_EQ(ktl::max(i, j), (map[{i, j}]));
        }
      }
    }
  }

  {
    const size_t cpu_count = 32u;
    auto maybe_map = CpuDistanceMapTestAccess::Create(
        cpu_count, [](cpu_num_t i, cpu_num_t j) { return ktl::max(i, j); });
    ASSERT_TRUE(maybe_map.has_value());
    CpuDistanceMap& map = maybe_map.value();

    for (cpu_num_t i = 0; i < cpu_count; i++) {
      for (cpu_num_t j = 0; j < cpu_count; j++) {
        if (i == j) {
          EXPECT_EQ(0u, (map[{i, j}]));
        } else {
          EXPECT_EQ(ktl::max(i, j), (map[{i, j}]));
        }
      }
    }
  }

  END_TEST;
}

static bool default_search_set_test() {
  BEGIN_TEST;

  // A default constructed search set must have one CPU that must be CPU 0.
  CpuSearchSet search_set = {};
  EXPECT_EQ(1u, search_set.cpu_count());
  auto iter = search_set.const_iterator();
  ASSERT_TRUE(iter.begin() != iter.end());
  EXPECT_EQ(0u, iter.begin()->cpu);

  END_TEST;
}

// Use static search set to avoid overflowing the kernel stack.
static CpuSearchSet search_set;

static bool cpu_search_set_test_1() {
  BEGIN_TEST;

  const size_t cpu_count = 1u;
  auto maybe_map =
      CpuDistanceMapTestAccess::Create(cpu_count, [](cpu_num_t, cpu_num_t) { return 1u; });
  ASSERT_TRUE(maybe_map.has_value());

  const uint32_t distance_threshold = 2u;
  maybe_map.value().set_distance_threshold(distance_threshold);
  const CpuDistanceMap& map = maybe_map.value();

  const cpu_num_t cpu0 = 0u;

  // A cluster set for one CPU should contain one cluster with CPU 0 in it.
  auto cluster_set = CpuSearchSetTestAccess::DoAutoCluster(cpu_count, map);
  ASSERT_EQ(1u, cluster_set.clusters.size());
  EXPECT_EQ(0u, cluster_set.clusters[0].id);
  ASSERT_EQ(cpu_count, cluster_set.clusters[0].members.size());
  EXPECT_EQ(cpu0, cluster_set.clusters[0].members[0]);

  CpuSearchSetTestAccess::DoInitialize(&search_set, cpu0, cpu_count, cluster_set, map);
  EXPECT_EQ(cpu_count, search_set.cpu_count());

  // Check that each CPU is in the search set.
  cpu_mask_t cpu_set = 0;
  for (const auto entry : search_set.const_iterator()) {
    ASSERT_GT(cpu_count, entry.cpu);
    cpu_set |= cpu_num_to_mask(entry.cpu);
  }
  EXPECT_TRUE(CpuSetCheck(cpu_set, cpu_count));

  END_TEST;
}

static bool cpu_search_set_test_2() {
  BEGIN_TEST;

  const size_t cpu_count = 2u;
  auto maybe_map =
      CpuDistanceMapTestAccess::Create(cpu_count, [](cpu_num_t, cpu_num_t) { return 1u; });
  ASSERT_TRUE(maybe_map.has_value());

  const uint32_t distance_threshold = 2u;
  maybe_map.value().set_distance_threshold(distance_threshold);
  const CpuDistanceMap& map = maybe_map.value();

  const cpu_num_t cpu0 = 0u;
  const cpu_num_t cpu1 = 1u;

  // A cluster set for two unit distance CPUs should contain one cluster with
  // CPU 0 and 1 in it.
  auto cluster_set = CpuSearchSetTestAccess::DoAutoCluster(cpu_count, map);
  ASSERT_EQ(1u, cluster_set.clusters.size());
  EXPECT_EQ(0u, cluster_set.clusters[0].id);
  ASSERT_EQ(cpu_count, cluster_set.clusters[0].members.size());
  EXPECT_EQ(cpu0, cluster_set.clusters[0].members[0]);
  EXPECT_EQ(cpu1, cluster_set.clusters[0].members[1]);

  {
    // The search set for CPU 0 should have two entries with CPU 0 as the first entry.
    CpuSearchSetTestAccess::DoInitialize(&search_set, cpu0, cpu_count, cluster_set, map);
    EXPECT_EQ(cpu_count, search_set.cpu_count());
    EXPECT_EQ(cpu0, search_set.const_iterator().begin()->cpu);

    // Check that each CPU is in the search set.
    cpu_mask_t cpu_set = 0;
    for (const auto entry : search_set.const_iterator()) {
      ASSERT_GT(cpu_count, entry.cpu);
      cpu_set |= cpu_num_to_mask(entry.cpu);
    }
    EXPECT_TRUE(CpuSetCheck(cpu_set, cpu_count));
  }

  {
    // The search set for CPU 1 should have two entries with CPU 1 as the first entry.
    CpuSearchSetTestAccess::DoInitialize(&search_set, cpu1, cpu_count, cluster_set, map);
    EXPECT_EQ(cpu_count, search_set.cpu_count());
    EXPECT_EQ(cpu1, search_set.const_iterator().begin()->cpu);

    // Check that each CPU is in the search set.
    cpu_mask_t cpu_set = 0;
    for (const auto entry : search_set.const_iterator()) {
      ASSERT_GT(cpu_count, entry.cpu);
      cpu_set |= cpu_num_to_mask(entry.cpu);
    }
    EXPECT_TRUE(CpuSetCheck(cpu_set, cpu_count));
  }

  END_TEST;
}

static bool cpu_search_set_test_4() {
  BEGIN_TEST;

  const size_t cpu_count = 4u;
  auto maybe_map = CpuDistanceMapTestAccess::Create(cpu_count, [](cpu_num_t i, cpu_num_t j) {
    return (i == 0 && j == 1) || (i == 2 && j == 3) ? 1u : 2u;
  });
  ASSERT_TRUE(maybe_map.has_value());

  const uint32_t distance_threshold = 2u;
  maybe_map.value().set_distance_threshold(distance_threshold);
  const CpuDistanceMap& map = maybe_map.value();

  const cpu_num_t cpu0 = 0u;
  const cpu_num_t cpu3 = 3u;

  // A cluster set for two sets of two equidistant CPUs should contain two
  // clusters with pairs CPU 0/1 and 2/3.
  auto cluster_set = CpuSearchSetTestAccess::DoAutoCluster(cpu_count, map);
  ASSERT_EQ(2u, cluster_set.clusters.size());
  EXPECT_EQ(0u, cluster_set.clusters[0].id);
  EXPECT_EQ(1u, cluster_set.clusters[1].id);
  ASSERT_EQ(2u, cluster_set.clusters[0].members.size());
  ASSERT_EQ(2u, cluster_set.clusters[1].members.size());
  EXPECT_EQ(cpu0, cluster_set.clusters[0].members[0]);
  EXPECT_EQ(cpu3, cluster_set.clusters[1].members[1]);

  {
    // The search set for CPU 0 should have four entries with CPU 0 as the first entry.
    CpuSearchSetTestAccess::DoInitialize(&search_set, cpu0, cpu_count, cluster_set, map);
    EXPECT_EQ(cpu_count, search_set.cpu_count());
    EXPECT_EQ(cpu0, search_set.const_iterator().begin()->cpu);

    // Check that each CPU is in the search set.
    cpu_mask_t cpu_set = 0;
    for (const auto entry : search_set.const_iterator()) {
      ASSERT_GT(cpu_count, entry.cpu);
      cpu_set |= cpu_num_to_mask(entry.cpu);
    }
    EXPECT_TRUE(CpuSetCheck(cpu_set, cpu_count));
  }

  {
    // The search set for CPU 3 should have four entries with CPU 3 as the first entry.
    CpuSearchSetTestAccess::DoInitialize(&search_set, cpu3, cpu_count, cluster_set, map);
    EXPECT_EQ(cpu_count, search_set.cpu_count());
    EXPECT_EQ(cpu3, search_set.const_iterator().begin()->cpu);

    // Check that each CPU is in the search set.
    cpu_mask_t cpu_set = 0;
    for (const auto entry : search_set.const_iterator()) {
      ASSERT_GT(cpu_count, entry.cpu);
      cpu_set |= cpu_num_to_mask(entry.cpu);
    }
    EXPECT_TRUE(CpuSetCheck(cpu_set, cpu_count));
  }

  END_TEST;
}

static bool cpu_search_set_test_max() {
  BEGIN_TEST;

  const size_t cpu_count = SMP_MAX_CPUS;
  auto maybe_map =
      CpuDistanceMapTestAccess::Create(cpu_count, [](cpu_num_t, cpu_num_t) { return 1u; });
  ASSERT_TRUE(maybe_map.has_value());

  const uint32_t distance_threshold = 2u;
  maybe_map.value().set_distance_threshold(distance_threshold);
  const CpuDistanceMap& map = maybe_map.value();

  const cpu_num_t cpu0 = 0u;
  const cpu_num_t cpu_max = cpu_count - 1;

  // A cluster set for 32 equidistant CPUs should contain one cluster with
  // all 32 CPUs in it.
  auto cluster_set = CpuSearchSetTestAccess::DoAutoCluster(cpu_count, map);
  ASSERT_EQ(1u, cluster_set.clusters.size());
  EXPECT_EQ(0u, cluster_set.clusters[0].id);
  ASSERT_EQ(cpu_count, cluster_set.clusters[0].members.size());
  EXPECT_EQ(cpu0, cluster_set.clusters[0].members[0]);
  EXPECT_EQ(cpu_max, cluster_set.clusters[0].members[cpu_max]);

  {
    // The search set for CPU 0 should have max entries with CPU 0 as the first entry.
    CpuSearchSetTestAccess::DoInitialize(&search_set, cpu0, cpu_count, cluster_set, map);
    EXPECT_EQ(cpu_count, search_set.cpu_count());
    EXPECT_EQ(cpu0, search_set.const_iterator().begin()->cpu);

    // Check that each CPU is in the search set.
    cpu_mask_t cpu_set = 0;
    for (const auto entry : search_set.const_iterator()) {
      ASSERT_GT(cpu_count, entry.cpu);
      cpu_set |= cpu_num_to_mask(entry.cpu);
    }
    EXPECT_TRUE(CpuSetCheck(cpu_set, cpu_count));
  }

  {
    // The search set for the last CPU should have max entries with last CPU as
    // the first entry.
    CpuSearchSetTestAccess::DoInitialize(&search_set, cpu_max, cpu_count, cluster_set, map);
    EXPECT_EQ(cpu_count, search_set.cpu_count());
    EXPECT_EQ(cpu_max, search_set.const_iterator().begin()->cpu);

    // Check that each CPU is in the search set.
    cpu_mask_t cpu_set = 0;
    for (const auto entry : search_set.const_iterator()) {
      ASSERT_GT(cpu_count, entry.cpu);
      cpu_set |= cpu_num_to_mask(entry.cpu);
    }
    EXPECT_TRUE(CpuSetCheck(cpu_set, cpu_count));
  }

  END_TEST;
}

UNITTEST_START_TESTCASE(cpu_distance_map_tests)
UNITTEST("distance_map_linear_index", distance_map_linear_index_test)
UNITTEST("allocate_distance_map", allocate_distance_map_tests)
UNITTEST("distance_map_entries", distance_map_entry_tests)
UNITTEST_END_TESTCASE(cpu_distance_map_tests, "cpu_distance_map_tests", "cpu_distance_map_tests")

UNITTEST_START_TESTCASE(cpu_search_set_tests)
UNITTEST("default_search_set_test", default_search_set_test)
UNITTEST("cpu_search_set_test_1", cpu_search_set_test_1)
UNITTEST("cpu_search_set_test_2", cpu_search_set_test_2)
UNITTEST("cpu_search_set_test_4", cpu_search_set_test_4)
UNITTEST("cpu_search_set_test_max", cpu_search_set_test_max)
UNITTEST_END_TESTCASE(cpu_search_set_tests, "cpu_search_set_tests", "cpu_search_set_tests")