Comments (3)
Hi! Thanks for finding this issue and posting patches. Yes, please create two PRs, one for the test case and one for the fix. Then the CI tests should be run automatically.
from tinc.
Thanks again for the patches, they've been merged!
from tinc.
I have also created a fix for that. The repo seems not having been actively accepting PR recently, so I just post the patch here. @gsliepen let me know if you would like me to send a PR.
diff --git a/src/graph.c b/src/graph.c
index 5a7a16a7..5bec2c16 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -141,6 +141,7 @@ void sssp_bfs(void) {
myself->prevedge = NULL;
myself->via = myself;
myself->distance = 0;
+ myself->weighted_distance = 0;
list_insert_head(todo_list, myself);
/* Loop while todo_list is filled */
@@ -178,14 +179,15 @@ void sssp_bfs(void) {
if(e->to->status.visited
&& (!e->to->status.indirect || indirect)
- && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->weight)) {
+ && (e->to->distance != n->distance + 1 || e->to->weighted_distance <= n->weighted_distance + e->weight)) {
continue;
}
// 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->to->weighted_distance > n->weighted_distance + e->weight)) {
e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
+ e->to->weighted_distance = n->weighted_distance + e->weight;
}
e->to->status.visited = true;
diff --git a/src/node.h b/src/node.h
index 51322c25..7d5a0c8c 100644
--- a/src/node.h
+++ b/src/node.h
@@ -76,6 +76,7 @@ typedef struct node_t {
compression_level_t outcompression; /* Compression level, 0 = no compression */
int distance;
+ int weighted_distance;
struct node_t *nexthop; /* nearest node from us to him */
struct edge_t *prevedge; /* nearest node from him to us */
struct node_t *via; /* next hop for UDP packets */
diff --git a/test/unit/test_graph.c b/test/unit/test_graph.c
index e09f2fcb..e11c8bc7 100644
--- a/test/unit/test_graph.c
+++ b/test/unit/test_graph.c
@@ -26,6 +26,54 @@ static node_t *make_node(const char *name) {
return node;
}
+static void test_sssp_bfs_2(void **state) {
+ (void)state;
+
+ node_t *mars = make_node("mars");
+ node_t *saturn = make_node("saturn");
+ node_t *neptune = make_node("neptune");
+
+ // 1000 500
+ // myself ---------- mars ------------- neptune
+ // \ /
+ // ------- saturn --------------
+ // 50 501
+
+ // Upper route
+ connect_nodes(myself, mars, 1000);
+ connect_nodes(mars, neptune, 500);
+
+ // Lower route
+ connect_nodes(myself, saturn, 50);
+ connect_nodes(saturn, neptune, 501);
+
+ 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 void test_sssp_bfs(void **state) {
(void)state;
@@ -91,6 +139,7 @@ static int teardown(void **state) {
int main(void) {
const struct CMUnitTest tests[] = {
cmocka_unit_test_setup_teardown(test_sssp_bfs, setup, teardown),
+ cmocka_unit_test_setup_teardown(test_sssp_bfs_2, setup, teardown)
};
return cmocka_run_group_tests(tests, NULL, NULL);
}
from tinc.
Related Issues (20)
- Got bad ID from <unknown> HOT 2
- Error joining to Linux node from Windows
- this page is broken. https://www.tinc-vpn.org/examples/ipv6-network/ HOT 1
- Relaying doesn't work when TCPOnly is enabled
- Performance improvements via TSO/GRO and UDP_SEGMENT HOT 4
- Please add time when you output the log. There are too many retry link logs but do not know the time. HOT 1
- Peer has an invalid key! on tinc join
- DNS failure and delays break connections HOT 1
- Is the project still being maintained? HOT 20
- Which routing protocol does Tinc use in router mode? HOT 5
- zip build HOT 3
- Invitation-generated tinc-up tries to set address/route before bringing up interface
- Handling 100+ groups? (+1 master) HOT 1
- server can not exchange the server‘s host HOT 1
- Peer tries to roll back protocol version to 17.0, Error while processing ID
- have the ability to compile with mbed-tls
- Question: Is there a limit/impact of huge amount of Subnet announcement?
- Compile with miniupnpc 2.2.8 fails
- systemd tinc.service gone after installing deb from Release section.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from tinc.