2 subnet.c -- handle subnet lookups and lists
3 Copyright (C) 2000-2017 Guus Sliepen <guus@tinc-vpn.org>,
4 2000-2005 Ivo Timmermans
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.
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.
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.
23 #include "splay_tree.h"
24 #include "control_common.h"
34 /* lists type of subnet */
36 splay_tree_t subnet_tree = {
37 .compare = (splay_compare_t) subnet_compare,
38 .delete = (splay_action_t) free_subnet,
41 /* Subnet lookup cache */
43 static uint32_t hash_function_ipv4_t(const ipv4_t *p) {
45 This basic hash works because
46 a) Most IPv4 networks routed via tinc are not /0
47 b) Most IPv4 networks have more unique low order bits
49 uint16_t *halfwidth = (uint16_t *)p;
50 uint32_t hash = hash_seed;
52 #if __BYTE_ORDER == __LITTLE_ENDIAN
54 hash += halfwidth[1] * 0x9e370001UL;
57 #if SUBNET_HASH_SIZE >= 0x10000
58 return hash ^ halfwidth[0];
60 // ensure that we have a /24 with no collisions on 32bit
61 return hash ^ ntohs(halfwidth[0]);
62 #endif // _____LP64_____
65 hash += halfwidth[0] * 0x9e370001UL;
67 // x.x.0.[0-255] part (ntohs is nop on big endian)
68 return hash ^ halfwidth[1];
69 #endif // __BYTE_ORDER == __LITTLE_ENDIAN
73 static uint32_t hash_function_ipv6_t(const ipv6_t *p) {
74 uint32_t *fullwidth = (uint32_t *)p;
75 uint32_t hash = hash_seed;
77 for(int i = 0; i < 4; i++) {
85 static uint32_t hash_function_mac_t(const mac_t *p) {
86 uint16_t *halfwidth = (uint16_t *)p;
87 uint32_t hash = hash_seed;
89 for(int i = 0; i < 3; i++) {
97 hash_define(ipv4_t, SUBNET_HASH_SIZE)
98 hash_define(ipv6_t, SUBNET_HASH_SIZE)
99 hash_define(mac_t, SUBNET_HASH_SIZE)
101 hash_new(ipv4_t, ipv4_cache);
102 hash_new(ipv6_t, ipv6_cache);
103 hash_new(mac_t, mac_cache);
106 void subnet_cache_flush_table(subnet_type_t stype) {
107 // NOTE: a subnet type of SUBNET_TYPES can be used to clear all hash tables
109 if(stype != SUBNET_IPV6) { // ipv4
110 hash_clear(ipv4_t, &ipv4_cache);
113 if(stype != SUBNET_IPV4) { // ipv6
114 hash_clear(ipv6_t, &ipv6_cache);
117 hash_clear(mac_t, &mac_cache);
120 /* Initialising trees */
122 void init_subnets(void) {
123 hash_seed = (uint32_t)rand();
126 void exit_subnets(void) {
127 splay_empty_tree(&subnet_tree);
128 subnet_cache_flush_tables();
131 void init_subnet_tree(splay_tree_t *tree) {
132 memset(tree, 0, sizeof(*tree));
133 tree->compare = (splay_compare_t) subnet_compare;
136 /* Allocating and freeing space for subnets */
138 subnet_t *new_subnet(void) {
139 return xzalloc(sizeof(subnet_t));
142 void free_subnet(subnet_t *subnet) {
146 void subnet_cache_flush_tables(void) {
147 // flushes all the tables
148 hash_clear(ipv4_t, &ipv4_cache);
149 hash_clear(ipv6_t, &ipv6_cache);
150 hash_clear(mac_t, &mac_cache);
153 void subnet_cache_flush(subnet_t *subnet) {
154 switch(subnet->type) {
156 if(subnet->net.ipv4.prefixlength == 32) {
157 hash_delete(ipv4_t, &ipv4_cache, &subnet->net.ipv4.address);
164 if(subnet->net.ipv4.prefixlength == 128) {
165 hash_delete(ipv6_t, &ipv6_cache, &subnet->net.ipv6.address);
172 hash_delete(mac_t, &mac_cache, &subnet->net.mac.address);
176 subnet_cache_flush_table(subnet->type);
179 /* Adding and removing subnets */
181 void subnet_add(node_t *n, subnet_t *subnet) {
184 splay_insert(&subnet_tree, subnet);
187 splay_insert(&n->subnet_tree, subnet);
190 subnet_cache_flush(subnet);
193 void subnet_del(node_t *n, subnet_t *subnet) {
195 splay_delete(&n->subnet_tree, subnet);
198 splay_delete(&subnet_tree, subnet);
200 subnet_cache_flush(subnet);
203 /* Subnet lookup routines */
205 subnet_t *lookup_subnet(node_t *owner, const subnet_t *subnet) {
206 return splay_search(&owner->subnet_tree, subnet);
209 subnet_t *lookup_subnet_mac(const node_t *owner, const mac_t *address) {
212 // Check if this address is cached
214 if((r = hash_search(mac_t, &mac_cache, address))) {
218 // Search all subnets for a matching one
220 for splay_each(subnet_t, p, owner ? &owner->subnet_tree : &subnet_tree) {
221 if(!p || p->type != SUBNET_MAC) {
225 if(!memcmp(address, &p->net.mac.address, sizeof(*address))) {
228 if(!p->owner || p->owner->status.reachable) {
237 hash_insert(mac_t, &mac_cache, address, r);
243 subnet_t *lookup_subnet_ipv4(const ipv4_t *address) {
246 // Check if this address is cached
248 if((r = hash_search(ipv4_t, &ipv4_cache, address))) {
252 // Search all subnets for a matching one
254 for splay_each(subnet_t, p, &subnet_tree) {
255 if(!p || p->type != SUBNET_IPV4) {
259 if(!maskcmp(address, &p->net.ipv4.address, p->net.ipv4.prefixlength)) {
262 if(!p->owner || p->owner->status.reachable) {
271 hash_insert(ipv4_t, &ipv4_cache, address, r);
277 subnet_t *lookup_subnet_ipv6(const ipv6_t *address) {
280 // Check if this address is cached
282 if((r = hash_search(ipv6_t, &ipv6_cache, address))) {
286 // Search all subnets for a matching one
288 for splay_each(subnet_t, p, &subnet_tree) {
289 if(!p || p->type != SUBNET_IPV6) {
293 if(!maskcmp(address, &p->net.ipv6.address, p->net.ipv6.prefixlength)) {
296 if(!p->owner || p->owner->status.reachable) {
305 hash_insert(ipv6_t, &ipv6_cache, address, r);
311 void subnet_update(node_t *owner, subnet_t *subnet, bool up) {
312 char netstr[MAXNETSTR];
313 char *name, *address, *port;
316 // Prepare environment variables to be passed to the script
319 environment_init(&env);
320 environment_add(&env, "NODE=%s", owner->name);
322 if(owner != myself) {
323 sockaddr2str(&owner->address, &address, &port);
324 environment_add(&env, "REMOTEADDRESS=%s", address);
325 environment_add(&env, "REMOTEPORT=%s", port);
330 int env_subnet = environment_add(&env, NULL);
331 int env_weight = environment_add(&env, NULL);
333 name = up ? "subnet-up" : "subnet-down";
336 for splay_each(subnet_t, subnet, &owner->subnet_tree) {
337 if(!net2str(netstr, sizeof(netstr), subnet)) {
341 // Strip the weight from the subnet, and put it in its own environment variable
342 char *weight = strchr(netstr, '#');
350 // Prepare the SUBNET and WEIGHT variables
351 environment_update(&env, env_subnet, "SUBNET=%s", netstr);
352 environment_update(&env, env_weight, "WEIGHT=%s", weight);
354 execute_script(name, &env);
357 if(net2str(netstr, sizeof(netstr), subnet)) {
358 // Strip the weight from the subnet, and put it in its own environment variable
359 char *weight = strchr(netstr, '#');
367 // Prepare the SUBNET and WEIGHT variables
368 environment_update(&env, env_subnet, "SUBNET=%s", netstr);
369 environment_update(&env, env_weight, "WEIGHT=%s", weight);
371 execute_script(name, &env);
375 environment_exit(&env);
378 bool dump_subnets(connection_t *c) {
379 for splay_each(subnet_t, subnet, &subnet_tree) {
380 char netstr[MAXNETSTR];
382 if(!net2str(netstr, sizeof(netstr), subnet)) {
386 send_request(c, "%d %d %s %s",
387 CONTROL, REQ_DUMP_SUBNETS,
388 netstr, subnet->owner ? subnet->owner->name : "(broadcast)");
391 return send_request(c, "%d %d", CONTROL, REQ_DUMP_SUBNETS);