Lines Matching refs:node
23 static void copy_and_assign_cidr(struct allowedips_node *node, const u8 *src,
26 node->cidr = cidr;
27 node->bit_at_a = cidr / 8U;
29 node->bit_at_a ^= (bits / 8U - 1U) % 8U;
31 node->bit_at_b = 7U - (cidr % 8U);
32 node->bitlen = bits;
33 memcpy(node->bits, src, bits / 8U);
36 static inline u8 choose(struct allowedips_node *node, const u8 *key)
38 return (key[node->bit_at_a] >> node->bit_at_b) & 1;
58 struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = {
62 while (len > 0 && (node = stack[--len])) {
63 push_rcu(stack, node->bit[0], &len);
64 push_rcu(stack, node->bit[1], &len);
65 kmem_cache_free(node_cache, node);
71 struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = { root };
74 while (len > 0 && (node = stack[--len])) {
75 push_rcu(stack, node->bit[0], &len);
76 push_rcu(stack, node->bit[1], &len);
77 if (rcu_access_pointer(node->peer))
78 list_del(&node->peer_list);
87 static u8 common_bits(const struct allowedips_node *node, const u8 *key,
91 return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key);
94 *(const u64 *)&node->bits[0] ^ *(const u64 *)&key[0],
95 *(const u64 *)&node->bits[8] ^ *(const u64 *)&key[8]);
99 static bool prefix_matches(const struct allowedips_node *node, const u8 *key,
108 return common_bits(node, key, bits) >= node->cidr;
114 struct allowedips_node *node = trie, *found = NULL;
116 while (node && prefix_matches(node, key, bits)) {
117 if (rcu_access_pointer(node->peer))
118 found = node;
119 if (node->cidr == bits)
121 node = rcu_dereference_bh(node->bit[choose(node, key)]);
132 struct allowedips_node *node;
139 node = find_node(rcu_dereference_bh(root), bits, ip);
140 if (node) {
141 peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer));
153 struct allowedips_node *node = rcu_dereference_protected(trie, lockdep_is_held(lock));
157 while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) {
158 parent = node;
163 node = rcu_dereference_protected(parent->bit[choose(parent, key)], lockdep_is_held(lock));
169 static inline void connect_node(struct allowedips_node __rcu **parent, u8 bit, struct allowedips_node *node)
171 node->parent_bit_packed = (unsigned long)parent | bit;
172 rcu_assign_pointer(*parent, node);
175 static inline void choose_and_connect_node(struct allowedips_node *parent, struct allowedips_node *node)
177 u8 bit = choose(parent, node->bits);
178 connect_node(&parent->bit[bit], bit, node);
184 struct allowedips_node *node, *parent, *down, *newnode;
190 node = kmem_cache_zalloc(node_cache, GFP_KERNEL);
191 if (unlikely(!node))
193 RCU_INIT_POINTER(node->peer, peer);
194 list_add_tail(&node->peer_list, &peer->allowedips_list);
195 copy_and_assign_cidr(node, key, cidr, bits);
196 connect_node(trie, 2, node);
199 if (node_placement(*trie, key, cidr, bits, &node, lock)) {
200 rcu_assign_pointer(node->peer, peer);
201 list_move_tail(&node->peer_list, &peer->allowedips_list);
212 if (!node) {
215 const u8 bit = choose(node, key);
216 down = rcu_dereference_protected(node->bit[bit], lockdep_is_held(lock));
218 connect_node(&node->bit[bit], bit, newnode);
223 parent = node;
234 node = kmem_cache_zalloc(node_cache, GFP_KERNEL);
235 if (unlikely(!node)) {
240 INIT_LIST_HEAD(&node->peer_list);
241 copy_and_assign_cidr(node, newnode->bits, cidr, bits);
243 choose_and_connect_node(node, down);
244 choose_and_connect_node(node, newnode);
246 connect_node(trie, 2, node);
248 choose_and_connect_node(parent, node);
266 struct allowedips_node *node = rcu_dereference_protected(old4,
269 root_remove_peer_lists(node);
270 call_rcu(&node->rcu, root_free_rcu);
273 struct allowedips_node *node = rcu_dereference_protected(old6,
276 root_remove_peer_lists(node);
277 call_rcu(&node->rcu, root_free_rcu);
306 struct allowedips_node *node, *child, **parent_bit, *parent, *tmp;
312 list_for_each_entry_safe(node, tmp, &peer->allowedips_list, peer_list) {
313 list_del_init(&node->peer_list);
314 RCU_INIT_POINTER(node->peer, NULL);
315 if (node->bit[0] && node->bit[1])
317 child = rcu_dereference_protected(node->bit[!rcu_access_pointer(node->bit[0])],
320 child->parent_bit_packed = node->parent_bit_packed;
321 parent_bit = (struct allowedips_node **)(node->parent_bit_packed & ~3UL);
324 offsetof(struct allowedips_node, bit[node->parent_bit_packed & 1]);
325 free_parent = !rcu_access_pointer(node->bit[0]) &&
326 !rcu_access_pointer(node->bit[1]) &&
327 (node->parent_bit_packed & 3) <= 1 &&
331 parent->bit[!(node->parent_bit_packed & 1)],
333 call_rcu(&node->rcu, node_free_rcu);
343 int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr)
345 const unsigned int cidr_bytes = DIV_ROUND_UP(node->cidr, 8U);
346 swap_endian(ip, node->bits, node->bitlen);
347 memset(ip + cidr_bytes, 0, node->bitlen / 8U - cidr_bytes);
348 if (node->cidr)
349 ip[cidr_bytes - 1U] &= ~0U << (-node->cidr % 8U);
351 *cidr = node->cidr;
352 return node->bitlen == 32 ? AF_INET : AF_INET6;