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