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