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(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)
 316                                 update_node_udp(e->to, &e->address);
 317
 318                         list_insert_tail(todo_list, e->to);
 319                 }
 320
 321                 todonext = from->next;
 322                 list_delete_node(todo_list, from);
 323         }
 324
 325         list_free(todo_list);
 326 }
 327
 328 void check_reachability() {
 329         splay_node_t *node, *next;
 330         node_t *n;
 331         char *name;
 332         char *address, *port;
 333         char *envp[7];
 334         int i;
 335
 336         /* Check reachability status. */
 337
 338         for(node = node_tree->head; node; node = next) {
 339                 next = node->next;
 340                 n = node->data;
 341
 342                 if(n->status.visited != n->status.reachable) {
 343                         n->status.reachable = !n->status.reachable;
 344
 345                         if(n->status.reachable) {
 346                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became reachable"),
 347                                            n->name, n->hostname);
 348                         } else {
 349                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, _("Node %s (%s) became unreachable"),
 350                                            n->name, n->hostname);
 351                         }
 352
 353                         /* TODO: only clear status.validkey if node is unreachable? */
 354
 355                         n->status.validkey = false;
 356                         n->status.waitingforkey = false;
 357
 358                         n->maxmtu = MTU;
 359                         n->minmtu = 0;
 360                         n->mtuprobes = 0;
 361
 362                         asprintf(&envp[0], "NETNAME=%s", netname ? : "");
 363                         asprintf(&envp[1], "DEVICE=%s", device ? : "");
 364                         asprintf(&envp[2], "INTERFACE=%s", iface ? : "");
 365                         asprintf(&envp[3], "NODE=%s", n->name);
 366                         sockaddr2str(&n->address, &address, &port);
 367                         asprintf(&envp[4], "REMOTEADDRESS=%s", address);
 368                         asprintf(&envp[5], "REMOTEPORT=%s", port);
 369                         envp[6] = NULL;
 370
 371                         execute_script(n->status.reachable ? "host-up" : "host-down", envp);
 372
 373                         asprintf(&name,
 374                                          n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 375                                          n->name);
 376                         execute_script(name, envp);
 377
 378                         free(name);
 379                         free(address);
 380                         free(port);
 381
 382                         for(i = 0; i < 6; i++)
 383                                 free(envp[i]);
 384
 385                         subnet_update(n, NULL, n->status.reachable);
 386                 }
 387         }
 388 }
 389
 390 /* Dump nodes and edges to a graphviz file.
 391
 392    The file can be converted to an image with
 393    dot -Tpng graph_filename -o image_filename.png -Gconcentrate=true
 394 */
 395
 396 int dump_graph(struct evbuffer *out) {
 397         splay_node_t *node;
 398         node_t *n;
 399         edge_t *e;
 400
 401         if(evbuffer_add_printf(out, "digraph {\n") == -1)
 402                 return errno;
 403
 404         /* dump all nodes first */
 405         for(node = node_tree->head; node; node = node->next) {
 406                 n = node->data;
 407                 if(evbuffer_add_printf(out, "   %s [label = \"%s\"];\n",
 408                                                            n->name, n->name) == -1)
 409                         return errno;
 410         }
 411
 412         /* now dump all edges */
 413         for(node = edge_weight_tree->head; node; node = node->next) {
 414                 e = node->data;
 415                 if(evbuffer_add_printf(out, "   %s -> %s;\n",
 416                                                            e->from->name, e->to->name) == -1)
 417                         return errno;
 418         }
 419
 420         if(evbuffer_add_printf(out, "}\n") == -1)
 421                 return errno;
 422
 423         return 0;
 424 }
 425
 426 void graph(void) {
 427     subnet_cache_flush();
 428         sssp_dijkstra();
 429         check_reachability();
 430         mst_kruskal();
 431 }