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
  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
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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  */
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  */
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
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 }