21 static void copy_and_assign_cidr(struct allowedips_node *node, const u8 *src,  in copy_and_assign_cidr()  argument
24 	node->cidr = cidr;  in copy_and_assign_cidr()
25 	node->bit_at_a = cidr / 8U;  in copy_and_assign_cidr()
27 	node->bit_at_a ^= (bits / 8U - 1U) % 8U;  in copy_and_assign_cidr()
29 	node->bit_at_b = 7U - (cidr % 8U);  in copy_and_assign_cidr()
30 	node->bitlen = bits;  in copy_and_assign_cidr()
31 	memcpy(node->bits, src, bits / 8U);  in copy_and_assign_cidr()
34 static inline u8 choose(struct allowedips_node *node, const u8 *key)  in choose()  argument
36 	return (key[node->bit_at_a] >> node->bit_at_b) & 1;  in choose()
55 	struct allowedips_node *node, *stack[128] = {  in root_free_rcu()  local
59 	while (len > 0 && (node = stack[--len])) {  in root_free_rcu()
60 		push_rcu(stack, node->bit[0], &len);  in root_free_rcu()
61 		push_rcu(stack, node->bit[1], &len);  in root_free_rcu()
62 		kmem_cache_free(node_cache, node);  in root_free_rcu()
68 	struct allowedips_node *node, *stack[128] = { root };  in root_remove_peer_lists()  local
71 	while (len > 0 && (node = stack[--len])) {  in root_remove_peer_lists()
72 		push_rcu(stack, node->bit[0], &len);  in root_remove_peer_lists()
73 		push_rcu(stack, node->bit[1], &len);  in root_remove_peer_lists()
74 		if (rcu_access_pointer(node->peer))  in root_remove_peer_lists()
75 			list_del(&node->peer_list);  in root_remove_peer_lists()
84 static u8 common_bits(const struct allowedips_node *node, const u8 *key,  in common_bits()  argument
88 		return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key);  in common_bits()
91 			*(const u64 *)&node->bits[0] ^ *(const u64 *)&key[0],  in common_bits()
92 			*(const u64 *)&node->bits[8] ^ *(const u64 *)&key[8]);  in common_bits()
96 static bool prefix_matches(const struct allowedips_node *node, const u8 *key,  in prefix_matches()  argument
105 	return common_bits(node, key, bits) >= node->cidr;  in prefix_matches()
111 	struct allowedips_node *node = trie, *found = NULL;  in find_node()  local
113 	while (node && prefix_matches(node, key, bits)) {  in find_node()
114 		if (rcu_access_pointer(node->peer))  in find_node()
115 			found = node;  in find_node()
116 		if (node->cidr == bits)  in find_node()
118 		node = rcu_dereference_bh(node->bit[choose(node, key)]);  in find_node()
129 	struct allowedips_node *node;  in lookup()  local
136 	node = find_node(rcu_dereference_bh(root), bits, ip);  in lookup()
137 	if (node) {  in lookup()
138 		peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer));  in lookup()
150 	struct allowedips_node *node = rcu_dereference_protected(trie, lockdep_is_held(lock));  in node_placement()  local
154 	while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) {  in node_placement()
155 		parent = node;  in node_placement()
160 		node = rcu_dereference_protected(parent->bit[choose(parent, key)], lockdep_is_held(lock));  in node_placement()
166 …tic inline void connect_node(struct allowedips_node **parent, u8 bit, struct allowedips_node *node)  in connect_node()  argument
168 	node->parent_bit_packed = (unsigned long)parent | bit;  in connect_node()
169 	rcu_assign_pointer(*parent, node);  in connect_node()
172 …c inline void choose_and_connect_node(struct allowedips_node *parent, struct allowedips_node *node)  in choose_and_connect_node()  argument
174 	u8 bit = choose(parent, node->bits);  in choose_and_connect_node()
175 	connect_node(&parent->bit[bit], bit, node);  in choose_and_connect_node()
181 	struct allowedips_node *node, *parent, *down, *newnode;  in add()  local
187 		node = kmem_cache_zalloc(node_cache, GFP_KERNEL);  in add()
188 		if (unlikely(!node))  in add()
190 		RCU_INIT_POINTER(node->peer, peer);  in add()
191 		list_add_tail(&node->peer_list, &peer->allowedips_list);  in add()
192 		copy_and_assign_cidr(node, key, cidr, bits);  in add()
193 		connect_node(trie, 2, node);  in add()
196 	if (node_placement(*trie, key, cidr, bits, &node, lock)) {  in add()
197 		rcu_assign_pointer(node->peer, peer);  in add()
198 		list_move_tail(&node->peer_list, &peer->allowedips_list);  in add()
209 	if (!node) {  in add()
212 		const u8 bit = choose(node, key);  in add()
213 		down = rcu_dereference_protected(node->bit[bit], lockdep_is_held(lock));  in add()
215 			connect_node(&node->bit[bit], bit, newnode);  in add()
220 	parent = node;  in add()
231 	node = kmem_cache_zalloc(node_cache, GFP_KERNEL);  in add()
232 	if (unlikely(!node)) {  in add()
237 	INIT_LIST_HEAD(&node->peer_list);  in add()
238 	copy_and_assign_cidr(node, newnode->bits, cidr, bits);  in add()
240 	choose_and_connect_node(node, down);  in add()
241 	choose_and_connect_node(node, newnode);  in add()
243 		connect_node(trie, 2, node);  in add()
245 		choose_and_connect_node(parent, node);  in add()
263 		struct allowedips_node *node = rcu_dereference_protected(old4,  in wg_allowedips_free()  local
266 		root_remove_peer_lists(node);  in wg_allowedips_free()
267 		call_rcu(&node->rcu, root_free_rcu);  in wg_allowedips_free()
270 		struct allowedips_node *node = rcu_dereference_protected(old6,  in wg_allowedips_free()  local
273 		root_remove_peer_lists(node);  in wg_allowedips_free()
274 		call_rcu(&node->rcu, root_free_rcu);  in wg_allowedips_free()
303 	struct allowedips_node *node, *child, **parent_bit, *parent, *tmp;  in wg_allowedips_remove_by_peer()  local
309 	list_for_each_entry_safe(node, tmp, &peer->allowedips_list, peer_list) {  in wg_allowedips_remove_by_peer()
310 		list_del_init(&node->peer_list);  in wg_allowedips_remove_by_peer()
311 		RCU_INIT_POINTER(node->peer, NULL);  in wg_allowedips_remove_by_peer()
312 		if (node->bit[0] && node->bit[1])  in wg_allowedips_remove_by_peer()
314 		child = rcu_dereference_protected(node->bit[!rcu_access_pointer(node->bit[0])],  in wg_allowedips_remove_by_peer()
317 			child->parent_bit_packed = node->parent_bit_packed;  in wg_allowedips_remove_by_peer()
318 		parent_bit = (struct allowedips_node **)(node->parent_bit_packed & ~3UL);  in wg_allowedips_remove_by_peer()
321 			 offsetof(struct allowedips_node, bit[node->parent_bit_packed & 1]);  in wg_allowedips_remove_by_peer()
322 		free_parent = !rcu_access_pointer(node->bit[0]) &&  in wg_allowedips_remove_by_peer()
323 			      !rcu_access_pointer(node->bit[1]) &&  in wg_allowedips_remove_by_peer()
324 			      (node->parent_bit_packed & 3) <= 1 &&  in wg_allowedips_remove_by_peer()
328 					parent->bit[!(node->parent_bit_packed & 1)],  in wg_allowedips_remove_by_peer()
330 		call_rcu(&node->rcu, node_free_rcu);  in wg_allowedips_remove_by_peer()
340 int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr)  in wg_allowedips_read_node()  argument
342 	const unsigned int cidr_bytes = DIV_ROUND_UP(node->cidr, 8U);  in wg_allowedips_read_node()
343 	swap_endian(ip, node->bits, node->bitlen);  in wg_allowedips_read_node()
344 	memset(ip + cidr_bytes, 0, node->bitlen / 8U - cidr_bytes);  in wg_allowedips_read_node()
345 	if (node->cidr)  in wg_allowedips_read_node()
346 		ip[cidr_bytes - 1U] &= ~0U << (-node->cidr % 8U);  in wg_allowedips_read_node()
348 	*cidr = node->cidr;  in wg_allowedips_read_node()
349 	return node->bitlen == 32 ? AF_INET : AF_INET6;  in wg_allowedips_read_node()