~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/testing/selftests/bpf/test_lpm_map.c

Version: ~ [ linux-5.16 ] ~ [ linux-5.15.13 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.90 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.170 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.224 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.261 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.296 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.298 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 <stdio.h>
 18 #include <stdlib.h>
 19 #include <string.h>
 20 #include <time.h>
 21 #include <unistd.h>
 22 #include <arpa/inet.h>
 23 #include <sys/time.h>
 24 #include <sys/resource.h>
 25 
 26 #include <bpf/bpf.h>
 27 #include "bpf_util.h"
 28 
 29 struct tlpm_node {
 30         struct tlpm_node *next;
 31         size_t n_bits;
 32         uint8_t key[];
 33 };
 34 
 35 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
 36                                     const uint8_t *key,
 37                                     size_t n_bits);
 38 
 39 static struct tlpm_node *tlpm_add(struct tlpm_node *list,
 40                                   const uint8_t *key,
 41                                   size_t n_bits)
 42 {
 43         struct tlpm_node *node;
 44         size_t n;
 45 
 46         n = (n_bits + 7) / 8;
 47 
 48         /* 'overwrite' an equivalent entry if one already exists */
 49         node = tlpm_match(list, key, n_bits);
 50         if (node && node->n_bits == n_bits) {
 51                 memcpy(node->key, key, n);
 52                 return list;
 53         }
 54 
 55         /* add new entry with @key/@n_bits to @list and return new head */
 56 
 57         node = malloc(sizeof(*node) + n);
 58         assert(node);
 59 
 60         node->next = list;
 61         node->n_bits = n_bits;
 62         memcpy(node->key, key, n);
 63 
 64         return node;
 65 }
 66 
 67 static void tlpm_clear(struct tlpm_node *list)
 68 {
 69         struct tlpm_node *node;
 70 
 71         /* free all entries in @list */
 72 
 73         while ((node = list)) {
 74                 list = list->next;
 75                 free(node);
 76         }
 77 }
 78 
 79 static struct tlpm_node *tlpm_match(struct tlpm_node *list,
 80                                     const uint8_t *key,
 81                                     size_t n_bits)
 82 {
 83         struct tlpm_node *best = NULL;
 84         size_t i;
 85 
 86         /* Perform longest prefix-match on @key/@n_bits. That is, iterate all
 87          * entries and match each prefix against @key. Remember the "best"
 88          * entry we find (i.e., the longest prefix that matches) and return it
 89          * to the caller when done.
 90          */
 91 
 92         for ( ; list; list = list->next) {
 93                 for (i = 0; i < n_bits && i < list->n_bits; ++i) {
 94                         if ((key[i / 8] & (1 << (7 - i % 8))) !=
 95                             (list->key[i / 8] & (1 << (7 - i % 8))))
 96                                 break;
 97                 }
 98 
 99                 if (i >= list->n_bits) {
100                         if (!best || i > best->n_bits)
101                                 best = list;
102                 }
103         }
104 
105         return best;
106 }
107 
108 static struct tlpm_node *tlpm_delete(struct tlpm_node *list,
109                                      const uint8_t *key,
110                                      size_t n_bits)
111 {
112         struct tlpm_node *best = tlpm_match(list, key, n_bits);
113         struct tlpm_node *node;
114 
115         if (!best || best->n_bits != n_bits)
116                 return list;
117 
118         if (best == list) {
119                 node = best->next;
120                 free(best);
121                 return node;
122         }
123 
124         for (node = list; node; node = node->next) {
125                 if (node->next == best) {
126                         node->next = best->next;
127                         free(best);
128                         return list;
129                 }
130         }
131         /* should never get here */
132         assert(0);
133         return list;
134 }
135 
136 static void test_lpm_basic(void)
137 {
138         struct tlpm_node *list = NULL, *t1, *t2;
139 
140         /* very basic, static tests to verify tlpm works as expected */
141 
142         assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
143 
144         t1 = list = tlpm_add(list, (uint8_t[]){ 0xff }, 8);
145         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
146         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
147         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0x00 }, 16));
148         assert(!tlpm_match(list, (uint8_t[]){ 0x7f }, 8));
149         assert(!tlpm_match(list, (uint8_t[]){ 0xfe }, 8));
150         assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 7));
151 
152         t2 = list = tlpm_add(list, (uint8_t[]){ 0xff, 0xff }, 16);
153         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
154         assert(t2 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
155         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15));
156         assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16));
157 
158         list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16);
159         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
160         assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
161 
162         list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8);
163         assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
164 
165         tlpm_clear(list);
166 }
167 
168 static void test_lpm_order(void)
169 {
170         struct tlpm_node *t1, *t2, *l1 = NULL, *l2 = NULL;
171         size_t i, j;
172 
173         /* Verify the tlpm implementation works correctly regardless of the
174          * order of entries. Insert a random set of entries into @l1, and copy
175          * the same data in reverse order into @l2. Then verify a lookup of
176          * random keys will yield the same result in both sets.
177          */
178 
179         for (i = 0; i < (1 << 12); ++i)
180                 l1 = tlpm_add(l1, (uint8_t[]){
181                                         rand() % 0xff,
182                                         rand() % 0xff,
183                                 }, rand() % 16 + 1);
184 
185         for (t1 = l1; t1; t1 = t1->next)
186                 l2 = tlpm_add(l2, t1->key, t1->n_bits);
187 
188         for (i = 0; i < (1 << 8); ++i) {
189                 uint8_t key[] = { rand() % 0xff, rand() % 0xff };
190 
191                 t1 = tlpm_match(l1, key, 16);
192                 t2 = tlpm_match(l2, key, 16);
193 
194                 assert(!t1 == !t2);
195                 if (t1) {
196                         assert(t1->n_bits == t2->n_bits);
197                         for (j = 0; j < t1->n_bits; ++j)
198                                 assert((t1->key[j / 8] & (1 << (7 - j % 8))) ==
199                                        (t2->key[j / 8] & (1 << (7 - j % 8))));
200                 }
201         }
202 
203         tlpm_clear(l1);
204         tlpm_clear(l2);
205 }
206 
207 static void test_lpm_map(int keysize)
208 {
209         size_t i, j, n_matches, n_matches_after_delete, n_nodes, n_lookups;
210         struct tlpm_node *t, *list = NULL;
211         struct bpf_lpm_trie_key *key;
212         uint8_t *data, *value;
213         int r, map;
214 
215         /* Compare behavior of tlpm vs. bpf-lpm. Create a randomized set of
216          * prefixes and insert it into both tlpm and bpf-lpm. Then run some
217          * randomized lookups and verify both maps return the same result.
218          */
219 
220         n_matches = 0;
221         n_matches_after_delete = 0;
222         n_nodes = 1 << 8;
223         n_lookups = 1 << 16;
224 
225         data = alloca(keysize);
226         memset(data, 0, keysize);
227 
228         value = alloca(keysize + 1);
229         memset(value, 0, keysize + 1);
230 
231         key = alloca(sizeof(*key) + keysize);
232         memset(key, 0, sizeof(*key) + keysize);
233 
234         map = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
235                              sizeof(*key) + keysize,
236                              keysize + 1,
237                              4096,
238                              BPF_F_NO_PREALLOC);
239         assert(map >= 0);
240 
241         for (i = 0; i < n_nodes; ++i) {
242                 for (j = 0; j < keysize; ++j)
243                         value[j] = rand() & 0xff;
244                 value[keysize] = rand() % (8 * keysize + 1);
245 
246                 list = tlpm_add(list, value, value[keysize]);
247 
248                 key->prefixlen = value[keysize];
249                 memcpy(key->data, value, keysize);
250                 r = bpf_map_update_elem(map, key, value, 0);
251                 assert(!r);
252         }
253 
254         for (i = 0; i < n_lookups; ++i) {
255                 for (j = 0; j < keysize; ++j)
256                         data[j] = rand() & 0xff;
257 
258                 t = tlpm_match(list, data, 8 * keysize);
259 
260                 key->prefixlen = 8 * keysize;
261                 memcpy(key->data, data, keysize);
262                 r = bpf_map_lookup_elem(map, key, value);
263                 assert(!r || errno == ENOENT);
264                 assert(!t == !!r);
265 
266                 if (t) {
267                         ++n_matches;
268                         assert(t->n_bits == value[keysize]);
269                         for (j = 0; j < t->n_bits; ++j)
270                                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
271                                        (value[j / 8] & (1 << (7 - j % 8))));
272                 }
273         }
274 
275         /* Remove the first half of the elements in the tlpm and the
276          * corresponding nodes from the bpf-lpm.  Then run the same
277          * large number of random lookups in both and make sure they match.
278          * Note: we need to count the number of nodes actually inserted
279          * since there may have been duplicates.
280          */
281         for (i = 0, t = list; t; i++, t = t->next)
282                 ;
283         for (j = 0; j < i / 2; ++j) {
284                 key->prefixlen = list->n_bits;
285                 memcpy(key->data, list->key, keysize);
286                 r = bpf_map_delete_elem(map, key);
287                 assert(!r);
288                 list = tlpm_delete(list, list->key, list->n_bits);
289                 assert(list);
290         }
291         for (i = 0; i < n_lookups; ++i) {
292                 for (j = 0; j < keysize; ++j)
293                         data[j] = rand() & 0xff;
294 
295                 t = tlpm_match(list, data, 8 * keysize);
296 
297                 key->prefixlen = 8 * keysize;
298                 memcpy(key->data, data, keysize);
299                 r = bpf_map_lookup_elem(map, key, value);
300                 assert(!r || errno == ENOENT);
301                 assert(!t == !!r);
302 
303                 if (t) {
304                         ++n_matches_after_delete;
305                         assert(t->n_bits == value[keysize]);
306                         for (j = 0; j < t->n_bits; ++j)
307                                 assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
308                                        (value[j / 8] & (1 << (7 - j % 8))));
309                 }
310         }
311 
312         close(map);
313         tlpm_clear(list);
314 
315         /* With 255 random nodes in the map, we are pretty likely to match
316          * something on every lookup. For statistics, use this:
317          *
318          *     printf("          nodes: %zu\n"
319          *            "        lookups: %zu\n"
320          *            "        matches: %zu\n"
321          *            "matches(delete): %zu\n",
322          *            n_nodes, n_lookups, n_matches, n_matches_after_delete);
323          */
324 }
325 
326 /* Test the implementation with some 'real world' examples */
327 
328 static void test_lpm_ipaddr(void)
329 {
330         struct bpf_lpm_trie_key *key_ipv4;
331         struct bpf_lpm_trie_key *key_ipv6;
332         size_t key_size_ipv4;
333         size_t key_size_ipv6;
334         int map_fd_ipv4;
335         int map_fd_ipv6;
336         __u64 value;
337 
338         key_size_ipv4 = sizeof(*key_ipv4) + sizeof(__u32);
339         key_size_ipv6 = sizeof(*key_ipv6) + sizeof(__u32) * 4;
340         key_ipv4 = alloca(key_size_ipv4);
341         key_ipv6 = alloca(key_size_ipv6);
342 
343         map_fd_ipv4 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
344                                      key_size_ipv4, sizeof(value),
345                                      100, BPF_F_NO_PREALLOC);
346         assert(map_fd_ipv4 >= 0);
347 
348         map_fd_ipv6 = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
349                                      key_size_ipv6, sizeof(value),
350                                      100, BPF_F_NO_PREALLOC);
351         assert(map_fd_ipv6 >= 0);
352 
353         /* Fill data some IPv4 and IPv6 address ranges */
354         value = 1;
355         key_ipv4->prefixlen = 16;
356         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
357         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
358 
359         value = 2;
360         key_ipv4->prefixlen = 24;
361         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
362         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
363 
364         value = 3;
365         key_ipv4->prefixlen = 24;
366         inet_pton(AF_INET, "192.168.128.0", key_ipv4->data);
367         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
368 
369         value = 5;
370         key_ipv4->prefixlen = 24;
371         inet_pton(AF_INET, "192.168.1.0", key_ipv4->data);
372         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
373 
374         value = 4;
375         key_ipv4->prefixlen = 23;
376         inet_pton(AF_INET, "192.168.0.0", key_ipv4->data);
377         assert(bpf_map_update_elem(map_fd_ipv4, key_ipv4, &value, 0) == 0);
378 
379         value = 0xdeadbeef;
380         key_ipv6->prefixlen = 64;
381         inet_pton(AF_INET6, "2a00:1450:4001:814::200e", key_ipv6->data);
382         assert(bpf_map_update_elem(map_fd_ipv6, key_ipv6, &value, 0) == 0);
383 
384         /* Set tprefixlen to maximum for lookups */
385         key_ipv4->prefixlen = 32;
386         key_ipv6->prefixlen = 128;
387 
388         /* Test some lookups that should come back with a value */
389         inet_pton(AF_INET, "192.168.128.23", key_ipv4->data);
390         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
391         assert(value == 3);
392 
393         inet_pton(AF_INET, "192.168.0.1", key_ipv4->data);
394         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == 0);
395         assert(value == 2);
396 
397         inet_pton(AF_INET6, "2a00:1450:4001:814::", key_ipv6->data);
398         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
399         assert(value == 0xdeadbeef);
400 
401         inet_pton(AF_INET6, "2a00:1450:4001:814::1", key_ipv6->data);
402         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == 0);
403         assert(value == 0xdeadbeef);
404 
405         /* Test some lookups that should not match any entry */
406         inet_pton(AF_INET, "10.0.0.1", key_ipv4->data);
407         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 &&
408                errno == ENOENT);
409 
410         inet_pton(AF_INET, "11.11.11.11", key_ipv4->data);
411         assert(bpf_map_lookup_elem(map_fd_ipv4, key_ipv4, &value) == -1 &&
412                errno == ENOENT);
413 
414         inet_pton(AF_INET6, "2a00:ffff::", key_ipv6->data);
415         assert(bpf_map_lookup_elem(map_fd_ipv6, key_ipv6, &value) == -1 &&
416                errno == ENOENT);
417 
418         close(map_fd_ipv4);
419         close(map_fd_ipv6);
420 }
421 
422 static void test_lpm_delete(void)
423 {
424         struct bpf_lpm_trie_key *key;
425         size_t key_size;
426         int map_fd;
427         __u64 value;
428 
429         key_size = sizeof(*key) + sizeof(__u32);
430         key = alloca(key_size);
431 
432         map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
433                                 key_size, sizeof(value),
434                                 100, BPF_F_NO_PREALLOC);
435         assert(map_fd >= 0);
436 
437         /* Add nodes:
438          * 192.168.0.0/16   (1)
439          * 192.168.0.0/24   (2)
440          * 192.168.128.0/24 (3)
441          * 192.168.1.0/24   (4)
442          *
443          *         (1)
444          *        /   \
445          *     (IM)    (3)
446          *    /   \
447          *   (2)  (4)
448          */
449         value = 1;
450         key->prefixlen = 16;
451         inet_pton(AF_INET, "192.168.0.0", key->data);
452         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
453 
454         value = 2;
455         key->prefixlen = 24;
456         inet_pton(AF_INET, "192.168.0.0", key->data);
457         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
458 
459         value = 3;
460         key->prefixlen = 24;
461         inet_pton(AF_INET, "192.168.128.0", key->data);
462         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
463 
464         value = 4;
465         key->prefixlen = 24;
466         inet_pton(AF_INET, "192.168.1.0", key->data);
467         assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
468 
469         /* remove non-existent node */
470         key->prefixlen = 32;
471         inet_pton(AF_INET, "10.0.0.1", key->data);
472         assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
473                 errno == ENOENT);
474 
475         /* assert initial lookup */
476         key->prefixlen = 32;
477         inet_pton(AF_INET, "192.168.0.1", key->data);
478         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
479         assert(value == 2);
480 
481         /* remove leaf node */
482         key->prefixlen = 24;
483         inet_pton(AF_INET, "192.168.0.0", key->data);
484         assert(bpf_map_delete_elem(map_fd, key) == 0);
485 
486         key->prefixlen = 32;
487         inet_pton(AF_INET, "192.168.0.1", key->data);
488         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
489         assert(value == 1);
490 
491         /* remove leaf (and intermediary) node */
492         key->prefixlen = 24;
493         inet_pton(AF_INET, "192.168.1.0", key->data);
494         assert(bpf_map_delete_elem(map_fd, key) == 0);
495 
496         key->prefixlen = 32;
497         inet_pton(AF_INET, "192.168.1.1", key->data);
498         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
499         assert(value == 1);
500 
501         /* remove root node */
502         key->prefixlen = 16;
503         inet_pton(AF_INET, "192.168.0.0", key->data);
504         assert(bpf_map_delete_elem(map_fd, key) == 0);
505 
506         key->prefixlen = 32;
507         inet_pton(AF_INET, "192.168.128.1", key->data);
508         assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
509         assert(value == 3);
510 
511         /* remove last node */
512         key->prefixlen = 24;
513         inet_pton(AF_INET, "192.168.128.0", key->data);
514         assert(bpf_map_delete_elem(map_fd, key) == 0);
515 
516         key->prefixlen = 32;
517         inet_pton(AF_INET, "192.168.128.1", key->data);
518         assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
519                 errno == ENOENT);
520 
521         close(map_fd);
522 }
523 
524 int main(void)
525 {
526         struct rlimit limit  = { RLIM_INFINITY, RLIM_INFINITY };
527         int i, ret;
528 
529         /* we want predictable, pseudo random tests */
530         srand(0xf00ba1);
531 
532         /* allow unlimited locked memory */
533         ret = setrlimit(RLIMIT_MEMLOCK, &limit);
534         if (ret < 0)
535                 perror("Unable to lift memlock rlimit");
536 
537         test_lpm_basic();
538         test_lpm_order();
539 
540         /* Test with 8, 16, 24, 32, ... 128 bit prefix length */
541         for (i = 1; i <= 16; ++i)
542                 test_lpm_map(i);
543 
544         test_lpm_ipaddr();
545 
546         test_lpm_delete();
547 
548         printf("test_lpm: OK\n");
549         return 0;
550 }
551 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp