src/graph.c

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001-2009 Guus Sliepen <guus@tinc-vpn.org>,
   4                   2001-2005 Ivo Timmermans
   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
  21 /* We need to generate two trees from the graph:
  22
  23    1. A minimum spanning tree for broadcasts,
  24    2. A single-source shortest path tree for unicasts.
  25
  26    Actually, the first one alone would suffice but would make unicast packets
  27    take longer routes than necessary.
  28
  29    For the MST algorithm we can choose from Prim's or Kruskal's. I personally
  30    favour Kruskal's, because we make an extra AVL tree of edges sorted on
  31    weights (metric). That tree only has to be updated when an edge is added or
  32    removed, and during the MST algorithm we just have go linearly through that
  33    tree, adding safe edges until #edges = #nodes - 1. The implementation here
  34    however is not so fast, because I tried to avoid having to make a forest and
  35    merge trees.
  36
  37    For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
  38    simple breadth-first search is presented here.
  39
  40    The SSSP algorithm will also be used to determine whether nodes are directly,
  41    indirectly or not reachable from the source. It will also set the correct
  42    destination address and port of a node if possible.
  43 */
  44
  45 #include "system.h"
  46
  47 #include "avl_tree.h"
  48 #include "config.h"
  49 #include "connection.h"
  50 #include "device.h"
  51 #include "edge.h"
  52 #include "logger.h"
  53 #include "netutl.h"
  54 #include "node.h"
  55 #include "process.h"
  56 #include "subnet.h"
  57 #include "utils.h"
  58 #include "xalloc.h"
  59
  60 static bool graph_changed = true;
  61
  62 /* Implementation of Kruskal's algorithm.
  63    Running time: O(EN)
  64    Please note that sorting on weight is already done by add_edge().
  65 */
  66
  67 void mst_kruskal(void)
  68 {
  69         avl_node_t *node, *next;
  70         edge_t *e;
  71         node_t *n;
  72         connection_t *c;
  73         int nodes = 0;
  74         int safe_edges = 0;
  75         bool skipped;
  76
  77         cp();
  78
  79         /* Clear MST status on connections */
  80
  81         for(node = connection_tree->head; node; node = node->next) {
  82                 c = node->data;
  83                 c->status.mst = false;
  84         }
  85
  86         /* Do we have something to do at all? */
  87
  88         if(!edge_weight_tree->head)
  89                 return;
  90
  91         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:");
  92
  93         /* Clear visited status on nodes */
  94
  95         for(node = node_tree->head; node; node = node->next) {
  96                 n = node->data;
  97                 n->status.visited = false;
  98                 nodes++;
  99         }
 100
 101         /* Starting point */
 102
 103         for(node = edge_weight_tree->head; node; node = node->next) {
 104                 e = node->data;
 105                 if(e->from->status.reachable) {
 106                         e->from->status.visited = true;
 107                         break;
 108                 }
 109         }
 110
 111         /* Add safe edges */
 112
 113         for(skipped = false, node = edge_weight_tree->head; node; node = next) {
 114                 next = node->next;
 115                 e = node->data;
 116
 117                 if(!e->reverse || e->from->status.visited == e->to->status.visited) {
 118                         skipped = true;
 119                         continue;
 120                 }
 121
 122                 e->from->status.visited = true;
 123                 e->to->status.visited = true;
 124
 125                 if(e->connection)
 126                         e->connection->status.mst = true;
 127
 128                 if(e->reverse->connection)
 129                         e->reverse->connection->status.mst = true;
 130
 131                 safe_edges++;
 132
 133                 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
 134                                    e->to->name, e->weight);
 135
 136                 if(skipped) {
 137                         skipped = false;
 138                         next = edge_weight_tree->head;
 139                         continue;
 140                 }
 141         }
 142
 143         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes,
 144                            safe_edges);
 145 }
 146
 147 /* Implementation of a simple breadth-first search algorithm.
 148    Running time: O(E)
 149 */
 150
 151 void sssp_bfs(void)
 152 {
 153         avl_node_t *node, *next, *to;
 154         edge_t *e;
 155         node_t *n;
 156         list_t *todo_list;
 157         list_node_t *from, *todonext;
 158         bool indirect;
 159         char *name;
 160         char *address, *port;
 161         char *envp[7];
 162         int i;
 163
 164         cp();
 165
 166         todo_list = list_alloc(NULL);
 167
 168         /* Clear visited status on nodes */
 169
 170         for(node = node_tree->head; node; node = node->next) {
 171                 n = node->data;
 172                 n->status.visited = false;
 173                 n->status.indirect = true;
 174         }
 175
 176         /* Begin with myself */
 177
 178         myself->status.visited = true;
 179         myself->status.indirect = false;
 180         myself->nexthop = myself;
 181         myself->via = myself;
 182         list_insert_head(todo_list, myself);
 183
 184         /* Loop while todo_list is filled */
 185
 186         for(from = todo_list->head; from; from = todonext) {    /* "from" is the node from which we start */
 187                 n = from->data;
 188
 189                 for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 190                         e = to->data;
 191
 192                         if(!e->reverse)
 193                                 continue;
 194
 195                         /* Situation:
 196
 197                                    /
 198                                   /
 199                            ----->(n)---e-->(e->to)
 200                                   \
 201                                    \
 202
 203                            Where e is an edge, (n) and (e->to) are nodes.
 204                            n->address is set to the e->address of the edge left of n to n.
 205                            We are currently examining the edge e right of n from n:
 206
 207                            - If e->reverse->address != n->address, then e->to is probably
 208                              not reachable for the nodes left of n. We do as if the indirectdata
 209                              flag is set on edge e.
 210                            - If edge e provides for better reachability of e->to, update
 211                              e->to and (re)add it to the todo_list to (re)examine the reachability
 212                              of nodes behind it.
 213                          */
 214
 215                         indirect = n->status.indirect || e->options & OPTION_INDIRECT
 216                                 || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address));
 217
 218                         if(e->to->status.visited
 219                            && (!e->to->status.indirect || indirect))
 220                                 continue;
 221
 222                         e->to->status.visited = true;
 223                         e->to->status.indirect = indirect;
 224                         e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 225                         e->to->via = indirect ? n->via : e->to;
 226                         e->to->options = e->options;
 227
 228                         if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)
 229                                 update_node_udp(e->to, &e->address);
 230
 231                         list_insert_tail(todo_list, e->to);
 232                 }
 233
 234                 todonext = from->next;
 235                 list_delete_node(todo_list, from);
 236         }
 237
 238         list_free(todo_list);
 239
 240         /* Check reachability status. */
 241
 242         for(node = node_tree->head; node; node = next) {
 243                 next = node->next;
 244                 n = node->data;
 245
 246                 if(n->status.visited != n->status.reachable) {
 247                         n->status.reachable = !n->status.reachable;
 248
 249                         if(n->status.reachable) {
 250                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became reachable"),
 251                                            n->name, n->hostname);
 252                         } else {
 253                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became unreachable"),
 254                                            n->name, n->hostname);
 255                         }
 256
 257                         /* TODO: only clear status.validkey if node is unreachable? */
 258
 259                         n->status.validkey = false;
 260                         n->status.waitingforkey = false;
 261
 262                         n->maxmtu = MTU;
 263                         n->minmtu = 0;
 264                         n->mtuprobes = 0;
 265
 266                         if(n->mtuevent) {
 267                                 event_del(n->mtuevent);
 268                                 n->mtuevent = NULL;
 269                         }
 270
 271                         xasprintf(&envp[0], "NETNAME=%s", netname ? : "");
 272                         xasprintf(&envp[1], "DEVICE=%s", device ? : "");
 273                         xasprintf(&envp[2], "INTERFACE=%s", iface ? : "");
 274                         xasprintf(&envp[3], "NODE=%s", n->name);
 275                         sockaddr2str(&n->address, &address, &port);
 276                         xasprintf(&envp[4], "REMOTEADDRESS=%s", address);
 277                         xasprintf(&envp[5], "REMOTEPORT=%s", port);
 278                         envp[6] = NULL;
 279
 280                         execute_script(n->status.reachable ? "host-up" : "host-down", envp);
 281
 282                         xasprintf(&name,
 283                                          n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 284                                          n->name);
 285                         execute_script(name, envp);
 286
 287                         free(name);
 288                         free(address);
 289                         free(port);
 290
 291                         for(i = 0; i < 6; i++)
 292                                 free(envp[i]);
 293
 294                         subnet_update(n, NULL, n->status.reachable);
 295                 }
 296         }
 297 }
 298
 299 void graph(void)
 300 {
 301         subnet_cache_flush();
 302         sssp_bfs();
 303         mst_kruskal();
 304         graph_changed = true;
 305 }
 306
 307
 308
 309 /* Dump nodes and edges to a graphviz file.
 310
 311    The file can be converted to an image with
 312    dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true
 313 */
 314
 315 void dump_graph(void)
 316 {
 317         avl_node_t *node;
 318         node_t *n;
 319         edge_t *e;
 320         char *filename = NULL, *tmpname = NULL;
 321         FILE *file;
 322
 323         if(!graph_changed || !get_config_string(lookup_config(config_tree, "GraphDumpFile"), &filename))
 324                 return;
 325
 326         graph_changed = false;
 327
 328         ifdebug(PROTOCOL) logger(LOG_NOTICE, "Dumping graph");
 329
 330         if(filename[0] == '|') {
 331                 file = popen(filename + 1, "w");
 332         } else {
 333                 xasprintf(&tmpname, "%s.new", filename);
 334                 file = fopen(tmpname, "w");
 335         }
 336
 337         if(!file) {
 338                 logger(LOG_ERR, "Unable to open graph dump file %s: %s", filename, strerror(errno));
 339                 free(tmpname);
 340                 return;
 341         }
 342
 343         fprintf(file, "digraph {\n");
 344
 345         /* dump all nodes first */
 346         for(node = node_tree->head; node; node = node->next) {
 347                 n = node->data;
 348                 fprintf(file, " %s [label = \"%s\"];\n", n->name, n->name);
 349         }
 350
 351         /* now dump all edges */
 352         for(node = edge_weight_tree->head; node; node = node->next) {
 353                 e = node->data;
 354                 fprintf(file, " %s -> %s;\n", e->from->name, e->to->name);
 355         }
 356
 357         fprintf(file, "}\n");
 358
 359         if(filename[0] == '|') {
 360                 pclose(file);
 361         } else {
 362                 fclose(file);
 363 #ifdef HAVE_MINGW
 364                 unlink(filename);
 365 #endif
 366                 rename(tmpname, filename);
 367                 free(tmpname);
 368         }
 369 }