From 82ebfc923ddb050c88bdf5d65ac943a15ca8748a Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Wed, 4 Sep 2002 13:48:52 +0000 Subject: [PATCH] Revert to edge and graph stuff. This time, use a directed graph. --- src/Makefile.am | 8 ++--- src/connection.h | 8 ++--- src/edge.c | 77 +++++++++++++-------------------------- src/edge.h | 16 ++++----- src/graph.c | 80 +++++++++++++++++++---------------------- src/net.c | 66 +++++++++++++++++++++------------- src/net_packet.c | 5 +-- src/net_setup.c | 7 +++- src/net_socket.c | 5 +-- src/node.c | 17 +++++++-- src/node.h | 7 ++-- src/protocol.c | 26 +++++--------- src/protocol.h | 20 +++++++---- src/protocol_auth.c | 87 +++++++++++++++++++++++++-------------------- src/protocol_edge.c | 59 ++++++++++++------------------ 15 files changed, 238 insertions(+), 250 deletions(-) diff --git a/src/Makefile.am b/src/Makefile.am index cc1cdc30..d8d8fd93 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,17 +1,17 @@ ## Produce this file with automake to get Makefile.in -# $Id: Makefile.am,v 1.4.4.26 2002/09/03 20:43:24 guus Exp $ +# $Id: Makefile.am,v 1.4.4.27 2002/09/04 13:48:51 guus Exp $ sbin_PROGRAMS = tincd EXTRA_DIST = linux/device.c freebsd/device.c openbsd/device.c solaris/device.c netbsd/device.c darwin/device.c cygwin/device.c -tincd_SOURCES = conf.c connection.c device.c event.c meta.c net.c net_packet.c net_setup.c \ - net_socket.c netutl.c node.c process.c protocol.c protocol_auth.c protocol_node.c protocol_misc.c \ +tincd_SOURCES = conf.c connection.c device.c edge.c event.c graph.c meta.c net.c net_packet.c net_setup.c \ + net_socket.c netutl.c node.c process.c protocol.c protocol_auth.c protocol_edge.c protocol_misc.c \ protocol_key.c protocol_subnet.c route.c subnet.c tincd.c INCLUDES = @INCLUDES@ -I$(top_builddir) -I$(top_srcdir)/lib -noinst_HEADERS = conf.h connection.h device.h event.h meta.h net.h netutl.h node.h process.h \ +noinst_HEADERS = conf.h connection.h device.h edge.h event.h graph.h meta.h net.h netutl.h node.h process.h \ protocol.h route.h subnet.h LIBS = @LIBS@ diff --git a/src/connection.h b/src/connection.h index fdc87d74..a6d8c58e 100644 --- a/src/connection.h +++ b/src/connection.h @@ -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: connection.h,v 1.1.2.28 2002/09/03 20:43:24 guus Exp $ + $Id: connection.h,v 1.1.2.29 2002/09/04 13:48:51 guus Exp $ */ #ifndef __TINC_CONNECTION_H__ @@ -44,6 +44,7 @@ #include "conf.h" #include "node.h" +#include "edge.h" #define OPTION_INDIRECT 0x0001 #define OPTION_TCPONLY 0x0002 @@ -65,19 +66,18 @@ typedef struct connection_t { char *name; /* name he claims to have */ sockaddr_t address; /* his real (internet) ip */ - sockaddr_t myaddress; /* our own address as seen by him */ - char *hostname; /* the hostname of its real ip */ int protocol_version; /* used protocol */ int socket; /* socket used for this connection */ long int options; /* options for this connection */ struct connection_status_t status; /* status info */ - int estimated_weight; /* estimation for the weight for this connection */ + int estimated_weight; /* estimation for the weight of the edge for this connection */ struct timeval start; /* time this connection was started, used for above estimation */ struct outgoing_t *outgoing; /* used to keep track of outgoing connections */ struct node_t *node; /* node associated with the other end */ + struct edge_t *edge; /* edge associated with this connection */ RSA *rsa_key; /* his public/private key */ const EVP_CIPHER *incipher; /* Cipher he will use to send data to us */ diff --git a/src/edge.c b/src/edge.c index eb664d27..a0f5535f 100644 --- a/src/edge.c +++ b/src/edge.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: edge.c,v 1.1.2.11 2002/06/21 10:11:12 guus Exp $ + $Id: edge.c,v 1.1.2.12 2002/09/04 13:48:51 guus Exp $ */ #include "config.h" @@ -35,6 +35,8 @@ #include "conf.h" #include #include "subnet.h" +#include "edge.h" +#include "node.h" #include "xalloc.h" #include "system.h" @@ -46,12 +48,12 @@ int edge_compare(edge_t *a, edge_t *b) { int result; - result = strcmp(a->from.node->name, b->from.node->name); + result = strcmp(a->from->name, b->from->name); if(result) return result; else - return strcmp(a->to.node->name, b->to.node->name); + return strcmp(a->to->name, b->to->name); } /* Evil edge_compare() from a parallel universe ;) @@ -60,34 +62,11 @@ int edge_compare(edge_t *a, edge_t *b) { int result; - return (result = strcmp(a->from.node->name, b->from.node->name)) || (result = strcmp(a->to.node->name, b->to.node->name)), result; + return (result = strcmp(a->from->name, b->from->name)) || (result = strcmp(a->to->name, b->to->name)), result; } */ -int edge_name_compare(edge_t *a, edge_t *b) -{ - int result; - char *name_a1, *name_a2, *name_b1, *name_b2; - - if(strcmp(a->from.node->name, a->to.node->name) < 0) - name_a1 = a->from.node->name, name_a2 = a->to.node->name; - else - name_a1 = a->to.node->name, name_a2 = a->from.node->name; - - if(strcmp(b->from.node->name, b->to.node->name) < 0) - name_b1 = b->from.node->name, name_b2 = b->to.node->name; - else - name_b1 = b->to.node->name, name_b2 = b->from.node->name; - - result = strcmp(name_a1, name_b1); - - if(result) - return result; - else - return strcmp(name_a2, name_b2); -} - int edge_weight_compare(edge_t *a, edge_t *b) { int result; @@ -97,7 +76,7 @@ int edge_weight_compare(edge_t *a, edge_t *b) if(result) return result; else - return edge_name_compare(a, b); + return edge_compare(a, b); } void init_edges(void) @@ -111,7 +90,7 @@ cp avl_tree_t *new_edge_tree(void) { cp - return avl_alloc_tree((avl_compare_t)edge_name_compare, NULL); + return avl_alloc_tree((avl_compare_t)edge_compare, NULL); cp } @@ -152,35 +131,32 @@ void edge_add(edge_t *e) cp avl_insert(edge_tree, e); avl_insert(edge_weight_tree, e); - avl_insert(e->from.node->edge_tree, e); - avl_insert(e->to.node->edge_tree, e); + avl_insert(e->from->edge_tree, e); +cp + e->reverse = lookup_edge(e->to, e->from); + if(e->reverse) + e->reverse->reverse = e; cp } void edge_del(edge_t *e) { +cp + if(e->reverse) + e->reverse->reverse = NULL; cp avl_delete(edge_tree, e); avl_delete(edge_weight_tree, e); - avl_delete(e->from.node->edge_tree, e); - avl_delete(e->to.node->edge_tree, e); + avl_delete(e->from->edge_tree, e); cp } edge_t *lookup_edge(node_t *from, node_t *to) { - edge_t v, *result; -cp - v.from.node = from; - v.to.node = to; - - result = avl_search(edge_tree, &v); - - if(result) - return result; + edge_t v; cp - v.from.node = to; - v.to.node = from; + v.from = from; + v.to = to; return avl_search(edge_tree, &v); } @@ -189,21 +165,18 @@ void dump_edges(void) { avl_node_t *node; edge_t *e; - char *from_udp, *to_udp; + char *address; cp syslog(LOG_DEBUG, _("Edges:")); for(node = edge_tree->head; node; node = node->next) { e = (edge_t *)node->data; - from_udp = sockaddr2hostname(&e->from.udpaddress); - to_udp = sockaddr2hostname(&e->to.udpaddress); - syslog(LOG_DEBUG, _(" %s at %s - %s at %s options %lx weight %d"), - e->from.node->name, from_udp, - e->to.node->name, to_udp, + address = sockaddr2hostname(&e->address); + syslog(LOG_DEBUG, _(" %s to %s at %s options %lx weight %d"), + e->from->name, e->to->name, address, e->options, e->weight); - free(from_udp); - free(to_udp); + free(address); } syslog(LOG_DEBUG, _("End of edges.")); diff --git a/src/edge.h b/src/edge.h index 2e5b910d..e3735e63 100644 --- a/src/edge.h +++ b/src/edge.h @@ -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: edge.h,v 1.1.2.8 2002/06/21 10:11:12 guus Exp $ + $Id: edge.h,v 1.1.2.9 2002/09/04 13:48:51 guus Exp $ */ #ifndef __TINC_EDGE_H__ @@ -29,23 +29,19 @@ #include "node.h" #include "connection.h" -typedef struct halfconnection_t { - struct node_t *node; /* node associated with this end of the connection */ -// sockaddr_t tcpaddress; /* real (internet) ip on this end of the meta connection */ - sockaddr_t udpaddress; /* real (internet) ip on this end of the vpn connection */ -} halfconnection_t; - typedef struct edge_t { - struct halfconnection_t from; - struct halfconnection_t to; + struct node_t *from; + struct node_t *to; + sockaddr_t address; long int options; /* options turned on for this edge */ int weight; /* weight of this edge */ struct connection_t *connection; /* connection associated with this edge, if available */ + struct edge_t *reverse; /* edge in the opposite direction, if available */ } edge_t; -extern avl_tree_t *edge_tree; /* Tree with all known edges (replaces active_tree) */ +extern avl_tree_t *edge_tree; /* Tree with all known edges */ extern avl_tree_t *edge_weight_tree; /* Tree with all known edges sorted on weight */ extern void init_edges(void); diff --git a/src/graph.c b/src/graph.c index 7d9caf27..b5e81931 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.14 2002/07/10 11:27:06 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: @@ -109,7 +109,7 @@ void mst_kruskal(void) /* Starting point */ - ((edge_t *)edge_weight_tree->head->data)->from.node->status.visited = 1; + ((edge_t *)edge_weight_tree->head->data)->from->status.visited = 1; /* Add safe edges */ @@ -118,24 +118,25 @@ void mst_kruskal(void) next = node->next; e = (edge_t *)node->data; - if(e->from.node->status.visited == e->to.node->status.visited) + if(!e->reverse || e->from->status.visited == e->to->status.visited) { skipped = 1; continue; } - e->from.node->status.visited = 1; - e->to.node->status.visited = 1; + e->from->status.visited = 1; + e->to->status.visited = 1; if(e->connection) e->connection->status.mst = 1; 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); + 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; } @@ -154,7 +155,6 @@ void sssp_bfs(void) avl_node_t *node, *from, *next, *to; edge_t *e; node_t *n; - halfconnection_t to_hc, from_hc; avl_tree_t *todo_tree; int indirect; char *name; @@ -195,52 +195,50 @@ void sssp_bfs(void) 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.node == n) /* "from_hc" is the halfconnection with .node == from */ - to_hc = e->to, from_hc = e->from; - else - to_hc = e->from, from_hc = e->to; + + if(!e->reverse) + continue; /* Situation: / / - ------(n)from_hc-----to_hc + ------(n)-----(e->to) \ \ - n->address is set to the to_hc.udpaddress of the edge left of n. - We are currently examining the edge right of n: + 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 from_hc.udpaddress != n->address, then to_hc.node is probably + - 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 to_hc.node, update - to_hc.node and (re)add it to the todo_tree to (re)examine the reachability + - 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, &from_hc.udpaddress)); + indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address)); - if(to_hc.node->status.visited && (!to_hc.node->status.indirect || indirect)) + if(e->to->status.visited && (!e->to->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); - } + 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 = to_hc.node; + node->data = e->to; avl_insert_before(todo_tree, from, node); } @@ -257,7 +255,7 @@ void sssp_bfs(void) next = node->next; n = (node_t *)node->data; - if(n->status.visited ^ n->status.reachable) + if(n->status.visited != n->status.reachable) { n->status.reachable = !n->status.reachable; if(debug_lvl >= DEBUG_TRAFFIC) @@ -266,13 +264,9 @@ void sssp_bfs(void) else syslog(LOG_DEBUG, _("Node %s (%s) became unreachable"), n->name, n->hostname); - if(!n->status.reachable) - { - n->status.reachable = 0; - n->status.validkey = 0; - n->status.waitingforkey = 0; - n->sent_seqno = 0; - } + 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:""); diff --git a/src/net.c b/src/net.c index ca70886f..4a5c4b9f 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.175 2002/09/03 20:43:25 guus Exp $ + $Id: net.c,v 1.35.4.176 2002/09/04 13:48:51 guus Exp $ */ #include "config.h" @@ -65,6 +65,7 @@ #include "process.h" #include "protocol.h" #include "subnet.h" +#include "graph.h" #include "process.h" #include "route.h" #include "device.h" @@ -82,12 +83,13 @@ int sigalrm = 0; time_t now = 0; -/* Purge subnets of unreachable nodes. Use carefully. */ +/* Purge edges and subnets of unreachable nodes. Use carefully. */ void purge(void) { - avl_node_t *nnode, *nnext, *snode, *snext, *cnode; + avl_node_t *nnode, *nnext, *enode, *enext, *snode, *snext, *cnode; node_t *n; + edge_t *e; subnet_t *s; connection_t *c; cp @@ -119,6 +121,21 @@ cp subnet_del(n, s); } + for(enode = n->edge_tree->head; enode; enode = enext) + { + enext = enode->next; + e = (edge_t *)enode->data; + + for(cnode = connection_tree->head; cnode; cnode = cnode->next) + { + c = (connection_t *)cnode->data; + if(c->status.active) + send_del_edge(c, e); + } + + edge_del(e); + } + node_del(n); } } @@ -165,15 +182,14 @@ cp /* Terminate a connection: - Close the socket - - Tell other connections about it if report = 1 + - Remove associated edge and tell other connections about it if report = 1 - Check if we need to retry making an outgoing connection - Deactivate the host */ void terminate_connection(connection_t *c, int report) { - avl_node_t *node, *node2; + avl_node_t *node; connection_t *other; - node_t *n; cp if(c->status.remove) return; @@ -186,30 +202,29 @@ cp c->status.active = 0; if(c->node) + c->node->connection = NULL; + + if(c->socket) + close(c->socket); + + if(c->edge) { - if(report && c->node->connection) + if(report) { for(node = connection_tree->head; node; node = node->next) { other = (connection_t *)node->data; - if(other == c) - continue; - for(node2 = node_tree->head; node2; node2 = node2->next) - { - n = (node_t *)node2->data; - if(n->nexthop == c->node) - { - send_del_node(other, n); - n->status.reachable = 0; - } - } + if(other->status.active && other != c) + send_del_edge(other, c->edge); } } - c->node->connection = NULL; - } - if(c->socket) - close(c->socket); + edge_del(c->edge); + + /* Run MST and SSSP algorithms */ + + graph(); + } /* Check if this was our outgoing connection */ @@ -231,13 +246,14 @@ cp */ void check_dead_connections(void) { - avl_node_t *node; + avl_node_t *node, *next; connection_t *c; cp - for(node = connection_tree->head; node; node = node->next) + for(node = connection_tree->head; node; node = next) { + next = node->next; c = (connection_t *)node->data; - if(c->last_ping_time + pingtimeout < now && !c->status.remove) + if(c->last_ping_time + pingtimeout < now) { if(c->status.active) { diff --git a/src/net_packet.c b/src/net_packet.c index bd1e4e21..8419d6a0 100644 --- a/src/net_packet.c +++ b/src/net_packet.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_packet.c,v 1.1.2.18 2002/09/03 20:43:25 guus Exp $ + $Id: net_packet.c,v 1.1.2.19 2002/09/04 13:48:52 guus Exp $ */ #include "config.h" @@ -70,6 +70,7 @@ #include "process.h" #include "protocol.h" #include "subnet.h" +#include "graph.h" #include "process.h" #include "route.h" #include "device.h" @@ -331,7 +332,7 @@ cp return; } - via = (n->options & OPTION_INDIRECT)?n->nexthop:n; + via = (n->via == myself)?n->nexthop:n->via; if(via != n && debug_lvl >= DEBUG_TRAFFIC) syslog(LOG_ERR, _("Sending packet to %s via %s (%s)"), diff --git a/src/net_setup.c b/src/net_setup.c index edbcbf54..fe7a562d 100644 --- a/src/net_setup.c +++ b/src/net_setup.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_setup.c,v 1.1.2.22 2002/09/03 20:43:25 guus Exp $ + $Id: net_setup.c,v 1.1.2.23 2002/09/04 13:48:52 guus Exp $ */ #include "config.h" @@ -67,6 +67,7 @@ #include "process.h" #include "protocol.h" #include "subnet.h" +#include "graph.h" #include "process.h" #include "route.h" #include "device.h" @@ -463,6 +464,8 @@ cp myself->status.reachable = 1; node_add(myself); + graph(); + cp /* Open sockets */ @@ -528,6 +531,7 @@ cp init_connections(); init_subnets(); init_nodes(); + init_edges(); init_events(); init_requests(); @@ -593,6 +597,7 @@ cp exit_requests(); exit_events(); + exit_edges(); exit_subnets(); exit_nodes(); exit_connections(); diff --git a/src/net_socket.c b/src/net_socket.c index e0cec2c8..0281d655 100644 --- a/src/net_socket.c +++ b/src/net_socket.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_socket.c,v 1.1.2.17 2002/09/03 20:43:25 guus Exp $ + $Id: net_socket.c,v 1.1.2.18 2002/09/04 13:48:52 guus Exp $ */ #include "config.h" @@ -63,6 +63,7 @@ #include "process.h" #include "protocol.h" #include "subnet.h" +#include "graph.h" #include "process.h" #include "route.h" #include "device.h" @@ -146,7 +147,7 @@ cp return -1; } - if(listen(nfd, 0)) + if(listen(nfd, 3)) { close(nfd); syslog(LOG_ERR, _("System call `%s' failed: %s"), "listen", strerror(errno)); diff --git a/src/node.c b/src/node.c index adc3a74d..a66bc177 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.14 2002/09/03 20:43:25 guus Exp $ + $Id: node.c,v 1.1.2.15 2002/09/04 13:48:52 guus Exp $ */ #include "config.h" @@ -77,6 +77,7 @@ node_t *new_node(void) node_t *n = (node_t *)xmalloc_and_zero(sizeof(*n)); cp n->subnet_tree = new_subnet_tree(); + n->edge_tree = new_edge_tree(); n->queue = list_alloc((list_action_t)free); cp return n; @@ -95,6 +96,8 @@ cp free(n->key); if(n->subnet_tree) free_subnet_tree(n->subnet_tree); + if(n->edge_tree) + free_edge_tree(n->edge_tree); free(n); cp } @@ -110,6 +113,7 @@ 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) @@ -118,6 +122,13 @@ cp s = (subnet_t *)node->data; subnet_del(n, s); } + + for(node = n->edge_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); @@ -152,9 +163,9 @@ cp for(node = node_tree->head; node; node = node->next) { n = (node_t *)node->data; - syslog(LOG_DEBUG, _(" %s at %s cipher %d digest %d maclength %d compression %d options %lx status %04x nexthop %s distance %d"), + syslog(LOG_DEBUG, _(" %s at %s cipher %d digest %d maclength %d compression %d options %lx status %04x nexthop %s via %s"), n->name, n->hostname, n->cipher?n->cipher->nid:0, n->digest?n->digest->type:0, n->maclength, n->compression, n->options, - n->status, n->nexthop?n->nexthop->name:"-", n->distance); + n->status, n->nexthop?n->nexthop->name:"-", n->via?n->via->name:"-"); } syslog(LOG_DEBUG, _("End of nodes.")); diff --git a/src/node.h b/src/node.h index f2bea91b..8f6b30ff 100644 --- a/src/node.h +++ b/src/node.h @@ -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.h,v 1.1.2.18 2002/09/04 08:33:08 guus Exp $ + $Id: node.h,v 1.1.2.19 2002/09/04 13:48:52 guus Exp $ */ #ifndef __TINC_NODE_H__ @@ -51,8 +51,6 @@ typedef struct node_t { struct node_status_t status; - int distance; /* Distance from us to that node */ - const EVP_CIPHER *cipher; /* Cipher type for UDP packets */ char *key; /* Cipher key and iv */ int keylength; /* Cipher key and iv length*/ @@ -65,11 +63,12 @@ typedef struct node_t { list_t *queue; /* Queue for packets awaiting to be encrypted */ struct node_t *nexthop; /* nearest node from us to him */ - struct node_t *prevhop; /* nearest node from him to us */ struct node_t *via; /* next hop for UDP packets */ avl_tree_t *subnet_tree; /* Pointer to a tree of subnets belonging to this node */ + avl_tree_t *edge_tree; /* Edges with this node as one of the endpoints */ + struct connection_t *connection; /* Connection associated with this node (if a direct connection exists) */ uint32_t sent_seqno; /* Sequence number last sent to this node */ diff --git a/src/protocol.c b/src/protocol.c index 91c4ef3a..644e89e9 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.131 2002/09/04 08:02:33 guus Exp $ + $Id: protocol.c,v 1.28.4.132 2002/09/04 13:48:52 guus Exp $ */ #include "config.h" @@ -62,15 +62,8 @@ int send_request(connection_t *c, const char *format, ...) va_list args; char buffer[MAXBUFSIZE]; int len, request; - char *name = "everyone"; - char *hostname = "broadcast"; -cp - if(c) - { - name = c->name; - hostname = c->hostname; - } +cp /* Use vsnprintf instead of vasprintf: faster, no memory fragmentation, cleanup is automatic, and there is a limit on the input buffer anyway */ @@ -81,7 +74,7 @@ cp if(len < 0 || len > MAXBUFSIZE-1) { - syslog(LOG_ERR, _("Output buffer overflow while sending request to %s (%s)"), name, hostname); + syslog(LOG_ERR, _("Output buffer overflow while sending request to %s (%s)"), c->name, c->hostname); return -1; } @@ -89,17 +82,14 @@ cp { sscanf(buffer, "%d", &request); if(debug_lvl >= DEBUG_META) - syslog(LOG_DEBUG, _("Sending %s to %s (%s): %s"), request_name[request], name, hostname, buffer); + syslog(LOG_DEBUG, _("Sending %s to %s (%s): %s"), request_name[request], c->name, c->hostname, buffer); else - syslog(LOG_DEBUG, _("Sending %s to %s (%s)"), request_name[request], name, hostname); + syslog(LOG_DEBUG, _("Sending %s to %s (%s)"), request_name[request], c->name, c->hostname); } buffer[len++] = '\n'; cp - if(c) - return send_meta(c, buffer, len); - else - return broadcast_meta(NULL, buffer, len); + return send_meta(c, buffer, len); } int receive_request(connection_t *c) @@ -236,7 +226,7 @@ int (*request_handlers[])(connection_t*) = { status_h, error_h, termreq_h, ping_h, pong_h, add_subnet_h, del_subnet_h, - add_node_h, del_node_h, + add_edge_h, del_edge_h, key_changed_h, req_key_h, ans_key_h, tcppacket_h, }; @@ -248,7 +238,7 @@ char (*request_name[]) = { "STATUS", "ERROR", "TERMREQ", "PING", "PONG", "ADD_SUBNET", "DEL_SUBNET", - "ADD_NODE", "DEL_NODE", + "ADD_EDGE", "DEL_EDGE", "KEY_CHANGED", "REQ_KEY", "ANS_KEY", "PACKET", }; diff --git a/src/protocol.h b/src/protocol.h index 1fd760a2..a021f4fe 100644 --- a/src/protocol.h +++ b/src/protocol.h @@ -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.h,v 1.5.4.32 2002/09/04 08:33:08 guus Exp $ + $Id: protocol.h,v 1.5.4.33 2002/09/04 13:48:52 guus Exp $ */ #ifndef __TINC_PROTOCOL_H__ @@ -25,13 +25,14 @@ #include "net.h" #include "node.h" +#include "edge.h" #include "subnet.h" /* Protocol version. Different versions are incompatible, incompatible version have different protocols. */ -#define PROT_CURRENT 16 +#define PROT_CURRENT 17 /* Request numbers */ @@ -40,8 +41,9 @@ enum { ID = 0, METAKEY, CHALLENGE, CHAL_REPLY, ACK, STATUS, ERROR, TERMREQ, PING, PONG, +// ADD_NODE, DEL_NODE, ADD_SUBNET, DEL_SUBNET, - ADD_NODE, DEL_NODE, + ADD_EDGE, DEL_EDGE, KEY_CHANGED, REQ_KEY, ANS_KEY, PACKET, LAST /* Guardian for the highest request number */ @@ -80,10 +82,12 @@ extern int send_error(connection_t *, int, char *); extern int send_termreq(connection_t *); extern int send_ping(connection_t *); extern int send_pong(connection_t *); +// extern int send_add_node(connection_t *, node_t *); +// extern int send_del_node(connection_t *, node_t *); extern int send_add_subnet(connection_t *, subnet_t *); extern int send_del_subnet(connection_t *, subnet_t *); -extern int send_add_node(connection_t *, node_t *); -extern int send_del_node(connection_t *, node_t *); +extern int send_add_edge(connection_t *, edge_t *); +extern int send_del_edge(connection_t *, edge_t *); extern int send_key_changed(connection_t *, node_t *); extern int send_req_key(connection_t *, node_t *, node_t *); extern int send_ans_key(connection_t *, node_t *, node_t *); @@ -103,10 +107,12 @@ extern int error_h(connection_t *); extern int termreq_h(connection_t *); extern int ping_h(connection_t *); extern int pong_h(connection_t *); +// extern int add_node_h(connection_t *); +// extern int del_node_h(connection_t *); extern int add_subnet_h(connection_t *); extern int del_subnet_h(connection_t *); -extern int add_node_h(connection_t *); -extern int del_node_h(connection_t *); +extern int add_edge_h(connection_t *); +extern int del_edge_h(connection_t *); extern int key_changed_h(connection_t *); extern int req_key_h(connection_t *); extern int ans_key_h(connection_t *); diff --git a/src/protocol_auth.c b/src/protocol_auth.c index 6563470c..14914ba8 100644 --- a/src/protocol_auth.c +++ b/src/protocol_auth.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_auth.c,v 1.1.4.11 2002/09/04 08:36:34 guus Exp $ + $Id: protocol_auth.c,v 1.1.4.12 2002/09/04 13:48:52 guus Exp $ */ #include "config.h" @@ -48,6 +48,8 @@ #include "meta.h" #include "connection.h" #include "node.h" +#include "edge.h" +#include "graph.h" #include "system.h" @@ -460,20 +462,16 @@ cp int send_ack(connection_t *c) { /* ACK message contains rest of the information the other end needs - to create node_t structures. */ + to create node_t and edge_t structures. */ int x; - char *address, *port; struct timeval now; cp /* Estimate weight */ gettimeofday(&now, NULL); c->estimated_weight = (now.tv_sec - c->start.tv_sec) * 1000 + (now.tv_usec - c->start.tv_usec) / 1000; - sockaddr2str(&c->address, &address, &port); - x = send_request(c, "%d %s %s %lx", ACK, myport, address, c->options); - free(address); - free(port); + x = send_request(c, "%d %s %s %d %lx", ACK, myport, c->estimated_weight, c->options); cp return x; } @@ -483,16 +481,13 @@ void send_everything(connection_t *c) avl_node_t *node, *node2; node_t *n; subnet_t *s; - connection_t *other; + edge_t *e; - /* Send all known nodes and subnets */ + /* Send all known subnets */ for(node = node_tree->head; node; node = node->next) { n = (node_t *)node->data; - - if(n != c->node && n != myself) - send_add_node(c, n); for(node2 = n->subnet_tree->head; node2; node2 = node2->next) { @@ -501,27 +496,27 @@ void send_everything(connection_t *c) } } - /* Inform others of this new node */ - - for(node = connection_tree->head; node; node = node->next) + /* Send all known edges */ + + for(node = edge_tree->head; node; node = node->next) { - other = (connection_t *)node->data; - - if(other->status.active && other != c) - send_add_node(other, c->node); + e = (edge_t *)node->data; + + send_add_edge(c, e); } } int ack_h(connection_t *c) { - char myaddress[MAX_STRING_SIZE]; char hisport[MAX_STRING_SIZE]; char *hisaddress, *dummy; + int weight; long int options; node_t *n; + connection_t *other; avl_node_t *node; cp - if(sscanf(c->buffer, "%*d "MAX_STRING" "MAX_STRING" %lx", hisport, myaddress, &options) != 3) + if(sscanf(c->buffer, "%*d "MAX_STRING" %d %lx", hisport, &weight, &options) != 3) { syslog(LOG_ERR, _("Got bad %s from %s (%s)"), "ACK", c->name, c->hostname); return -1; @@ -546,27 +541,29 @@ cp syslog(LOG_DEBUG, _("Established a second connection with %s (%s), closing old connection"), n->name, n->hostname); terminate_connection(n->connection, 0); } + + /* FIXME: check if information in existing node matches that of the other end of this connection */ } + n->connection = c; c->node = n; c->options |= options; - c->myaddress = str2sockaddr(myaddress, myport); - - n->connection = c; + + /* Create an edge_t for this connection */ + + c->edge = new_edge(); +cp + c->edge->from = myself; + c->edge->to = n; sockaddr2str(&c->address, &hisaddress, &dummy); - node = avl_unlink(node_udp_tree, n); - n->address = str2sockaddr(hisaddress, hisport); - avl_insert_node(node_udp_tree, node); - if(n->hostname) - free(n->hostname); - n->hostname = sockaddr2hostname(&n->address); - n->options = c->options; - n->distance = 1; - n->via = n->nexthop = n; - n->prevhop = myself; - n->status.reachable = 1; - n->status.validkey = 0; - n->status.waitingforkey = 0; + c->edge->address = str2sockaddr(hisaddress, hisport); + free(hisaddress); + free(dummy); + c->edge->weight = (weight + c->estimated_weight) / 2; + c->edge->connection = c; + c->edge->options = c->options; +cp + edge_add(c->edge); /* Activate this connection */ @@ -577,9 +574,23 @@ cp syslog(LOG_NOTICE, _("Connection with %s (%s) activated"), c->name, c->hostname); cp - /* Send him everything we know and tell the others about him */ + /* Send him everything we know */ send_everything(c); + + /* Notify others of this connection */ + + for(node = connection_tree->head; node; node = node->next) + { + other = (connection_t *)node->data; + + if(other->status.active && other != c) + send_add_edge(other, c->edge); + } + + /* Run MST and SSSP algorithms */ + + graph(); cp return 0; } diff --git a/src/protocol_edge.c b/src/protocol_edge.c index a13a096a..9b35a9fb 100644 --- a/src/protocol_edge.c +++ b/src/protocol_edge.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_edge.c,v 1.1.4.8 2002/06/21 10:11:19 guus Exp $ + $Id: protocol_edge.c,v 1.1.4.9 2002/09/04 13:48:52 guus Exp $ */ #include "config.h" @@ -48,19 +48,14 @@ int send_add_edge(connection_t *c, edge_t *e) { int x; - char *from_udpaddress, *from_udpport; - char *to_udpaddress, *to_udpport; + char *address, *port; cp - sockaddr2str(&e->from.udpaddress, &from_udpaddress, &from_udpport); - sockaddr2str(&e->to.udpaddress, &to_udpaddress, &to_udpport); - x = send_request(c, "%d %lx %s %s %s %s %s %s %lx %d", ADD_EDGE, random(), - e->from.node->name, from_udpaddress, from_udpport, - e->to.node->name, to_udpaddress, to_udpport, + sockaddr2str(&e->address, &address, &port); + x = send_request(c, "%d %lx %s %s %s %s %lx %d", ADD_EDGE, random(), + e->from->name, e->to->name, address, port, e->options, e->weight); - free(from_udpaddress); - free(from_udpport); - free(to_udpaddress); - free(to_udpport); + free(address); + free(port); cp return x; } @@ -72,20 +67,15 @@ int add_edge_h(connection_t *c) node_t *from, *to; char from_name[MAX_STRING_SIZE]; char to_name[MAX_STRING_SIZE]; - char from_address[MAX_STRING_SIZE]; - char from_udpport[MAX_STRING_SIZE]; char to_address[MAX_STRING_SIZE]; - char to_udpport[MAX_STRING_SIZE]; - sockaddr_t from_udpaddress; - sockaddr_t to_udpaddress; + char to_port[MAX_STRING_SIZE]; + sockaddr_t address; long int options; int weight; avl_node_t *node; cp - if(sscanf(c->buffer, "%*d %*x "MAX_STRING" "MAX_STRING" "MAX_STRING" "MAX_STRING" "MAX_STRING" "MAX_STRING" %lx %d", - from_name, from_address, from_udpport, - to_name, to_address, to_udpport, - &options, &weight) != 8) + if(sscanf(c->buffer, "%*d %*x "MAX_STRING" "MAX_STRING" "MAX_STRING" "MAX_STRING" %lx %d", + from_name, to_name, to_address, to_port, &options, &weight) != 6) { syslog(LOG_ERR, _("Got bad %s from %s (%s)"), "ADD_EDGE", c->name, c->hostname); return -1; @@ -130,8 +120,7 @@ cp /* Convert addresses */ - from_udpaddress = str2sockaddr(from_address, from_udpport); - to_udpaddress = str2sockaddr(to_address, to_udpport); + address = str2sockaddr(to_address, to_port); /* Check if edge already exists */ @@ -139,12 +128,9 @@ cp if(e) { - if(e->weight != weight || e->options != options - || ((e->from.node == from) && (sockaddrcmp(&e->from.udpaddress, &from_udpaddress)|| sockaddrcmp(&e->to.udpaddress, &to_udpaddress))) - || ((e->from.node == to) && (sockaddrcmp(&e->from.udpaddress, &to_udpaddress) || sockaddrcmp(&e->to.udpaddress, &from_udpaddress))) - ) + if(e->weight != weight || e->options != options || sockaddrcmp(&e->address, &address)) { - if(from == myself || to == myself) + if(from == myself) { if(debug_lvl >= DEBUG_PROTOCOL) syslog(LOG_WARNING, _("Got %s from %s (%s) for ourself which does not match existing entry"), "ADD_EDGE", c->name, c->hostname); @@ -161,23 +147,22 @@ cp else return 0; } - else if(from == myself || to == myself) + else if(from == myself) { if(debug_lvl >= DEBUG_PROTOCOL) syslog(LOG_WARNING, _("Got %s from %s (%s) for ourself which does not exist"), "ADD_EDGE", c->name, c->hostname); e = new_edge(); - e->from.node = from; - e->to.node = to; + e->from = from; + e->to = to; send_del_edge(c, e); free_edge(e); return 0; } e = new_edge(); - e->from.node = from; - e->from.udpaddress = from_udpaddress; - e->to.node = to; - e->to.udpaddress = to_udpaddress; + e->from = from; + e->to = to; + e->address = address; e->options = options; e->weight = weight; edge_add(e); @@ -202,7 +187,7 @@ int send_del_edge(connection_t *c, edge_t *e) { cp return send_request(c, "%d %lx %s %s", DEL_EDGE, random(), - e->from.node->name, e->to.node->name); + e->from->name, e->to->name); } int del_edge_h(connection_t *c) @@ -269,7 +254,7 @@ cp return 0; } - if(e->from.node == myself || e->to.node == myself) + if(e->from == myself) { if(debug_lvl >= DEBUG_PROTOCOL) syslog(LOG_WARNING, _("Got %s from %s (%s) for ourself"), "DEL_EDGE", c->name, c->hostname); -- 2.39.5