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

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