blob: 7cb361aaa145eef3ecacb42658f8b0702933916e [file] [log] [blame]
// 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
#ifndef ZIRCON_KERNEL_INCLUDE_KERNEL_CPU_DISTANCE_MAP_H_
#define ZIRCON_KERNEL_INCLUDE_KERNEL_CPU_DISTANCE_MAP_H_
#include <assert.h>
#include <debug.h>
#include <inttypes.h>
#include <lib/lazy_init/lazy_init.h>
#include <stddef.h>
#include <stdint.h>
#include <fbl/alloc_checker.h>
#include <kernel/cpu.h>
#include <ktl/algorithm.h>
#include <ktl/forward.h>
#include <ktl/limits.h>
#include <ktl/move.h>
#include <ktl/optional.h>
#include <ktl/unique_ptr.h>
class CpuDistanceMap;
// Don't use directly. Use CpuDistanceMap::Get().
extern lazy_init::LazyInit<CpuDistanceMap> g_cpu_distance_map;
// A compact distance matrix storing the metric distance between CPUs.
class CpuDistanceMap {
public:
~CpuDistanceMap() = default;
CpuDistanceMap(const CpuDistanceMap&) = delete;
CpuDistanceMap& operator=(const CpuDistanceMap&) = delete;
CpuDistanceMap(CpuDistanceMap&&) = default;
CpuDistanceMap& operator=(CpuDistanceMap&&) = default;
// Index pair that sorts the index elements so that i < j.
struct Index {
Index(cpu_num_t i, cpu_num_t j) : i{ktl::min(i, j)}, j{ktl::max(i, j)} {}
const cpu_num_t i;
const cpu_num_t j;
};
// The value type for metric distances.
using Distance = uint32_t;
// Returns the distace for the given index pair (i, j).
Distance operator[](Index index) const {
if (index.i == index.j) {
return 0;
}
return entries_[LinearIndex(index, cpu_count_)].distance;
}
size_t cpu_count() const { return cpu_count_; }
size_t entry_count() const { return entry_count_; }
Distance distance_threshold() const { return distance_threshold_; }
// Sets the metric distance representing the first significant distance in the
// map. The value is not used directly by this class. Instead, it is provided
// as a convenience for reference by consumers when processing map values.
//
// For example, this value may be used to communicate the threshold for auto
// clustering from the producer of the map to the clustering logic.
void set_distance_threshold(Distance distance_threshold) {
distance_threshold_ = distance_threshold;
}
void Dump() {
dprintf(INFO, "CPU distance map:\n");
const auto& map = *this;
for (cpu_num_t i = 0; i < cpu_count_; i++) {
dprintf(INFO, "CPU %2" PRIu32 ": ", i);
for (cpu_num_t j = 0; j < cpu_count_; j++) {
dprintf(INFO, "%02" PRIu32 "%s", map[{i, j}], (j < cpu_count_ - 1 ? ":" : ""));
}
dprintf(INFO, "\n");
}
}
static CpuDistanceMap& Get() { return g_cpu_distance_map.Get(); }
template <typename Callable>
static void Initialize(size_t cpu_count, Callable&& callable) {
if (auto result = Create(cpu_count, ktl::forward<Callable>(callable))) {
g_cpu_distance_map.Initialize(ktl::move(*result));
} else {
dprintf(CRITICAL, "Failed to create distance map!\n");
}
}
private:
friend struct CpuDistanceMapTestAccess;
struct Entry {
Distance distance;
};
static size_t EntryCountFromCpuCount(size_t cpu_count) {
// Avoid silent integer overflow.
ASSERT(cpu_count <= (size_t{1} << 32));
return (cpu_count * cpu_count - cpu_count) / 2;
}
CpuDistanceMap(size_t cpu_count, size_t entry_count, ktl::unique_ptr<Entry[]> entries)
: cpu_count_{cpu_count}, entry_count_{entry_count}, entries_{ktl::move(entries)} {}
// Creates a distance map with the given number of entries. Invokes the given
// callable with each unique pair of CPUs (i, j), excluding i==j, to compute
// the distance between each pair.
template <typename Callable>
static ktl::optional<CpuDistanceMap> Create(size_t cpu_count, Callable&& callable) {
if (cpu_count == 0) {
return ktl::nullopt;
}
const auto entry_count = EntryCountFromCpuCount(cpu_count);
if (entry_count == 0u) {
return CpuDistanceMap(cpu_count, entry_count, nullptr);
}
if (auto distance_map = AllocateEntries(entry_count)) {
dprintf(INFO, "Allocated %zu entries for CPU distance map.\n", entry_count);
// Fill the distance map entries with CPU distances.
for (cpu_num_t i = 0; i < cpu_count; i++) {
for (cpu_num_t j = i + 1; j < cpu_count; j++) {
if (i != j) {
const auto linear_index = LinearIndex({i, j}, cpu_count);
DEBUG_ASSERT(linear_index < entry_count);
const Entry entry{static_cast<Distance>(ktl::forward<Callable>(callable)(i, j))};
distance_map[linear_index] = entry;
}
}
}
return CpuDistanceMap{cpu_count, entry_count, ktl::move(distance_map)};
}
return ktl::nullopt;
}
// Creates a default distance map where every CPU is equidistant.
static ktl::optional<CpuDistanceMap> Create(size_t cpu_count) {
return Create(cpu_count, [](cpu_num_t i, cpu_num_t j) -> Distance { return i == j ? 0 : 1; });
}
// Returns a linear index into the compact distance matrix.
//
// The compact distance matrix is the upper triangle of the full distance
// matrix, arranged in a compacted row-major linear array. Is it unnecessary
// to store the lower triangle or the diagonal, as the full distance matrix
// is both symmetric around the diagonal and hollow (diagonal is zero).
//
// This function maps the row-by-column indices (i, j) to the linear index k.
// The mapping is defined for 0 <= i < j < n, undefined otherwise.
//
// Example of a full 5x5 distance matrix and the linearized upper triangle,
// with corresponding entries of the upper, lower, and linearized triangles
// labeled a-j:
//
// 0 a b c d
// a 0 e f g
// b e 0 h i -> [a b c d e f g h i j]
// c f h 0 j
// d g i j 0
//
// The mapping (i, k) -> k is derived from the following terms:
//
// The order of the square distance matrix: n
// The row-major linear offset: S = n*i + j
// The triangular number of index i: T = (i*i + i)/2
// The number of diagonal zeros up to row i, inclusive: D = i + 1
//
// k(i, j, n) = S - T - D
//
// The mapping computes the row-major linear offset of (i, j) and subtracts
// the offsets of the lower triangle and diagonal entries up to row i.
//
static size_t LinearIndex(Index index, size_t cpu_count) {
DEBUG_ASSERT_MSG(index.i < cpu_count && index.j < cpu_count && index.i < index.j,
"i=%" PRIu32 " j=%" PRIu32 " count=%zu", index.i, index.j, cpu_count);
const size_t square = cpu_count * index.i + index.j;
const size_t triangle = (index.i * index.i + index.i) / 2;
const size_t diagonal = index.i + 1;
return square - triangle - diagonal;
}
static ktl::unique_ptr<Entry[]> AllocateEntries(size_t entry_count) {
fbl::AllocChecker alloc_checker;
ktl::unique_ptr<Entry[]> distance_map{new (&alloc_checker) Entry[entry_count]};
if (alloc_checker.check()) {
return distance_map;
}
return nullptr;
}
size_t cpu_count_{0};
size_t entry_count_{0};
Distance distance_threshold_{ktl::numeric_limits<Distance>::max()};
ktl::unique_ptr<Entry[]> entries_{};
};
#endif // ZIRCON_KERNEL_INCLUDE_KERNEL_CPU_DISTANCE_MAP_H_