git.meshlink.io Git - meshlink/blob - src/graph.c

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001-2011 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 edge e provides for better reachability of e->to, update
 289                              e->to and (re)add it to the todo_list to (re)examine the reachability
 290                              of nodes behind it.
 291                          */
 292
 293                         indirect = n->status.indirect || e->options & OPTION_INDIRECT;
 294
 295                         if(e->to->status.visited
 296                            && (!e->to->status.indirect || indirect))
 297                                 continue;
 298
 299                         e->to->status.visited = true;
 300                         e->to->status.indirect = indirect;
 301                         e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
 302                         e->to->via = indirect ? n->via : e->to;
 303                         e->to->options = e->options;
 304
 305                         if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN)
 306                                 update_node_udp(e->to, &e->address);
 307
 308                         list_insert_tail(todo_list, e->to);
 309                 }
 310
 311                 todonext = from->next;
 312                 list_delete_node(todo_list, from);
 313         }
 314
 315         list_free(todo_list);
 316 }
 317
 318 void check_reachability() {
 319         splay_node_t *node, *next;
 320         node_t *n;
 321         char *name;
 322         char *address, *port;
 323         char *envp[7];
 324         int i;
 325
 326         /* Check reachability status. */
 327
 328         for(node = node_tree->head; node; node = next) {
 329                 next = node->next;
 330                 n = node->data;
 331
 332                 if(n->status.visited != n->status.reachable) {
 333                         n->status.reachable = !n->status.reachable;
 334
 335                         if(n->status.reachable) {
 336                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable",
 337                                            n->name, n->hostname);
 338                         } else {
 339                                 ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable",
 340                                            n->name, n->hostname);
 341                         }
 342
 343                         /* TODO: only clear status.validkey if node is unreachable? */
 344
 345                         n->status.validkey = false;
 346                         n->last_req_key = 0;
 347
 348                         n->maxmtu = MTU;
 349                         n->minmtu = 0;
 350                         n->mtuprobes = 0;
 351
 352                         event_del(&n->mtuevent);
 353
 354                         xasprintf(&envp[0], "NETNAME=%s", netname ? : "");
 355                         xasprintf(&envp[1], "DEVICE=%s", device ? : "");
 356                         xasprintf(&envp[2], "INTERFACE=%s", iface ? : "");
 357                         xasprintf(&envp[3], "NODE=%s", n->name);
 358                         sockaddr2str(&n->address, &address, &port);
 359                         xasprintf(&envp[4], "REMOTEADDRESS=%s", address);
 360                         xasprintf(&envp[5], "REMOTEPORT=%s", port);
 361                         envp[6] = NULL;
 362
 363                         execute_script(n->status.reachable ? "host-up" : "host-down", envp);
 364
 365                         xasprintf(&name,
 366                                          n->status.reachable ? "hosts/%s-up" : "hosts/%s-down",
 367                                          n->name);
 368                         execute_script(name, envp);
 369
 370                         free(name);
 371                         free(address);
 372                         free(port);
 373
 374                         for(i = 0; i < 6; i++)
 375                                 free(envp[i]);
 376
 377                         subnet_update(n, NULL, n->status.reachable);
 378
 379                         if(!n->status.reachable)
 380                                 update_node_udp(n, NULL);
 381                         else if(n->connection)
 382                                 send_ans_key(n);
 383                 }
 384         }
 385 }
 386
 387 void graph(void) {
 388         subnet_cache_flush();
 389         sssp_dijkstra();
 390         check_reachability();
 391         mst_kruskal();
 392 }