Move repeating MIN/MAX macros into dropin.h.
[tinc] / src / subnet.c
1 /*
2     subnet.c -- handle subnet lookups and lists
3     Copyright (C) 2000-2017 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 "hash.h"
26 #include "logger.h"
27 #include "net.h"
28 #include "netutl.h"
29 #include "node.h"
30 #include "script.h"
31 #include "subnet.h"
32 #include "xalloc.h"
33
34 /* lists type of subnet */
35 uint32_t hash_seed;
36 splay_tree_t subnet_tree = {
37         .compare = (splay_compare_t) subnet_compare,
38         .delete = (splay_action_t) free_subnet,
39 };
40
41 /* Subnet lookup cache */
42
43 static uint32_t wrapping_add32(uint32_t a, uint32_t b) {
44         return (uint32_t)((uint64_t)a + b);
45 }
46
47 static uint32_t wrapping_mul32(uint32_t a, uint32_t b) {
48         return (uint32_t)((uint64_t)a * b);
49 }
50
51 static uint32_t hash_function_ipv4_t(const ipv4_t *p) {
52         /*
53         This basic hash works because
54         a) Most IPv4 networks routed via tinc are not /0
55         b) Most IPv4 networks have more unique low order bits
56         */
57         uint16_t *halfwidth = (uint16_t *)p;
58         uint32_t hash = hash_seed;
59
60 #if __BYTE_ORDER == __LITTLE_ENDIAN
61         // 10.0.x.x/16 part
62         hash = wrapping_add32(hash, wrapping_mul32(halfwidth[1], 0x9e370001U));
63
64         // x.x.0.[0-255] part
65 #if SUBNET_HASH_SIZE >= 0x10000
66         return hash ^ halfwidth[0];
67 #else
68         // ensure that we have a /24 with no collisions on 32bit
69         return hash ^ ntohs(halfwidth[0]);
70 #endif // _____LP64_____
71 #else
72         // 10.0.x.x/16 part
73         hash = wrapping_add32(hash, wrapping_mul32(halfwidth[0], 0x9e370001U));
74
75         // x.x.0.[0-255] part (ntohs is nop on big endian)
76         return hash ^ halfwidth[1];
77 #endif // __BYTE_ORDER == __LITTLE_ENDIAN
78 }
79
80
81 static uint32_t hash_function_ipv6_t(const ipv6_t *p) {
82         uint32_t *fullwidth = (uint32_t *)p;
83         uint32_t hash = hash_seed;
84
85         for(int i = 0; i < 4; i++) {
86                 hash = wrapping_add32(hash, fullwidth[i]);
87                 hash = wrapping_mul32(hash, 0x9e370001U);
88         }
89
90         return hash;
91 }
92
93 static uint32_t hash_function_mac_t(const mac_t *p) {
94         uint16_t *halfwidth = (uint16_t *)p;
95         uint32_t hash = hash_seed;
96
97         for(int i = 0; i < 3; i++) {
98                 hash = wrapping_add32(hash, halfwidth[i]);
99                 hash = wrapping_mul32(hash, 0x9e370001U);
100         }
101
102         return hash;
103 }
104
105 hash_define(ipv4_t, SUBNET_HASH_SIZE)
106 hash_define(ipv6_t, SUBNET_HASH_SIZE)
107 hash_define(mac_t, SUBNET_HASH_SIZE)
108
109 hash_new(ipv4_t, ipv4_cache);
110 hash_new(ipv6_t, ipv6_cache);
111 hash_new(mac_t, mac_cache);
112
113
114 void subnet_cache_flush_table(subnet_type_t stype) {
115         // NOTE: a subnet type of SUBNET_TYPES can be used to clear all hash tables
116
117         if(stype != SUBNET_IPV6) { // ipv4
118                 hash_clear(ipv4_t, &ipv4_cache);
119         }
120
121         if(stype != SUBNET_IPV4) { // ipv6
122                 hash_clear(ipv6_t, &ipv6_cache);
123         }
124
125         hash_clear(mac_t, &mac_cache);
126 }
127
128 /* Initialising trees */
129
130 void init_subnets(void) {
131         hash_seed = (uint32_t)rand();
132
133         // tables need to be cleared on startup
134         subnet_cache_flush_tables();
135 }
136
137 void exit_subnets(void) {
138         splay_empty_tree(&subnet_tree);
139         subnet_cache_flush_tables();
140 }
141
142 void init_subnet_tree(splay_tree_t *tree) {
143         memset(tree, 0, sizeof(*tree));
144         tree->compare = (splay_compare_t) subnet_compare;
145 }
146
147 /* Allocating and freeing space for subnets */
148
149 subnet_t *new_subnet(void) {
150         return xzalloc(sizeof(subnet_t));
151 }
152
153 void free_subnet(subnet_t *subnet) {
154         free(subnet);
155 }
156
157 void subnet_cache_flush_tables(void) {
158         // flushes all the tables
159         hash_clear(ipv4_t, &ipv4_cache);
160         hash_clear(ipv6_t, &ipv6_cache);
161         hash_clear(mac_t, &mac_cache);
162 }
163
164 void subnet_cache_flush(subnet_t *subnet) {
165         switch(subnet->type) {
166         case SUBNET_IPV4:
167                 if(subnet->net.ipv4.prefixlength == 32) {
168                         hash_delete(ipv4_t, &ipv4_cache, &subnet->net.ipv4.address);
169                         return;
170                 }
171
172                 break;
173
174         case SUBNET_IPV6:
175                 if(subnet->net.ipv4.prefixlength == 128) {
176                         hash_delete(ipv6_t, &ipv6_cache, &subnet->net.ipv6.address);
177                         return;
178                 }
179
180                 break;
181
182         case SUBNET_MAC:
183                 hash_delete(mac_t, &mac_cache, &subnet->net.mac.address);
184                 return;
185         }
186
187         subnet_cache_flush_table(subnet->type);
188 }
189
190 /* Adding and removing subnets */
191
192 void subnet_add(node_t *n, subnet_t *subnet) {
193         subnet->owner = n;
194
195         splay_insert(&subnet_tree, subnet);
196
197         if(n) {
198                 splay_insert(&n->subnet_tree, subnet);
199         }
200
201         subnet_cache_flush(subnet);
202 }
203
204 void subnet_del(node_t *n, subnet_t *subnet) {
205         if(n) {
206                 splay_delete(&n->subnet_tree, subnet);
207         }
208
209         splay_delete(&subnet_tree, subnet);
210
211         subnet_cache_flush(subnet);
212 }
213
214 /* Subnet lookup routines */
215
216 subnet_t *lookup_subnet(node_t *owner, const subnet_t *subnet) {
217         return splay_search(&owner->subnet_tree, subnet);
218 }
219
220 subnet_t *lookup_subnet_mac(const node_t *owner, const mac_t *address) {
221         subnet_t *r = NULL;
222
223         // Check if this address is cached
224
225         if((r = hash_search(mac_t, &mac_cache, address))) {
226                 return r;
227         }
228
229         // Search all subnets for a matching one
230
231         for splay_each(subnet_t, p, owner ? &owner->subnet_tree : &subnet_tree) {
232                 if(!p || p->type != SUBNET_MAC) {
233                         continue;
234                 }
235
236                 if(!memcmp(address, &p->net.mac.address, sizeof(*address))) {
237                         r = p;
238
239                         if(!p->owner || p->owner->status.reachable) {
240                                 break;
241                         }
242                 }
243         }
244
245         // Cache the result
246
247         if(r) {
248                 hash_insert(mac_t, &mac_cache, address, r);
249         }
250
251         return r;
252 }
253
254 subnet_t *lookup_subnet_ipv4(const ipv4_t *address) {
255         subnet_t *r = NULL;
256
257         // Check if this address is cached
258
259         if((r = hash_search(ipv4_t, &ipv4_cache, address))) {
260                 return r;
261         }
262
263         // Search all subnets for a matching one
264
265         for splay_each(subnet_t, p, &subnet_tree) {
266                 if(!p || p->type != SUBNET_IPV4) {
267                         continue;
268                 }
269
270                 if(!maskcmp(address, &p->net.ipv4.address, p->net.ipv4.prefixlength)) {
271                         r = p;
272
273                         if(!p->owner || p->owner->status.reachable) {
274                                 break;
275                         }
276                 }
277         }
278
279         // Cache the result
280
281         if(r) {
282                 hash_insert(ipv4_t, &ipv4_cache, address, r);
283         }
284
285         return r;
286 }
287
288 subnet_t *lookup_subnet_ipv6(const ipv6_t *address) {
289         subnet_t *r = NULL;
290
291         // Check if this address is cached
292
293         if((r = hash_search(ipv6_t, &ipv6_cache, address))) {
294                 return r;
295         }
296
297         // Search all subnets for a matching one
298
299         for splay_each(subnet_t, p, &subnet_tree) {
300                 if(!p || p->type != SUBNET_IPV6) {
301                         continue;
302                 }
303
304                 if(!maskcmp(address, &p->net.ipv6.address, p->net.ipv6.prefixlength)) {
305                         r = p;
306
307                         if(!p->owner || p->owner->status.reachable) {
308                                 break;
309                         }
310                 }
311         }
312
313         // Cache the result
314
315         if(r) {
316                 hash_insert(ipv6_t, &ipv6_cache, address, r);
317         }
318
319         return r;
320 }
321
322 void subnet_update(node_t *owner, subnet_t *subnet, bool up) {
323         char netstr[MAXNETSTR];
324         char *name, *address, *port;
325         char empty[] = "";
326
327         // Prepare environment variables to be passed to the script
328
329         environment_t env;
330         environment_init(&env);
331         environment_add(&env, "NODE=%s", owner->name);
332
333         if(owner != myself) {
334                 sockaddr2str(&owner->address, &address, &port);
335                 environment_add(&env, "REMOTEADDRESS=%s", address);
336                 environment_add(&env, "REMOTEPORT=%s", port);
337                 free(port);
338                 free(address);
339         }
340
341         int env_subnet = environment_add(&env, NULL);
342         int env_weight = environment_add(&env, NULL);
343
344         name = up ? "subnet-up" : "subnet-down";
345
346         if(!subnet) {
347                 for splay_each(subnet_t, subnet, &owner->subnet_tree) {
348                         if(!net2str(netstr, sizeof(netstr), subnet)) {
349                                 continue;
350                         }
351
352                         // Strip the weight from the subnet, and put it in its own environment variable
353                         char *weight = strchr(netstr, '#');
354
355                         if(weight) {
356                                 *weight++ = 0;
357                         } else {
358                                 weight = empty;
359                         }
360
361                         // Prepare the SUBNET and WEIGHT variables
362                         environment_update(&env, env_subnet, "SUBNET=%s", netstr);
363                         environment_update(&env, env_weight, "WEIGHT=%s", weight);
364
365                         execute_script(name, &env);
366                 }
367         } else {
368                 if(net2str(netstr, sizeof(netstr), subnet)) {
369                         // Strip the weight from the subnet, and put it in its own environment variable
370                         char *weight = strchr(netstr, '#');
371
372                         if(weight) {
373                                 *weight++ = 0;
374                         } else {
375                                 weight = empty;
376                         }
377
378                         // Prepare the SUBNET and WEIGHT variables
379                         environment_update(&env, env_subnet, "SUBNET=%s", netstr);
380                         environment_update(&env, env_weight, "WEIGHT=%s", weight);
381
382                         execute_script(name, &env);
383                 }
384         }
385
386         environment_exit(&env);
387 }
388
389 bool dump_subnets(connection_t *c) {
390         for splay_each(subnet_t, subnet, &subnet_tree) {
391                 char netstr[MAXNETSTR];
392
393                 if(!net2str(netstr, sizeof(netstr), subnet)) {
394                         continue;
395                 }
396
397                 send_request(c, "%d %d %s %s",
398                              CONTROL, REQ_DUMP_SUBNETS,
399                              netstr, subnet->owner ? subnet->owner->name : "(broadcast)");
400         }
401
402         return send_request(c, "%d %d", CONTROL, REQ_DUMP_SUBNETS);
403 }