]>
git.proxmox.com Git - mirror_ubuntu-kernels.git/blob - tools/testing/selftests/bpf/test_lpm_map.c
1 // SPDX-License-Identifier: GPL-2.0
3 * Randomized tests for eBPF longest-prefix-match maps
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.
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.
16 #include <linux/bpf.h>
22 #include <arpa/inet.h>
24 #include <sys/resource.h>
30 struct tlpm_node
*next
;
35 static struct tlpm_node
*tlpm_add(struct tlpm_node
*list
,
39 struct tlpm_node
*node
;
42 /* add new entry with @key/@n_bits to @list and return new head */
45 node
= malloc(sizeof(*node
) + n
);
49 node
->n_bits
= n_bits
;
50 memcpy(node
->key
, key
, n
);
55 static void tlpm_clear(struct tlpm_node
*list
)
57 struct tlpm_node
*node
;
59 /* free all entries in @list */
61 while ((node
= list
)) {
67 static struct tlpm_node
*tlpm_match(struct tlpm_node
*list
,
71 struct tlpm_node
*best
= NULL
;
74 /* Perform longest prefix-match on @key/@n_bits. That is, iterate all
75 * entries and match each prefix against @key. Remember the "best"
76 * entry we find (i.e., the longest prefix that matches) and return it
77 * to the caller when done.
80 for ( ; list
; list
= list
->next
) {
81 for (i
= 0; i
< n_bits
&& i
< list
->n_bits
; ++i
) {
82 if ((key
[i
/ 8] & (1 << (7 - i
% 8))) !=
83 (list
->key
[i
/ 8] & (1 << (7 - i
% 8))))
87 if (i
>= list
->n_bits
) {
88 if (!best
|| i
> best
->n_bits
)
96 static void test_lpm_basic(void)
98 struct tlpm_node
*list
= NULL
, *t1
, *t2
;
100 /* very basic, static tests to verify tlpm works as expected */
102 assert(!tlpm_match(list
, (uint8_t[]){ 0xff }, 8));
104 t1
= list
= tlpm_add(list
, (uint8_t[]){ 0xff }, 8);
105 assert(t1
== tlpm_match(list
, (uint8_t[]){ 0xff }, 8));
106 assert(t1
== tlpm_match(list
, (uint8_t[]){ 0xff, 0xff }, 16));
107 assert(t1
== tlpm_match(list
, (uint8_t[]){ 0xff, 0x00 }, 16));
108 assert(!tlpm_match(list
, (uint8_t[]){ 0x7f }, 8));
109 assert(!tlpm_match(list
, (uint8_t[]){ 0xfe }, 8));
110 assert(!tlpm_match(list
, (uint8_t[]){ 0xff }, 7));
112 t2
= list
= tlpm_add(list
, (uint8_t[]){ 0xff, 0xff }, 16);
113 assert(t1
== tlpm_match(list
, (uint8_t[]){ 0xff }, 8));
114 assert(t2
== tlpm_match(list
, (uint8_t[]){ 0xff, 0xff }, 16));
115 assert(t1
== tlpm_match(list
, (uint8_t[]){ 0xff, 0xff }, 15));
116 assert(!tlpm_match(list
, (uint8_t[]){ 0x7f, 0xff }, 16));
121 static void test_lpm_order(void)
123 struct tlpm_node
*t1
, *t2
, *l1
= NULL
, *l2
= NULL
;
126 /* Verify the tlpm implementation works correctly regardless of the
127 * order of entries. Insert a random set of entries into @l1, and copy
128 * the same data in reverse order into @l2. Then verify a lookup of
129 * random keys will yield the same result in both sets.
132 for (i
= 0; i
< (1 << 12); ++i
)
133 l1
= tlpm_add(l1
, (uint8_t[]){
138 for (t1
= l1
; t1
; t1
= t1
->next
)
139 l2
= tlpm_add(l2
, t1
->key
, t1
->n_bits
);
141 for (i
= 0; i
< (1 << 8); ++i
) {
142 uint8_t key
[] = { rand() % 0xff, rand() % 0xff };
144 t1
= tlpm_match(l1
, key
, 16);
145 t2
= tlpm_match(l2
, key
, 16);
149 assert(t1
->n_bits
== t2
->n_bits
);
150 for (j
= 0; j
< t1
->n_bits
; ++j
)
151 assert((t1
->key
[j
/ 8] & (1 << (7 - j
% 8))) ==
152 (t2
->key
[j
/ 8] & (1 << (7 - j
% 8))));
160 static void test_lpm_map(int keysize
)
162 size_t i
, j
, n_matches
, n_nodes
, n_lookups
;
163 struct tlpm_node
*t
, *list
= NULL
;
164 struct bpf_lpm_trie_key
*key
;
165 uint8_t *data
, *value
;
168 /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of
169 * prefixes and insert it into both tlpm and bpf-lpm. Then run some
170 * randomized lookups and verify both maps return the same result.
177 data
= alloca(keysize
);
178 memset(data
, 0, keysize
);
180 value
= alloca(keysize
+ 1);
181 memset(value
, 0, keysize
+ 1);
183 key
= alloca(sizeof(*key
) + keysize
);
184 memset(key
, 0, sizeof(*key
) + keysize
);
186 map
= bpf_create_map(BPF_MAP_TYPE_LPM_TRIE
,
187 sizeof(*key
) + keysize
,
193 for (i
= 0; i
< n_nodes
; ++i
) {
194 for (j
= 0; j
< keysize
; ++j
)
195 value
[j
] = rand() & 0xff;
196 value
[keysize
] = rand() % (8 * keysize
+ 1);
198 list
= tlpm_add(list
, value
, value
[keysize
]);
200 key
->prefixlen
= value
[keysize
];
201 memcpy(key
->data
, value
, keysize
);
202 r
= bpf_map_update_elem(map
, key
, value
, 0);
206 for (i
= 0; i
< n_lookups
; ++i
) {
207 for (j
= 0; j
< keysize
; ++j
)
208 data
[j
] = rand() & 0xff;
210 t
= tlpm_match(list
, data
, 8 * keysize
);
212 key
->prefixlen
= 8 * keysize
;
213 memcpy(key
->data
, data
, keysize
);
214 r
= bpf_map_lookup_elem(map
, key
, value
);
215 assert(!r
|| errno
== ENOENT
);
220 assert(t
->n_bits
== value
[keysize
]);
221 for (j
= 0; j
< t
->n_bits
; ++j
)
222 assert((t
->key
[j
/ 8] & (1 << (7 - j
% 8))) ==
223 (value
[j
/ 8] & (1 << (7 - j
% 8))));
230 /* With 255 random nodes in the map, we are pretty likely to match
231 * something on every lookup. For statistics, use this:
233 * printf(" nodes: %zu\n"
235 * "matches: %zu\n", n_nodes, n_lookups, n_matches);
239 /* Test the implementation with some 'real world' examples */
241 static void test_lpm_ipaddr(void)
243 struct bpf_lpm_trie_key
*key_ipv4
;
244 struct bpf_lpm_trie_key
*key_ipv6
;
245 size_t key_size_ipv4
;
246 size_t key_size_ipv6
;
251 key_size_ipv4
= sizeof(*key_ipv4
) + sizeof(__u32
);
252 key_size_ipv6
= sizeof(*key_ipv6
) + sizeof(__u32
) * 4;
253 key_ipv4
= alloca(key_size_ipv4
);
254 key_ipv6
= alloca(key_size_ipv6
);
256 map_fd_ipv4
= bpf_create_map(BPF_MAP_TYPE_LPM_TRIE
,
257 key_size_ipv4
, sizeof(value
),
258 100, BPF_F_NO_PREALLOC
);
259 assert(map_fd_ipv4
>= 0);
261 map_fd_ipv6
= bpf_create_map(BPF_MAP_TYPE_LPM_TRIE
,
262 key_size_ipv6
, sizeof(value
),
263 100, BPF_F_NO_PREALLOC
);
264 assert(map_fd_ipv6
>= 0);
266 /* Fill data some IPv4 and IPv6 address ranges */
268 key_ipv4
->prefixlen
= 16;
269 inet_pton(AF_INET
, "192.168.0.0", key_ipv4
->data
);
270 assert(bpf_map_update_elem(map_fd_ipv4
, key_ipv4
, &value
, 0) == 0);
273 key_ipv4
->prefixlen
= 24;
274 inet_pton(AF_INET
, "192.168.0.0", key_ipv4
->data
);
275 assert(bpf_map_update_elem(map_fd_ipv4
, key_ipv4
, &value
, 0) == 0);
278 key_ipv4
->prefixlen
= 24;
279 inet_pton(AF_INET
, "192.168.128.0", key_ipv4
->data
);
280 assert(bpf_map_update_elem(map_fd_ipv4
, key_ipv4
, &value
, 0) == 0);
283 key_ipv4
->prefixlen
= 24;
284 inet_pton(AF_INET
, "192.168.1.0", key_ipv4
->data
);
285 assert(bpf_map_update_elem(map_fd_ipv4
, key_ipv4
, &value
, 0) == 0);
288 key_ipv4
->prefixlen
= 23;
289 inet_pton(AF_INET
, "192.168.0.0", key_ipv4
->data
);
290 assert(bpf_map_update_elem(map_fd_ipv4
, key_ipv4
, &value
, 0) == 0);
293 key_ipv6
->prefixlen
= 64;
294 inet_pton(AF_INET6
, "2a00:1450:4001:814::200e", key_ipv6
->data
);
295 assert(bpf_map_update_elem(map_fd_ipv6
, key_ipv6
, &value
, 0) == 0);
297 /* Set tprefixlen to maximum for lookups */
298 key_ipv4
->prefixlen
= 32;
299 key_ipv6
->prefixlen
= 128;
301 /* Test some lookups that should come back with a value */
302 inet_pton(AF_INET
, "192.168.128.23", key_ipv4
->data
);
303 assert(bpf_map_lookup_elem(map_fd_ipv4
, key_ipv4
, &value
) == 0);
306 inet_pton(AF_INET
, "192.168.0.1", key_ipv4
->data
);
307 assert(bpf_map_lookup_elem(map_fd_ipv4
, key_ipv4
, &value
) == 0);
310 inet_pton(AF_INET6
, "2a00:1450:4001:814::", key_ipv6
->data
);
311 assert(bpf_map_lookup_elem(map_fd_ipv6
, key_ipv6
, &value
) == 0);
312 assert(value
== 0xdeadbeef);
314 inet_pton(AF_INET6
, "2a00:1450:4001:814::1", key_ipv6
->data
);
315 assert(bpf_map_lookup_elem(map_fd_ipv6
, key_ipv6
, &value
) == 0);
316 assert(value
== 0xdeadbeef);
318 /* Test some lookups that should not match any entry */
319 inet_pton(AF_INET
, "10.0.0.1", key_ipv4
->data
);
320 assert(bpf_map_lookup_elem(map_fd_ipv4
, key_ipv4
, &value
) == -1 &&
323 inet_pton(AF_INET
, "11.11.11.11", key_ipv4
->data
);
324 assert(bpf_map_lookup_elem(map_fd_ipv4
, key_ipv4
, &value
) == -1 &&
327 inet_pton(AF_INET6
, "2a00:ffff::", key_ipv6
->data
);
328 assert(bpf_map_lookup_elem(map_fd_ipv6
, key_ipv6
, &value
) == -1 &&
337 struct rlimit limit
= { RLIM_INFINITY
, RLIM_INFINITY
};
340 /* we want predictable, pseudo random tests */
343 /* allow unlimited locked memory */
344 ret
= setrlimit(RLIMIT_MEMLOCK
, &limit
);
346 perror("Unable to lift memlock rlimit");
351 /* Test with 8, 16, 24, 32, ... 128 bit prefix length */
352 for (i
= 1; i
<= 16; ++i
)
357 printf("test_lpm: OK\n");