tinc-vpn.org Git - tinc/blob - src/graph.c

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001-2002 Guus Sliepen <guus@sliepen.eu.org>,
   4                   2001-2002 Ivo Timmermans <ivo@o2w.nl>
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19
  20     $Id: graph.c,v 1.1.2.14 2002/07/10 11:27:06 guus Exp $
  21 */
  22
  23 /* We need to generate two trees from the graph:
  24
  25    1. A minimum spanning tree for broadcasts,
  26    2. A single-source shortest path tree for unicasts.
  27
  28    Actually, the first one alone would suffice but would make unicast packets
  29    take longer routes than necessary.
  30
  31    For the MST algorithm we can choose from Prim's or Kruskal's. I personally
  32    favour Kruskal's, because we make an extra AVL tree of edges sorted on
  33    weights (metric). That tree only has to be updated when an edge is added or
  34    removed, and during the MST algorithm we just have go linearly through that
  35    tree, adding safe edges until #edges = #nodes - 1. The implementation here
  36    however is not so fast, because I tried to avoid having to make a forest and
  37    merge trees.
  38
  39    For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
  40    simple breadth-first search is presented here.
  41
  42    The SSSP algorithm will also be used to determine whether nodes are directly,
  43    indirectly or not reachable from the source. It will also set the correct
  44    destination address and port of a node if possible.
  45 */
  46
  47 #include "config.h"
  48
  49 #include <stdio.h>
  50 #include <syslog.h>
  51 #include "config.h"
  52 #include <string.h>
  53 #ifdef HAVE_SYS_PARAM_H
  54  #include <sys/param.h>
  55 #endif
  56 #include <netinet/in.h>
  57
  58 #include <avl_tree.h>
  59 #include <utils.h>
  60
  61 #include "netutl.h"
  62 #include "node.h"
  63 #include "edge.h"
  64 #include "connection.h"
  65 #include "process.h"
  66 #include "device.h"
  67
  68 #include "system.h"
  69
  70 /* Implementation of Kruskal's algorithm.
  71    Running time: O(EN)
  72    Please note that sorting on weight is already done by add_edge().
  73 */
  74
  75 void mst_kruskal(void)
  76 {
  77   avl_node_t *node, *next;
  78   edge_t *e;
  79   node_t *n;
  80   connection_t *c;
  81   int nodes = 0;
  82   int safe_edges = 0;
  83   int skipped;
  84
  85   /* Clear MST status on connections */
  86
  87   for(node = connection_tree->head; node; node = node->next)
  88     {
  89       c = (connection_t *)node->data;
  90       c->status.mst = 0;
  91     }
  92
  93   /* Do we have something to do at all? */
  94
  95   if(!edge_weight_tree->head)
  96     return;
  97
  98   if(debug_lvl >= DEBUG_SCARY_THINGS)
  99     syslog(LOG_DEBUG, "Running Kruskal's algorithm:");
 100
 101   /* Clear visited status on nodes */
 102
 103   for(node = node_tree->head; node; node = node->next)
 104     {
 105       n = (node_t *)node->data;
 106       n->status.visited = 0;
 107       nodes++;
 108     }
 109
 110   /* Starting point */
 111
 112   ((edge_t *)edge_weight_tree->head->data)->from.node->status.visited = 1;
 113
 114   /* Add safe edges */
 115
 116   for(skipped = 0, node = edge_weight_tree->head; node; node = next)
 117     {
 118       next = node->next;
 119       e = (edge_t *)node->data;
 120
 121       if(e->from.node->status.visited == e->to.node->status.visited)
 122         {
 123           skipped = 1;
 124           continue;
 125         }
 126
 127       e->from.node->status.visited = 1;
 128       e->to.node->status.visited = 1;
 129       if(e->connection)
 130         e->connection->status.mst = 1;
 131
 132       safe_edges++;
 133
 134       if(debug_lvl >= DEBUG_SCARY_THINGS)
 135         syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from.node->name, e->to.node->name, e->weight);
 136
 137       if(skipped)
 138         {
 139           next = edge_weight_tree->head;
 140           continue;
 141         }
 142     }
 143
 144   if(debug_lvl >= DEBUG_SCARY_THINGS)
 145     syslog(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes, safe_edges);
 146 }
 147
 148 /* Implementation of a simple breadth-first search algorithm.
 149    Running time: O(E)
 150 */
 151
 152 void sssp_bfs(void)
 153 {
 154   avl_node_t *node, *from, *next, *to;
 155   edge_t *e;
 156   node_t *n;
 157   halfconnection_t to_hc, from_hc;
 158   avl_tree_t *todo_tree;
 159   int indirect;
 160   char *name;
 161   char *address, *port;
 162   char *envp[7];
 163   int i;
 164
 165   todo_tree = avl_alloc_tree(NULL, NULL);
 166
 167   /* Clear visited status on nodes */
 168
 169   for(node = node_tree->head; node; node = node->next)
 170     {
 171       n = (node_t *)node->data;
 172       n->status.visited = 0;
 173       n->status.indirect = 1;
 174     }
 175
 176   /* Begin with myself */
 177
 178   myself->status.visited = 1;
 179   myself->status.indirect = 0;
 180   myself->nexthop = myself;
 181   myself->via = myself;
 182   node = avl_alloc_node();
 183   node->data = myself;
 184   avl_insert_top(todo_tree, node);
 185
 186   /* Loop while todo_tree is filled */
 187
 188   while(todo_tree->head)
 189     {
 190       for(from = todo_tree->head; from; from = next)             /* "from" is the node from which we start */
 191         {
 192           next = from->next;
 193           n = (node_t *)from->data;
 194
 195           for(to = n->edge_tree->head; to; to = to->next)        /* "to" is the edge connected to "from" */
 196             {
 197               e = (edge_t *)to->data;
 198
 199               if(e->from.node == n)                              /* "from_hc" is the halfconnection with .node == from */
 200                 to_hc = e->to, from_hc = e->from;
 201               else
 202                 to_hc = e->from, from_hc = e->to;
 203
 204               /* Situation:
 205
 206                           /
 207                          /
 208                  ------(n)from_hc-----to_hc
 209                          \
 210                           \
 211
 212                  n->address is set to the to_hc.udpaddress of the edge left of n.
 213                  We are currently examining the edge right of n:
 214
 215                  - If from_hc.udpaddress != n->address, then to_hc.node is probably
 216                    not reachable for the nodes left of n. We do as if the indirectdata
 217                    flag is set on edge e.
 218                  - If edge e provides for better reachability of to_hc.node, update
 219                    to_hc.node and (re)add it to the todo_tree to (re)examine the reachability
 220                    of nodes behind it.
 221               */
 222
 223               indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &from_hc.udpaddress));
 224
 225               if(to_hc.node->status.visited && (!to_hc.node->status.indirect || indirect))
 226                 continue;
 227
 228               to_hc.node->status.visited = 1;
 229               to_hc.node->status.indirect = indirect;
 230               to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop;
 231               to_hc.node->via = indirect ? n->via : to_hc.node;
 232               to_hc.node->options = e->options;
 233               if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress))
 234               {
 235                 node = avl_unlink(node_udp_tree, to_hc.node);
 236                 to_hc.node->address = to_hc.udpaddress;
 237                 if(to_hc.node->hostname)
 238                   free(to_hc.node->hostname);
 239                 to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress);
 240                 avl_insert_node(node_udp_tree, node);
 241               }
 242               node = avl_alloc_node();
 243               node->data = to_hc.node;
 244               avl_insert_before(todo_tree, from, node);
 245             }
 246
 247           avl_delete_node(todo_tree, from);
 248         }
 249     }
 250
 251   avl_free_tree(todo_tree);
 252
 253   /* Check reachability status. */
 254
 255   for(node = node_tree->head; node; node = next)
 256     {
 257       next = node->next;
 258       n = (node_t *)node->data;
 259
 260       if(n->status.visited ^ n->status.reachable)
 261       {
 262         n->status.reachable = !n->status.reachable;
 263         if(debug_lvl >= DEBUG_TRAFFIC)
 264           if(n->status.reachable)
 265             syslog(LOG_DEBUG, _("Node %s (%s) became reachable"), n->name, n->hostname);
 266           else
 267             syslog(LOG_DEBUG, _("Node %s (%s) became unreachable"), n->name, n->hostname);
 268
 269           if(!n->status.reachable)
 270             {
 271               n->status.reachable = 0;
 272               n->status.validkey = 0;
 273               n->status.waitingforkey = 0;
 274               n->sent_seqno = 0;
 275             }
 276
 277         asprintf(&envp[0], "NETNAME=%s", netname?netname:"");
 278         asprintf(&envp[1], "DEVICE=%s", device?device:"");
 279         asprintf(&envp[2], "INTERFACE=%s", interface?interface:"");
 280         asprintf(&envp[3], "NODE=%s", n->name);
 281         sockaddr2str(&n->address, &address, &port);
 282         asprintf(&envp[4], "REMOTEADDRESS=%s", address);
 283         asprintf(&envp[5], "REMOTEPORT=%s", port);
 284         envp[6] = NULL;
 285
 286         asprintf(&name, n->status.reachable?"hosts/%s-up":"hosts/%s-down", n->name);
 287         execute_script(name, envp);
 288         free(name);
 289         free(address);
 290         free(port);
 291
 292         for(i = 0; i < 7; i++)
 293           free(envp[i]);
 294       }
 295     }
 296 }
 297
 298 void graph(void)
 299 {
 300   mst_kruskal();
 301   sssp_bfs();
 302 }