summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2014-09-05 00:22:21 +0200
committerMatthias Schiffer <mschiffer@universe-factory.net>2014-09-05 00:22:21 +0200
commit5f898aa52f81671cbc54beea19211c8a75e0962f (patch)
treef413f1ec0159a5072e826d9e3fca3079afa9517a
parent95c81c5d77398517c5d84c4eb2704732a3fb9a41 (diff)
downloadfastd-5f898aa52f81671cbc54beea19211c8a75e0962f.tar
fastd-5f898aa52f81671cbc54beea19211c8a75e0962f.zip
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.
-rw-r--r--src/fastd.h2
-rw-r--r--src/peer_hashtable.c41
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 */