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.

1 files changed, 55 insertions, 14 deletions

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