X-Git-Url: https://git.librecmc.org/?p=oweals%2Ftinc.git;a=blobdiff_plain;f=src%2Fgraph.c;h=73dadc47f6152c300a4f9924536d9474ca22c489;hp=f7054eeee01bb6190e703595f189a5fb3b511d66;hb=e913f3f232e4809b7218d081ab9f94cef1c94ac3;hpb=c217d214f4f071c235bc7c463a1da6124e2570a6 diff --git a/src/graph.c b/src/graph.c index f7054ee..73dadc4 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-2013 Guus Sliepen , 2001-2005 Ivo Timmermans This program is free software; you can redistribute it and/or modify @@ -13,9 +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. + 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: @@ -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,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; @@ -74,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) { @@ -148,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; @@ -158,11 +156,9 @@ void sssp_bfs(void) bool indirect; char *name; char *address, *port; - char *envp[7]; + char *envp[8] = {NULL}; int i; - cp(); - todo_list = list_alloc(NULL); /* Clear visited status on nodes */ @@ -178,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); @@ -204,24 +201,25 @@ 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)) 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; @@ -247,17 +245,17 @@ 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); } 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); } /* 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; @@ -275,7 +273,7 @@ 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); @@ -288,16 +286,23 @@ void sssp_bfs(void) 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) { + 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(); @@ -312,13 +317,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; @@ -328,7 +332,7 @@ 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 { xasprintf(&tmpname, "%s.new", filename); file = fopen(tmpname, "w"); @@ -336,6 +340,7 @@ 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; } @@ -356,14 +361,17 @@ void dump_graph(void) fprintf(file, "}\n"); - if(filename[0] == '|') { - pclose(file); + 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); }