X-Git-Url: https://www.tinc-vpn.org/git/browse?a=blobdiff_plain;f=src%2Fgraph.c;h=216f9de2754d054213bc08ee25892fba171bc6d9;hb=103543aa2c15d9f1e2aa313a2e593a7524cce484;hp=8e801b3d55e567c36b3eb8fc80d79d951a8b8e62;hpb=08aabbf9317806bc50a9a6693ca866c8936ce26b;p=tinc diff --git a/src/graph.c b/src/graph.c index 8e801b3d..216f9de2 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,6 +1,6 @@ /* graph.c -- graph algorithms - Copyright (C) 2001-2009 Guus Sliepen , + Copyright (C) 2001-2010 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: @@ -55,8 +53,10 @@ #include "netutl.h" #include "node.h" #include "process.h" +#include "protocol.h" #include "subnet.h" #include "utils.h" +#include "xalloc.h" /* Implementation of Kruskal's algorithm. Running time: O(E) @@ -69,8 +69,6 @@ void mst_kruskal(void) { node_t *n; connection_t *c; - cp(); - /* Clear MST status on connections */ for(node = connection_tree->head; node; node = node->next) { @@ -122,8 +120,6 @@ void sssp_dijkstra(void) { list_node_t *lnode, *nnode; bool indirect; - cp(); - todo_list = list_alloc(NULL); ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Dijkstra's algorithm:"); @@ -248,8 +244,6 @@ void sssp_bfs(void) { list_node_t *from, *todonext; bool indirect; - cp(); - todo_list = list_alloc(NULL); /* Clear visited status on nodes */ @@ -312,27 +306,8 @@ void sssp_bfs(void) { e->to->via = indirect ? n->via : e->to; e->to->options = e->options; - if(sockaddrcmp(&e->to->address, &e->address)) { - node = splay_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) - splay_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); } @@ -362,34 +337,36 @@ void check_reachability() { 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); - splay_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); - splay_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); + event_del(&n->mtuevent); + + 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); @@ -402,48 +379,17 @@ void check_reachability() { free(envp[i]); subnet_update(n, NULL, n->status.reachable); - } - } -} -/* Dump nodes and edges to a graphviz file. - - The file can be converted to an image with - dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true -*/ - -int dump_graph(struct evbuffer *out) { - splay_node_t *node; - node_t *n; - edge_t *e; - - if(evbuffer_add_printf(out, "digraph {\n") == -1) - return errno; - - /* dump all nodes first */ - for(node = node_tree->head; node; node = node->next) { - n = node->data; - if(evbuffer_add_printf(out, " %s [label = \"%s\"];\n", - n->name, n->name) == -1) - return errno; - } - - /* now dump all edges */ - for(node = edge_weight_tree->head; node; node = node->next) { - e = node->data; - if(evbuffer_add_printf(out, " %s -> %s;\n", - e->from->name, e->to->name) == -1) - return errno; + if(!n->status.reachable) + update_node_udp(n, NULL); + else if(n->connection) + send_ans_key(n); + } } - - if(evbuffer_add_printf(out, "}\n") == -1) - return errno; - - return 0; } void graph(void) { - subnet_cache_flush(); + subnet_cache_flush(); sssp_dijkstra(); check_reachability(); mst_kruskal();