Implement new hash table to keep track of unknown peers handshakes have been sent to

This should significantly reduce the number of handshakes sent after restarting
fastd with many active connections.

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;
 }