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 <endian.h>
24 #include <arpa/inet.h>
25 #include <sys/time.h>
26
27 #include <bpf/bpf.h>
28 #include <test_maps.h>
29
30 #include "bpf_util.h"
31
32 struct tlpm_node {
33 struct tlpm_node *next;
34 size_t n_bits;
35 uint8_t key[];
36 };
37
38 struct lpm_trie_bytes_key {
39 union {
40 struct bpf_lpm_trie_key_hdr hdr;
41 __u32 prefixlen;
42 };
43 unsigned char data[8];
44 };
45
46 struct lpm_trie_int_key {
47 union {
48 struct bpf_lpm_trie_key_hdr hdr;
49 __u32 prefixlen;
50 };
51 unsigned int data;
52 };
53
54 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
55 const uint8_t *key,
56 size_t n_bits);
57
tlpm_add(struct tlpm_node * list,const uint8_t * key,size_t n_bits)58 static struct tlpm_node *tlpm_add(struct tlpm_node *list,
59 const uint8_t *key,
60 size_t n_bits)
61 {
62 struct tlpm_node *node;
63 size_t n;
64
65 n = (n_bits + 7) / 8;
66
67 /* 'overwrite' an equivalent entry if one already exists */
68 node = tlpm_match(list, key, n_bits);
69 if (node && node->n_bits == n_bits) {
70 memcpy(node->key, key, n);
71 return list;
72 }
73
74 /* add new entry with @key/@n_bits to @list and return new head */
75
76 node = malloc(sizeof(*node) + n);
77 assert(node);
78
79 node->next = list;
80 node->n_bits = n_bits;
81 memcpy(node->key, key, n);
82
83 return node;
84 }
85
tlpm_clear(struct tlpm_node * list)86 static void tlpm_clear(struct tlpm_node *list)
87 {
88 struct tlpm_node *node;
89
90 /* free all entries in @list */
91
92 while ((node = list)) {
93 list = list->next;
94 free(node);
95 }
96 }
97
tlpm_match(struct tlpm_node * list,const uint8_t * key,size_t n_bits)98 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
99 const uint8_t *key,
100 size_t n_bits)
101 {
102 struct tlpm_node *best = NULL;
103 size_t i;
104
105 /* Perform longest prefix-match on @key/@n_bits. That is, iterate all
106 * entries and match each prefix against @key. Remember the "best"
107 * entry we find (i.e., the longest prefix that matches) and return it
108 * to the caller when done.
109 */
110
111 for ( ; list; list = list->next) {
112 for (i = 0; i < n_bits && i < list->n_bits; ++i) {
113 if ((key[i / 8] & (1 << (7 - i % 8))) !=
114 (list->key[i / 8] & (1 << (7 - i % 8))))
115 break;
116 }
117
118 if (i >= list->n_bits) {
119 if (!best || i > best->n_bits)
120 best = list;
121 }
122 }
123
124 return best;
125 }
126
tlpm_delete(struct tlpm_node * list,const uint8_t * key,size_t n_bits)127 static struct tlpm_node *tlpm_delete(struct tlpm_node *list,
128 const uint8_t *key,
129 size_t n_bits)
130 {
131 struct tlpm_node *best = tlpm_match(list, key, n_bits);
132 struct tlpm_node *node;
133
134 if (!best || best->n_bits != n_bits)
135 return list;
136
137 if (best == list) {
138 node = best->next;
139 free(best);
140 return node;
141 }
142
143 for (node = list; node; node = node->next) {
144 if (node->next == best) {
145 node->next = best->next;
146 free(best);
147 return list;
148 }
149 }
150 /* should never get here */
151 assert(0);
152 return list;
153 }
154
test_lpm_basic(void)155 static void test_lpm_basic(void)
156 {
157 struct tlpm_node *list = NULL, *t1, *t2;
158
159 /* very basic, static tests to verify tlpm works as expected */
160
161 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
162
163 t1 = list = tlpm_add(list, (uint8_t[]){ 0xff }, 8);
164 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
165 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
166 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0x00 }, 16));
167 assert(!tlpm_match(list, (uint8_t[]){ 0x7f }, 8));
168 assert(!tlpm_match(list, (uint8_t[]){ 0xfe }, 8));
169 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 7));
170
171 t2 = list = tlpm_add(list, (uint8_t[]){ 0xff, 0xff }, 16);
172 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
173 assert(t2 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
174 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15));
175 assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16));
176
177 list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16);
178 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
179 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
180
181 list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8);
182 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
183
184 tlpm_clear(list);
185 }
186
test_lpm_order(void)187 static void test_lpm_order(void)
188 {
189 struct tlpm_node *t1, *t2, *l1 = NULL, *l2 = NULL;
190 size_t i, j;
191
192 /* Verify the tlpm implementation works correctly regardless of the
193 * order of entries. Insert a random set of entries into @l1, and copy
194 * the same data in reverse order into @l2. Then verify a lookup of
195 * random keys will yield the same result in both sets.
196 */
197
198 for (i = 0; i < (1 << 12); ++i)
199 l1 = tlpm_add(l1, (uint8_t[]){
200 rand() % 0xff,
201 rand() % 0xff,
202 }, rand() % 16 + 1);
203
204 for (t1 = l1; t1; t1 = t1->next)
205 l2 = tlpm_add(l2, t1->key, t1->n_bits);
206
207 for (i = 0; i < (1 << 8); ++i) {
208 uint8_t key[] = { rand() % 0xff, rand() % 0xff };
209
210 t1 = tlpm_match(l1, key, 16);
211 t2 = tlpm_match(l2, key, 16);
212
213 assert(!t1 == !t2);
214 if (t1) {
215 assert(t1->n_bits == t2->n_bits);
216 for (j = 0; j < t1->n_bits; ++j)
217 assert((t1->key[j / 8] & (1 << (7 - j % 8))) ==
218 (t2->key[j / 8] & (1 << (7 - j % 8))));
219 }
220 }
221
222 tlpm_clear(l1);
223 tlpm_clear(l2);
224 }
225
test_lpm_map(int keysize)226 static void test_lpm_map(int keysize)
227 {
228 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
229 volatile size_t n_matches, n_matches_after_delete;
230 size_t i, j, n_nodes, n_lookups;
231 struct tlpm_node *t, *list = NULL;
232 struct bpf_lpm_trie_key_u8 *key;
233 uint8_t *data, *value;
234 int r, map;
235
236 /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of
237 * prefixes and insert it into both tlpm and bpf-lpm. Then run some
238 * randomized lookups and verify both maps return the same result.
239 */
240
241 n_matches = 0;
242 n_matches_after_delete = 0;
243 n_nodes = 1 << 8;
244 n_lookups = 1 << 9;
245
246 data = alloca(keysize);
247 memset(data, 0, keysize);
248
249 value = alloca(keysize + 1);
250 memset(value, 0, keysize + 1);
251
252 key = alloca(sizeof(*key) + keysize);
253 memset(key, 0, sizeof(*key) + keysize);
254
255 map = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
256 sizeof(*key) + keysize,
257 keysize + 1,
258 4096,
259 &opts);
260 assert(map >= 0);
261
262 for (i = 0; i < n_nodes; ++i) {
263 for (j = 0; j < keysize; ++j)
264 value[j] = rand() & 0xff;
265 value[keysize] = rand() % (8 * keysize + 1);
266
267 list = tlpm_add(list, value, value[keysize]);
268
269 key->prefixlen = value[keysize];
270 memcpy(key->data, value, keysize);
271 r = bpf_map_update_elem(map, key, value, 0);
272 assert(!r);
273 }
274
275 for (i = 0; i < n_lookups; ++i) {
276 for (j = 0; j < keysize; ++j)
277 data[j] = rand() & 0xff;
278
279 t = tlpm_match(list, data, 8 * keysize);
280
281 key->prefixlen = 8 * keysize;
282 memcpy(key->data, data, keysize);
283 r = bpf_map_lookup_elem(map, key, value);
284 assert(!r || errno == ENOENT);
285 assert(!t == !!r);
286
287 if (t) {
288 ++n_matches;
289 assert(t->n_bits == value[keysize]);
290 for (j = 0; j < t->n_bits; ++j)
291 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
292 (value[j / 8] & (1 << (7 - j % 8))));
293 }
294 }
295
296 /* Remove the first half of the elements in the tlpm and the
297 * corresponding nodes from the bpf-lpm. Then run the same
298 * large number of random lookups in both and make sure they match.
299 * Note: we need to count the number of nodes actually inserted
300 * since there may have been duplicates.
301 */
302 for (i = 0, t = list; t; i++, t = t->next)
303 ;
304 for (j = 0; j < i / 2; ++j) {
305 key->prefixlen = list->n_bits;
306 memcpy(key->data, list->key, keysize);
307 r = bpf_map_delete_elem(map, key);
308 assert(!r);
309 list = tlpm_delete(list, list->key, list->n_bits);
310 assert(list);
311 }
312 for (i = 0; i < n_lookups; ++i) {
313 for (j = 0; j < keysize; ++j)
314 data[j] = rand() & 0xff;
315
316 t = tlpm_match(list, data, 8 * keysize);
317
318 key->prefixlen = 8 * keysize;
319 memcpy(key->data, data, keysize);
320 r = bpf_map_lookup_elem(map, key, value);
321 assert(!r || errno == ENOENT);
322 assert(!t == !!r);
323
324 if (t) {
325 ++n_matches_after_delete;
326 assert(t->n_bits == value[keysize]);
327 for (j = 0; j < t->n_bits; ++j)
328 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
329 (value[j / 8] & (1 << (7 - j % 8))));
330 }
331 }
332
333 close(map);
334 tlpm_clear(list);
335
336 /* With 255 random nodes in the map, we are pretty likely to match
337 * something on every lookup. For statistics, use this:
338 *
339 * printf(" nodes: %zu\n"
340 * " lookups: %zu\n"
341 * " matches: %zu\n"
342 * "matches(delete): %zu\n",
343 * n_nodes, n_lookups, n_matches, n_matches_after_delete);
344 */
345 }
346
347 /* Test the implementation with some 'real world' examples */
348
test_lpm_ipaddr(void)349 static void test_lpm_ipaddr(void)
350 {
351 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
352 struct bpf_lpm_trie_key_u8 *key_ipv4;
353 struct bpf_lpm_trie_key_u8 *key_ipv6;
354 size_t key_size_ipv4;
355 size_t key_size_ipv6;
356 int map_fd_ipv4;
357 int map_fd_ipv6;
358 __u64 value;
359
360 key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32);
361 key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4;
362 key_ipv4 = alloca(key_size_ipv4);
363 key_ipv6 = alloca(key_size_ipv6);
364
365 map_fd_ipv4 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
366 key_size_ipv4, sizeof(value),
367 100, &opts);
368 assert(map_fd_ipv4 >= 0);
369
370 map_fd_ipv6 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
371 key_size_ipv6, sizeof(value),
372 100, &opts);
373 assert(map_fd_ipv6 >= 0);
374
375 /* Fill data some IPv4 and IPv6 address ranges */
376 value = 1;
377 key_ipv4->prefixlen = 16;
378 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
379 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
380
381 value = 2;
382 key_ipv4->prefixlen = 24;
383 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
384 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
385
386 value = 3;
387 key_ipv4->prefixlen = 24;
388 inet_pton(AF_INET, "192.168.128.0", key_ipv4->data);
389 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
390
391 value = 5;
392 key_ipv4->prefixlen = 24;
393 inet_pton(AF_INET, "192.168.1.0", key_ipv4->data);
394 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
395
396 value = 4;
397 key_ipv4->prefixlen = 23;
398 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
399 assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
400
401 value = 0xdeadbeef;
402 key_ipv6->prefixlen = 64;
403 inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data);
404 assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0);
405
406 /* Set tprefixlen to maximum for lookups */
407 key_ipv4->prefixlen = 32;
408 key_ipv6->prefixlen = 128;
409
410 /* Test some lookups that should come back with a value */
411 inet_pton(AF_INET, "192.168.128.23", key_ipv4->data);
412 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
413 assert(value == 3);
414
415 inet_pton(AF_INET, "192.168.0.1", key_ipv4->data);
416 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
417 assert(value == 2);
418
419 inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data);
420 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
421 assert(value == 0xdeadbeef);
422
423 inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data);
424 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
425 assert(value == 0xdeadbeef);
426
427 /* Test some lookups that should not match any entry */
428 inet_pton(AF_INET, "10.0.0.1", key_ipv4->data);
429 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT);
430
431 inet_pton(AF_INET, "11.11.11.11", key_ipv4->data);
432 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT);
433
434 inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data);
435 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -ENOENT);
436
437 close(map_fd_ipv4);
438 close(map_fd_ipv6);
439 }
440
test_lpm_delete(void)441 static void test_lpm_delete(void)
442 {
443 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
444 struct bpf_lpm_trie_key_u8 *key;
445 size_t key_size;
446 int map_fd;
447 __u64 value;
448
449 key_size = sizeof(*key) + sizeof(__u32);
450 key = alloca(key_size);
451
452 map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
453 key_size, sizeof(value),
454 100, &opts);
455 assert(map_fd >= 0);
456
457 /* Add nodes:
458 * 192.168.0.0/16 (1)
459 * 192.168.0.0/24 (2)
460 * 192.168.128.0/24 (3)
461 * 192.168.1.0/24 (4)
462 *
463 * (1)
464 * / \
465 * (IM) (3)
466 * / \
467 * (2) (4)
468 */
469 value = 1;
470 key->prefixlen = 16;
471 inet_pton(AF_INET, "192.168.0.0", key->data);
472 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
473
474 value = 2;
475 key->prefixlen = 24;
476 inet_pton(AF_INET, "192.168.0.0", key->data);
477 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
478
479 value = 3;
480 key->prefixlen = 24;
481 inet_pton(AF_INET, "192.168.128.0", key->data);
482 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
483
484 value = 4;
485 key->prefixlen = 24;
486 inet_pton(AF_INET, "192.168.1.0", key->data);
487 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
488
489 /* remove non-existent node */
490 key->prefixlen = 32;
491 inet_pton(AF_INET, "10.0.0.1", key->data);
492 assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT);
493
494 key->prefixlen = 30; // unused prefix so far
495 inet_pton(AF_INET, "192.255.0.0", key->data);
496 assert(bpf_map_delete_elem(map_fd, key) == -ENOENT);
497
498 key->prefixlen = 16; // same prefix as the root node
499 inet_pton(AF_INET, "192.255.0.0", key->data);
500 assert(bpf_map_delete_elem(map_fd, key) == -ENOENT);
501
502 /* assert initial lookup */
503 key->prefixlen = 32;
504 inet_pton(AF_INET, "192.168.0.1", key->data);
505 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
506 assert(value == 2);
507
508 /* remove leaf node */
509 key->prefixlen = 24;
510 inet_pton(AF_INET, "192.168.0.0", key->data);
511 assert(bpf_map_delete_elem(map_fd, key) == 0);
512
513 key->prefixlen = 32;
514 inet_pton(AF_INET, "192.168.0.1", key->data);
515 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
516 assert(value == 1);
517
518 /* remove leaf (and intermediary) node */
519 key->prefixlen = 24;
520 inet_pton(AF_INET, "192.168.1.0", key->data);
521 assert(bpf_map_delete_elem(map_fd, key) == 0);
522
523 key->prefixlen = 32;
524 inet_pton(AF_INET, "192.168.1.1", key->data);
525 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
526 assert(value == 1);
527
528 /* remove root node */
529 key->prefixlen = 16;
530 inet_pton(AF_INET, "192.168.0.0", key->data);
531 assert(bpf_map_delete_elem(map_fd, key) == 0);
532
533 key->prefixlen = 32;
534 inet_pton(AF_INET, "192.168.128.1", key->data);
535 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
536 assert(value == 3);
537
538 /* remove last node */
539 key->prefixlen = 24;
540 inet_pton(AF_INET, "192.168.128.0", key->data);
541 assert(bpf_map_delete_elem(map_fd, key) == 0);
542
543 key->prefixlen = 32;
544 inet_pton(AF_INET, "192.168.128.1", key->data);
545 assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT);
546
547 close(map_fd);
548 }
549
test_lpm_get_next_key(void)550 static void test_lpm_get_next_key(void)
551 {
552 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
553 struct bpf_lpm_trie_key_u8 *key_p, *next_key_p;
554 size_t key_size;
555 __u32 value = 0;
556 int map_fd;
557
558 key_size = sizeof(*key_p) + sizeof(__u32);
559 key_p = alloca(key_size);
560 next_key_p = alloca(key_size);
561
562 map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, sizeof(value), 100, &opts);
563 assert(map_fd >= 0);
564
565 /* empty tree. get_next_key should return ENOENT */
566 assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -ENOENT);
567
568 /* get and verify the first key, get the second one should fail. */
569 key_p->prefixlen = 16;
570 inet_pton(AF_INET, "192.168.0.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 == 16 && key_p->data[0] == 192 &&
576 key_p->data[1] == 168);
577
578 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
579
580 /* no exact matching key should get the first one in post order. */
581 key_p->prefixlen = 8;
582 assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
583 assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
584 key_p->data[1] == 168);
585
586 /* add one more element (total two) */
587 key_p->prefixlen = 24;
588 inet_pton(AF_INET, "192.168.128.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] == 128);
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 == 16 && next_key_p->data[0] == 192 &&
599 next_key_p->data[1] == 168);
600
601 memcpy(key_p, next_key_p, key_size);
602 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
603
604 /* Add one more element (total three) */
605 key_p->prefixlen = 24;
606 inet_pton(AF_INET, "192.168.0.0", key_p->data);
607 assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
608
609 memset(key_p, 0, key_size);
610 assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
611 assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
612 key_p->data[1] == 168 && key_p->data[2] == 0);
613
614 memset(next_key_p, 0, key_size);
615 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
616 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
617 next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
618
619 memcpy(key_p, next_key_p, key_size);
620 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
621 assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
622 next_key_p->data[1] == 168);
623
624 memcpy(key_p, next_key_p, key_size);
625 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
626
627 /* Add one more element (total four) */
628 key_p->prefixlen = 24;
629 inet_pton(AF_INET, "192.168.1.0", key_p->data);
630 assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
631
632 memset(key_p, 0, key_size);
633 assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
634 assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
635 key_p->data[1] == 168 && key_p->data[2] == 0);
636
637 memset(next_key_p, 0, key_size);
638 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
639 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
640 next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
641
642 memcpy(key_p, next_key_p, key_size);
643 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
644 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
645 next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
646
647 memcpy(key_p, next_key_p, key_size);
648 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
649 assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
650 next_key_p->data[1] == 168);
651
652 memcpy(key_p, next_key_p, key_size);
653 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
654
655 /* Add one more element (total five) */
656 key_p->prefixlen = 28;
657 inet_pton(AF_INET, "192.168.1.128", key_p->data);
658 assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
659
660 memset(key_p, 0, key_size);
661 assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
662 assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
663 key_p->data[1] == 168 && key_p->data[2] == 0);
664
665 memset(next_key_p, 0, key_size);
666 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
667 assert(next_key_p->prefixlen == 28 && next_key_p->data[0] == 192 &&
668 next_key_p->data[1] == 168 && next_key_p->data[2] == 1 &&
669 next_key_p->data[3] == 128);
670
671 memcpy(key_p, next_key_p, key_size);
672 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
673 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
674 next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
675
676 memcpy(key_p, next_key_p, key_size);
677 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
678 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
679 next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
680
681 memcpy(key_p, next_key_p, key_size);
682 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
683 assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
684 next_key_p->data[1] == 168);
685
686 memcpy(key_p, next_key_p, key_size);
687 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
688
689 /* no exact matching key should return the first one in post order */
690 key_p->prefixlen = 22;
691 inet_pton(AF_INET, "192.168.1.0", key_p->data);
692 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
693 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
694 next_key_p->data[1] == 168 && next_key_p->data[2] == 0);
695
696 close(map_fd);
697 }
698
699 #define MAX_TEST_KEYS 4
700 struct lpm_mt_test_info {
701 int cmd; /* 0: update, 1: delete, 2: lookup, 3: get_next_key */
702 int iter;
703 int map_fd;
704 struct {
705 __u32 prefixlen;
706 __u32 data;
707 } key[MAX_TEST_KEYS];
708 };
709
lpm_test_command(void * arg)710 static void *lpm_test_command(void *arg)
711 {
712 int i, j, ret, iter, key_size;
713 struct lpm_mt_test_info *info = arg;
714 struct bpf_lpm_trie_key_u8 *key_p;
715
716 key_size = sizeof(*key_p) + sizeof(__u32);
717 key_p = alloca(key_size);
718 for (iter = 0; iter < info->iter; iter++)
719 for (i = 0; i < MAX_TEST_KEYS; i++) {
720 /* first half of iterations in forward order,
721 * and second half in backward order.
722 */
723 j = (iter < (info->iter / 2)) ? i : MAX_TEST_KEYS - i - 1;
724 key_p->prefixlen = info->key[j].prefixlen;
725 memcpy(key_p->data, &info->key[j].data, sizeof(__u32));
726 if (info->cmd == 0) {
727 __u32 value = j;
728 /* update must succeed */
729 assert(bpf_map_update_elem(info->map_fd, key_p, &value, 0) == 0);
730 } else if (info->cmd == 1) {
731 ret = bpf_map_delete_elem(info->map_fd, key_p);
732 assert(ret == 0 || errno == ENOENT);
733 } else if (info->cmd == 2) {
734 __u32 value;
735 ret = bpf_map_lookup_elem(info->map_fd, key_p, &value);
736 assert(ret == 0 || errno == ENOENT);
737 } else {
738 struct bpf_lpm_trie_key_u8 *next_key_p = alloca(key_size);
739 ret = bpf_map_get_next_key(info->map_fd, key_p, next_key_p);
740 assert(ret == 0 || errno == ENOENT || errno == ENOMEM);
741 }
742 }
743
744 // Pass successful exit info back to the main thread
745 pthread_exit((void *)info);
746 }
747
setup_lpm_mt_test_info(struct lpm_mt_test_info * info,int map_fd)748 static void setup_lpm_mt_test_info(struct lpm_mt_test_info *info, int map_fd)
749 {
750 info->iter = 2000;
751 info->map_fd = map_fd;
752 info->key[0].prefixlen = 16;
753 inet_pton(AF_INET, "192.168.0.0", &info->key[0].data);
754 info->key[1].prefixlen = 24;
755 inet_pton(AF_INET, "192.168.0.0", &info->key[1].data);
756 info->key[2].prefixlen = 24;
757 inet_pton(AF_INET, "192.168.128.0", &info->key[2].data);
758 info->key[3].prefixlen = 24;
759 inet_pton(AF_INET, "192.168.1.0", &info->key[3].data);
760 }
761
test_lpm_multi_thread(void)762 static void test_lpm_multi_thread(void)
763 {
764 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
765 struct lpm_mt_test_info info[4];
766 size_t key_size, value_size;
767 pthread_t thread_id[4];
768 int i, map_fd;
769 void *ret;
770
771 /* create a trie */
772 value_size = sizeof(__u32);
773 key_size = sizeof(struct bpf_lpm_trie_key_hdr) + value_size;
774 map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, value_size, 100, &opts);
775
776 /* create 4 threads to test update, delete, lookup and get_next_key */
777 setup_lpm_mt_test_info(&info[0], map_fd);
778 for (i = 0; i < 4; i++) {
779 if (i != 0)
780 memcpy(&info[i], &info[0], sizeof(info[i]));
781 info[i].cmd = i;
782 assert(pthread_create(&thread_id[i], NULL, &lpm_test_command, &info[i]) == 0);
783 }
784
785 for (i = 0; i < 4; i++)
786 assert(pthread_join(thread_id[i], &ret) == 0 && ret == (void *)&info[i]);
787
788 close(map_fd);
789 }
790
lpm_trie_create(unsigned int key_size,unsigned int value_size,unsigned int max_entries)791 static int lpm_trie_create(unsigned int key_size, unsigned int value_size, unsigned int max_entries)
792 {
793 LIBBPF_OPTS(bpf_map_create_opts, opts);
794 int fd;
795
796 opts.map_flags = BPF_F_NO_PREALLOC;
797 fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, "lpm_trie", key_size, value_size, max_entries,
798 &opts);
799 CHECK(fd < 0, "bpf_map_create", "error %d\n", errno);
800
801 return fd;
802 }
803
test_lpm_trie_update_flags(void)804 static void test_lpm_trie_update_flags(void)
805 {
806 struct lpm_trie_int_key key;
807 unsigned int value, got;
808 int fd, err;
809
810 fd = lpm_trie_create(sizeof(key), sizeof(value), 3);
811
812 /* invalid flags (Error) */
813 key.prefixlen = 32;
814 key.data = 0;
815 value = 0;
816 err = bpf_map_update_elem(fd, &key, &value, BPF_F_LOCK);
817 CHECK(err != -EINVAL, "invalid update flag", "error %d\n", err);
818
819 /* invalid flags (Error) */
820 key.prefixlen = 32;
821 key.data = 0;
822 value = 0;
823 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST | BPF_EXIST);
824 CHECK(err != -EINVAL, "invalid update flag", "error %d\n", err);
825
826 /* overwrite an empty qp-trie (Error) */
827 key.prefixlen = 32;
828 key.data = 0;
829 value = 2;
830 err = bpf_map_update_elem(fd, &key, &value, BPF_EXIST);
831 CHECK(err != -ENOENT, "overwrite empty qp-trie", "error %d\n", err);
832
833 /* add a new node */
834 key.prefixlen = 16;
835 key.data = 0;
836 value = 1;
837 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
838 CHECK(err, "add new elem", "error %d\n", err);
839 got = 0;
840 err = bpf_map_lookup_elem(fd, &key, &got);
841 CHECK(err, "lookup elem", "error %d\n", err);
842 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
843
844 /* add the same node as new node (Error) */
845 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
846 CHECK(err != -EEXIST, "add new elem again", "error %d\n", err);
847
848 /* overwrite the existed node */
849 value = 4;
850 err = bpf_map_update_elem(fd, &key, &value, BPF_EXIST);
851 CHECK(err, "overwrite elem", "error %d\n", err);
852 got = 0;
853 err = bpf_map_lookup_elem(fd, &key, &got);
854 CHECK(err, "lookup elem", "error %d\n", err);
855 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
856
857 /* overwrite the node */
858 value = 1;
859 err = bpf_map_update_elem(fd, &key, &value, BPF_ANY);
860 CHECK(err, "update elem", "error %d\n", err);
861 got = 0;
862 err = bpf_map_lookup_elem(fd, &key, &got);
863 CHECK(err, "lookup elem", "error %d\n", err);
864 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
865
866 /* overwrite a non-existent node which is the prefix of the first
867 * node (Error).
868 */
869 key.prefixlen = 8;
870 key.data = 0;
871 value = 2;
872 err = bpf_map_update_elem(fd, &key, &value, BPF_EXIST);
873 CHECK(err != -ENOENT, "overwrite nonexistent elem", "error %d\n", err);
874
875 /* add a new node which is the prefix of the first node */
876 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
877 CHECK(err, "add new elem", "error %d\n", err);
878 got = 0;
879 err = bpf_map_lookup_elem(fd, &key, &got);
880 CHECK(err, "lookup key", "error %d\n", err);
881 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
882
883 /* add another new node which will be the sibling of the first node */
884 key.prefixlen = 9;
885 key.data = htobe32(1 << 23);
886 value = 5;
887 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
888 CHECK(err, "add new elem", "error %d\n", err);
889 got = 0;
890 err = bpf_map_lookup_elem(fd, &key, &got);
891 CHECK(err, "lookup key", "error %d\n", err);
892 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
893
894 /* overwrite the third node */
895 value = 3;
896 err = bpf_map_update_elem(fd, &key, &value, BPF_ANY);
897 CHECK(err, "overwrite elem", "error %d\n", err);
898 got = 0;
899 err = bpf_map_lookup_elem(fd, &key, &got);
900 CHECK(err, "lookup key", "error %d\n", err);
901 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
902
903 /* delete the second node to make it an intermediate node */
904 key.prefixlen = 8;
905 key.data = 0;
906 err = bpf_map_delete_elem(fd, &key);
907 CHECK(err, "del elem", "error %d\n", err);
908
909 /* overwrite the intermediate node (Error) */
910 value = 2;
911 err = bpf_map_update_elem(fd, &key, &value, BPF_EXIST);
912 CHECK(err != -ENOENT, "overwrite nonexistent elem", "error %d\n", err);
913
914 close(fd);
915 }
916
test_lpm_trie_update_full_map(void)917 static void test_lpm_trie_update_full_map(void)
918 {
919 struct lpm_trie_int_key key;
920 int value, got;
921 int fd, err;
922
923 fd = lpm_trie_create(sizeof(key), sizeof(value), 3);
924
925 /* add a new node */
926 key.prefixlen = 16;
927 key.data = 0;
928 value = 0;
929 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
930 CHECK(err, "add new elem", "error %d\n", err);
931 got = 0;
932 err = bpf_map_lookup_elem(fd, &key, &got);
933 CHECK(err, "lookup elem", "error %d\n", err);
934 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
935
936 /* add new node */
937 key.prefixlen = 8;
938 key.data = 0;
939 value = 1;
940 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
941 CHECK(err, "add new elem", "error %d\n", err);
942 got = 0;
943 err = bpf_map_lookup_elem(fd, &key, &got);
944 CHECK(err, "lookup elem", "error %d\n", err);
945 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
946
947 /* add new node */
948 key.prefixlen = 9;
949 key.data = htobe32(1 << 23);
950 value = 2;
951 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
952 CHECK(err, "add new elem", "error %d\n", err);
953 got = 0;
954 err = bpf_map_lookup_elem(fd, &key, &got);
955 CHECK(err, "lookup elem", "error %d\n", err);
956 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
957
958 /* try to add more node (Error) */
959 key.prefixlen = 32;
960 key.data = 0;
961 value = 3;
962 err = bpf_map_update_elem(fd, &key, &value, BPF_ANY);
963 CHECK(err != -ENOSPC, "add to full trie", "error %d\n", err);
964
965 /* update the value of an existed node with BPF_EXIST */
966 key.prefixlen = 16;
967 key.data = 0;
968 value = 4;
969 err = bpf_map_update_elem(fd, &key, &value, BPF_EXIST);
970 CHECK(err, "overwrite elem", "error %d\n", err);
971 got = 0;
972 err = bpf_map_lookup_elem(fd, &key, &got);
973 CHECK(err, "lookup elem", "error %d\n", err);
974 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
975
976 /* update the value of an existed node with BPF_ANY */
977 key.prefixlen = 9;
978 key.data = htobe32(1 << 23);
979 value = 5;
980 err = bpf_map_update_elem(fd, &key, &value, BPF_ANY);
981 CHECK(err, "overwrite elem", "error %d\n", err);
982 got = 0;
983 err = bpf_map_lookup_elem(fd, &key, &got);
984 CHECK(err, "lookup elem", "error %d\n", err);
985 CHECK(got != value, "check value", "got %d exp %d\n", got, value);
986
987 close(fd);
988 }
989
cmp_str(const void * a,const void * b)990 static int cmp_str(const void *a, const void *b)
991 {
992 const char *str_a = *(const char **)a, *str_b = *(const char **)b;
993
994 return strcmp(str_a, str_b);
995 }
996
997 /* Save strings in LPM trie. The trailing '\0' for each string will be
998 * accounted in the prefixlen. The strings returned during the iteration
999 * should be sorted as expected.
1000 */
test_lpm_trie_iterate_strs(void)1001 static void test_lpm_trie_iterate_strs(void)
1002 {
1003 static const char * const keys[] = {
1004 "ab", "abO", "abc", "abo", "abS", "abcd",
1005 };
1006 const char *sorted_keys[ARRAY_SIZE(keys)];
1007 struct lpm_trie_bytes_key key, next_key;
1008 unsigned int value, got, i, j, len;
1009 struct lpm_trie_bytes_key *cur;
1010 int fd, err;
1011
1012 fd = lpm_trie_create(sizeof(key), sizeof(value), ARRAY_SIZE(keys));
1013
1014 for (i = 0; i < ARRAY_SIZE(keys); i++) {
1015 unsigned int flags;
1016
1017 /* add i-th element */
1018 flags = i % 2 ? BPF_NOEXIST : 0;
1019 len = strlen(keys[i]);
1020 /* include the trailing '\0' */
1021 key.prefixlen = (len + 1) * 8;
1022 memset(key.data, 0, sizeof(key.data));
1023 memcpy(key.data, keys[i], len);
1024 value = i + 100;
1025 err = bpf_map_update_elem(fd, &key, &value, flags);
1026 CHECK(err, "add elem", "#%u error %d\n", i, err);
1027
1028 err = bpf_map_lookup_elem(fd, &key, &got);
1029 CHECK(err, "lookup elem", "#%u error %d\n", i, err);
1030 CHECK(got != value, "lookup elem", "#%u expect %u got %u\n", i, value, got);
1031
1032 /* re-add i-th element (Error) */
1033 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
1034 CHECK(err != -EEXIST, "re-add elem", "#%u error %d\n", i, err);
1035
1036 /* Overwrite i-th element */
1037 flags = i % 2 ? 0 : BPF_EXIST;
1038 value = i;
1039 err = bpf_map_update_elem(fd, &key, &value, flags);
1040 CHECK(err, "update elem", "error %d\n", err);
1041
1042 /* Lookup #[0~i] elements */
1043 for (j = 0; j <= i; j++) {
1044 len = strlen(keys[j]);
1045 key.prefixlen = (len + 1) * 8;
1046 memset(key.data, 0, sizeof(key.data));
1047 memcpy(key.data, keys[j], len);
1048 err = bpf_map_lookup_elem(fd, &key, &got);
1049 CHECK(err, "lookup elem", "#%u/%u error %d\n", i, j, err);
1050 CHECK(got != j, "lookup elem", "#%u/%u expect %u got %u\n",
1051 i, j, value, got);
1052 }
1053 }
1054
1055 /* Add element to a full qp-trie (Error) */
1056 key.prefixlen = sizeof(key.data) * 8;
1057 memset(key.data, 0, sizeof(key.data));
1058 value = 0;
1059 err = bpf_map_update_elem(fd, &key, &value, 0);
1060 CHECK(err != -ENOSPC, "add to full qp-trie", "error %d\n", err);
1061
1062 /* Iterate sorted elements: no deletion */
1063 memcpy(sorted_keys, keys, sizeof(keys));
1064 qsort(sorted_keys, ARRAY_SIZE(sorted_keys), sizeof(sorted_keys[0]), cmp_str);
1065 cur = NULL;
1066 for (i = 0; i < ARRAY_SIZE(sorted_keys); i++) {
1067 len = strlen(sorted_keys[i]);
1068 err = bpf_map_get_next_key(fd, cur, &next_key);
1069 CHECK(err, "iterate", "#%u error %d\n", i, err);
1070 CHECK(next_key.prefixlen != (len + 1) * 8, "iterate",
1071 "#%u invalid len %u expect %u\n",
1072 i, next_key.prefixlen, (len + 1) * 8);
1073 CHECK(memcmp(sorted_keys[i], next_key.data, len + 1), "iterate",
1074 "#%u got %.*s exp %.*s\n", i, len, next_key.data, len, sorted_keys[i]);
1075
1076 cur = &next_key;
1077 }
1078 err = bpf_map_get_next_key(fd, cur, &next_key);
1079 CHECK(err != -ENOENT, "more element", "error %d\n", err);
1080
1081 /* Iterate sorted elements: delete the found key after each iteration */
1082 cur = NULL;
1083 for (i = 0; i < ARRAY_SIZE(sorted_keys); i++) {
1084 len = strlen(sorted_keys[i]);
1085 err = bpf_map_get_next_key(fd, cur, &next_key);
1086 CHECK(err, "iterate", "#%u error %d\n", i, err);
1087 CHECK(next_key.prefixlen != (len + 1) * 8, "iterate",
1088 "#%u invalid len %u expect %u\n",
1089 i, next_key.prefixlen, (len + 1) * 8);
1090 CHECK(memcmp(sorted_keys[i], next_key.data, len + 1), "iterate",
1091 "#%u got %.*s exp %.*s\n", i, len, next_key.data, len, sorted_keys[i]);
1092
1093 cur = &next_key;
1094
1095 err = bpf_map_delete_elem(fd, cur);
1096 CHECK(err, "delete", "#%u error %d\n", i, err);
1097 }
1098 err = bpf_map_get_next_key(fd, cur, &next_key);
1099 CHECK(err != -ENOENT, "non-empty qp-trie", "error %d\n", err);
1100
1101 close(fd);
1102 }
1103
1104 /* Use the fixed prefixlen (32) and save integers in LPM trie. The iteration of
1105 * LPM trie will return these integers in big-endian order, therefore, convert
1106 * these integers to big-endian before update. After each iteration, delete the
1107 * found key (the smallest integer) and expect the next iteration will return
1108 * the second smallest number.
1109 */
test_lpm_trie_iterate_ints(void)1110 static void test_lpm_trie_iterate_ints(void)
1111 {
1112 struct lpm_trie_int_key key, next_key;
1113 unsigned int i, max_entries;
1114 struct lpm_trie_int_key *cur;
1115 unsigned int *data_set;
1116 int fd, err;
1117 bool value;
1118
1119 max_entries = 4096;
1120 data_set = calloc(max_entries, sizeof(*data_set));
1121 CHECK(!data_set, "malloc", "no mem\n");
1122 for (i = 0; i < max_entries; i++)
1123 data_set[i] = i;
1124
1125 fd = lpm_trie_create(sizeof(key), sizeof(value), max_entries);
1126 value = true;
1127 for (i = 0; i < max_entries; i++) {
1128 key.prefixlen = 32;
1129 key.data = htobe32(data_set[i]);
1130
1131 err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
1132 CHECK(err, "add elem", "#%u error %d\n", i, err);
1133 }
1134
1135 cur = NULL;
1136 for (i = 0; i < max_entries; i++) {
1137 err = bpf_map_get_next_key(fd, cur, &next_key);
1138 CHECK(err, "iterate", "#%u error %d\n", i, err);
1139 CHECK(next_key.prefixlen != 32, "iterate", "#%u invalid len %u\n",
1140 i, next_key.prefixlen);
1141 CHECK(be32toh(next_key.data) != data_set[i], "iterate", "#%u got 0x%x exp 0x%x\n",
1142 i, be32toh(next_key.data), data_set[i]);
1143 cur = &next_key;
1144
1145 /*
1146 * Delete the minimal key, the next call of bpf_get_next_key()
1147 * will return the second minimal key.
1148 */
1149 err = bpf_map_delete_elem(fd, &next_key);
1150 CHECK(err, "del elem", "#%u elem error %d\n", i, err);
1151 }
1152 err = bpf_map_get_next_key(fd, cur, &next_key);
1153 CHECK(err != -ENOENT, "more element", "error %d\n", err);
1154
1155 err = bpf_map_get_next_key(fd, NULL, &next_key);
1156 CHECK(err != -ENOENT, "no-empty qp-trie", "error %d\n", err);
1157
1158 free(data_set);
1159
1160 close(fd);
1161 }
1162
test_lpm_trie_map_basic_ops(void)1163 void test_lpm_trie_map_basic_ops(void)
1164 {
1165 int i;
1166
1167 /* we want predictable, pseudo random tests */
1168 srand(0xf00ba1);
1169
1170 test_lpm_basic();
1171 test_lpm_order();
1172
1173 /* Test with 8, 16, 24, 32, ... 128 bit prefix length */
1174 for (i = 1; i <= 16; ++i)
1175 test_lpm_map(i);
1176
1177 test_lpm_ipaddr();
1178 test_lpm_delete();
1179 test_lpm_get_next_key();
1180 test_lpm_multi_thread();
1181
1182 test_lpm_trie_update_flags();
1183 test_lpm_trie_update_full_map();
1184 test_lpm_trie_iterate_strs();
1185 test_lpm_trie_iterate_ints();
1186
1187 printf("%s: PASS\n", __func__);
1188 }
1189