From b2ec36268f0f33dc9f5af77c373014681fafa7f6 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Mon, 7 Aug 2017 20:45:42 +0200 Subject: hashtables: allow up to 2^{20} peers per interface This allows for nearly 1 million peers per interface, which should be more than enough. If needed later, this number could easily be increased beyond this. We also increase the size of the hashtables to accommodate this upper bound. In the future, it might be smart to dynamically expand the hashtable instead of this hard coded compromise value between small systems and large systems. Ongoing work includes figuring out the most optimal scheme for these hashtables and for the insertion to mask their order from timing inference. --- src/hashtables.c | 22 ++++++++++++++++++++++ src/hashtables.h | 6 ++++-- src/messages.h | 2 +- src/uapi.h | 4 ++-- 4 files changed, 29 insertions(+), 5 deletions(-) diff --git a/src/hashtables.c b/src/hashtables.c index a01a899..b3f5ca3 100644 --- a/src/hashtables.c +++ b/src/hashtables.c @@ -61,6 +61,28 @@ void index_hashtable_init(struct index_hashtable *table) spin_lock_init(&table->lock); } +/* At the moment, we limit ourselves to 2^20 total peers, which generally might amount to 2^20*3 + * items in this hashtable. The algorithm below works by picking a random number and testing it. + * We can see that these limits mean we usually succeed pretty quickly: + * + * >>> def calculation(tries, size): + * ... return (size / 2**32)**(tries - 1) * (1 - (size / 2**32)) + * ... + * >>> calculation(1, 2**20 * 3) + * 0.999267578125 + * >>> calculation(2, 2**20 * 3) + * 0.0007318854331970215 + * >>> calculation(3, 2**20 * 3) + * 5.360489012673497e-07 + * >>> calculation(4, 2**20 * 3) + * 3.9261394135792216e-10 + * + * At the moment, we don't do any masking, so this algorithm isn't exactly constant time in + * either the random guessing or in the hash list lookup. We could require a minimum of 3 + * tries, which would successfully mask the guessing. TODO: this would not, however, help + * with the growing hash lengths. + */ + __le32 index_hashtable_insert(struct index_hashtable *table, struct index_hashtable_entry *entry) { struct index_hashtable_entry *existing_entry; diff --git a/src/hashtables.h b/src/hashtables.h index 08a2a5d..2a178a0 100644 --- a/src/hashtables.h +++ b/src/hashtables.h @@ -12,7 +12,8 @@ struct wireguard_peer; struct pubkey_hashtable { - DECLARE_HASHTABLE(hashtable, 8); + /* TODO: move to rhashtable */ + DECLARE_HASHTABLE(hashtable, 11); siphash_key_t key; struct mutex lock; }; @@ -23,7 +24,8 @@ void pubkey_hashtable_remove(struct pubkey_hashtable *table, struct wireguard_pe struct wireguard_peer *pubkey_hashtable_lookup(struct pubkey_hashtable *table, const u8 pubkey[NOISE_PUBLIC_KEY_LEN]); struct index_hashtable { - DECLARE_HASHTABLE(hashtable, 10); + /* TODO: move to rhashtable */ + DECLARE_HASHTABLE(hashtable, 13); spinlock_t lock; }; diff --git a/src/messages.h b/src/messages.h index 6119cd5..2c0658d 100644 --- a/src/messages.h +++ b/src/messages.h @@ -46,7 +46,7 @@ enum limits { REKEY_AFTER_TIME = 120 * HZ, REJECT_AFTER_TIME = 180 * HZ, INITIATIONS_PER_SECOND = HZ / 50, - MAX_PEERS_PER_DEVICE = U16_MAX, + MAX_PEERS_PER_DEVICE = 1 << 20, KEEPALIVE_TIMEOUT = 10 * HZ, MAX_TIMER_HANDSHAKES = (90 * HZ) / REKEY_TIMEOUT, MAX_QUEUED_INCOMING_HANDSHAKES = 4096, diff --git a/src/uapi.h b/src/uapi.h index 1cc2bba..e699025 100644 --- a/src/uapi.h +++ b/src/uapi.h @@ -128,7 +128,7 @@ enum { }; enum { - WG_API_VERSION_MAGIC = 0xbeef0002 + WG_API_VERSION_MAGIC = 0xbeef0003 }; struct wgdevice { @@ -142,7 +142,7 @@ struct wgdevice { __u16 port; /* Get/Set */ union { - __u16 num_peers; /* Get/Set */ + __u32 num_peers; /* Get/Set */ __u32 peers_size; /* Get */ }; }; -- cgit v1.2.3-59-g8ed1b