1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * Randomized tests for eBPF longest-prefix-match maps |
4 | * |
5 | * This program runs randomized tests against the lpm-bpf-map. It implements a |
6 | * "Trivial Longest Prefix Match" (tlpm) based on simple, linear, singly linked |
7 | * lists. The implementation should be pretty straightforward. |
8 | * |
9 | * Based on tlpm, this inserts randomized data into bpf-lpm-maps and verifies |
10 | * the trie-based bpf-map implementation behaves the same way as tlpm. |
11 | */ |
12 | |
13 | #include <assert.h> |
14 | #include <errno.h> |
15 | #include <inttypes.h> |
16 | #include <linux/bpf.h> |
17 | #include <pthread.h> |
18 | #include <stdio.h> |
19 | #include <stdlib.h> |
20 | #include <string.h> |
21 | #include <time.h> |
22 | #include <unistd.h> |
23 | #include <arpa/inet.h> |
24 | #include <sys/time.h> |
25 | |
26 | #include <bpf/bpf.h> |
27 | |
28 | #include "bpf_util.h" |
29 | |
30 | struct tlpm_node { |
31 | struct tlpm_node *next; |
32 | size_t n_bits; |
33 | uint8_t key[]; |
34 | }; |
35 | |
36 | static struct tlpm_node *tlpm_match(struct tlpm_node *list, |
37 | const uint8_t *key, |
38 | size_t n_bits); |
39 | |
40 | static struct tlpm_node *tlpm_add(struct tlpm_node *list, |
41 | const uint8_t *key, |
42 | size_t n_bits) |
43 | { |
44 | struct tlpm_node *node; |
45 | size_t n; |
46 | |
47 | n = (n_bits + 7) / 8; |
48 | |
49 | /* 'overwrite' an equivalent entry if one already exists */ |
50 | node = tlpm_match(list, key, n_bits); |
51 | if (node && node->n_bits == n_bits) { |
52 | memcpy(node->key, key, n); |
53 | return list; |
54 | } |
55 | |
56 | /* add new entry with @key/@n_bits to @list and return new head */ |
57 | |
58 | node = malloc(sizeof(*node) + n); |
59 | assert(node); |
60 | |
61 | node->next = list; |
62 | node->n_bits = n_bits; |
63 | memcpy(node->key, key, n); |
64 | |
65 | return node; |
66 | } |
67 | |
68 | static void tlpm_clear(struct tlpm_node *list) |
69 | { |
70 | struct tlpm_node *node; |
71 | |
72 | /* free all entries in @list */ |
73 | |
74 | while ((node = list)) { |
75 | list = list->next; |
76 | free(node); |
77 | } |
78 | } |
79 | |
80 | static struct tlpm_node *tlpm_match(struct tlpm_node *list, |
81 | const uint8_t *key, |
82 | size_t n_bits) |
83 | { |
84 | struct tlpm_node *best = NULL; |
85 | size_t i; |
86 | |
87 | /* Perform longest prefix-match on @key/@n_bits. That is, iterate all |
88 | * entries and match each prefix against @key. Remember the "best" |
89 | * entry we find (i.e., the longest prefix that matches) and return it |
90 | * to the caller when done. |
91 | */ |
92 | |
93 | for ( ; list; list = list->next) { |
94 | for (i = 0; i < n_bits && i < list->n_bits; ++i) { |
95 | if ((key[i / 8] & (1 << (7 - i % 8))) != |
96 | (list->key[i / 8] & (1 << (7 - i % 8)))) |
97 | break; |
98 | } |
99 | |
100 | if (i >= list->n_bits) { |
101 | if (!best || i > best->n_bits) |
102 | best = list; |
103 | } |
104 | } |
105 | |
106 | return best; |
107 | } |
108 | |
109 | static struct tlpm_node *tlpm_delete(struct tlpm_node *list, |
110 | const uint8_t *key, |
111 | size_t n_bits) |
112 | { |
113 | struct tlpm_node *best = tlpm_match(list, key, n_bits); |
114 | struct tlpm_node *node; |
115 | |
116 | if (!best || best->n_bits != n_bits) |
117 | return list; |
118 | |
119 | if (best == list) { |
120 | node = best->next; |
121 | free(best); |
122 | return node; |
123 | } |
124 | |
125 | for (node = list; node; node = node->next) { |
126 | if (node->next == best) { |
127 | node->next = best->next; |
128 | free(best); |
129 | return list; |
130 | } |
131 | } |
132 | /* should never get here */ |
133 | assert(0); |
134 | return list; |
135 | } |
136 | |
137 | static void test_lpm_basic(void) |
138 | { |
139 | struct tlpm_node *list = NULL, *t1, *t2; |
140 | |
141 | /* very basic, static tests to verify tlpm works as expected */ |
142 | |
143 | assert(!tlpm_match(list, key: (uint8_t[]){ 0xff }, n_bits: 8)); |
144 | |
145 | t1 = list = tlpm_add(list, key: (uint8_t[]){ 0xff }, n_bits: 8); |
146 | assert(t1 == tlpm_match(list, key: (uint8_t[]){ 0xff }, n_bits: 8)); |
147 | assert(t1 == tlpm_match(list, key: (uint8_t[]){ 0xff, 0xff }, n_bits: 16)); |
148 | assert(t1 == tlpm_match(list, key: (uint8_t[]){ 0xff, 0x00 }, n_bits: 16)); |
149 | assert(!tlpm_match(list, key: (uint8_t[]){ 0x7f }, n_bits: 8)); |
150 | assert(!tlpm_match(list, key: (uint8_t[]){ 0xfe }, n_bits: 8)); |
151 | assert(!tlpm_match(list, key: (uint8_t[]){ 0xff }, n_bits: 7)); |
152 | |
153 | t2 = list = tlpm_add(list, key: (uint8_t[]){ 0xff, 0xff }, n_bits: 16); |
154 | assert(t1 == tlpm_match(list, key: (uint8_t[]){ 0xff }, n_bits: 8)); |
155 | assert(t2 == tlpm_match(list, key: (uint8_t[]){ 0xff, 0xff }, n_bits: 16)); |
156 | assert(t1 == tlpm_match(list, key: (uint8_t[]){ 0xff, 0xff }, n_bits: 15)); |
157 | assert(!tlpm_match(list, key: (uint8_t[]){ 0x7f, 0xff }, n_bits: 16)); |
158 | |
159 | list = tlpm_delete(list, key: (uint8_t[]){ 0xff, 0xff }, n_bits: 16); |
160 | assert(t1 == tlpm_match(list, key: (uint8_t[]){ 0xff }, n_bits: 8)); |
161 | assert(t1 == tlpm_match(list, key: (uint8_t[]){ 0xff, 0xff }, n_bits: 16)); |
162 | |
163 | list = tlpm_delete(list, key: (uint8_t[]){ 0xff }, n_bits: 8); |
164 | assert(!tlpm_match(list, key: (uint8_t[]){ 0xff }, n_bits: 8)); |
165 | |
166 | tlpm_clear(list); |
167 | } |
168 | |
169 | static void test_lpm_order(void) |
170 | { |
171 | struct tlpm_node *t1, *t2, *l1 = NULL, *l2 = NULL; |
172 | size_t i, j; |
173 | |
174 | /* Verify the tlpm implementation works correctly regardless of the |
175 | * order of entries. Insert a random set of entries into @l1, and copy |
176 | * the same data in reverse order into @l2. Then verify a lookup of |
177 | * random keys will yield the same result in both sets. |
178 | */ |
179 | |
180 | for (i = 0; i < (1 << 12); ++i) |
181 | l1 = tlpm_add(list: l1, key: (uint8_t[]){ |
182 | rand() % 0xff, |
183 | rand() % 0xff, |
184 | }, n_bits: rand() % 16 + 1); |
185 | |
186 | for (t1 = l1; t1; t1 = t1->next) |
187 | l2 = tlpm_add(list: l2, key: t1->key, n_bits: t1->n_bits); |
188 | |
189 | for (i = 0; i < (1 << 8); ++i) { |
190 | uint8_t key[] = { rand() % 0xff, rand() % 0xff }; |
191 | |
192 | t1 = tlpm_match(list: l1, key, n_bits: 16); |
193 | t2 = tlpm_match(list: l2, key, n_bits: 16); |
194 | |
195 | assert(!t1 == !t2); |
196 | if (t1) { |
197 | assert(t1->n_bits == t2->n_bits); |
198 | for (j = 0; j < t1->n_bits; ++j) |
199 | assert((t1->key[j / 8] & (1 << (7 - j % 8))) == |
200 | (t2->key[j / 8] & (1 << (7 - j % 8)))); |
201 | } |
202 | } |
203 | |
204 | tlpm_clear(list: l1); |
205 | tlpm_clear(list: l2); |
206 | } |
207 | |
208 | static void test_lpm_map(int keysize) |
209 | { |
210 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
211 | volatile size_t n_matches, n_matches_after_delete; |
212 | size_t i, j, n_nodes, n_lookups; |
213 | struct tlpm_node *t, *list = NULL; |
214 | struct bpf_lpm_trie_key_u8 *key; |
215 | uint8_t *data, *value; |
216 | int r, map; |
217 | |
218 | /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of |
219 | * prefixes and insert it into both tlpm and bpf-lpm. Then run some |
220 | * randomized lookups and verify both maps return the same result. |
221 | */ |
222 | |
223 | n_matches = 0; |
224 | n_matches_after_delete = 0; |
225 | n_nodes = 1 << 8; |
226 | n_lookups = 1 << 16; |
227 | |
228 | data = alloca(keysize); |
229 | memset(data, 0, keysize); |
230 | |
231 | value = alloca(keysize + 1); |
232 | memset(value, 0, keysize + 1); |
233 | |
234 | key = alloca(sizeof(*key) + keysize); |
235 | memset(key, 0, sizeof(*key) + keysize); |
236 | |
237 | map = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
238 | sizeof(*key) + keysize, |
239 | keysize + 1, |
240 | 4096, |
241 | &opts); |
242 | assert(map >= 0); |
243 | |
244 | for (i = 0; i < n_nodes; ++i) { |
245 | for (j = 0; j < keysize; ++j) |
246 | value[j] = rand() & 0xff; |
247 | value[keysize] = rand() % (8 * keysize + 1); |
248 | |
249 | list = tlpm_add(list, key: value, n_bits: value[keysize]); |
250 | |
251 | key->prefixlen = value[keysize]; |
252 | memcpy(key->data, value, keysize); |
253 | r = bpf_map_update_elem(map, key, value, 0); |
254 | assert(!r); |
255 | } |
256 | |
257 | for (i = 0; i < n_lookups; ++i) { |
258 | for (j = 0; j < keysize; ++j) |
259 | data[j] = rand() & 0xff; |
260 | |
261 | t = tlpm_match(list, key: data, n_bits: 8 * keysize); |
262 | |
263 | key->prefixlen = 8 * keysize; |
264 | memcpy(key->data, data, keysize); |
265 | r = bpf_map_lookup_elem(map, key, value); |
266 | assert(!r || errno == ENOENT); |
267 | assert(!t == !!r); |
268 | |
269 | if (t) { |
270 | ++n_matches; |
271 | assert(t->n_bits == value[keysize]); |
272 | for (j = 0; j < t->n_bits; ++j) |
273 | assert((t->key[j / 8] & (1 << (7 - j % 8))) == |
274 | (value[j / 8] & (1 << (7 - j % 8)))); |
275 | } |
276 | } |
277 | |
278 | /* Remove the first half of the elements in the tlpm and the |
279 | * corresponding nodes from the bpf-lpm. Then run the same |
280 | * large number of random lookups in both and make sure they match. |
281 | * Note: we need to count the number of nodes actually inserted |
282 | * since there may have been duplicates. |
283 | */ |
284 | for (i = 0, t = list; t; i++, t = t->next) |
285 | ; |
286 | for (j = 0; j < i / 2; ++j) { |
287 | key->prefixlen = list->n_bits; |
288 | memcpy(key->data, list->key, keysize); |
289 | r = bpf_map_delete_elem(map, key); |
290 | assert(!r); |
291 | list = tlpm_delete(list, key: list->key, n_bits: list->n_bits); |
292 | assert(list); |
293 | } |
294 | for (i = 0; i < n_lookups; ++i) { |
295 | for (j = 0; j < keysize; ++j) |
296 | data[j] = rand() & 0xff; |
297 | |
298 | t = tlpm_match(list, key: data, n_bits: 8 * keysize); |
299 | |
300 | key->prefixlen = 8 * keysize; |
301 | memcpy(key->data, data, keysize); |
302 | r = bpf_map_lookup_elem(map, key, value); |
303 | assert(!r || errno == ENOENT); |
304 | assert(!t == !!r); |
305 | |
306 | if (t) { |
307 | ++n_matches_after_delete; |
308 | assert(t->n_bits == value[keysize]); |
309 | for (j = 0; j < t->n_bits; ++j) |
310 | assert((t->key[j / 8] & (1 << (7 - j % 8))) == |
311 | (value[j / 8] & (1 << (7 - j % 8)))); |
312 | } |
313 | } |
314 | |
315 | close(map); |
316 | tlpm_clear(list); |
317 | |
318 | /* With 255 random nodes in the map, we are pretty likely to match |
319 | * something on every lookup. For statistics, use this: |
320 | * |
321 | * printf(" nodes: %zu\n" |
322 | * " lookups: %zu\n" |
323 | * " matches: %zu\n" |
324 | * "matches(delete): %zu\n", |
325 | * n_nodes, n_lookups, n_matches, n_matches_after_delete); |
326 | */ |
327 | } |
328 | |
329 | /* Test the implementation with some 'real world' examples */ |
330 | |
331 | static void test_lpm_ipaddr(void) |
332 | { |
333 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
334 | struct bpf_lpm_trie_key_u8 *key_ipv4; |
335 | struct bpf_lpm_trie_key_u8 *key_ipv6; |
336 | size_t key_size_ipv4; |
337 | size_t key_size_ipv6; |
338 | int map_fd_ipv4; |
339 | int map_fd_ipv6; |
340 | __u64 value; |
341 | |
342 | key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32); |
343 | key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4; |
344 | key_ipv4 = alloca(key_size_ipv4); |
345 | key_ipv6 = alloca(key_size_ipv6); |
346 | |
347 | map_fd_ipv4 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
348 | key_size_ipv4, sizeof(value), |
349 | 100, &opts); |
350 | assert(map_fd_ipv4 >= 0); |
351 | |
352 | map_fd_ipv6 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
353 | key_size_ipv6, sizeof(value), |
354 | 100, &opts); |
355 | assert(map_fd_ipv6 >= 0); |
356 | |
357 | /* Fill data some IPv4 and IPv6 address ranges */ |
358 | value = 1; |
359 | key_ipv4->prefixlen = 16; |
360 | inet_pton(AF_INET, "192.168.0.0" , key_ipv4->data); |
361 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
362 | |
363 | value = 2; |
364 | key_ipv4->prefixlen = 24; |
365 | inet_pton(AF_INET, "192.168.0.0" , key_ipv4->data); |
366 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
367 | |
368 | value = 3; |
369 | key_ipv4->prefixlen = 24; |
370 | inet_pton(AF_INET, "192.168.128.0" , key_ipv4->data); |
371 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
372 | |
373 | value = 5; |
374 | key_ipv4->prefixlen = 24; |
375 | inet_pton(AF_INET, "192.168.1.0" , key_ipv4->data); |
376 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
377 | |
378 | value = 4; |
379 | key_ipv4->prefixlen = 23; |
380 | inet_pton(AF_INET, "192.168.0.0" , key_ipv4->data); |
381 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
382 | |
383 | value = 0xdeadbeef; |
384 | key_ipv6->prefixlen = 64; |
385 | inet_pton(AF_INET6, "2a00:1450:4001:814::200e" , key_ipv6->data); |
386 | assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0); |
387 | |
388 | /* Set tprefixlen to maximum for lookups */ |
389 | key_ipv4->prefixlen = 32; |
390 | key_ipv6->prefixlen = 128; |
391 | |
392 | /* Test some lookups that should come back with a value */ |
393 | inet_pton(AF_INET, "192.168.128.23" , key_ipv4->data); |
394 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); |
395 | assert(value == 3); |
396 | |
397 | inet_pton(AF_INET, "192.168.0.1" , key_ipv4->data); |
398 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); |
399 | assert(value == 2); |
400 | |
401 | inet_pton(AF_INET6, "2a00:1450:4001:814::" , key_ipv6->data); |
402 | assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); |
403 | assert(value == 0xdeadbeef); |
404 | |
405 | inet_pton(AF_INET6, "2a00:1450:4001:814::1" , key_ipv6->data); |
406 | assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); |
407 | assert(value == 0xdeadbeef); |
408 | |
409 | /* Test some lookups that should not match any entry */ |
410 | inet_pton(AF_INET, "10.0.0.1" , key_ipv4->data); |
411 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT); |
412 | |
413 | inet_pton(AF_INET, "11.11.11.11" , key_ipv4->data); |
414 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT); |
415 | |
416 | inet_pton(AF_INET6, "2a00:ffff::" , key_ipv6->data); |
417 | assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -ENOENT); |
418 | |
419 | close(map_fd_ipv4); |
420 | close(map_fd_ipv6); |
421 | } |
422 | |
423 | static void test_lpm_delete(void) |
424 | { |
425 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
426 | struct bpf_lpm_trie_key_u8 *key; |
427 | size_t key_size; |
428 | int map_fd; |
429 | __u64 value; |
430 | |
431 | key_size = sizeof(*key) + sizeof(__u32); |
432 | key = alloca(key_size); |
433 | |
434 | map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
435 | key_size, sizeof(value), |
436 | 100, &opts); |
437 | assert(map_fd >= 0); |
438 | |
439 | /* Add nodes: |
440 | * 192.168.0.0/16 (1) |
441 | * 192.168.0.0/24 (2) |
442 | * 192.168.128.0/24 (3) |
443 | * 192.168.1.0/24 (4) |
444 | * |
445 | * (1) |
446 | * / \ |
447 | * (IM) (3) |
448 | * / \ |
449 | * (2) (4) |
450 | */ |
451 | value = 1; |
452 | key->prefixlen = 16; |
453 | inet_pton(AF_INET, "192.168.0.0" , key->data); |
454 | assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); |
455 | |
456 | value = 2; |
457 | key->prefixlen = 24; |
458 | inet_pton(AF_INET, "192.168.0.0" , key->data); |
459 | assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); |
460 | |
461 | value = 3; |
462 | key->prefixlen = 24; |
463 | inet_pton(AF_INET, "192.168.128.0" , key->data); |
464 | assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); |
465 | |
466 | value = 4; |
467 | key->prefixlen = 24; |
468 | inet_pton(AF_INET, "192.168.1.0" , key->data); |
469 | assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); |
470 | |
471 | /* remove non-existent node */ |
472 | key->prefixlen = 32; |
473 | inet_pton(AF_INET, "10.0.0.1" , key->data); |
474 | assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT); |
475 | |
476 | key->prefixlen = 30; // unused prefix so far |
477 | inet_pton(AF_INET, "192.255.0.0" , key->data); |
478 | assert(bpf_map_delete_elem(map_fd, key) == -ENOENT); |
479 | |
480 | key->prefixlen = 16; // same prefix as the root node |
481 | inet_pton(AF_INET, "192.255.0.0" , key->data); |
482 | assert(bpf_map_delete_elem(map_fd, key) == -ENOENT); |
483 | |
484 | /* assert initial lookup */ |
485 | key->prefixlen = 32; |
486 | inet_pton(AF_INET, "192.168.0.1" , key->data); |
487 | assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); |
488 | assert(value == 2); |
489 | |
490 | /* remove leaf node */ |
491 | key->prefixlen = 24; |
492 | inet_pton(AF_INET, "192.168.0.0" , key->data); |
493 | assert(bpf_map_delete_elem(map_fd, key) == 0); |
494 | |
495 | key->prefixlen = 32; |
496 | inet_pton(AF_INET, "192.168.0.1" , key->data); |
497 | assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); |
498 | assert(value == 1); |
499 | |
500 | /* remove leaf (and intermediary) node */ |
501 | key->prefixlen = 24; |
502 | inet_pton(AF_INET, "192.168.1.0" , key->data); |
503 | assert(bpf_map_delete_elem(map_fd, key) == 0); |
504 | |
505 | key->prefixlen = 32; |
506 | inet_pton(AF_INET, "192.168.1.1" , key->data); |
507 | assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); |
508 | assert(value == 1); |
509 | |
510 | /* remove root node */ |
511 | key->prefixlen = 16; |
512 | inet_pton(AF_INET, "192.168.0.0" , key->data); |
513 | assert(bpf_map_delete_elem(map_fd, key) == 0); |
514 | |
515 | key->prefixlen = 32; |
516 | inet_pton(AF_INET, "192.168.128.1" , key->data); |
517 | assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); |
518 | assert(value == 3); |
519 | |
520 | /* remove last node */ |
521 | key->prefixlen = 24; |
522 | inet_pton(AF_INET, "192.168.128.0" , key->data); |
523 | assert(bpf_map_delete_elem(map_fd, key) == 0); |
524 | |
525 | key->prefixlen = 32; |
526 | inet_pton(AF_INET, "192.168.128.1" , key->data); |
527 | assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT); |
528 | |
529 | close(map_fd); |
530 | } |
531 | |
532 | static void test_lpm_get_next_key(void) |
533 | { |
534 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
535 | struct bpf_lpm_trie_key_u8 *key_p, *next_key_p; |
536 | size_t key_size; |
537 | __u32 value = 0; |
538 | int map_fd; |
539 | |
540 | key_size = sizeof(*key_p) + sizeof(__u32); |
541 | key_p = alloca(key_size); |
542 | next_key_p = alloca(key_size); |
543 | |
544 | map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, sizeof(value), 100, &opts); |
545 | assert(map_fd >= 0); |
546 | |
547 | /* empty tree. get_next_key should return ENOENT */ |
548 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -ENOENT); |
549 | |
550 | /* get and verify the first key, get the second one should fail. */ |
551 | key_p->prefixlen = 16; |
552 | inet_pton(AF_INET, "192.168.0.0" , key_p->data); |
553 | assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0); |
554 | |
555 | memset(key_p, 0, key_size); |
556 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0); |
557 | assert(key_p->prefixlen == 16 && key_p->data[0] == 192 && |
558 | key_p->data[1] == 168); |
559 | |
560 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
561 | |
562 | /* no exact matching key should get the first one in post order. */ |
563 | key_p->prefixlen = 8; |
564 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0); |
565 | assert(key_p->prefixlen == 16 && key_p->data[0] == 192 && |
566 | key_p->data[1] == 168); |
567 | |
568 | /* add one more element (total two) */ |
569 | key_p->prefixlen = 24; |
570 | inet_pton(AF_INET, "192.168.128.0" , key_p->data); |
571 | assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0); |
572 | |
573 | memset(key_p, 0, key_size); |
574 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0); |
575 | assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && |
576 | key_p->data[1] == 168 && key_p->data[2] == 128); |
577 | |
578 | memset(next_key_p, 0, key_size); |
579 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
580 | assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && |
581 | next_key_p->data[1] == 168); |
582 | |
583 | memcpy(key_p, next_key_p, key_size); |
584 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
585 | |
586 | /* Add one more element (total three) */ |
587 | key_p->prefixlen = 24; |
588 | inet_pton(AF_INET, "192.168.0.0" , key_p->data); |
589 | assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0); |
590 | |
591 | memset(key_p, 0, key_size); |
592 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0); |
593 | assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && |
594 | key_p->data[1] == 168 && key_p->data[2] == 0); |
595 | |
596 | memset(next_key_p, 0, key_size); |
597 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
598 | assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && |
599 | next_key_p->data[1] == 168 && next_key_p->data[2] == 128); |
600 | |
601 | memcpy(key_p, next_key_p, key_size); |
602 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
603 | assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && |
604 | next_key_p->data[1] == 168); |
605 | |
606 | memcpy(key_p, next_key_p, key_size); |
607 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
608 | |
609 | /* Add one more element (total four) */ |
610 | key_p->prefixlen = 24; |
611 | inet_pton(AF_INET, "192.168.1.0" , key_p->data); |
612 | assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0); |
613 | |
614 | memset(key_p, 0, key_size); |
615 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0); |
616 | assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && |
617 | key_p->data[1] == 168 && key_p->data[2] == 0); |
618 | |
619 | memset(next_key_p, 0, key_size); |
620 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
621 | assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && |
622 | next_key_p->data[1] == 168 && next_key_p->data[2] == 1); |
623 | |
624 | memcpy(key_p, next_key_p, key_size); |
625 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
626 | assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && |
627 | next_key_p->data[1] == 168 && next_key_p->data[2] == 128); |
628 | |
629 | memcpy(key_p, next_key_p, key_size); |
630 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
631 | assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && |
632 | next_key_p->data[1] == 168); |
633 | |
634 | memcpy(key_p, next_key_p, key_size); |
635 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
636 | |
637 | /* Add one more element (total five) */ |
638 | key_p->prefixlen = 28; |
639 | inet_pton(AF_INET, "192.168.1.128" , key_p->data); |
640 | assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0); |
641 | |
642 | memset(key_p, 0, key_size); |
643 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0); |
644 | assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && |
645 | key_p->data[1] == 168 && key_p->data[2] == 0); |
646 | |
647 | memset(next_key_p, 0, key_size); |
648 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
649 | assert(next_key_p->prefixlen == 28 && next_key_p->data[0] == 192 && |
650 | next_key_p->data[1] == 168 && next_key_p->data[2] == 1 && |
651 | next_key_p->data[3] == 128); |
652 | |
653 | memcpy(key_p, next_key_p, key_size); |
654 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
655 | assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && |
656 | next_key_p->data[1] == 168 && next_key_p->data[2] == 1); |
657 | |
658 | memcpy(key_p, next_key_p, key_size); |
659 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
660 | assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && |
661 | next_key_p->data[1] == 168 && next_key_p->data[2] == 128); |
662 | |
663 | memcpy(key_p, next_key_p, key_size); |
664 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
665 | assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && |
666 | next_key_p->data[1] == 168); |
667 | |
668 | memcpy(key_p, next_key_p, key_size); |
669 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
670 | |
671 | /* no exact matching key should return the first one in post order */ |
672 | key_p->prefixlen = 22; |
673 | inet_pton(AF_INET, "192.168.1.0" , key_p->data); |
674 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0); |
675 | assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && |
676 | next_key_p->data[1] == 168 && next_key_p->data[2] == 0); |
677 | |
678 | close(map_fd); |
679 | } |
680 | |
681 | #define MAX_TEST_KEYS 4 |
682 | struct lpm_mt_test_info { |
683 | int cmd; /* 0: update, 1: delete, 2: lookup, 3: get_next_key */ |
684 | int iter; |
685 | int map_fd; |
686 | struct { |
687 | __u32 prefixlen; |
688 | __u32 data; |
689 | } key[MAX_TEST_KEYS]; |
690 | }; |
691 | |
692 | static void *lpm_test_command(void *arg) |
693 | { |
694 | int i, j, ret, iter, key_size; |
695 | struct lpm_mt_test_info *info = arg; |
696 | struct bpf_lpm_trie_key_u8 *key_p; |
697 | |
698 | key_size = sizeof(*key_p) + sizeof(__u32); |
699 | key_p = alloca(key_size); |
700 | for (iter = 0; iter < info->iter; iter++) |
701 | for (i = 0; i < MAX_TEST_KEYS; i++) { |
702 | /* first half of iterations in forward order, |
703 | * and second half in backward order. |
704 | */ |
705 | j = (iter < (info->iter / 2)) ? i : MAX_TEST_KEYS - i - 1; |
706 | key_p->prefixlen = info->key[j].prefixlen; |
707 | memcpy(key_p->data, &info->key[j].data, sizeof(__u32)); |
708 | if (info->cmd == 0) { |
709 | __u32 value = j; |
710 | /* update must succeed */ |
711 | assert(bpf_map_update_elem(info->map_fd, key_p, &value, 0) == 0); |
712 | } else if (info->cmd == 1) { |
713 | ret = bpf_map_delete_elem(info->map_fd, key_p); |
714 | assert(ret == 0 || errno == ENOENT); |
715 | } else if (info->cmd == 2) { |
716 | __u32 value; |
717 | ret = bpf_map_lookup_elem(info->map_fd, key_p, &value); |
718 | assert(ret == 0 || errno == ENOENT); |
719 | } else { |
720 | struct bpf_lpm_trie_key_u8 *next_key_p = alloca(key_size); |
721 | ret = bpf_map_get_next_key(info->map_fd, key_p, next_key_p); |
722 | assert(ret == 0 || errno == ENOENT || errno == ENOMEM); |
723 | } |
724 | } |
725 | |
726 | // Pass successful exit info back to the main thread |
727 | pthread_exit((void *)info); |
728 | } |
729 | |
730 | static void setup_lpm_mt_test_info(struct lpm_mt_test_info *info, int map_fd) |
731 | { |
732 | info->iter = 2000; |
733 | info->map_fd = map_fd; |
734 | info->key[0].prefixlen = 16; |
735 | inet_pton(AF_INET, "192.168.0.0" , &info->key[0].data); |
736 | info->key[1].prefixlen = 24; |
737 | inet_pton(AF_INET, "192.168.0.0" , &info->key[1].data); |
738 | info->key[2].prefixlen = 24; |
739 | inet_pton(AF_INET, "192.168.128.0" , &info->key[2].data); |
740 | info->key[3].prefixlen = 24; |
741 | inet_pton(AF_INET, "192.168.1.0" , &info->key[3].data); |
742 | } |
743 | |
744 | static void test_lpm_multi_thread(void) |
745 | { |
746 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
747 | struct lpm_mt_test_info info[4]; |
748 | size_t key_size, value_size; |
749 | pthread_t thread_id[4]; |
750 | int i, map_fd; |
751 | void *ret; |
752 | |
753 | /* create a trie */ |
754 | value_size = sizeof(__u32); |
755 | key_size = sizeof(struct bpf_lpm_trie_key_hdr) + value_size; |
756 | map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, value_size, 100, &opts); |
757 | |
758 | /* create 4 threads to test update, delete, lookup and get_next_key */ |
759 | setup_lpm_mt_test_info(info: &info[0], map_fd); |
760 | for (i = 0; i < 4; i++) { |
761 | if (i != 0) |
762 | memcpy(&info[i], &info[0], sizeof(info[i])); |
763 | info[i].cmd = i; |
764 | assert(pthread_create(&thread_id[i], NULL, &lpm_test_command, &info[i]) == 0); |
765 | } |
766 | |
767 | for (i = 0; i < 4; i++) |
768 | assert(pthread_join(thread_id[i], &ret) == 0 && ret == (void *)&info[i]); |
769 | |
770 | close(map_fd); |
771 | } |
772 | |
773 | int main(void) |
774 | { |
775 | int i; |
776 | |
777 | /* we want predictable, pseudo random tests */ |
778 | srand(0xf00ba1); |
779 | |
780 | /* Use libbpf 1.0 API mode */ |
781 | libbpf_set_strict_mode(LIBBPF_STRICT_ALL); |
782 | |
783 | test_lpm_basic(); |
784 | test_lpm_order(); |
785 | |
786 | /* Test with 8, 16, 24, 32, ... 128 bit prefix length */ |
787 | for (i = 1; i <= 16; ++i) |
788 | test_lpm_map(keysize: i); |
789 | |
790 | test_lpm_ipaddr(); |
791 | test_lpm_delete(); |
792 | test_lpm_get_next_key(); |
793 | test_lpm_multi_thread(); |
794 | |
795 | printf("test_lpm: OK\n" ); |
796 | return 0; |
797 | } |
798 | |