git.meshlink.io Git - meshlink/blob - 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     $Id$
  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 "system.h"
  48
  49 #include "splay_tree.h"
  50 #include "config.h"
  51 #include "connection.h"
  52 #include "device.h"
  53 #include "edge.h"
  54 #include "logger.h"
  55 #include "netutl.h"
  56 #include "node.h"
  57 #include "process.h"
  58 #include "subnet.h"
  59 #include "utils.h"
  60
  61 /* Implementation of Kruskal's algorithm.
  62    Running time: O(E)
  63    Please note that sorting on weight is already done by add_edge().
  64 */
  65
  66 void mst_kruskal(void) {
  67         splay_node_t *node, *next;
  68         edge_t *e;
  69         node_t *n;
  70         connection_t *c;
  71
  72         cp();
  73
  74         /* Clear MST status on connections */
  75
  76         for(node = connection_tree->head; node; node = node->next) {
  77                 c = node->data;
  78                 c->status.mst = false;
  79         }
  80
  81         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:");
  82
  83         /* Clear visited status on nodes */
  84
  85         for(node = node_tree->head; node; node = node->next) {
  86                 n = node->data;
  87                 n->status.visited = false;
  88         }
  89
  90         /* Add safe edges */
  91
  92         for(node = edge_weight_tree->head; node; node = next) {
  93                 next = node->next;
  94                 e = node->data;
  95
  96                 if(!e->reverse || (e->from->status.visited && e->to->status.visited))
  97                         continue;
  98
  99                 e->from->status.visited = true;
 100                 e->to->status.visited = true;
 101
 102                 if(e->connection)
 103                         e->connection->status.mst = true;
 104
 105                 if(e->reverse->connection)
 106                         e->reverse->connection->status.mst = true;
 107
 108                 ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name,
 109                                    e->to->name, e->weight);
 110         }
 111 }
 112
 113 /* Implementation of Dijkstra's algorithm.
 114    Running time: O(N^2)
 115 */
 116
 117 void sssp_dijkstra(void) {
 118         splay_node_t *node, *to;
 119         edge_t *e;
 120         node_t *n, *m;
 121         list_t *todo_list;
 122         list_node_t *lnode, *nnode;
 123         bool indirect;
 124
 125         cp();
 126
 127         todo_list = list_alloc(NULL);
 128
 129         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Dijkstra's algorithm:");
 130
 131         /* Clear visited status on nodes */
 132
 133         for(node = node_tree->head; node; node = node->next) {
 134                 n = node->data;
 135                 n->status.visited = false;
 136                 n->status.indirect = true;
 137                 n->distance = -1;
 138         }
 139
 140         /* Begin with myself */
 141
 142         myself->status.indirect = false;
 143         myself->nexthop = myself;
 144         myself->via = myself;
 145         myself->distance = 0;
 146         list_insert_head(todo_list, myself);
 147
 148         /* Loop while todo_list is filled */
 149
 150         while(todo_list->head) {
 151                 n = NULL;
 152                 nnode = NULL;
 153
 154                 /* Select node from todo_list with smallest distance */
 155
 156                 for(lnode = todo_list->head; lnode; lnode = lnode->next) {
 157                         m = lnode->data;
 158                         if(!n || m->status.indirect < n->status.indirect || m->distance < n->distance) {
 159                                 n = m;
 160                                 nnode = lnode;
 161                         }
 162                 }
 163
 164                 /* Mark this node as visited and remove it from the todo_list */
 165
 166                 n->status.visited = true;
 167                 list_unlink_node(todo_list, nnode);
 168
 169                 /* Update distance of neighbours and add them to the todo_list */
 170
 171                 for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 172                         e = to->data;
 173
 174                         if(e->to->status.visited || !e->reverse)
 175                                 continue;
 176
 177                         /* Situation:
 178
 179                                    /
 180                                   /
 181                            ----->(n)---e-->(e->to)
 182                                   \
 183                                    \
 184
 185                            Where e is an edge, (n) and (e->to) are nodes.
 186                            n->address is set to the e->address of the edge left of n to n.
 187                            We are currently examining the edge e right of n from n:
 188
 189                            - If e->reverse->address != n->address, then e->to is probably
 190                              not reachable for the nodes left of n. We do as if the indirectdata
 191                              flag is set on edge e.
 192                            - If edge e provides for better reachability of e->to, update e->to.
 193                          */
 194
 195                         if(e->to->distance < 0)
 196                                 list_insert_tail(todo_list, e->to);
 197
 198                         indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address));
 199
 200                         if(e->to->distance >= 0 && (!e->to->status.indirect || indirect) && e->to->distance <= n->distance + e->weight)
 201                                 continue;
 202
 203                         e->to->distance = n->distance + e->weight;
 204                         e->to->status.indirect = indirect;
 205                         e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 206                         e->to->via = indirect ? n->via : e->to;
 207                         e->to->options = e->options;
 208
 209                         if(sockaddrcmp(&e->to->address, &e->address)) {
 210                                 node = splay_unlink(node_udp_tree, e->to);
 211                                 sockaddrfree(&e->to->address);
 212                                 sockaddrcpy(&e->to->address, &e->address);
 213
 214                                 if(e->to->hostname)
 215                                         free(e->to->hostname);
 216
 217                                 e->to->hostname = sockaddr2hostname(&e->to->address);
 218
 219                                 if(node)
 220                                         splay_insert_node(node_udp_tree, node);
 221
 222                                 if(e->to->options & OPTION_PMTU_DISCOVERY) {
 223                                         e->to->mtuprobes = 0;
 224                                         e->to->minmtu = 0;
 225                                         e->to->maxmtu = MTU;
 226                                         if(e->to->status.validkey)
 227                                                 send_mtu_probe(e->to);
 228                                 }
 229                         }
 230
 231                         ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Updating edge %s - %s weight %d distance %d", e->from->name,
 232                                            e->to->name, e->weight, e->to->distance);
 233                 }
 234         }
 235
 236         list_free(todo_list);
 237 }
 238
 239 /* Implementation of a simple breadth-first search algorithm.
 240    Running time: O(E)
 241 */
 242
 243 void sssp_bfs(void) {
 244         splay_node_t *node, *to;
 245         edge_t *e;
 246         node_t *n;
 247         list_t *todo_list;
 248         list_node_t *from, *todonext;
 249         bool indirect;
 250
 251         cp();
 252
 253         todo_list = list_alloc(NULL);
 254
 255         /* Clear visited status on nodes */
 256
 257         for(node = node_tree->head; node; node = node->next) {
 258                 n = node->data;
 259                 n->status.visited = false;
 260                 n->status.indirect = true;
 261         }
 262
 263         /* Begin with myself */
 264
 265         myself->status.visited = true;
 266         myself->status.indirect = false;
 267         myself->nexthop = myself;
 268         myself->via = myself;
 269         list_insert_head(todo_list, myself);
 270
 271         /* Loop while todo_list is filled */
 272
 273         for(from = todo_list->head; from; from = todonext) {    /* "from" is the node from which we start */
 274                 n = from->data;
 275
 276                 for(to = n->edge_tree->head; to; to = to->next) {       /* "to" is the edge connected to "from" */
 277                         e = to->data;
 278
 279                         if(!e->reverse)
 280                                 continue;
 281
 282                         /* Situation:
 283
 284                                    /
 285                                   /
 286                            ----->(n)---e-->(e->to)
 287                                   \
 288                                    \
 289
 290                            Where e is an edge, (n) and (e->to) are nodes.
 291                            n->address is set to the e->address of the edge left of n to n.
 292                            We are currently examining the edge e right of n from n:
 293
 294                            - If e->reverse->address != n->address, then e->to is probably
 295                              not reachable for the nodes left of n. We do as if the indirectdata
 296                              flag is set on edge e.
 297                            - If edge e provides for better reachability of e->to, update
 298                              e->to and (re)add it to the todo_list to (re)examine the reachability
 299                              of nodes behind it.
 300                          */
 301
 302                         indirect = n->status.indirect || e->options & OPTION_INDIRECT
 303                                 || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address));
 304
 305                         if(e->to->status.visited
 306                            && (!e->to->status.indirect || indirect))
 307                                 continue;
 308
 309                         e->to->status.visited = true;
 310                         e->to->status.indirect = indirect;
 311                         e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 312                         e->to->via = indirect ? n->via : e->to;
 313                         e->to->options = e->options;
 314
 315                         if(sockaddrcmp(&e->to->address, &e->address)) {
 316                                 node = splay_unlink(node_udp_tree, e->to);
 317                                 sockaddrfree(&e->to->address);
 318                                 sockaddrcpy(&e->to->address, &e->address);
 319
 320                                 if(e->to->hostname)
 321                                         free(e->to->hostname);
 322
 323                                 e->to->hostname = sockaddr2hostname(&e->to->address);
 324
 325                                 if(node)
 326                                         splay_insert_node(node_udp_tree, node);
 327
 328                                 if(e->to->options & OPTION_PMTU_DISCOVERY) {
 329                                         e->to->mtuprobes = 0;
 330                                         e->to->minmtu = 0;
 331                                         e->to->maxmtu = MTU;
 332                                         if(e->to->status.validkey)
 333                                                 send_mtu_probe(e->to);
 334                                 }
 335                         }
 336
 337                         list_insert_tail(todo_list, e->to);
 338                 }
 339
 340                 todonext = from->next;
 341                 list_delete_node(todo_list, from);
 342         }
 343
 344         list_free(todo_list);
 345 }
 346
 347 void check_reachability() {
 348         splay_node_t *node, *next;
 349         node_t *n;
 350         char *name;
 351         char *address, *port;
 352         char *envp[7];
 353         int i;
 354
 355         /* Check reachability status. */
 356
 357         for(node = node_tree->head; node; node = next) {
 358                 next = node->next;
 359                 n = node->data;
 360
 361                 if(n->status.visited != n->status.reachable) {
 362                         n->status.reachable = !n->status.reachable;
 363
 364                         if(n->status.reachable) {
 365                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became reachable"),
 366                                            n->name, n->hostname);
 367                                 splay_insert(node_udp_tree, n);
 368                         } else {
 369                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became unreachable"),
 370                                            n->name, n->hostname);
 371                                 splay_delete(node_udp_tree, n);
 372                         }
 373
 374                         n->status.validkey = false;
 375                         n->status.waitingforkey = false;
 376
 377                         n->maxmtu = MTU;
 378                         n->minmtu = 0;
 379                         n->mtuprobes = 0;
 380
 381                         asprintf(&envp[0], "NETNAME=%s", netname ? : "");
 382                         asprintf(&envp[1], "DEVICE=%s", device ? : "");
 383                         asprintf(&envp[2], "INTERFACE=%s", iface ? : "");
 384                         asprintf(&envp[3], "NODE=%s", n->name);
 385                         sockaddr2str(&n->address, &address, &port);
 386                         asprintf(&envp[4], "REMOTEADDRESS=%s", address);
 387                         asprintf(&envp[5], "REMOTEPORT=%s", port);
 388                         envp[6] = NULL;
 389
 390                         execute_script(n->status.reachable ? "host-up" : "host-down", envp);
 391
 392                         asprintf(&name,
 393                                          n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 394                                          n->name);
 395                         execute_script(name, envp);
 396
 397                         free(name);
 398                         free(address);
 399                         free(port);
 400
 401                         for(i = 0; i < 6; i++)
 402                                 free(envp[i]);
 403
 404                         subnet_update(n, NULL, n->status.reachable);
 405                 }
 406         }
 407 }
 408
 409 /* Dump nodes and edges to a graphviz file.
 410
 411    The file can be converted to an image with
 412    dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true
 413 */
 414
 415 int dump_graph(struct evbuffer *out) {
 416         splay_node_t *node;
 417         node_t *n;
 418         edge_t *e;
 419
 420         if(evbuffer_add_printf(out, "digraph {\n") == -1)
 421                 return errno;
 422
 423         /* dump all nodes first */
 424         for(node = node_tree->head; node; node = node->next) {
 425                 n = node->data;
 426                 if(evbuffer_add_printf(out, "   %s [label = \"%s\"];\n",
 427                                                            n->name, n->name) == -1)
 428                         return errno;
 429         }
 430
 431         /* now dump all edges */
 432         for(node = edge_weight_tree->head; node; node = node->next) {
 433                 e = node->data;
 434                 if(evbuffer_add_printf(out, "   %s -> %s;\n",
 435                                                            e->from->name, e->to->name) == -1)
 436                         return errno;
 437         }
 438
 439         if(evbuffer_add_printf(out, "}\n") == -1)
 440                 return errno;
 441
 442         return 0;
 443 }
 444
 445 void graph(void) {
 446     subnet_cache_flush();
 447         sssp_dijkstra();
 448         check_reachability();
 449         mst_kruskal();
 450 }