Loading...
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
4 */
5
6#include "allowedips.h"
7#include "peer.h"
8
9enum { MAX_ALLOWEDIPS_DEPTH = 129 };
10
11static struct kmem_cache *node_cache;
12
13static void swap_endian(u8 *dst, const u8 *src, u8 bits)
14{
15 if (bits == 32) {
16 *(u32 *)dst = be32_to_cpu(*(const __be32 *)src);
17 } else if (bits == 128) {
18 ((u64 *)dst)[0] = be64_to_cpu(((const __be64 *)src)[0]);
19 ((u64 *)dst)[1] = be64_to_cpu(((const __be64 *)src)[1]);
20 }
21}
22
23static void copy_and_assign_cidr(struct allowedips_node *node, const u8 *src,
24 u8 cidr, u8 bits)
25{
26 node->cidr = cidr;
27 node->bit_at_a = cidr / 8U;
28#ifdef __LITTLE_ENDIAN
29 node->bit_at_a ^= (bits / 8U - 1U) % 8U;
30#endif
31 node->bit_at_b = 7U - (cidr % 8U);
32 node->bitlen = bits;
33 memcpy(node->bits, src, bits / 8U);
34}
35
36static inline u8 choose(struct allowedips_node *node, const u8 *key)
37{
38 return (key[node->bit_at_a] >> node->bit_at_b) & 1;
39}
40
41static void push_rcu(struct allowedips_node **stack,
42 struct allowedips_node __rcu *p, unsigned int *len)
43{
44 if (rcu_access_pointer(p)) {
45 if (WARN_ON(IS_ENABLED(DEBUG) && *len >= MAX_ALLOWEDIPS_DEPTH))
46 return;
47 stack[(*len)++] = rcu_dereference_raw(p);
48 }
49}
50
51static void node_free_rcu(struct rcu_head *rcu)
52{
53 kmem_cache_free(node_cache, container_of(rcu, struct allowedips_node, rcu));
54}
55
56static void root_free_rcu(struct rcu_head *rcu)
57{
58 struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = {
59 container_of(rcu, struct allowedips_node, rcu) };
60 unsigned int len = 1;
61
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);
66 }
67}
68
69static void root_remove_peer_lists(struct allowedips_node *root)
70{
71 struct allowedips_node *node, *stack[MAX_ALLOWEDIPS_DEPTH] = { root };
72 unsigned int len = 1;
73
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);
79 }
80}
81
82static unsigned int fls128(u64 a, u64 b)
83{
84 return a ? fls64(a) + 64U : fls64(b);
85}
86
87static u8 common_bits(const struct allowedips_node *node, const u8 *key,
88 u8 bits)
89{
90 if (bits == 32)
91 return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key);
92 else if (bits == 128)
93 return 128U - fls128(
94 *(const u64 *)&node->bits[0] ^ *(const u64 *)&key[0],
95 *(const u64 *)&node->bits[8] ^ *(const u64 *)&key[8]);
96 return 0;
97}
98
99static bool prefix_matches(const struct allowedips_node *node, const u8 *key,
100 u8 bits)
101{
102 /* This could be much faster if it actually just compared the common
103 * bits properly, by precomputing a mask bswap(~0 << (32 - cidr)), and
104 * the rest, but it turns out that common_bits is already super fast on
105 * modern processors, even taking into account the unfortunate bswap.
106 * So, we just inline it like this instead.
107 */
108 return common_bits(node, key, bits) >= node->cidr;
109}
110
111static struct allowedips_node *find_node(struct allowedips_node *trie, u8 bits,
112 const u8 *key)
113{
114 struct allowedips_node *node = trie, *found = NULL;
115
116 while (node && prefix_matches(node, key, bits)) {
117 if (rcu_access_pointer(node->peer))
118 found = node;
119 if (node->cidr == bits)
120 break;
121 node = rcu_dereference_bh(node->bit[choose(node, key)]);
122 }
123 return found;
124}
125
126/* Returns a strong reference to a peer */
127static struct wg_peer *lookup(struct allowedips_node __rcu *root, u8 bits,
128 const void *be_ip)
129{
130 /* Aligned so it can be passed to fls/fls64 */
131 u8 ip[16] __aligned(__alignof(u64));
132 struct allowedips_node *node;
133 struct wg_peer *peer = NULL;
134
135 swap_endian(ip, be_ip, bits);
136
137 rcu_read_lock_bh();
138retry:
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));
142 if (!peer)
143 goto retry;
144 }
145 rcu_read_unlock_bh();
146 return peer;
147}
148
149static bool node_placement(struct allowedips_node __rcu *trie, const u8 *key,
150 u8 cidr, u8 bits, struct allowedips_node **rnode,
151 struct mutex *lock)
152{
153 struct allowedips_node *node = rcu_dereference_protected(trie, lockdep_is_held(lock));
154 struct allowedips_node *parent = NULL;
155 bool exact = false;
156
157 while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) {
158 parent = node;
159 if (parent->cidr == cidr) {
160 exact = true;
161 break;
162 }
163 node = rcu_dereference_protected(parent->bit[choose(parent, key)], lockdep_is_held(lock));
164 }
165 *rnode = parent;
166 return exact;
167}
168
169static inline void connect_node(struct allowedips_node __rcu **parent, u8 bit, struct allowedips_node *node)
170{
171 node->parent_bit_packed = (unsigned long)parent | bit;
172 rcu_assign_pointer(*parent, node);
173}
174
175static inline void choose_and_connect_node(struct allowedips_node *parent, struct allowedips_node *node)
176{
177 u8 bit = choose(parent, node->bits);
178 connect_node(&parent->bit[bit], bit, node);
179}
180
181static int add(struct allowedips_node __rcu **trie, u8 bits, const u8 *key,
182 u8 cidr, struct wg_peer *peer, struct mutex *lock)
183{
184 struct allowedips_node *node, *parent, *down, *newnode;
185
186 if (unlikely(cidr > bits || !peer))
187 return -EINVAL;
188
189 if (!rcu_access_pointer(*trie)) {
190 node = kmem_cache_zalloc(node_cache, GFP_KERNEL);
191 if (unlikely(!node))
192 return -ENOMEM;
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);
197 return 0;
198 }
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);
202 return 0;
203 }
204
205 newnode = kmem_cache_zalloc(node_cache, GFP_KERNEL);
206 if (unlikely(!newnode))
207 return -ENOMEM;
208 RCU_INIT_POINTER(newnode->peer, peer);
209 list_add_tail(&newnode->peer_list, &peer->allowedips_list);
210 copy_and_assign_cidr(newnode, key, cidr, bits);
211
212 if (!node) {
213 down = rcu_dereference_protected(*trie, lockdep_is_held(lock));
214 } else {
215 const u8 bit = choose(node, key);
216 down = rcu_dereference_protected(node->bit[bit], lockdep_is_held(lock));
217 if (!down) {
218 connect_node(&node->bit[bit], bit, newnode);
219 return 0;
220 }
221 }
222 cidr = min(cidr, common_bits(down, key, bits));
223 parent = node;
224
225 if (newnode->cidr == cidr) {
226 choose_and_connect_node(newnode, down);
227 if (!parent)
228 connect_node(trie, 2, newnode);
229 else
230 choose_and_connect_node(parent, newnode);
231 return 0;
232 }
233
234 node = kmem_cache_zalloc(node_cache, GFP_KERNEL);
235 if (unlikely(!node)) {
236 list_del(&newnode->peer_list);
237 kmem_cache_free(node_cache, newnode);
238 return -ENOMEM;
239 }
240 INIT_LIST_HEAD(&node->peer_list);
241 copy_and_assign_cidr(node, newnode->bits, cidr, bits);
242
243 choose_and_connect_node(node, down);
244 choose_and_connect_node(node, newnode);
245 if (!parent)
246 connect_node(trie, 2, node);
247 else
248 choose_and_connect_node(parent, node);
249 return 0;
250}
251
252void wg_allowedips_init(struct allowedips *table)
253{
254 table->root4 = table->root6 = NULL;
255 table->seq = 1;
256}
257
258void wg_allowedips_free(struct allowedips *table, struct mutex *lock)
259{
260 struct allowedips_node __rcu *old4 = table->root4, *old6 = table->root6;
261
262 ++table->seq;
263 RCU_INIT_POINTER(table->root4, NULL);
264 RCU_INIT_POINTER(table->root6, NULL);
265 if (rcu_access_pointer(old4)) {
266 struct allowedips_node *node = rcu_dereference_protected(old4,
267 lockdep_is_held(lock));
268
269 root_remove_peer_lists(node);
270 call_rcu(&node->rcu, root_free_rcu);
271 }
272 if (rcu_access_pointer(old6)) {
273 struct allowedips_node *node = rcu_dereference_protected(old6,
274 lockdep_is_held(lock));
275
276 root_remove_peer_lists(node);
277 call_rcu(&node->rcu, root_free_rcu);
278 }
279}
280
281int wg_allowedips_insert_v4(struct allowedips *table, const struct in_addr *ip,
282 u8 cidr, struct wg_peer *peer, struct mutex *lock)
283{
284 /* Aligned so it can be passed to fls */
285 u8 key[4] __aligned(__alignof(u32));
286
287 ++table->seq;
288 swap_endian(key, (const u8 *)ip, 32);
289 return add(&table->root4, 32, key, cidr, peer, lock);
290}
291
292int wg_allowedips_insert_v6(struct allowedips *table, const struct in6_addr *ip,
293 u8 cidr, struct wg_peer *peer, struct mutex *lock)
294{
295 /* Aligned so it can be passed to fls64 */
296 u8 key[16] __aligned(__alignof(u64));
297
298 ++table->seq;
299 swap_endian(key, (const u8 *)ip, 128);
300 return add(&table->root6, 128, key, cidr, peer, lock);
301}
302
303void wg_allowedips_remove_by_peer(struct allowedips *table,
304 struct wg_peer *peer, struct mutex *lock)
305{
306 struct allowedips_node *node, *child, **parent_bit, *parent, *tmp;
307 bool free_parent;
308
309 if (list_empty(&peer->allowedips_list))
310 return;
311 ++table->seq;
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])
316 continue;
317 child = rcu_dereference_protected(node->bit[!rcu_access_pointer(node->bit[0])],
318 lockdep_is_held(lock));
319 if (child)
320 child->parent_bit_packed = node->parent_bit_packed;
321 parent_bit = (struct allowedips_node **)(node->parent_bit_packed & ~3UL);
322 *parent_bit = child;
323 parent = (void *)parent_bit -
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 &&
328 !rcu_access_pointer(parent->peer);
329 if (free_parent)
330 child = rcu_dereference_protected(
331 parent->bit[!(node->parent_bit_packed & 1)],
332 lockdep_is_held(lock));
333 call_rcu(&node->rcu, node_free_rcu);
334 if (!free_parent)
335 continue;
336 if (child)
337 child->parent_bit_packed = parent->parent_bit_packed;
338 *(struct allowedips_node **)(parent->parent_bit_packed & ~3UL) = child;
339 call_rcu(&parent->rcu, node_free_rcu);
340 }
341}
342
343int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr)
344{
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);
350
351 *cidr = node->cidr;
352 return node->bitlen == 32 ? AF_INET : AF_INET6;
353}
354
355/* Returns a strong reference to a peer */
356struct wg_peer *wg_allowedips_lookup_dst(struct allowedips *table,
357 struct sk_buff *skb)
358{
359 if (skb->protocol == htons(ETH_P_IP))
360 return lookup(table->root4, 32, &ip_hdr(skb)->daddr);
361 else if (skb->protocol == htons(ETH_P_IPV6))
362 return lookup(table->root6, 128, &ipv6_hdr(skb)->daddr);
363 return NULL;
364}
365
366/* Returns a strong reference to a peer */
367struct wg_peer *wg_allowedips_lookup_src(struct allowedips *table,
368 struct sk_buff *skb)
369{
370 if (skb->protocol == htons(ETH_P_IP))
371 return lookup(table->root4, 32, &ip_hdr(skb)->saddr);
372 else if (skb->protocol == htons(ETH_P_IPV6))
373 return lookup(table->root6, 128, &ipv6_hdr(skb)->saddr);
374 return NULL;
375}
376
377int __init wg_allowedips_slab_init(void)
378{
379 node_cache = KMEM_CACHE(allowedips_node, 0);
380 return node_cache ? 0 : -ENOMEM;
381}
382
383void wg_allowedips_slab_uninit(void)
384{
385 rcu_barrier();
386 kmem_cache_destroy(node_cache);
387}
388
389#include "selftest/allowedips.c"
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
4 */
5
6#include "allowedips.h"
7#include "peer.h"
8
9static void swap_endian(u8 *dst, const u8 *src, u8 bits)
10{
11 if (bits == 32) {
12 *(u32 *)dst = be32_to_cpu(*(const __be32 *)src);
13 } else if (bits == 128) {
14 ((u64 *)dst)[0] = be64_to_cpu(((const __be64 *)src)[0]);
15 ((u64 *)dst)[1] = be64_to_cpu(((const __be64 *)src)[1]);
16 }
17}
18
19static void copy_and_assign_cidr(struct allowedips_node *node, const u8 *src,
20 u8 cidr, u8 bits)
21{
22 node->cidr = cidr;
23 node->bit_at_a = cidr / 8U;
24#ifdef __LITTLE_ENDIAN
25 node->bit_at_a ^= (bits / 8U - 1U) % 8U;
26#endif
27 node->bit_at_b = 7U - (cidr % 8U);
28 node->bitlen = bits;
29 memcpy(node->bits, src, bits / 8U);
30}
31#define CHOOSE_NODE(parent, key) \
32 parent->bit[(key[parent->bit_at_a] >> parent->bit_at_b) & 1]
33
34static void push_rcu(struct allowedips_node **stack,
35 struct allowedips_node __rcu *p, unsigned int *len)
36{
37 if (rcu_access_pointer(p)) {
38 WARN_ON(IS_ENABLED(DEBUG) && *len >= 128);
39 stack[(*len)++] = rcu_dereference_raw(p);
40 }
41}
42
43static void root_free_rcu(struct rcu_head *rcu)
44{
45 struct allowedips_node *node, *stack[128] = {
46 container_of(rcu, struct allowedips_node, rcu) };
47 unsigned int len = 1;
48
49 while (len > 0 && (node = stack[--len])) {
50 push_rcu(stack, node->bit[0], &len);
51 push_rcu(stack, node->bit[1], &len);
52 kfree(node);
53 }
54}
55
56static void root_remove_peer_lists(struct allowedips_node *root)
57{
58 struct allowedips_node *node, *stack[128] = { root };
59 unsigned int len = 1;
60
61 while (len > 0 && (node = stack[--len])) {
62 push_rcu(stack, node->bit[0], &len);
63 push_rcu(stack, node->bit[1], &len);
64 if (rcu_access_pointer(node->peer))
65 list_del(&node->peer_list);
66 }
67}
68
69static void walk_remove_by_peer(struct allowedips_node __rcu **top,
70 struct wg_peer *peer, struct mutex *lock)
71{
72#define REF(p) rcu_access_pointer(p)
73#define DEREF(p) rcu_dereference_protected(*(p), lockdep_is_held(lock))
74#define PUSH(p) ({ \
75 WARN_ON(IS_ENABLED(DEBUG) && len >= 128); \
76 stack[len++] = p; \
77 })
78
79 struct allowedips_node __rcu **stack[128], **nptr;
80 struct allowedips_node *node, *prev;
81 unsigned int len;
82
83 if (unlikely(!peer || !REF(*top)))
84 return;
85
86 for (prev = NULL, len = 0, PUSH(top); len > 0; prev = node) {
87 nptr = stack[len - 1];
88 node = DEREF(nptr);
89 if (!node) {
90 --len;
91 continue;
92 }
93 if (!prev || REF(prev->bit[0]) == node ||
94 REF(prev->bit[1]) == node) {
95 if (REF(node->bit[0]))
96 PUSH(&node->bit[0]);
97 else if (REF(node->bit[1]))
98 PUSH(&node->bit[1]);
99 } else if (REF(node->bit[0]) == prev) {
100 if (REF(node->bit[1]))
101 PUSH(&node->bit[1]);
102 } else {
103 if (rcu_dereference_protected(node->peer,
104 lockdep_is_held(lock)) == peer) {
105 RCU_INIT_POINTER(node->peer, NULL);
106 list_del_init(&node->peer_list);
107 if (!node->bit[0] || !node->bit[1]) {
108 rcu_assign_pointer(*nptr, DEREF(
109 &node->bit[!REF(node->bit[0])]));
110 kfree_rcu(node, rcu);
111 node = DEREF(nptr);
112 }
113 }
114 --len;
115 }
116 }
117
118#undef REF
119#undef DEREF
120#undef PUSH
121}
122
123static unsigned int fls128(u64 a, u64 b)
124{
125 return a ? fls64(a) + 64U : fls64(b);
126}
127
128static u8 common_bits(const struct allowedips_node *node, const u8 *key,
129 u8 bits)
130{
131 if (bits == 32)
132 return 32U - fls(*(const u32 *)node->bits ^ *(const u32 *)key);
133 else if (bits == 128)
134 return 128U - fls128(
135 *(const u64 *)&node->bits[0] ^ *(const u64 *)&key[0],
136 *(const u64 *)&node->bits[8] ^ *(const u64 *)&key[8]);
137 return 0;
138}
139
140static bool prefix_matches(const struct allowedips_node *node, const u8 *key,
141 u8 bits)
142{
143 /* This could be much faster if it actually just compared the common
144 * bits properly, by precomputing a mask bswap(~0 << (32 - cidr)), and
145 * the rest, but it turns out that common_bits is already super fast on
146 * modern processors, even taking into account the unfortunate bswap.
147 * So, we just inline it like this instead.
148 */
149 return common_bits(node, key, bits) >= node->cidr;
150}
151
152static struct allowedips_node *find_node(struct allowedips_node *trie, u8 bits,
153 const u8 *key)
154{
155 struct allowedips_node *node = trie, *found = NULL;
156
157 while (node && prefix_matches(node, key, bits)) {
158 if (rcu_access_pointer(node->peer))
159 found = node;
160 if (node->cidr == bits)
161 break;
162 node = rcu_dereference_bh(CHOOSE_NODE(node, key));
163 }
164 return found;
165}
166
167/* Returns a strong reference to a peer */
168static struct wg_peer *lookup(struct allowedips_node __rcu *root, u8 bits,
169 const void *be_ip)
170{
171 /* Aligned so it can be passed to fls/fls64 */
172 u8 ip[16] __aligned(__alignof(u64));
173 struct allowedips_node *node;
174 struct wg_peer *peer = NULL;
175
176 swap_endian(ip, be_ip, bits);
177
178 rcu_read_lock_bh();
179retry:
180 node = find_node(rcu_dereference_bh(root), bits, ip);
181 if (node) {
182 peer = wg_peer_get_maybe_zero(rcu_dereference_bh(node->peer));
183 if (!peer)
184 goto retry;
185 }
186 rcu_read_unlock_bh();
187 return peer;
188}
189
190static bool node_placement(struct allowedips_node __rcu *trie, const u8 *key,
191 u8 cidr, u8 bits, struct allowedips_node **rnode,
192 struct mutex *lock)
193{
194 struct allowedips_node *node = rcu_dereference_protected(trie,
195 lockdep_is_held(lock));
196 struct allowedips_node *parent = NULL;
197 bool exact = false;
198
199 while (node && node->cidr <= cidr && prefix_matches(node, key, bits)) {
200 parent = node;
201 if (parent->cidr == cidr) {
202 exact = true;
203 break;
204 }
205 node = rcu_dereference_protected(CHOOSE_NODE(parent, key),
206 lockdep_is_held(lock));
207 }
208 *rnode = parent;
209 return exact;
210}
211
212static int add(struct allowedips_node __rcu **trie, u8 bits, const u8 *key,
213 u8 cidr, struct wg_peer *peer, struct mutex *lock)
214{
215 struct allowedips_node *node, *parent, *down, *newnode;
216
217 if (unlikely(cidr > bits || !peer))
218 return -EINVAL;
219
220 if (!rcu_access_pointer(*trie)) {
221 node = kzalloc(sizeof(*node), GFP_KERNEL);
222 if (unlikely(!node))
223 return -ENOMEM;
224 RCU_INIT_POINTER(node->peer, peer);
225 list_add_tail(&node->peer_list, &peer->allowedips_list);
226 copy_and_assign_cidr(node, key, cidr, bits);
227 rcu_assign_pointer(*trie, node);
228 return 0;
229 }
230 if (node_placement(*trie, key, cidr, bits, &node, lock)) {
231 rcu_assign_pointer(node->peer, peer);
232 list_move_tail(&node->peer_list, &peer->allowedips_list);
233 return 0;
234 }
235
236 newnode = kzalloc(sizeof(*newnode), GFP_KERNEL);
237 if (unlikely(!newnode))
238 return -ENOMEM;
239 RCU_INIT_POINTER(newnode->peer, peer);
240 list_add_tail(&newnode->peer_list, &peer->allowedips_list);
241 copy_and_assign_cidr(newnode, key, cidr, bits);
242
243 if (!node) {
244 down = rcu_dereference_protected(*trie, lockdep_is_held(lock));
245 } else {
246 down = rcu_dereference_protected(CHOOSE_NODE(node, key),
247 lockdep_is_held(lock));
248 if (!down) {
249 rcu_assign_pointer(CHOOSE_NODE(node, key), newnode);
250 return 0;
251 }
252 }
253 cidr = min(cidr, common_bits(down, key, bits));
254 parent = node;
255
256 if (newnode->cidr == cidr) {
257 rcu_assign_pointer(CHOOSE_NODE(newnode, down->bits), down);
258 if (!parent)
259 rcu_assign_pointer(*trie, newnode);
260 else
261 rcu_assign_pointer(CHOOSE_NODE(parent, newnode->bits),
262 newnode);
263 } else {
264 node = kzalloc(sizeof(*node), GFP_KERNEL);
265 if (unlikely(!node)) {
266 list_del(&newnode->peer_list);
267 kfree(newnode);
268 return -ENOMEM;
269 }
270 INIT_LIST_HEAD(&node->peer_list);
271 copy_and_assign_cidr(node, newnode->bits, cidr, bits);
272
273 rcu_assign_pointer(CHOOSE_NODE(node, down->bits), down);
274 rcu_assign_pointer(CHOOSE_NODE(node, newnode->bits), newnode);
275 if (!parent)
276 rcu_assign_pointer(*trie, node);
277 else
278 rcu_assign_pointer(CHOOSE_NODE(parent, node->bits),
279 node);
280 }
281 return 0;
282}
283
284void wg_allowedips_init(struct allowedips *table)
285{
286 table->root4 = table->root6 = NULL;
287 table->seq = 1;
288}
289
290void wg_allowedips_free(struct allowedips *table, struct mutex *lock)
291{
292 struct allowedips_node __rcu *old4 = table->root4, *old6 = table->root6;
293
294 ++table->seq;
295 RCU_INIT_POINTER(table->root4, NULL);
296 RCU_INIT_POINTER(table->root6, NULL);
297 if (rcu_access_pointer(old4)) {
298 struct allowedips_node *node = rcu_dereference_protected(old4,
299 lockdep_is_held(lock));
300
301 root_remove_peer_lists(node);
302 call_rcu(&node->rcu, root_free_rcu);
303 }
304 if (rcu_access_pointer(old6)) {
305 struct allowedips_node *node = rcu_dereference_protected(old6,
306 lockdep_is_held(lock));
307
308 root_remove_peer_lists(node);
309 call_rcu(&node->rcu, root_free_rcu);
310 }
311}
312
313int wg_allowedips_insert_v4(struct allowedips *table, const struct in_addr *ip,
314 u8 cidr, struct wg_peer *peer, struct mutex *lock)
315{
316 /* Aligned so it can be passed to fls */
317 u8 key[4] __aligned(__alignof(u32));
318
319 ++table->seq;
320 swap_endian(key, (const u8 *)ip, 32);
321 return add(&table->root4, 32, key, cidr, peer, lock);
322}
323
324int wg_allowedips_insert_v6(struct allowedips *table, const struct in6_addr *ip,
325 u8 cidr, struct wg_peer *peer, struct mutex *lock)
326{
327 /* Aligned so it can be passed to fls64 */
328 u8 key[16] __aligned(__alignof(u64));
329
330 ++table->seq;
331 swap_endian(key, (const u8 *)ip, 128);
332 return add(&table->root6, 128, key, cidr, peer, lock);
333}
334
335void wg_allowedips_remove_by_peer(struct allowedips *table,
336 struct wg_peer *peer, struct mutex *lock)
337{
338 ++table->seq;
339 walk_remove_by_peer(&table->root4, peer, lock);
340 walk_remove_by_peer(&table->root6, peer, lock);
341}
342
343int wg_allowedips_read_node(struct allowedips_node *node, u8 ip[16], u8 *cidr)
344{
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);
350
351 *cidr = node->cidr;
352 return node->bitlen == 32 ? AF_INET : AF_INET6;
353}
354
355/* Returns a strong reference to a peer */
356struct wg_peer *wg_allowedips_lookup_dst(struct allowedips *table,
357 struct sk_buff *skb)
358{
359 if (skb->protocol == htons(ETH_P_IP))
360 return lookup(table->root4, 32, &ip_hdr(skb)->daddr);
361 else if (skb->protocol == htons(ETH_P_IPV6))
362 return lookup(table->root6, 128, &ipv6_hdr(skb)->daddr);
363 return NULL;
364}
365
366/* Returns a strong reference to a peer */
367struct wg_peer *wg_allowedips_lookup_src(struct allowedips *table,
368 struct sk_buff *skb)
369{
370 if (skb->protocol == htons(ETH_P_IP))
371 return lookup(table->root4, 32, &ip_hdr(skb)->saddr);
372 else if (skb->protocol == htons(ETH_P_IPV6))
373 return lookup(table->root6, 128, &ipv6_hdr(skb)->saddr);
374 return NULL;
375}
376
377#include "selftest/allowedips.c"