From 5f898aa52f81671cbc54beea19211c8a75e0962f Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Fri, 5 Sep 2014 00:22:21 +0200 Subject: 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. --- src/fastd.h | 2 ++ src/peer_hashtable.c | 41 +++++++++++++++++++++++++++++++++-------- 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 */ -- cgit v1.2.3