Do not try to dereference myself->connection->config_tree.
[tinc] / 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 }