Dynamically grow hashtable when there are more than twice as many entries as buckets

This allows us to start with a much smaller hashtable and scale much higher.

2 files changed, 35 insertions, 8 deletions

diff --git a/src/fastd.h b/src/fastd.h
index 79d72e1..17689cd 100644
--- a/src/fastd.h
+++ b/src/fastd.h
@@ -253,6 +253,8 @@ struct fastd_context {
 	bool has_floating;			/**< Specifies if any of the configured peers have floating remotes */
 
 	uint32_t peer_addr_ht_seed;		/**< The hash seed used for peer_addr_ht */
+	size_t peer_addr_ht_size;		/**< The number of hash buckets in the peer address hashtable */
+	size_t peer_addr_ht_used;		/**< The current number of entries in the peer address hashtable */
 	VECTOR(fastd_peer_t *) *peer_addr_ht;	/**< An array of hash buckets for the peer hash table */
 
 	fastd_dlist_head_t handshake_queue;	/**< A doubly linked list of the peers currently queued for handshakes (ordered by the time of the next handshake) */
diff --git a/src/peer_hashtable.c b/src/peer_hashtable.c
index 321b0d5..603d6c7 100644
--- a/src/peer_hashtable.c
+++ b/src/peer_hashtable.c
@@ -36,26 +36,42 @@
 #include "peer.h"
 
 
-/** The number of hash buckets used */
-#define PEER_ADDR_HT_SIZE 64
-
-
 /** Initializes the hashtable */
-void fastd_peer_hashtable_init(void) {
+static void init_hashtable(void) {
 	fastd_random_bytes(&ctx.peer_addr_ht_seed, sizeof(ctx.peer_addr_ht_seed), false);
+	ctx.peer_addr_ht = fastd_new0_array(ctx.peer_addr_ht_size, __typeof__(*ctx.peer_addr_ht));
+}
 
-	ctx.peer_addr_ht = fastd_new0_array(PEER_ADDR_HT_SIZE, __typeof__(*ctx.peer_addr_ht));
+/** Initializes the hashtable with the default size */
+void fastd_peer_hashtable_init(void) {
+	ctx.peer_addr_ht_size = 8;
+	init_hashtable();
 }
 
 /** Frees the resources used by the hashtable */
 void fastd_peer_hashtable_free(void) {
 	size_t i;
-	for (i = 0; i < PEER_ADDR_HT_SIZE; i++)
+	for (i = 0; i < ctx.peer_addr_ht_size; i++)
 		VECTOR_FREE(ctx.peer_addr_ht[i]);
 
 	free(ctx.peer_addr_ht);
 }
 
+/** Doubles the size of the peer hashtable and rebuild it afterwards */
+static void resize_hashtable(void) {
+	fastd_peer_hashtable_free();
+	ctx.peer_addr_ht_used = 0;
+
+	ctx.peer_addr_ht_size *= 2;
+	pr_debug("resizing peer address hashtable to %u buckets", (unsigned)ctx.peer_addr_ht_size);
+
+	init_hashtable();
+
+	size_t i;
+	for (i = 0; i < VECTOR_LEN(ctx.peers); i++)
+		fastd_peer_hashtable_insert(VECTOR_INDEX(ctx.peers, i));
+}
+
 /** 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;
@@ -79,7 +95,7 @@ static size_t peer_address_bucket(const fastd_peer_address_t *addr) {
 
 	fastd_hash_final(&hash);
 
-	return hash % PEER_ADDR_HT_SIZE;
+	return hash % ctx.peer_addr_ht_size;
 }
 
 /**
@@ -91,6 +107,13 @@ void fastd_peer_hashtable_insert(fastd_peer_t *peer) {
 	if (!peer->address.sa.sa_family)
 		return;
 
+	ctx.peer_addr_ht_used++;
+
+	if (ctx.peer_addr_ht_used > 2*ctx.peer_addr_ht_size) {
+		resize_hashtable();
+		return;
+	}
+
 	size_t b = peer_address_bucket(&peer->address);
 	VECTOR_ADD(ctx.peer_addr_ht[b], peer);
 }
@@ -113,6 +136,8 @@ void fastd_peer_hashtable_remove(fastd_peer_t *peer) {
 			break;
 		}
 	}
+
+	ctx.peer_addr_ht_used--;
 }
 
 /** Looks up a peer in the hashtable */