Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
4d3381f5 DH |
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> | |
af32efee | 17 | #include <pthread.h> |
4d3381f5 DH |
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> | |
4d3381f5 | 25 | |
10ecc728 | 26 | #include <bpf/bpf.h> |
fe8d662a | 27 | |
4d3381f5 DH |
28 | #include "bpf_util.h" |
29 | ||
30 | struct tlpm_node { | |
31 | struct tlpm_node *next; | |
32 | size_t n_bits; | |
33 | uint8_t key[]; | |
34 | }; | |
35 | ||
bae30468 CG |
36 | static struct tlpm_node *tlpm_match(struct tlpm_node *list, |
37 | const uint8_t *key, | |
38 | size_t n_bits); | |
39 | ||
4d3381f5 DH |
40 | static 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 | ||
bae30468 CG |
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 | ||
4d3381f5 DH |
56 | /* add new entry with @key/@n_bits to @list and return new head */ |
57 | ||
4d3381f5 DH |
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 | ||
68 | static 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 | ||
80 | static 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 | ||
e8d17499 CG |
109 | static 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 | ||
4d3381f5 DH |
137 | static 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 | ||
e8d17499 CG |
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 | ||
4d3381f5 DH |
166 | tlpm_clear(list); |
167 | } | |
168 | ||
169 | static 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 | ||
208 | static void test_lpm_map(int keysize) | |
209 | { | |
2fe256a4 | 210 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
ccaff3d5 YS |
211 | volatile size_t n_matches, n_matches_after_delete; |
212 | size_t i, j, n_nodes, n_lookups; | |
4d3381f5 | 213 | struct tlpm_node *t, *list = NULL; |
896880ff | 214 | struct bpf_lpm_trie_key_u8 *key; |
4d3381f5 DH |
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; | |
e8d17499 | 224 | n_matches_after_delete = 0; |
4d3381f5 DH |
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 | ||
2fe256a4 | 237 | map = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
4d3381f5 DH |
238 | sizeof(*key) + keysize, |
239 | keysize + 1, | |
240 | 4096, | |
2fe256a4 | 241 | &opts); |
4d3381f5 DH |
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); | |
10ecc728 | 253 | r = bpf_map_update_elem(map, key, value, 0); |
4d3381f5 DH |
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); | |
e5ff7c40 | 265 | r = bpf_map_lookup_elem(map, key, value); |
4d3381f5 DH |
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 | ||
e8d17499 CG |
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 | ||
4d3381f5 DH |
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 | * | |
e8d17499 CG |
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); | |
4d3381f5 DH |
326 | */ |
327 | } | |
328 | ||
329 | /* Test the implementation with some 'real world' examples */ | |
330 | ||
331 | static void test_lpm_ipaddr(void) | |
332 | { | |
2fe256a4 | 333 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
896880ff KC |
334 | struct bpf_lpm_trie_key_u8 *key_ipv4; |
335 | struct bpf_lpm_trie_key_u8 *key_ipv6; | |
4d3381f5 DH |
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 | ||
2fe256a4 | 347 | map_fd_ipv4 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
4d3381f5 | 348 | key_size_ipv4, sizeof(value), |
2fe256a4 | 349 | 100, &opts); |
4d3381f5 DH |
350 | assert(map_fd_ipv4 >= 0); |
351 | ||
2fe256a4 | 352 | map_fd_ipv6 = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
4d3381f5 | 353 | key_size_ipv6, sizeof(value), |
2fe256a4 | 354 | 100, &opts); |
4d3381f5 DH |
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); | |
10ecc728 | 361 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
4d3381f5 DH |
362 | |
363 | value = 2; | |
364 | key_ipv4->prefixlen = 24; | |
365 | inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); | |
10ecc728 | 366 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
4d3381f5 DH |
367 | |
368 | value = 3; | |
369 | key_ipv4->prefixlen = 24; | |
370 | inet_pton(AF_INET, "192.168.128.0", key_ipv4->data); | |
10ecc728 | 371 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
4d3381f5 DH |
372 | |
373 | value = 5; | |
374 | key_ipv4->prefixlen = 24; | |
375 | inet_pton(AF_INET, "192.168.1.0", key_ipv4->data); | |
10ecc728 | 376 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
4d3381f5 DH |
377 | |
378 | value = 4; | |
379 | key_ipv4->prefixlen = 23; | |
380 | inet_pton(AF_INET, "192.168.0.0", key_ipv4->data); | |
10ecc728 | 381 | assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0); |
4d3381f5 DH |
382 | |
383 | value = 0xdeadbeef; | |
384 | key_ipv6->prefixlen = 64; | |
385 | inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data); | |
10ecc728 | 386 | assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0); |
4d3381f5 DH |
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); | |
e5ff7c40 | 394 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); |
4d3381f5 DH |
395 | assert(value == 3); |
396 | ||
397 | inet_pton(AF_INET, "192.168.0.1", key_ipv4->data); | |
e5ff7c40 | 398 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0); |
4d3381f5 DH |
399 | assert(value == 2); |
400 | ||
401 | inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data); | |
e5ff7c40 | 402 | assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); |
4d3381f5 DH |
403 | assert(value == 0xdeadbeef); |
404 | ||
405 | inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data); | |
e5ff7c40 | 406 | assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0); |
4d3381f5 DH |
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); | |
c14766a8 | 411 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT); |
4d3381f5 DH |
412 | |
413 | inet_pton(AF_INET, "11.11.11.11", key_ipv4->data); | |
c14766a8 | 414 | assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -ENOENT); |
4d3381f5 DH |
415 | |
416 | inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data); | |
c14766a8 | 417 | assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -ENOENT); |
4d3381f5 DH |
418 | |
419 | close(map_fd_ipv4); | |
420 | close(map_fd_ipv6); | |
421 | } | |
422 | ||
e8d17499 CG |
423 | static void test_lpm_delete(void) |
424 | { | |
2fe256a4 | 425 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
896880ff | 426 | struct bpf_lpm_trie_key_u8 *key; |
e8d17499 CG |
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 | ||
2fe256a4 | 434 | map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, |
e8d17499 | 435 | key_size, sizeof(value), |
2fe256a4 | 436 | 100, &opts); |
e8d17499 CG |
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); | |
c14766a8 | 474 | assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT); |
e8d17499 | 475 | |
7c0cdf0b AC |
476 | key->prefixlen = 30; // unused prefix so far |
477 | inet_pton(AF_INET, "192.255.0.0", key->data); | |
c14766a8 | 478 | assert(bpf_map_delete_elem(map_fd, key) == -ENOENT); |
7c0cdf0b AC |
479 | |
480 | key->prefixlen = 16; // same prefix as the root node | |
481 | inet_pton(AF_INET, "192.255.0.0", key->data); | |
c14766a8 | 482 | assert(bpf_map_delete_elem(map_fd, key) == -ENOENT); |
7c0cdf0b | 483 | |
e8d17499 CG |
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); | |
c14766a8 | 527 | assert(bpf_map_lookup_elem(map_fd, key, &value) == -ENOENT); |
e8d17499 CG |
528 | |
529 | close(map_fd); | |
530 | } | |
531 | ||
8c417dc1 YS |
532 | static void test_lpm_get_next_key(void) |
533 | { | |
2fe256a4 | 534 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
896880ff | 535 | struct bpf_lpm_trie_key_u8 *key_p, *next_key_p; |
8c417dc1 YS |
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 | ||
2fe256a4 | 544 | map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, sizeof(value), 100, &opts); |
8c417dc1 YS |
545 | assert(map_fd >= 0); |
546 | ||
547 | /* empty tree. get_next_key should return ENOENT */ | |
c14766a8 | 548 | assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -ENOENT); |
8c417dc1 YS |
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 | ||
c14766a8 | 560 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
8c417dc1 YS |
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; | |
da2577fd | 570 | inet_pton(AF_INET, "192.168.128.0", key_p->data); |
8c417dc1 YS |
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 && | |
da2577fd | 576 | key_p->data[1] == 168 && key_p->data[2] == 128); |
8c417dc1 YS |
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); | |
c14766a8 | 584 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
8c417dc1 YS |
585 | |
586 | /* Add one more element (total three) */ | |
587 | key_p->prefixlen = 24; | |
da2577fd | 588 | inet_pton(AF_INET, "192.168.0.0", key_p->data); |
8c417dc1 YS |
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); | |
c14766a8 | 607 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
8c417dc1 YS |
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); | |
da2577fd JL |
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); | |
c14766a8 | 635 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
da2577fd JL |
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); | |
8c417dc1 YS |
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); | |
c14766a8 | 669 | assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -ENOENT); |
8c417dc1 YS |
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 | ||
af32efee YS |
681 | #define MAX_TEST_KEYS 4 |
682 | struct 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 | ||
692 | static void *lpm_test_command(void *arg) | |
693 | { | |
694 | int i, j, ret, iter, key_size; | |
695 | struct lpm_mt_test_info *info = arg; | |
896880ff | 696 | struct bpf_lpm_trie_key_u8 *key_p; |
af32efee | 697 | |
896880ff | 698 | key_size = sizeof(*key_p) + sizeof(__u32); |
af32efee YS |
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 { | |
896880ff | 720 | struct bpf_lpm_trie_key_u8 *next_key_p = alloca(key_size); |
af32efee YS |
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 | ||
730 | static 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 | ||
744 | static void test_lpm_multi_thread(void) | |
745 | { | |
2fe256a4 | 746 | LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = BPF_F_NO_PREALLOC); |
af32efee YS |
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); | |
896880ff | 755 | key_size = sizeof(struct bpf_lpm_trie_key_hdr) + value_size; |
2fe256a4 | 756 | map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, NULL, key_size, value_size, 100, &opts); |
af32efee YS |
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 | ||
4d3381f5 DH |
773 | int main(void) |
774 | { | |
fe8d662a | 775 | int i; |
4d3381f5 DH |
776 | |
777 | /* we want predictable, pseudo random tests */ | |
778 | srand(0xf00ba1); | |
779 | ||
b858ba8c YS |
780 | /* Use libbpf 1.0 API mode */ |
781 | libbpf_set_strict_mode(LIBBPF_STRICT_ALL); | |
782 | ||
4d3381f5 DH |
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(); | |
e8d17499 | 791 | test_lpm_delete(); |
8c417dc1 | 792 | test_lpm_get_next_key(); |
af32efee YS |
793 | test_lpm_multi_thread(); |
794 | ||
4d3381f5 DH |
795 | printf("test_lpm: OK\n"); |
796 | return 0; | |
797 | } |