diff options
| -rw-r--r-- | src/fastd.c | 5 | ||||
| -rw-r--r-- | src/fastd.h | 6 | ||||
| -rw-r--r-- | src/fastd_config.h.in | 7 | ||||
| -rw-r--r-- | src/peer_hashtable.c | 22 | ||||
| -rw-r--r-- | src/peer_hashtable.h | 24 | ||||
| -rw-r--r-- | src/receive.c | 69 |
6 files changed, 94 insertions, 39 deletions
diff --git a/src/fastd.c b/src/fastd.c index f05b43e..4ac0e8e 100644 --- a/src/fastd.c +++ b/src/fastd.c @@ -489,7 +489,8 @@ static inline void init(int argc, char *argv[]) { fastd_update_time(); ctx.next_maintenance = ctx.now + MAINTENANCE_INTERVAL; - ctx.unknown_handshakes[0].timeout = ctx.now; + + fastd_receive_unknown_init(); #ifdef WITH_DYNAMIC_PEERS fastd_sem_init(&ctx.verify_limit, VERIFY_LIMIT); @@ -663,6 +664,8 @@ static inline void cleanup(void) { ERR_free_strings(); #endif + fastd_receive_unknown_free(); + close_log(); fastd_config_release(); } diff --git a/src/fastd.h b/src/fastd.h index cecb542..9d240b2 100644 --- a/src/fastd.h +++ b/src/fastd.h @@ -320,8 +320,8 @@ struct fastd_context { VECTOR(fastd_peer_eth_addr_t) eth_addrs; /**< Sorted vector of all known ethernet addresses with associated peers and timeouts */ - size_t unknown_handshake_pos; /**< Current start position in the ring buffer unknown_handshakes */ - fastd_handshake_timeout_t unknown_handshakes[8]; /**< Ring buffer of unknown addresses handshakes have been received from */ + uint32_t unknown_handshake_seed; /**< Hash seed for the unknown handshake hashtables */ + fastd_handshake_timeout_t *unknown_handshakes[UNKNOWN_TABLES]; /**< Hash tables unknown addresses handshakes have been sent to */ fastd_protocol_state_t *protocol_state; /**< Protocol-specific state */ }; @@ -341,6 +341,8 @@ void fastd_send(const fastd_socket_t *sock, const fastd_peer_address_t *local_ad void fastd_send_handshake(const fastd_socket_t *sock, const fastd_peer_address_t *local_addr, const fastd_peer_address_t *remote_addr, fastd_peer_t *peer, fastd_buffer_t buffer); void fastd_send_data(fastd_buffer_t buffer, fastd_peer_t *source); +void fastd_receive_unknown_init(void); +void fastd_receive_unknown_free(void); void fastd_receive(fastd_socket_t *sock); void fastd_handle_receive(fastd_peer_t *peer, fastd_buffer_t buffer, bool reordered); diff --git a/src/fastd_config.h.in b/src/fastd_config.h.in index 03ccc56..6a55930 100644 --- a/src/fastd_config.h.in +++ b/src/fastd_config.h.in @@ -146,6 +146,13 @@ /** The minimum interval between two resolves of the same remote */ #define MIN_RESOLVE_INTERVAL 15000 /* 15 seconds */ +/** The number of hash tables for backoff_unknown() */ +#define UNKNOWN_TABLES 16 + +/** The number of entries per unknown peer table */ +#define UNKNOWN_ENTRIES 64 + + /** How long a session stays valid after a key is negotiated */ #define KEY_VALID 3600000 /* 60 minutes */ diff --git a/src/peer_hashtable.c b/src/peer_hashtable.c index 4b606b0..d499be7 100644 --- a/src/peer_hashtable.c +++ b/src/peer_hashtable.c @@ -31,9 +31,6 @@ #include "peer_hashtable.h" -#include "fastd.h" -#include "hash.h" -#include "peer.h" /** Initializes the hashtable */ @@ -75,24 +72,7 @@ static void resize_hashtable(void) { /** Gets the hash bucket used for an address */ static size_t peer_address_bucket(const fastd_peer_address_t *addr) { uint32_t hash = ctx.peer_addr_ht_seed; - - switch(addr->sa.sa_family) { - case AF_INET: - fastd_hash(&hash, &addr->in.sin_addr.s_addr, sizeof(addr->in.sin_addr.s_addr)); - fastd_hash(&hash, &addr->in.sin_port, sizeof(addr->in.sin_port)); - break; - - case AF_INET6: - fastd_hash(&hash, &addr->in6.sin6_addr, sizeof(addr->in6.sin6_addr)); - fastd_hash(&hash, &addr->in6.sin6_port, sizeof(addr->in6.sin6_port)); - if (IN6_IS_ADDR_LINKLOCAL(&addr->in6.sin6_addr)) - fastd_hash(&hash, &addr->in6.sin6_scope_id, sizeof(addr->in6.sin6_scope_id)); - break; - - default: - exit_bug("peer_address_bucket: unknown address family"); - } - + fastd_peer_address_hash(&hash, addr); fastd_hash_final(&hash); return hash % ctx.peer_addr_ht_size; diff --git a/src/peer_hashtable.h b/src/peer_hashtable.h index 0923a50..79b8f28 100644 --- a/src/peer_hashtable.h +++ b/src/peer_hashtable.h @@ -33,7 +33,29 @@ #pragma once -#include "types.h" +#include "hash.h" +#include "peer.h" + + +/** Hashes a peer address */ +static inline void fastd_peer_address_hash(uint32_t *hash, const fastd_peer_address_t *addr) { + switch(addr->sa.sa_family) { + case AF_INET: + fastd_hash(hash, &addr->in.sin_addr.s_addr, sizeof(addr->in.sin_addr.s_addr)); + fastd_hash(hash, &addr->in.sin_port, sizeof(addr->in.sin_port)); + break; + + case AF_INET6: + fastd_hash(hash, &addr->in6.sin6_addr, sizeof(addr->in6.sin6_addr)); + fastd_hash(hash, &addr->in6.sin6_port, sizeof(addr->in6.sin6_port)); + if (IN6_IS_ADDR_LINKLOCAL(&addr->in6.sin6_addr)) + fastd_hash(hash, &addr->in6.sin6_scope_id, sizeof(addr->in6.sin6_scope_id)); + break; + + default: + exit_bug("peer_address_bucket: unknown address family"); + } +} void fastd_peer_hashtable_init(void); diff --git a/src/receive.c b/src/receive.c index 22c26c5..2ee402a 100644 --- a/src/receive.c +++ b/src/receive.c @@ -32,6 +32,7 @@ #include "fastd.h" #include "handshake.h" +#include "hash.h" #include "peer.h" #include "peer_hashtable.h" @@ -86,34 +87,74 @@ static inline void handle_socket_control(struct msghdr *message, const fastd_soc } } +/** Initializes the hashtables used to keep track of handshakes sent to unknown peers */ +void fastd_receive_unknown_init(void) { + size_t i, j; + for (i = 0; i < UNKNOWN_TABLES; i++) { + ctx.unknown_handshakes[i] = fastd_new0_array(UNKNOWN_ENTRIES, fastd_handshake_timeout_t); + + for (j = 0; j < UNKNOWN_ENTRIES; j++) + ctx.unknown_handshakes[i][j].timeout = ctx.now; + } + + fastd_random_bytes(&ctx.unknown_handshake_seed, sizeof(ctx.unknown_handshake_seed), false); +} + +/** Frees the hashtables used to keep track of handshakes sent to unknown peers */ +void fastd_receive_unknown_free(void) { + size_t i; + for (i = 0; i < UNKNOWN_TABLES; i++) + free(ctx.unknown_handshakes[i]); +} + +/** Returns the i'th hash bucket for a peer address */ +fastd_handshake_timeout_t * unknown_hash_entry(int64_t base, size_t i, const fastd_peer_address_t *addr) { + int64_t slice = base - i; + uint32_t hash = ctx.unknown_handshake_seed; + fastd_hash(&hash, &slice, sizeof(slice)); + fastd_peer_address_hash(&hash, addr); + fastd_hash_final(&hash); + + return &ctx.unknown_handshakes[(size_t)slice % UNKNOWN_TABLES][hash % UNKNOWN_ENTRIES]; +} + + /** Checks if a handshake should be sent after an unexpected payload packet has been received backoff_unknown() tries to avoid flooding hosts with handshakes. */ static bool backoff_unknown(const fastd_peer_address_t *addr) { - size_t i; - for (i = 0; i < array_size(ctx.unknown_handshakes); i++) { - const fastd_handshake_timeout_t *t = &ctx.unknown_handshakes[(ctx.unknown_handshake_pos + i) % array_size(ctx.unknown_handshakes)]; + static const size_t table_interval = MIN_HANDSHAKE_INTERVAL / (UNKNOWN_TABLES - 1); - if (fastd_timed_out(t->timeout)) - break; + int64_t base = ctx.now / table_interval; + size_t first_empty = UNKNOWN_TABLES, i; - if (fastd_peer_address_equal(addr, &t->address)) { - pr_debug2("sent a handshake to unknown address %I a short time ago, not sending again", addr); - return true; + for (i = 0; i < UNKNOWN_TABLES; i++) { + const fastd_handshake_timeout_t *t = unknown_hash_entry(base, i, addr); + + if (fastd_timed_out(t->timeout)) { + if (first_empty == UNKNOWN_TABLES) + first_empty = i; + + continue; } + + if (!fastd_peer_address_equal(addr, &t->address)) + continue; + + pr_debug2("sent a handshake to unknown address %I a short time ago, not sending again", addr); + return true; } - if (ctx.unknown_handshake_pos == 0) - ctx.unknown_handshake_pos = array_size(ctx.unknown_handshakes)-1; - else - ctx.unknown_handshake_pos--; + /* We didn't find the address in any of the hashtables, now insert it */ + if (first_empty == UNKNOWN_TABLES) + first_empty = fastd_rand(0, UNKNOWN_TABLES); - fastd_handshake_timeout_t *t = &ctx.unknown_handshakes[ctx.unknown_handshake_pos]; + fastd_handshake_timeout_t *t = unknown_hash_entry(base, first_empty, addr); t->address = *addr; - t->timeout = ctx.now + MIN_HANDSHAKE_INTERVAL; + t->timeout = ctx.now + MIN_HANDSHAKE_INTERVAL - first_empty * table_interval; return false; } |