798 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Randomized tests for eBPF longest-prefix-match maps4 *5 * This program runs randomized tests against the lpm-bpf-map. It implements a6 * "Trivial Longest Prefix Match" (tlpm) based on simple, linear, singly linked7 * lists. The implementation should be pretty straightforward.8 *9 * Based on tlpm, this inserts randomized data into bpf-lpm-maps and verifies10 * 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 30struct tlpm_node {31 struct tlpm_node *next;32 size_t n_bits;33 uint8_t key[];34};35 36static struct tlpm_node *tlpm_match(struct tlpm_node *list,37 const uint8_t *key,38 size_t n_bits);39 40static 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 68static 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 80static 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 all88 * entries and match each prefix against @key. Remember the "best"89 * entry we find (i.e., the longest prefix that matches) and return it90 * 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 109static 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 137static 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, (uint8_t[]){ 0xff }, 8));144 145 t1 = list = tlpm_add(list, (uint8_t[]){ 0xff }, 8);146 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));147 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));148 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0x00 }, 16));149 assert(!tlpm_match(list, (uint8_t[]){ 0x7f }, 8));150 assert(!tlpm_match(list, (uint8_t[]){ 0xfe }, 8));151 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 7));152 153 t2 = list = tlpm_add(list, (uint8_t[]){ 0xff, 0xff }, 16);154 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));155 assert(t2 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));156 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15));157 assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16));158 159 list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16);160 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));161 assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));162 163 list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8);164 assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));165 166 tlpm_clear(list);167}168 169static 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 the175 * order of entries. Insert a random set of entries into @l1, and copy176 * the same data in reverse order into @l2. Then verify a lookup of177 * random keys will yield the same result in both sets.178 */179 180 for (i = 0; i < (1 << 12); ++i)181 l1 = tlpm_add(l1, (uint8_t[]){182 rand() % 0xff,183 rand() % 0xff,184 }, rand() % 16 + 1);185 186 for (t1 = l1; t1; t1 = t1->next)187 l2 = tlpm_add(l2, t1->key, 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(l1, key, 16);193 t2 = tlpm_match(l2, key, 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(l1);205 tlpm_clear(l2);206}207 208static 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 of219 * prefixes and insert it into both tlpm and bpf-lpm. Then run some220 * 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, value, 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, data, 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 the279 * corresponding nodes from the bpf-lpm. Then run the same280 * large number of random lookups in both and make sure they match.281 * Note: we need to count the number of nodes actually inserted282 * 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, list->key, 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, data, 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 match319 * 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 331static 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 423static 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 far477 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 node481 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 532static 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 4682struct 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 692static 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 thread727 pthread_exit((void *)info);728}729 730static 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 744static 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[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 773int 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(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