Lines Matching +full:key +full:- +full:2
1 // SPDX-License-Identifier: GPL-2.0
3 * Randomized tests for eBPF longest-prefix-match maps
5 * This program runs randomized tests against the lpm-bpf-map. It implements a
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.
33 uint8_t key[]; member
37 const uint8_t *key,
41 const uint8_t *key, in tlpm_add() argument
50 node = tlpm_match(list, key, n_bits); in tlpm_add()
51 if (node && node->n_bits == n_bits) { in tlpm_add()
52 memcpy(node->key, key, n); in tlpm_add()
56 /* add new entry with @key/@n_bits to @list and return new head */ in tlpm_add()
61 node->next = list; in tlpm_add()
62 node->n_bits = n_bits; in tlpm_add()
63 memcpy(node->key, key, n); in tlpm_add()
75 list = list->next; in tlpm_clear()
81 const uint8_t *key, in tlpm_match() argument
87 /* Perform longest prefix-match on @key/@n_bits. That is, iterate all in tlpm_match()
88 * entries and match each prefix against @key. Remember the "best" in tlpm_match()
93 for ( ; list; list = list->next) { in tlpm_match()
94 for (i = 0; i < n_bits && i < list->n_bits; ++i) { in tlpm_match()
95 if ((key[i / 8] & (1 << (7 - i % 8))) != in tlpm_match()
96 (list->key[i / 8] & (1 << (7 - i % 8)))) in tlpm_match()
100 if (i >= list->n_bits) { in tlpm_match()
101 if (!best || i > best->n_bits) in tlpm_match()
110 const uint8_t *key, in tlpm_delete() argument
113 struct tlpm_node *best = tlpm_match(list, key, n_bits); in tlpm_delete()
116 if (!best || best->n_bits != n_bits) in tlpm_delete()
120 node = best->next; in tlpm_delete()
125 for (node = list; node; node = node->next) { in tlpm_delete()
126 if (node->next == best) { in tlpm_delete()
127 node->next = best->next; in tlpm_delete()
186 for (t1 = l1; t1; t1 = t1->next) in test_lpm_order()
187 l2 = tlpm_add(l2, t1->key, t1->n_bits); in test_lpm_order()
190 uint8_t key[] = { rand() % 0xff, rand() % 0xff }; in test_lpm_order() local
192 t1 = tlpm_match(l1, key, 16); in test_lpm_order()
193 t2 = tlpm_match(l2, key, 16); in test_lpm_order()
197 assert(t1->n_bits == t2->n_bits); in test_lpm_order()
198 for (j = 0; j < t1->n_bits; ++j) in test_lpm_order()
199 assert((t1->key[j / 8] & (1 << (7 - j % 8))) == in test_lpm_order()
200 (t2->key[j / 8] & (1 << (7 - j % 8)))); in test_lpm_order()
214 struct bpf_lpm_trie_key_u8 *key; in test_lpm_map() local
218 /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of in test_lpm_map()
219 * prefixes and insert it into both tlpm and bpf-lpm. Then run some in test_lpm_map()
234 key = alloca(sizeof(*key) + keysize); in test_lpm_map()
235 memset(key, 0, sizeof(*key) + keysize); in test_lpm_map()
238 sizeof(*key) + keysize, in test_lpm_map()
251 key->prefixlen = value[keysize]; in test_lpm_map()
252 memcpy(key->data, value, keysize); in test_lpm_map()
253 r = bpf_map_update_elem(map, key, value, 0); in test_lpm_map()
263 key->prefixlen = 8 * keysize; in test_lpm_map()
264 memcpy(key->data, data, keysize); in test_lpm_map()
265 r = bpf_map_lookup_elem(map, key, value); in test_lpm_map()
271 assert(t->n_bits == value[keysize]); in test_lpm_map()
272 for (j = 0; j < t->n_bits; ++j) in test_lpm_map()
273 assert((t->key[j / 8] & (1 << (7 - j % 8))) == in test_lpm_map()
274 (value[j / 8] & (1 << (7 - j % 8)))); in test_lpm_map()
279 * corresponding nodes from the bpf-lpm. Then run the same in test_lpm_map()
284 for (i = 0, t = list; t; i++, t = t->next) in test_lpm_map()
286 for (j = 0; j < i / 2; ++j) { in test_lpm_map()
287 key->prefixlen = list->n_bits; in test_lpm_map()
288 memcpy(key->data, list->key, keysize); in test_lpm_map()
289 r = bpf_map_delete_elem(map, key); in test_lpm_map()
291 list = tlpm_delete(list, list->key, list->n_bits); in test_lpm_map()
300 key->prefixlen = 8 * keysize; in test_lpm_map()
301 memcpy(key->data, data, keysize); in test_lpm_map()
302 r = bpf_map_lookup_elem(map, key, value); in test_lpm_map()
308 assert(t->n_bits == value[keysize]); in test_lpm_map()
309 for (j = 0; j < t->n_bits; ++j) in test_lpm_map()
310 assert((t->key[j / 8] & (1 << (7 - j % 8))) == in test_lpm_map()
311 (value[j / 8] & (1 << (7 - j % 8)))); in test_lpm_map()
359 key_ipv4->prefixlen = 16; in test_lpm_ipaddr()
360 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); in test_lpm_ipaddr()
363 value = 2; in test_lpm_ipaddr()
364 key_ipv4->prefixlen = 24; in test_lpm_ipaddr()
365 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); in test_lpm_ipaddr()
369 key_ipv4->prefixlen = 24; in test_lpm_ipaddr()
370 inet_pton(AF_INET, "192.168.128.0", key_ipv4->data); in test_lpm_ipaddr()
374 key_ipv4->prefixlen = 24; in test_lpm_ipaddr()
375 inet_pton(AF_INET, "192.168.1.0", key_ipv4->data); in test_lpm_ipaddr()
379 key_ipv4->prefixlen = 23; in test_lpm_ipaddr()
380 inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); in test_lpm_ipaddr()
384 key_ipv6->prefixlen = 64; in test_lpm_ipaddr()
385 inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data); in test_lpm_ipaddr()
389 key_ipv4->prefixlen = 32; in test_lpm_ipaddr()
390 key_ipv6->prefixlen = 128; in test_lpm_ipaddr()
393 inet_pton(AF_INET, "192.168.128.23", key_ipv4->data); in test_lpm_ipaddr()
397 inet_pton(AF_INET, "192.168.0.1", key_ipv4->data); in test_lpm_ipaddr()
399 assert(value == 2); in test_lpm_ipaddr()
401 inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data); in test_lpm_ipaddr()
405 inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data); in test_lpm_ipaddr()
410 inet_pton(AF_INET, "10.0.0.1", key_ipv4->data); in test_lpm_ipaddr()
411 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT); in test_lpm_ipaddr()
413 inet_pton(AF_INET, "11.11.11.11", key_ipv4->data); in test_lpm_ipaddr()
414 assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT); in test_lpm_ipaddr()
416 inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data); in test_lpm_ipaddr()
417 assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -ENOENT); in test_lpm_ipaddr()
426 struct bpf_lpm_trie_key_u8 *key; in test_lpm_delete() local
431 key_size = sizeof(*key) + sizeof(__u32); in test_lpm_delete()
432 key = alloca(key_size); in test_lpm_delete()
441 * 192.168.0.0/24 (2) in test_lpm_delete()
449 * (2) (4) in test_lpm_delete()
452 key->prefixlen = 16; in test_lpm_delete()
453 inet_pton(AF_INET, "192.168.0.0", key->data); in test_lpm_delete()
454 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); in test_lpm_delete()
456 value = 2; in test_lpm_delete()
457 key->prefixlen = 24; in test_lpm_delete()
458 inet_pton(AF_INET, "192.168.0.0", key->data); in test_lpm_delete()
459 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); in test_lpm_delete()
462 key->prefixlen = 24; in test_lpm_delete()
463 inet_pton(AF_INET, "192.168.128.0", key->data); in test_lpm_delete()
464 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); in test_lpm_delete()
467 key->prefixlen = 24; in test_lpm_delete()
468 inet_pton(AF_INET, "192.168.1.0", key->data); in test_lpm_delete()
469 assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); in test_lpm_delete()
471 /* remove non-existent node */ in test_lpm_delete()
472 key->prefixlen = 32; in test_lpm_delete()
473 inet_pton(AF_INET, "10.0.0.1", key->data); in test_lpm_delete()
474 assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT); in test_lpm_delete()
476 key->prefixlen = 30; // unused prefix so far in test_lpm_delete()
477 inet_pton(AF_INET, "192.255.0.0", key->data); in test_lpm_delete()
478 assert(bpf_map_delete_elem(map_fd, key) == -ENOENT); in test_lpm_delete()
480 key->prefixlen = 16; // same prefix as the root node in test_lpm_delete()
481 inet_pton(AF_INET, "192.255.0.0", key->data); in test_lpm_delete()
482 assert(bpf_map_delete_elem(map_fd, key) == -ENOENT); in test_lpm_delete()
485 key->prefixlen = 32; in test_lpm_delete()
486 inet_pton(AF_INET, "192.168.0.1", key->data); in test_lpm_delete()
487 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); in test_lpm_delete()
488 assert(value == 2); in test_lpm_delete()
491 key->prefixlen = 24; in test_lpm_delete()
492 inet_pton(AF_INET, "192.168.0.0", key->data); in test_lpm_delete()
493 assert(bpf_map_delete_elem(map_fd, key) == 0); in test_lpm_delete()
495 key->prefixlen = 32; in test_lpm_delete()
496 inet_pton(AF_INET, "192.168.0.1", key->data); in test_lpm_delete()
497 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); in test_lpm_delete()
501 key->prefixlen = 24; in test_lpm_delete()
502 inet_pton(AF_INET, "192.168.1.0", key->data); in test_lpm_delete()
503 assert(bpf_map_delete_elem(map_fd, key) == 0); in test_lpm_delete()
505 key->prefixlen = 32; in test_lpm_delete()
506 inet_pton(AF_INET, "192.168.1.1", key->data); in test_lpm_delete()
507 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); in test_lpm_delete()
511 key->prefixlen = 16; in test_lpm_delete()
512 inet_pton(AF_INET, "192.168.0.0", key->data); in test_lpm_delete()
513 assert(bpf_map_delete_elem(map_fd, key) == 0); in test_lpm_delete()
515 key->prefixlen = 32; in test_lpm_delete()
516 inet_pton(AF_INET, "192.168.128.1", key->data); in test_lpm_delete()
517 assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); in test_lpm_delete()
521 key->prefixlen = 24; in test_lpm_delete()
522 inet_pton(AF_INET, "192.168.128.0", key->data); in test_lpm_delete()
523 assert(bpf_map_delete_elem(map_fd, key) == 0); in test_lpm_delete()
525 key->prefixlen = 32; in test_lpm_delete()
526 inet_pton(AF_INET, "192.168.128.1", key->data); in test_lpm_delete()
527 assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT); in test_lpm_delete()
548 assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -ENOENT); in test_lpm_get_next_key()
550 /* get and verify the first key, get the second one should fail. */ in test_lpm_get_next_key()
551 key_p->prefixlen = 16; in test_lpm_get_next_key()
552 inet_pton(AF_INET, "192.168.0.0", key_p->data); in test_lpm_get_next_key()
557 assert(key_p->prefixlen == 16 && key_p->data[0] == 192 && in test_lpm_get_next_key()
558 key_p->data[1] == 168); in test_lpm_get_next_key()
560 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); in test_lpm_get_next_key()
562 /* no exact matching key should get the first one in post order. */ in test_lpm_get_next_key()
563 key_p->prefixlen = 8; in test_lpm_get_next_key()
565 assert(key_p->prefixlen == 16 && key_p->data[0] == 192 && in test_lpm_get_next_key()
566 key_p->data[1] == 168); in test_lpm_get_next_key()
569 key_p->prefixlen = 24; in test_lpm_get_next_key()
570 inet_pton(AF_INET, "192.168.128.0", key_p->data); in test_lpm_get_next_key()
575 assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && in test_lpm_get_next_key()
576 key_p->data[1] == 168 && key_p->data[2] == 128); in test_lpm_get_next_key()
580 assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
581 next_key_p->data[1] == 168); in test_lpm_get_next_key()
584 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); in test_lpm_get_next_key()
587 key_p->prefixlen = 24; in test_lpm_get_next_key()
588 inet_pton(AF_INET, "192.168.0.0", key_p->data); in test_lpm_get_next_key()
593 assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && in test_lpm_get_next_key()
594 key_p->data[1] == 168 && key_p->data[2] == 0); in test_lpm_get_next_key()
598 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
599 next_key_p->data[1] == 168 && next_key_p->data[2] == 128); in test_lpm_get_next_key()
603 assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
604 next_key_p->data[1] == 168); in test_lpm_get_next_key()
607 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); in test_lpm_get_next_key()
610 key_p->prefixlen = 24; in test_lpm_get_next_key()
611 inet_pton(AF_INET, "192.168.1.0", key_p->data); in test_lpm_get_next_key()
616 assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && in test_lpm_get_next_key()
617 key_p->data[1] == 168 && key_p->data[2] == 0); in test_lpm_get_next_key()
621 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
622 next_key_p->data[1] == 168 && next_key_p->data[2] == 1); in test_lpm_get_next_key()
626 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
627 next_key_p->data[1] == 168 && next_key_p->data[2] == 128); in test_lpm_get_next_key()
631 assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
632 next_key_p->data[1] == 168); in test_lpm_get_next_key()
635 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); in test_lpm_get_next_key()
638 key_p->prefixlen = 28; in test_lpm_get_next_key()
639 inet_pton(AF_INET, "192.168.1.128", key_p->data); in test_lpm_get_next_key()
644 assert(key_p->prefixlen == 24 && key_p->data[0] == 192 && in test_lpm_get_next_key()
645 key_p->data[1] == 168 && key_p->data[2] == 0); in test_lpm_get_next_key()
649 assert(next_key_p->prefixlen == 28 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
650 next_key_p->data[1] == 168 && next_key_p->data[2] == 1 && in test_lpm_get_next_key()
651 next_key_p->data[3] == 128); in test_lpm_get_next_key()
655 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
656 next_key_p->data[1] == 168 && next_key_p->data[2] == 1); in test_lpm_get_next_key()
660 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
661 next_key_p->data[1] == 168 && next_key_p->data[2] == 128); in test_lpm_get_next_key()
665 assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
666 next_key_p->data[1] == 168); in test_lpm_get_next_key()
669 assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); in test_lpm_get_next_key()
671 /* no exact matching key should return the first one in post order */ in test_lpm_get_next_key()
672 key_p->prefixlen = 22; in test_lpm_get_next_key()
673 inet_pton(AF_INET, "192.168.1.0", key_p->data); in test_lpm_get_next_key()
675 assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 && in test_lpm_get_next_key()
676 next_key_p->data[1] == 168 && next_key_p->data[2] == 0); in test_lpm_get_next_key()
683 int cmd; /* 0: update, 1: delete, 2: lookup, 3: get_next_key */
689 } key[MAX_TEST_KEYS]; member
700 for (iter = 0; iter < info->iter; iter++) in lpm_test_command()
705 j = (iter < (info->iter / 2)) ? i : MAX_TEST_KEYS - i - 1; in lpm_test_command()
706 key_p->prefixlen = info->key[j].prefixlen; in lpm_test_command()
707 memcpy(key_p->data, &info->key[j].data, sizeof(__u32)); in lpm_test_command()
708 if (info->cmd == 0) { in lpm_test_command()
711 assert(bpf_map_update_elem(info->map_fd, key_p, &value, 0) == 0); in lpm_test_command()
712 } else if (info->cmd == 1) { in lpm_test_command()
713 ret = bpf_map_delete_elem(info->map_fd, key_p); in lpm_test_command()
715 } else if (info->cmd == 2) { in lpm_test_command()
717 ret = bpf_map_lookup_elem(info->map_fd, key_p, &value); in lpm_test_command()
721 ret = bpf_map_get_next_key(info->map_fd, key_p, next_key_p); in lpm_test_command()
732 info->iter = 2000; in setup_lpm_mt_test_info()
733 info->map_fd = map_fd; in setup_lpm_mt_test_info()
734 info->key[0].prefixlen = 16; in setup_lpm_mt_test_info()
735 inet_pton(AF_INET, "192.168.0.0", &info->key[0].data); in setup_lpm_mt_test_info()
736 info->key[1].prefixlen = 24; in setup_lpm_mt_test_info()
737 inet_pton(AF_INET, "192.168.0.0", &info->key[1].data); in setup_lpm_mt_test_info()
738 info->key[2].prefixlen = 24; in setup_lpm_mt_test_info()
739 inet_pton(AF_INET, "192.168.128.0", &info->key[2].data); in setup_lpm_mt_test_info()
740 info->key[3].prefixlen = 24; in setup_lpm_mt_test_info()
741 inet_pton(AF_INET, "192.168.1.0", &info->key[3].data); in setup_lpm_mt_test_info()