Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Randomized tests for eBPF longest-prefix-match maps
0004  *
0005  * This program runs randomized tests against the lpm-bpf-map. It implements a
0006  * "Trivial Longest Prefix Match" (tlpm) based on simple, linear, singly linked
0007  * lists. The implementation should be pretty straightforward.
0008  *
0009  * Based on tlpm, this inserts randomized data into bpf-lpm-maps and verifies
0010  * the trie-based bpf-map implementation behaves the same way as tlpm.
0011  */
0012 
0013 #include <assert.h>
0014 #include <errno.h>
0015 #include <inttypes.h>
0016 #include <linux/bpf.h>
0017 #include <pthread.h>
0018 #include <stdio.h>
0019 #include <stdlib.h>
0020 #include <string.h>
0021 #include <time.h>
0022 #include <unistd.h>
0023 #include <arpa/inet.h>
0024 #include <sys/time.h>
0025 
0026 #include <bpf/bpf.h>
0027 
0028 #include "bpf_util.h"
0029 
0030 struct tlpm_node {
0031     struct tlpm_node *next;
0032     size_t n_bits;
0033     uint8_t key[];
0034 };
0035 
0036 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
0037                     const uint8_t *key,
0038                     size_t n_bits);
0039 
0040 static struct tlpm_node *tlpm_add(struct tlpm_node *list,
0041                   const uint8_t *key,
0042                   size_t n_bits)
0043 {
0044     struct tlpm_node *node;
0045     size_t n;
0046 
0047     n = (n_bits + 7) / 8;
0048 
0049     /* 'overwrite' an equivalent entry if one already exists */
0050     node = tlpm_match(list, key, n_bits);
0051     if (node && node->n_bits == n_bits) {
0052         memcpy(node->key, key, n);
0053         return list;
0054     }
0055 
0056     /* add new entry with @key/@n_bits to @list and return new head */
0057 
0058     node = malloc(sizeof(*node) + n);
0059     assert(node);
0060 
0061     node->next = list;
0062     node->n_bits = n_bits;
0063     memcpy(node->key, key, n);
0064 
0065     return node;
0066 }
0067 
0068 static void tlpm_clear(struct tlpm_node *list)
0069 {
0070     struct tlpm_node *node;
0071 
0072     /* free all entries in @list */
0073 
0074     while ((node = list)) {
0075         list = list->next;
0076         free(node);
0077     }
0078 }
0079 
0080 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
0081                     const uint8_t *key,
0082                     size_t n_bits)
0083 {
0084     struct tlpm_node *best = NULL;
0085     size_t i;
0086 
0087     /* Perform longest prefix-match on @key/@n_bits. That is, iterate all
0088      * entries and match each prefix against @key. Remember the "best"
0089      * entry we find (i.e., the longest prefix that matches) and return it
0090      * to the caller when done.
0091      */
0092 
0093     for ( ; list; list = list->next) {
0094         for (i = 0; i < n_bits && i < list->n_bits; ++i) {
0095             if ((key[i / 8] & (1 << (7 - i % 8))) !=
0096                 (list->key[i / 8] & (1 << (7 - i % 8))))
0097                 break;
0098         }
0099 
0100         if (i >= list->n_bits) {
0101             if (!best || i > best->n_bits)
0102                 best = list;
0103         }
0104     }
0105 
0106     return best;
0107 }
0108 
0109 static struct tlpm_node *tlpm_delete(struct tlpm_node *list,
0110                      const uint8_t *key,
0111                      size_t n_bits)
0112 {
0113     struct tlpm_node *best = tlpm_match(list, key, n_bits);
0114     struct tlpm_node *node;
0115 
0116     if (!best || best->n_bits != n_bits)
0117         return list;
0118 
0119     if (best == list) {
0120         node = best->next;
0121         free(best);
0122         return node;
0123     }
0124 
0125     for (node = list; node; node = node->next) {
0126         if (node->next == best) {
0127             node->next = best->next;
0128             free(best);
0129             return list;
0130         }
0131     }
0132     /* should never get here */
0133     assert(0);
0134     return list;
0135 }
0136 
0137 static void test_lpm_basic(void)
0138 {
0139     struct tlpm_node *list = NULL, *t1, *t2;
0140 
0141     /* very basic, static tests to verify tlpm works as expected */
0142 
0143     assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
0144 
0145     t1 = list = tlpm_add(list, (uint8_t[]){ 0xff }, 8);
0146     assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
0147     assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
0148     assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0x00 }, 16));
0149     assert(!tlpm_match(list, (uint8_t[]){ 0x7f }, 8));
0150     assert(!tlpm_match(list, (uint8_t[]){ 0xfe }, 8));
0151     assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 7));
0152 
0153     t2 = list = tlpm_add(list, (uint8_t[]){ 0xff, 0xff }, 16);
0154     assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
0155     assert(t2 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
0156     assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15));
0157     assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16));
0158 
0159     list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16);
0160     assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
0161     assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
0162 
0163     list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8);
0164     assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
0165 
0166     tlpm_clear(list);
0167 }
0168 
0169 static void test_lpm_order(void)
0170 {
0171     struct tlpm_node *t1, *t2, *l1 = NULL, *l2 = NULL;
0172     size_t i, j;
0173 
0174     /* Verify the tlpm implementation works correctly regardless of the
0175      * order of entries. Insert a random set of entries into @l1, and copy
0176      * the same data in reverse order into @l2. Then verify a lookup of
0177      * random keys will yield the same result in both sets.
0178      */
0179 
0180     for (i = 0; i < (1 << 12); ++i)
0181         l1 = tlpm_add(l1, (uint8_t[]){
0182                     rand() % 0xff,
0183                     rand() % 0xff,
0184                 }, rand() % 16 + 1);
0185 
0186     for (t1 = l1; t1; t1 = t1->next)
0187         l2 = tlpm_add(l2, t1->key, t1->n_bits);
0188 
0189     for (i = 0; i < (1 << 8); ++i) {
0190         uint8_t key[] = { rand() % 0xff, rand() % 0xff };
0191 
0192         t1 = tlpm_match(l1, key, 16);
0193         t2 = tlpm_match(l2, key, 16);
0194 
0195         assert(!t1 == !t2);
0196         if (t1) {
0197             assert(t1->n_bits == t2->n_bits);
0198             for (j = 0; j < t1->n_bits; ++j)
0199                 assert((t1->key[j / 8] & (1 << (7 - j % 8))) ==
0200                        (t2->key[j / 8] & (1 << (7 - j % 8))));
0201         }
0202     }
0203 
0204     tlpm_clear(l1);
0205     tlpm_clear(l2);
0206 }
0207 
0208 static void test_lpm_map(int keysize)
0209 {
0210     LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
0211     volatile size_t n_matches, n_matches_after_delete;
0212     size_t i, j, n_nodes, n_lookups;
0213     struct tlpm_node *t, *list = NULL;
0214     struct bpf_lpm_trie_key *key;
0215     uint8_t *data, *value;
0216     int r, map;
0217 
0218     /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of
0219      * prefixes and insert it into both tlpm and bpf-lpm. Then run some
0220      * randomized lookups and verify both maps return the same result.
0221      */
0222 
0223     n_matches = 0;
0224     n_matches_after_delete = 0;
0225     n_nodes = 1 << 8;
0226     n_lookups = 1 << 16;
0227 
0228     data = alloca(keysize);
0229     memset(data, 0, keysize);
0230 
0231     value = alloca(keysize + 1);
0232     memset(value, 0, keysize + 1);
0233 
0234     key = alloca(sizeof(*key) + keysize);
0235     memset(key, 0, sizeof(*key) + keysize);
0236 
0237     map = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
0238                  sizeof(*key) + keysize,
0239                  keysize + 1,
0240                  4096,
0241                  &opts);
0242     assert(map >= 0);
0243 
0244     for (i = 0; i < n_nodes; ++i) {
0245         for (j = 0; j < keysize; ++j)
0246             value[j] = rand() & 0xff;
0247         value[keysize] = rand() % (8 * keysize + 1);
0248 
0249         list = tlpm_add(list, value, value[keysize]);
0250 
0251         key->prefixlen = value[keysize];
0252         memcpy(key->data, value, keysize);
0253         r = bpf_map_update_elem(map, key, value, 0);
0254         assert(!r);
0255     }
0256 
0257     for (i = 0; i < n_lookups; ++i) {
0258         for (j = 0; j < keysize; ++j)
0259             data[j] = rand() & 0xff;
0260 
0261         t = tlpm_match(list, data, 8 * keysize);
0262 
0263         key->prefixlen = 8 * keysize;
0264         memcpy(key->data, data, keysize);
0265         r = bpf_map_lookup_elem(map, key, value);
0266         assert(!r || errno == ENOENT);
0267         assert(!t == !!r);
0268 
0269         if (t) {
0270             ++n_matches;
0271             assert(t->n_bits == value[keysize]);
0272             for (j = 0; j < t->n_bits; ++j)
0273                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
0274                        (value[j / 8] & (1 << (7 - j % 8))));
0275         }
0276     }
0277 
0278     /* Remove the first half of the elements in the tlpm and the
0279      * corresponding nodes from the bpf-lpm.  Then run the same
0280      * large number of random lookups in both and make sure they match.
0281      * Note: we need to count the number of nodes actually inserted
0282      * since there may have been duplicates.
0283      */
0284     for (i = 0, t = list; t; i++, t = t->next)
0285         ;
0286     for (j = 0; j < i / 2; ++j) {
0287         key->prefixlen = list->n_bits;
0288         memcpy(key->data, list->key, keysize);
0289         r = bpf_map_delete_elem(map, key);
0290         assert(!r);
0291         list = tlpm_delete(list, list->key, list->n_bits);
0292         assert(list);
0293     }
0294     for (i = 0; i < n_lookups; ++i) {
0295         for (j = 0; j < keysize; ++j)
0296             data[j] = rand() & 0xff;
0297 
0298         t = tlpm_match(list, data, 8 * keysize);
0299 
0300         key->prefixlen = 8 * keysize;
0301         memcpy(key->data, data, keysize);
0302         r = bpf_map_lookup_elem(map, key, value);
0303         assert(!r || errno == ENOENT);
0304         assert(!t == !!r);
0305 
0306         if (t) {
0307             ++n_matches_after_delete;
0308             assert(t->n_bits == value[keysize]);
0309             for (j = 0; j < t->n_bits; ++j)
0310                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
0311                        (value[j / 8] & (1 << (7 - j % 8))));
0312         }
0313     }
0314 
0315     close(map);
0316     tlpm_clear(list);
0317 
0318     /* With 255 random nodes in the map, we are pretty likely to match
0319      * something on every lookup. For statistics, use this:
0320      *
0321      *     printf("          nodes: %zu\n"
0322      *            "        lookups: %zu\n"
0323      *            "        matches: %zu\n"
0324      *            "matches(delete): %zu\n",
0325      *            n_nodes, n_lookups, n_matches, n_matches_after_delete);
0326      */
0327 }
0328 
0329 /* Test the implementation with some 'real world' examples */
0330 
0331 static void test_lpm_ipaddr(void)
0332 {
0333     LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
0334     struct bpf_lpm_trie_key *key_ipv4;
0335     struct bpf_lpm_trie_key *key_ipv6;
0336     size_t key_size_ipv4;
0337     size_t key_size_ipv6;
0338     int map_fd_ipv4;
0339     int map_fd_ipv6;
0340     __u64 value;
0341 
0342     key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32);
0343     key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4;
0344     key_ipv4 = alloca(key_size_ipv4);
0345     key_ipv6 = alloca(key_size_ipv6);
0346 
0347     map_fd_ipv4 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
0348                      key_size_ipv4, sizeof(value),
0349                      100, &opts);
0350     assert(map_fd_ipv4 >= 0);
0351 
0352     map_fd_ipv6 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
0353                      key_size_ipv6, sizeof(value),
0354                      100, &opts);
0355     assert(map_fd_ipv6 >= 0);
0356 
0357     /* Fill data some IPv4 and IPv6 address ranges */
0358     value = 1;
0359     key_ipv4->prefixlen = 16;
0360     inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
0361     assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
0362 
0363     value = 2;
0364     key_ipv4->prefixlen = 24;
0365     inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
0366     assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
0367 
0368     value = 3;
0369     key_ipv4->prefixlen = 24;
0370     inet_pton(AF_INET, "192.168.128.0", key_ipv4->data);
0371     assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
0372 
0373     value = 5;
0374     key_ipv4->prefixlen = 24;
0375     inet_pton(AF_INET, "192.168.1.0", key_ipv4->data);
0376     assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
0377 
0378     value = 4;
0379     key_ipv4->prefixlen = 23;
0380     inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
0381     assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
0382 
0383     value = 0xdeadbeef;
0384     key_ipv6->prefixlen = 64;
0385     inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data);
0386     assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0);
0387 
0388     /* Set tprefixlen to maximum for lookups */
0389     key_ipv4->prefixlen = 32;
0390     key_ipv6->prefixlen = 128;
0391 
0392     /* Test some lookups that should come back with a value */
0393     inet_pton(AF_INET, "192.168.128.23", key_ipv4->data);
0394     assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
0395     assert(value == 3);
0396 
0397     inet_pton(AF_INET, "192.168.0.1", key_ipv4->data);
0398     assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
0399     assert(value == 2);
0400 
0401     inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data);
0402     assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
0403     assert(value == 0xdeadbeef);
0404 
0405     inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data);
0406     assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
0407     assert(value == 0xdeadbeef);
0408 
0409     /* Test some lookups that should not match any entry */
0410     inet_pton(AF_INET, "10.0.0.1", key_ipv4->data);
0411     assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT);
0412 
0413     inet_pton(AF_INET, "11.11.11.11", key_ipv4->data);
0414     assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT);
0415 
0416     inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data);
0417     assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -ENOENT);
0418 
0419     close(map_fd_ipv4);
0420     close(map_fd_ipv6);
0421 }
0422 
0423 static void test_lpm_delete(void)
0424 {
0425     LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
0426     struct bpf_lpm_trie_key *key;
0427     size_t key_size;
0428     int map_fd;
0429     __u64 value;
0430 
0431     key_size = sizeof(*key) + sizeof(__u32);
0432     key = alloca(key_size);
0433 
0434     map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL,
0435                 key_size, sizeof(value),
0436                 100, &opts);
0437     assert(map_fd >= 0);
0438 
0439     /* Add nodes:
0440      * 192.168.0.0/16   (1)
0441      * 192.168.0.0/24   (2)
0442      * 192.168.128.0/24 (3)
0443      * 192.168.1.0/24   (4)
0444      *
0445      *         (1)
0446      *        /   \
0447          *     (IM)    (3)
0448      *    /   \
0449          *   (2)  (4)
0450      */
0451     value = 1;
0452     key->prefixlen = 16;
0453     inet_pton(AF_INET, "192.168.0.0", key->data);
0454     assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
0455 
0456     value = 2;
0457     key->prefixlen = 24;
0458     inet_pton(AF_INET, "192.168.0.0", key->data);
0459     assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
0460 
0461     value = 3;
0462     key->prefixlen = 24;
0463     inet_pton(AF_INET, "192.168.128.0", key->data);
0464     assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
0465 
0466     value = 4;
0467     key->prefixlen = 24;
0468     inet_pton(AF_INET, "192.168.1.0", key->data);
0469     assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
0470 
0471     /* remove non-existent node */
0472     key->prefixlen = 32;
0473     inet_pton(AF_INET, "10.0.0.1", key->data);
0474     assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT);
0475 
0476     key->prefixlen = 30; // unused prefix so far
0477     inet_pton(AF_INET, "192.255.0.0", key->data);
0478     assert(bpf_map_delete_elem(map_fd, key) == -ENOENT);
0479 
0480     key->prefixlen = 16; // same prefix as the root node
0481     inet_pton(AF_INET, "192.255.0.0", key->data);
0482     assert(bpf_map_delete_elem(map_fd, key) == -ENOENT);
0483 
0484     /* assert initial lookup */
0485     key->prefixlen = 32;
0486     inet_pton(AF_INET, "192.168.0.1", key->data);
0487     assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
0488     assert(value == 2);
0489 
0490     /* remove leaf node */
0491     key->prefixlen = 24;
0492     inet_pton(AF_INET, "192.168.0.0", key->data);
0493     assert(bpf_map_delete_elem(map_fd, key) == 0);
0494 
0495     key->prefixlen = 32;
0496     inet_pton(AF_INET, "192.168.0.1", key->data);
0497     assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
0498     assert(value == 1);
0499 
0500     /* remove leaf (and intermediary) node */
0501     key->prefixlen = 24;
0502     inet_pton(AF_INET, "192.168.1.0", key->data);
0503     assert(bpf_map_delete_elem(map_fd, key) == 0);
0504 
0505     key->prefixlen = 32;
0506     inet_pton(AF_INET, "192.168.1.1", key->data);
0507     assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
0508     assert(value == 1);
0509 
0510     /* remove root node */
0511     key->prefixlen = 16;
0512     inet_pton(AF_INET, "192.168.0.0", key->data);
0513     assert(bpf_map_delete_elem(map_fd, key) == 0);
0514 
0515     key->prefixlen = 32;
0516     inet_pton(AF_INET, "192.168.128.1", key->data);
0517     assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
0518     assert(value == 3);
0519 
0520     /* remove last node */
0521     key->prefixlen = 24;
0522     inet_pton(AF_INET, "192.168.128.0", key->data);
0523     assert(bpf_map_delete_elem(map_fd, key) == 0);
0524 
0525     key->prefixlen = 32;
0526     inet_pton(AF_INET, "192.168.128.1", key->data);
0527     assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT);
0528 
0529     close(map_fd);
0530 }
0531 
0532 static void test_lpm_get_next_key(void)
0533 {
0534     LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
0535     struct bpf_lpm_trie_key *key_p, *next_key_p;
0536     size_t key_size;
0537     __u32 value = 0;
0538     int map_fd;
0539 
0540     key_size = sizeof(*key_p) + sizeof(__u32);
0541     key_p = alloca(key_size);
0542     next_key_p = alloca(key_size);
0543 
0544     map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, sizeof(value), 100, &opts);
0545     assert(map_fd >= 0);
0546 
0547     /* empty tree. get_next_key should return ENOENT */
0548     assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -ENOENT);
0549 
0550     /* get and verify the first key, get the second one should fail. */
0551     key_p->prefixlen = 16;
0552     inet_pton(AF_INET, "192.168.0.0", key_p->data);
0553     assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
0554 
0555     memset(key_p, 0, key_size);
0556     assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
0557     assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
0558            key_p->data[1] == 168);
0559 
0560     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
0561 
0562     /* no exact matching key should get the first one in post order. */
0563     key_p->prefixlen = 8;
0564     assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
0565     assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
0566            key_p->data[1] == 168);
0567 
0568     /* add one more element (total two) */
0569     key_p->prefixlen = 24;
0570     inet_pton(AF_INET, "192.168.128.0", key_p->data);
0571     assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
0572 
0573     memset(key_p, 0, key_size);
0574     assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
0575     assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
0576            key_p->data[1] == 168 && key_p->data[2] == 128);
0577 
0578     memset(next_key_p, 0, key_size);
0579     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0580     assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
0581            next_key_p->data[1] == 168);
0582 
0583     memcpy(key_p, next_key_p, key_size);
0584     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
0585 
0586     /* Add one more element (total three) */
0587     key_p->prefixlen = 24;
0588     inet_pton(AF_INET, "192.168.0.0", key_p->data);
0589     assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
0590 
0591     memset(key_p, 0, key_size);
0592     assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
0593     assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
0594            key_p->data[1] == 168 && key_p->data[2] == 0);
0595 
0596     memset(next_key_p, 0, key_size);
0597     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0598     assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
0599            next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
0600 
0601     memcpy(key_p, next_key_p, key_size);
0602     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0603     assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
0604            next_key_p->data[1] == 168);
0605 
0606     memcpy(key_p, next_key_p, key_size);
0607     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
0608 
0609     /* Add one more element (total four) */
0610     key_p->prefixlen = 24;
0611     inet_pton(AF_INET, "192.168.1.0", key_p->data);
0612     assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
0613 
0614     memset(key_p, 0, key_size);
0615     assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
0616     assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
0617            key_p->data[1] == 168 && key_p->data[2] == 0);
0618 
0619     memset(next_key_p, 0, key_size);
0620     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0621     assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
0622            next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
0623 
0624     memcpy(key_p, next_key_p, key_size);
0625     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0626     assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
0627            next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
0628 
0629     memcpy(key_p, next_key_p, key_size);
0630     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0631     assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
0632            next_key_p->data[1] == 168);
0633 
0634     memcpy(key_p, next_key_p, key_size);
0635     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
0636 
0637     /* Add one more element (total five) */
0638     key_p->prefixlen = 28;
0639     inet_pton(AF_INET, "192.168.1.128", key_p->data);
0640     assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
0641 
0642     memset(key_p, 0, key_size);
0643     assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
0644     assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
0645            key_p->data[1] == 168 && key_p->data[2] == 0);
0646 
0647     memset(next_key_p, 0, key_size);
0648     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0649     assert(next_key_p->prefixlen == 28 && next_key_p->data[0] == 192 &&
0650            next_key_p->data[1] == 168 && next_key_p->data[2] == 1 &&
0651            next_key_p->data[3] == 128);
0652 
0653     memcpy(key_p, next_key_p, key_size);
0654     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0655     assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
0656            next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
0657 
0658     memcpy(key_p, next_key_p, key_size);
0659     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0660     assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
0661            next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
0662 
0663     memcpy(key_p, next_key_p, key_size);
0664     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0665     assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
0666            next_key_p->data[1] == 168);
0667 
0668     memcpy(key_p, next_key_p, key_size);
0669     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT);
0670 
0671     /* no exact matching key should return the first one in post order */
0672     key_p->prefixlen = 22;
0673     inet_pton(AF_INET, "192.168.1.0", key_p->data);
0674     assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
0675     assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
0676            next_key_p->data[1] == 168 && next_key_p->data[2] == 0);
0677 
0678     close(map_fd);
0679 }
0680 
0681 #define MAX_TEST_KEYS   4
0682 struct lpm_mt_test_info {
0683     int cmd; /* 0: update, 1: delete, 2: lookup, 3: get_next_key */
0684     int iter;
0685     int map_fd;
0686     struct {
0687         __u32 prefixlen;
0688         __u32 data;
0689     } key[MAX_TEST_KEYS];
0690 };
0691 
0692 static void *lpm_test_command(void *arg)
0693 {
0694     int i, j, ret, iter, key_size;
0695     struct lpm_mt_test_info *info = arg;
0696     struct bpf_lpm_trie_key *key_p;
0697 
0698     key_size = sizeof(struct bpf_lpm_trie_key) + sizeof(__u32);
0699     key_p = alloca(key_size);
0700     for (iter = 0; iter < info->iter; iter++)
0701         for (i = 0; i < MAX_TEST_KEYS; i++) {
0702             /* first half of iterations in forward order,
0703              * and second half in backward order.
0704              */
0705             j = (iter < (info->iter / 2)) ? i : MAX_TEST_KEYS - i - 1;
0706             key_p->prefixlen = info->key[j].prefixlen;
0707             memcpy(key_p->data, &info->key[j].data, sizeof(__u32));
0708             if (info->cmd == 0) {
0709                 __u32 value = j;
0710                 /* update must succeed */
0711                 assert(bpf_map_update_elem(info->map_fd, key_p, &value, 0) == 0);
0712             } else if (info->cmd == 1) {
0713                 ret = bpf_map_delete_elem(info->map_fd, key_p);
0714                 assert(ret == 0 || errno == ENOENT);
0715             } else if (info->cmd == 2) {
0716                 __u32 value;
0717                 ret = bpf_map_lookup_elem(info->map_fd, key_p, &value);
0718                 assert(ret == 0 || errno == ENOENT);
0719             } else {
0720                 struct bpf_lpm_trie_key *next_key_p = alloca(key_size);
0721                 ret = bpf_map_get_next_key(info->map_fd, key_p, next_key_p);
0722                 assert(ret == 0 || errno == ENOENT || errno == ENOMEM);
0723             }
0724         }
0725 
0726     // Pass successful exit info back to the main thread
0727     pthread_exit((void *)info);
0728 }
0729 
0730 static void setup_lpm_mt_test_info(struct lpm_mt_test_info *info, int map_fd)
0731 {
0732     info->iter = 2000;
0733     info->map_fd = map_fd;
0734     info->key[0].prefixlen = 16;
0735     inet_pton(AF_INET, "192.168.0.0", &info->key[0].data);
0736     info->key[1].prefixlen = 24;
0737     inet_pton(AF_INET, "192.168.0.0", &info->key[1].data);
0738     info->key[2].prefixlen = 24;
0739     inet_pton(AF_INET, "192.168.128.0", &info->key[2].data);
0740     info->key[3].prefixlen = 24;
0741     inet_pton(AF_INET, "192.168.1.0", &info->key[3].data);
0742 }
0743 
0744 static void test_lpm_multi_thread(void)
0745 {
0746     LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC);
0747     struct lpm_mt_test_info info[4];
0748     size_t key_size, value_size;
0749     pthread_t thread_id[4];
0750     int i, map_fd;
0751     void *ret;
0752 
0753     /* create a trie */
0754     value_size = sizeof(__u32);
0755     key_size = sizeof(struct bpf_lpm_trie_key) + value_size;
0756     map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, value_size, 100, &opts);
0757 
0758     /* create 4 threads to test update, delete, lookup and get_next_key */
0759     setup_lpm_mt_test_info(&info[0], map_fd);
0760     for (i = 0; i < 4; i++) {
0761         if (i != 0)
0762             memcpy(&info[i], &info[0], sizeof(info[i]));
0763         info[i].cmd = i;
0764         assert(pthread_create(&thread_id[i], NULL, &lpm_test_command, &info[i]) == 0);
0765     }
0766 
0767     for (i = 0; i < 4; i++)
0768         assert(pthread_join(thread_id[i], &ret) == 0 && ret == (void *)&info[i]);
0769 
0770     close(map_fd);
0771 }
0772 
0773 int main(void)
0774 {
0775     int i;
0776 
0777     /* we want predictable, pseudo random tests */
0778     srand(0xf00ba1);
0779 
0780     /* Use libbpf 1.0 API mode */
0781     libbpf_set_strict_mode(LIBBPF_STRICT_ALL);
0782 
0783     test_lpm_basic();
0784     test_lpm_order();
0785 
0786     /* Test with 8, 16, 24, 32, ... 128 bit prefix length */
0787     for (i = 1; i <= 16; ++i)
0788         test_lpm_map(i);
0789 
0790     test_lpm_ipaddr();
0791     test_lpm_delete();
0792     test_lpm_get_next_key();
0793     test_lpm_multi_thread();
0794 
0795     printf("test_lpm: OK\n");
0796     return 0;
0797 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!