Keep peers in a hash table to allow fast address lookups

8 files changed, 213 insertions, 7 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index dcd21bc..f9143db 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -28,6 +28,7 @@ add_executable(fastd
   log.c
   options.c
   peer.c
+  peer_hashtable.c
   poll.c
   random.c
   receive.c
diff --git a/src/fastd.c b/src/fastd.c
index f87f43e..1236e55 100644
--- a/src/fastd.c
+++ b/src/fastd.c
@@ -30,6 +30,7 @@
 #include "crypto.h"
 #include "handshake.h"
 #include "peer.h"
+#include "peer_hashtable.h"
 #include "poll.h"
 #include <fastd_version.h>
 
@@ -854,6 +855,8 @@ int main(int argc, char *argv[]) {
 	VECTOR_ALLOC(ctx.peers, 0);
 	VECTOR_ALLOC(ctx.peers_temp, 0);
 
+	fastd_peer_hashtable_init(&ctx);
+
 	init_peers(&ctx);
 
 	while (!terminate) {
@@ -901,6 +904,8 @@ int main(int argc, char *argv[]) {
 
 	on_post_down(&ctx);
 
+	fastd_peer_hashtable_free(&ctx);
+
 	VECTOR_FREE(ctx.peers_temp);
 	VECTOR_FREE(ctx.peers);
 	VECTOR_FREE(ctx.eth_addrs);
diff --git a/src/fastd.h b/src/fastd.h
index a116baf..8fcd247 100644
--- a/src/fastd.h
+++ b/src/fastd.h
@@ -245,6 +245,9 @@ struct fastd_context {
 
 	VECTOR(fastd_peer_t*) peers_temp;
 
+	uint32_t peer_addr_ht_seed;
+	VECTOR(fastd_peer_t*) *peer_addr_ht;
+
 	fastd_dlist_head_t handshake_queue;
 	struct timespec next_maintenance;
 
diff --git a/src/hash.h b/src/hash.h
new file mode 100644
index 0000000..7a47388
--- /dev/null
+++ b/src/hash.h
@@ -0,0 +1,47 @@
+/*
+  Copyright (c) 2012-2014, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+
+#pragma once
+
+
+#include <stddef.h>
+#include <stdint.h>
+
+
+static inline void fastd_hash(uint32_t *hash, const void *data, size_t len) {
+	size_t i;
+	for (i = 0; i < len; ++i) {
+		*hash += ((uint8_t*)data)[i];
+		*hash += (*hash << 10);
+		*hash ^= (*hash >> 6);
+	}
+}
+
+static inline void fastd_hash_final(uint32_t *hash) {
+	*hash += (*hash << 3);
+	*hash ^= (*hash >> 11);
+	*hash += (*hash << 15);
+}
diff --git a/src/peer.c b/src/peer.c
index ecb7e2c..e7574ef 100644
--- a/src/peer.c
+++ b/src/peer.c
@@ -25,6 +25,7 @@
 
 
 #include "peer.h"
+#include "peer_hashtable.h"
 #include "poll.h"
 
 #include <arpa/inet.h>
@@ -272,6 +273,8 @@ static void delete_peer(fastd_context_t *ctx, fastd_peer_t *peer) {
 		}
 	}
 
+	fastd_peer_hashtable_remove(ctx, peer);
+
 	ctx->conf->protocol->free_peer_state(ctx, peer);
 
 	if (!peer->config)
@@ -392,6 +395,7 @@ static inline void reset_peer_address(fastd_context_t *ctx, fastd_peer_t *peer)
 	if (fastd_peer_is_established(peer))
 		fastd_peer_reset(ctx, peer);
 
+	fastd_peer_hashtable_remove(ctx, peer);
 	memset(&peer->address, 0, sizeof(fastd_peer_address_t));
 }
 
@@ -455,7 +459,13 @@ bool fastd_peer_claim_address(fastd_context_t *ctx, fastd_peer_t *new_peer, fast
 		}
 	}
 
+	fastd_peer_hashtable_remove(ctx, new_peer);
+
 	new_peer->address = *remote_addr;
+
+	if (remote_addr->sa.sa_family != AF_UNSPEC)
+		fastd_peer_hashtable_insert(ctx, new_peer);
+
 	if (sock && sock->addr && sock != new_peer->sock) {
 		free_socket(ctx, new_peer);
 		new_peer->sock = sock;
diff --git a/src/peer_hashtable.c b/src/peer_hashtable.c
new file mode 100644
index 0000000..f6cc11e
--- /dev/null
+++ b/src/peer_hashtable.c
@@ -0,0 +1,107 @@
+/*
+  Copyright (c) 2012-2014, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+
+#include "peer_hashtable.h"
+#include "fastd.h"
+#include "hash.h"
+#include "peer.h"
+
+
+#define PEER_ADDR_HT_SIZE 64
+
+
+void fastd_peer_hashtable_init(fastd_context_t *ctx) {
+	fastd_random_bytes(ctx, &ctx->peer_addr_ht_seed, sizeof(ctx->peer_addr_ht_seed), false);
+
+	ctx->peer_addr_ht = malloc(sizeof(*ctx->peer_addr_ht) * PEER_ADDR_HT_SIZE);
+
+	size_t i;
+	for (i = 0; i < PEER_ADDR_HT_SIZE; i++)
+		VECTOR_ALLOC(ctx->peer_addr_ht[i], 0);
+}
+
+void fastd_peer_hashtable_free(fastd_context_t *ctx) {
+	size_t i;
+	for (i = 0; i < PEER_ADDR_HT_SIZE; i++)
+		VECTOR_FREE(ctx->peer_addr_ht[i]);
+
+	free(ctx->peer_addr_ht);
+}
+
+static size_t peer_address_bucket(fastd_context_t *ctx, 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, sizeof(addr->in));
+		break;
+
+	case AF_INET6:
+		fastd_hash(&hash, &addr->in6, sizeof(addr->in6));
+		break;
+
+	default:
+		exit_bug(ctx, "peer_address_bucket: unknown address family");
+	}
+
+	fastd_hash_final(&hash);
+
+	return hash % PEER_ADDR_HT_SIZE;
+}
+
+void fastd_peer_hashtable_insert(fastd_context_t *ctx, fastd_peer_t *peer) {
+	size_t b = peer_address_bucket(ctx, &peer->address);
+	VECTOR_ADD(ctx->peer_addr_ht[b], peer);
+}
+
+void fastd_peer_hashtable_remove(fastd_context_t *ctx, fastd_peer_t *peer) {
+	if (!peer->address.sa.sa_family)
+		return;
+
+	size_t b = peer_address_bucket(ctx, &peer->address);
+
+	size_t i;
+	for (i = 0; i < VECTOR_LEN(ctx->peer_addr_ht[b]); i++) {
+		if (VECTOR_INDEX(ctx->peer_addr_ht[b], i) == peer) {
+			VECTOR_DELETE(ctx->peer_addr_ht[b], i);
+			break;
+		}
+	}
+}
+
+fastd_peer_t *fastd_peer_hashtable_lookup(fastd_context_t *ctx, const fastd_peer_address_t *addr) {
+	size_t b = peer_address_bucket(ctx, addr);
+
+	size_t i;
+	for (i = 0; i < VECTOR_LEN(ctx->peer_addr_ht[b]); i++) {
+		fastd_peer_t *peer = VECTOR_INDEX(ctx->peer_addr_ht[b], i);
+
+		if (fastd_peer_address_equal(&peer->address, addr))
+			return peer;
+	}
+
+	return NULL;
+}
diff --git a/src/peer_hashtable.h b/src/peer_hashtable.h
new file mode 100644
index 0000000..5952ae4
--- /dev/null
+++ b/src/peer_hashtable.h
@@ -0,0 +1,38 @@
+/*
+  Copyright (c) 2012-2014, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+
+#pragma once
+
+
+#include "types.h"
+
+
+void fastd_peer_hashtable_init(fastd_context_t *ctx);
+void fastd_peer_hashtable_free(fastd_context_t *ctx);
+
+void fastd_peer_hashtable_insert(fastd_context_t *ctx, fastd_peer_t *peer);
+void fastd_peer_hashtable_remove(fastd_context_t *ctx, fastd_peer_t *peer);
+fastd_peer_t *fastd_peer_hashtable_lookup(fastd_context_t *ctx, const fastd_peer_address_t *addr);
diff --git a/src/receive.c b/src/receive.c
index 5bbab23..32a1c39 100644
--- a/src/receive.c
+++ b/src/receive.c
@@ -27,6 +27,7 @@
 #include "fastd.h"
 #include "handshake.h"
 #include "peer.h"
+#include "peer_hashtable.h"
 
 
 static inline void handle_socket_control(struct msghdr *message, const fastd_socket_t *sock, fastd_peer_address_t *local_addr) {
@@ -163,13 +164,7 @@ static inline void handle_socket_receive(fastd_context_t *ctx, fastd_socket_t *s
 		peer = sock->peer;
 	}
 	else {
-		size_t i;
-		for (i = 0; i < VECTOR_LEN(ctx->peers); i++) {
-			peer = VECTOR_INDEX(ctx->peers, i);
-
-			if (fastd_peer_address_equal(&peer->address, remote_addr))
-				break;
-		}
+		peer = fastd_peer_hashtable_lookup(ctx, remote_addr);
 	}
 
 	if (peer) {