tools/testing/selftests/bpf/test_lpm_map.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 <arpa/inet.h>
  24 #include <sys/time.h>
  25
  26 #include <bpf/bpf.h>
  27
  28 #include "bpf_util.h"
  29 #include "bpf_rlimit.h"
  30
  31 struct tlpm_node {
  32         struct tlpm_node *next;
  33         size_t n_bits;
  34         uint8_t key[];
  35 };
  36
  37 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
  38                                     const uint8_t *key,
  39                                     size_t n_bits);
  40
  41 static struct tlpm_node *tlpm_add(struct tlpm_node *list,
  42                                   const uint8_t *key,
  43                                   size_t n_bits)
  44 {
  45         struct tlpm_node *node;
  46         size_t n;
  47
  48         n = (n_bits + 7) / 8;
  49
  50         /* 'overwrite' an equivalent entry if one already exists */
  51         node = tlpm_match(list, key, n_bits);
  52         if (node && node->n_bits == n_bits) {
  53                 memcpy(node->key, key, n);
  54                 return list;
  55         }
  56
  57         /* add new entry with @key/@n_bits to @list and return new head */
  58
  59         node = malloc(sizeof(*node) + n);
  60         assert(node);
  61
  62         node->next = list;
  63         node->n_bits = n_bits;
  64         memcpy(node->key, key, n);
  65
  66         return node;
  67 }
  68
  69 static void tlpm_clear(struct tlpm_node *list)
  70 {
  71         struct tlpm_node *node;
  72
  73         /* free all entries in @list */
  74
  75         while ((node = list)) {
  76                 list = list->next;
  77                 free(node);
  78         }
  79 }
  80
  81 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
  82                                     const uint8_t *key,
  83                                     size_t n_bits)
  84 {
  85         struct tlpm_node *best = NULL;
  86         size_t i;
  87
  88         /* Perform longest prefix-match on @key/@n_bits. That is, iterate all
  89          * entries and match each prefix against @key. Remember the "best"
  90          * entry we find (i.e., the longest prefix that matches) and return it
  91          * to the caller when done.
  92          */
  93
  94         for ( ; list; list = list->next) {
  95                 for (i = 0; i < n_bits && i < list->n_bits; ++i) {
  96                         if ((key[i / 8] & (1 << (7 - i % 8))) !=
  97                             (list->key[i / 8] & (1 << (7 - i % 8))))
  98                                 break;
  99                 }
 100
 101                 if (i >= list->n_bits) {
 102                         if (!best || i > best->n_bits)
 103                                 best = list;
 104                 }
 105         }
 106
 107         return best;
 108 }
 109
 110 static struct tlpm_node *tlpm_delete(struct tlpm_node *list,
 111                                      const uint8_t *key,
 112                                      size_t n_bits)
 113 {
 114         struct tlpm_node *best = tlpm_match(list, key, n_bits);
 115         struct tlpm_node *node;
 116
 117         if (!best || best->n_bits != n_bits)
 118                 return list;
 119
 120         if (best == list) {
 121                 node = best->next;
 122                 free(best);
 123                 return node;
 124         }
 125
 126         for (node = list; node; node = node->next) {
 127                 if (node->next == best) {
 128                         node->next = best->next;
 129                         free(best);
 130                         return list;
 131                 }
 132         }
 133         /* should never get here */
 134         assert(0);
 135         return list;
 136 }
 137
 138 static void test_lpm_basic(void)
 139 {
 140         struct tlpm_node *list = NULL, *t1, *t2;
 141
 142         /* very basic, static tests to verify tlpm works as expected */
 143
 144         assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
 145
 146         t1 = list = tlpm_add(list, (uint8_t[]){ 0xff }, 8);
 147         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
 148         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
 149         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0x00 }, 16));
 150         assert(!tlpm_match(list, (uint8_t[]){ 0x7f }, 8));
 151         assert(!tlpm_match(list, (uint8_t[]){ 0xfe }, 8));
 152         assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 7));
 153
 154         t2 = list = tlpm_add(list, (uint8_t[]){ 0xff, 0xff }, 16);
 155         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
 156         assert(t2 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
 157         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15));
 158         assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16));
 159
 160         list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16);
 161         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
 162         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
 163
 164         list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8);
 165         assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
 166
 167         tlpm_clear(list);
 168 }
 169
 170 static void test_lpm_order(void)
 171 {
 172         struct tlpm_node *t1, *t2, *l1 = NULL, *l2 = NULL;
 173         size_t i, j;
 174
 175         /* Verify the tlpm implementation works correctly regardless of the
 176          * order of entries. Insert a random set of entries into @l1, and copy
 177          * the same data in reverse order into @l2. Then verify a lookup of
 178          * random keys will yield the same result in both sets.
 179          */
 180
 181         for (i = 0; i < (1 << 12); ++i)
 182                 l1 = tlpm_add(l1, (uint8_t[]){
 183                                         rand() % 0xff,
 184                                         rand() % 0xff,
 185                                 }, rand() % 16 + 1);
 186
 187         for (t1 = l1; t1; t1 = t1->next)
 188                 l2 = tlpm_add(l2, t1->key, t1->n_bits);
 189
 190         for (i = 0; i < (1 << 8); ++i) {
 191                 uint8_t key[] = { rand() % 0xff, rand() % 0xff };
 192
 193                 t1 = tlpm_match(l1, key, 16);
 194                 t2 = tlpm_match(l2, key, 16);
 195
 196                 assert(!t1 == !t2);
 197                 if (t1) {
 198                         assert(t1->n_bits == t2->n_bits);
 199                         for (j = 0; j < t1->n_bits; ++j)
 200                                 assert((t1->key[j / 8] & (1 << (7 - j % 8))) ==
 201                                        (t2->key[j / 8] & (1 << (7 - j % 8))));
 202                 }
 203         }
 204
 205         tlpm_clear(l1);
 206         tlpm_clear(l2);
 207 }
 208
 209 static void test_lpm_map(int keysize)
 210 {
 211         LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
 212         volatile size_t n_matches, n_matches_after_delete;
 213         size_t i, j, n_nodes, n_lookups;
 214         struct tlpm_node *t, *list = NULL;
 215         struct bpf_lpm_trie_key *key;
 216         uint8_t *data, *value;
 217         int r, map;
 218
 219         /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of
 220          * prefixes and insert it into both tlpm and bpf-lpm. Then run some
 221          * randomized lookups and verify both maps return the same result.
 222          */
 223
 224         n_matches = 0;
 225         n_matches_after_delete = 0;
 226         n_nodes = 1 << 8;
 227         n_lookups = 1 << 16;
 228
 229         data = alloca(keysize);
 230         memset(data, 0, keysize);
 231
 232         value = alloca(keysize + 1);
 233         memset(value, 0, keysize + 1);
 234
 235         key = alloca(sizeof(*key) + keysize);
 236         memset(key, 0, sizeof(*key) + keysize);
 237
 238         map = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
 239                              sizeof(*key) + keysize,
 240                              keysize + 1,
 241                              4096,
 242                              &opts);
 243         assert(map >= 0);
 244
 245         for (i = 0; i < n_nodes; ++i) {
 246                 for (j = 0; j < keysize; ++j)
 247                         value[j] = rand() & 0xff;
 248                 value[keysize] = rand() % (8 * keysize + 1);
 249
 250                 list = tlpm_add(list, value, value[keysize]);
 251
 252                 key->prefixlen = value[keysize];
 253                 memcpy(key->data, value, keysize);
 254                 r = bpf_map_update_elem(map, key, value, 0);
 255                 assert(!r);
 256         }
 257
 258         for (i = 0; i < n_lookups; ++i) {
 259                 for (j = 0; j < keysize; ++j)
 260                         data[j] = rand() & 0xff;
 261
 262                 t = tlpm_match(list, data, 8 * keysize);
 263
 264                 key->prefixlen = 8 * keysize;
 265                 memcpy(key->data, data, keysize);
 266                 r = bpf_map_lookup_elem(map, key, value);
 267                 assert(!r || errno == ENOENT);
 268                 assert(!t == !!r);
 269
 270                 if (t) {
 271                         ++n_matches;
 272                         assert(t->n_bits == value[keysize]);
 273                         for (j = 0; j < t->n_bits; ++j)
 274                                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
 275                                        (value[j / 8] & (1 << (7 - j % 8))));
 276                 }
 277         }
 278
 279         /* Remove the first half of the elements in the tlpm and the
 280          * corresponding nodes from the bpf-lpm.  Then run the same
 281          * large number of random lookups in both and make sure they match.
 282          * Note: we need to count the number of nodes actually inserted
 283          * since there may have been duplicates.
 284          */
 285         for (i = 0, t = list; t; i++, t = t->next)
 286                 ;
 287         for (j = 0; j < i / 2; ++j) {
 288                 key->prefixlen = list->n_bits;
 289                 memcpy(key->data, list->key, keysize);
 290                 r = bpf_map_delete_elem(map, key);
 291                 assert(!r);
 292                 list = tlpm_delete(list, list->key, list->n_bits);
 293                 assert(list);
 294         }
 295         for (i = 0; i < n_lookups; ++i) {
 296                 for (j = 0; j < keysize; ++j)
 297                         data[j] = rand() & 0xff;
 298
 299                 t = tlpm_match(list, data, 8 * keysize);
 300
 301                 key->prefixlen = 8 * keysize;
 302                 memcpy(key->data, data, keysize);
 303                 r = bpf_map_lookup_elem(map, key, value);
 304                 assert(!r || errno == ENOENT);
 305                 assert(!t == !!r);
 306
 307                 if (t) {
 308                         ++n_matches_after_delete;
 309                         assert(t->n_bits == value[keysize]);
 310                         for (j = 0; j < t->n_bits; ++j)
 311                                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
 312                                        (value[j / 8] & (1 << (7 - j % 8))));
 313                 }
 314         }
 315
 316         close(map);
 317         tlpm_clear(list);
 318
 319         /* With 255 random nodes in the map, we are pretty likely to match
 320          * something on every lookup. For statistics, use this:
 321          *
 322          *     printf("          nodes: %zu\n"
 323          *            "        lookups: %zu\n"
 324          *            "        matches: %zu\n"
 325          *            "matches(delete): %zu\n",
 326          *            n_nodes, n_lookups, n_matches, n_matches_after_delete);
 327          */
 328 }
 329
 330 /* Test the implementation with some 'real world' examples */
 331
 332 static void test_lpm_ipaddr(void)
 333 {
 334         LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
 335         struct bpf_lpm_trie_key *key_ipv4;
 336         struct bpf_lpm_trie_key *key_ipv6;
 337         size_t key_size_ipv4;
 338         size_t key_size_ipv6;
 339         int map_fd_ipv4;
 340         int map_fd_ipv6;
 341         __u64 value;
 342
 343         key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32);
 344         key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4;
 345         key_ipv4 = alloca(key_size_ipv4);
 346         key_ipv6 = alloca(key_size_ipv6);
 347
 348         map_fd_ipv4 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
 349                                      key_size_ipv4, sizeof(value),
 350                                      100, &opts);
 351         assert(map_fd_ipv4 >= 0);
 352
 353         map_fd_ipv6 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
 354                                      key_size_ipv6, sizeof(value),
 355                                      100, &opts);
 356         assert(map_fd_ipv6 >= 0);
 357
 358         /* Fill data some IPv4 and IPv6 address ranges */
 359         value = 1;
 360         key_ipv4->prefixlen = 16;
 361         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
 362         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 363
 364         value = 2;
 365         key_ipv4->prefixlen = 24;
 366         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
 367         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 368
 369         value = 3;
 370         key_ipv4->prefixlen = 24;
 371         inet_pton(AF_INET, "192.168.128.0", key_ipv4->data);
 372         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 373
 374         value = 5;
 375         key_ipv4->prefixlen = 24;
 376         inet_pton(AF_INET, "192.168.1.0", key_ipv4->data);
 377         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 378
 379         value = 4;
 380         key_ipv4->prefixlen = 23;
 381         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
 382         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 383
 384         value = 0xdeadbeef;
 385         key_ipv6->prefixlen = 64;
 386         inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data);
 387         assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0);
 388
 389         /* Set tprefixlen to maximum for lookups */
 390         key_ipv4->prefixlen = 32;
 391         key_ipv6->prefixlen = 128;
 392
 393         /* Test some lookups that should come back with a value */
 394         inet_pton(AF_INET, "192.168.128.23", key_ipv4->data);
 395         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
 396         assert(value == 3);
 397
 398         inet_pton(AF_INET, "192.168.0.1", key_ipv4->data);
 399         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
 400         assert(value == 2);
 401
 402         inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data);
 403         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
 404         assert(value == 0xdeadbeef);
 405
 406         inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data);
 407         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
 408         assert(value == 0xdeadbeef);
 409
 410         /* Test some lookups that should not match any entry */
 411         inet_pton(AF_INET, "10.0.0.1", key_ipv4->data);
 412         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 &&
 413                errno == ENOENT);
 414
 415         inet_pton(AF_INET, "11.11.11.11", key_ipv4->data);
 416         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 &&
 417                errno == ENOENT);
 418
 419         inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data);
 420         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -1 &&
 421                errno == ENOENT);
 422
 423         close(map_fd_ipv4);
 424         close(map_fd_ipv6);
 425 }
 426
 427 static void test_lpm_delete(void)
 428 {
 429         LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
 430         struct bpf_lpm_trie_key *key;
 431         size_t key_size;
 432         int map_fd;
 433         __u64 value;
 434
 435         key_size = sizeof(*key) + sizeof(__u32);
 436         key = alloca(key_size);
 437
 438         map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
 439                                 key_size, sizeof(value),
 440                                 100, &opts);
 441         assert(map_fd >= 0);
 442
 443         /* Add nodes:
 444          * 192.168.0.0/16   (1)
 445          * 192.168.0.0/24   (2)
 446          * 192.168.128.0/24 (3)
 447          * 192.168.1.0/24   (4)
 448          *
 449          *         (1)
 450          *        /   \
 451          *     (IM)    (3)
 452          *    /   \
 453          *   (2)  (4)
 454          */
 455         value = 1;
 456         key->prefixlen = 16;
 457         inet_pton(AF_INET, "192.168.0.0", key->data);
 458         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 459
 460         value = 2;
 461         key->prefixlen = 24;
 462         inet_pton(AF_INET, "192.168.0.0", key->data);
 463         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 464
 465         value = 3;
 466         key->prefixlen = 24;
 467         inet_pton(AF_INET, "192.168.128.0", key->data);
 468         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 469
 470         value = 4;
 471         key->prefixlen = 24;
 472         inet_pton(AF_INET, "192.168.1.0", key->data);
 473         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 474
 475         /* remove non-existent node */
 476         key->prefixlen = 32;
 477         inet_pton(AF_INET, "10.0.0.1", key->data);
 478         assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
 479                 errno == ENOENT);
 480
 481         key->prefixlen = 30; // unused prefix so far
 482         inet_pton(AF_INET, "192.255.0.0", key->data);
 483         assert(bpf_map_delete_elem(map_fd, key) == -1 &&
 484                 errno == ENOENT);
 485
 486         key->prefixlen = 16; // same prefix as the root node
 487         inet_pton(AF_INET, "192.255.0.0", key->data);
 488         assert(bpf_map_delete_elem(map_fd, key) == -1 &&
 489                 errno == ENOENT);
 490
 491         /* assert initial lookup */
 492         key->prefixlen = 32;
 493         inet_pton(AF_INET, "192.168.0.1", key->data);
 494         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 495         assert(value == 2);
 496
 497         /* remove leaf node */
 498         key->prefixlen = 24;
 499         inet_pton(AF_INET, "192.168.0.0", key->data);
 500         assert(bpf_map_delete_elem(map_fd, key) == 0);
 501
 502         key->prefixlen = 32;
 503         inet_pton(AF_INET, "192.168.0.1", key->data);
 504         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 505         assert(value == 1);
 506
 507         /* remove leaf (and intermediary) node */
 508         key->prefixlen = 24;
 509         inet_pton(AF_INET, "192.168.1.0", key->data);
 510         assert(bpf_map_delete_elem(map_fd, key) == 0);
 511
 512         key->prefixlen = 32;
 513         inet_pton(AF_INET, "192.168.1.1", key->data);
 514         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 515         assert(value == 1);
 516
 517         /* remove root node */
 518         key->prefixlen = 16;
 519         inet_pton(AF_INET, "192.168.0.0", key->data);
 520         assert(bpf_map_delete_elem(map_fd, key) == 0);
 521
 522         key->prefixlen = 32;
 523         inet_pton(AF_INET, "192.168.128.1", key->data);
 524         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 525         assert(value == 3);
 526
 527         /* remove last node */
 528         key->prefixlen = 24;
 529         inet_pton(AF_INET, "192.168.128.0", key->data);
 530         assert(bpf_map_delete_elem(map_fd, key) == 0);
 531
 532         key->prefixlen = 32;
 533         inet_pton(AF_INET, "192.168.128.1", key->data);
 534         assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
 535                 errno == ENOENT);
 536
 537         close(map_fd);
 538 }
 539
 540 static void test_lpm_get_next_key(void)
 541 {
 542         LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
 543         struct bpf_lpm_trie_key *key_p, *next_key_p;
 544         size_t key_size;
 545         __u32 value = 0;
 546         int map_fd;
 547
 548         key_size = sizeof(*key_p) + sizeof(__u32);
 549         key_p = alloca(key_size);
 550         next_key_p = alloca(key_size);
 551
 552         map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, sizeof(value), 100, &opts);
 553         assert(map_fd >= 0);
 554
 555         /* empty tree. get_next_key should return ENOENT */
 556         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -1 &&
 557                errno == ENOENT);
 558
 559         /* get and verify the first key, get the second one should fail. */
 560         key_p->prefixlen = 16;
 561         inet_pton(AF_INET, "192.168.0.0", key_p->data);
 562         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 563
 564         memset(key_p, 0, key_size);
 565         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 566         assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
 567                key_p->data[1] == 168);
 568
 569         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 570                errno == ENOENT);
 571
 572         /* no exact matching key should get the first one in post order. */
 573         key_p->prefixlen = 8;
 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         /* add one more element (total two) */
 579         key_p->prefixlen = 24;
 580         inet_pton(AF_INET, "192.168.128.0", key_p->data);
 581         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 582
 583         memset(key_p, 0, key_size);
 584         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 585         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 586                key_p->data[1] == 168 && key_p->data[2] == 128);
 587
 588         memset(next_key_p, 0, key_size);
 589         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 590         assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
 591                next_key_p->data[1] == 168);
 592
 593         memcpy(key_p, next_key_p, key_size);
 594         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 595                errno == ENOENT);
 596
 597         /* Add one more element (total three) */
 598         key_p->prefixlen = 24;
 599         inet_pton(AF_INET, "192.168.0.0", key_p->data);
 600         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 601
 602         memset(key_p, 0, key_size);
 603         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 604         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 605                key_p->data[1] == 168 && key_p->data[2] == 0);
 606
 607         memset(next_key_p, 0, key_size);
 608         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 609         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 610                next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
 611
 612         memcpy(key_p, next_key_p, key_size);
 613         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 614         assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
 615                next_key_p->data[1] == 168);
 616
 617         memcpy(key_p, next_key_p, key_size);
 618         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 619                errno == ENOENT);
 620
 621         /* Add one more element (total four) */
 622         key_p->prefixlen = 24;
 623         inet_pton(AF_INET, "192.168.1.0", key_p->data);
 624         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 625
 626         memset(key_p, 0, key_size);
 627         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 628         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 629                key_p->data[1] == 168 && key_p->data[2] == 0);
 630
 631         memset(next_key_p, 0, key_size);
 632         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 633         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 634                next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
 635
 636         memcpy(key_p, next_key_p, key_size);
 637         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 638         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 639                next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
 640
 641         memcpy(key_p, next_key_p, key_size);
 642         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 643         assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
 644                next_key_p->data[1] == 168);
 645
 646         memcpy(key_p, next_key_p, key_size);
 647         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 648                errno == ENOENT);
 649
 650         /* Add one more element (total five) */
 651         key_p->prefixlen = 28;
 652         inet_pton(AF_INET, "192.168.1.128", key_p->data);
 653         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 654
 655         memset(key_p, 0, key_size);
 656         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 657         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 658                key_p->data[1] == 168 && key_p->data[2] == 0);
 659
 660         memset(next_key_p, 0, key_size);
 661         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 662         assert(next_key_p->prefixlen == 28 && next_key_p->data[0] == 192 &&
 663                next_key_p->data[1] == 168 && next_key_p->data[2] == 1 &&
 664                next_key_p->data[3] == 128);
 665
 666         memcpy(key_p, next_key_p, key_size);
 667         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 668         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 669                next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
 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] == 128);
 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 == 16 && next_key_p->data[0] == 192 &&
 679                next_key_p->data[1] == 168);
 680
 681         memcpy(key_p, next_key_p, key_size);
 682         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 683                errno == ENOENT);
 684
 685         /* no exact matching key should return the first one in post order */
 686         key_p->prefixlen = 22;
 687         inet_pton(AF_INET, "192.168.1.0", key_p->data);
 688         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 689         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 690                next_key_p->data[1] == 168 && next_key_p->data[2] == 0);
 691
 692         close(map_fd);
 693 }
 694
 695 #define MAX_TEST_KEYS   4
 696 struct lpm_mt_test_info {
 697         int cmd; /* 0: update, 1: delete, 2: lookup, 3: get_next_key */
 698         int iter;
 699         int map_fd;
 700         struct {
 701                 __u32 prefixlen;
 702                 __u32 data;
 703         } key[MAX_TEST_KEYS];
 704 };
 705
 706 static void *lpm_test_command(void *arg)
 707 {
 708         int i, j, ret, iter, key_size;
 709         struct lpm_mt_test_info *info = arg;
 710         struct bpf_lpm_trie_key *key_p;
 711
 712         key_size = sizeof(struct bpf_lpm_trie_key) + sizeof(__u32);
 713         key_p = alloca(key_size);
 714         for (iter = 0; iter < info->iter; iter++)
 715                 for (i = 0; i < MAX_TEST_KEYS; i++) {
 716                         /* first half of iterations in forward order,
 717                          * and second half in backward order.
 718                          */
 719                         j = (iter < (info->iter / 2)) ? i : MAX_TEST_KEYS - i - 1;
 720                         key_p->prefixlen = info->key[j].prefixlen;
 721                         memcpy(key_p->data, &info->key[j].data, sizeof(__u32));
 722                         if (info->cmd == 0) {
 723                                 __u32 value = j;
 724                                 /* update must succeed */
 725                                 assert(bpf_map_update_elem(info->map_fd, key_p, &value, 0) == 0);
 726                         } else if (info->cmd == 1) {
 727                                 ret = bpf_map_delete_elem(info->map_fd, key_p);
 728                                 assert(ret == 0 || errno == ENOENT);
 729                         } else if (info->cmd == 2) {
 730                                 __u32 value;
 731                                 ret = bpf_map_lookup_elem(info->map_fd, key_p, &value);
 732                                 assert(ret == 0 || errno == ENOENT);
 733                         } else {
 734                                 struct bpf_lpm_trie_key *next_key_p = alloca(key_size);
 735                                 ret = bpf_map_get_next_key(info->map_fd, key_p, next_key_p);
 736                                 assert(ret == 0 || errno == ENOENT || errno == ENOMEM);
 737                         }
 738                 }
 739
 740         // Pass successful exit info back to the main thread
 741         pthread_exit((void *)info);
 742 }
 743
 744 static void setup_lpm_mt_test_info(struct lpm_mt_test_info *info, int map_fd)
 745 {
 746         info->iter = 2000;
 747         info->map_fd = map_fd;
 748         info->key[0].prefixlen = 16;
 749         inet_pton(AF_INET, "192.168.0.0", &info->key[0].data);
 750         info->key[1].prefixlen = 24;
 751         inet_pton(AF_INET, "192.168.0.0", &info->key[1].data);
 752         info->key[2].prefixlen = 24;
 753         inet_pton(AF_INET, "192.168.128.0", &info->key[2].data);
 754         info->key[3].prefixlen = 24;
 755         inet_pton(AF_INET, "192.168.1.0", &info->key[3].data);
 756 }
 757
 758 static void test_lpm_multi_thread(void)
 759 {
 760         LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
 761         struct lpm_mt_test_info info[4];
 762         size_t key_size, value_size;
 763         pthread_t thread_id[4];
 764         int i, map_fd;
 765         void *ret;
 766
 767         /* create a trie */
 768         value_size = sizeof(__u32);
 769         key_size = sizeof(struct bpf_lpm_trie_key) + value_size;
 770         map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, value_size, 100, &opts);
 771
 772         /* create 4 threads to test update, delete, lookup and get_next_key */
 773         setup_lpm_mt_test_info(&info[0], map_fd);
 774         for (i = 0; i < 4; i++) {
 775                 if (i != 0)
 776                         memcpy(&info[i], &info[0], sizeof(info[i]));
 777                 info[i].cmd = i;
 778                 assert(pthread_create(&thread_id[i], NULL, &lpm_test_command, &info[i]) == 0);
 779         }
 780
 781         for (i = 0; i < 4; i++)
 782                 assert(pthread_join(thread_id[i], &ret) == 0 && ret == (void *)&info[i]);
 783
 784         close(map_fd);
 785 }
 786
 787 int main(void)
 788 {
 789         int i;
 790
 791         /* we want predictable, pseudo random tests */
 792         srand(0xf00ba1);
 793
 794         test_lpm_basic();
 795         test_lpm_order();
 796
 797         /* Test with 8, 16, 24, 32, ... 128 bit prefix length */
 798         for (i = 1; i <= 16; ++i)
 799                 test_lpm_map(i);
 800
 801         test_lpm_ipaddr();
 802         test_lpm_delete();
 803         test_lpm_get_next_key();
 804         test_lpm_multi_thread();
 805
 806         printf("test_lpm: OK\n");
 807         return 0;
 808 }