From: Kirill Isakov <bootctl@gmail.com>
Date: Mon, 23 May 2022 09:48:50 +0000 (+0600)
Subject: Fix weight comparison in edge BFS
X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=commitdiff_plain;h=72091d5c770856870bb8cd51bcc5641078c7562c

Fix weight comparison in edge BFS

… and add a test to reproduce the issue.

Noticed and reported by Jingrong Chen (@crazyboycjr)
https://github.com/gsliepen/tinc/issues/393
---

diff --git a/src/graph.c b/src/graph.c
index da649091..c100a933 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -115,11 +115,13 @@ static void mst_kruskal(void) {
 	}
 }
 
+// Not putting it into header, the outside world doesn't need to know about it.
+extern void sssp_bfs(void);
+
 /* Implementation of a simple breadth-first search algorithm.
    Running time: O(E)
 */
-
-static void sssp_bfs(void) {
+void sssp_bfs(void) {
 	list_t *todo_list = list_alloc(NULL);
 
 	/* Clear visited status on nodes */
@@ -181,7 +183,7 @@ static void sssp_bfs(void) {
 
 			// Only update nexthop if it doesn't increase the path length
 
-			if(!e->to->status.visited || (e->to->distance == n->distance + 1 && e->weight >= e->to->prevedge->weight)) {
+			if(!e->to->status.visited || (e->to->distance == n->distance + 1 && e->weight < e->to->prevedge->weight)) {
 				e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 			}
 
diff --git a/test/unit/meson.build b/test/unit/meson.build
index 8633c186..52005987 100644
--- a/test/unit/meson.build
+++ b/test/unit/meson.build
@@ -31,6 +31,9 @@ tests = {
     'code': 'test_random_noinit.c',
     'fail': true,
   },
+  'graph': {
+    'code': 'test_graph.c',
+  },
   'netutl': {
     'code': 'test_netutl.c',
   },
diff --git a/test/unit/test_graph.c b/test/unit/test_graph.c
new file mode 100644
index 00000000..5d72104b
--- /dev/null
+++ b/test/unit/test_graph.c
@@ -0,0 +1,98 @@
+#include "unittest.h"
+#include "../../src/connection.h"
+#include "../../src/node.h"
+#include "../../src/xalloc.h"
+
+extern void sssp_bfs(void);
+
+static void connect_nodes(node_t *from, node_t *to, int weight) {
+	edge_t *direct = new_edge();
+	direct->from = from;
+	direct->to = to;
+	direct->weight = weight;
+	edge_add(direct);
+
+	edge_t *reverse = new_edge();
+	reverse->from = to;
+	reverse->to = from;
+	reverse->weight = weight;
+	edge_add(reverse);
+}
+
+static node_t *make_node(const char *name) {
+	node_t *node = new_node();
+	node->name = xstrdup(name);
+	node->status.reachable = true;
+	node_add(node);
+	return node;
+}
+
+static void test_sssp_bfs(void **state) {
+	(void)state;
+
+	node_t *mars = make_node("mars");
+	node_t *saturn = make_node("saturn");
+	node_t *neptune = make_node("neptune");
+
+	//          50            1000
+	// myself ------ mars ------------- neptune
+	//      \                             /
+	//       ----------------- saturn ----
+	//              500                10
+
+	// Upper route
+	connect_nodes(myself, mars, 50);
+	connect_nodes(mars, neptune, 1000);
+
+	// Lower route
+	connect_nodes(myself, saturn, 500);
+	connect_nodes(saturn, neptune, 10);
+
+	sssp_bfs();
+
+	assert_true(mars->status.visited);
+	assert_true(saturn->status.visited);
+	assert_true(neptune->status.visited);
+
+	assert_false(mars->status.indirect);
+	assert_false(saturn->status.indirect);
+	assert_false(neptune->status.indirect);
+
+	assert_int_equal(1, mars->distance);
+	assert_int_equal(1, saturn->distance);
+	assert_int_equal(2, neptune->distance);
+
+	assert_ptr_equal(mars, mars->nexthop);
+	assert_ptr_equal(saturn, saturn->nexthop);
+	assert_ptr_equal(saturn, neptune->nexthop);
+
+	assert_ptr_equal(lookup_edge(myself, mars), mars->prevedge);
+	assert_ptr_equal(lookup_edge(myself, saturn), saturn->prevedge);
+	assert_ptr_equal(lookup_edge(saturn, neptune), neptune->prevedge);
+
+	assert_ptr_equal(mars, mars->via);
+	assert_ptr_equal(saturn, saturn->via);
+	assert_ptr_equal(neptune, neptune->via);
+}
+
+static int setup(void **state) {
+	(void)state;
+	myself = new_node();
+	myself->name = xstrdup("myself");
+	return 0;
+}
+
+static int teardown(void **state) {
+	(void)state;
+	free_node(myself);
+	exit_nodes();
+	exit_edges();
+	return 0;
+}
+
+int main(void) {
+	const struct CMUnitTest tests[] = {
+		cmocka_unit_test_setup_teardown(test_sssp_bfs, setup, teardown),
+	};
+	return cmocka_run_group_tests(tests, NULL, NULL);
+}