1use fidl_fuchsia_hardware_interconnect as icc;
6use log::error;
7use std::collections::{BTreeMap, BTreeSet, VecDeque};
8use zx::Status;
9
10#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
11pub struct NodeId(pub u32);
12
13#[derive(Debug, PartialEq, Eq)]
14struct IncomingEdge {
15 weight: u32,
17}
18
19#[derive(Debug, PartialEq, Eq)]
20struct BandwidthRequest {
21 average_bandwidth_bps: u64,
22 peak_bandwidth_bps: u64,
23}
24
25#[derive(Debug, PartialEq, Eq)]
26struct InterconnectNode {
27 name: String,
28 id: NodeId,
29 incoming_edges: BTreeMap<NodeId, IncomingEdge>,
31 path_bandwidth_requests: BTreeMap<PathId, BandwidthRequest>,
33 initial_avg_bandwidth_bps: u64,
34 initial_peak_bandwidth_bps: u64,
35}
36
37#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
38pub struct PathId(pub u32);
39
40impl std::fmt::Display for PathId {
41 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
42 write!(f, "{}", self.0)
43 }
44}
45
46#[derive(Debug, PartialEq, Eq)]
47pub struct Path {
48 name: String,
49 id: PathId,
50 nodes: Vec<NodeId>,
51}
52
53impl Path {
54 pub fn name(&self) -> &str {
55 &self.name
56 }
57
58 pub fn id(&self) -> PathId {
59 self.id
60 }
61}
62
63#[derive(Debug, PartialEq, Eq)]
64pub struct NodeGraph {
65 nodes: BTreeMap<NodeId, InterconnectNode>,
68}
69
70impl NodeGraph {
71 pub fn new(nodes: Vec<icc::Node>, edges: Vec<icc::Edge>) -> Result<Self, Status> {
72 struct ParsedNode {
74 id: NodeId,
75 name: String,
76 #[allow(unused)]
77 interconnect_name: Option<String>,
78 initial_avg_bandwidth_bps: u64,
79 initial_peak_bandwidth_bps: u64,
80 }
81 let nodes: Vec<_> = Result::from_iter(nodes.into_iter().map(|node| {
82 Ok::<_, Status>(ParsedNode {
83 id: NodeId(node.id.ok_or(Status::INVALID_ARGS)?),
84 name: node.name.ok_or(Status::INVALID_ARGS)?,
85 interconnect_name: node.interconnect_name,
86 initial_avg_bandwidth_bps: node.initial_avg_bandwidth_bps.unwrap_or(0),
87 initial_peak_bandwidth_bps: node.initial_peak_bandwidth_bps.unwrap_or(0),
88 })
89 }))?;
90
91 struct ParsedEdge {
92 src_node_id: NodeId,
93 dst_node_id: NodeId,
94 weight: u32,
95 }
96 let edges: Vec<_> = Result::from_iter(edges.into_iter().map(|edge| {
97 Ok::<_, Status>(ParsedEdge {
98 src_node_id: NodeId(edge.src_node_id.ok_or(Status::INVALID_ARGS)?),
99 dst_node_id: NodeId(edge.dst_node_id.ok_or(Status::INVALID_ARGS)?),
100 weight: edge.weight.unwrap_or(1),
101 })
102 }))?;
103
104 let valid_node_ids: BTreeSet<_> = nodes.iter().map(|node| node.id).collect();
106 if valid_node_ids.len() != nodes.len() {
107 error!("Node list contains duplicate entries.");
108 return Err(Status::INVALID_ARGS);
109 }
110
111 let edge_pairs: BTreeSet<_> =
112 edges.iter().map(|edge| (edge.src_node_id, edge.dst_node_id)).collect();
113 if edge_pairs.len() != edges.len() {
114 error!("Edge list contains duplicate pairs of source to destination node ids.");
115 return Err(Status::INVALID_ARGS);
116 }
117
118 for edge in edges.iter() {
119 if !valid_node_ids.contains(&edge.src_node_id) {
120 error!("Edge contains an invalid src node id {:?}.", edge.src_node_id);
121 return Err(Status::INVALID_ARGS);
122 }
123 if !valid_node_ids.contains(&edge.dst_node_id) {
124 error!("Edge contains an invalid dst node id {:?}.", edge.dst_node_id);
125 return Err(Status::INVALID_ARGS);
126 }
127 if edge.src_node_id == edge.dst_node_id {
128 error!("Edge cannot have src and dst node ids be the same.");
129 return Err(Status::INVALID_ARGS);
130 }
131 }
132
133 let mut graph = BTreeMap::new();
135 for node in nodes {
136 let incoming_edges: BTreeMap<_, _> = edges
141 .iter()
142 .filter(|edge| edge.dst_node_id == node.id)
143 .map(|edge| (edge.src_node_id, IncomingEdge { weight: edge.weight }))
144 .collect();
145 graph.insert(
146 node.id,
147 InterconnectNode {
148 name: node.name,
149 id: node.id,
150 incoming_edges,
151 path_bandwidth_requests: BTreeMap::new(),
152 initial_avg_bandwidth_bps: node.initial_avg_bandwidth_bps,
153 initial_peak_bandwidth_bps: node.initial_peak_bandwidth_bps,
154 },
155 );
156 }
157
158 Ok(NodeGraph { nodes: graph })
159 }
160
161 pub fn update_path(
163 &mut self,
164 path: &Path,
165 average_bandwidth_bps: u64,
166 peak_bandwidth_bps: u64,
167 ) {
168 for node in &path.nodes {
169 let node = self.nodes.get_mut(&node).expect("path is already validated");
170 let request = node
171 .path_bandwidth_requests
172 .get_mut(&path.id)
173 .expect("path was created from graph");
174 request.average_bandwidth_bps = average_bandwidth_bps;
175 request.peak_bandwidth_bps = peak_bandwidth_bps;
176 }
177 }
178
179 pub fn make_bandwidth_requests(&self, path: &Path) -> Vec<icc::NodeBandwidth> {
182 path.nodes
183 .iter()
184 .map(|node_id| {
185 let node = self.nodes.get(&node_id).expect("path is already validated");
186 let requests: Vec<_> = node
187 .path_bandwidth_requests
188 .iter()
189 .map(|(_, request)| icc::BandwidthRequest {
190 average_bandwidth_bps: Some(request.average_bandwidth_bps),
191 peak_bandwidth_bps: Some(request.peak_bandwidth_bps),
192 ..Default::default()
193 })
194 .collect();
195 icc::NodeBandwidth {
196 node_id: Some(node_id.0),
197 requests: Some(requests),
198 ..Default::default()
199 }
200 })
201 .collect()
202 }
203
204 pub fn make_path(
206 &mut self,
207 path_id: PathId,
208 path_name: impl Into<String>,
209 src_node_id: NodeId,
210 dst_node_id: NodeId,
211 ) -> Result<Path, Status> {
212 let mut queue = VecDeque::new();
213 let mut visited = BTreeSet::new();
215 queue.push_back((dst_node_id, Vec::new()));
216 while let Some((node_id, mut path)) = queue.pop_front() {
218 if visited.contains(&node_id) {
219 continue;
220 }
221 visited.insert(node_id);
222 path.push(node_id);
223 if node_id == src_node_id {
224 path.reverse();
225 for node_id in path.iter() {
227 let node = self.nodes.get(&node_id).unwrap();
228 if node.path_bandwidth_requests.contains_key(&path_id) {
229 error!("Duplicate path id {path_id:?}");
230 return Err(Status::ALREADY_EXISTS);
231 }
232 }
233 for node_id in path.iter() {
234 let node = self.nodes.get_mut(&node_id).unwrap();
235 node.path_bandwidth_requests.insert(
236 path_id,
237 BandwidthRequest {
238 average_bandwidth_bps: node.initial_avg_bandwidth_bps,
239 peak_bandwidth_bps: node.initial_peak_bandwidth_bps,
240 },
241 );
242 }
243 return Ok(Path { name: path_name.into(), id: path_id, nodes: path });
244 }
245 for (node_id, _) in &self.nodes.get(&node_id).unwrap().incoming_edges {
247 queue.push_back((*node_id, path.clone()));
248 }
249 }
250 error!("Path between {src_node_id:?} and {dst_node_id:?} not found");
251 Err(Status::NOT_FOUND)
252 }
253}
254
255#[cfg(test)]
256mod tests {
257 use super::*;
258
259 #[fuchsia::test]
260 fn test_node_graph_simple() {
261 let nodes = vec![
262 icc::Node {
263 id: Some(0),
264 name: Some("zero".to_string()),
265 interconnect_name: None,
266 ..Default::default()
267 },
268 icc::Node {
269 id: Some(1),
270 name: Some("one".to_string()),
271 interconnect_name: None,
272 ..Default::default()
273 },
274 ];
275 let edges = vec![icc::Edge {
276 src_node_id: Some(0),
277 dst_node_id: Some(1),
278 weight: None,
279 ..Default::default()
280 }];
281 let graph = NodeGraph::new(nodes, edges).unwrap();
282 assert_eq!(
283 graph,
284 NodeGraph {
285 nodes: BTreeMap::from([
286 (
287 NodeId(0),
288 InterconnectNode {
289 name: "zero".to_string(),
290 id: NodeId(0),
291 incoming_edges: BTreeMap::new(),
292 path_bandwidth_requests: BTreeMap::new(),
293 initial_avg_bandwidth_bps: 0,
294 initial_peak_bandwidth_bps: 0,
295 }
296 ),
297 (
298 NodeId(1),
299 InterconnectNode {
300 name: "one".to_string(),
301 id: NodeId(1),
302 incoming_edges: BTreeMap::from([(
303 NodeId(0),
304 IncomingEdge { weight: 1 }
305 )]),
306 path_bandwidth_requests: BTreeMap::new(),
307 initial_avg_bandwidth_bps: 0,
308 initial_peak_bandwidth_bps: 0,
309 }
310 ),
311 ]),
312 }
313 );
314 }
315
316 #[fuchsia::test]
317 fn test_node_graph_missing_id() {
318 let nodes = vec![
319 icc::Node {
320 id: None,
321 name: Some("zero".to_string()),
322 interconnect_name: None,
323 ..Default::default()
324 },
325 icc::Node {
326 id: Some(1),
327 name: Some("one".to_string()),
328 interconnect_name: None,
329 ..Default::default()
330 },
331 ];
332 let edges = vec![icc::Edge {
333 src_node_id: Some(0),
334 dst_node_id: Some(1),
335 weight: Some(1),
336 ..Default::default()
337 }];
338 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
339 }
340
341 #[fuchsia::test]
342 fn test_node_graph_missing_name() {
343 let nodes = vec![
344 icc::Node { id: Some(0), name: None, interconnect_name: None, ..Default::default() },
345 icc::Node {
346 id: Some(1),
347 name: Some("one".to_string()),
348 interconnect_name: None,
349 ..Default::default()
350 },
351 ];
352 let edges = vec![icc::Edge {
353 src_node_id: Some(0),
354 dst_node_id: Some(1),
355 weight: Some(1),
356 ..Default::default()
357 }];
358 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
359 }
360
361 #[fuchsia::test]
362 fn test_node_graph_missing_src() {
363 let nodes = vec![
364 icc::Node {
365 id: Some(0),
366 name: Some("zero".to_string()),
367 interconnect_name: None,
368 ..Default::default()
369 },
370 icc::Node {
371 id: Some(1),
372 name: Some("one".to_string()),
373 interconnect_name: None,
374 ..Default::default()
375 },
376 ];
377 let edges = vec![icc::Edge {
378 src_node_id: None,
379 dst_node_id: Some(1),
380 weight: Some(1),
381 ..Default::default()
382 }];
383 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
384 }
385
386 #[fuchsia::test]
387 fn test_node_graph_missing_dst() {
388 let nodes = vec![
389 icc::Node {
390 id: Some(0),
391 name: Some("zero".to_string()),
392 interconnect_name: None,
393 ..Default::default()
394 },
395 icc::Node {
396 id: Some(1),
397 name: Some("one".to_string()),
398 interconnect_name: None,
399 ..Default::default()
400 },
401 ];
402 let edges = vec![icc::Edge {
403 src_node_id: Some(0),
404 dst_node_id: None,
405 weight: Some(1),
406 ..Default::default()
407 }];
408 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
409 }
410
411 #[fuchsia::test]
412 fn test_node_graph_invalid_edge() {
413 let nodes = vec![
414 icc::Node {
415 id: Some(0),
416 name: Some("zero".to_string()),
417 interconnect_name: None,
418 ..Default::default()
419 },
420 icc::Node {
421 id: Some(1),
422 name: Some("one".to_string()),
423 interconnect_name: None,
424 ..Default::default()
425 },
426 ];
427 let edges = vec![icc::Edge {
428 src_node_id: Some(0),
429 dst_node_id: Some(0),
430 weight: Some(1),
431 ..Default::default()
432 }];
433 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
434 }
435
436 #[fuchsia::test]
437 fn test_node_graph_missing_dst_node() {
438 let nodes = vec![icc::Node {
439 id: Some(0),
440 name: Some("zero".to_string()),
441 interconnect_name: None,
442 ..Default::default()
443 }];
444 let edges = vec![icc::Edge {
445 src_node_id: Some(0),
446 dst_node_id: Some(1),
447 weight: Some(1),
448 ..Default::default()
449 }];
450 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
451 }
452
453 #[fuchsia::test]
454 fn test_node_graph_missing_src_node() {
455 let nodes = vec![icc::Node {
456 id: Some(0),
457 name: Some("zero".to_string()),
458 interconnect_name: None,
459 ..Default::default()
460 }];
461 let edges = vec![icc::Edge {
462 src_node_id: Some(1),
463 dst_node_id: Some(0),
464 weight: Some(1),
465 ..Default::default()
466 }];
467 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
468 }
469
470 #[fuchsia::test]
471 fn test_node_graph_missing_duplicate_node() {
472 let nodes = vec![
473 icc::Node {
474 id: Some(0),
475 name: Some("zero".to_string()),
476 interconnect_name: None,
477 ..Default::default()
478 },
479 icc::Node {
480 id: Some(0),
481 name: Some("zero-2".to_string()),
482 interconnect_name: None,
483 ..Default::default()
484 },
485 icc::Node {
486 id: Some(1),
487 name: Some("one".to_string()),
488 interconnect_name: None,
489 ..Default::default()
490 },
491 ];
492 let edges = vec![icc::Edge {
493 src_node_id: Some(0),
494 dst_node_id: Some(1),
495 weight: Some(1),
496 ..Default::default()
497 }];
498 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
499 }
500
501 #[fuchsia::test]
502 fn test_node_graph_missing_duplicate_edge() {
503 let nodes = vec![
504 icc::Node {
505 id: Some(0),
506 name: Some("zero".to_string()),
507 interconnect_name: None,
508 ..Default::default()
509 },
510 icc::Node {
511 id: Some(1),
512 name: Some("one".to_string()),
513 interconnect_name: None,
514 ..Default::default()
515 },
516 ];
517 let edges = vec![
518 icc::Edge {
519 src_node_id: Some(0),
520 dst_node_id: Some(1),
521 weight: Some(1),
522 ..Default::default()
523 },
524 icc::Edge {
525 src_node_id: Some(0),
526 dst_node_id: Some(1),
527 weight: Some(4),
528 ..Default::default()
529 },
530 ];
531 assert_eq!(NodeGraph::new(nodes, edges), Err(Status::INVALID_ARGS));
532 }
533
534 #[fuchsia::test]
535 fn test_node_graph_complex() {
536 let nodes = vec![
537 icc::Node {
538 id: Some(0),
539 name: Some("zero".to_string()),
540 interconnect_name: None,
541 ..Default::default()
542 },
543 icc::Node {
544 id: Some(1),
545 name: Some("one".to_string()),
546 interconnect_name: None,
547 ..Default::default()
548 },
549 icc::Node {
550 id: Some(2),
551 name: Some("two".to_string()),
552 interconnect_name: None,
553 ..Default::default()
554 },
555 icc::Node {
556 id: Some(3),
557 name: Some("three".to_string()),
558 interconnect_name: None,
559 ..Default::default()
560 },
561 ];
562 let edges = vec![
563 icc::Edge {
564 src_node_id: Some(0),
565 dst_node_id: Some(1),
566 weight: Some(1),
567 ..Default::default()
568 },
569 icc::Edge {
570 src_node_id: Some(1),
571 dst_node_id: Some(2),
572 weight: Some(1),
573 ..Default::default()
574 },
575 icc::Edge {
576 src_node_id: Some(1),
577 dst_node_id: Some(3),
578 weight: Some(1),
579 ..Default::default()
580 },
581 icc::Edge {
582 src_node_id: Some(2),
583 dst_node_id: Some(1),
584 weight: Some(1),
585 ..Default::default()
586 },
587 ];
588 let graph = NodeGraph::new(nodes, edges).unwrap();
589 assert_eq!(
590 graph,
591 NodeGraph {
592 nodes: BTreeMap::from([
593 (
594 NodeId(0),
595 InterconnectNode {
596 name: "zero".to_string(),
597 id: NodeId(0),
598 incoming_edges: BTreeMap::new(),
599 path_bandwidth_requests: BTreeMap::new(),
600 initial_avg_bandwidth_bps: 0,
601 initial_peak_bandwidth_bps: 0,
602 }
603 ),
604 (
605 NodeId(1),
606 InterconnectNode {
607 name: "one".to_string(),
608 id: NodeId(1),
609 incoming_edges: BTreeMap::from([
610 (NodeId(0), IncomingEdge { weight: 1 }),
611 (NodeId(2), IncomingEdge { weight: 1 }),
612 ]),
613 path_bandwidth_requests: BTreeMap::new(),
614 initial_avg_bandwidth_bps: 0,
615 initial_peak_bandwidth_bps: 0,
616 }
617 ),
618 (
619 NodeId(2),
620 InterconnectNode {
621 name: "two".to_string(),
622 id: NodeId(2),
623 incoming_edges: BTreeMap::from([(
624 NodeId(1),
625 IncomingEdge { weight: 1 }
626 )]),
627 path_bandwidth_requests: BTreeMap::new(),
628 initial_avg_bandwidth_bps: 0,
629 initial_peak_bandwidth_bps: 0,
630 }
631 ),
632 (
633 NodeId(3),
634 InterconnectNode {
635 name: "three".to_string(),
636 id: NodeId(3),
637 incoming_edges: BTreeMap::from([(
638 NodeId(1),
639 IncomingEdge { weight: 1 }
640 )]),
641 path_bandwidth_requests: BTreeMap::new(),
642 initial_avg_bandwidth_bps: 0,
643 initial_peak_bandwidth_bps: 0,
644 }
645 ),
646 ]),
647 }
648 );
649 }
650
651 #[fuchsia::test]
652 fn test_find_full_path() {
653 let nodes = vec![
654 icc::Node {
655 id: Some(0),
656 name: Some("zero".to_string()),
657 interconnect_name: None,
658 ..Default::default()
659 },
660 icc::Node {
661 id: Some(1),
662 name: Some("one".to_string()),
663 interconnect_name: None,
664 ..Default::default()
665 },
666 icc::Node {
667 id: Some(2),
668 name: Some("two".to_string()),
669 interconnect_name: None,
670 ..Default::default()
671 },
672 icc::Node {
673 id: Some(3),
674 name: Some("three".to_string()),
675 interconnect_name: None,
676 ..Default::default()
677 },
678 ];
679 let edges = vec![
680 icc::Edge {
681 src_node_id: Some(0),
682 dst_node_id: Some(1),
683 weight: Some(1),
684 ..Default::default()
685 },
686 icc::Edge {
687 src_node_id: Some(1),
688 dst_node_id: Some(2),
689 weight: Some(1),
690 ..Default::default()
691 },
692 icc::Edge {
693 src_node_id: Some(1),
694 dst_node_id: Some(3),
695 weight: Some(1),
696 ..Default::default()
697 },
698 icc::Edge {
699 src_node_id: Some(2),
700 dst_node_id: Some(1),
701 weight: Some(1),
702 ..Default::default()
703 },
704 ];
705 let mut graph = NodeGraph::new(nodes, edges).unwrap();
706
707 static PATH_NAME: &str = "";
708
709 let path = graph.make_path(PathId(0), PATH_NAME, NodeId(0), NodeId(2)).unwrap();
710 assert_eq!(
711 path,
712 Path {
713 id: PathId(0),
714 name: PATH_NAME.to_string(),
715 nodes: vec![NodeId(0), NodeId(1), NodeId(2)]
716 }
717 );
718 assert_eq!(
719 graph.make_path(PathId(1), PATH_NAME, NodeId(0), NodeId(3)),
720 Ok(Path {
721 id: PathId(1),
722 name: PATH_NAME.to_string(),
723 nodes: vec![NodeId(0), NodeId(1), NodeId(3)],
724 })
725 );
726 assert_eq!(
727 graph.make_path(PathId(2), PATH_NAME, NodeId(2), NodeId(3)),
728 Ok(Path {
729 id: PathId(2),
730 name: PATH_NAME.to_string(),
731 nodes: vec![NodeId(2), NodeId(1), NodeId(3)]
732 })
733 );
734 assert_eq!(
735 graph.make_path(PathId(2), PATH_NAME, NodeId(2), NodeId(3)),
736 Err(Status::ALREADY_EXISTS)
737 );
738 assert_eq!(
739 graph.make_path(PathId(3), PATH_NAME, NodeId(1), NodeId(0)),
740 Err(Status::NOT_FOUND)
741 );
742 assert_eq!(
743 graph.make_path(PathId(4), PATH_NAME, NodeId(2), NodeId(0)),
744 Err(Status::NOT_FOUND)
745 );
746 assert_eq!(
747 graph.make_path(PathId(5), PATH_NAME, NodeId(3), NodeId(2)),
748 Err(Status::NOT_FOUND)
749 );
750
751 graph.update_path(&path, 100, 500);
752
753 assert_eq!(
754 graph.make_bandwidth_requests(&path),
755 vec![
756 icc::NodeBandwidth {
757 node_id: Some(0),
758 requests: Some(vec![
759 icc::BandwidthRequest {
760 average_bandwidth_bps: Some(100),
761 peak_bandwidth_bps: Some(500),
762 ..Default::default()
763 },
764 icc::BandwidthRequest {
765 average_bandwidth_bps: Some(0),
766 peak_bandwidth_bps: Some(0),
767 ..Default::default()
768 },
769 ]),
770 ..Default::default()
771 },
772 icc::NodeBandwidth {
773 node_id: Some(1),
774 requests: Some(vec![
775 icc::BandwidthRequest {
776 average_bandwidth_bps: Some(100),
777 peak_bandwidth_bps: Some(500),
778 ..Default::default()
779 },
780 icc::BandwidthRequest {
781 average_bandwidth_bps: Some(0),
782 peak_bandwidth_bps: Some(0),
783 ..Default::default()
784 },
785 icc::BandwidthRequest {
786 average_bandwidth_bps: Some(0),
787 peak_bandwidth_bps: Some(0),
788 ..Default::default()
789 },
790 ]),
791 ..Default::default()
792 },
793 icc::NodeBandwidth {
794 node_id: Some(2),
795 requests: Some(vec![
796 icc::BandwidthRequest {
797 average_bandwidth_bps: Some(100),
798 peak_bandwidth_bps: Some(500),
799 ..Default::default()
800 },
801 icc::BandwidthRequest {
802 average_bandwidth_bps: Some(0),
803 peak_bandwidth_bps: Some(0),
804 ..Default::default()
805 },
806 ]),
807 ..Default::default()
808 },
809 ]
810 );
811 }
812}