1 #include <lib/system-topology.h>
2 #include <zircon/errors.h>
3
4 namespace system_topology {
5 namespace {
6 constexpr size_t kMaxTopologyDepth = 20;
7
ValidationError(int index,const char * message)8 inline void ValidationError(int index, const char* message) {
9 printf("Error validating topology at node %d : %s \n", index, message);
10 }
11
12 } // namespace
13
Update(zbi_topology_node_t * flat_nodes,size_t count)14 zx_status_t Graph::Update(zbi_topology_node_t* flat_nodes, size_t count) {
15 if (flat_nodes == nullptr || count == 0 || !Validate(flat_nodes, static_cast<int>(count))) {
16 return ZX_ERR_INVALID_ARGS;
17 }
18
19 if (nodes_.get() != nullptr) {
20 return ZX_ERR_ALREADY_EXISTS;
21 }
22
23 fbl::AllocChecker checker;
24 nodes_.reset(new Node[count]{{}});
25
26 Node* node = nullptr;
27 zbi_topology_node_t* flat_node = nullptr;
28 for (size_t i = 0; i < count; ++i) {
29 flat_node = &flat_nodes[i];
30 node = &nodes_[i];
31
32 node->entity_type = flat_node->entity_type;
33
34 // Copy info.
35 switch (node->entity_type) {
36 case ZBI_TOPOLOGY_ENTITY_PROCESSOR:
37 node->entity.processor = flat_node->entity.processor;
38
39 processors_.push_back(node, &checker);
40 if (!checker.check()) {
41 nodes_.reset(nullptr);
42 return ZX_ERR_NO_MEMORY;
43 }
44
45 for (int i = 0; i < node->entity.processor.logical_id_count; ++i) {
46 processors_by_logical_id_.insert(node->entity.processor.logical_ids[i],
47 node, &checker);
48 if (!checker.check()) {
49 nodes_.reset(nullptr);
50 return ZX_ERR_NO_MEMORY;
51 }
52 }
53
54 break;
55 case ZBI_TOPOLOGY_ENTITY_CLUSTER:
56 node->entity.cluster = flat_node->entity.cluster;
57 break;
58 case ZBI_TOPOLOGY_ENTITY_NUMA_REGION:
59 node->entity.numa_region = flat_node->entity.numa_region;
60 break;
61 default:
62 // Other types don't have attached info.
63 break;
64 }
65
66 if (flat_node->parent_index != ZBI_TOPOLOGY_NO_PARENT) {
67 // Validation should have prevented this.
68 ZX_DEBUG_ASSERT_MSG(flat_node->parent_index >= 0 && flat_node->parent_index < count,
69 "parent_index out of range: %u\n", flat_node->parent_index);
70
71 node->parent = &nodes_[flat_node->parent_index];
72 node->parent->children.push_back(node, &checker);
73 if (!checker.check()) {
74 nodes_.reset(nullptr);
75 return ZX_ERR_NO_MEMORY;
76 }
77 }
78 }
79
80 return ZX_OK;
81 }
82
Validate(zbi_topology_node_t * nodes,int count) const83 bool Graph::Validate(zbi_topology_node_t* nodes, int count) const {
84 uint16_t parents[kMaxTopologyDepth];
85 for (size_t i = 0; i < kMaxTopologyDepth; ++i) {
86 parents[i] = ZBI_TOPOLOGY_NO_PARENT;
87 }
88
89 uint8_t current_type = ZBI_TOPOLOGY_ENTITY_UNDEFINED;
90 int current_depth = 0;
91
92 zbi_topology_node_t* node;
93 for (int current_index = count - 1; current_index >= 0; current_index--) {
94 node = &nodes[current_index];
95
96 if (current_type == ZBI_TOPOLOGY_ENTITY_UNDEFINED) {
97 current_type = node->entity_type;
98 }
99
100 if (current_type != node->entity_type) {
101
102 if (current_index == parents[current_depth]) {
103 // If the type changes then it should be the parent of the
104 // previous level.
105 current_depth++;
106
107 if (current_depth == kMaxTopologyDepth) {
108 ValidationError(current_index,
109 "Structure is too deep, we only support 20 levels.");
110 return false;
111 }
112 } else if (node->entity_type == ZBI_TOPOLOGY_ENTITY_PROCESSOR) {
113 // If it isn't the parent of the previous level, but it is a process than we have
114 // encountered a new branch and should start walking from the bottom again.
115
116 // Clear the parent index's for all levels but the top, we want to ensure that the
117 // top level of the new branch reports to the same parent as we do.
118 for (int i = current_depth - 1; i >= 0; --i) {
119 parents[i] = ZBI_TOPOLOGY_NO_PARENT;
120 }
121 current_depth = 0;
122 } else {
123 // Otherwise the structure is incorrect.
124 ValidationError(current_index,
125 "Graph is not stored in correct order, with children adjacent to "
126 "parents");
127 return false;
128 }
129 current_type = node->entity_type;
130 }
131
132 if (parents[current_depth] == ZBI_TOPOLOGY_NO_PARENT) {
133 parents[current_depth] = node->parent_index;
134 } else if (parents[current_depth] != node->parent_index) {
135 ValidationError(current_index, "Parents at level do not match.");
136 return false;
137 }
138
139 // Ensure that all leaf nodes are processors.
140 if (current_depth == 0 && node->entity_type != ZBI_TOPOLOGY_ENTITY_PROCESSOR) {
141 ValidationError(current_index, "Encountered a leaf node that isn't a processor.");
142 return false;
143 }
144
145 // Ensure that all processors are leaf nodes.
146 if (current_depth != 0 && node->entity_type == ZBI_TOPOLOGY_ENTITY_PROCESSOR) {
147 ValidationError(current_index, "Encountered a processor that isn't a leaf node.");
148 return false;
149 }
150
151 // By the time we reach the first parent we should be at the maximum depth and have no
152 // parents defined.
153 if (current_index == 0 && parents[current_depth] != ZBI_TOPOLOGY_NO_PARENT &&
154 (current_depth == kMaxTopologyDepth - 1 ||
155 parents[current_depth + 1] == ZBI_TOPOLOGY_NO_PARENT)) {
156 ValidationError(current_index, "Top level of tree should not have a parent");
157 return false;
158 }
159 }
160 return true;
161 }
162
163 } // namespace system_topology
164