1 // SPDX-License-Identifier: GPL-2.0
3  * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
26 	node->cidr = cidr;  in copy_and_assign_cidr()
27 	node->bit_at_a = cidr / 8U;  in copy_and_assign_cidr()
29 	node->bit_at_a ^= (bits / 8U - 1U) % 8U;  in copy_and_assign_cidr()
31 	node->bit_at_b = 7U - (cidr % 8U);  in copy_and_assign_cidr()
32 	node->bitlen = bits;  in copy_and_assign_cidr()
33 	memcpy(node->bits, src, bits / 8U);  in copy_and_assign_cidr()
38 	return (key[node->bit_at_a] >> node->bit_at_b) & 1;  in choose()
42 		     struct allowedips_node __rcu *p, unsigned int *len)  in push_rcu()  argument
45 		if (WARN_ON(IS_ENABLED(DEBUG) && *len >= MAX_ALLOWEDIPS_DEPTH))  in push_rcu()
47 		stack[(*len)++] = rcu_dereference_raw(p);  in push_rcu()
60 	unsigned int len = 1;  in root_free_rcu()  local
62 	while (len > 0 && (node = stack[--len])) {  in root_free_rcu()
63 		push_rcu(stack, node->bit[0], &len);  in root_free_rcu()
64 		push_rcu(stack, node->bit[1], &len);  in root_free_rcu()
72 	unsigned int len = 1;  in root_remove_peer_lists()  local
74 	while (len > 0 && (node = stack[--len])) {  in root_remove_peer_lists()
75 		push_rcu(stack, node->bit[0], &len);  in root_remove_peer_lists()
76 		push_rcu(stack, node->bit[1], &len);  in root_remove_peer_lists()
77 		if (rcu_access_pointer(node->peer))  in root_remove_peer_lists()
78 			list_del(&node->peer_list);  in root_remove_peer_lists()
91 		return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key);  in common_bits()
93 		return 128U - fls128(  in common_bits()
94 			*(const u64 *)&node->bits[0] ^ *(const u64 *)&key[0],  in common_bits()
95 			*(const u64 *)&node->bits[8] ^ *(const u64 *)&key[8]);  in common_bits()
103 	 * bits properly, by precomputing a mask bswap(~0 << (32 - cidr)), and  in prefix_matches()
108 	return common_bits(node, key, bits) >= node->cidr;  in prefix_matches()
117 		if (rcu_access_pointer(node->peer))  in find_node()
119 		if (node->cidr == bits)  in find_node()
121 		node = rcu_dereference_bh(node->bit[choose(node, key)]);  in find_node()
141 		peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer));  in lookup()
155 	bool exact = false;  in node_placement()  local
157 	while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) {  in node_placement()
159 		if (parent->cidr == cidr) {  in node_placement()
160 			exact = true;  in node_placement()
163 		node = rcu_dereference_protected(parent->bit[choose(parent, key)], lockdep_is_held(lock));  in node_placement()
166 	return exact;  in node_placement()
171 	node->parent_bit_packed = (unsigned long)parent | bit;  in connect_node()
177 	u8 bit = choose(parent, node->bits);  in choose_and_connect_node()
178 	connect_node(&parent->bit[bit], bit, node);  in choose_and_connect_node()
187 		return -EINVAL;  in add()
192 			return -ENOMEM;  in add()
193 		RCU_INIT_POINTER(node->peer, peer);  in add()
194 		list_add_tail(&node->peer_list, &peer->allowedips_list);  in add()
200 		rcu_assign_pointer(node->peer, peer);  in add()
201 		list_move_tail(&node->peer_list, &peer->allowedips_list);  in add()
207 		return -ENOMEM;  in add()
208 	RCU_INIT_POINTER(newnode->peer, peer);  in add()
209 	list_add_tail(&newnode->peer_list, &peer->allowedips_list);  in add()
216 		down = rcu_dereference_protected(node->bit[bit], lockdep_is_held(lock));  in add()
218 			connect_node(&node->bit[bit], bit, newnode);  in add()
225 	if (newnode->cidr == cidr) {  in add()
236 		list_del(&newnode->peer_list);  in add()
238 		return -ENOMEM;  in add()
240 	INIT_LIST_HEAD(&node->peer_list);  in add()
241 	copy_and_assign_cidr(node, newnode->bits, cidr, bits);  in add()
254 	table->root4 = table->root6 = NULL;  in wg_allowedips_init()
255 	table->seq = 1;  in wg_allowedips_init()
260 	struct allowedips_node __rcu *old4 = table->root4, *old6 = table->root6;  in wg_allowedips_free()
262 	++table->seq;  in wg_allowedips_free()
263 	RCU_INIT_POINTER(table->root4, NULL);  in wg_allowedips_free()
264 	RCU_INIT_POINTER(table->root6, NULL);  in wg_allowedips_free()
270 		call_rcu(&node->rcu, root_free_rcu);  in wg_allowedips_free()
277 		call_rcu(&node->rcu, root_free_rcu);  in wg_allowedips_free()
287 	++table->seq;  in wg_allowedips_insert_v4()
289 	return add(&table->root4, 32, key, cidr, peer, lock);  in wg_allowedips_insert_v4()
298 	++table->seq;  in wg_allowedips_insert_v6()
300 	return add(&table->root6, 128, key, cidr, peer, lock);  in wg_allowedips_insert_v6()
309 	if (list_empty(&peer->allowedips_list))  in wg_allowedips_remove_by_peer()
311 	++table->seq;  in wg_allowedips_remove_by_peer()
312 	list_for_each_entry_safe(node, tmp, &peer->allowedips_list, peer_list) {  in wg_allowedips_remove_by_peer()
313 		list_del_init(&node->peer_list);  in wg_allowedips_remove_by_peer()
314 		RCU_INIT_POINTER(node->peer, NULL);  in wg_allowedips_remove_by_peer()
315 		if (node->bit[0] && node->bit[1])  in wg_allowedips_remove_by_peer()
317 		child = rcu_dereference_protected(node->bit[!rcu_access_pointer(node->bit[0])],  in wg_allowedips_remove_by_peer()
320 			child->parent_bit_packed = node->parent_bit_packed;  in wg_allowedips_remove_by_peer()
321 		parent_bit = (struct allowedips_node **)(node->parent_bit_packed & ~3UL);  in wg_allowedips_remove_by_peer()
323 		parent = (void *)parent_bit -  in wg_allowedips_remove_by_peer()
324 			 offsetof(struct allowedips_node, bit[node->parent_bit_packed & 1]);  in wg_allowedips_remove_by_peer()
325 		free_parent = !rcu_access_pointer(node->bit[0]) &&  in wg_allowedips_remove_by_peer()
326 			      !rcu_access_pointer(node->bit[1]) &&  in wg_allowedips_remove_by_peer()
327 			      (node->parent_bit_packed & 3) <= 1 &&  in wg_allowedips_remove_by_peer()
328 			      !rcu_access_pointer(parent->peer);  in wg_allowedips_remove_by_peer()
331 					parent->bit[!(node->parent_bit_packed & 1)],  in wg_allowedips_remove_by_peer()
333 		call_rcu(&node->rcu, node_free_rcu);  in wg_allowedips_remove_by_peer()
337 			child->parent_bit_packed = parent->parent_bit_packed;  in wg_allowedips_remove_by_peer()
338 		*(struct allowedips_node **)(parent->parent_bit_packed & ~3UL) = child;  in wg_allowedips_remove_by_peer()
339 		call_rcu(&parent->rcu, node_free_rcu);  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()
380 	return node_cache ? 0 : -ENOMEM;  in wg_allowedips_slab_init()