From 9a018c2e371eb1cef9708ac71653f2f2868895fa Mon Sep 17 00:00:00 2001 From: Mathew Heard Date: Tue, 29 Jun 2021 11:27:24 +1000 Subject: [PATCH] Subnet Cache hashtable improvements - inline & staticly allocated hash table - increased hashtable size (32bit: 1024, 64bit: 65536) - re-arrange subnet members - Add key type - reduce clearing of hash table - cleanup key pointer operations - removed unused hash_search_or_insert - add open addressing to hash table - type specific hash functions & hash seeding - no collisions for 32bit os - implement cache flush by SUBNET_MAC --- src/Makefile.am | 2 +- src/graph.c | 2 +- src/hash.c | 128 ------------------------------------------- src/hash.h | 70 ++++++++++++++++++------ src/subnet.c | 141 ++++++++++++++++++++++++++++++++++++++++-------- src/subnet.h | 10 ++-- src/system.h | 6 +++ 7 files changed, 186 insertions(+), 173 deletions(-) delete mode 100644 src/hash.c diff --git a/src/Makefile.am b/src/Makefile.am index 12bfe176..792dd784 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -74,7 +74,7 @@ tincd_SOURCES = \ event.c event.h \ fd_device.c \ graph.c graph.h \ - hash.c hash.h \ + hash.h \ keys.c keys.h \ have.h \ ipv4.h \ diff --git a/src/graph.c b/src/graph.c index 3dd2ff18..da649091 100644 --- a/src/graph.c +++ b/src/graph.c @@ -307,7 +307,7 @@ static void check_reachability(void) { } void graph(void) { - subnet_cache_flush(); + subnet_cache_flush_tables(); sssp_bfs(); check_reachability(); mst_kruskal(); diff --git a/src/hash.c b/src/hash.c deleted file mode 100644 index 39e88c99..00000000 --- a/src/hash.c +++ /dev/null @@ -1,128 +0,0 @@ -/* - hash.c -- hash table management - Copyright (C) 2012-2013 Guus Sliepen - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License along - with this program; if not, write to the Free Software Foundation, Inc., - 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. -*/ - -#include "system.h" - -#include "hash.h" -#include "xalloc.h" - -/* Generic hash function */ - -static uint32_t hash_function(const void *p, size_t len) { - const uint8_t *q = p; - uint32_t hash = 0; - - while(true) { - for(size_t i = len > 4 ? 4 : len; --i;) { - hash += (uint32_t)q[len - i] << (8 * i); - } - - hash = (uint32_t)(hash * 0x9e370001UL); // Golden ratio prime. - - if(len <= 4) { - break; - } - - len -= 4; - } - - return hash; -} - -/* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */ - -static uint32_t modulo(uint32_t hash, size_t n) { - if(n == 0x100) { - return (hash >> 24) ^ ((hash >> 16) & 0xff) ^ ((hash >> 8) & 0xff) ^ (hash & 0xff); - } else if(n == 0x10000) { - return (hash >> 16) ^ (hash & 0xffff); - } else { - return hash % n; - } -} - -/* (De)allocation */ - -hash_t *hash_alloc(size_t n, size_t size) { - hash_t *hash = xzalloc(sizeof(*hash)); - hash->n = n; - hash->size = size; - hash->keys = xzalloc(hash->n * hash->size); - hash->values = xzalloc(hash->n * sizeof(*hash->values)); - return hash; -} - -void hash_free(hash_t *hash) { - free(hash->keys); - free(hash->values); - free(hash); -} - -/* Searching and inserting */ - -void hash_insert(hash_t *hash, const void *key, const void *value) { - uint32_t i = modulo(hash_function(key, hash->size), hash->n); - memcpy(hash->keys + i * hash->size, key, hash->size); - hash->values[i] = value; -} - -void *hash_search(const hash_t *hash, const void *key) { - uint32_t i = modulo(hash_function(key, hash->size), hash->n); - - if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) { - return (void *)hash->values[i]; - } - - return NULL; -} - -void *hash_search_or_insert(hash_t *hash, const void *key, const void *value) { - uint32_t i = modulo(hash_function(key, hash->size), hash->n); - - if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) { - return (void *)hash->values[i]; - } - - memcpy(hash->keys + i * hash->size, key, hash->size); - hash->values[i] = value; - return NULL; -} - -/* Deleting */ - -void hash_delete(hash_t *hash, const void *key) { - uint32_t i = modulo(hash_function(key, hash->size), hash->n); - hash->values[i] = NULL; -} - -/* Utility functions */ - -void hash_clear(hash_t *hash) { - memset(hash->values, 0, hash->n * sizeof(*hash->values)); -} - -void hash_resize(hash_t *hash, size_t n) { - hash->keys = xrealloc(hash->keys, n * hash->size); - hash->values = xrealloc(hash->values, n * sizeof(*hash->values)); - - if(n > hash->n) { - memset(hash->keys + hash->n * hash->size, 0, (n - hash->n) * hash->size); - memset(hash->values + hash->n, 0, (n - hash->n) * sizeof(*hash->values)); - } -} diff --git a/src/hash.h b/src/hash.h index 1a6ce32f..45cf6410 100644 --- a/src/hash.h +++ b/src/hash.h @@ -20,25 +20,65 @@ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ -#include "system.h" -typedef struct hash_t { - size_t n; - size_t size; - uint8_t *keys; - const void **values; -} hash_t; +/* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */ -extern hash_t *hash_alloc(size_t n, size_t size) __attribute__((__malloc__)); -extern void hash_free(hash_t *); +uint32_t modulo(uint32_t hash, size_t n); -extern void hash_insert(hash_t *, const void *key, const void *value); -extern void hash_delete(hash_t *, const void *key); +#define HASH_SEARCH_ITERATIONS 4 -extern void *hash_search(const hash_t *, const void *key); -extern void *hash_search_or_insert(hash_t *, const void *key, const void *value); +#define hash_insert(t, ...) hash_insert_ ## t (__VA_ARGS__) +#define hash_delete(t, ...) hash_delete_ ## t (__VA_ARGS__) +#define hash_search(t, ...) hash_search_ ## t (__VA_ARGS__) +#define hash_clear(t, n) hash_clear_ ## t ((n)) -extern void hash_clear(hash_t *); -extern void hash_resize(hash_t *, size_t n); +#define hash_define(t, n) \ + typedef struct hash_ ## t { \ + t keys[n]; \ + const void *values[n]; \ + } hash_ ## t; \ + static uint32_t inline hash_modulo_ ## t(uint32_t hash) { \ + return hash & (n - 1); \ + } \ + void hash_insert_ ## t (hash_ ##t *hash, const t *key, const void *value) { \ + uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \ + for(uint8_t f=0; f< (HASH_SEARCH_ITERATIONS - 1); f++){ \ + if(hash->values[i] == NULL || !memcmp(key, &hash->keys[i], sizeof(#t))) { \ + memcpy(&hash->keys[i], key, sizeof(#t)); \ + hash->values[i] = value; \ + return; \ + } \ + if(++i == n) i = 0; \ + } \ + /* We always pick the last slot. It's unfair. But thats life */ \ + memcpy(&hash->keys[i], key, sizeof(#t)); \ + hash->values[i] = value; \ + } \ + void *hash_search_ ## t (const hash_ ##t *hash, const t *key) { \ + uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \ + for(uint8_t f=0; fkeys[i], sizeof(#t))) { \ + return (void *)hash->values[i]; \ + } \ + if(++i == n) i = 0; \ + } \ + return NULL; \ + } \ + void hash_delete_ ## t (hash_ ##t *hash, const t *key) { \ + uint32_t i = hash_modulo_ ## t(hash_function_ ## t(key)); \ + for(uint8_t f=0; fkeys[i], sizeof(#t))) { \ + hash->values[i] = NULL; \ + return; \ + } \ + if(++i == n) i = 0; \ + } \ + } \ + void hash_clear_ ## t(hash_ ##t *hash) { \ + memset(hash->values, 0, n * sizeof(*hash->values)); \ + } + + +#define hash_new(t, name) static hash_ ## t name #endif 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; diff --git a/src/subnet.h b/src/subnet.h index eb558495..ad0a8b8d 100644 --- a/src/subnet.h +++ b/src/subnet.h @@ -27,8 +27,7 @@ typedef enum subnet_type_t { SUBNET_MAC = 0, SUBNET_IPV4, - SUBNET_IPV6, - SUBNET_TYPES /* Guardian */ + SUBNET_IPV6 } subnet_type_t; typedef struct subnet_mac_t { @@ -36,13 +35,13 @@ typedef struct subnet_mac_t { } subnet_mac_t; typedef struct subnet_ipv4_t { - ipv4_t address; int prefixlength; + ipv4_t address; } subnet_ipv4_t; typedef struct subnet_ipv6_t { - ipv6_t address; int prefixlength; + ipv6_t address; } subnet_ipv6_t; typedef struct subnet_t { @@ -86,6 +85,7 @@ extern subnet_t *lookup_subnet_mac(const struct node_t *owner, const mac_t *addr extern subnet_t *lookup_subnet_ipv4(const ipv4_t *address); extern subnet_t *lookup_subnet_ipv6(const ipv6_t *address); extern bool dump_subnets(struct connection_t *c); -extern void subnet_cache_flush(void); +extern void subnet_cache_flush_tables(void); +extern void subnet_cache_flush_table(subnet_type_t ipver); #endif diff --git a/src/system.h b/src/system.h index f9675f95..b3d9e0ab 100644 --- a/src/system.h +++ b/src/system.h @@ -29,6 +29,12 @@ # define strsignal(p) "" #endif +#if _____LP64_____ +#define SUBNET_HASH_SIZE 0x10000 +#else +#define SUBNET_HASH_SIZE 0x1000 +#endif + /* Other functions */ #include "dropin.h" -- 2.20.1