cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

test_lpm_map.c (23627B)


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