X-Git-Url: https://tinc-vpn.org/git/browse?a=blobdiff_plain;f=src%2Fgraph.c;h=3dd2ff1897a9106ba2dea4633ff767613473072a;hb=914d1be411229c28e6e8e4a0df99afa076a8b448;hp=1f1fdb3d54c50050530afd5034a2bb75930a3855;hpb=5cbef906209eb5005f821af8f55a6f5d7e7d060c;p=tinc diff --git a/src/graph.c b/src/graph.c index 1f1fdb3d..3dd2ff18 100644 --- a/src/graph.c +++ b/src/graph.c @@ -45,20 +45,16 @@ #include "system.h" #include "connection.h" -#include "device.h" #include "edge.h" #include "graph.h" #include "list.h" #include "logger.h" -#include "names.h" #include "netutl.h" #include "node.h" #include "protocol.h" #include "script.h" #include "subnet.h" -#include "utils.h" #include "xalloc.h" -#include "graph.h" /* Implementation of Kruskal's algorithm. Running time: O(EN) @@ -68,19 +64,21 @@ static void mst_kruskal(void) { /* Clear MST status on connections */ - for list_each(connection_t, c, connection_list) + for list_each(connection_t, c, &connection_list) { c->status.mst = false; + } logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Running Kruskal's algorithm:"); /* Clear visited status on nodes */ - for splay_each(node_t, n, node_tree) + for splay_each(node_t, n, &node_tree) { n->status.visited = false; + } /* Starting point */ - for splay_each(edge_t, e, edge_weight_tree) { + for splay_each(edge_t, e, &edge_weight_tree) { if(e->from->status.reachable) { e->from->status.visited = true; break; @@ -91,7 +89,7 @@ static void mst_kruskal(void) { bool skipped = false; - for splay_each(edge_t, e, edge_weight_tree) { + for splay_each(edge_t, e, &edge_weight_tree) { if(!e->reverse || (e->from->status.visited == e->to->status.visited)) { skipped = true; continue; @@ -100,17 +98,19 @@ static void mst_kruskal(void) { e->from->status.visited = true; e->to->status.visited = true; - if(e->connection) + if(e->connection) { e->connection->status.mst = true; + } - if(e->reverse->connection) + if(e->reverse->connection) { e->reverse->connection->status.mst = true; + } logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight); if(skipped) { skipped = false; - next = edge_weight_tree->head; + next = edge_weight_tree.head; } } } @@ -124,7 +124,7 @@ static void sssp_bfs(void) { /* Clear visited status on nodes */ - for splay_each(node_t, n, node_tree) { + for splay_each(node_t, n, &node_tree) { n->status.visited = false; n->status.indirect = true; n->distance = -1; @@ -145,20 +145,22 @@ static void sssp_bfs(void) { for list_each(node_t, n, todo_list) { /* "n" is the node from which we start */ logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Examining edges from %s", n->name); - if(n->distance < 0) + if(n->distance < 0) { abort(); + } - for splay_each(edge_t, e, n->edge_tree) { /* "e" is the edge connected to "from" */ - if(!e->reverse || e->to == myself) + for splay_each(edge_t, e, &n->edge_tree) { /* "e" is the edge connected to "from" */ + if(!e->reverse || e->to == myself) { continue; + } /* Situation: - / - / + / + / ----->(n)---e-->(e->to) - \ - \ + \ + \ Where e is an edge, (n) and (e->to) are nodes. n->address is set to the e->address of the edge left of n to n. @@ -172,14 +174,16 @@ static void sssp_bfs(void) { bool indirect = n->status.indirect || e->options & OPTION_INDIRECT; if(e->to->status.visited - && (!e->to->status.indirect || indirect) - && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->weight)) + && (!e->to->status.indirect || indirect) + && (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)) + 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; @@ -188,8 +192,9 @@ static void sssp_bfs(void) { e->to->options = e->options; e->to->distance = n->distance + 1; - if(!e->to->status.reachable || (e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)) + if(!e->to->status.reachable || (e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)) { update_node_udp(e->to, &e->address); + } list_insert_tail(todo_list, e->to); } @@ -207,33 +212,41 @@ static void check_reachability(void) { int reachable_count = 0; int became_reachable_count = 0; int became_unreachable_count = 0; - for splay_each(node_t, n, node_tree) { + + for splay_each(node_t, n, &node_tree) { if(n->status.visited != n->status.reachable) { n->status.reachable = !n->status.reachable; n->last_state_change = now.tv_sec; if(n->status.reachable) { logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became reachable", - n->name, n->hostname); - if (n != myself) + n->name, n->hostname); + + if(n != myself) { became_reachable_count++; + } } else { logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became unreachable", - n->name, n->hostname); - if (n != myself) + n->name, n->hostname); + + if(n != myself) { became_unreachable_count++; + } } - if(experimental && OPTION_VERSION(n->options) >= 2) + if(experimental && OPTION_VERSION(n->options) >= 2) { n->status.sptps = true; + } /* TODO: only clear status.validkey if node is unreachable? */ n->status.validkey = false; + if(n->status.sptps) { sptps_stop(&n->sptps); n->status.waitingforkey = false; } + n->last_req_key = 0; n->status.udp_confirmed = false; @@ -269,24 +282,27 @@ static void check_reachability(void) { if(!n->status.reachable) { update_node_udp(n, NULL); - memset(&n->status, 0, sizeof n->status); + memset(&n->status, 0, sizeof(n->status)); n->options = 0; } else if(n->connection) { // Speed up UDP probing by sending our key. - if(!n->status.sptps) + if(!n->status.sptps) { send_ans_key(n); + } } } - if(n->status.reachable && n != myself) + if(n->status.reachable && n != myself) { reachable_count++; + } } - if (device_standby) { - if (reachable_count == 0 && became_unreachable_count > 0) + if(device_standby) { + if(reachable_count == 0 && became_unreachable_count > 0) { device_disable(); - else if (reachable_count > 0 && reachable_count == became_reachable_count) + } else if(reachable_count > 0 && reachable_count == became_reachable_count) { device_enable(); + } } }