Lines Matching +full:32 +full:- +full:bits
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
9 static void swap_endian(u8 *dst, const u8 *src, u8 bits) in swap_endian() argument
11 if (bits == 32) { in swap_endian()
13 } else if (bits == 128) { in swap_endian()
20 u8 cidr, u8 bits) in copy_and_assign_cidr() argument
22 node->cidr = cidr; in copy_and_assign_cidr()
23 node->bit_at_a = cidr / 8U; in copy_and_assign_cidr()
25 node->bit_at_a ^= (bits / 8U - 1U) % 8U; in copy_and_assign_cidr()
27 node->bit_at_b = 7U - (cidr % 8U); in copy_and_assign_cidr()
28 node->bitlen = bits; in copy_and_assign_cidr()
29 memcpy(node->bits, src, bits / 8U); in copy_and_assign_cidr()
32 parent->bit[(key[parent->bit_at_a] >> parent->bit_at_b) & 1]
49 while (len > 0 && (node = stack[--len])) { in root_free_rcu()
50 push_rcu(stack, node->bit[0], &len); in root_free_rcu()
51 push_rcu(stack, node->bit[1], &len); in root_free_rcu()
61 while (len > 0 && (node = stack[--len])) { in root_remove_peer_lists()
62 push_rcu(stack, node->bit[0], &len); in root_remove_peer_lists()
63 push_rcu(stack, node->bit[1], &len); in root_remove_peer_lists()
64 if (rcu_access_pointer(node->peer)) in root_remove_peer_lists()
65 list_del(&node->peer_list); in root_remove_peer_lists()
87 nptr = stack[len - 1]; in walk_remove_by_peer()
90 --len; in walk_remove_by_peer()
93 if (!prev || REF(prev->bit[0]) == node || in walk_remove_by_peer()
94 REF(prev->bit[1]) == node) { in walk_remove_by_peer()
95 if (REF(node->bit[0])) in walk_remove_by_peer()
96 PUSH(&node->bit[0]); in walk_remove_by_peer()
97 else if (REF(node->bit[1])) in walk_remove_by_peer()
98 PUSH(&node->bit[1]); in walk_remove_by_peer()
99 } else if (REF(node->bit[0]) == prev) { in walk_remove_by_peer()
100 if (REF(node->bit[1])) in walk_remove_by_peer()
101 PUSH(&node->bit[1]); in walk_remove_by_peer()
103 if (rcu_dereference_protected(node->peer, in walk_remove_by_peer()
105 RCU_INIT_POINTER(node->peer, NULL); in walk_remove_by_peer()
106 list_del_init(&node->peer_list); in walk_remove_by_peer()
107 if (!node->bit[0] || !node->bit[1]) { in walk_remove_by_peer()
109 &node->bit[!REF(node->bit[0])])); in walk_remove_by_peer()
114 --len; in walk_remove_by_peer()
129 u8 bits) in common_bits() argument
131 if (bits == 32) in common_bits()
132 return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key); in common_bits()
133 else if (bits == 128) in common_bits()
134 return 128U - fls128( in common_bits()
135 *(const u64 *)&node->bits[0] ^ *(const u64 *)&key[0], in common_bits()
136 *(const u64 *)&node->bits[8] ^ *(const u64 *)&key[8]); in common_bits()
141 u8 bits) in prefix_matches() argument
144 * bits properly, by precomputing a mask bswap(~0 << (32 - cidr)), and in prefix_matches()
149 return common_bits(node, key, bits) >= node->cidr; in prefix_matches()
152 static struct allowedips_node *find_node(struct allowedips_node *trie, u8 bits, in find_node() argument
157 while (node && prefix_matches(node, key, bits)) { in find_node()
158 if (rcu_access_pointer(node->peer)) in find_node()
160 if (node->cidr == bits) in find_node()
168 static struct wg_peer *lookup(struct allowedips_node __rcu *root, u8 bits, in lookup() argument
176 swap_endian(ip, be_ip, bits); in lookup()
180 node = find_node(rcu_dereference_bh(root), bits, ip); in lookup()
182 peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer)); in lookup()
191 u8 cidr, u8 bits, struct allowedips_node **rnode, in node_placement() argument
199 while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) { in node_placement()
201 if (parent->cidr == cidr) { in node_placement()
212 static int add(struct allowedips_node __rcu **trie, u8 bits, const u8 *key, in add() argument
217 if (unlikely(cidr > bits || !peer)) in add()
218 return -EINVAL; in add()
223 return -ENOMEM; in add()
224 RCU_INIT_POINTER(node->peer, peer); in add()
225 list_add_tail(&node->peer_list, &peer->allowedips_list); in add()
226 copy_and_assign_cidr(node, key, cidr, bits); in add()
230 if (node_placement(*trie, key, cidr, bits, &node, lock)) { in add()
231 rcu_assign_pointer(node->peer, peer); in add()
232 list_move_tail(&node->peer_list, &peer->allowedips_list); in add()
238 return -ENOMEM; in add()
239 RCU_INIT_POINTER(newnode->peer, peer); in add()
240 list_add_tail(&newnode->peer_list, &peer->allowedips_list); in add()
241 copy_and_assign_cidr(newnode, key, cidr, bits); in add()
253 cidr = min(cidr, common_bits(down, key, bits)); in add()
256 if (newnode->cidr == cidr) { in add()
257 rcu_assign_pointer(CHOOSE_NODE(newnode, down->bits), down); in add()
261 rcu_assign_pointer(CHOOSE_NODE(parent, newnode->bits), in add()
266 list_del(&newnode->peer_list); in add()
268 return -ENOMEM; in add()
270 INIT_LIST_HEAD(&node->peer_list); in add()
271 copy_and_assign_cidr(node, newnode->bits, cidr, bits); in add()
273 rcu_assign_pointer(CHOOSE_NODE(node, down->bits), down); in add()
274 rcu_assign_pointer(CHOOSE_NODE(node, newnode->bits), newnode); in add()
278 rcu_assign_pointer(CHOOSE_NODE(parent, node->bits), in add()
286 table->root4 = table->root6 = NULL; in wg_allowedips_init()
287 table->seq = 1; in wg_allowedips_init()
292 struct allowedips_node __rcu *old4 = table->root4, *old6 = table->root6; in wg_allowedips_free()
294 ++table->seq; in wg_allowedips_free()
295 RCU_INIT_POINTER(table->root4, NULL); in wg_allowedips_free()
296 RCU_INIT_POINTER(table->root6, NULL); in wg_allowedips_free()
302 call_rcu(&node->rcu, root_free_rcu); in wg_allowedips_free()
309 call_rcu(&node->rcu, root_free_rcu); in wg_allowedips_free()
319 ++table->seq; in wg_allowedips_insert_v4()
320 swap_endian(key, (const u8 *)ip, 32); in wg_allowedips_insert_v4()
321 return add(&table->root4, 32, key, cidr, peer, lock); in wg_allowedips_insert_v4()
330 ++table->seq; in wg_allowedips_insert_v6()
332 return add(&table->root6, 128, key, cidr, peer, lock); in wg_allowedips_insert_v6()
338 ++table->seq; in wg_allowedips_remove_by_peer()
339 walk_remove_by_peer(&table->root4, peer, lock); in wg_allowedips_remove_by_peer()
340 walk_remove_by_peer(&table->root6, peer, lock); in wg_allowedips_remove_by_peer()
345 const unsigned int cidr_bytes = DIV_ROUND_UP(node->cidr, 8U); in wg_allowedips_read_node()
346 swap_endian(ip, node->bits, node->bitlen); in wg_allowedips_read_node()
347 memset(ip + cidr_bytes, 0, node->bitlen / 8U - cidr_bytes); in wg_allowedips_read_node()
348 if (node->cidr) in wg_allowedips_read_node()
349 ip[cidr_bytes - 1U] &= ~0U << (-node->cidr % 8U); in wg_allowedips_read_node()
351 *cidr = node->cidr; in wg_allowedips_read_node()
352 return node->bitlen == 32 ? AF_INET : AF_INET6; in wg_allowedips_read_node()
359 if (skb->protocol == htons(ETH_P_IP)) in wg_allowedips_lookup_dst()
360 return lookup(table->root4, 32, &ip_hdr(skb)->daddr); in wg_allowedips_lookup_dst()
361 else if (skb->protocol == htons(ETH_P_IPV6)) in wg_allowedips_lookup_dst()
362 return lookup(table->root6, 128, &ipv6_hdr(skb)->daddr); in wg_allowedips_lookup_dst()
370 if (skb->protocol == htons(ETH_P_IP)) in wg_allowedips_lookup_src()
371 return lookup(table->root4, 32, &ip_hdr(skb)->saddr); in wg_allowedips_lookup_src()
372 else if (skb->protocol == htons(ETH_P_IPV6)) in wg_allowedips_lookup_src()
373 return lookup(table->root6, 128, &ipv6_hdr(skb)->saddr); in wg_allowedips_lookup_src()