Lines Matching refs:node
23 static void copy_and_assign_cidr(struct allowedips_node *node, const u8 *src, in copy_and_assign_cidr() argument
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()
36 static inline u8 choose(struct allowedips_node *node, const u8 *key) in choose() argument
38 return (key[node->bit_at_a] >> node->bit_at_b) & 1; in choose()
58 struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = { 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()
65 kmem_cache_free(node_cache, node); in root_free_rcu()
71 struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = { root }; 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()
87 static u8 common_bits(const struct allowedips_node *node, const u8 *key, in common_bits() argument
91 return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key); 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()
99 static bool prefix_matches(const struct allowedips_node *node, const u8 *key, in prefix_matches() argument
108 return common_bits(node, key, bits) >= node->cidr; in prefix_matches()
114 struct allowedips_node *node = trie, *found = NULL; in find_node() local
116 while (node && prefix_matches(node, key, bits)) { in find_node()
117 if (rcu_access_pointer(node->peer)) in find_node()
118 found = node; in find_node()
119 if (node->cidr == bits) in find_node()
121 node = rcu_dereference_bh(node->bit[choose(node, key)]); in find_node()
132 struct allowedips_node *node; in lookup() local
139 node = find_node(rcu_dereference_bh(root), bits, ip); in lookup()
140 if (node) { in lookup()
141 peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer)); in lookup()
153 struct allowedips_node *node = rcu_dereference_protected(trie, lockdep_is_held(lock)); in node_placement() local
157 while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) { in node_placement()
158 parent = node; in node_placement()
163 node = rcu_dereference_protected(parent->bit[choose(parent, key)], lockdep_is_held(lock)); in node_placement()
169 …line void connect_node(struct allowedips_node __rcu **parent, u8 bit, struct allowedips_node *node) in connect_node() argument
171 node->parent_bit_packed = (unsigned long)parent | bit; in connect_node()
172 rcu_assign_pointer(*parent, node); in connect_node()
175 …c inline void choose_and_connect_node(struct allowedips_node *parent, struct allowedips_node *node) in choose_and_connect_node() argument
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()
184 struct allowedips_node *node, *parent, *down, *newnode; in add() local
190 node = kmem_cache_zalloc(node_cache, GFP_KERNEL); in add()
191 if (unlikely(!node)) in add()
193 RCU_INIT_POINTER(node->peer, peer); in add()
194 list_add_tail(&node->peer_list, &peer->allowedips_list); in add()
195 copy_and_assign_cidr(node, key, cidr, bits); in add()
196 connect_node(trie, 2, node); in add()
199 if (node_placement(*trie, key, cidr, bits, &node, lock)) { in add()
200 rcu_assign_pointer(node->peer, peer); in add()
201 list_move_tail(&node->peer_list, &peer->allowedips_list); in add()
212 if (!node) { in add()
215 const u8 bit = choose(node, key); 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()
223 parent = node; in add()
234 node = kmem_cache_zalloc(node_cache, GFP_KERNEL); in add()
235 if (unlikely(!node)) { in add()
240 INIT_LIST_HEAD(&node->peer_list); in add()
241 copy_and_assign_cidr(node, newnode->bits, cidr, bits); in add()
243 choose_and_connect_node(node, down); in add()
244 choose_and_connect_node(node, newnode); in add()
246 connect_node(trie, 2, node); in add()
248 choose_and_connect_node(parent, node); in add()
252 static void remove_node(struct allowedips_node *node, struct mutex *lock) in remove_node() argument
257 list_del_init(&node->peer_list); in remove_node()
258 RCU_INIT_POINTER(node->peer, NULL); in remove_node()
259 if (node->bit[0] && node->bit[1]) in remove_node()
261 child = rcu_dereference_protected(node->bit[!rcu_access_pointer(node->bit[0])], in remove_node()
264 child->parent_bit_packed = node->parent_bit_packed; in remove_node()
265 parent_bit = (struct allowedips_node **)(node->parent_bit_packed & ~3UL); in remove_node()
268 offsetof(struct allowedips_node, bit[node->parent_bit_packed & 1]); in remove_node()
269 free_parent = !rcu_access_pointer(node->bit[0]) && !rcu_access_pointer(node->bit[1]) && in remove_node()
270 (node->parent_bit_packed & 3) <= 1 && !rcu_access_pointer(parent->peer); in remove_node()
272 child = rcu_dereference_protected(parent->bit[!(node->parent_bit_packed & 1)], in remove_node()
274 call_rcu(&node->rcu, node_free_rcu); in remove_node()
286 struct allowedips_node *node; in remove() local
290 if (!rcu_access_pointer(*trie) || !node_placement(*trie, key, cidr, bits, &node, lock) || in remove()
291 peer != rcu_access_pointer(node->peer)) in remove()
294 remove_node(node, lock); in remove()
312 struct allowedips_node *node = rcu_dereference_protected(old4, in wg_allowedips_free() local
315 root_remove_peer_lists(node); in wg_allowedips_free()
316 call_rcu(&node->rcu, root_free_rcu); in wg_allowedips_free()
319 struct allowedips_node *node = rcu_dereference_protected(old6, in wg_allowedips_free() local
322 root_remove_peer_lists(node); in wg_allowedips_free()
323 call_rcu(&node->rcu, root_free_rcu); in wg_allowedips_free()
374 struct allowedips_node *node, *tmp; in wg_allowedips_remove_by_peer() local
379 list_for_each_entry_safe(node, tmp, &peer->allowedips_list, peer_list) in wg_allowedips_remove_by_peer()
380 remove_node(node, lock); in wg_allowedips_remove_by_peer()
383 int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr) in wg_allowedips_read_node() argument
385 const unsigned int cidr_bytes = DIV_ROUND_UP(node->cidr, 8U); in wg_allowedips_read_node()
386 swap_endian(ip, node->bits, node->bitlen); in wg_allowedips_read_node()
387 memset(ip + cidr_bytes, 0, node->bitlen / 8U - cidr_bytes); in wg_allowedips_read_node()
388 if (node->cidr) in wg_allowedips_read_node()
389 ip[cidr_bytes - 1U] &= ~0U << (-node->cidr % 8U); in wg_allowedips_read_node()
391 *cidr = node->cidr; in wg_allowedips_read_node()
392 return node->bitlen == 32 ? AF_INET : AF_INET6; in wg_allowedips_read_node()