X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fgraph.c;h=b5e81931f8d9aed4dc7526f2f1a02026696a6f93;hp=aa1ec72a26bddf757e3d0b4c21e1b45397e78ece;hb=82ebfc923ddb050c88bdf5d65ac943a15ca8748a;hpb=c0a3f67a5d66088aaf526f1461986f9e86d5dd1f diff --git a/src/graph.c b/src/graph.c index aa1ec72a..b5e81931 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,7 +1,7 @@ /* graph.c -- graph algorithms - Copyright (C) 2001 Guus Sliepen , - 2001 Ivo Timmermans + Copyright (C) 2001-2002 Guus Sliepen , + 2001-2002 Ivo Timmermans This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -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.5 2001/10/31 12:50:24 guus Exp $ + $Id: graph.c,v 1.1.2.15 2002/09/04 13:48:51 guus Exp $ */ /* We need to generate two trees from the graph: @@ -38,17 +38,32 @@ For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a simple breadth-first search is presented here. + + The SSSP algorithm will also be used to determine whether nodes are directly, + indirectly or not reachable from the source. It will also set the correct + destination address and port of a node if possible. */ +#include "config.h" + +#include #include #include "config.h" #include +#ifdef HAVE_SYS_PARAM_H + #include +#endif +#include #include +#include +#include "netutl.h" #include "node.h" #include "edge.h" #include "connection.h" +#include "process.h" +#include "device.h" #include "system.h" @@ -67,6 +82,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) @@ -80,14 +111,6 @@ void mst_kruskal(void) ((edge_t *)edge_weight_tree->head->data)->from->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) @@ -95,7 +118,7 @@ void mst_kruskal(void) next = node->next; e = (edge_t *)node->data; - if(e->from->status.visited == e->to->status.visited) + if(!e->reverse || e->from->status.visited == e->to->status.visited) { skipped = 1; continue; @@ -108,24 +131,36 @@ void mst_kruskal(void) safe_edges++; + if(debug_lvl >= DEBUG_SCARY_THINGS) + syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight); + if(skipped) { + skipped = 0; 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. Running time: O(E) */ -void sssp_bfs(int prune) +void sssp_bfs(void) { avl_node_t *node, *from, *next, *to; edge_t *e; - node_t *n, *check; + node_t *n; avl_tree_t *todo_tree; + int indirect; + char *name; + char *address, *port; + char *envp[7]; + int i; todo_tree = avl_alloc_tree(NULL, NULL); @@ -135,11 +170,13 @@ void sssp_bfs(int prune) { 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(); @@ -150,46 +187,110 @@ void sssp_bfs(int prune) while(todo_tree->head) { - for(from = todo_tree->head; from; from = next) + for(from = todo_tree->head; from; from = next) /* "from" is the node from which we start */ { next = from->next; n = (node_t *)from->data; - for(to = n->edge_tree->head; to; to = to->next) + for(to = n->edge_tree->head; to; to = to->next) /* "to" is the edge connected to "from" */ { e = (edge_t *)to->data; - - if(e->from == n) - check = e->to; - else - check = e->from; - - if(!check->status.visited) - { - check->status.visited = 1; - check->nexthop = (n->nexthop == myself) ? check : n->nexthop; - check->via = (e->options & OPTION_INDIRECT || n->via != n) ? n->via : check; - node = avl_alloc_node(); - node->data = check; - avl_insert_before(todo_tree, from, node); - } + + if(!e->reverse) + continue; + + /* Situation: + + / + / + ------(n)-----(e->to) + \ + \ + + 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_tree 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)); + + if(e->to->status.visited && (!e->to->status.indirect || indirect)) + continue; + + e->to->status.visited = 1; + e->to->status.indirect = indirect; + e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; + 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); + e->to->address = e->address; + if(e->to->hostname) + free(e->to->hostname); + e->to->hostname = sockaddr2hostname(&e->to->address); + avl_insert_node(node_udp_tree, node); + } + node = avl_alloc_node(); + node->data = e->to; + avl_insert_before(todo_tree, from, node); } - avl_delete_node(todo_tree, from); + avl_delete_node(todo_tree, from); } } avl_free_tree(todo_tree); - /* Nodes we haven't visited are unreachable, prune them. */ + /* Check reachability status. */ - if(prune) - for(node = node_tree->head; node; node = next) - { - next = node->next; - n = (node_t *)node->data; + for(node = node_tree->head; node; node = next) + { + next = node->next; + n = (node_t *)node->data; - if(n->status.visited == 0) - node_del(n); + if(n->status.visited != n->status.reachable) + { + n->status.reachable = !n->status.reachable; + if(debug_lvl >= DEBUG_TRAFFIC) + if(n->status.reachable) + syslog(LOG_DEBUG, _("Node %s (%s) became reachable"), n->name, n->hostname); + else + syslog(LOG_DEBUG, _("Node %s (%s) became unreachable"), n->name, n->hostname); + + n->status.validkey = 0; + n->status.waitingforkey = 0; + n->sent_seqno = 0; + + asprintf(&envp[0], "NETNAME=%s", netname?netname:""); + asprintf(&envp[1], "DEVICE=%s", device?device:""); + asprintf(&envp[2], "INTERFACE=%s", interface?interface:""); + asprintf(&envp[3], "NODE=%s", n->name); + sockaddr2str(&n->address, &address, &port); + asprintf(&envp[4], "REMOTEADDRESS=%s", address); + asprintf(&envp[5], "REMOTEPORT=%s", port); + envp[6] = NULL; + + asprintf(&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 < 7; i++) + free(envp[i]); } + } +} + +void graph(void) +{ + mst_kruskal(); + sssp_bfs(); }