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