X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fgraph.c;h=203942dbdf2ec9d5e9427ed77d262266025dfb70;hp=014177ce7b67048963d63723d7ceeeb3c5d7ff9c;hb=c9c3cc03bfec664f7386011f3fc608d1c0844836;hpb=5674bba5c54c1aee3a4ac5b3aba6b3ebded91bbc diff --git a/src/graph.c b/src/graph.c index 014177ce..203942db 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,6 +1,6 @@ /* graph.c -- graph algorithms - Copyright (C) 2001-2007 Guus Sliepen , + Copyright (C) 2001-2013 Guus Sliepen , 2001-2005 Ivo Timmermans This program is free software; you can redistribute it and/or modify @@ -13,11 +13,9 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - - $Id$ + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ /* We need to generate two trees from the graph: @@ -51,12 +49,15 @@ #include "connection.h" #include "device.h" #include "edge.h" +#include "graph.h" #include "logger.h" #include "netutl.h" #include "node.h" #include "process.h" +#include "protocol.h" #include "subnet.h" #include "utils.h" +#include "xalloc.h" static bool graph_changed = true; @@ -65,8 +66,7 @@ static bool graph_changed = true; Please note that sorting on weight is already done by add_edge(). */ -void mst_kruskal(void) -{ +static void mst_kruskal(void) { avl_node_t *node, *next; edge_t *e; node_t *n; @@ -75,8 +75,6 @@ void mst_kruskal(void) int safe_edges = 0; bool skipped; - cp(); - /* Clear MST status on connections */ for(node = connection_tree->head; node; node = node->next) { @@ -149,8 +147,7 @@ void mst_kruskal(void) Running time: O(E) */ -void sssp_bfs(void) -{ +static void sssp_bfs(void) { avl_node_t *node, *next, *to; edge_t *e; node_t *n; @@ -162,8 +159,6 @@ void sssp_bfs(void) char *envp[7]; int i; - cp(); - todo_list = list_alloc(NULL); /* Clear visited status on nodes */ @@ -179,6 +174,7 @@ void sssp_bfs(void) myself->status.visited = true; myself->status.indirect = false; myself->nexthop = myself; + myself->prevedge = NULL; myself->via = myself; list_insert_head(todo_list, myself); @@ -205,16 +201,12 @@ void sssp_bfs(void) n->address is set to the e->address of the edge left of n to n. We are currently examining the edge e right of n from n: - - If e->reverse->address != n->address, then e->to 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 e->to, update e->to and (re)add it to the todo_list to (re)examine the reachability of nodes behind it. */ - indirect = n->status.indirect || e->options & OPTION_INDIRECT - || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address)); + indirect = n->status.indirect || e->options & OPTION_INDIRECT; if(e->to->status.visited && (!e->to->status.indirect || indirect)) @@ -223,30 +215,12 @@ void sssp_bfs(void) 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; - if(sockaddrcmp(&e->to->address, &e->address)) { - node = avl_unlink(node_udp_tree, e->to); - sockaddrfree(&e->to->address); - sockaddrcpy(&e->to->address, &e->address); - - if(e->to->hostname) - free(e->to->hostname); - - e->to->hostname = sockaddr2hostname(&e->to->address); - - if(node) - avl_insert_node(node_udp_tree, node); - - if(e->to->options & OPTION_PMTU_DISCOVERY) { - e->to->mtuprobes = 0; - e->to->minmtu = 0; - e->to->maxmtu = MTU; - if(e->to->status.validkey) - send_mtu_probe(e->to); - } - } + if(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); } @@ -267,34 +241,39 @@ void sssp_bfs(void) n->status.reachable = !n->status.reachable; if(n->status.reachable) { - ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became reachable"), + ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable", n->name, n->hostname); - avl_insert(node_udp_tree, n); } else { - ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became unreachable"), + ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable", n->name, n->hostname); - avl_delete(node_udp_tree, n); } + /* TODO: only clear status.validkey if node is unreachable? */ + n->status.validkey = false; - n->status.waitingforkey = false; + n->last_req_key = 0; n->maxmtu = MTU; n->minmtu = 0; n->mtuprobes = 0; - asprintf(&envp[0], "NETNAME=%s", netname ? : ""); - asprintf(&envp[1], "DEVICE=%s", device ? : ""); - asprintf(&envp[2], "INTERFACE=%s", iface ? : ""); - asprintf(&envp[3], "NODE=%s", n->name); + if(n->mtuevent) { + event_del(n->mtuevent); + n->mtuevent = NULL; + } + + xasprintf(&envp[0], "NETNAME=%s", netname ? : ""); + xasprintf(&envp[1], "DEVICE=%s", device ? : ""); + xasprintf(&envp[2], "INTERFACE=%s", iface ? : ""); + xasprintf(&envp[3], "NODE=%s", n->name); sockaddr2str(&n->address, &address, &port); - asprintf(&envp[4], "REMOTEADDRESS=%s", address); - asprintf(&envp[5], "REMOTEPORT=%s", port); + xasprintf(&envp[4], "REMOTEADDRESS=%s", address); + xasprintf(&envp[5], "REMOTEPORT=%s", port); envp[6] = NULL; execute_script(n->status.reachable ? "host-up" : "host-down", envp); - asprintf(&name, + xasprintf(&name, n->status.reachable ? "hosts/%s-up" : "hosts/%s-down", n->name); execute_script(name, envp); @@ -307,12 +286,19 @@ void sssp_bfs(void) free(envp[i]); subnet_update(n, NULL, n->status.reachable); + + if(!n->status.reachable) { + update_node_udp(n, NULL); + memset(&n->status, 0, sizeof n->status); + n->options = 0; + } else if(n->connection) { + send_ans_key(n); + } } } } -void graph(void) -{ +void graph(void) { subnet_cache_flush(); sssp_bfs(); mst_kruskal(); @@ -327,13 +313,12 @@ void graph(void) dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true */ -void dump_graph(void) -{ +void dump_graph(void) { avl_node_t *node; node_t *n; edge_t *e; char *filename = NULL, *tmpname = NULL; - FILE *file; + FILE *file, *pipe = NULL; if(!graph_changed || !get_config_string(lookup_config(config_tree, "GraphDumpFile"), &filename)) return; @@ -343,9 +328,9 @@ void dump_graph(void) ifdebug(PROTOCOL) logger(LOG_NOTICE, "Dumping graph"); if(filename[0] == '|') { - file = popen(filename + 1, "w"); + file = pipe = popen(filename + 1, "w"); } else { - asprintf(&tmpname, "%s.new", filename); + xasprintf(&tmpname, "%s.new", filename); file = fopen(tmpname, "w"); } @@ -371,8 +356,8 @@ void dump_graph(void) fprintf(file, "}\n"); - if(filename[0] == '|') { - pclose(file); + if(pipe) { + pclose(pipe); } else { fclose(file); #ifdef HAVE_MINGW