| // 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 <assert.h> |
| #include <debug.h> |
| #include <lib/system-topology.h> |
| #include <zircon/boot/image.h> |
| #include <zircon/errors.h> |
| |
| #include <ktl/move.h> |
| #include <ktl/unique_ptr.h> |
| |
| namespace system_topology { |
| |
| decltype(Graph::system_topology_) Graph::system_topology_; |
| |
| namespace { |
| |
| constexpr size_t kMaxTopologyDepth = 20; |
| |
| inline void ValidationError(size_t index, const char* message) { |
| printf("Error validating topology at node %zu : %s\n", index, message); |
| } |
| |
| template <typename T> |
| zx_status_t GrowVector(size_t new_size, fbl::Vector<T>* vector, fbl::AllocChecker* checker) { |
| for (size_t i = vector->size(); i < new_size; i++) { |
| vector->push_back(T(), checker); |
| if (!checker->check()) { |
| return ZX_ERR_NO_MEMORY; |
| } |
| } |
| return ZX_OK; |
| } |
| |
| } // namespace |
| |
| zx_status_t Graph::Initialize(Graph* graph, const zbi_topology_node_t* flat_nodes, size_t count) { |
| DEBUG_ASSERT(flat_nodes != nullptr); |
| DEBUG_ASSERT(count > 0); |
| |
| if (!Validate(flat_nodes, count)) { |
| return ZX_ERR_INVALID_ARGS; |
| } |
| |
| fbl::AllocChecker checker; |
| ktl::unique_ptr<Node[]> nodes(new (&checker) Node[count]{{}}); |
| if (!checker.check()) { |
| return ZX_ERR_NO_MEMORY; |
| } |
| |
| // Create local instances, if successful we will move them to the Graph's fields. |
| fbl::Vector<Node*> processors; |
| fbl::Vector<Node*> processors_by_logical_id; |
| size_t logical_processor_count = 0; |
| |
| Node* node = nullptr; |
| const zbi_topology_node_t* flat_node = nullptr; |
| for (size_t i = 0; i < count; ++i) { |
| flat_node = &flat_nodes[i]; |
| node = &nodes[i]; |
| |
| node->entity_type = flat_node->entity_type; |
| |
| // Copy info. |
| switch (node->entity_type) { |
| case ZBI_TOPOLOGY_ENTITY_PROCESSOR: |
| node->entity.processor = flat_node->entity.processor; |
| |
| processors.push_back(node, &checker); |
| logical_processor_count += node->entity.processor.logical_id_count; |
| if (!checker.check()) { |
| return ZX_ERR_NO_MEMORY; |
| } |
| |
| for (int i = 0; i < node->entity.processor.logical_id_count; ++i) { |
| const auto index = node->entity.processor.logical_ids[i]; |
| GrowVector(index + 1, &processors_by_logical_id, &checker); |
| processors_by_logical_id[index] = node; |
| if (!checker.check()) { |
| return ZX_ERR_NO_MEMORY; |
| } |
| } |
| break; |
| case ZBI_TOPOLOGY_ENTITY_CLUSTER: |
| node->entity.cluster = flat_node->entity.cluster; |
| break; |
| case ZBI_TOPOLOGY_ENTITY_NUMA_REGION: |
| node->entity.numa_region = flat_node->entity.numa_region; |
| break; |
| case ZBI_TOPOLOGY_ENTITY_CACHE: |
| node->entity.cache = flat_node->entity.cache; |
| break; |
| default: |
| // Other types don't have attached info. |
| break; |
| } |
| |
| if (flat_node->parent_index != ZBI_TOPOLOGY_NO_PARENT) { |
| // Validation should have prevented this. |
| ZX_DEBUG_ASSERT_MSG(flat_node->parent_index >= 0 && flat_node->parent_index < count, |
| "parent_index out of range: %u\n", flat_node->parent_index); |
| |
| node->parent = &nodes[flat_node->parent_index]; |
| node->parent->children.push_back(node, &checker); |
| if (!checker.check()) { |
| return ZX_ERR_NO_MEMORY; |
| } |
| } |
| } |
| |
| *graph = Graph{ktl::move(nodes), ktl::move(processors), logical_processor_count, |
| ktl::move(processors_by_logical_id)}; |
| return ZX_OK; |
| } |
| |
| zx_status_t Graph::InitializeSystemTopology(const zbi_topology_node_t* nodes, size_t count) { |
| Graph graph; |
| const auto status = Graph::Initialize(&graph, nodes, count); |
| if (status != ZX_OK) { |
| return status; |
| } |
| |
| // Initialize the global system topology graph instance. |
| system_topology_.Initialize(ktl::move(graph)); |
| return ZX_OK; |
| } |
| |
| bool Graph::Validate(const zbi_topology_node_t* nodes, size_t count) { |
| DEBUG_ASSERT(nodes != nullptr); |
| DEBUG_ASSERT(count > 0); |
| |
| uint16_t parents[kMaxTopologyDepth]; |
| for (size_t i = 0; i < kMaxTopologyDepth; ++i) { |
| parents[i] = ZBI_TOPOLOGY_NO_PARENT; |
| } |
| |
| uint8_t current_type = ZBI_TOPOLOGY_ENTITY_UNDEFINED; |
| int current_depth = 0; |
| |
| const zbi_topology_node_t* node; |
| for (size_t index = 0; index < count; index++) { |
| // Traverse the nodes in reverse order. |
| const size_t current_index = count - index - 1; |
| |
| node = &nodes[current_index]; |
| |
| if (current_type == ZBI_TOPOLOGY_ENTITY_UNDEFINED) { |
| current_type = node->entity_type; |
| } |
| |
| if (current_type != node->entity_type) { |
| if (current_index == parents[current_depth]) { |
| // If the type changes then it should be the parent of the |
| // previous level. |
| current_depth++; |
| |
| if (current_depth == kMaxTopologyDepth) { |
| ValidationError(current_index, "Structure is too deep, we only support 20 levels."); |
| return false; |
| } |
| } else if (node->entity_type == ZBI_TOPOLOGY_ENTITY_PROCESSOR) { |
| // If it isn't the parent of the previous level, but it is a process than we have |
| // encountered a new branch and should start walking from the bottom again. |
| |
| // Clear the parent index's for all levels but the top, we want to ensure that the |
| // top level of the new branch reports to the same parent as we do. |
| for (int i = current_depth - 1; i >= 0; --i) { |
| parents[i] = ZBI_TOPOLOGY_NO_PARENT; |
| } |
| current_depth = 0; |
| } else { |
| // Otherwise the structure is incorrect. |
| ValidationError(current_index, |
| "Graph is not stored in correct order, with children adjacent to " |
| "parents"); |
| return false; |
| } |
| current_type = node->entity_type; |
| } |
| |
| if (parents[current_depth] == ZBI_TOPOLOGY_NO_PARENT) { |
| parents[current_depth] = node->parent_index; |
| } else if (parents[current_depth] != node->parent_index) { |
| ValidationError(current_index, "Parents at level do not match."); |
| return false; |
| } |
| |
| // Ensure that all leaf nodes are processors. |
| if (current_depth == 0 && node->entity_type != ZBI_TOPOLOGY_ENTITY_PROCESSOR) { |
| ValidationError(current_index, "Encountered a leaf node that isn't a processor."); |
| return false; |
| } |
| |
| // Ensure that all processors are leaf nodes. |
| if (current_depth != 0 && node->entity_type == ZBI_TOPOLOGY_ENTITY_PROCESSOR) { |
| ValidationError(current_index, "Encountered a processor that isn't a leaf node."); |
| return false; |
| } |
| |
| // By the time we reach the first parent we should be at the maximum depth and have no |
| // parents defined. |
| if (current_index == 0 && parents[current_depth] != ZBI_TOPOLOGY_NO_PARENT && |
| (current_depth == kMaxTopologyDepth - 1 || |
| parents[current_depth + 1] == ZBI_TOPOLOGY_NO_PARENT)) { |
| ValidationError(current_index, "Top level of tree should not have a parent"); |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| uint8_t GetPerformanceClass(cpu_num_t cpu_id) { |
| Node* cpu_node = nullptr; |
| if (GetSystemTopology().ProcessorByLogicalId(cpu_id, &cpu_node) != ZX_OK) { |
| dprintf(INFO, "System topology: Failed to get processor node for cpu %u\n", cpu_id); |
| return 0; |
| } |
| DEBUG_ASSERT(cpu_node != nullptr); |
| |
| for (Node* node = cpu_node->parent; node != nullptr; node = node->parent) { |
| if (node->entity_type == ZBI_TOPOLOGY_ENTITY_CLUSTER) { |
| return node->entity.cluster.performance_class; |
| } |
| } |
| |
| return 0; |
| } |
| |
| } // namespace system_topology |