227 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.4 */5 6#include "peerlookup.h"7#include "peer.h"8#include "noise.h"9 10static struct hlist_head *pubkey_bucket(struct pubkey_hashtable *table,11 const u8 pubkey[NOISE_PUBLIC_KEY_LEN])12{13 /* siphash gives us a secure 64bit number based on a random key. Since14 * the bits are uniformly distributed, we can then mask off to get the15 * bits we need.16 */17 const u64 hash = siphash(pubkey, NOISE_PUBLIC_KEY_LEN, &table->key);18 19 return &table->hashtable[hash & (HASH_SIZE(table->hashtable) - 1)];20}21 22struct pubkey_hashtable *wg_pubkey_hashtable_alloc(void)23{24 struct pubkey_hashtable *table = kvmalloc(sizeof(*table), GFP_KERNEL);25 26 if (!table)27 return NULL;28 29 get_random_bytes(&table->key, sizeof(table->key));30 hash_init(table->hashtable);31 mutex_init(&table->lock);32 return table;33}34 35void wg_pubkey_hashtable_add(struct pubkey_hashtable *table,36 struct wg_peer *peer)37{38 mutex_lock(&table->lock);39 hlist_add_head_rcu(&peer->pubkey_hash,40 pubkey_bucket(table, peer->handshake.remote_static));41 mutex_unlock(&table->lock);42}43 44void wg_pubkey_hashtable_remove(struct pubkey_hashtable *table,45 struct wg_peer *peer)46{47 mutex_lock(&table->lock);48 hlist_del_init_rcu(&peer->pubkey_hash);49 mutex_unlock(&table->lock);50}51 52/* Returns a strong reference to a peer */53struct wg_peer *54wg_pubkey_hashtable_lookup(struct pubkey_hashtable *table,55 const u8 pubkey[NOISE_PUBLIC_KEY_LEN])56{57 struct wg_peer *iter_peer, *peer = NULL;58 59 rcu_read_lock_bh();60 hlist_for_each_entry_rcu_bh(iter_peer, pubkey_bucket(table, pubkey),61 pubkey_hash) {62 if (!memcmp(pubkey, iter_peer->handshake.remote_static,63 NOISE_PUBLIC_KEY_LEN)) {64 peer = iter_peer;65 break;66 }67 }68 peer = wg_peer_get_maybe_zero(peer);69 rcu_read_unlock_bh();70 return peer;71}72 73static struct hlist_head *index_bucket(struct index_hashtable *table,74 const __le32 index)75{76 /* Since the indices are random and thus all bits are uniformly77 * distributed, we can find its bucket simply by masking.78 */79 return &table->hashtable[(__force u32)index &80 (HASH_SIZE(table->hashtable) - 1)];81}82 83struct index_hashtable *wg_index_hashtable_alloc(void)84{85 struct index_hashtable *table = kvmalloc(sizeof(*table), GFP_KERNEL);86 87 if (!table)88 return NULL;89 90 hash_init(table->hashtable);91 spin_lock_init(&table->lock);92 return table;93}94 95/* At the moment, we limit ourselves to 2^20 total peers, which generally might96 * amount to 2^20*3 items in this hashtable. The algorithm below works by97 * picking a random number and testing it. We can see that these limits mean we98 * usually succeed pretty quickly:99 *100 * >>> def calculation(tries, size):101 * ... return (size / 2**32)**(tries - 1) * (1 - (size / 2**32))102 * ...103 * >>> calculation(1, 2**20 * 3)104 * 0.999267578125105 * >>> calculation(2, 2**20 * 3)106 * 0.0007318854331970215107 * >>> calculation(3, 2**20 * 3)108 * 5.360489012673497e-07109 * >>> calculation(4, 2**20 * 3)110 * 3.9261394135792216e-10111 *112 * At the moment, we don't do any masking, so this algorithm isn't exactly113 * constant time in either the random guessing or in the hash list lookup. We114 * could require a minimum of 3 tries, which would successfully mask the115 * guessing. this would not, however, help with the growing hash lengths, which116 * is another thing to consider moving forward.117 */118 119__le32 wg_index_hashtable_insert(struct index_hashtable *table,120 struct index_hashtable_entry *entry)121{122 struct index_hashtable_entry *existing_entry;123 124 spin_lock_bh(&table->lock);125 hlist_del_init_rcu(&entry->index_hash);126 spin_unlock_bh(&table->lock);127 128 rcu_read_lock_bh();129 130search_unused_slot:131 /* First we try to find an unused slot, randomly, while unlocked. */132 entry->index = (__force __le32)get_random_u32();133 hlist_for_each_entry_rcu_bh(existing_entry,134 index_bucket(table, entry->index),135 index_hash) {136 if (existing_entry->index == entry->index)137 /* If it's already in use, we continue searching. */138 goto search_unused_slot;139 }140 141 /* Once we've found an unused slot, we lock it, and then double-check142 * that nobody else stole it from us.143 */144 spin_lock_bh(&table->lock);145 hlist_for_each_entry_rcu_bh(existing_entry,146 index_bucket(table, entry->index),147 index_hash) {148 if (existing_entry->index == entry->index) {149 spin_unlock_bh(&table->lock);150 /* If it was stolen, we start over. */151 goto search_unused_slot;152 }153 }154 /* Otherwise, we know we have it exclusively (since we're locked),155 * so we insert.156 */157 hlist_add_head_rcu(&entry->index_hash,158 index_bucket(table, entry->index));159 spin_unlock_bh(&table->lock);160 161 rcu_read_unlock_bh();162 163 return entry->index;164}165 166bool wg_index_hashtable_replace(struct index_hashtable *table,167 struct index_hashtable_entry *old,168 struct index_hashtable_entry *new)169{170 bool ret;171 172 spin_lock_bh(&table->lock);173 ret = !hlist_unhashed(&old->index_hash);174 if (unlikely(!ret))175 goto out;176 177 new->index = old->index;178 hlist_replace_rcu(&old->index_hash, &new->index_hash);179 180 /* Calling init here NULLs out index_hash, and in fact after this181 * function returns, it's theoretically possible for this to get182 * reinserted elsewhere. That means the RCU lookup below might either183 * terminate early or jump between buckets, in which case the packet184 * simply gets dropped, which isn't terrible.185 */186 INIT_HLIST_NODE(&old->index_hash);187out:188 spin_unlock_bh(&table->lock);189 return ret;190}191 192void wg_index_hashtable_remove(struct index_hashtable *table,193 struct index_hashtable_entry *entry)194{195 spin_lock_bh(&table->lock);196 hlist_del_init_rcu(&entry->index_hash);197 spin_unlock_bh(&table->lock);198}199 200/* Returns a strong reference to a entry->peer */201struct index_hashtable_entry *202wg_index_hashtable_lookup(struct index_hashtable *table,203 const enum index_hashtable_type type_mask,204 const __le32 index, struct wg_peer **peer)205{206 struct index_hashtable_entry *iter_entry, *entry = NULL;207 208 rcu_read_lock_bh();209 hlist_for_each_entry_rcu_bh(iter_entry, index_bucket(table, index),210 index_hash) {211 if (iter_entry->index == index) {212 if (likely(iter_entry->type & type_mask))213 entry = iter_entry;214 break;215 }216 }217 if (likely(entry)) {218 entry->peer = wg_peer_get_maybe_zero(entry->peer);219 if (likely(entry->peer))220 *peer = entry->peer;221 else222 entry = NULL;223 }224 rcu_read_unlock_bh();225 return entry;226}227