23245950079

Committed 18 Mar 2026 01:01PM UTC coverage: 75.924% (-3.4%) from 79.315%

Build # 23245950079

Build Type

Pull #15054

github

Committed by

web-flow

Commit Message

Merge e08fe523b into 6587e363a

Pull Request Pull Request #15054: Flowbit ordering cyclic/v8

Coverage Stats

316 of 354 new or added lines in 2 files covered. (89.27%)

11404 existing lines in 477 files now uncovered.

253672 of 334114 relevant lines covered (75.92%)

3702735.03 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.64

/rust/src/utils/flowbits_resolver.rs

/* Copyright (C) 2025 Open Information Security Foundation
 *
 * You can copy, redistribute or modify this Program under the terms of
 * the GNU General Public License version 2 as published by the Free
 * Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * version 2 along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

// Author: Shivani Bhardwaj <shivani@oisf.net>

use itertools::iproduct;
use petgraph::algo::{is_cyclic_directed, tarjan_scc};
use petgraph::graph::{GraphError, NodeIndex};
use petgraph::stable_graph::StableDiGraph;
use petgraph::visit::Bfs;
use petgraph::Direction;
use std::collections::HashMap;
use std::os::raw::c_void;


/// Special Graph Node storing flowbit or signature
#[derive(Debug, Copy, Clone)]
struct SCGNode {
    iid: u32,        /* signature iid or flowbits iid (in VarNameStore) */
    ntype: bool,     /* node type: Signature (0), Flowbit (1) */
    nidx: NodeIndex, /* Graph's internal node index */
}

/// Function to create an empty directed Graph
#[no_mangle]
pub unsafe extern "C" fn SCCreateDirectedGraph() -> *mut c_void {
    // StableDiGraph is the ideal choice here for there is removal of
    // nodes in the line later and this type of graph guarantees to
    // not re-use any existing node indices
    let graph: StableDiGraph<SCGNode, u8> = StableDiGraph::new();
    let boxed_graph = Box::new(graph);

    /* Make an opaque pointer for C as nothing is changed there */
    return Box::into_raw(boxed_graph) as *mut c_void;
}

/// Drop the directed Graph. Called from C.
#[no_mangle]
pub unsafe extern "C" fn SCFreeDirectedGraph(graph: *mut c_void) {
    let _ = Box::from_raw(graph as *mut StableDiGraph<SCGNode, u8>);
}

/// Function to get or create a node and add an appropriate directed
/// edge based on its type
#[no_mangle]
pub unsafe extern "C" fn SCCreateNodeEdgeDirectedGraph(
    graph: *mut c_void, iid: u32, ntype: bool, write_cmd: bool, cmd: u8, sig_gid: u32,
) -> i64 {
    let g = &mut *(graph as *mut StableDiGraph<SCGNode, u8>);

    let node_idx;
    if let Some(nidx) = get_or_create_node(g, iid, ntype) {
        node_idx = nidx;
    } else {
        SCLogError!("Error adding node; Graph is at full capacity");
        return -2;
    }

    let sidx = NodeIndex::from(sig_gid);

    if !ntype {
        SCLogNotice!("Node type is not flowbit");
        return node_idx.index() as i64;
    }

    /* flowbit type node */
    if write_cmd {
        /* WRITE command */
        match g.try_update_edge(sidx, node_idx, cmd) {
            /* edge from signature to flowbit */
            Ok(_) => {
                SCLogNotice!("Created an edge from {:?} -> {:?}", sidx, node_idx);
            }
            Err(GraphError::EdgeIxLimit) => {
                SCLogError!("Error adding edge; Graph is at full capacity");
                return -2;
            }
            Err(GraphError::NodeOutBounds) => {
                SCLogError!("Error adding edge; node does not exist");
                return -2;
            }
            Err(_) => {
                SCLogError!("Error adding edge to the Graph");
                return -2;
            }
        }
    } else {
        match g.try_update_edge(node_idx, sidx, 3 /* READ command does not affect the output */) {
            /* edge from flowbit to signature */
            Ok(_) => {
                SCLogNotice!("Created an edge from {:?} -> {:?}", sidx, node_idx);
            }
            Err(GraphError::EdgeIxLimit) => {
                SCLogError!("Error adding edge; Graph is at full capacity");
                return -2;
            }
            Err(GraphError::NodeOutBounds) => {
                SCLogError!("Error adding edge; node does not exist");
                return -2;
            }
            Err(_) => {
                SCLogError!("Error adding edge to the Graph");
                return -2;
            }
        }
    }

    SCLogNotice!("node count: {:?}", g.node_count());
    node_idx.index() as i64
}

/// Recursive fn to find a valid cycle and update the graph
/// STODO what is the time complexity of this entire algorithm now with so
/// much of fluff?
fn check_cycle_update_graph(graph: &mut StableDiGraph<SCGNode, u8>) -> i8
{
    /* Check graph for any cycles */
    if !is_cyclic_directed(&graph.clone()) { /* O(V+E) */
        SCLogNotice!("no cycles");
        return 0;
    }

    SCLogNotice!("Found a cycle. Checking if its valid..");
    let sccs = tarjan_scc(&*graph); /* O(V+E) */
    // find all strongly connected components of the graph
    for scc in sccs.iter().filter(|scc| scc.len() > 1) {
        SCLogNotice!("Cycle nodes: {:?}", scc);
        let mut prev_wt = 0;
        let mut prev_e = Default::default();
        for np in scc.windows(2) {
            if let [a, b] = np {
                if let Some(e) = graph.find_edge(*a, *b) {
                    if let Some(wt) = graph.edge_weight(e) {
                        if prev_wt == 0 {
                            prev_wt = *wt;
                            prev_e = e;
                        } else if prev_wt != *wt {
                            // Remove the edge with higher weight (so lower priority)
                            if prev_wt > *wt {
                                graph.remove_edge(prev_e); /* O(e'): e' => size of edge lists of the affected vertices */
                            } else {
                                graph.remove_edge(e);
                            }
                            // Check for multiple cycles
                            check_cycle_update_graph(graph);
                        }
                    }
                }
            }
        }
    }
    return -1;
}


/// Wrapper function to resolve flowbit dependencies
#[no_mangle]
pub unsafe extern "C" fn SCResolveFlowbitDependencies(
    graph: *mut c_void, sorted_sid_list: *mut u32, sorted_sid_list_len: u32,
) -> i8 {
    let g = &mut *(graph as *mut StableDiGraph<SCGNode, u8>);

    debug_validate_bug_on!(g.node_count() == 0);

    /* Create a signature only directed graph */
    normalize_graph(g);

    let sorted_sid_list =
        std::slice::from_raw_parts_mut(&mut *sorted_sid_list, sorted_sid_list_len as usize);

    /* No need for all the extra work if there's just one node */
    if g.node_count() == 1 {
        debug_validate_bug_on!(sorted_sid_list_len != 1);
        sorted_sid_list[0] = g[NodeIndex::from(0)].iid;
        /* Given that first a signature is added, it is guaranteed
         * that 0th node must always be a signature node */
        debug_validate_bug_on!(g[NodeIndex::from(0)].ntype);
        return 0;
    }

    if check_cycle_update_graph(g) == -1 {
        // Couldn't do anything to fix the graph, it's a legit cycle
        return -1;
    }

    /* At this point, it must be a DAG, so perform a BFS on the tree to find
     * out the correct order of signatures */
    return bfs_tree_dag(g, sorted_sid_list);
}

fn get_or_create_node(
    g: &mut StableDiGraph<SCGNode, u8>, iid: u32, ntype: bool,
) -> Option<NodeIndex> {
    for node in g.node_weights() {
        if node.iid == iid && node.ntype == ntype {
            return Some(node.nidx);
        }
    }
    let nd = SCGNode {
        iid,
        ntype,
        nidx: NodeIndex::from(u32::MAX),
    };
    if let Ok(idx) = g.try_add_node(nd) { /* O(1) */
        g[idx].nidx = idx;
        SCLogNotice!("Created node: {:?}", g[idx]);
        return Some(idx);
    }

    None
}

/// Function to create a dependency graph among signatures
/// A map of all the edges is created and then flowbit nodes
/// are eliminated while creating a direct directed edge between
/// the signature nodes connected by the flowbit node
fn normalize_graph(g: &mut StableDiGraph<SCGNode, u8>) {
    let mut map_new_edges: Vec<(NodeIndex, Vec<(NodeIndex, NodeIndex)>)> = Vec::new();
    let mut fb_nodes_list: Vec<SCGNode> = Vec::new();

    for nd in g.node_weights() {
        if nd.ntype {
            let in_edges: Vec<NodeIndex> =
                g.neighbors_directed(nd.nidx, Direction::Incoming).collect();

            let out_edges: Vec<NodeIndex> =
                g.neighbors_directed(nd.nidx, Direction::Outgoing).collect();

            let map_edges_curnode: Vec<(NodeIndex, NodeIndex)> =
                iproduct!(in_edges, out_edges).collect();
            map_new_edges.push((nd.nidx, map_edges_curnode));
            fb_nodes_list.push(*nd);
        }
    }

    for (fb_nd, sig_nds) in map_new_edges {
        SCLogNotice!("map_new_edges -- from: {:?}; to: {:?}", fb_nd, sig_nds);
        for nd in sig_nds {
            let mut nweight = 0;
            if let Some(ei) = g.find_edge(fb_nd, nd.0) {
                if let Some(w) = g.edge_weight(ei) {
                    nweight |= 1 << w;
                }
            }
            if let Some(ei) = g.find_edge(fb_nd, nd.1) {
                if let Some(w) = g.edge_weight(ei) {
                    nweight |= 1 << w;
                }
            }
            debug_validate_bug_on!(nweight == 0);
            g.add_edge(nd.0, nd.1, nweight); /* O(1) */
        }
    }

    for node in fb_nodes_list {
        SCLogNotice!("Removing node {:?}", node);
        /* Only flowbit nodes must be removed from the graph */
        debug_validate_bug_on!(!node.ntype);
        g.remove_node(node.nidx); /* O(e'): e' => number of edges connected to the node */
    }
}

fn calculate_in_degree_nodes(
    g: &mut StableDiGraph<SCGNode, u8>, in_degrees: &mut HashMap<NodeIndex, usize>,
) {
    for node_idx in g.node_indices() {
        let in_degree = g.neighbors_directed(node_idx, Direction::Incoming).count();
        SCLogNotice!("in_degree for node {:?}: {:?}", g[node_idx], in_degree);
        in_degrees.insert(node_idx, in_degree);
    }
}

/// Perform a BFS (Breadth First Search) of the DAG (Directed Acyclic Graph)
fn bfs_tree_dag(g: &mut StableDiGraph<SCGNode, u8>, sorted_sid_list: &mut [u32]) -> i8 {
    let mut in_degrees: HashMap<NodeIndex, usize> = HashMap::new();
    calculate_in_degree_nodes(g, &mut in_degrees);

    let nidx;
    if let Some(idx) = get_or_create_node(g, u32::MAX, false) {
        nidx = idx;
    } else {
        SCLogError!("Error adding node; Graph is at full capacity");
        return -1;
    }

    /* Connect all the loner nodes to the dummy node so as to create a discoverable
     * path and a connected tree to perform a BFS */
    for (node_idx, in_degree) in in_degrees {
        if in_degree == 0 {
            SCLogNotice!("added edge from {:?} -> {:?}", nidx, node_idx);
            g.add_edge(nidx, node_idx, 1 << 7);
        }
    }

    let mut bfs = Bfs::new(&*g, nidx);
    let mut i = 0;

    SCLogNotice!("BFS of the graph:");
    while let Some(idx) = bfs.next(&*g) {
        /* Don't add dummy node to the graph */
        if idx != nidx {
            SCLogNotice!("[{:?}]: {:?}", i, g[idx]);
            sorted_sid_list[i] = g[idx].iid;
            i += 1;
        }
    }
    0
}

1	/* Copyright (C) 2025 Open Information Security Foundation
2	*
3	* You can copy, redistribute or modify this Program under the terms of
4	* the GNU General Public License version 2 as published by the Free
5	* Software Foundation.
6	*
7	* This program is distributed in the hope that it will be useful,
8	* but WITHOUT ANY WARRANTY; without even the implied warranty of
9	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10	* GNU General Public License for more details.
11	*
12	* You should have received a copy of the GNU General Public License
13	* version 2 along with this program; if not, write to the Free Software
14	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15	* 02110-1301, USA.
16	*/
17
18	// Author: Shivani Bhardwaj <shivani@oisf.net>
19
20	use itertools::iproduct;
21	use petgraph::algo::{is_cyclic_directed, tarjan_scc};
22	use petgraph::graph::{GraphError, NodeIndex};
23	use petgraph::stable_graph::StableDiGraph;
24	use petgraph::visit::Bfs;
25	use petgraph::Direction;
26	use std::collections::HashMap;
27	use std::os::raw::c_void;
28
29
30	/// Special Graph Node storing flowbit or signature
31	#[derive(Debug, Copy, Clone)]
32	struct SCGNode {
33	iid: u32, /* signature iid or flowbits iid (in VarNameStore) */
34	ntype: bool, /* node type: Signature (0), Flowbit (1) */
35	nidx: NodeIndex, /* Graph's internal node index */
36	}
37
38	/// Function to create an empty directed Graph
39	#[no_mangle]
40	pub unsafe extern "C" fn SCCreateDirectedGraph() -> *mut c_void {	29✔
41	// StableDiGraph is the ideal choice here for there is removal of	29✔
42	// nodes in the line later and this type of graph guarantees to	29✔
43	// not re-use any existing node indices	29✔
44	let graph: StableDiGraph<SCGNode, u8> = StableDiGraph::new();	29✔
45	let boxed_graph = Box::new(graph);	29✔
46		29✔
47	/* Make an opaque pointer for C as nothing is changed there */	29✔
48	return Box::into_raw(boxed_graph) as *mut c_void;	29✔
49	}	29✔
50
51	/// Drop the directed Graph. Called from C.
52	#[no_mangle]
53	pub unsafe extern "C" fn SCFreeDirectedGraph(graph: *mut c_void) {	29✔
54	let _ = Box::from_raw(graph as *mut StableDiGraph<SCGNode, u8>);	29✔
55	}	29✔
56
57	/// Function to get or create a node and add an appropriate directed
58	/// edge based on its type
59	#[no_mangle]
60	pub unsafe extern "C" fn SCCreateNodeEdgeDirectedGraph(	840✔
61	graph: *mut c_void, iid: u32, ntype: bool, write_cmd: bool, cmd: u8, sig_gid: u32,	840✔
62	) -> i64 {	840✔
63	let g = &mut (graph as mut StableDiGraph<SCGNode, u8>);	840✔
64
65	let node_idx;
66	if let Some(nidx) = get_or_create_node(g, iid, ntype) {	840✔
67	node_idx = nidx;	840✔
68	} else {	840✔
NEW 69	SCLogError!("Error adding node; Graph is at full capacity");	×
NEW 70	return -2;	×
71	}
72
73	let sidx = NodeIndex::from(sig_gid);	840✔
74		840✔
75	if !ntype {	840✔
76	SCLogNotice!("Node type is not flowbit");	257✔
77	return node_idx.index() as i64;	257✔
78	}	583✔
79		583✔
80	/* flowbit type node */	583✔
81	if write_cmd {	583✔
82	/* WRITE command */
83	match g.try_update_edge(sidx, node_idx, cmd) {	304✔
84	/* edge from signature to flowbit */
85	Ok(_) => {
86	SCLogNotice!("Created an edge from {:?} -> {:?}", sidx, node_idx);	304✔
87	}
88	Err(GraphError::EdgeIxLimit) => {
NEW 89	SCLogError!("Error adding edge; Graph is at full capacity");	×
NEW 90	return -2;	×
91	}
92	Err(GraphError::NodeOutBounds) => {
NEW 93	SCLogError!("Error adding edge; node does not exist");	×
NEW 94	return -2;	×
95	}
96	Err(_) => {
NEW 97	SCLogError!("Error adding edge to the Graph");	×
NEW 98	return -2;	×
99	}
100	}
101	} else {
102	match g.try_update_edge(node_idx, sidx, 3 /* READ command does not affect the output */) {	279✔
103	/* edge from flowbit to signature */
104	Ok(_) => {
105	SCLogNotice!("Created an edge from {:?} -> {:?}", sidx, node_idx);	279✔
106	}
107	Err(GraphError::EdgeIxLimit) => {
NEW 108	SCLogError!("Error adding edge; Graph is at full capacity");	×
NEW 109	return -2;	×
110	}
111	Err(GraphError::NodeOutBounds) => {
NEW 112	SCLogError!("Error adding edge; node does not exist");	×
NEW 113	return -2;	×
114	}
115	Err(_) => {
NEW 116	SCLogError!("Error adding edge to the Graph");	×
NEW 117	return -2;	×
118	}
119	}
120	}
121
122	SCLogNotice!("node count: {:?}", g.node_count());	583✔
123	node_idx.index() as i64	583✔
124	}	840✔
125
126	/// Recursive fn to find a valid cycle and update the graph
127	/// STODO what is the time complexity of this entire algorithm now with so
128	/// much of fluff?
129	fn check_cycle_update_graph(graph: &mut StableDiGraph<SCGNode, u8>) -> i8	6✔
130	{	6✔
131	/* Check graph for any cycles */	6✔
132	if !is_cyclic_directed(&graph.clone()) { /* O(V+E) */	6✔
133	SCLogNotice!("no cycles");	3✔
134	return 0;	3✔
135	}	3✔
136		3✔
137	SCLogNotice!("Found a cycle. Checking if its valid..");	3✔
138	let sccs = tarjan_scc(&graph); / O(V+E) */	3✔
139	// find all strongly connected components of the graph
140	for scc in sccs.iter().filter(\|scc\| scc.len() > 1) {	169✔
141	SCLogNotice!("Cycle nodes: {:?}", scc);	23✔
142	let mut prev_wt = 0;	23✔
143	let mut prev_e = Default::default();	23✔
144	for np in scc.windows(2) {	59✔
145	if let [a, b] = np {	59✔
146	if let Some(e) = graph.find_edge(a, b) {	59✔
147	if let Some(wt) = graph.edge_weight(e) {	59✔
148	if prev_wt == 0 {	59✔
149	prev_wt = *wt;	23✔
150	prev_e = e;	23✔
151	} else if prev_wt != *wt {	36✔
152	// Remove the edge with higher weight (so lower priority)
NEW 153	if prev_wt > *wt {	×
NEW 154	graph.remove_edge(prev_e); /* O(e'): e' => size of edge lists of the affected vertices */	×
NEW 155	} else {	×
NEW 156	graph.remove_edge(e);	×
NEW 157	}	×
158	// Check for multiple cycles
NEW 159	check_cycle_update_graph(graph);	×
160	}	36✔
NEW 161	}	×
NEW 162	}	×
NEW 163	}	×
164	}
165	}
166	return -1;	3✔
167	}	6✔
168
169
170	/// Wrapper function to resolve flowbit dependencies
171	#[no_mangle]
172	pub unsafe extern "C" fn SCResolveFlowbitDependencies(	29✔
173	graph: mut c_void, sorted_sid_list: mut u32, sorted_sid_list_len: u32,	29✔
174	) -> i8 {	29✔
175	let g = &mut (graph as mut StableDiGraph<SCGNode, u8>);	29✔
176		29✔
177	debug_validate_bug_on!(g.node_count() == 0);	29✔
178		29✔
179	/* Create a signature only directed graph */	29✔
180	normalize_graph(g);	29✔
181		29✔
182	let sorted_sid_list =	29✔
183	std::slice::from_raw_parts_mut(&mut *sorted_sid_list, sorted_sid_list_len as usize);	29✔
184		29✔
185	/* No need for all the extra work if there's just one node */	29✔
186	if g.node_count() == 1 {	29✔
187	debug_validate_bug_on!(sorted_sid_list_len != 1);
188	sorted_sid_list[0] = g[NodeIndex::from(0)].iid;	23✔
189	/* Given that first a signature is added, it is guaranteed	23✔
190	* that 0th node must always be a signature node */	23✔
191	debug_validate_bug_on!(g[NodeIndex::from(0)].ntype);	23✔
192	return 0;	23✔
193	}	6✔
194		6✔
195	if check_cycle_update_graph(g) == -1 {	6✔
196	// Couldn't do anything to fix the graph, it's a legit cycle
197	return -1;	3✔
198	}	3✔
199		3✔
200	/* At this point, it must be a DAG, so perform a BFS on the tree to find	3✔
201	* out the correct order of signatures */	3✔
202	return bfs_tree_dag(g, sorted_sid_list);	3✔
203	}	29✔
204
205	fn get_or_create_node(	843✔
206	g: &mut StableDiGraph<SCGNode, u8>, iid: u32, ntype: bool,	843✔
207	) -> Option<NodeIndex> {	843✔
208	for node in g.node_weights() {	64,978✔
209	if node.iid == iid && node.ntype == ntype {	64,978✔
210	return Some(node.nidx);	393✔
211	}	64,585✔
212	}
213	let nd = SCGNode {	450✔
214	iid,	450✔
215	ntype,	450✔
216	nidx: NodeIndex::from(u32::MAX),	450✔
217	};	450✔
218	if let Ok(idx) = g.try_add_node(nd) { /* O(1) */	450✔
219	g[idx].nidx = idx;	450✔
220	SCLogNotice!("Created node: {:?}", g[idx]);	450✔
221	return Some(idx);	450✔
NEW 222	}	×
NEW 223		×
NEW 224	None	×
225	}	843✔
226
227	/// Function to create a dependency graph among signatures
228	/// A map of all the edges is created and then flowbit nodes
229	/// are eliminated while creating a direct directed edge between
230	/// the signature nodes connected by the flowbit node
231	fn normalize_graph(g: &mut StableDiGraph<SCGNode, u8>) {	29✔
232	let mut map_new_edges: Vec<(NodeIndex, Vec<(NodeIndex, NodeIndex)>)> = Vec::new();	29✔
233	let mut fb_nodes_list: Vec<SCGNode> = Vec::new();	29✔
234
235	for nd in g.node_weights() {	447✔
236	if nd.ntype {	447✔
237	let in_edges: Vec<NodeIndex> =	190✔
238	g.neighbors_directed(nd.nidx, Direction::Incoming).collect();	190✔
239		190✔
240	let out_edges: Vec<NodeIndex> =	190✔
241	g.neighbors_directed(nd.nidx, Direction::Outgoing).collect();	190✔
242		190✔
243	let map_edges_curnode: Vec<(NodeIndex, NodeIndex)> =	190✔
244	iproduct!(in_edges, out_edges).collect();	190✔
245	map_new_edges.push((nd.nidx, map_edges_curnode));	190✔
246	fb_nodes_list.push(*nd);	190✔
247	}	261✔
248	}
249
250	for (fb_nd, sig_nds) in map_new_edges {	219✔
251	SCLogNotice!("map_new_edges -- from: {:?}; to: {:?}", fb_nd, sig_nds);	190✔
252	for nd in sig_nds {	1,155✔
253	let mut nweight = 0;	965✔
254	if let Some(ei) = g.find_edge(fb_nd, nd.0) {	965✔
255	if let Some(w) = g.edge_weight(ei) {	688✔
256	nweight \|= 1 << w;	688✔
257	}	688✔
258	}	277✔
259	if let Some(ei) = g.find_edge(fb_nd, nd.1) {	965✔
260	if let Some(w) = g.edge_weight(ei) {	965✔
261	nweight \|= 1 << w;	965✔
262	}	965✔
NEW 263	}	×
264	debug_validate_bug_on!(nweight == 0);
265	g.add_edge(nd.0, nd.1, nweight); /* O(1) */	965✔
266	}
267	}
268
269	for node in fb_nodes_list {	219✔
270	SCLogNotice!("Removing node {:?}", node);	190✔
271	/* Only flowbit nodes must be removed from the graph */
272	debug_validate_bug_on!(!node.ntype);
273	g.remove_node(node.nidx); /* O(e'): e' => number of edges connected to the node */	190✔
274	}
275	}	29✔
276
277	fn calculate_in_degree_nodes(	3✔
278	g: &mut StableDiGraph<SCGNode, u8>, in_degrees: &mut HashMap<NodeIndex, usize>,	3✔
279	) {	3✔
280	for node_idx in g.node_indices() {	6✔
281	let in_degree = g.neighbors_directed(node_idx, Direction::Incoming).count();	6✔
282	SCLogNotice!("in_degree for node {:?}: {:?}", g[node_idx], in_degree);	6✔
283	in_degrees.insert(node_idx, in_degree);	6✔
284	}
285	}	3✔
286
287	/// Perform a BFS (Breadth First Search) of the DAG (Directed Acyclic Graph)
288	fn bfs_tree_dag(g: &mut StableDiGraph<SCGNode, u8>, sorted_sid_list: &mut [u32]) -> i8 {	3✔
289	let mut in_degrees: HashMap<NodeIndex, usize> = HashMap::new();	3✔
290	calculate_in_degree_nodes(g, &mut in_degrees);	3✔
291
292	let nidx;
293	if let Some(idx) = get_or_create_node(g, u32::MAX, false) {	3✔
294	nidx = idx;	3✔
295	} else {	3✔
NEW 296	SCLogError!("Error adding node; Graph is at full capacity");	×
NEW 297	return -1;	×
298	}
299
300	/* Connect all the loner nodes to the dummy node so as to create a discoverable
301	* path and a connected tree to perform a BFS */
302	for (node_idx, in_degree) in in_degrees {	9✔
303	if in_degree == 0 {	6✔
304	SCLogNotice!("added edge from {:?} -> {:?}", nidx, node_idx);	5✔
305	g.add_edge(nidx, node_idx, 1 << 7);	5✔
306	}	1✔
307	}
308
309	let mut bfs = Bfs::new(&*g, nidx);	3✔
310	let mut i = 0;	3✔
311		3✔
312	SCLogNotice!("BFS of the graph:");	3✔
313	while let Some(idx) = bfs.next(&*g) {	12✔
314	/* Don't add dummy node to the graph */
315	if idx != nidx {	9✔
316	SCLogNotice!("[{:?}]: {:?}", i, g[idx]);	6✔
317	sorted_sid_list[i] = g[idx].iid;	6✔
318	i += 1;	6✔
319	}	3✔
320	}
321	0	3✔
322	}	3✔

OISF / suricata / 23245950079

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous