Fix memory leak while running Dijkstra's algorithm.
[tinc] / src / subnet.c
1 /*
2     subnet.c -- handle subnet lookups and lists
3     Copyright (C) 2000-2010 Guus Sliepen <guus@tinc-vpn.org>,
4                   2000-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 #include "system.h"
22
23 #include "splay_tree.h"
24 #include "control_common.h"
25 #include "device.h"
26 #include "logger.h"
27 #include "net.h"
28 #include "netutl.h"
29 #include "node.h"
30 #include "process.h"
31 #include "subnet.h"
32 #include "utils.h"
33 #include "xalloc.h"
34
35 /* lists type of subnet */
36
37 splay_tree_t *subnet_tree;
38
39 /* Subnet lookup cache */
40
41 static ipv4_t cache_ipv4_address[2];
42 static subnet_t *cache_ipv4_subnet[2];
43 static bool cache_ipv4_valid[2];
44 static int cache_ipv4_slot;
45
46 static ipv6_t cache_ipv6_address[2];
47 static subnet_t *cache_ipv6_subnet[2];
48 static bool cache_ipv6_valid[2];
49 static int cache_ipv6_slot;
50
51 static mac_t cache_mac_address[2];
52 static subnet_t *cache_mac_subnet[2];
53 static bool cache_mac_valid[2];
54 static int cache_mac_slot;
55
56 void subnet_cache_flush() {
57         cache_ipv4_valid[0] = cache_ipv4_valid[1] = false;
58         cache_ipv6_valid[0] = cache_ipv6_valid[1] = false;
59         cache_mac_valid[0] = cache_mac_valid[1] = false;
60 }
61
62 /* Subnet comparison */
63
64 static int subnet_compare_mac(const subnet_t *a, const subnet_t *b) {
65         int result;
66
67         result = memcmp(&a->net.mac.address, &b->net.mac.address, sizeof a->net.mac.address);
68
69         if(result)
70                 return result;
71         
72         result = a->weight - b->weight;
73
74         if(result || !a->owner || !b->owner)
75                 return result;
76
77         return strcmp(a->owner->name, b->owner->name);
78 }
79
80 static int subnet_compare_ipv4(const subnet_t *a, const subnet_t *b) {
81         int result;
82
83         result = b->net.ipv4.prefixlength - a->net.ipv4.prefixlength;
84
85         if(result)
86                 return result;
87
88         result = memcmp(&a->net.ipv4.address, &b->net.ipv4.address, sizeof(ipv4_t));
89
90         if(result)
91                 return result;
92         
93         result = a->weight - b->weight;
94
95         if(result || !a->owner || !b->owner)
96                 return result;
97
98         return strcmp(a->owner->name, b->owner->name);
99 }
100
101 static int subnet_compare_ipv6(const subnet_t *a, const subnet_t *b) {
102         int result;
103
104         result = b->net.ipv6.prefixlength - a->net.ipv6.prefixlength;
105
106         if(result)
107                 return result;
108         
109         result = memcmp(&a->net.ipv6.address, &b->net.ipv6.address, sizeof(ipv6_t));
110
111         if(result)
112                 return result;
113         
114         result = a->weight - b->weight;
115
116         if(result || !a->owner || !b->owner)
117                 return result;
118
119         return strcmp(a->owner->name, b->owner->name);
120 }
121
122 int subnet_compare(const subnet_t *a, const subnet_t *b) {
123         int result;
124
125         result = a->type - b->type;
126
127         if(result)
128                 return result;
129
130         switch (a->type) {
131         case SUBNET_MAC:
132                 return subnet_compare_mac(a, b);
133         case SUBNET_IPV4:
134                 return subnet_compare_ipv4(a, b);
135         case SUBNET_IPV6:
136                 return subnet_compare_ipv6(a, b);
137         default:
138                 logger(LOG_ERR, "subnet_compare() was called with unknown subnet type %d, exitting!",
139                            a->type);
140                 exit(0);
141         }
142
143         return 0;
144 }
145
146 /* Initialising trees */
147
148 void init_subnets(void) {
149         subnet_tree = splay_alloc_tree((splay_compare_t) subnet_compare, (splay_action_t) free_subnet);
150
151         subnet_cache_flush();
152 }
153
154 void exit_subnets(void) {
155         splay_delete_tree(subnet_tree);
156 }
157
158 splay_tree_t *new_subnet_tree(void) {
159         return splay_alloc_tree((splay_compare_t) subnet_compare, NULL);
160 }
161
162 void free_subnet_tree(splay_tree_t *subnet_tree) {
163         splay_delete_tree(subnet_tree);
164 }
165
166 /* Allocating and freeing space for subnets */
167
168 subnet_t *new_subnet(void) {
169         return xmalloc_and_zero(sizeof(subnet_t));
170 }
171
172 void free_subnet(subnet_t *subnet) {
173         free(subnet);
174 }
175
176 /* Adding and removing subnets */
177
178 void subnet_add(node_t *n, subnet_t *subnet) {
179         subnet->owner = n;
180
181         splay_insert(subnet_tree, subnet);
182         splay_insert(n->subnet_tree, subnet);
183
184         subnet_cache_flush();
185 }
186
187 void subnet_del(node_t *n, subnet_t *subnet) {
188         splay_delete(n->subnet_tree, subnet);
189         splay_delete(subnet_tree, subnet);
190
191         subnet_cache_flush();
192 }
193
194 /* Ascii representation of subnets */
195
196 bool str2net(subnet_t *subnet, const char *subnetstr) {
197         int i, l;
198         uint16_t x[8];
199         int weight = 10;
200
201         if(sscanf(subnetstr, "%hu.%hu.%hu.%hu/%d#%d",
202                           &x[0], &x[1], &x[2], &x[3], &l, &weight) >= 5) {
203                 if(l < 0 || l > 32)
204                         return false;
205
206                 subnet->type = SUBNET_IPV4;
207                 subnet->net.ipv4.prefixlength = l;
208                 subnet->weight = weight;
209
210                 for(i = 0; i < 4; i++) {
211                         if(x[i] > 255)
212                                 return false;
213                         subnet->net.ipv4.address.x[i] = x[i];
214                 }
215
216                 return true;
217         }
218
219         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx/%d#%d",
220                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5], &x[6], &x[7],
221                           &l, &weight) >= 9) {
222                 if(l < 0 || l > 128)
223                         return false;
224
225                 subnet->type = SUBNET_IPV6;
226                 subnet->net.ipv6.prefixlength = l;
227                 subnet->weight = weight;
228
229                 for(i = 0; i < 8; i++)
230                         subnet->net.ipv6.address.x[i] = htons(x[i]);
231
232                 return true;
233         }
234
235         if(sscanf(subnetstr, "%hu.%hu.%hu.%hu#%d", &x[0], &x[1], &x[2], &x[3], &weight) >= 4) {
236                 subnet->type = SUBNET_IPV4;
237                 subnet->net.ipv4.prefixlength = 32;
238                 subnet->weight = weight;
239
240                 for(i = 0; i < 4; i++) {
241                         if(x[i] > 255)
242                                 return false;
243                         subnet->net.ipv4.address.x[i] = x[i];
244                 }
245
246                 return true;
247         }
248
249         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx#%d",
250                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5], &x[6], &x[7], &weight) >= 8) {
251                 subnet->type = SUBNET_IPV6;
252                 subnet->net.ipv6.prefixlength = 128;
253                 subnet->weight = weight;
254
255                 for(i = 0; i < 8; i++)
256                         subnet->net.ipv6.address.x[i] = htons(x[i]);
257
258                 return true;
259         }
260
261         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx#%d",
262                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5], &weight) >= 6) {
263                 subnet->type = SUBNET_MAC;
264                 subnet->weight = weight;
265
266                 for(i = 0; i < 6; i++)
267                         subnet->net.mac.address.x[i] = x[i];
268
269                 return true;
270         }
271
272         return false;
273 }
274
275 bool net2str(char *netstr, int len, const subnet_t *subnet) {
276         if(!netstr || !subnet) {
277                 logger(LOG_ERR, "net2str() was called with netstr=%p, subnet=%p!", netstr, subnet);
278                 return false;
279         }
280
281         switch (subnet->type) {
282                 case SUBNET_MAC:
283                         snprintf(netstr, len, "%hx:%hx:%hx:%hx:%hx:%hx#%d",
284                                          subnet->net.mac.address.x[0],
285                                          subnet->net.mac.address.x[1],
286                                          subnet->net.mac.address.x[2],
287                                          subnet->net.mac.address.x[3],
288                                          subnet->net.mac.address.x[4],
289                                          subnet->net.mac.address.x[5],
290                                          subnet->weight);
291                         break;
292
293                 case SUBNET_IPV4:
294                         snprintf(netstr, len, "%hu.%hu.%hu.%hu/%d#%d",
295                                          subnet->net.ipv4.address.x[0],
296                                          subnet->net.ipv4.address.x[1],
297                                          subnet->net.ipv4.address.x[2],
298                                          subnet->net.ipv4.address.x[3],
299                                          subnet->net.ipv4.prefixlength,
300                                          subnet->weight);
301                         break;
302
303                 case SUBNET_IPV6:
304                         snprintf(netstr, len, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx/%d#%d",
305                                          ntohs(subnet->net.ipv6.address.x[0]),
306                                          ntohs(subnet->net.ipv6.address.x[1]),
307                                          ntohs(subnet->net.ipv6.address.x[2]),
308                                          ntohs(subnet->net.ipv6.address.x[3]),
309                                          ntohs(subnet->net.ipv6.address.x[4]),
310                                          ntohs(subnet->net.ipv6.address.x[5]),
311                                          ntohs(subnet->net.ipv6.address.x[6]),
312                                          ntohs(subnet->net.ipv6.address.x[7]),
313                                          subnet->net.ipv6.prefixlength,
314                                          subnet->weight);
315                         break;
316
317                 default:
318                         logger(LOG_ERR,
319                                    "net2str() was called with unknown subnet type %d, exiting!",
320                                    subnet->type);
321                         exit(0);
322         }
323
324         return true;
325 }
326
327 /* Subnet lookup routines */
328
329 subnet_t *lookup_subnet(const node_t *owner, const subnet_t *subnet) {
330         return splay_search(owner->subnet_tree, subnet);
331 }
332
333 subnet_t *lookup_subnet_mac(const node_t *owner, const mac_t *address) {
334         subnet_t *p, *r = NULL;
335         splay_node_t *n;
336         int i;
337
338         // Check if this address is cached
339
340         for(i = 0; i < 2; i++) {
341                 if(!cache_mac_valid[i])
342                         continue;
343                 if(owner && cache_mac_subnet[i] && cache_mac_subnet[i]->owner != owner)
344                         continue;
345                 if(!memcmp(address, &cache_mac_address[i], sizeof *address))
346                         return cache_mac_subnet[i];
347         }
348
349         // Search all subnets for a matching one
350
351         for(n = owner ? owner->subnet_tree->head : subnet_tree->head; n; n = n->next) {
352                 p = n->data;
353                 
354                 if(!p || p->type != SUBNET_MAC)
355                         continue;
356
357                 if(!memcmp(address, &p->net.mac.address, sizeof *address)) {
358                         r = p;
359                         if(p->owner->status.reachable)
360                                 break;
361                 }
362         }
363
364         // Cache the result
365
366         cache_mac_slot = !cache_mac_slot;
367         memcpy(&cache_mac_address[cache_mac_slot], address, sizeof *address);
368         cache_mac_subnet[cache_mac_slot] = r;
369         cache_mac_valid[cache_mac_slot] = true;
370
371         return r;
372 }
373
374 subnet_t *lookup_subnet_ipv4(const ipv4_t *address) {
375         subnet_t *p, *r = NULL;
376         splay_node_t *n;
377         int i;
378
379         // Check if this address is cached
380
381         for(i = 0; i < 2; i++) {
382                 if(!cache_ipv4_valid[i])
383                         continue;
384                 if(!memcmp(address, &cache_ipv4_address[i], sizeof *address))
385                         return cache_ipv4_subnet[i];
386         }
387
388         // Search all subnets for a matching one
389
390         for(n = subnet_tree->head; n; n = n->next) {
391                 p = n->data;
392                 
393                 if(!p || p->type != SUBNET_IPV4)
394                         continue;
395
396                 if(!maskcmp(address, &p->net.ipv4.address, p->net.ipv4.prefixlength)) {
397                         r = p;
398                         if(p->owner->status.reachable)
399                                 break;
400                 }
401         }
402
403         // Cache the result
404
405         cache_ipv4_slot = !cache_ipv4_slot;
406         memcpy(&cache_ipv4_address[cache_ipv4_slot], address, sizeof *address);
407         cache_ipv4_subnet[cache_ipv4_slot] = r;
408         cache_ipv4_valid[cache_ipv4_slot] = true;
409
410         return r;
411 }
412
413 subnet_t *lookup_subnet_ipv6(const ipv6_t *address) {
414         subnet_t *p, *r = NULL;
415         splay_node_t *n;
416         int i;
417
418         // Check if this address is cached
419
420         for(i = 0; i < 2; i++) {
421                 if(!cache_ipv6_valid[i])
422                         continue;
423                 if(!memcmp(address, &cache_ipv6_address[i], sizeof *address))
424                         return cache_ipv6_subnet[i];
425         }
426
427         // Search all subnets for a matching one
428
429         for(n = subnet_tree->head; n; n = n->next) {
430                 p = n->data;
431                 
432                 if(!p || p->type != SUBNET_IPV6)
433                         continue;
434
435                 if(!maskcmp(address, &p->net.ipv6.address, p->net.ipv6.prefixlength)) {
436                         r = p;
437                         if(p->owner->status.reachable)
438                                 break;
439                 }
440         }
441
442         // Cache the result
443
444         cache_ipv6_slot = !cache_ipv6_slot;
445         memcpy(&cache_ipv6_address[cache_ipv6_slot], address, sizeof *address);
446         cache_ipv6_subnet[cache_ipv6_slot] = r;
447         cache_ipv6_valid[cache_ipv6_slot] = true;
448
449         return r;
450 }
451
452 void subnet_update(node_t *owner, subnet_t *subnet, bool up) {
453         splay_node_t *node;
454         int i;
455         char *envp[9] = {0};
456         char netstr[MAXNETSTR];
457         char *name, *address, *port;
458         char empty[] = "";
459
460         // Prepare environment variables to be passed to the script
461
462         xasprintf(&envp[0], "NETNAME=%s", netname ? : "");
463         xasprintf(&envp[1], "DEVICE=%s", device ? : "");
464         xasprintf(&envp[2], "INTERFACE=%s", iface ? : "");
465         xasprintf(&envp[3], "NODE=%s", owner->name);
466
467         if(owner != myself) {
468                 sockaddr2str(&owner->address, &address, &port);
469                 // 4 and 5 are reserved for SUBNET and WEIGHT
470                 xasprintf(&envp[6], "REMOTEADDRESS=%s", address);
471                 xasprintf(&envp[7], "REMOTEPORT=%s", port);
472         }
473
474         name = up ? "subnet-up" : "subnet-down";
475
476         if(!subnet) {
477                 for(node = owner->subnet_tree->head; node; node = node->next) {
478                         subnet = node->data;
479                         if(!net2str(netstr, sizeof netstr, subnet))
480                                 continue;
481                         // Strip the weight from the subnet, and put it in its own environment variable
482                         char *weight = strchr(netstr, '#');
483                         if(weight)
484                                 *weight++ = 0;
485                         else
486                                 weight = empty;
487
488                         // Prepare the SUBNET and WEIGHT variables
489                         if(envp[4])
490                                 free(envp[4]);
491                         if(envp[5])
492                                 free(envp[5]);
493                         xasprintf(&envp[4], "SUBNET=%s", netstr);
494                         xasprintf(&envp[5], "WEIGHT=%s", weight);
495
496                         execute_script(name, envp);
497                 }
498         } else {
499                 if(net2str(netstr, sizeof netstr, subnet)) {
500                         // Strip the weight from the subnet, and put it in its own environment variable
501                         char *weight = strchr(netstr, '#');
502                         if(weight)
503                                 *weight++ = 0;
504                         else
505                                 weight = empty;
506
507                         // Prepare the SUBNET and WEIGHT variables
508                         xasprintf(&envp[4], "SUBNET=%s", netstr);
509                         xasprintf(&envp[5], "WEIGHT=%s", weight);
510
511                         execute_script(name, envp);
512                 }
513         }
514
515         for(i = 0; envp[i] && i < 8; i++)
516                 free(envp[i]);
517 }
518
519 bool dump_subnets(connection_t *c) {
520         char netstr[MAXNETSTR];
521         subnet_t *subnet;
522         splay_node_t *node;
523
524         for(node = subnet_tree->head; node; node = node->next) {
525                 subnet = node->data;
526                 if(!net2str(netstr, sizeof netstr, subnet))
527                         continue;
528                 send_request(c, "%d %d %s owner %s",
529                                 CONTROL, REQ_DUMP_SUBNETS,
530                                 netstr, subnet->owner->name);
531         }
532
533         return send_request(c, "%d %d", CONTROL, REQ_DUMP_SUBNETS);
534 }