aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorJason A. Donenfeld <Jason@zx2c4.com>2017-08-07 20:45:42 +0200
committerJason A. Donenfeld <Jason@zx2c4.com>2017-08-08 05:57:25 +0200
commitb2ec36268f0f33dc9f5af77c373014681fafa7f6 (patch)
tree9d2585981d7ffdb1d4cf5ad692a6b9c46680cdd3
parentcompat: support grsecurity with our compat padata implementation (diff)
downloadwireguard-monolithic-historical-b2ec36268f0f33dc9f5af77c373014681fafa7f6.tar.xz
wireguard-monolithic-historical-b2ec36268f0f33dc9f5af77c373014681fafa7f6.zip
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.
-rw-r--r--src/hashtables.c22
-rw-r--r--src/hashtables.h6
-rw-r--r--src/messages.h2
-rw-r--r--src/uapi.h4
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 */
};
};