drivers/net/wireguard/allowedips.c

   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 "allowedips.h"
   7 #include "peer.h"
   8
   9 enum { MAX_ALLOWEDIPS_DEPTH = 129 };
  10
  11 static struct kmem_cache *node_cache;
  12
  13 static void swap_endian(u8 *dst, const u8 *src, u8 bits)
  14 {
  15         if (bits == 32) {
  16                 *(u32 *)dst = be32_to_cpu(*(const __be32 *)src);
  17         } else if (bits == 128) {
  18                 ((u64 *)dst)[0] = be64_to_cpu(((const __be64 *)src)[0]);
  19                 ((u64 *)dst)[1] = be64_to_cpu(((const __be64 *)src)[1]);
  20         }
  21 }
  22
  23 static void copy_and_assign_cidr(struct allowedips_node *node, const u8 *src,
  24                                  u8 cidr, u8 bits)
  25 {
  26         node->cidr = cidr;
  27         node->bit_at_a = cidr / 8U;
  28 #ifdef __LITTLE_ENDIAN
  29         node->bit_at_a ^= (bits / 8U - 1U) % 8U;
  30 #endif
  31         node->bit_at_b = 7U - (cidr % 8U);
  32         node->bitlen = bits;
  33         memcpy(node->bits, src, bits / 8U);
  34 }
  35
  36 static inline u8 choose(struct allowedips_node *node, const u8 *key)
  37 {
  38         return (key[node->bit_at_a] >> node->bit_at_b) & 1;
  39 }
  40
  41 static void push_rcu(struct allowedips_node **stack,
  42                      struct allowedips_node __rcu *p, unsigned int *len)
  43 {
  44         if (rcu_access_pointer(p)) {
  45                 if (WARN_ON(IS_ENABLED(DEBUG) && *len >= MAX_ALLOWEDIPS_DEPTH))
  46                         return;
  47                 stack[(*len)++] = rcu_dereference_raw(p);
  48         }
  49 }
  50
  51 static void node_free_rcu(struct rcu_head *rcu)
  52 {
  53         kmem_cache_free(node_cache, container_of(rcu, struct allowedips_node, rcu));
  54 }
  55
  56 static void root_free_rcu(struct rcu_head *rcu)
  57 {
  58         struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = {
  59                 container_of(rcu, struct allowedips_node, rcu) };
  60         unsigned int len = 1;
  61
  62         while (len > 0 && (node = stack[--len])) {
  63                 push_rcu(stack, node->bit[0], &len);
  64                 push_rcu(stack, node->bit[1], &len);
  65                 kmem_cache_free(node_cache, node);
  66         }
  67 }
  68
  69 static void root_remove_peer_lists(struct allowedips_node *root)
  70 {
  71         struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = { root };
  72         unsigned int len = 1;
  73
  74         while (len > 0 && (node = stack[--len])) {
  75                 push_rcu(stack, node->bit[0], &len);
  76                 push_rcu(stack, node->bit[1], &len);
  77                 if (rcu_access_pointer(node->peer))
  78                         list_del(&node->peer_list);
  79         }
  80 }
  81
  82 static unsigned int fls128(u64 a, u64 b)
  83 {
  84         return a ? fls64(a) + 64U : fls64(b);
  85 }
  86
  87 static u8 common_bits(const struct allowedips_node *node, const u8 *key,
  88                       u8 bits)
  89 {
  90         if (bits == 32)
  91                 return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key);
  92         else if (bits == 128)
  93                 return 128U - fls128(
  94                         *(const u64 *)&node->bits[0] ^ *(const u64 *)&key[0],
  95                         *(const u64 *)&node->bits[8] ^ *(const u64 *)&key[8]);
  96         return 0;
  97 }
  98
  99 static bool prefix_matches(const struct allowedips_node *node, const u8 *key,
 100                            u8 bits)
 101 {
 102         /* This could be much faster if it actually just compared the common
 103          * bits properly, by precomputing a mask bswap(~0 << (32 - cidr)), and
 104          * the rest, but it turns out that common_bits is already super fast on
 105          * modern processors, even taking into account the unfortunate bswap.
 106          * So, we just inline it like this instead.
 107          */
 108         return common_bits(node, key, bits) >= node->cidr;
 109 }
 110
 111 static struct allowedips_node *find_node(struct allowedips_node *trie, u8 bits,
 112                                          const u8 *key)
 113 {
 114         struct allowedips_node *node = trie, *found = NULL;
 115
 116         while (node && prefix_matches(node, key, bits)) {
 117                 if (rcu_access_pointer(node->peer))
 118                         found = node;
 119                 if (node->cidr == bits)
 120                         break;
 121                 node = rcu_dereference_bh(node->bit[choose(node, key)]);
 122         }
 123         return found;
 124 }
 125
 126 /* Returns a strong reference to a peer */
 127 static struct wg_peer *lookup(struct allowedips_node __rcu *root, u8 bits,
 128                               const void *be_ip)
 129 {
 130         /* Aligned so it can be passed to fls/fls64 */
 131         u8 ip[16] __aligned(__alignof(u64));
 132         struct allowedips_node *node;
 133         struct wg_peer *peer = NULL;
 134
 135         swap_endian(ip, be_ip, bits);
 136
 137         rcu_read_lock_bh();
 138 retry:
 139         node = find_node(rcu_dereference_bh(root), bits, ip);
 140         if (node) {
 141                 peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer));
 142                 if (!peer)
 143                         goto retry;
 144         }
 145         rcu_read_unlock_bh();
 146         return peer;
 147 }
 148
 149 static bool node_placement(struct allowedips_node __rcu *trie, const u8 *key,
 150                            u8 cidr, u8 bits, struct allowedips_node **rnode,
 151                            struct mutex *lock)
 152 {
 153         struct allowedips_node *node = rcu_dereference_protected(trie, lockdep_is_held(lock));
 154         struct allowedips_node *parent = NULL;
 155         bool exact = false;
 156
 157         while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) {
 158                 parent = node;
 159                 if (parent->cidr == cidr) {
 160                         exact = true;
 161                         break;
 162                 }
 163                 node = rcu_dereference_protected(parent->bit[choose(parent, key)], lockdep_is_held(lock));
 164         }
 165         *rnode = parent;
 166         return exact;
 167 }
 168
 169 static inline void connect_node(struct allowedips_node __rcu **parent, u8 bit, struct allowedips_node *node)
 170 {
 171         node->parent_bit_packed = (unsigned long)parent | bit;
 172         rcu_assign_pointer(*parent, node);
 173 }
 174
 175 static inline void choose_and_connect_node(struct allowedips_node *parent, struct allowedips_node *node)
 176 {
 177         u8 bit = choose(parent, node->bits);
 178         connect_node(&parent->bit[bit], bit, node);
 179 }
 180
 181 static int add(struct allowedips_node __rcu **trie, u8 bits, const u8 *key,
 182                u8 cidr, struct wg_peer *peer, struct mutex *lock)
 183 {
 184         struct allowedips_node *node, *parent, *down, *newnode;
 185
 186         if (unlikely(cidr > bits || !peer))
 187                 return -EINVAL;
 188
 189         if (!rcu_access_pointer(*trie)) {
 190                 node = kmem_cache_zalloc(node_cache, GFP_KERNEL);
 191                 if (unlikely(!node))
 192                         return -ENOMEM;
 193                 RCU_INIT_POINTER(node->peer, peer);
 194                 list_add_tail(&node->peer_list, &peer->allowedips_list);
 195                 copy_and_assign_cidr(node, key, cidr, bits);
 196                 connect_node(trie, 2, node);
 197                 return 0;
 198         }
 199         if (node_placement(*trie, key, cidr, bits, &node, lock)) {
 200                 rcu_assign_pointer(node->peer, peer);
 201                 list_move_tail(&node->peer_list, &peer->allowedips_list);
 202                 return 0;
 203         }
 204
 205         newnode = kmem_cache_zalloc(node_cache, GFP_KERNEL);
 206         if (unlikely(!newnode))
 207                 return -ENOMEM;
 208         RCU_INIT_POINTER(newnode->peer, peer);
 209         list_add_tail(&newnode->peer_list, &peer->allowedips_list);
 210         copy_and_assign_cidr(newnode, key, cidr, bits);
 211
 212         if (!node) {
 213                 down = rcu_dereference_protected(*trie, lockdep_is_held(lock));
 214         } else {
 215                 const u8 bit = choose(node, key);
 216                 down = rcu_dereference_protected(node->bit[bit], lockdep_is_held(lock));
 217                 if (!down) {
 218                         connect_node(&node->bit[bit], bit, newnode);
 219                         return 0;
 220                 }
 221         }
 222         cidr = min(cidr, common_bits(down, key, bits));
 223         parent = node;
 224
 225         if (newnode->cidr == cidr) {
 226                 choose_and_connect_node(newnode, down);
 227                 if (!parent)
 228                         connect_node(trie, 2, newnode);
 229                 else
 230                         choose_and_connect_node(parent, newnode);
 231                 return 0;
 232         }
 233
 234         node = kmem_cache_zalloc(node_cache, GFP_KERNEL);
 235         if (unlikely(!node)) {
 236                 list_del(&newnode->peer_list);
 237                 kmem_cache_free(node_cache, newnode);
 238                 return -ENOMEM;
 239         }
 240         INIT_LIST_HEAD(&node->peer_list);
 241         copy_and_assign_cidr(node, newnode->bits, cidr, bits);
 242
 243         choose_and_connect_node(node, down);
 244         choose_and_connect_node(node, newnode);
 245         if (!parent)
 246                 connect_node(trie, 2, node);
 247         else
 248                 choose_and_connect_node(parent, node);
 249         return 0;
 250 }
 251
 252 void wg_allowedips_init(struct allowedips *table)
 253 {
 254         table->root4 = table->root6 = NULL;
 255         table->seq = 1;
 256 }
 257
 258 void wg_allowedips_free(struct allowedips *table, struct mutex *lock)
 259 {
 260         struct allowedips_node __rcu *old4 = table->root4, *old6 = table->root6;
 261
 262         ++table->seq;
 263         RCU_INIT_POINTER(table->root4, NULL);
 264         RCU_INIT_POINTER(table->root6, NULL);
 265         if (rcu_access_pointer(old4)) {
 266                 struct allowedips_node *node = rcu_dereference_protected(old4,
 267                                                         lockdep_is_held(lock));
 268
 269                 root_remove_peer_lists(node);
 270                 call_rcu(&node->rcu, root_free_rcu);
 271         }
 272         if (rcu_access_pointer(old6)) {
 273                 struct allowedips_node *node = rcu_dereference_protected(old6,
 274                                                         lockdep_is_held(lock));
 275
 276                 root_remove_peer_lists(node);
 277                 call_rcu(&node->rcu, root_free_rcu);
 278         }
 279 }
 280
 281 int wg_allowedips_insert_v4(struct allowedips *table, const struct in_addr *ip,
 282                             u8 cidr, struct wg_peer *peer, struct mutex *lock)
 283 {
 284         /* Aligned so it can be passed to fls */
 285         u8 key[4] __aligned(__alignof(u32));
 286
 287         ++table->seq;
 288         swap_endian(key, (const u8 *)ip, 32);
 289         return add(&table->root4, 32, key, cidr, peer, lock);
 290 }
 291
 292 int wg_allowedips_insert_v6(struct allowedips *table, const struct in6_addr *ip,
 293                             u8 cidr, struct wg_peer *peer, struct mutex *lock)
 294 {
 295         /* Aligned so it can be passed to fls64 */
 296         u8 key[16] __aligned(__alignof(u64));
 297
 298         ++table->seq;
 299         swap_endian(key, (const u8 *)ip, 128);
 300         return add(&table->root6, 128, key, cidr, peer, lock);
 301 }
 302
 303 void wg_allowedips_remove_by_peer(struct allowedips *table,
 304                                   struct wg_peer *peer, struct mutex *lock)
 305 {
 306         struct allowedips_node *node, *child, **parent_bit, *parent, *tmp;
 307         bool free_parent;
 308
 309         if (list_empty(&peer->allowedips_list))
 310                 return;
 311         ++table->seq;
 312         list_for_each_entry_safe(node, tmp, &peer->allowedips_list, peer_list) {
 313                 list_del_init(&node->peer_list);
 314                 RCU_INIT_POINTER(node->peer, NULL);
 315                 if (node->bit[0] && node->bit[1])
 316                         continue;
 317                 child = rcu_dereference_protected(node->bit[!rcu_access_pointer(node->bit[0])],
 318                                                   lockdep_is_held(lock));
 319                 if (child)
 320                         child->parent_bit_packed = node->parent_bit_packed;
 321                 parent_bit = (struct allowedips_node **)(node->parent_bit_packed & ~3UL);
 322                 *parent_bit = child;
 323                 parent = (void *)parent_bit -
 324                          offsetof(struct allowedips_node, bit[node->parent_bit_packed & 1]);
 325                 free_parent = !rcu_access_pointer(node->bit[0]) &&
 326                               !rcu_access_pointer(node->bit[1]) &&
 327                               (node->parent_bit_packed & 3) <= 1 &&
 328                               !rcu_access_pointer(parent->peer);
 329                 if (free_parent)
 330                         child = rcu_dereference_protected(
 331                                         parent->bit[!(node->parent_bit_packed & 1)],
 332                                         lockdep_is_held(lock));
 333                 call_rcu(&node->rcu, node_free_rcu);
 334                 if (!free_parent)
 335                         continue;
 336                 if (child)
 337                         child->parent_bit_packed = parent->parent_bit_packed;
 338                 *(struct allowedips_node **)(parent->parent_bit_packed & ~3UL) = child;
 339                 call_rcu(&parent->rcu, node_free_rcu);
 340         }
 341 }
 342
 343 int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr)
 344 {
 345         const unsigned int cidr_bytes = DIV_ROUND_UP(node->cidr, 8U);
 346         swap_endian(ip, node->bits, node->bitlen);
 347         memset(ip + cidr_bytes, 0, node->bitlen / 8U - cidr_bytes);
 348         if (node->cidr)
 349                 ip[cidr_bytes - 1U] &= ~0U << (-node->cidr % 8U);
 350
 351         *cidr = node->cidr;
 352         return node->bitlen == 32 ? AF_INET : AF_INET6;
 353 }
 354
 355 /* Returns a strong reference to a peer */
 356 struct wg_peer *wg_allowedips_lookup_dst(struct allowedips *table,
 357                                          struct sk_buff *skb)
 358 {
 359         if (skb->protocol == htons(ETH_P_IP))
 360                 return lookup(table->root4, 32, &ip_hdr(skb)->daddr);
 361         else if (skb->protocol == htons(ETH_P_IPV6))
 362                 return lookup(table->root6, 128, &ipv6_hdr(skb)->daddr);
 363         return NULL;
 364 }
 365
 366 /* Returns a strong reference to a peer */
 367 struct wg_peer *wg_allowedips_lookup_src(struct allowedips *table,
 368                                          struct sk_buff *skb)
 369 {
 370         if (skb->protocol == htons(ETH_P_IP))
 371                 return lookup(table->root4, 32, &ip_hdr(skb)->saddr);
 372         else if (skb->protocol == htons(ETH_P_IPV6))
 373                 return lookup(table->root6, 128, &ipv6_hdr(skb)->saddr);
 374         return NULL;
 375 }
 376
 377 int __init wg_allowedips_slab_init(void)
 378 {
 379         node_cache = KMEM_CACHE(allowedips_node, 0);
 380         return node_cache ? 0 : -ENOMEM;
 381 }
 382
 383 void wg_allowedips_slab_uninit(void)
 384 {
 385         rcu_barrier();
 386         kmem_cache_destroy(node_cache);
 387 }
 388
 389 #include "selftest/allowedips.c"