Skip to contentSkip to conversation

wireguard: use rhashtables instead of hashtables

PATCH In review Dmitrii Ermakov 2 participants 2 messages Jan 5, 2025 – Mar 19, 2025

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 wireguard: use rhashtables instead of hashtables

Replace hashtable of static length (8192) with dynamic rhashtable

---
 drivers/net/wireguard/device.c     |   4 +
 drivers/net/wireguard/noise.h      |   4 +-
 drivers/net/wireguard/peer.h       |   4 +-
 drivers/net/wireguard/peerlookup.c | 195 ++++++++++++++++++-----------
 drivers/net/wireguard/peerlookup.h |  10 +-
 5 files changed, 138 insertions(+), 79 deletions(-)
drivers/net/wireguard/device.c +4 -0
index 6cf173a008e7..2068039667dd 100644
@@ -3,6 +3,8 @@
  * Copyright (C) 2015-2019 Jason A. Donenfeld <[email protected]>. All Rights Reserved.
  */
 
+#include "linux/rhashtable-types.h"
+#include "linux/rhashtable.h"
 #include "queueing.h"
 #include "socket.h"
 #include "timers.h"
@@ -261,6 +263,8 @@ static void wg_destruct(struct net_device *dev)
 	rcu_barrier(); /* Wait for all the peers to be actually freed. */
 	wg_ratelimiter_uninit();
 	memzero_explicit(&wg->static_identity, sizeof(wg->static_identity));
+	rhashtable_destroy(&wg->index_hashtable->rhashtable);
+	rhashtable_destroy(&wg->peer_hashtable->rhashtable);
 	kvfree(wg->index_hashtable);
 	kvfree(wg->peer_hashtable);
 	mutex_unlock(&wg->device_update_lock);
drivers/net/wireguard/noise.h +3 -1
index c527253dba80..216abc956c32 100644
@@ -5,6 +5,7 @@
 #ifndef _WG_NOISE_H
 #define _WG_NOISE_H
 
+#include "linux/siphash.h"
 #include "messages.h"
 #include "peerlookup.h"
 
@@ -74,7 +75,6 @@ struct noise_handshake {
 	u8 remote_static[NOISE_PUBLIC_KEY_LEN];
 	u8 remote_ephemeral[NOISE_PUBLIC_KEY_LEN];
 	u8 precomputed_static_static[NOISE_PUBLIC_KEY_LEN];
-
 	u8 preshared_key[NOISE_SYMMETRIC_KEY_LEN];
 
 	u8 hash[NOISE_HASH_LEN];
@@ -83,6 +83,8 @@ struct noise_handshake {
 	u8 latest_timestamp[NOISE_TIMESTAMP_LEN];
 	__le32 remote_index;
 
+	siphash_key_t hash_seed;
+
 	/* Protects all members except the immutable (after noise_handshake_
 	 * init): remote_static, precomputed_static_static, static_identity.
 	 */
drivers/net/wireguard/peer.h +3 -1
index 76e4d3128ad4..06250679822b 100644
@@ -7,6 +7,7 @@
 #define _WG_PEER_H
 
 #include "device.h"
+#include "linux/siphash.h"
 #include "noise.h"
 #include "cookie.h"
 
@@ -15,6 +16,7 @@
 #include <linux/spinlock.h>
 #include <linux/kref.h>
 #include <net/dst_cache.h>
+#include <linux/rhashtable.h>
 
 struct wg_device;
 
@@ -48,7 +50,7 @@ struct wg_peer {
 	atomic64_t last_sent_handshake;
 	struct work_struct transmit_handshake_work, clear_peer_work, transmit_packet_work;
 	struct cookie latest_cookie;
-	struct hlist_node pubkey_hash;
+	struct rhash_head pubkey_hash;
 	u64 rx_bytes, tx_bytes;
 	struct timer_list timer_retransmit_handshake, timer_send_keepalive;
 	struct timer_list timer_new_handshake, timer_zero_key_material;
drivers/net/wireguard/peerlookup.c +124 -71

303 lines not on this page · raw message

drivers/net/wireguard/peerlookup.h +4 -6
index ced811797680..edc6acc21d79 100644
@@ -8,15 +8,14 @@
 
 #include "messages.h"
 
-#include <linux/hashtable.h>
 #include <linux/mutex.h>
 #include <linux/siphash.h>
+#include <linux/rhashtable.h>
 
 struct wg_peer;
 
 struct pubkey_hashtable {
-	/* TODO: move to rhashtable */
-	DECLARE_HASHTABLE(hashtable, 11);
+	struct rhashtable rhashtable;
 	siphash_key_t key;
 	struct mutex lock;
 };
@@ -31,8 +30,7 @@ wg_pubkey_hashtable_lookup(struct pubkey_hashtable *table,
 			   const u8 pubkey[NOISE_PUBLIC_KEY_LEN]);
 
 struct index_hashtable {
-	/* TODO: move to rhashtable */
-	DECLARE_HASHTABLE(hashtable, 13);
+	struct rhashtable rhashtable;
 	spinlock_t lock;
 };
 
@@ -43,7 +41,7 @@ enum index_hashtable_type {
 
 struct index_hashtable_entry {
 	struct wg_peer *peer;
-	struct hlist_node index_hash;
+	struct rhash_head index_hash;
 	enum index_hashtable_type type;
 	__le32 index;
 };
Signature · 1 line
2.45.2
#1 lore raw

drivers/net/wireguard/noise.h struct noise_handshake { · line 86

Quoted 13 lines · Dmitrii Ermakov
drivers/net/wireguard/noise.h +1 -1
@@ -74,7 +75,6 @@ struct noise_handshake {
 	u8 remote_static[NOISE_PUBLIC_KEY_LEN];
 	u8 remote_ephemeral[NOISE_PUBLIC_KEY_LEN];
 	u8 precomputed_static_static[NOISE_PUBLIC_KEY_LEN];
-
 	u8 preshared_key[NOISE_SYMMETRIC_KEY_LEN];
 
 	u8 hash[NOISE_HASH_LEN];
@@ -83,6 +83,8 @@ struct noise_handshake {
 	u8 latest_timestamp[NOISE_TIMESTAMP_LEN];
 	__le32 remote_index;
 
+	siphash_key_t hash_seed;

Why?

drivers/net/wireguard/peerlookup.c line 11

Quoted 5 lines
drivers/net/wireguard/peerlookup.c +5 -0
+#include "linux/printk.h"
+#include "linux/rcupdate.h"
+#include "linux/rhashtable-types.h"
+#include "linux/rhashtable.h"
+#include "linux/siphash.h"

Seems wrong.

drivers/net/wireguard/peerlookup.c line 15

Quoted 4 lines
drivers/net/wireguard/peerlookup.c +2 -0
+#include "messages.h"
 #include "peer.h"
 #include "noise.h"
+#include "linux/memory.h"

Ditto.

drivers/net/wireguard/peerlookup.c line 21

Quoted 13 lines
drivers/net/wireguard/peerlookup.c +4 -7
-static struct hlist_head *pubkey_bucket(struct pubkey_hashtable *table,
-					const u8 pubkey[NOISE_PUBLIC_KEY_LEN])
+static inline u32 index_hashfn(const void *data, u32 len, u32 seed)
 {
-	/* siphash gives us a secure 64bit number based on a random key. Since
-	 * the bits are uniformly distributed, we can then mask off to get the
-	 * bits we need.
-	 */
-	const u64 hash = siphash(pubkey, NOISE_PUBLIC_KEY_LEN, &table->key);
+	const u32 *index = data;
+	return *index;
+}

But shouldn't this actually use siphash? What's happening here?

Quoted 5 lines
drivers/net/wireguard/peerlookup.c +5 -0
+struct peer_hash_pubkey {
+	siphash_key_t key;
+	u8 pubkey[NOISE_PUBLIC_KEY_LEN];
+};
+

drivers/net/wireguard/peerlookup.c line 45

Quoted 10 lines
drivers/net/wireguard/peerlookup.c +10 -0
+static inline u32 wg_peer_obj_hashfn(const void *data, u32 len, u32 seed)
+{
+	const struct wg_peer *peer = data;
+	struct peer_hash_pubkey key;
+	u64 hash;
+
+	memcpy(&key.key, &peer->handshake.hash_seed, sizeof(key.key));
+	memcpy(&key.pubkey, &peer->handshake.remote_static, NOISE_PUBLIC_KEY_LEN);
+
+	hash = siphash(&key.pubkey, NOISE_PUBLIC_KEY_LEN, &key.key);

Why this weird construction with this other struct?

I'll stop reading here. There's a lot of strangeness with this patch. Maybe it's workable with enough care, but I think to review this into shape, in its current state, would be about the same as just rewriting it.