Lines Matching full:node
19 static void copy_and_assign_cidr(struct allowedips_node *node, const u8 *src, 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()
45 struct allowedips_node *node, *stack[128] = { in root_free_rcu() local
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()
52 kfree(node); in root_free_rcu()
58 struct allowedips_node *node, *stack[128] = { root }; in root_remove_peer_lists() local
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()
80 struct allowedips_node *node, *prev; in walk_remove_by_peer() local
86 for (prev = NULL, len = 0, PUSH(top); len > 0; prev = node) { in walk_remove_by_peer()
88 node = DEREF(nptr); in walk_remove_by_peer()
89 if (!node) { 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()
110 kfree_rcu(node, rcu); in walk_remove_by_peer()
111 node = DEREF(nptr); in walk_remove_by_peer()
128 static u8 common_bits(const struct allowedips_node *node, const u8 *key, in common_bits() argument
132 return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key); 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()
140 static bool prefix_matches(const struct allowedips_node *node, const u8 *key, in prefix_matches() argument
149 return common_bits(node, key, bits) >= node->cidr; in prefix_matches()
155 struct allowedips_node *node = trie, *found = NULL; in find_node() local
157 while (node && prefix_matches(node, key, bits)) { in find_node()
158 if (rcu_access_pointer(node->peer)) in find_node()
159 found = node; in find_node()
160 if (node->cidr == bits) in find_node()
162 node = rcu_dereference_bh(CHOOSE_NODE(node, key)); in find_node()
173 struct allowedips_node *node; in lookup() local
180 node = find_node(rcu_dereference_bh(root), bits, ip); in lookup()
181 if (node) { in lookup()
182 peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer)); in lookup()
194 struct allowedips_node *node = rcu_dereference_protected(trie, in node_placement() local
199 while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) { in node_placement()
200 parent = node; in node_placement()
205 node = rcu_dereference_protected(CHOOSE_NODE(parent, key), in node_placement()
215 struct allowedips_node *node, *parent, *down, *newnode; in add() local
221 node = kzalloc(sizeof(*node), GFP_KERNEL); in add()
222 if (unlikely(!node)) 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()
227 rcu_assign_pointer(*trie, node); 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()
243 if (!node) { in add()
246 down = rcu_dereference_protected(CHOOSE_NODE(node, key), in add()
249 rcu_assign_pointer(CHOOSE_NODE(node, key), newnode); in add()
254 parent = node; in add()
264 node = kzalloc(sizeof(*node), GFP_KERNEL); in add()
265 if (unlikely(!node)) { 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()
276 rcu_assign_pointer(*trie, node); in add()
278 rcu_assign_pointer(CHOOSE_NODE(parent, node->bits), in add()
279 node); in add()
298 struct allowedips_node *node = rcu_dereference_protected(old4, in wg_allowedips_free() local
301 root_remove_peer_lists(node); in wg_allowedips_free()
302 call_rcu(&node->rcu, root_free_rcu); in wg_allowedips_free()
305 struct allowedips_node *node = rcu_dereference_protected(old6, in wg_allowedips_free() local
308 root_remove_peer_lists(node); in wg_allowedips_free()
309 call_rcu(&node->rcu, root_free_rcu); in wg_allowedips_free()
343 int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr) in wg_allowedips_read_node() argument
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()