From 6c58b00a5a30d783048dc5e1f7aa8961d739e740 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Mon, 25 Mar 2019 12:39:47 +0100 Subject: peerlookup: rename from hashtables Signed-off-by: Jason A. Donenfeld --- src/Kbuild | 2 +- src/device.h | 2 +- src/hashtables.c | 221 ------------------------------------------------------- src/hashtables.h | 64 ---------------- src/noise.c | 2 +- src/noise.h | 2 +- src/peer.c | 2 +- src/peerlookup.c | 221 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/peerlookup.h | 64 ++++++++++++++++ 9 files changed, 290 insertions(+), 290 deletions(-) delete mode 100644 src/hashtables.c delete mode 100644 src/hashtables.h create mode 100644 src/peerlookup.c create mode 100644 src/peerlookup.h (limited to 'src') diff --git a/src/Kbuild b/src/Kbuild index abf6b2e..f84b4de 100644 --- a/src/Kbuild +++ b/src/Kbuild @@ -6,7 +6,7 @@ ccflags-y := -O3 -fvisibility=hidden ccflags-$(CONFIG_WIREGUARD_DEBUG) += -DDEBUG -g ccflags-y += -D'pr_fmt(fmt)=KBUILD_MODNAME ": " fmt' -wireguard-y := main.o noise.o device.o peer.o timers.o queueing.o send.o receive.o socket.o hashtables.o allowedips.o ratelimiter.o cookie.o netlink.o +wireguard-y := main.o noise.o device.o peer.o timers.o queueing.o send.o receive.o socket.o peerlookup.o allowedips.o ratelimiter.o cookie.o netlink.o include $(src)/crypto/Kbuild.include include $(src)/compat/Kbuild.include diff --git a/src/device.h b/src/device.h index 7e7e216..b15a8be 100644 --- a/src/device.h +++ b/src/device.h @@ -8,7 +8,7 @@ #include "noise.h" #include "allowedips.h" -#include "hashtables.h" +#include "peerlookup.h" #include "cookie.h" #include diff --git a/src/hashtables.c b/src/hashtables.c deleted file mode 100644 index 8aedc17..0000000 --- a/src/hashtables.c +++ /dev/null @@ -1,221 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 -/* - * Copyright (C) 2015-2019 Jason A. Donenfeld . All Rights Reserved. - */ - -#include "hashtables.h" -#include "peer.h" -#include "noise.h" - -static struct hlist_head *pubkey_bucket(struct pubkey_hashtable *table, - const u8 pubkey[NOISE_PUBLIC_KEY_LEN]) -{ - /* 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); - - return &table->hashtable[hash & (HASH_SIZE(table->hashtable) - 1)]; -} - -struct pubkey_hashtable *wg_pubkey_hashtable_alloc(void) -{ - struct pubkey_hashtable *table = kvmalloc(sizeof(*table), GFP_KERNEL); - - if (!table) - return NULL; - - get_random_bytes(&table->key, sizeof(table->key)); - hash_init(table->hashtable); - mutex_init(&table->lock); - return table; -} - -void wg_pubkey_hashtable_add(struct pubkey_hashtable *table, - struct wg_peer *peer) -{ - mutex_lock(&table->lock); - hlist_add_head_rcu(&peer->pubkey_hash, - pubkey_bucket(table, peer->handshake.remote_static)); - mutex_unlock(&table->lock); -} - -void wg_pubkey_hashtable_remove(struct pubkey_hashtable *table, - struct wg_peer *peer) -{ - mutex_lock(&table->lock); - hlist_del_init_rcu(&peer->pubkey_hash); - mutex_unlock(&table->lock); -} - -/* Returns a strong reference to a peer */ -struct wg_peer * -wg_pubkey_hashtable_lookup(struct pubkey_hashtable *table, - const u8 pubkey[NOISE_PUBLIC_KEY_LEN]) -{ - struct wg_peer *iter_peer, *peer = NULL; - - 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 = wg_peer_get_maybe_zero(peer); - rcu_read_unlock_bh(); - return peer; -} - -static struct hlist_head *index_bucket(struct index_hashtable *table, - const __le32 index) -{ - /* 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)]; -} - -struct index_hashtable *wg_index_hashtable_alloc(void) -{ - struct index_hashtable *table = kvmalloc(sizeof(*table), GFP_KERNEL); - - if (!table) - return NULL; - - hash_init(table->hashtable); - spin_lock_init(&table->lock); - return table; -} - -/* 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. this would not, however, help with the growing hash lengths, which - * is another thing to consider moving forward. - */ - -__le32 wg_index_hashtable_insert(struct index_hashtable *table, - struct index_hashtable_entry *entry) -{ - 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) - /* If it's already in use, we continue searching. */ - goto search_unused_slot; - } - - /* 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); - /* If it was stolen, we start over. */ - goto search_unused_slot; - } - } - /* 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)); - spin_unlock_bh(&table->lock); - - rcu_read_unlock_bh(); - - return entry->index; -} - -bool wg_index_hashtable_replace(struct index_hashtable *table, - struct index_hashtable_entry *old, - struct index_hashtable_entry *new) -{ - if (unlikely(hlist_unhashed(&old->index_hash))) - return false; - spin_lock_bh(&table->lock); - new->index = old->index; - hlist_replace_rcu(&old->index_hash, &new->index_hash); - - /* Calling init here NULLs out index_hash, and in fact after this - * function returns, it's theoretically possible for this to get - * reinserted elsewhere. That means the RCU lookup below might either - * terminate early or jump between buckets, in which case the packet - * simply gets dropped, which isn't terrible. - */ - INIT_HLIST_NODE(&old->index_hash); - spin_unlock_bh(&table->lock); - return true; -} - -void wg_index_hashtable_remove(struct index_hashtable *table, - struct index_hashtable_entry *entry) -{ - spin_lock_bh(&table->lock); - hlist_del_init_rcu(&entry->index_hash); - spin_unlock_bh(&table->lock); -} - -/* Returns a strong reference to a entry->peer */ -struct index_hashtable_entry * -wg_index_hashtable_lookup(struct index_hashtable *table, - const enum index_hashtable_type type_mask, - const __le32 index, struct wg_peer **peer) -{ - struct index_hashtable_entry *iter_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->peer = wg_peer_get_maybe_zero(entry->peer); - if (likely(entry->peer)) - *peer = entry->peer; - else - entry = NULL; - } - rcu_read_unlock_bh(); - return entry; -} diff --git a/src/hashtables.h b/src/hashtables.h deleted file mode 100644 index de77537..0000000 --- a/src/hashtables.h +++ /dev/null @@ -1,64 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ -/* - * Copyright (C) 2015-2019 Jason A. Donenfeld . All Rights Reserved. - */ - -#ifndef _WG_HASHTABLES_H -#define _WG_HASHTABLES_H - -#include "messages.h" - -#include -#include -#include - -struct wg_peer; - -struct pubkey_hashtable { - /* TODO: move to rhashtable */ - DECLARE_HASHTABLE(hashtable, 11); - siphash_key_t key; - struct mutex lock; -}; - -struct pubkey_hashtable *wg_pubkey_hashtable_alloc(void); -void wg_pubkey_hashtable_add(struct pubkey_hashtable *table, - struct wg_peer *peer); -void wg_pubkey_hashtable_remove(struct pubkey_hashtable *table, - struct wg_peer *peer); -struct wg_peer * -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); - spinlock_t lock; -}; - -enum index_hashtable_type { - INDEX_HASHTABLE_HANDSHAKE = 1U << 0, - INDEX_HASHTABLE_KEYPAIR = 1U << 1 -}; - -struct index_hashtable_entry { - struct wg_peer *peer; - struct hlist_node index_hash; - enum index_hashtable_type type; - __le32 index; -}; - -struct index_hashtable *wg_index_hashtable_alloc(void); -__le32 wg_index_hashtable_insert(struct index_hashtable *table, - struct index_hashtable_entry *entry); -bool wg_index_hashtable_replace(struct index_hashtable *table, - struct index_hashtable_entry *old, - struct index_hashtable_entry *new); -void wg_index_hashtable_remove(struct index_hashtable *table, - struct index_hashtable_entry *entry); -struct index_hashtable_entry * -wg_index_hashtable_lookup(struct index_hashtable *table, - const enum index_hashtable_type type_mask, - const __le32 index, struct wg_peer **peer); - -#endif /* _WG_HASHTABLES_H */ diff --git a/src/noise.c b/src/noise.c index 2e05e27..bf0b8c5 100644 --- a/src/noise.c +++ b/src/noise.c @@ -8,7 +8,7 @@ #include "peer.h" #include "messages.h" #include "queueing.h" -#include "hashtables.h" +#include "peerlookup.h" #include #include diff --git a/src/noise.h b/src/noise.h index 8e5cc0a..9c2cc62 100644 --- a/src/noise.h +++ b/src/noise.h @@ -6,7 +6,7 @@ #define _WG_NOISE_H #include "messages.h" -#include "hashtables.h" +#include "peerlookup.h" #include #include diff --git a/src/peer.c b/src/peer.c index 0c7e942..508f1d5 100644 --- a/src/peer.c +++ b/src/peer.c @@ -7,7 +7,7 @@ #include "device.h" #include "queueing.h" #include "timers.h" -#include "hashtables.h" +#include "peerlookup.h" #include "noise.h" #include diff --git a/src/peerlookup.c b/src/peerlookup.c new file mode 100644 index 0000000..e4deb33 --- /dev/null +++ b/src/peerlookup.c @@ -0,0 +1,221 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2015-2019 Jason A. Donenfeld . All Rights Reserved. + */ + +#include "peerlookup.h" +#include "peer.h" +#include "noise.h" + +static struct hlist_head *pubkey_bucket(struct pubkey_hashtable *table, + const u8 pubkey[NOISE_PUBLIC_KEY_LEN]) +{ + /* 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); + + return &table->hashtable[hash & (HASH_SIZE(table->hashtable) - 1)]; +} + +struct pubkey_hashtable *wg_pubkey_hashtable_alloc(void) +{ + struct pubkey_hashtable *table = kvmalloc(sizeof(*table), GFP_KERNEL); + + if (!table) + return NULL; + + get_random_bytes(&table->key, sizeof(table->key)); + hash_init(table->hashtable); + mutex_init(&table->lock); + return table; +} + +void wg_pubkey_hashtable_add(struct pubkey_hashtable *table, + struct wg_peer *peer) +{ + mutex_lock(&table->lock); + hlist_add_head_rcu(&peer->pubkey_hash, + pubkey_bucket(table, peer->handshake.remote_static)); + mutex_unlock(&table->lock); +} + +void wg_pubkey_hashtable_remove(struct pubkey_hashtable *table, + struct wg_peer *peer) +{ + mutex_lock(&table->lock); + hlist_del_init_rcu(&peer->pubkey_hash); + mutex_unlock(&table->lock); +} + +/* Returns a strong reference to a peer */ +struct wg_peer * +wg_pubkey_hashtable_lookup(struct pubkey_hashtable *table, + const u8 pubkey[NOISE_PUBLIC_KEY_LEN]) +{ + struct wg_peer *iter_peer, *peer = NULL; + + 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 = wg_peer_get_maybe_zero(peer); + rcu_read_unlock_bh(); + return peer; +} + +static struct hlist_head *index_bucket(struct index_hashtable *table, + const __le32 index) +{ + /* 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)]; +} + +struct index_hashtable *wg_index_hashtable_alloc(void) +{ + struct index_hashtable *table = kvmalloc(sizeof(*table), GFP_KERNEL); + + if (!table) + return NULL; + + hash_init(table->hashtable); + spin_lock_init(&table->lock); + return table; +} + +/* 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. this would not, however, help with the growing hash lengths, which + * is another thing to consider moving forward. + */ + +__le32 wg_index_hashtable_insert(struct index_hashtable *table, + struct index_hashtable_entry *entry) +{ + 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) + /* If it's already in use, we continue searching. */ + goto search_unused_slot; + } + + /* 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); + /* If it was stolen, we start over. */ + goto search_unused_slot; + } + } + /* 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)); + spin_unlock_bh(&table->lock); + + rcu_read_unlock_bh(); + + return entry->index; +} + +bool wg_index_hashtable_replace(struct index_hashtable *table, + struct index_hashtable_entry *old, + struct index_hashtable_entry *new) +{ + if (unlikely(hlist_unhashed(&old->index_hash))) + return false; + spin_lock_bh(&table->lock); + new->index = old->index; + hlist_replace_rcu(&old->index_hash, &new->index_hash); + + /* Calling init here NULLs out index_hash, and in fact after this + * function returns, it's theoretically possible for this to get + * reinserted elsewhere. That means the RCU lookup below might either + * terminate early or jump between buckets, in which case the packet + * simply gets dropped, which isn't terrible. + */ + INIT_HLIST_NODE(&old->index_hash); + spin_unlock_bh(&table->lock); + return true; +} + +void wg_index_hashtable_remove(struct index_hashtable *table, + struct index_hashtable_entry *entry) +{ + spin_lock_bh(&table->lock); + hlist_del_init_rcu(&entry->index_hash); + spin_unlock_bh(&table->lock); +} + +/* Returns a strong reference to a entry->peer */ +struct index_hashtable_entry * +wg_index_hashtable_lookup(struct index_hashtable *table, + const enum index_hashtable_type type_mask, + const __le32 index, struct wg_peer **peer) +{ + struct index_hashtable_entry *iter_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->peer = wg_peer_get_maybe_zero(entry->peer); + if (likely(entry->peer)) + *peer = entry->peer; + else + entry = NULL; + } + rcu_read_unlock_bh(); + return entry; +} diff --git a/src/peerlookup.h b/src/peerlookup.h new file mode 100644 index 0000000..ced8117 --- /dev/null +++ b/src/peerlookup.h @@ -0,0 +1,64 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * Copyright (C) 2015-2019 Jason A. Donenfeld . All Rights Reserved. + */ + +#ifndef _WG_PEERLOOKUP_H +#define _WG_PEERLOOKUP_H + +#include "messages.h" + +#include +#include +#include + +struct wg_peer; + +struct pubkey_hashtable { + /* TODO: move to rhashtable */ + DECLARE_HASHTABLE(hashtable, 11); + siphash_key_t key; + struct mutex lock; +}; + +struct pubkey_hashtable *wg_pubkey_hashtable_alloc(void); +void wg_pubkey_hashtable_add(struct pubkey_hashtable *table, + struct wg_peer *peer); +void wg_pubkey_hashtable_remove(struct pubkey_hashtable *table, + struct wg_peer *peer); +struct wg_peer * +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); + spinlock_t lock; +}; + +enum index_hashtable_type { + INDEX_HASHTABLE_HANDSHAKE = 1U << 0, + INDEX_HASHTABLE_KEYPAIR = 1U << 1 +}; + +struct index_hashtable_entry { + struct wg_peer *peer; + struct hlist_node index_hash; + enum index_hashtable_type type; + __le32 index; +}; + +struct index_hashtable *wg_index_hashtable_alloc(void); +__le32 wg_index_hashtable_insert(struct index_hashtable *table, + struct index_hashtable_entry *entry); +bool wg_index_hashtable_replace(struct index_hashtable *table, + struct index_hashtable_entry *old, + struct index_hashtable_entry *new); +void wg_index_hashtable_remove(struct index_hashtable *table, + struct index_hashtable_entry *entry); +struct index_hashtable_entry * +wg_index_hashtable_lookup(struct index_hashtable *table, + const enum index_hashtable_type type_mask, + const __le32 index, struct wg_peer **peer); + +#endif /* _WG_PEERLOOKUP_H */ -- cgit v1.2.3