X-Git-Url: https://tinc-vpn.org/git/browse?a=blobdiff_plain;f=src%2Fsubnet.c;h=8c766378f1ee84a7ca7880a32ca1f74d648fe008;hb=9a018c2e371eb1cef9708ac71653f2f2868895fa;hp=04254957c2e4461e371b6106fb4ccbd0ba4761dc;hpb=914d1be411229c28e6e8e4a0df99afa076a8b448;p=tinc diff --git a/src/subnet.c b/src/subnet.c index 04254957..8c766378 100644 --- a/src/subnet.c +++ b/src/subnet.c @@ -32,7 +32,7 @@ #include "xalloc.h" /* lists type of subnet */ - +uint32_t hash_seed; splay_tree_t subnet_tree = { .compare = (splay_compare_t) subnet_compare, .delete = (splay_action_t) free_subnet, @@ -40,30 +40,92 @@ splay_tree_t subnet_tree = { /* Subnet lookup cache */ -static hash_t *ipv4_cache; -static hash_t *ipv6_cache; -static hash_t *mac_cache; +static uint32_t hash_function_ipv4_t(const ipv4_t *p) { + /* + This basic hash works because + a) Most IPv4 networks routed via tinc are not /0 + b) Most IPv4 networks have more unique low order bits + */ + uint16_t *halfwidth = (uint16_t *)p; + uint32_t hash = hash_seed; + +#if __BYTE_ORDER == __LITTLE_ENDIAN + // 10.0.x.x/16 part + hash += halfwidth[1] * 0x9e370001UL; + + // x.x.0.[0-255] part +#if SUBNET_HASH_SIZE >= 0x10000 + return hash ^ halfwidth[0]; +#else + // ensure that we have a /24 with no collisions on 32bit + return hash ^ ntohs(halfwidth[0]); +#endif // _____LP64_____ +#else + // 10.0.x.x/16 part + hash += halfwidth[0] * 0x9e370001UL; + + // x.x.0.[0-255] part (ntohs is nop on big endian) + return hash ^ halfwidth[1]; +#endif // __BYTE_ORDER == __LITTLE_ENDIAN +} + + +static uint32_t hash_function_ipv6_t(const ipv6_t *p) { + uint32_t *fullwidth = (uint32_t *)p; + uint32_t hash = hash_seed; + + for(int i = 0; i < 4; i++) { + hash += fullwidth[i]; + hash *= 0x9e370001UL; + } + + return hash; +} + +static uint32_t hash_function_mac_t(const mac_t *p) { + uint16_t *halfwidth = (uint16_t *)p; + uint32_t hash = hash_seed; + + for(int i = 0; i < 3; i++) { + hash += halfwidth[i]; + hash *= 0x9e370001UL; + } + + return hash; +} + +hash_define(ipv4_t, SUBNET_HASH_SIZE) +hash_define(ipv6_t, SUBNET_HASH_SIZE) +hash_define(mac_t, SUBNET_HASH_SIZE) + +hash_new(ipv4_t, ipv4_cache); +hash_new(ipv6_t, ipv6_cache); +hash_new(mac_t, mac_cache); + + +void subnet_cache_flush_table(subnet_type_t stype) { + // NOTE: a subnet type of SUBNET_TYPES can be used to clear all hash tables -void subnet_cache_flush(void) { - hash_clear(ipv4_cache); - hash_clear(ipv6_cache); - hash_clear(mac_cache); + if(stype != SUBNET_IPV6) { // ipv4 + hash_clear(ipv4_t, &ipv4_cache); + } + + if(stype != SUBNET_IPV4) { // ipv6 + hash_clear(ipv6_t, &ipv6_cache); + } + + hash_clear(mac_t, &mac_cache); } /* Initialising trees */ void init_subnets(void) { - ipv4_cache = hash_alloc(0x100, sizeof(ipv4_t)); - ipv6_cache = hash_alloc(0x100, sizeof(ipv6_t)); - mac_cache = hash_alloc(0x100, sizeof(mac_t)); + hash_seed = (uint32_t)rand(); } void exit_subnets(void) { splay_empty_tree(&subnet_tree); - - hash_free(ipv4_cache); - hash_free(ipv6_cache); - hash_free(mac_cache); + subnet_cache_flush_tables(); } void init_subnet_tree(splay_tree_t *tree) { @@ -81,6 +143,39 @@ void free_subnet(subnet_t *subnet) { free(subnet); } +void subnet_cache_flush_tables(void) { + // flushes all the tables + hash_clear(ipv4_t, &ipv4_cache); + hash_clear(ipv6_t, &ipv6_cache); + hash_clear(mac_t, &mac_cache); +} + +void subnet_cache_flush(subnet_t *subnet) { + switch(subnet->type) { + case SUBNET_IPV4: + if(subnet->net.ipv4.prefixlength == 32) { + hash_delete(ipv4_t, &ipv4_cache, &subnet->net.ipv4.address); + return; + } + + break; + + case SUBNET_IPV6: + if(subnet->net.ipv4.prefixlength == 128) { + hash_delete(ipv6_t, &ipv6_cache, &subnet->net.ipv6.address); + return; + } + + break; + + case SUBNET_MAC: + hash_delete(mac_t, &mac_cache, &subnet->net.mac.address); + return; + } + + subnet_cache_flush_table(subnet->type); +} + /* Adding and removing subnets */ void subnet_add(node_t *n, subnet_t *subnet) { @@ -92,7 +187,7 @@ void subnet_add(node_t *n, subnet_t *subnet) { splay_insert(&n->subnet_tree, subnet); } - subnet_cache_flush(); + subnet_cache_flush(subnet); } void subnet_del(node_t *n, subnet_t *subnet) { @@ -102,7 +197,7 @@ void subnet_del(node_t *n, subnet_t *subnet) { splay_delete(&subnet_tree, subnet); - subnet_cache_flush(); + subnet_cache_flush(subnet); } /* Subnet lookup routines */ @@ -116,7 +211,7 @@ subnet_t *lookup_subnet_mac(const node_t *owner, const mac_t *address) { // Check if this address is cached - if((r = hash_search(mac_cache, address))) { + if((r = hash_search(mac_t, &mac_cache, address))) { return r; } @@ -139,7 +234,7 @@ subnet_t *lookup_subnet_mac(const node_t *owner, const mac_t *address) { // Cache the result if(r) { - hash_insert(mac_cache, address, r); + hash_insert(mac_t, &mac_cache, address, r); } return r; @@ -150,7 +245,7 @@ subnet_t *lookup_subnet_ipv4(const ipv4_t *address) { // Check if this address is cached - if((r = hash_search(ipv4_cache, address))) { + if((r = hash_search(ipv4_t, &ipv4_cache, address))) { return r; } @@ -173,7 +268,7 @@ subnet_t *lookup_subnet_ipv4(const ipv4_t *address) { // Cache the result if(r) { - hash_insert(ipv4_cache, address, r); + hash_insert(ipv4_t, &ipv4_cache, address, r); } return r; @@ -184,7 +279,7 @@ subnet_t *lookup_subnet_ipv6(const ipv6_t *address) { // Check if this address is cached - if((r = hash_search(ipv6_cache, address))) { + if((r = hash_search(ipv6_t, &ipv6_cache, address))) { return r; } @@ -207,7 +302,7 @@ subnet_t *lookup_subnet_ipv6(const ipv6_t *address) { // Cache the result if(r) { - hash_insert(ipv6_cache, address, r); + hash_insert(ipv6_t, &ipv6_cache, address, r); } return r;