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

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001-2014 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 along
  17     with this program; if not, write to the Free Software Foundation, Inc.,
  18     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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 "conf.h"
  49 #include "connection.h"
  50 #include "device.h"
  51 #include "edge.h"
  52 #include "graph.h"
  53 #include "logger.h"
  54 #include "netutl.h"
  55 #include "node.h"
  56 #include "process.h"
  57 #include "protocol.h"
  58 #include "subnet.h"
  59 #include "utils.h"
  60 #include "xalloc.h"
  61
  62 static bool graph_changed = true;
  63
  64 /* Implementation of Kruskal's algorithm.
  65    Running time: O(EN)
  66    Please note that sorting on weight is already done by add_edge().
  67 */
  68
  69 static void mst_kruskal(void) {
  70         avl_node_t *node, *next;
  71         edge_t *e;
  72         node_t *n;
  73         connection_t *c;
  74         int nodes = 0;
  75         int safe_edges = 0;
  76         bool skipped;
  77
  78         /* Clear MST status on connections */
  79
  80         for(node = connection_tree->head; node; node = node->next) {
  81                 c = node->data;
  82                 c->status.mst = false;
  83         }
  84
  85         /* Do we have something to do at all? */
  86
  87         if(!edge_weight_tree->head) {
  88                 return;
  89         }
  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
 106                 if(e->from->status.reachable) {
 107                         e->from->status.visited = true;
 108                         break;
 109                 }
 110         }
 111
 112         /* Add safe edges */
 113
 114         for(skipped = false, node = edge_weight_tree->head; node; node = next) {
 115                 next = node->next;
 116                 e = node->data;
 117
 118                 if(!e->reverse || e->from->status.visited == e->to->status.visited) {
 119                         skipped = true;
 120                         continue;
 121                 }
 122
 123                 e->from->status.visited = true;
 124                 e->to->status.visited = true;
 125
 126                 if(e->connection) {
 127                         e->connection->status.mst = true;
 128                 }
 129
 130                 if(e->reverse->connection) {
 131                         e->reverse->connection->status.mst = true;
 132                 }
 133
 134                 safe_edges++;
 135
 136                 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
 137                                              e->to->name, e->weight);
 138
 139                 if(skipped) {
 140                         skipped = false;
 141                         next = edge_weight_tree->head;
 142                         continue;
 143                 }
 144         }
 145
 146         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes,
 147                                      safe_edges);
 148 }
 149
 150 /* Implementation of a simple breadth-first search algorithm.
 151    Running time: O(E)
 152 */
 153
 154 static void sssp_bfs(void) {
 155         avl_node_t *node, *next, *to;
 156         edge_t *e;
 157         node_t *n;
 158         list_t *todo_list;
 159         list_node_t *from, *todonext;
 160         bool indirect;
 161         char *name;
 162         char *address, *port;
 163         char *envp[8] = {NULL};
 164         int i;
 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->prevedge = NULL;
 182         myself->via = myself;
 183         list_insert_head(todo_list, myself);
 184
 185         /* Loop while todo_list is filled */
 186
 187         for(from = todo_list->head; from; from = todonext) {    /* "from" is the node from which we start */
 188                 n = from->data;
 189
 190                 for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 191                         e = to->data;
 192
 193                         if(!e->reverse) {
 194                                 continue;
 195                         }
 196
 197                         /* Situation:
 198
 199                                    /
 200                                   /
 201                            ----->(n)---e-->(e->to)
 202                                   \
 203                                    \
 204
 205                            Where e is an edge, (n) and (e->to) are nodes.
 206                            n->address is set to the e->address of the edge left of n to n.
 207                            We are currently examining the edge e right of n from n:
 208
 209                            - If edge e provides for better reachability of e->to, update
 210                              e->to and (re)add it to the todo_list to (re)examine the reachability
 211                              of nodes behind it.
 212                          */
 213
 214                         indirect = n->status.indirect || e->options & OPTION_INDIRECT;
 215
 216                         if(e->to->status.visited
 217                                         && (!e->to->status.indirect || indirect)) {
 218                                 continue;
 219                         }
 220
 221                         // Only update nexthop the first time we visit this node.
 222
 223                         if(!e->to->status.visited) {
 224                                 e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 225                         }
 226
 227                         e->to->status.visited = true;
 228                         e->to->status.indirect = indirect;
 229                         e->to->prevedge = e;
 230                         e->to->via = indirect ? n->via : e->to;
 231                         e->to->options = e->options;
 232
 233                         if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN) {
 234                                 update_node_udp(e->to, &e->address);
 235                         }
 236
 237                         list_insert_tail(todo_list, e->to);
 238                 }
 239
 240                 todonext = from->next;
 241                 list_delete_node(todo_list, from);
 242         }
 243
 244         list_free(todo_list);
 245
 246         /* Check reachability status. */
 247
 248         for(node = node_tree->head; node; node = next) {
 249                 next = node->next;
 250                 n = node->data;
 251
 252                 if(n->status.visited != n->status.reachable) {
 253                         n->status.reachable = !n->status.reachable;
 254
 255                         if(n->status.reachable) {
 256                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable",
 257                                                         n->name, n->hostname);
 258                         } else {
 259                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable",
 260                                                         n->name, n->hostname);
 261                         }
 262
 263                         /* TODO: only clear status.validkey if node is unreachable? */
 264
 265                         n->status.validkey = false;
 266                         n->last_req_key = 0;
 267
 268                         n->maxmtu = MTU;
 269                         n->minmtu = 0;
 270                         n->mtuprobes = 0;
 271
 272                         if(n->mtuevent) {
 273                                 event_del(n->mtuevent);
 274                                 n->mtuevent = NULL;
 275                         }
 276
 277                         xasprintf(&envp[0], "NETNAME=%s", netname ? : "");
 278                         xasprintf(&envp[1], "DEVICE=%s", device ? : "");
 279                         xasprintf(&envp[2], "INTERFACE=%s", iface ? : "");
 280                         xasprintf(&envp[3], "NODE=%s", n->name);
 281                         sockaddr2str(&n->address, &address, &port);
 282                         xasprintf(&envp[4], "REMOTEADDRESS=%s", address);
 283                         xasprintf(&envp[5], "REMOTEPORT=%s", port);
 284                         xasprintf(&envp[6], "NAME=%s", myself->name);
 285
 286                         execute_script(n->status.reachable ? "host-up" : "host-down", envp);
 287
 288                         xasprintf(&name,
 289                                   n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 290                                   n->name);
 291                         execute_script(name, envp);
 292
 293                         free(name);
 294                         free(address);
 295                         free(port);
 296
 297                         for(i = 0; i < 7; i++) {
 298                                 free(envp[i]);
 299                         }
 300
 301                         subnet_update(n, NULL, n->status.reachable);
 302
 303                         if(!n->status.reachable) {
 304                                 update_node_udp(n, NULL);
 305                                 memset(&n->status, 0, sizeof(n->status));
 306                                 n->options = 0;
 307                         } else if(n->connection) {
 308                                 send_ans_key(n);
 309                         }
 310                 }
 311         }
 312 }
 313
 314 void graph(void) {
 315         subnet_cache_flush();
 316         sssp_bfs();
 317         mst_kruskal();
 318         graph_changed = true;
 319 }
 320
 321
 322
 323 /* Dump nodes and edges to a graphviz file.
 324
 325    The file can be converted to an image with
 326    dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true
 327 */
 328
 329 void dump_graph(void) {
 330         avl_node_t *node;
 331         node_t *n;
 332         edge_t *e;
 333         char *filename = NULL, *tmpname = NULL;
 334         FILE *file, *pipe = NULL;
 335
 336         if(!graph_changed || !get_config_string(lookup_config(config_tree, "GraphDumpFile"), &filename)) {
 337                 return;
 338         }
 339
 340         graph_changed = false;
 341
 342         ifdebug(PROTOCOL) logger(LOG_NOTICE, "Dumping graph");
 343
 344         if(filename[0] == '|') {
 345                 file = pipe = popen(filename + 1, "w");
 346         } else {
 347                 xasprintf(&tmpname, "%s.new", filename);
 348                 file = fopen(tmpname, "w");
 349         }
 350
 351         if(!file) {
 352                 logger(LOG_ERR, "Unable to open graph dump file %s: %s", filename, strerror(errno));
 353                 free(filename);
 354                 free(tmpname);
 355                 return;
 356         }
 357
 358         fprintf(file, "digraph {\n");
 359
 360         /* dump all nodes first */
 361         for(node = node_tree->head; node; node = node->next) {
 362                 n = node->data;
 363                 fprintf(file, " %s [label = \"%s\"];\n", n->name, n->name);
 364         }
 365
 366         /* now dump all edges */
 367         for(node = edge_weight_tree->head; node; node = node->next) {
 368                 e = node->data;
 369                 fprintf(file, " %s -> %s;\n", e->from->name, e->to->name);
 370         }
 371
 372         fprintf(file, "}\n");
 373
 374         if(pipe) {
 375                 pclose(pipe);
 376         } else {
 377                 fclose(file);
 378 #ifdef HAVE_MINGW
 379                 unlink(filename);
 380 #endif
 381
 382                 if(rename(tmpname, filename)) {
 383                         logger(LOG_ERR, "Could not rename %s to %s: %s\n", tmpname, filename, strerror(errno));
 384                 }
 385
 386                 free(tmpname);
 387         }
 388
 389         free(filename);
 390 }