From: Guus Sliepen Date: Wed, 31 Oct 2001 12:50:24 +0000 (+0000) Subject: - Small fixes to graph algorithms X-Git-Tag: release-1.0pre5~38 X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=commitdiff_plain;h=c0a3f67a5d66088aaf526f1461986f9e86d5dd1f;hp=2165931c62f0433fd97bd3ac6aefea3627218946 - Small fixes to graph algorithms - More control over tap device, ability to set interface name to something other than the netname. - Export NETNAME, DEVICE and INTERFACE environment variables to scripts. --- diff --git a/src/device.h b/src/device.h index c2c28a13..05dcaaa6 100644 --- a/src/device.h +++ b/src/device.h @@ -17,13 +17,15 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: device.h,v 1.1.2.3 2001/10/27 13:13:35 guus Exp $ + $Id: device.h,v 1.1.2.4 2001/10/31 12:50:24 guus Exp $ */ #ifndef __TINC_DEVICE_H__ #define __TINC_DEVICE_H__ extern int device_fd; +extern char *device; +extern char *interface; extern int setup_device(void); extern void close_device(void); diff --git a/src/graph.c b/src/graph.c index 53cf6a99..aa1ec72a 100644 --- a/src/graph.c +++ b/src/graph.c @@ -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.4 2001/10/30 12:59:12 guus Exp $ + $Id: graph.c,v 1.1.2.5 2001/10/31 12:50:24 guus Exp $ */ /* We need to generate two trees from the graph: @@ -59,7 +59,7 @@ void mst_kruskal(void) { - avl_node_t *node; + avl_node_t *node, *next; edge_t *e; node_t *n; connection_t *c; @@ -90,9 +90,9 @@ void mst_kruskal(void) /* Add safe edges */ - while(safe_edges < nodes - 1) - for(skipped = 0, node = edge_weight_tree->head; node; node = node->next) + for(skipped = 0, node = edge_weight_tree->head; node; node = next) { + next = node->next; e = (edge_t *)node->data; if(e->from->status.visited == e->to->status.visited) @@ -109,7 +109,10 @@ void mst_kruskal(void) safe_edges++; if(skipped) - break; + { + next = edge_weight_tree->head; + continue; + } } } @@ -117,7 +120,7 @@ void mst_kruskal(void) Running time: O(E) */ -void sssp_bfs(void) +void sssp_bfs(int prune) { avl_node_t *node, *from, *next, *to; edge_t *e; @@ -165,7 +168,7 @@ void sssp_bfs(void) { check->status.visited = 1; check->nexthop = (n->nexthop == myself) ? check : n->nexthop; - check->via = check; /* FIXME: only if !(e->options & INDIRECT), otherwise use n->via */ + 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); @@ -177,4 +180,16 @@ void sssp_bfs(void) } avl_free_tree(todo_tree); + + /* Nodes we haven't visited are unreachable, prune them. */ + + if(prune) + for(node = node_tree->head; node; node = next) + { + next = node->next; + n = (node_t *)node->data; + + if(n->status.visited == 0) + node_del(n); + } } diff --git a/src/graph.h b/src/graph.h index c69fc98b..bd6cc3f8 100644 --- a/src/graph.h +++ b/src/graph.h @@ -17,9 +17,8 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: graph.h,v 1.1.2.1 2001/10/29 13:14:57 guus Exp $ + $Id: graph.h,v 1.1.2.2 2001/10/31 12:50:24 guus Exp $ */ extern void mst_kruskal(void); -extern void mst_prim(void); -extern void sssp_bfs(void); +extern void sssp_bfs(int); diff --git a/src/linux/device.c b/src/linux/device.c index 1cb43077..02d7a7a5 100644 --- a/src/linux/device.c +++ b/src/linux/device.c @@ -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: device.c,v 1.1.2.3 2001/10/27 13:13:35 guus Exp $ + $Id: device.c,v 1.1.2.4 2001/10/31 12:50:24 guus Exp $ */ #include "config.h" @@ -55,7 +55,9 @@ int device_fd = -1; int device_type; -char *device_fname; +char *device; +char *interface; +char ifrname[IFNAMSIZ]; char *device_info; int device_total_in = 0; @@ -71,13 +73,15 @@ int setup_device(void) struct ifreq ifr; cp - if(!get_config_string(lookup_config(config_tree, "Device"), &device_fname)) - device_fname = DEFAULT_DEVICE; + if(!get_config_string(lookup_config(config_tree, "Device"), &device)) + device = DEFAULT_DEVICE; + if(!get_config_string(lookup_config(config_tree, "Interface"), &interface)) + interface = netname; cp - if((device_fd = open(device_fname, O_RDWR | O_NONBLOCK)) < 0) + if((device_fd = open(device, O_RDWR | O_NONBLOCK)) < 0) { - syslog(LOG_ERR, _("Could not open %s: %m"), device_fname); + syslog(LOG_ERR, _("Could not open %s: %m"), device); return -1; } cp @@ -97,20 +101,24 @@ cp memset(&ifr, 0, sizeof(ifr)); cp ifr.ifr_flags = IFF_TAP | IFF_NO_PI; - if (netname) - strncpy(ifr.ifr_name, netname, IFNAMSIZ); + if (interface) + strncpy(ifr.ifr_name, interface, IFNAMSIZ); cp if (!ioctl(device_fd, TUNSETIFF, (void *) &ifr)) { - device_info = _("Linux tun/tap device"); + device_info = _("Linux tun/tap device"); device_type = DEVICE_TYPE_TUNTAP; + strncpy(ifrname, ifr.ifr_name, IFNAMSIZ); + interface = ifrname; } else if (!ioctl(device_fd, (('T'<< 8) | 202), (void *) &ifr)) { - syslog(LOG_WARNING, _("Old ioctl() request was needed for %s"), device_fname); + syslog(LOG_WARNING, _("Old ioctl() request was needed for %s"), device); device_type = DEVICE_TYPE_TUNTAP; device_info = _("Linux tun/tap device"); + strncpy(ifrname, ifr.ifr_name, IFNAMSIZ); + interface = ifrname; } else #endif @@ -119,7 +127,7 @@ cp device_type = DEVICE_TYPE_ETHERTAP; } - syslog(LOG_INFO, _("%s is a %s"), device_fname, device_info); + syslog(LOG_INFO, _("%s is a %s"), device, device_info); cp return 0; } @@ -142,7 +150,7 @@ cp { if((lenin = read(device_fd, packet->data, MTU)) <= 0) { - syslog(LOG_ERR, _("Error while reading from %s %s: %m"), device_info, device_fname); + syslog(LOG_ERR, _("Error while reading from %s %s: %m"), device_info, device); return -1; } @@ -154,7 +162,7 @@ cp if((lenin = readv(device_fd, vector, 2)) <= 0) { - syslog(LOG_ERR, _("Error while reading from %s %s: %m"), device_info, device_fname); + syslog(LOG_ERR, _("Error while reading from %s %s: %m"), device_info, device); return -1; } @@ -183,7 +191,7 @@ cp { if(write(device_fd, packet->data, packet->len) < 0) { - syslog(LOG_ERR, _("Can't write to %s %s: %m"), device_info, device_fname); + syslog(LOG_ERR, _("Can't write to %s %s: %m"), device_info, device); return -1; } } @@ -193,7 +201,7 @@ cp if(writev(device_fd, vector, 2) < 0) { - syslog(LOG_ERR, _("Can't write to %s %s: %m"), device_info, device_fname); + syslog(LOG_ERR, _("Can't write to %s %s: %m"), device_info, device); return -1; } } @@ -206,7 +214,7 @@ cp void dump_device_stats(void) { cp - syslog(LOG_DEBUG, _("Statistics for %s %s:"), device_info, device_fname); + syslog(LOG_DEBUG, _("Statistics for %s %s:"), device_info, device); syslog(LOG_DEBUG, _(" total bytes in: %10d"), device_total_in); syslog(LOG_DEBUG, _(" total bytes out: %10d"), device_total_out); cp diff --git a/src/net.c b/src/net.c index 1895bc18..230f2baa 100644 --- a/src/net.c +++ b/src/net.c @@ -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: net.c,v 1.35.4.143 2001/10/30 16:34:32 guus Exp $ + $Id: net.c,v 1.35.4.144 2001/10/31 12:50:24 guus Exp $ */ #include "config.h" @@ -975,7 +975,8 @@ cp /* Deactivate */ c->status.active = 0; - c->node->connection = NULL; + if(c->node) + c->node->connection = NULL; do_prune = 1; cp } diff --git a/src/node.c b/src/node.c index 95a1d4f7..9a518382 100644 --- a/src/node.c +++ b/src/node.c @@ -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: node.c,v 1.1.2.5 2001/10/30 12:59:12 guus Exp $ + $Id: node.c,v 1.1.2.6 2001/10/31 12:50:24 guus Exp $ */ #include "config.h" @@ -109,6 +109,23 @@ cp void node_del(node_t *n) { + avl_node_t *node, *next; + edge_t *e; + subnet_t *s; +cp + for(node = n->subnet_tree->head; node; node = next) + { + next = node->next; + s = (subnet_t *)node->data; + subnet_del(n, s); + } + + for(node = n->subnet_tree->head; node; node = next) + { + next = node->next; + e = (edge_t *)node->data; + edge_del(e); + } cp avl_delete(node_tree, n); avl_delete(node_udp_tree, n); diff --git a/src/process.c b/src/process.c index 525836b8..7373a70c 100644 --- a/src/process.c +++ b/src/process.c @@ -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: process.c,v 1.1.2.29 2001/10/28 10:16:18 guus Exp $ + $Id: process.c,v 1.1.2.30 2001/10/31 12:50:24 guus Exp $ */ #include "config.h" @@ -44,6 +44,7 @@ #include "subnet.h" #include "device.h" #include "connection.h" +#include "device.h" #include "system.h" @@ -199,17 +200,29 @@ void _execute_script(const char *name) char *scriptname; char *s; cp +#ifdef HAVE_UNSETENV + unsetenv("NETNAME"); + unsetenv("DEVICE"); + unsetenv("INTERFACE"); +#endif + if(netname) { asprintf(&s, "NETNAME=%s", netname); putenv(s); /* Don't free s! see man 3 putenv */ } -#ifdef HAVE_UNSETENV - else + + if(device) { - unsetenv("NETNAME"); + asprintf(&s, "DEVICE=%s", device); + putenv(s); /* Don't free s! see man 3 putenv */ + } + + if(interface) + { + asprintf(&s, "INTERFACE=%s", interface); + putenv(s); /* Don't free s! see man 3 putenv */ } -#endif chdir("/"); diff --git a/src/protocol.c b/src/protocol.c index c8c41d9f..7540e473 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -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: protocol.c,v 1.28.4.114 2001/10/30 16:34:32 guus Exp $ + $Id: protocol.c,v 1.28.4.115 2001/10/31 12:50:24 guus Exp $ */ #include "config.h" @@ -682,7 +682,7 @@ cp /* Run MST and SSSP algorithms */ mst_kruskal(); - sssp_bfs(); + sssp_bfs(0); cp return 0; } @@ -912,12 +912,11 @@ cp int del_node_h(connection_t *c) { node_t *n; - edge_t *e; char name[MAX_STRING_SIZE]; ipv4_t address; port_t port; connection_t *other; - avl_node_t *node, *next; + avl_node_t *node; cp if(sscanf(c->buffer, "%*d "MAX_STRING" %lx:%hd", name, &address, &port) != 3) { @@ -969,21 +968,12 @@ cp send_del_node(other, n); } - /* Delete all edges associated with the node */ - - for(node = n->edge_tree->head; node; node = next) - { - next = node->next; - e = (edge_t *)node->data; - edge_del(e); - } - /* Delete the node */ node_del(n); mst_kruskal(); - sssp_bfs(); + sssp_bfs(0); cp return 0; } @@ -1082,7 +1072,7 @@ cp /* Run MST before or after we tell the rest? */ mst_kruskal(); - sssp_bfs(); + sssp_bfs(0); cp return 0; } @@ -1178,7 +1168,7 @@ cp /* Run MST before or after we tell the rest? */ mst_kruskal(); - sssp_bfs(); + sssp_bfs(1); cp return 0; }