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.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>

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 */
 	};
 };