FILE
lpm_trie_map_basic_ops.c
File preview with syntax highlighting.
linux-6.19.14/tools/testing/selftests/bpf/map_tests/lpm_trie_map_basic_ops.c
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 32struct tlpm_node { 33 struct tlpm_node *next; 34 size_t n_bits; 35 uint8_t key[]; 36}; 37 38struct 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 46struct lpm_trie_int_key { 47 union { 48 struct bpf_lpm_trie_key_hdr hdr; 49 __u32 prefixlen; 50 }; 51 unsigned int data; 52}; 53 54static struct tlpm_node *tlpm_match(struct tlpm_node *list, 55 const uint8_t *key, 56 size_t n_bits); 57 58static 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 86static 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 98static 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 127static 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 155static 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 187static 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 226static 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 349static 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 441static 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 550static 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 700struct 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 710static 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 748static 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 762static 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 791static 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 804static 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 917static 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 990static 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 */ 1001static 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 */ 1110static 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 1163void 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}
~/
Read-only file preview.