X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fgraph.c;h=53152a545155736e43974f5eabaaba6e23a5d03e;hp=abc918d9b1ce881cb05d56db7c545c335256ed5a;hb=d699f3079c658e05f928c358d110d1d27849ea71;hpb=c2b9c06062d36bde859b630b99a08c7b7428e721 diff --git a/src/graph.c b/src/graph.c index abc918d9..53152a54 100644 --- a/src/graph.c +++ b/src/graph.c @@ -17,7 +17,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: graph.c,v 1.1.2.7 2002/02/18 16:25:16 guus Exp $ + $Id: graph.c,v 1.1.2.11 2002/03/24 16:28:27 guus Exp $ */ /* We need to generate two trees from the graph: @@ -44,6 +44,9 @@ destination address and port of a node if possible. */ +#include "config.h" + +#include #include #include "config.h" #include @@ -59,6 +62,7 @@ #include "node.h" #include "edge.h" #include "connection.h" +#include "process.h" #include "system.h" @@ -77,11 +81,22 @@ void mst_kruskal(void) int safe_edges = 0; int skipped; + /* Clear MST status on connections */ + + for(node = connection_tree->head; node; node = node->next) + { + c = (connection_t *)node->data; + c->status.mst = 0; + } + /* Do we have something to do at all? */ if(!edge_weight_tree->head) return; + if(debug_lvl >= DEBUG_SCARY_THINGS) + syslog(LOG_DEBUG, "Running Kruskal's algorithm:"); + /* Clear visited status on nodes */ for(node = node_tree->head; node; node = node->next) @@ -95,14 +110,6 @@ void mst_kruskal(void) ((edge_t *)edge_weight_tree->head->data)->from.node->status.visited = 1; - /* Clear MST status on connections */ - - for(node = connection_tree->head; node; node = node->next) - { - c = (connection_t *)node->data; - c->status.mst = 0; - } - /* Add safe edges */ for(skipped = 0, node = edge_weight_tree->head; node; node = next) @@ -123,12 +130,18 @@ void mst_kruskal(void) safe_edges++; + if(debug_lvl >= DEBUG_SCARY_THINGS) + syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from.node->name, e->to.node->name, e->weight); + if(skipped) { next = edge_weight_tree->head; continue; } } + + if(debug_lvl >= DEBUG_SCARY_THINGS) + syslog(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes, safe_edges); } /* Implementation of a simple breadth-first search algorithm. @@ -142,6 +155,8 @@ void sssp_bfs(void) node_t *n; halfconnection_t to_hc, from_hc; avl_tree_t *todo_tree; + int indirect; + char *name; todo_tree = avl_alloc_tree(NULL, NULL); @@ -151,11 +166,13 @@ void sssp_bfs(void) { n = (node_t *)node->data; n->status.visited = 0; + n->status.indirect = 1; } /* Begin with myself */ myself->status.visited = 1; + myself->status.indirect = 0; myself->nexthop = myself; myself->via = myself; node = avl_alloc_node(); @@ -180,25 +197,47 @@ void sssp_bfs(void) else to_hc = e->from, from_hc = e->to; - if(!to_hc.node->status.visited) - { - to_hc.node->status.visited = 1; - to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop; - to_hc.node->via = (e->options & OPTION_INDIRECT || n->via != n) ? n->via : to_hc.node; - to_hc.node->options = e->options; - if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress)) - { - node = avl_unlink(node_udp_tree, to_hc.node); - to_hc.node->address = to_hc.udpaddress; - if(to_hc.node->hostname) - free(to_hc.node->hostname); - to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress); - avl_insert_node(node_udp_tree, node); - } - node = avl_alloc_node(); - node->data = to_hc.node; - avl_insert_before(todo_tree, from, node); - } + /* Situation: + + / + / + ------(n)from_hc-----to_hc + \ + \ + + n->address is set to the to_hc.udpaddress of the edge left of n. + We are currently examining the edge right of n: + + - If from_hc.udpaddress != n->address, then to_hc.node is probably + not reachable for the nodes left of n. We do as if the indirectdata + flag is set on edge e. + - If edge e provides for better reachability of to_hc.node, update + to_hc.node and (re)add it to the todo_tree to (re)examine the reachability + of nodes behind it. + */ + + indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &from_hc.udpaddress)); + + if(to_hc.node->status.visited && (!to_hc.node->status.indirect || indirect)) + continue; + + to_hc.node->status.visited = 1; + to_hc.node->status.indirect = indirect; + to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop; + to_hc.node->via = indirect ? n->via : to_hc.node; + to_hc.node->options = e->options; + if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress)) + { + node = avl_unlink(node_udp_tree, to_hc.node); + to_hc.node->address = to_hc.udpaddress; + if(to_hc.node->hostname) + free(to_hc.node->hostname); + to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress); + avl_insert_node(node_udp_tree, node); + } + node = avl_alloc_node(); + node->data = to_hc.node; + avl_insert_before(todo_tree, from, node); } avl_delete_node(todo_tree, from); @@ -221,6 +260,9 @@ void sssp_bfs(void) if(debug_lvl >= DEBUG_TRAFFIC) syslog(LOG_DEBUG, _("Node %s (%s) became reachable"), n->name, n->hostname); n->status.reachable = 1; + asprintf(&name, "hosts/%s-up", n->name); + execute_script(name); + free(name); } } else @@ -233,6 +275,9 @@ void sssp_bfs(void) n->status.validkey = 0; n->status.waitingforkey = 0; n->sent_seqno = 0; + asprintf(&name, "hosts/%s-down", n->name); + execute_script(name); + free(name); } } }