// Copyright 2018 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/system-topology.h>
#include <lib/unittest/unittest.h>

namespace {

using system_topology::Graph;
using system_topology::Node;

// Should be larger than the largest topology used here.
constexpr size_t kTopologyArraySize = 60;

struct FlatTopo {
  zbi_topology_node_t nodes[kTopologyArraySize];
  size_t node_count = 0;
};

// Defined at bottom of file, they are long and noisy.

// A generic arm big.LITTLE.
FlatTopo SimpleTopology();

// Roughly a threadripper 2990X.
FlatTopo ComplexTopology();

// Same as Simple but stored with all nodes on a level adjacent to each other.
FlatTopo HierarchicalTopology();

bool test_flat_to_heap_simple() {
  BEGIN_TEST;
  FlatTopo topo = SimpleTopology();

  Graph graph;
  ASSERT_EQ(ZX_OK, Graph::Initialize(&graph, topo.nodes, topo.node_count));
  ASSERT_EQ(3u, graph.processors().size());
  ASSERT_EQ(4u, graph.logical_processor_count());  // One of the cores is SMT2.

  // Test lookup.
  system_topology::Node* node;
  ASSERT_EQ(ZX_OK, graph.ProcessorByLogicalId(1, &node));
  ASSERT_EQ(ZBI_TOPOLOGY_ENTITY_PROCESSOR, node->entity.discriminant);
  ASSERT_EQ(ZBI_TOPOLOGY_PROCESSOR_FLAGS_PRIMARY, node->entity.processor.flags);
  ASSERT_EQ(ZBI_TOPOLOGY_ENTITY_CLUSTER, node->parent->entity.discriminant);
  ASSERT_EQ(1, node->parent->entity.cluster.performance_class);

  // Test out of bounds lookup.
  ASSERT_EQ(ZX_ERR_NOT_FOUND, graph.ProcessorByLogicalId(
                                  static_cast<cpu_num_t>(graph.logical_processor_count()), &node));

  END_TEST;
}

bool test_flat_to_heap_complex() {
  BEGIN_TEST;
  FlatTopo topo = ComplexTopology();

  Graph graph;
  ASSERT_EQ(ZX_OK, Graph::Initialize(&graph, topo.nodes, topo.node_count));
  ASSERT_EQ(32u, graph.processors().size());

  END_TEST;
}

bool test_flat_to_heap_walk_result() {
  BEGIN_TEST;
  FlatTopo topo = ComplexTopology();

  Graph graph;
  ASSERT_EQ(ZX_OK, Graph::Initialize(&graph, topo.nodes, topo.node_count));
  ASSERT_EQ(32u, graph.processors().size());

  // For each processor we walk all the way up the graph.
  for (Node* processor : graph.processors()) {
    Node* current = processor;
    Node* next = current->parent;
    while (next != nullptr) {
      // Ensure that the children lists contain all children.
      bool found = false;
      for (Node* child : next->children) {
        found |= child == current;
      }
      ASSERT_TRUE(found, "A node is not listed as a child of its parent.");

      current = current->parent;
      next = current->parent;
    }
  }

  END_TEST;
}

bool test_validate_processor_not_leaf() {
  BEGIN_TEST;
  FlatTopo topo = ComplexTopology();

  // Replace a die node with a processor.
  topo.nodes[1].entity.discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR;

  Graph graph;
  ASSERT_EQ(ZX_ERR_INVALID_ARGS, Graph::Initialize(&graph, topo.nodes, topo.node_count));

  END_TEST;
}

bool test_validate_leaf_not_processor() {
  BEGIN_TEST;
  FlatTopo topo = SimpleTopology();

  // Replace a processor node with a cluster.
  topo.nodes[4].entity.discriminant = ZBI_TOPOLOGY_ENTITY_CLUSTER;

  Graph graph;
  ASSERT_EQ(ZX_ERR_INVALID_ARGS, Graph::Initialize(&graph, topo.nodes, topo.node_count));

  END_TEST;
}

bool test_validate_cycle() {
  BEGIN_TEST;
  FlatTopo topo = ComplexTopology();

  // Set the parent index of the die to a processor under it.
  topo.nodes[1].parent_index = 4;

  Graph graph;
  ASSERT_EQ(ZX_ERR_INVALID_ARGS, Graph::Initialize(&graph, topo.nodes, topo.node_count));

  END_TEST;
}

// This is a cycle like above but fails due to parent mismatch with other nodes
// on its level.
bool test_validate_cycle_shared_parent() {
  BEGIN_TEST;
  FlatTopo topo = ComplexTopology();

  // Set the parent index of the die to a processor under it.
  topo.nodes[2].parent_index = 4;

  Graph graph;
  ASSERT_EQ(ZX_ERR_INVALID_ARGS, Graph::Initialize(&graph, topo.nodes, topo.node_count));

  END_TEST;
}

// Another logical way to store the graph would be hierarchical, all the top
// level nodes together, followed by the next level, and so on.
// We are proscriptive however that they should be stored in a depth-first
// ordering, so this other ordering should fail validation.
bool test_validate_hierarchical_storage() {
  BEGIN_TEST;
  FlatTopo topo = HierarchicalTopology();

  // Set the parent index of the die to a processor under it.
  topo.nodes[2].parent_index = 4;

  Graph graph;
  ASSERT_EQ(ZX_ERR_INVALID_ARGS, Graph::Initialize(&graph, topo.nodes, topo.node_count));

  END_TEST;
}

UNITTEST_START_TESTCASE(system_topology_tests)
UNITTEST("Parse flat topology, simple.", test_flat_to_heap_simple)
UNITTEST("Parse flat topology, complex.", test_flat_to_heap_complex)
UNITTEST("Parse complex then walk result.", test_flat_to_heap_walk_result)
UNITTEST("Fail validation if processor is not a leaf.", test_validate_processor_not_leaf)
UNITTEST("Fail validation if leaf is not processor.", test_validate_leaf_not_processor)
UNITTEST("Fail validation if there is a cycle.", test_validate_cycle)
UNITTEST("Fail validation if a cycle with a shared parent.", test_validate_cycle_shared_parent)
UNITTEST("Fail validation if storage order is incorrect.", test_validate_hierarchical_storage)
UNITTEST_END_TESTCASE(system_topology_tests, "system-topology",
                      "Test parsing and validation of the flat system topology.")

// Generic ARM big.LITTLE layout.
//   [cluster]       [cluster]
//   [p1a,p1b]      [p3]   [p4]
FlatTopo SimpleTopology() {
  FlatTopo topo;
  zbi_topology_node_t* nodes = topo.nodes;

  uint16_t logical_processor = 0;
  uint16_t big_cluster = 0, little_cluster = 0;

  uint16_t index = 0;
  nodes[big_cluster = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_CLUSTER,
              .cluster =
                  {
                      .performance_class = 1,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[index++] = zbi_topology_node_t{
      .entity = {.discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR,
                 .processor =
                     {
                         .architecture_info = {},
                         .flags = ZBI_TOPOLOGY_PROCESSOR_FLAGS_PRIMARY,
                         .logical_ids = {logical_processor++, logical_processor++},
                         .logical_id_count = 2,
                     }},
      .parent_index = big_cluster,
  };

  nodes[little_cluster = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_CLUSTER,
              .cluster =
                  {
                      .performance_class = 0,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR,
              .processor =
                  {
                      .architecture_info = {},
                      .flags = 0,
                      .logical_ids = {logical_processor++},
                      .logical_id_count = 1,
                  },
          },
      .parent_index = little_cluster,
  };

  nodes[index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR,
              .processor =
                  {
                      .architecture_info = {},
                      .flags = 0,
                      .logical_ids = {logical_processor++},
                      .logical_id_count = 1,
                  },
          },
      .parent_index = little_cluster,
  };

  topo.node_count = index;
  return topo;
}

FlatTopo HierarchicalTopology() {
  FlatTopo topo;
  zbi_topology_node_t* nodes = topo.nodes;

  uint16_t logical_processor = 0;
  uint16_t big_cluster = 0, little_cluster = 0;

  uint16_t index = 0;
  nodes[big_cluster = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_CLUSTER,
              .cluster =
                  {
                      .performance_class = 1,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[little_cluster = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_CLUSTER,
              .cluster =
                  {
                      .performance_class = 0,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR,
              .processor =
                  {
                      .architecture_info = {},
                      .flags = ZBI_TOPOLOGY_PROCESSOR_FLAGS_PRIMARY,
                      .logical_ids = {logical_processor++, logical_processor++},
                      .logical_id_count = 2,

                  },
          },
      .parent_index = big_cluster,
  };

  nodes[index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR,
              .processor =
                  {
                      .architecture_info = {},
                      .flags = 0,
                      .logical_ids = {logical_processor++},
                      .logical_id_count = 1,

                  },
          },
      .parent_index = little_cluster,
  };

  nodes[index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR,
              .processor =
                  {

                      .architecture_info = {},
                      .flags = 0,
                      .logical_ids = {logical_processor++},
                      .logical_id_count = 1,
                  },
          },
      .parent_index = little_cluster,
  };

  topo.node_count = index;
  return topo;
}

// Add a threadripper CCX (CPU complex), a four core cluster.
void AddCCX(uint16_t parent, zbi_topology_node_t* nodes, uint16_t* index,
            uint16_t* logical_processor) {
  uint16_t cache = 0, cluster = 0;
  nodes[cluster = (*index)++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_CLUSTER,
              .cluster =
                  {
                      .performance_class = 0,
                  },
          },
      .parent_index = parent,
  };

  nodes[cache = (*index)++] = zbi_topology_node_t{
      .entity = {.discriminant = ZBI_TOPOLOGY_ENTITY_CACHE},
      .parent_index = cluster,
  };

  for (int i = 0; i < 4; i++) {
    nodes[(*index)++] = zbi_topology_node_t{
        .entity =
            {
                .discriminant = ZBI_TOPOLOGY_ENTITY_PROCESSOR,
                .processor =
                    {

                        .architecture_info = {},
                        .flags = 0,
                        .logical_ids = {(*logical_processor)++, (*logical_processor)++},
                        .logical_id_count = 2,
                    },
            },
        .parent_index = cache,
    };
  }
}

// Roughly a threadripper 2990X.
// Four sets of the following:
//                [numa1]
//                [die1]
//     [cluster1]         [cluster2]
//      [cache1]           [cache2]
//  [p1][p2][p3][p4]   [p5][p6][p7][p8]
FlatTopo ComplexTopology() {
  FlatTopo topo;
  zbi_topology_node_t* nodes = topo.nodes;

  uint16_t logical_processor = 0;
  uint16_t die[4] = {0};
  uint16_t numa[4] = {0};

  uint16_t index = 0;

  nodes[numa[0] = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_NUMA_REGION,
              .numa_region =
                  {
                      .start = 0x1,
                      .size = 1,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[die[0] = index++] = zbi_topology_node_t{
      .entity = {.discriminant = ZBI_TOPOLOGY_ENTITY_DIE},
      .parent_index = numa[0],
  };

  AddCCX(die[0], nodes, &index, &logical_processor);
  AddCCX(die[0], nodes, &index, &logical_processor);

  nodes[numa[1] = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_NUMA_REGION,
              .numa_region =
                  {
                      .start = 0x3,
                      .size = 1,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[die[1] = index++] = zbi_topology_node_t{
      .entity = {.discriminant = ZBI_TOPOLOGY_ENTITY_DIE},
      .parent_index = numa[1],
  };

  AddCCX(die[1], nodes, &index, &logical_processor);
  AddCCX(die[1], nodes, &index, &logical_processor);

  nodes[numa[2] = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_NUMA_REGION,
              .numa_region =
                  {
                      .start = 0x5,
                      .size = 1,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[die[2] = index++] = zbi_topology_node_t{
      .entity = {.discriminant = ZBI_TOPOLOGY_ENTITY_DIE},
      .parent_index = numa[2],
  };

  AddCCX(die[2], nodes, &index, &logical_processor);
  AddCCX(die[2], nodes, &index, &logical_processor);

  nodes[numa[3] = index++] = zbi_topology_node_t{
      .entity =
          {
              .discriminant = ZBI_TOPOLOGY_ENTITY_NUMA_REGION,
              .numa_region =
                  {
                      .start = 0x7,
                      .size = 1,
                  },
          },
      .parent_index = ZBI_TOPOLOGY_NO_PARENT,
  };

  nodes[die[3] = index++] = zbi_topology_node_t{
      .entity = {.discriminant = ZBI_TOPOLOGY_ENTITY_DIE},
      .parent_index = numa[3],
  };

  AddCCX(die[3], nodes, &index, &logical_processor);
  AddCCX(die[3], nodes, &index, &logical_processor);

  topo.node_count = index;
  return topo;
}

}  // namespace
/*
int main(int argc, char** argv) {
    return unittest_run_all_tests(argc, argv) ? 0 : -1;
}
*/