When purging nodes, only delete them if nobody references them anymore.
[tinc] / src / subnet.c
1 /*
2     subnet.c -- handle subnet lookups and lists
3     Copyright (C) 2000-2003 Guus Sliepen <guus@sliepen.eu.org>,
4                   2000-2003 Ivo Timmermans <ivo@o2w.nl>
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: subnet.c,v 1.1.2.49 2003/07/30 11:50:45 guus Exp $
21 */
22
23 #include "system.h"
24
25 #include "avl_tree.h"
26 #include "logger.h"
27 #include "net.h"
28 #include "netutl.h"
29 #include "node.h"
30 #include "subnet.h"
31 #include "utils.h"
32 #include "xalloc.h"
33
34 /* lists type of subnet */
35
36 avl_tree_t *subnet_tree;
37
38 /* Subnet comparison */
39
40 static int subnet_compare_mac(const subnet_t *a, const subnet_t *b)
41 {
42         int result;
43
44         result = memcmp(&a->net.mac.address, &b->net.mac.address, sizeof(mac_t));
45
46         if(result || !a->owner || !b->owner)
47                 return result;
48
49         return strcmp(a->owner->name, b->owner->name);
50 }
51
52 static int subnet_compare_ipv4(const subnet_t *a, const subnet_t *b)
53 {
54         int result;
55
56         result = memcmp(&a->net.ipv4.address, &b->net.ipv4.address, sizeof(ipv4_t));
57
58         if(result)
59                 return result;
60
61         result = a->net.ipv4.prefixlength - b->net.ipv4.prefixlength;
62
63         if(result || !a->owner || !b->owner)
64                 return result;
65
66         return strcmp(a->owner->name, b->owner->name);
67 }
68
69 static int subnet_compare_ipv6(const subnet_t *a, const subnet_t *b)
70 {
71         int result;
72
73         result = memcmp(&a->net.ipv6.address, &b->net.ipv6.address, sizeof(ipv6_t));
74
75         if(result)
76                 return result;
77
78         result = a->net.ipv6.prefixlength - b->net.ipv6.prefixlength;
79
80         if(result || !a->owner || !b->owner)
81                 return result;
82
83         return strcmp(a->owner->name, b->owner->name);
84 }
85
86 static int subnet_compare(const subnet_t *a, const subnet_t *b)
87 {
88         int result;
89
90         result = a->type - b->type;
91
92         if(result)
93                 return result;
94
95         switch (a->type) {
96         case SUBNET_MAC:
97                 return subnet_compare_mac(a, b);
98         case SUBNET_IPV4:
99                 return subnet_compare_ipv4(a, b);
100         case SUBNET_IPV6:
101                 return subnet_compare_ipv6(a, b);
102         default:
103                 logger(LOG_ERR, _("subnet_compare() was called with unknown subnet type %d, exitting!"),
104                            a->type);
105                 cp_trace();
106                 exit(0);
107         }
108
109         return 0;
110 }
111
112 /* Initialising trees */
113
114 void init_subnets(void)
115 {
116         cp();
117
118         subnet_tree = avl_alloc_tree((avl_compare_t) subnet_compare, (avl_action_t) free_subnet);
119 }
120
121 void exit_subnets(void)
122 {
123         cp();
124
125         avl_delete_tree(subnet_tree);
126 }
127
128 avl_tree_t *new_subnet_tree(void)
129 {
130         cp();
131
132         return avl_alloc_tree((avl_compare_t) subnet_compare, NULL);
133 }
134
135 void free_subnet_tree(avl_tree_t *subnet_tree)
136 {
137         cp();
138
139         avl_delete_tree(subnet_tree);
140 }
141
142 /* Allocating and freeing space for subnets */
143
144 subnet_t *new_subnet(void)
145 {
146         cp();
147
148         return (subnet_t *) xmalloc_and_zero(sizeof(subnet_t));
149 }
150
151 void free_subnet(subnet_t *subnet)
152 {
153         cp();
154
155         free(subnet);
156 }
157
158 /* Adding and removing subnets */
159
160 void subnet_add(node_t *n, subnet_t *subnet)
161 {
162         cp();
163
164         subnet->owner = n;
165
166         avl_insert(subnet_tree, subnet);
167         avl_insert(n->subnet_tree, subnet);
168 }
169
170 void subnet_del(node_t *n, subnet_t *subnet)
171 {
172         cp();
173
174         avl_delete(n->subnet_tree, subnet);
175         avl_delete(subnet_tree, subnet);
176 }
177
178 /* Ascii representation of subnets */
179
180 subnet_t *str2net(const char *subnetstr)
181 {
182         int i, l;
183         subnet_t *subnet;
184         uint16_t x[8];
185
186         cp();
187
188         subnet = new_subnet();
189
190         if(sscanf(subnetstr, "%hu.%hu.%hu.%hu/%d",
191                           &x[0], &x[1], &x[2], &x[3], &l) == 5) {
192                 subnet->type = SUBNET_IPV4;
193                 subnet->net.ipv4.prefixlength = l;
194
195                 for(i = 0; i < 4; i++)
196                         subnet->net.ipv4.address.x[i] = x[i];
197
198                 return subnet;
199         }
200
201         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx/%d",
202                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5], &x[6], &x[7],
203                           &l) == 9) {
204                 subnet->type = SUBNET_IPV6;
205                 subnet->net.ipv6.prefixlength = l;
206
207                 for(i = 0; i < 8; i++)
208                         subnet->net.ipv6.address.x[i] = htons(x[i]);
209
210                 return subnet;
211         }
212
213         if(sscanf(subnetstr, "%hu.%hu.%hu.%hu", &x[0], &x[1], &x[2], &x[3]) == 4) {
214                 subnet->type = SUBNET_IPV4;
215                 subnet->net.ipv4.prefixlength = 32;
216
217                 for(i = 0; i < 4; i++)
218                         subnet->net.ipv4.address.x[i] = x[i];
219
220                 return subnet;
221         }
222
223         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx",
224                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5], &x[6], &x[7]) == 8) {
225                 subnet->type = SUBNET_IPV6;
226                 subnet->net.ipv6.prefixlength = 128;
227
228                 for(i = 0; i < 8; i++)
229                         subnet->net.ipv6.address.x[i] = htons(x[i]);
230
231                 return subnet;
232         }
233
234         if(sscanf(subnetstr, "%hx:%hx:%hx:%hx:%hx:%hx",
235                           &x[0], &x[1], &x[2], &x[3], &x[4], &x[5]) == 6) {
236                 subnet->type = SUBNET_MAC;
237
238                 for(i = 0; i < 6; i++)
239                         subnet->net.mac.address.x[i] = x[i];
240
241                 return subnet;
242         }
243
244         free(subnet);
245
246         return NULL;
247 }
248
249 char *net2str(const subnet_t *subnet)
250 {
251         char *netstr;
252
253         cp();
254
255         switch (subnet->type) {
256                 case SUBNET_MAC:
257                         asprintf(&netstr, "%hx:%hx:%hx:%hx:%hx:%hx",
258                                          subnet->net.mac.address.x[0],
259                                          subnet->net.mac.address.x[1],
260                                          subnet->net.mac.address.x[2],
261                                          subnet->net.mac.address.x[3],
262                                          subnet->net.mac.address.x[4], subnet->net.mac.address.x[5]);
263                         break;
264
265                 case SUBNET_IPV4:
266                         asprintf(&netstr, "%hu.%hu.%hu.%hu/%d",
267                                          subnet->net.ipv4.address.x[0],
268                                          subnet->net.ipv4.address.x[1],
269                                          subnet->net.ipv4.address.x[2],
270                                          subnet->net.ipv4.address.x[3], subnet->net.ipv4.prefixlength);
271                         break;
272
273                 case SUBNET_IPV6:
274                         asprintf(&netstr, "%hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx/%d",
275                                          ntohs(subnet->net.ipv6.address.x[0]),
276                                          ntohs(subnet->net.ipv6.address.x[1]),
277                                          ntohs(subnet->net.ipv6.address.x[2]),
278                                          ntohs(subnet->net.ipv6.address.x[3]),
279                                          ntohs(subnet->net.ipv6.address.x[4]),
280                                          ntohs(subnet->net.ipv6.address.x[5]),
281                                          ntohs(subnet->net.ipv6.address.x[6]),
282                                          ntohs(subnet->net.ipv6.address.x[7]),
283                                          subnet->net.ipv6.prefixlength);
284                         break;
285
286                 default:
287                         logger(LOG_ERR,
288                                    _("net2str() was called with unknown subnet type %d, exiting!"),
289                                    subnet->type);
290                         cp_trace();
291                         exit(0);
292         }
293
294         return netstr;
295 }
296
297 /* Subnet lookup routines */
298
299 subnet_t *lookup_subnet(const node_t *owner, const subnet_t *subnet)
300 {
301         cp();
302
303         return avl_search(owner->subnet_tree, subnet);
304 }
305
306 subnet_t *lookup_subnet_mac(const mac_t *address)
307 {
308         subnet_t *p, subnet = {0};
309
310         cp();
311
312         subnet.type = SUBNET_MAC;
313         subnet.net.mac.address = *address;
314         subnet.owner = NULL;
315
316         p = (subnet_t *) avl_search(subnet_tree, &subnet);
317
318         return p;
319 }
320
321 subnet_t *lookup_subnet_ipv4(const ipv4_t *address)
322 {
323         subnet_t *p, subnet = {0};
324
325         cp();
326
327         subnet.type = SUBNET_IPV4;
328         subnet.net.ipv4.address = *address;
329         subnet.net.ipv4.prefixlength = 32;
330         subnet.owner = NULL;
331
332         do {
333                 /* Go find subnet */
334
335                 p = (subnet_t *) avl_search_closest_smaller(subnet_tree, &subnet);
336
337                 /* Check if the found subnet REALLY matches */
338
339                 if(p) {
340                         if(p->type != SUBNET_IPV4) {
341                                 p = NULL;
342                                 break;
343                         }
344
345                         if(!maskcmp(address, &p->net.ipv4.address, p->net.ipv4.prefixlength, sizeof(ipv4_t)))
346                                 break;
347                         else {
348                                 /* Otherwise, see if there is a bigger enclosing subnet */
349
350                                 subnet.net.ipv4.prefixlength = p->net.ipv4.prefixlength - 1;
351                                 maskcpy(&subnet.net.ipv4.address, &p->net.ipv4.address, subnet.net.ipv4.prefixlength, sizeof(ipv4_t));
352                         }
353                 }
354         } while(p);
355
356         return p;
357 }
358
359 subnet_t *lookup_subnet_ipv6(const ipv6_t *address)
360 {
361         subnet_t *p, subnet = {0};
362
363         cp();
364
365         subnet.type = SUBNET_IPV6;
366         subnet.net.ipv6.address = *address;
367         subnet.net.ipv6.prefixlength = 128;
368         subnet.owner = NULL;
369
370         do {
371                 /* Go find subnet */
372
373                 p = (subnet_t *) avl_search_closest_smaller(subnet_tree, &subnet);
374
375                 /* Check if the found subnet REALLY matches */
376
377                 if(p) {
378                         if(p->type != SUBNET_IPV6)
379                                 return NULL;
380
381                         if(!maskcmp(address, &p->net.ipv6.address, p->net.ipv6.prefixlength, sizeof(ipv6_t)))
382                                 break;
383                         else {
384                                 /* Otherwise, see if there is a bigger enclosing subnet */
385
386                                 subnet.net.ipv6.prefixlength = p->net.ipv6.prefixlength - 1;
387                                 maskcpy(&subnet.net.ipv6.address, &p->net.ipv6.address, subnet.net.ipv6.prefixlength, sizeof(ipv6_t));
388                         }
389                 }
390         } while(p);
391
392         return p;
393 }
394
395 void dump_subnets(void)
396 {
397         char *netstr;
398         subnet_t *subnet;
399         avl_node_t *node;
400
401         cp();
402
403         logger(LOG_DEBUG, _("Subnet list:"));
404
405         for(node = subnet_tree->head; node; node = node->next) {
406                 subnet = (subnet_t *) node->data;
407                 netstr = net2str(subnet);
408                 logger(LOG_DEBUG, _(" %s owner %s"), netstr, subnet->owner->name);
409                 free(netstr);
410         }
411
412         logger(LOG_DEBUG, _("End of subnet list."));
413 }