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         size_t i, j, n_matches, n_matches_after_delete, n_nodes, n_lookups;
 212         struct tlpm_node *t, *list = NULL;
 213         struct bpf_lpm_trie_key *key;
 214         uint8_t *data, *value;
 215         int r, map;
 216
 217         /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of
 218          * prefixes and insert it into both tlpm and bpf-lpm. Then run some
 219          * randomized lookups and verify both maps return the same result.
 220          */
 221
 222         n_matches = 0;
 223         n_matches_after_delete = 0;
 224         n_nodes = 1 << 8;
 225         n_lookups = 1 << 16;
 226
 227         data = alloca(keysize);
 228         memset(data, 0, keysize);
 229
 230         value = alloca(keysize + 1);
 231         memset(value, 0, keysize + 1);
 232
 233         key = alloca(sizeof(*key) + keysize);
 234         memset(key, 0, sizeof(*key) + keysize);
 235
 236         map = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
 237                              sizeof(*key) + keysize,
 238                              keysize + 1,
 239                              4096,
 240                              BPF_F_NO_PREALLOC);
 241         assert(map >= 0);
 242
 243         for (i = 0; i < n_nodes; ++i) {
 244                 for (j = 0; j < keysize; ++j)
 245                         value[j] = rand() & 0xff;
 246                 value[keysize] = rand() % (8 * keysize + 1);
 247
 248                 list = tlpm_add(list, value, value[keysize]);
 249
 250                 key->prefixlen = value[keysize];
 251                 memcpy(key->data, value, keysize);
 252                 r = bpf_map_update_elem(map, key, value, 0);
 253                 assert(!r);
 254         }
 255
 256         for (i = 0; i < n_lookups; ++i) {
 257                 for (j = 0; j < keysize; ++j)
 258                         data[j] = rand() & 0xff;
 259
 260                 t = tlpm_match(list, data, 8 * keysize);
 261
 262                 key->prefixlen = 8 * keysize;
 263                 memcpy(key->data, data, keysize);
 264                 r = bpf_map_lookup_elem(map, key, value);
 265                 assert(!r || errno == ENOENT);
 266                 assert(!t == !!r);
 267
 268                 if (t) {
 269                         ++n_matches;
 270                         assert(t->n_bits == value[keysize]);
 271                         for (j = 0; j < t->n_bits; ++j)
 272                                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
 273                                        (value[j / 8] & (1 << (7 - j % 8))));
 274                 }
 275         }
 276
 277         /* Remove the first half of the elements in the tlpm and the
 278          * corresponding nodes from the bpf-lpm.  Then run the same
 279          * large number of random lookups in both and make sure they match.
 280          * Note: we need to count the number of nodes actually inserted
 281          * since there may have been duplicates.
 282          */
 283         for (i = 0, t = list; t; i++, t = t->next)
 284                 ;
 285         for (j = 0; j < i / 2; ++j) {
 286                 key->prefixlen = list->n_bits;
 287                 memcpy(key->data, list->key, keysize);
 288                 r = bpf_map_delete_elem(map, key);
 289                 assert(!r);
 290                 list = tlpm_delete(list, list->key, list->n_bits);
 291                 assert(list);
 292         }
 293         for (i = 0; i < n_lookups; ++i) {
 294                 for (j = 0; j < keysize; ++j)
 295                         data[j] = rand() & 0xff;
 296
 297                 t = tlpm_match(list, data, 8 * keysize);
 298
 299                 key->prefixlen = 8 * keysize;
 300                 memcpy(key->data, data, keysize);
 301                 r = bpf_map_lookup_elem(map, key, value);
 302                 assert(!r || errno == ENOENT);
 303                 assert(!t == !!r);
 304
 305                 if (t) {
 306                         ++n_matches_after_delete;
 307                         assert(t->n_bits == value[keysize]);
 308                         for (j = 0; j < t->n_bits; ++j)
 309                                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
 310                                        (value[j / 8] & (1 << (7 - j % 8))));
 311                 }
 312         }
 313
 314         close(map);
 315         tlpm_clear(list);
 316
 317         /* With 255 random nodes in the map, we are pretty likely to match
 318          * something on every lookup. For statistics, use this:
 319          *
 320          *     printf("          nodes: %zu\n"
 321          *            "        lookups: %zu\n"
 322          *            "        matches: %zu\n"
 323          *            "matches(delete): %zu\n",
 324          *            n_nodes, n_lookups, n_matches, n_matches_after_delete);
 325          */
 326 }
 327
 328 /* Test the implementation with some 'real world' examples */
 329
 330 static void test_lpm_ipaddr(void)
 331 {
 332         struct bpf_lpm_trie_key *key_ipv4;
 333         struct bpf_lpm_trie_key *key_ipv6;
 334         size_t key_size_ipv4;
 335         size_t key_size_ipv6;
 336         int map_fd_ipv4;
 337         int map_fd_ipv6;
 338         __u64 value;
 339
 340         key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32);
 341         key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4;
 342         key_ipv4 = alloca(key_size_ipv4);
 343         key_ipv6 = alloca(key_size_ipv6);
 344
 345         map_fd_ipv4 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
 346                                      key_size_ipv4, sizeof(value),
 347                                      100, BPF_F_NO_PREALLOC);
 348         assert(map_fd_ipv4 >= 0);
 349
 350         map_fd_ipv6 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
 351                                      key_size_ipv6, sizeof(value),
 352                                      100, BPF_F_NO_PREALLOC);
 353         assert(map_fd_ipv6 >= 0);
 354
 355         /* Fill data some IPv4 and IPv6 address ranges */
 356         value = 1;
 357         key_ipv4->prefixlen = 16;
 358         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
 359         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 360
 361         value = 2;
 362         key_ipv4->prefixlen = 24;
 363         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
 364         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 365
 366         value = 3;
 367         key_ipv4->prefixlen = 24;
 368         inet_pton(AF_INET, "192.168.128.0", key_ipv4->data);
 369         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 370
 371         value = 5;
 372         key_ipv4->prefixlen = 24;
 373         inet_pton(AF_INET, "192.168.1.0", key_ipv4->data);
 374         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
 375
 376         value = 4;
 377         key_ipv4->prefixlen = 23;
 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 = 0xdeadbeef;
 382         key_ipv6->prefixlen = 64;
 383         inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data);
 384         assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0);
 385
 386         /* Set tprefixlen to maximum for lookups */
 387         key_ipv4->prefixlen = 32;
 388         key_ipv6->prefixlen = 128;
 389
 390         /* Test some lookups that should come back with a value */
 391         inet_pton(AF_INET, "192.168.128.23", key_ipv4->data);
 392         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
 393         assert(value == 3);
 394
 395         inet_pton(AF_INET, "192.168.0.1", key_ipv4->data);
 396         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
 397         assert(value == 2);
 398
 399         inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data);
 400         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
 401         assert(value == 0xdeadbeef);
 402
 403         inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data);
 404         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
 405         assert(value == 0xdeadbeef);
 406
 407         /* Test some lookups that should not match any entry */
 408         inet_pton(AF_INET, "10.0.0.1", key_ipv4->data);
 409         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 &&
 410                errno == ENOENT);
 411
 412         inet_pton(AF_INET, "11.11.11.11", key_ipv4->data);
 413         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 &&
 414                errno == ENOENT);
 415
 416         inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data);
 417         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -1 &&
 418                errno == ENOENT);
 419
 420         close(map_fd_ipv4);
 421         close(map_fd_ipv6);
 422 }
 423
 424 static void test_lpm_delete(void)
 425 {
 426         struct bpf_lpm_trie_key *key;
 427         size_t key_size;
 428         int map_fd;
 429         __u64 value;
 430
 431         key_size = sizeof(*key) + sizeof(__u32);
 432         key = alloca(key_size);
 433
 434         map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
 435                                 key_size, sizeof(value),
 436                                 100, BPF_F_NO_PREALLOC);
 437         assert(map_fd >= 0);
 438
 439         /* Add nodes:
 440          * 192.168.0.0/16   (1)
 441          * 192.168.0.0/24   (2)
 442          * 192.168.128.0/24 (3)
 443          * 192.168.1.0/24   (4)
 444          *
 445          *         (1)
 446          *        /   \
 447          *     (IM)    (3)
 448          *    /   \
 449          *   (2)  (4)
 450          */
 451         value = 1;
 452         key->prefixlen = 16;
 453         inet_pton(AF_INET, "192.168.0.0", key->data);
 454         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 455
 456         value = 2;
 457         key->prefixlen = 24;
 458         inet_pton(AF_INET, "192.168.0.0", key->data);
 459         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 460
 461         value = 3;
 462         key->prefixlen = 24;
 463         inet_pton(AF_INET, "192.168.128.0", key->data);
 464         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 465
 466         value = 4;
 467         key->prefixlen = 24;
 468         inet_pton(AF_INET, "192.168.1.0", key->data);
 469         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
 470
 471         /* remove non-existent node */
 472         key->prefixlen = 32;
 473         inet_pton(AF_INET, "10.0.0.1", key->data);
 474         assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
 475                 errno == ENOENT);
 476
 477         key->prefixlen = 30; // unused prefix so far
 478         inet_pton(AF_INET, "192.255.0.0", key->data);
 479         assert(bpf_map_delete_elem(map_fd, key) == -1 &&
 480                 errno == ENOENT);
 481
 482         key->prefixlen = 16; // same prefix as the root node
 483         inet_pton(AF_INET, "192.255.0.0", key->data);
 484         assert(bpf_map_delete_elem(map_fd, key) == -1 &&
 485                 errno == ENOENT);
 486
 487         /* assert initial lookup */
 488         key->prefixlen = 32;
 489         inet_pton(AF_INET, "192.168.0.1", key->data);
 490         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 491         assert(value == 2);
 492
 493         /* remove leaf node */
 494         key->prefixlen = 24;
 495         inet_pton(AF_INET, "192.168.0.0", key->data);
 496         assert(bpf_map_delete_elem(map_fd, key) == 0);
 497
 498         key->prefixlen = 32;
 499         inet_pton(AF_INET, "192.168.0.1", key->data);
 500         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 501         assert(value == 1);
 502
 503         /* remove leaf (and intermediary) node */
 504         key->prefixlen = 24;
 505         inet_pton(AF_INET, "192.168.1.0", key->data);
 506         assert(bpf_map_delete_elem(map_fd, key) == 0);
 507
 508         key->prefixlen = 32;
 509         inet_pton(AF_INET, "192.168.1.1", key->data);
 510         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 511         assert(value == 1);
 512
 513         /* remove root node */
 514         key->prefixlen = 16;
 515         inet_pton(AF_INET, "192.168.0.0", key->data);
 516         assert(bpf_map_delete_elem(map_fd, key) == 0);
 517
 518         key->prefixlen = 32;
 519         inet_pton(AF_INET, "192.168.128.1", key->data);
 520         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
 521         assert(value == 3);
 522
 523         /* remove last node */
 524         key->prefixlen = 24;
 525         inet_pton(AF_INET, "192.168.128.0", key->data);
 526         assert(bpf_map_delete_elem(map_fd, key) == 0);
 527
 528         key->prefixlen = 32;
 529         inet_pton(AF_INET, "192.168.128.1", key->data);
 530         assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
 531                 errno == ENOENT);
 532
 533         close(map_fd);
 534 }
 535
 536 static void test_lpm_get_next_key(void)
 537 {
 538         struct bpf_lpm_trie_key *key_p, *next_key_p;
 539         size_t key_size;
 540         __u32 value = 0;
 541         int map_fd;
 542
 543         key_size = sizeof(*key_p) + sizeof(__u32);
 544         key_p = alloca(key_size);
 545         next_key_p = alloca(key_size);
 546
 547         map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, key_size, sizeof(value),
 548                                 100, BPF_F_NO_PREALLOC);
 549         assert(map_fd >= 0);
 550
 551         /* empty tree. get_next_key should return ENOENT */
 552         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -1 &&
 553                errno == ENOENT);
 554
 555         /* get and verify the first key, get the second one should fail. */
 556         key_p->prefixlen = 16;
 557         inet_pton(AF_INET, "192.168.0.0", key_p->data);
 558         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 559
 560         memset(key_p, 0, key_size);
 561         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 562         assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
 563                key_p->data[1] == 168);
 564
 565         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 566                errno == ENOENT);
 567
 568         /* no exact matching key should get the first one in post order. */
 569         key_p->prefixlen = 8;
 570         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 571         assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
 572                key_p->data[1] == 168);
 573
 574         /* add one more element (total two) */
 575         key_p->prefixlen = 24;
 576         inet_pton(AF_INET, "192.168.128.0", key_p->data);
 577         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 578
 579         memset(key_p, 0, key_size);
 580         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 581         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 582                key_p->data[1] == 168 && key_p->data[2] == 128);
 583
 584         memset(next_key_p, 0, key_size);
 585         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 586         assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
 587                next_key_p->data[1] == 168);
 588
 589         memcpy(key_p, next_key_p, key_size);
 590         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 591                errno == ENOENT);
 592
 593         /* Add one more element (total three) */
 594         key_p->prefixlen = 24;
 595         inet_pton(AF_INET, "192.168.0.0", key_p->data);
 596         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 597
 598         memset(key_p, 0, key_size);
 599         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 600         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 601                key_p->data[1] == 168 && key_p->data[2] == 0);
 602
 603         memset(next_key_p, 0, key_size);
 604         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 605         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 606                next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
 607
 608         memcpy(key_p, next_key_p, key_size);
 609         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 610         assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
 611                next_key_p->data[1] == 168);
 612
 613         memcpy(key_p, next_key_p, key_size);
 614         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 615                errno == ENOENT);
 616
 617         /* Add one more element (total four) */
 618         key_p->prefixlen = 24;
 619         inet_pton(AF_INET, "192.168.1.0", key_p->data);
 620         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 621
 622         memset(key_p, 0, key_size);
 623         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 624         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 625                key_p->data[1] == 168 && key_p->data[2] == 0);
 626
 627         memset(next_key_p, 0, key_size);
 628         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 629         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 630                next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
 631
 632         memcpy(key_p, next_key_p, key_size);
 633         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 634         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 635                next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
 636
 637         memcpy(key_p, next_key_p, key_size);
 638         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 639         assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
 640                next_key_p->data[1] == 168);
 641
 642         memcpy(key_p, next_key_p, key_size);
 643         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 644                errno == ENOENT);
 645
 646         /* Add one more element (total five) */
 647         key_p->prefixlen = 28;
 648         inet_pton(AF_INET, "192.168.1.128", key_p->data);
 649         assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
 650
 651         memset(key_p, 0, key_size);
 652         assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
 653         assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
 654                key_p->data[1] == 168 && key_p->data[2] == 0);
 655
 656         memset(next_key_p, 0, key_size);
 657         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 658         assert(next_key_p->prefixlen == 28 && next_key_p->data[0] == 192 &&
 659                next_key_p->data[1] == 168 && next_key_p->data[2] == 1 &&
 660                next_key_p->data[3] == 128);
 661
 662         memcpy(key_p, next_key_p, key_size);
 663         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 664         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 665                next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
 666
 667         memcpy(key_p, next_key_p, key_size);
 668         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 669         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 670                next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
 671
 672         memcpy(key_p, next_key_p, key_size);
 673         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 674         assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
 675                next_key_p->data[1] == 168);
 676
 677         memcpy(key_p, next_key_p, key_size);
 678         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 679                errno == ENOENT);
 680
 681         /* no exact matching key should return the first one in post order */
 682         key_p->prefixlen = 22;
 683         inet_pton(AF_INET, "192.168.1.0", key_p->data);
 684         assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
 685         assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
 686                next_key_p->data[1] == 168 && next_key_p->data[2] == 0);
 687
 688         close(map_fd);
 689 }
 690
 691 #define MAX_TEST_KEYS   4
 692 struct lpm_mt_test_info {
 693         int cmd; /* 0: update, 1: delete, 2: lookup, 3: get_next_key */
 694         int iter;
 695         int map_fd;
 696         struct {
 697                 __u32 prefixlen;
 698                 __u32 data;
 699         } key[MAX_TEST_KEYS];
 700 };
 701
 702 static void *lpm_test_command(void *arg)
 703 {
 704         int i, j, ret, iter, key_size;
 705         struct lpm_mt_test_info *info = arg;
 706         struct bpf_lpm_trie_key *key_p;
 707
 708         key_size = sizeof(struct bpf_lpm_trie_key) + sizeof(__u32);
 709         key_p = alloca(key_size);
 710         for (iter = 0; iter < info->iter; iter++)
 711                 for (i = 0; i < MAX_TEST_KEYS; i++) {
 712                         /* first half of iterations in forward order,
 713                          * and second half in backward order.
 714                          */
 715                         j = (iter < (info->iter / 2)) ? i : MAX_TEST_KEYS - i - 1;
 716                         key_p->prefixlen = info->key[j].prefixlen;
 717                         memcpy(key_p->data, &info->key[j].data, sizeof(__u32));
 718                         if (info->cmd == 0) {
 719                                 __u32 value = j;
 720                                 /* update must succeed */
 721                                 assert(bpf_map_update_elem(info->map_fd, key_p, &value, 0) == 0);
 722                         } else if (info->cmd == 1) {
 723                                 ret = bpf_map_delete_elem(info->map_fd, key_p);
 724                                 assert(ret == 0 || errno == ENOENT);
 725                         } else if (info->cmd == 2) {
 726                                 __u32 value;
 727                                 ret = bpf_map_lookup_elem(info->map_fd, key_p, &value);
 728                                 assert(ret == 0 || errno == ENOENT);
 729                         } else {
 730                                 struct bpf_lpm_trie_key *next_key_p = alloca(key_size);
 731                                 ret = bpf_map_get_next_key(info->map_fd, key_p, next_key_p);
 732                                 assert(ret == 0 || errno == ENOENT || errno == ENOMEM);
 733                         }
 734                 }
 735
 736         // Pass successful exit info back to the main thread
 737         pthread_exit((void *)info);
 738 }
 739
 740 static void setup_lpm_mt_test_info(struct lpm_mt_test_info *info, int map_fd)
 741 {
 742         info->iter = 2000;
 743         info->map_fd = map_fd;
 744         info->key[0].prefixlen = 16;
 745         inet_pton(AF_INET, "192.168.0.0", &info->key[0].data);
 746         info->key[1].prefixlen = 24;
 747         inet_pton(AF_INET, "192.168.0.0", &info->key[1].data);
 748         info->key[2].prefixlen = 24;
 749         inet_pton(AF_INET, "192.168.128.0", &info->key[2].data);
 750         info->key[3].prefixlen = 24;
 751         inet_pton(AF_INET, "192.168.1.0", &info->key[3].data);
 752 }
 753
 754 static void test_lpm_multi_thread(void)
 755 {
 756         struct lpm_mt_test_info info[4];
 757         size_t key_size, value_size;
 758         pthread_t thread_id[4];
 759         int i, map_fd;
 760         void *ret;
 761
 762         /* create a trie */
 763         value_size = sizeof(__u32);
 764         key_size = sizeof(struct bpf_lpm_trie_key) + value_size;
 765         map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, key_size, value_size,
 766                                 100, BPF_F_NO_PREALLOC);
 767
 768         /* create 4 threads to test update, delete, lookup and get_next_key */
 769         setup_lpm_mt_test_info(&info[0], map_fd);
 770         for (i = 0; i < 4; i++) {
 771                 if (i != 0)
 772                         memcpy(&info[i], &info[0], sizeof(info[i]));
 773                 info[i].cmd = i;
 774                 assert(pthread_create(&thread_id[i], NULL, &lpm_test_command, &info[i]) == 0);
 775         }
 776
 777         for (i = 0; i < 4; i++)
 778                 assert(pthread_join(thread_id[i], &ret) == 0 && ret == (void *)&info[i]);
 779
 780         close(map_fd);
 781 }
 782
 783 int main(void)
 784 {
 785         int i;
 786
 787         /* we want predictable, pseudo random tests */
 788         srand(0xf00ba1);
 789
 790         test_lpm_basic();
 791         test_lpm_order();
 792
 793         /* Test with 8, 16, 24, 32, ... 128 bit prefix length */
 794         for (i = 1; i <= 16; ++i)
 795                 test_lpm_map(i);
 796
 797         test_lpm_ipaddr();
 798         test_lpm_delete();
 799         test_lpm_get_next_key();
 800         test_lpm_multi_thread();
 801
 802         printf("test_lpm: OK\n");
 803         return 0;
 804 }