/*
graph.c -- graph algorithms
- Copyright (C) 2001-2002 Guus Sliepen <guus@sliepen.warande.net>,
- 2001-2002 Ivo Timmermans <itimmermans@bigfoot.com>
+ Copyright (C) 2001-2002 Guus Sliepen <guus@sliepen.eu.org>,
+ 2001-2002 Ivo Timmermans <ivo@o2w.nl>
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
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.6 2002/02/10 21:57:54 guus Exp $
+ $Id: graph.c,v 1.1.2.13 2002/06/21 10:11:12 guus Exp $
*/
/* We need to generate two trees from the graph:
destination address and port of a node if possible.
*/
+#include "config.h"
+
+#include <stdio.h>
#include <syslog.h>
#include "config.h"
#include <string.h>
-#if defined(HAVE_FREEBSD) || defined(HAVE_OPENBSD)
+#ifdef HAVE_SYS_PARAM_H
#include <sys/param.h>
#endif
#include <netinet/in.h>
#include "node.h"
#include "edge.h"
#include "connection.h"
+#include "process.h"
#include "system.h"
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)
((edge_t *)edge_weight_tree->head->data)->from.node->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)
safe_edges++;
+ if(debug_lvl >= DEBUG_SCARY_THINGS)
+ syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from.node->name, e->to.node->name, e->weight);
+
if(skipped)
{
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.
node_t *n;
halfconnection_t to_hc, from_hc;
avl_tree_t *todo_tree;
+ int indirect;
+ char *name;
todo_tree = avl_alloc_tree(NULL, NULL);
{
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();
else
to_hc = e->from, from_hc = e->to;
- if(!to_hc.node->status.visited)
- {
- to_hc.node->status.visited = 1;
- to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop;
- to_hc.node->via = (e->options & OPTION_INDIRECT || n->via != n) ? n->via : to_hc.node;
- to_hc.node->options = e->options;
- if(to_hc.node->address != to_hc.address || to_hc.node->port != to_hc.port)
- {
- node = avl_unlink(node_udp_tree, to_hc.node);
- to_hc.node->address = to_hc.address;
- to_hc.node->port = to_hc.port;
- if(to_hc.node->hostname)
- free(to_hc.node->hostname);
- to_hc.node->hostname = hostlookup(htonl(to_hc.address));
- avl_insert_node(node_udp_tree, node);
- }
- to_hc.node->port = to_hc.port;
- node = avl_alloc_node();
- node->data = to_hc.node;
- avl_insert_before(todo_tree, from, node);
- }
+ /* Situation:
+
+ /
+ /
+ ------(n)from_hc-----to_hc
+ \
+ \
+
+ n->address is set to the to_hc.udpaddress of the edge left of n.
+ We are currently examining the edge right of n:
+
+ - If from_hc.udpaddress != n->address, then to_hc.node 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 to_hc.node, update
+ to_hc.node 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, &from_hc.udpaddress));
+
+ if(to_hc.node->status.visited && (!to_hc.node->status.indirect || indirect))
+ continue;
+
+ to_hc.node->status.visited = 1;
+ to_hc.node->status.indirect = indirect;
+ to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop;
+ to_hc.node->via = indirect ? n->via : to_hc.node;
+ to_hc.node->options = e->options;
+ if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress))
+ {
+ node = avl_unlink(node_udp_tree, to_hc.node);
+ to_hc.node->address = to_hc.udpaddress;
+ if(to_hc.node->hostname)
+ free(to_hc.node->hostname);
+ to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress);
+ avl_insert_node(node_udp_tree, node);
+ }
+ node = avl_alloc_node();
+ node->data = to_hc.node;
+ avl_insert_before(todo_tree, from, node);
}
avl_delete_node(todo_tree, from);
if(debug_lvl >= DEBUG_TRAFFIC)
syslog(LOG_DEBUG, _("Node %s (%s) became reachable"), n->name, n->hostname);
n->status.reachable = 1;
+ asprintf(&name, "hosts/%s-up", n->name);
+ execute_script(name);
+ free(name);
}
}
else
n->status.validkey = 0;
n->status.waitingforkey = 0;
n->sent_seqno = 0;
+ asprintf(&name, "hosts/%s-down", n->name);
+ execute_script(name);
+ free(name);
}
}
}