Revert to edge and graph stuff. This time, use a directed graph.
authorGuus Sliepen <guus@tinc-vpn.org>
Wed, 4 Sep 2002 13:48:52 +0000 (13:48 +0000)
committerGuus Sliepen <guus@tinc-vpn.org>
Wed, 4 Sep 2002 13:48:52 +0000 (13:48 +0000)
15 files changed:
src/Makefile.am
src/connection.h
src/edge.c
src/edge.h
src/graph.c
src/net.c
src/net_packet.c
src/net_setup.c
src/net_socket.c
src/node.c
src/node.h
src/protocol.c
src/protocol.h
src/protocol_auth.c
src/protocol_edge.c

index cc1cdc3..d8d8fd9 100644 (file)
@@ -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@
index fdc87d7..a6d8c58 100644 (file)
@@ -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 */
index eb664d2..a0f5535 100644 (file)
@@ -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 <utils.h>
 #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."));
index 2e5b910..e3735e6 100644 (file)
@@ -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__
 #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);
index 7d9caf2..b5e8193 100644 (file)
@@ -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:"");
index ca70886..4a5c4b9 100644 (file)
--- 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)
             {
index bd1e4e2..8419d6a 100644 (file)
@@ -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)"),
index edbcbf5..fe7a562 100644 (file)
@@ -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();
index e0cec2c..0281d65 100644 (file)
@@ -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));
index adc3a74..a66bc17 100644 (file)
@@ -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."));
index f2bea91..8f6b30f 100644 (file)
@@ -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 */
index 91c4ef3..644e89e 100644 (file)
@@ -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",
 };
index 1fd760a..a021f4f 100644 (file)
@@ -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__
 
 #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 *);
index 6563470..14914ba 100644 (file)
@@ -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;
 }
index a13a096..9b35a9f 100644 (file)
@@ -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"
 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);