aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorJonathan Neuschäfer <j.neuschaefer@gmx.net>2018-07-21 03:34:46 +0200
committerJonathan Neuschäfer <j.neuschaefer@gmx.net>2018-07-21 03:34:46 +0200
commit9d0d777b2bbe4358e1b64b4d09683371ed0ccca9 (patch)
treec1f4af8acf1a135705abbd2b6bbc22618d17bb3c
parentreceive: check against proper return value type (diff)
downloadWireGuard-jn/rhashtable.tar.xz
WireGuard-jn/rhashtable.zip
hashtables: switch to rhashtablejn/rhashtable
NOTE: Due to a limitation in the rhashtable API, the siphash key (or "seed") is reduced to 32 bits of random, rather than 128 bits that were used before. Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
-rw-r--r--src/device.c50
-rw-r--r--src/hashtables.c123
-rw-r--r--src/hashtables.h16
-rw-r--r--src/peer.h2
4 files changed, 106 insertions, 85 deletions
diff --git a/src/device.c b/src/device.c
index 54a94fb..268341a 100644
--- a/src/device.c
+++ b/src/device.c
@@ -235,6 +235,8 @@ static void destruct(struct net_device *dev)
skb_queue_purge(&wg->incoming_handshakes);
free_percpu(dev->tstats);
free_percpu(wg->incoming_handshakes_worker);
+ pubkey_hashtable_cleanup(&wg->peer_hashtable);
+ index_hashtable_cleanup(&wg->index_hashtable);
if (wg->have_creating_net_ref)
put_net(wg->creating_net);
mutex_unlock(&wg->device_update_lock);
@@ -289,46 +291,52 @@ static int newlink(struct net *src_net, struct net_device *dev, struct nlattr *t
mutex_init(&wg->socket_update_lock);
mutex_init(&wg->device_update_lock);
skb_queue_head_init(&wg->incoming_handshakes);
- pubkey_hashtable_init(&wg->peer_hashtable);
- index_hashtable_init(&wg->index_hashtable);
allowedips_init(&wg->peer_allowedips);
cookie_checker_init(&wg->cookie_checker, wg);
INIT_LIST_HEAD(&wg->peer_list);
wg->device_update_gen = 1;
+ ret = pubkey_hashtable_init(&wg->peer_hashtable);
+ if (ret)
+ goto error_1;
+
+ ret = index_hashtable_init(&wg->index_hashtable);
+ if (ret)
+ goto error_2;
+
dev->tstats = netdev_alloc_pcpu_stats(struct pcpu_sw_netstats);
if (!dev->tstats)
- goto error_1;
+ goto error_3;
wg->incoming_handshakes_worker = packet_alloc_percpu_multicore_worker(packet_handshake_receive_worker, wg);
if (!wg->incoming_handshakes_worker)
- goto error_2;
+ goto error_4;
wg->handshake_receive_wq = alloc_workqueue("wg-kex-%s", WQ_CPU_INTENSIVE | WQ_FREEZABLE, 0, dev->name);
if (!wg->handshake_receive_wq)
- goto error_3;
+ goto error_5;
wg->handshake_send_wq = alloc_workqueue("wg-kex-%s", WQ_UNBOUND | WQ_FREEZABLE, 0, dev->name);
if (!wg->handshake_send_wq)
- goto error_4;
+ goto error_6;
wg->packet_crypt_wq = alloc_workqueue("wg-crypt-%s", WQ_CPU_INTENSIVE | WQ_MEM_RECLAIM, 0, dev->name);
if (!wg->packet_crypt_wq)
- goto error_5;
+ goto error_7;
if (packet_queue_init(&wg->encrypt_queue, packet_encrypt_worker, true, MAX_QUEUED_PACKETS) < 0)
- goto error_6;
+ goto error_8;
if (packet_queue_init(&wg->decrypt_queue, packet_decrypt_worker, true, MAX_QUEUED_PACKETS) < 0)
- goto error_7;
+ goto error_9;
ret = ratelimiter_init();
if (ret < 0)
- goto error_8;
+ goto error_10;
ret = register_netdevice(dev);
if (ret < 0)
- goto error_9;
+ goto error_11;
list_add(&wg->device_list, &device_list);
@@ -340,22 +348,26 @@ static int newlink(struct net *src_net, struct net_device *dev, struct nlattr *t
pr_debug("%s: Interface created\n", dev->name);
return ret;
-error_9:
+error_11:
ratelimiter_uninit();
-error_8:
+error_10:
packet_queue_free(&wg->decrypt_queue, true);
-error_7:
+error_9:
packet_queue_free(&wg->encrypt_queue, true);
-error_6:
+error_8:
destroy_workqueue(wg->packet_crypt_wq);
-error_5:
+error_7:
destroy_workqueue(wg->handshake_send_wq);
-error_4:
+error_6:
destroy_workqueue(wg->handshake_receive_wq);
-error_3:
+error_5:
free_percpu(wg->incoming_handshakes_worker);
-error_2:
+error_4:
free_percpu(dev->tstats);
+error_3:
+ index_hashtable_cleanup(&wg->index_hashtable);
+error_2:
+ pubkey_hashtable_cleanup(&wg->peer_hashtable);
error_1:
return ret;
}
diff --git a/src/hashtables.c b/src/hashtables.c
index 0e5235d..a549fb6 100644
--- a/src/hashtables.c
+++ b/src/hashtables.c
@@ -7,66 +7,84 @@
#include "peer.h"
#include "noise.h"
-static inline struct hlist_head *pubkey_bucket(struct pubkey_hashtable *table, const u8 pubkey[NOISE_PUBLIC_KEY_LEN])
+static u32 pubkey_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.
- */
- return &table->hashtable[siphash(pubkey, NOISE_PUBLIC_KEY_LEN, &table->key) & (HASH_SIZE(table->hashtable) - 1)];
+ /* The rhashtable API only allows 32 bits of seed, while siphash expects 128 bits. */
+ siphash_key_t key = { .key = { seed } };
+
+ return siphash(data, len, &key);
+}
+
+static const struct rhashtable_params pubkey_params = {
+ .key_offset = offsetof(struct wireguard_peer, handshake.remote_static),
+ .key_len = FIELD_SIZEOF(struct wireguard_peer, handshake.remote_static),
+ .head_offset = offsetof(struct wireguard_peer, pubkey_hash),
+ .hashfn = pubkey_hashfn,
+ .automatic_shrinking = true,
+};
+
+int pubkey_hashtable_init(struct pubkey_hashtable *table)
+{
+ return rhashtable_init(&table->hashtable, &pubkey_params);
}
-void pubkey_hashtable_init(struct pubkey_hashtable *table)
+void pubkey_hashtable_cleanup(struct pubkey_hashtable *table)
{
- get_random_bytes(&table->key, sizeof(table->key));
- hash_init(table->hashtable);
- mutex_init(&table->lock);
+ rhashtable_destroy(&table->hashtable);
}
void pubkey_hashtable_add(struct pubkey_hashtable *table, struct wireguard_peer *peer)
{
- mutex_lock(&table->lock);
- hlist_add_head_rcu(&peer->pubkey_hash, pubkey_bucket(table, peer->handshake.remote_static));
- mutex_unlock(&table->lock);
+ /* TODO: does this really work with hash collisions? */
+ rhashtable_insert_fast(&table->hashtable, &peer->pubkey_hash, pubkey_params);
}
void pubkey_hashtable_remove(struct pubkey_hashtable *table, struct wireguard_peer *peer)
{
- mutex_lock(&table->lock);
- hlist_del_init_rcu(&peer->pubkey_hash);
- mutex_unlock(&table->lock);
+ rhashtable_remove_fast(&table->hashtable, &peer->pubkey_hash, pubkey_params);
}
/* Returns a strong reference to a peer */
struct wireguard_peer *pubkey_hashtable_lookup(struct pubkey_hashtable *table, const u8 pubkey[NOISE_PUBLIC_KEY_LEN])
{
- struct wireguard_peer *iter_peer, *peer = NULL;
+ struct wireguard_peer *peer;
rcu_read_lock_bh();
- hlist_for_each_entry_rcu_bh(iter_peer, pubkey_bucket(table, pubkey), pubkey_hash) {
- if (!memcmp(pubkey, iter_peer->handshake.remote_static, NOISE_PUBLIC_KEY_LEN)) {
- peer = iter_peer;
- break;
- }
- }
- peer = peer_get(peer);
+ peer = peer_get(rhashtable_lookup_fast(&table->hashtable, pubkey, pubkey_params));
rcu_read_unlock_bh();
+
return peer;
}
-static inline struct hlist_head *index_bucket(struct index_hashtable *table, const __le32 index)
+static u32 index_hashfn(const void *data, u32 len, u32 seed)
{
- /* Since the indices are random and thus all bits are uniformly distributed,
- * we can find its bucket simply by masking.
- */
- return &table->hashtable[(__force u32)index & (HASH_SIZE(table->hashtable) - 1)];
+ BUG_ON(len != 4);
+ return *(u32 *)data;
}
-void index_hashtable_init(struct index_hashtable *table)
+static const struct rhashtable_params index_params = {
+ .key_offset = offsetof(struct index_hashtable_entry, index),
+ .key_len = FIELD_SIZEOF(struct index_hashtable_entry, index),
+ .head_offset = offsetof(struct index_hashtable_entry, index_hash),
+ .hashfn = index_hashfn,
+ .automatic_shrinking = true,
+};
+
+int index_hashtable_init(struct index_hashtable *table)
{
- hash_init(table->hashtable);
+ int ret;
+
+ ret = rhashtable_init(&table->hashtable, &index_params);
spin_lock_init(&table->lock);
+ return ret;
}
+void index_hashtable_cleanup(struct index_hashtable *table)
+{
+ rhashtable_destroy(&table->hashtable);
+}
+
+
/* 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:
@@ -93,32 +111,28 @@ __le32 index_hashtable_insert(struct index_hashtable *table, struct index_hashta
{
struct index_hashtable_entry *existing_entry;
- spin_lock_bh(&table->lock);
- hlist_del_init_rcu(&entry->index_hash);
- spin_unlock_bh(&table->lock);
-
rcu_read_lock_bh();
search_unused_slot:
/* First we try to find an unused slot, randomly, while unlocked. */
entry->index = (__force __le32)get_random_u32();
- hlist_for_each_entry_rcu_bh(existing_entry, index_bucket(table, entry->index), index_hash) {
- if (existing_entry->index == entry->index)
- goto search_unused_slot; /* If it's already in use, we continue searching. */
+ existing_entry = rhashtable_lookup_fast(&table->hashtable, &entry->index, index_params);
+ if (existing_entry && existing_entry->index == entry->index) {
+ goto search_unused_slot; /* If it's already in use, we continue searching. */
}
/* Once we've found an unused slot, we lock it, and then double-check
* that nobody else stole it from us.
*/
spin_lock_bh(&table->lock);
- hlist_for_each_entry_rcu_bh(existing_entry, index_bucket(table, entry->index), index_hash) {
- if (existing_entry->index == entry->index) {
- spin_unlock_bh(&table->lock);
- goto search_unused_slot; /* If it was stolen, we start over. */
- }
+ existing_entry = rhashtable_lookup_fast(&table->hashtable, &entry->index, index_params);
+ if (existing_entry && existing_entry->index == entry->index) {
+ spin_unlock_bh(&table->lock);
+ goto search_unused_slot; /* If it was stolen, we start over. */
}
+
/* Otherwise, we know we have it exclusively (since we're locked), so we insert. */
- hlist_add_head_rcu(&entry->index_hash, index_bucket(table, entry->index));
+ rhashtable_insert_fast(&table->hashtable, &entry->index_hash, index_params);
spin_unlock_bh(&table->lock);
rcu_read_unlock_bh();
@@ -128,12 +142,15 @@ search_unused_slot:
bool index_hashtable_replace(struct index_hashtable *table, struct index_hashtable_entry *old, struct index_hashtable_entry *new)
{
- if (unlikely(hlist_unhashed(&old->index_hash)))
+ int ret;
+
+ if (unlikely(rhashtable_lookup_fast(&table->hashtable, old, index_params)))
return false;
+
spin_lock_bh(&table->lock);
new->index = old->index;
- hlist_replace_rcu(&old->index_hash, &new->index_hash);
- INIT_HLIST_NODE(&old->index_hash);
+ ret = rhashtable_replace_fast(&table->hashtable, &old->index_hash, &new->index_hash, index_params);
+ WARN_ON_ONCE(ret != 0);
spin_unlock_bh(&table->lock);
return true;
}
@@ -141,24 +158,18 @@ bool index_hashtable_replace(struct index_hashtable *table, struct index_hashtab
void index_hashtable_remove(struct index_hashtable *table, struct index_hashtable_entry *entry)
{
spin_lock_bh(&table->lock);
- hlist_del_init_rcu(&entry->index_hash);
+ rhashtable_remove_fast(&table->hashtable, &entry->index_hash, index_params);
spin_unlock_bh(&table->lock);
}
/* Returns a strong reference to a entry->peer */
struct index_hashtable_entry *index_hashtable_lookup(struct index_hashtable *table, const enum index_hashtable_type type_mask, const __le32 index)
{
- struct index_hashtable_entry *iter_entry, *entry = NULL;
+ struct index_hashtable_entry *entry = NULL;
rcu_read_lock_bh();
- hlist_for_each_entry_rcu_bh(iter_entry, index_bucket(table, index), index_hash) {
- if (iter_entry->index == index) {
- if (likely(iter_entry->type & type_mask))
- entry = iter_entry;
- break;
- }
- }
- if (likely(entry)) {
+ entry = rhashtable_lookup_fast(&table->hashtable, &index, index_params);
+ if (likely(entry && entry->type & type_mask)) {
entry->peer = peer_get(entry->peer);
if (unlikely(!entry->peer))
entry = NULL;
diff --git a/src/hashtables.h b/src/hashtables.h
index a2ef6f0..432e32e 100644
--- a/src/hashtables.h
+++ b/src/hashtables.h
@@ -15,20 +15,17 @@
struct wireguard_peer;
struct pubkey_hashtable {
- /* TODO: move to rhashtable */
- DECLARE_HASHTABLE(hashtable, 11);
- siphash_key_t key;
- struct mutex lock;
+ struct rhashtable hashtable;
};
-void pubkey_hashtable_init(struct pubkey_hashtable *table);
+int pubkey_hashtable_init(struct pubkey_hashtable *table);
+void pubkey_hashtable_cleanup(struct pubkey_hashtable *table);
void pubkey_hashtable_add(struct pubkey_hashtable *table, struct wireguard_peer *peer);
void pubkey_hashtable_remove(struct pubkey_hashtable *table, struct wireguard_peer *peer);
struct wireguard_peer *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 hashtable;
spinlock_t lock;
};
@@ -39,11 +36,12 @@ enum index_hashtable_type {
struct index_hashtable_entry {
struct wireguard_peer *peer;
- struct hlist_node index_hash;
+ struct rhash_head index_hash;
enum index_hashtable_type type;
__le32 index;
};
-void index_hashtable_init(struct index_hashtable *table);
+int index_hashtable_init(struct index_hashtable *table);
+void index_hashtable_cleanup(struct index_hashtable *table);
__le32 index_hashtable_insert(struct index_hashtable *table, struct index_hashtable_entry *entry);
bool index_hashtable_replace(struct index_hashtable *table, struct index_hashtable_entry *old, struct index_hashtable_entry *new);
void index_hashtable_remove(struct index_hashtable *table, struct index_hashtable_entry *entry);
diff --git a/src/peer.h b/src/peer.h
index 088a6ee..6136287 100644
--- a/src/peer.h
+++ b/src/peer.h
@@ -46,7 +46,7 @@ struct wireguard_peer {
u64 last_sent_handshake;
struct work_struct transmit_handshake_work, clear_peer_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, timer_new_handshake, timer_zero_key_material, timer_persistent_keepalive;
unsigned int timer_handshake_attempts;