X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fgraph.c;h=832e01754a143274eb449d8f58068d3e3e133190;hp=f5aff5bfd7a2511e71042162408e390a332d19ea;hb=3fae14fae5a347823679ef694ab630b4991a201d;hpb=369fe1ab1cbfc3f8305de1faab2e30157378b044 diff --git a/src/graph.c b/src/graph.c index f5aff5bf..832e0175 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-2014 Guus Sliepen , 2001-2005 Ivo Timmermans This program is free software; you can redistribute it and/or modify @@ -45,14 +45,16 @@ #include "system.h" #include "avl_tree.h" -#include "config.h" +#include "conf.h" #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" @@ -64,7 +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; @@ -82,8 +84,9 @@ void mst_kruskal(void) { /* Do we have something to do at all? */ - if(!edge_weight_tree->head) + if(!edge_weight_tree->head) { return; + } ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:"); @@ -99,6 +102,7 @@ void mst_kruskal(void) { for(node = edge_weight_tree->head; node; node = node->next) { e = node->data; + if(e->from->status.reachable) { e->from->status.visited = true; break; @@ -119,16 +123,18 @@ 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; + } safe_edges++; ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, - e->to->name, e->weight); + e->to->name, e->weight); if(skipped) { skipped = false; @@ -138,14 +144,14 @@ void mst_kruskal(void) { } ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes, - safe_edges); + safe_edges); } /* Implementation of a simple breadth-first search algorithm. 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; @@ -154,7 +160,7 @@ void sssp_bfs(void) { bool indirect; char *name; char *address, *port; - char *envp[7]; + char *envp[8] = {NULL}; int i; todo_list = list_alloc(NULL); @@ -172,55 +178,61 @@ 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); /* Loop while todo_list is filled */ - for(from = todo_list->head; from; from = todonext) { /* "from" is the node from which we start */ + for(from = todo_list->head; from; from = todonext) { /* "from" is the node from which we start */ n = from->data; - for(to = n->edge_tree->head; to; to = to->next) { /* "to" is the edge connected to "from" */ + for(to = n->edge_tree->head; to; to = to->next) { /* "to" is the edge connected to "from" */ e = to->data; - if(!e->reverse) + if(!e->reverse) { 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. 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)) + && (!e->to->status.indirect || indirect)) { continue; + } + + // Only update nexthop the first time we visit this node. + + if(!e->to->status.visited) { + 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; - if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN) + 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); } @@ -242,16 +254,16 @@ void sssp_bfs(void) { if(n->status.reachable) { ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable", - n->name, n->hostname); + n->name, n->hostname); } else { ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable", - n->name, n->hostname); + n->name, n->hostname); } /* 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; @@ -269,26 +281,32 @@ void sssp_bfs(void) { sockaddr2str(&n->address, &address, &port); xasprintf(&envp[4], "REMOTEADDRESS=%s", address); xasprintf(&envp[5], "REMOTEPORT=%s", port); - envp[6] = NULL; + xasprintf(&envp[6], "NAME=%s", myself->name); execute_script(n->status.reachable ? "host-up" : "host-down", envp); xasprintf(&name, - n->status.reachable ? "hosts/%s-up" : "hosts/%s-down", - n->name); + n->status.reachable ? "hosts/%s-up" : "hosts/%s-down", + n->name); execute_script(name, envp); free(name); free(address); free(port); - for(i = 0; i < 6; i++) + for(i = 0; i < 7; i++) { free(envp[i]); + } subnet_update(n, NULL, n->status.reachable); - if(!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); + } } } } @@ -303,7 +321,7 @@ void graph(void) { /* 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 */ @@ -313,17 +331,18 @@ void dump_graph(void) { node_t *n; edge_t *e; char *filename = NULL, *tmpname = NULL; - FILE *file; - - if(!graph_changed || !get_config_string(lookup_config(config_tree, "GraphDumpFile"), &filename)) + FILE *file, *pipe = NULL; + + if(!graph_changed || !get_config_string(lookup_config(config_tree, "GraphDumpFile"), &filename)) { return; + } graph_changed = false; ifdebug(PROTOCOL) logger(LOG_NOTICE, "Dumping graph"); - + if(filename[0] == '|') { - file = popen(filename + 1, "w"); + file = pipe = popen(filename + 1, "w"); } else { xasprintf(&tmpname, "%s.new", filename); file = fopen(tmpname, "w"); @@ -331,12 +350,13 @@ void dump_graph(void) { if(!file) { logger(LOG_ERR, "Unable to open graph dump file %s: %s", filename, strerror(errno)); + free(filename); free(tmpname); return; } fprintf(file, "digraph {\n"); - + /* dump all nodes first */ for(node = node_tree->head; node; node = node->next) { n = node->data; @@ -349,16 +369,22 @@ void dump_graph(void) { fprintf(file, " %s -> %s;\n", e->from->name, e->to->name); } - fprintf(file, "}\n"); - - if(filename[0] == '|') { - pclose(file); + fprintf(file, "}\n"); + + if(pipe) { + pclose(pipe); } else { fclose(file); #ifdef HAVE_MINGW unlink(filename); #endif - rename(tmpname, filename); + + if(rename(tmpname, filename)) { + logger(LOG_ERR, "Could not rename %s to %s: %s\n", tmpname, filename, strerror(errno)); + } + free(tmpname); } + + free(filename); }