1 // SPDX-License-Identifier: GPL-2.0 2 /* 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 10 static 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. Since 14 * the bits are uniformly distributed, we can then mask off to get the 15 * 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 22 struct 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 35 void 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 44 void 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 */ 53 struct wg_peer * 54 wg_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 73 static 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 uniformly 77 * 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 83 struct 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 might 96 * amount to 2^20*3 items in this hashtable. The algorithm below works by 97 * picking a random number and testing it. We can see that these limits mean we 98 * 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.999267578125 105 * >>> calculation(2, 2**20 * 3) 106 * 0.0007318854331970215 107 * >>> calculation(3, 2**20 * 3) 108 * 5.360489012673497e-07 109 * >>> calculation(4, 2**20 * 3) 110 * 3.9261394135792216e-10 111 * 112 * At the moment, we don't do any masking, so this algorithm isn't exactly 113 * constant time in either the random guessing or in the hash list lookup. We 114 * could require a minimum of 3 tries, which would successfully mask the 115 * guessing. this would not, however, help with the growing hash lengths, which 116 * 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 130 search_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-check 142 * 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 166 bool wg_index_hashtable_replace(struct index_hashtable *table, 167 struct index_hashtable_entry *old, 168 struct index_hashtable_entry *new) 169 { 170 if (unlikely(hlist_unhashed(&old->index_hash))) 171 return false; 172 spin_lock_bh(&table->lock); 173 new->index = old->index; 174 hlist_replace_rcu(&old->index_hash, &new->index_hash); 175 176 /* Calling init here NULLs out index_hash, and in fact after this 177 * function returns, it's theoretically possible for this to get 178 * reinserted elsewhere. That means the RCU lookup below might either 179 * terminate early or jump between buckets, in which case the packet 180 * simply gets dropped, which isn't terrible. 181 */ 182 INIT_HLIST_NODE(&old->index_hash); 183 spin_unlock_bh(&table->lock); 184 return true; 185 } 186 187 void wg_index_hashtable_remove(struct index_hashtable *table, 188 struct index_hashtable_entry *entry) 189 { 190 spin_lock_bh(&table->lock); 191 hlist_del_init_rcu(&entry->index_hash); 192 spin_unlock_bh(&table->lock); 193 } 194 195 /* Returns a strong reference to a entry->peer */ 196 struct index_hashtable_entry * 197 wg_index_hashtable_lookup(struct index_hashtable *table, 198 const enum index_hashtable_type type_mask, 199 const __le32 index, struct wg_peer **peer) 200 { 201 struct index_hashtable_entry *iter_entry, *entry = NULL; 202 203 rcu_read_lock_bh(); 204 hlist_for_each_entry_rcu_bh(iter_entry, index_bucket(table, index), 205 index_hash) { 206 if (iter_entry->index == index) { 207 if (likely(iter_entry->type & type_mask)) 208 entry = iter_entry; 209 break; 210 } 211 } 212 if (likely(entry)) { 213 entry->peer = wg_peer_get_maybe_zero(entry->peer); 214 if (likely(entry->peer)) 215 *peer = entry->peer; 216 else 217 entry = NULL; 218 } 219 rcu_read_unlock_bh(); 220 return entry; 221 } 222