From bc33a073d82cd4b5e75d00e379ddfeeaa6ade962 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Tue, 6 May 2014 12:58:25 +0200 Subject: [PATCH] Nexthop calculation should always use the shortest path. When tinc runs the graph algorithms and updates the nexthop and via pointers, it uses a breadth-first search, but it can sometimes revisit nodes that have already been visited if the previous path is marked as being indirect, and there is a longer path that is "direct". The via pointer should be updated in this case, because this points to the closest hop to the destination that can be reached directly. However, the nexthop pointer should not be updated. This fixes a bug where there could potentially be a routing loop if a node in the graph has an edge with the indirect flag set, and some other edge without that flag, the indirect edge is part of the minimum spanning tree, and a broadcast packet is being sent. --- src/graph.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/src/graph.c b/src/graph.c index 396e35a3..8f20ec7d 100644 --- a/src/graph.c +++ b/src/graph.c @@ -176,9 +176,13 @@ static void sssp_bfs(void) { && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->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)) + e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; + e->to->status.visited = true; e->to->status.indirect = indirect; - e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; e->to->prevedge = e; e->to->via = indirect ? n->via : e->to; e->to->options = e->options; -- 2.20.1