4 * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 #include <sys/queue.h>
40 #include <rte_common.h>
41 #include <rte_cycles.h>
42 #include <rte_memory.h>
43 #include <rte_random.h>
44 #include <rte_branch_prediction.h>
51 #include "test_lpm_routes.h"
52 #include "test_xmmt_ops.h"
54 #define TEST_LPM_ASSERT(cond) do { \
56 printf("Error at line %d: \n", __LINE__); \
61 typedef int32_t (*rte_lpm_test)(void);
63 static int32_t test0(void);
64 static int32_t test1(void);
65 static int32_t test2(void);
66 static int32_t test3(void);
67 static int32_t test4(void);
68 static int32_t test5(void);
69 static int32_t test6(void);
70 static int32_t test7(void);
71 static int32_t test8(void);
72 static int32_t test9(void);
73 static int32_t test10(void);
74 static int32_t test11(void);
75 static int32_t test12(void);
76 static int32_t test13(void);
77 static int32_t test14(void);
78 static int32_t test15(void);
79 static int32_t test16(void);
80 static int32_t test17(void);
81 static int32_t perf_test(void);
83 rte_lpm_test tests[] = {
106 #define NUM_LPM_TESTS (sizeof(tests)/sizeof(tests[0]))
108 #define MAX_RULES 256
109 #define NUMBER_TBL8S 256
113 * Check that rte_lpm_create fails gracefully for incorrect user input
119 struct rte_lpm *lpm = NULL;
120 struct rte_lpm_config config;
122 config.max_rules = MAX_RULES;
123 config.number_tbl8s = NUMBER_TBL8S;
126 /* rte_lpm_create: lpm name == NULL */
127 lpm = rte_lpm_create(NULL, SOCKET_ID_ANY, &config);
128 TEST_LPM_ASSERT(lpm == NULL);
130 /* rte_lpm_create: max_rules = 0 */
131 /* Note: __func__ inserts the function name, in this case "test0". */
132 config.max_rules = 0;
133 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
134 TEST_LPM_ASSERT(lpm == NULL);
136 /* socket_id < -1 is invalid */
137 config.max_rules = MAX_RULES;
138 lpm = rte_lpm_create(__func__, -2, &config);
139 TEST_LPM_ASSERT(lpm == NULL);
145 * Create lpm table then delete lpm table 100 times
146 * Use a slightly different rules size each time
151 struct rte_lpm *lpm = NULL;
152 struct rte_lpm_config config;
154 config.number_tbl8s = NUMBER_TBL8S;
158 /* rte_lpm_free: Free NULL */
159 for (i = 0; i < 100; i++) {
160 config.max_rules = MAX_RULES - i;
161 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
162 TEST_LPM_ASSERT(lpm != NULL);
167 /* Can not test free so return success */
172 * Call rte_lpm_free for NULL pointer user input. Note: free has no return and
173 * therefore it is impossible to check for failure but this test is added to
174 * increase function coverage metrics and to validate that freeing null does
180 struct rte_lpm *lpm = NULL;
181 struct rte_lpm_config config;
183 config.max_rules = MAX_RULES;
184 config.number_tbl8s = NUMBER_TBL8S;
187 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
188 TEST_LPM_ASSERT(lpm != NULL);
196 * Check that rte_lpm_add fails gracefully for incorrect user input arguments
201 struct rte_lpm *lpm = NULL;
202 struct rte_lpm_config config;
204 config.max_rules = MAX_RULES;
205 config.number_tbl8s = NUMBER_TBL8S;
207 uint32_t ip = IPv4(0, 0, 0, 0), next_hop = 100;
211 /* rte_lpm_add: lpm == NULL */
212 status = rte_lpm_add(NULL, ip, depth, next_hop);
213 TEST_LPM_ASSERT(status < 0);
215 /*Create vaild lpm to use in rest of test. */
216 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
217 TEST_LPM_ASSERT(lpm != NULL);
219 /* rte_lpm_add: depth < 1 */
220 status = rte_lpm_add(lpm, ip, 0, next_hop);
221 TEST_LPM_ASSERT(status < 0);
223 /* rte_lpm_add: depth > MAX_DEPTH */
224 status = rte_lpm_add(lpm, ip, (MAX_DEPTH + 1), next_hop);
225 TEST_LPM_ASSERT(status < 0);
233 * Check that rte_lpm_delete fails gracefully for incorrect user input
239 struct rte_lpm *lpm = NULL;
240 struct rte_lpm_config config;
242 config.max_rules = MAX_RULES;
243 config.number_tbl8s = NUMBER_TBL8S;
245 uint32_t ip = IPv4(0, 0, 0, 0);
249 /* rte_lpm_delete: lpm == NULL */
250 status = rte_lpm_delete(NULL, ip, depth);
251 TEST_LPM_ASSERT(status < 0);
253 /*Create vaild lpm to use in rest of test. */
254 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
255 TEST_LPM_ASSERT(lpm != NULL);
257 /* rte_lpm_delete: depth < 1 */
258 status = rte_lpm_delete(lpm, ip, 0);
259 TEST_LPM_ASSERT(status < 0);
261 /* rte_lpm_delete: depth > MAX_DEPTH */
262 status = rte_lpm_delete(lpm, ip, (MAX_DEPTH + 1));
263 TEST_LPM_ASSERT(status < 0);
271 * Check that rte_lpm_lookup fails gracefully for incorrect user input
277 #if defined(RTE_LIBRTE_LPM_DEBUG)
278 struct rte_lpm *lpm = NULL;
279 struct rte_lpm_config config;
281 config.max_rules = MAX_RULES;
282 config.number_tbl8s = NUMBER_TBL8S;
284 uint32_t ip = IPv4(0, 0, 0, 0), next_hop_return = 0;
287 /* rte_lpm_lookup: lpm == NULL */
288 status = rte_lpm_lookup(NULL, ip, &next_hop_return);
289 TEST_LPM_ASSERT(status < 0);
291 /*Create vaild lpm to use in rest of test. */
292 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
293 TEST_LPM_ASSERT(lpm != NULL);
295 /* rte_lpm_lookup: depth < 1 */
296 status = rte_lpm_lookup(lpm, ip, NULL);
297 TEST_LPM_ASSERT(status < 0);
307 * Call add, lookup and delete for a single rule with depth <= 24
312 struct rte_lpm *lpm = NULL;
313 struct rte_lpm_config config;
315 config.max_rules = MAX_RULES;
316 config.number_tbl8s = NUMBER_TBL8S;
318 uint32_t ip = IPv4(0, 0, 0, 0), next_hop_add = 100, next_hop_return = 0;
322 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
323 TEST_LPM_ASSERT(lpm != NULL);
325 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
326 TEST_LPM_ASSERT(status == 0);
328 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
329 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
331 status = rte_lpm_delete(lpm, ip, depth);
332 TEST_LPM_ASSERT(status == 0);
334 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
335 TEST_LPM_ASSERT(status == -ENOENT);
343 * Call add, lookup and delete for a single rule with depth > 24
351 struct rte_lpm *lpm = NULL;
352 struct rte_lpm_config config;
354 config.max_rules = MAX_RULES;
355 config.number_tbl8s = NUMBER_TBL8S;
357 uint32_t ip = IPv4(0, 0, 0, 0), next_hop_add = 100, next_hop_return = 0;
361 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
362 TEST_LPM_ASSERT(lpm != NULL);
364 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
365 TEST_LPM_ASSERT(status == 0);
367 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
368 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
370 ipx4 = vect_set_epi32(ip, ip + 0x100, ip - 0x100, ip);
371 rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
372 TEST_LPM_ASSERT(hop[0] == next_hop_add);
373 TEST_LPM_ASSERT(hop[1] == UINT32_MAX);
374 TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
375 TEST_LPM_ASSERT(hop[3] == next_hop_add);
377 status = rte_lpm_delete(lpm, ip, depth);
378 TEST_LPM_ASSERT(status == 0);
380 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
381 TEST_LPM_ASSERT(status == -ENOENT);
389 * Use rte_lpm_add to add rules which effect only the second half of the lpm
390 * table. Use all possible depths ranging from 1..32. Set the next hop = to the
391 * depth. Check lookup hit for on every add and check for lookup miss on the
392 * first half of the lpm table after each add. Finally delete all rules going
393 * backwards (i.e. from depth = 32 ..1) and carry out a lookup after each
394 * delete. The lookup should return the next_hop_add value related to the
395 * previous depth value (i.e. depth -1).
402 struct rte_lpm *lpm = NULL;
403 struct rte_lpm_config config;
405 config.max_rules = MAX_RULES;
406 config.number_tbl8s = NUMBER_TBL8S;
408 uint32_t ip1 = IPv4(127, 255, 255, 255), ip2 = IPv4(128, 0, 0, 0);
409 uint32_t next_hop_add, next_hop_return;
413 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
414 TEST_LPM_ASSERT(lpm != NULL);
416 /* Loop with rte_lpm_add. */
417 for (depth = 1; depth <= 32; depth++) {
418 /* Let the next_hop_add value = depth. Just for change. */
419 next_hop_add = depth;
421 status = rte_lpm_add(lpm, ip2, depth, next_hop_add);
422 TEST_LPM_ASSERT(status == 0);
424 /* Check IP in first half of tbl24 which should be empty. */
425 status = rte_lpm_lookup(lpm, ip1, &next_hop_return);
426 TEST_LPM_ASSERT(status == -ENOENT);
428 status = rte_lpm_lookup(lpm, ip2, &next_hop_return);
429 TEST_LPM_ASSERT((status == 0) &&
430 (next_hop_return == next_hop_add));
432 ipx4 = vect_set_epi32(ip2, ip1, ip2, ip1);
433 rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
434 TEST_LPM_ASSERT(hop[0] == UINT32_MAX);
435 TEST_LPM_ASSERT(hop[1] == next_hop_add);
436 TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
437 TEST_LPM_ASSERT(hop[3] == next_hop_add);
440 /* Loop with rte_lpm_delete. */
441 for (depth = 32; depth >= 1; depth--) {
442 next_hop_add = (uint8_t) (depth - 1);
444 status = rte_lpm_delete(lpm, ip2, depth);
445 TEST_LPM_ASSERT(status == 0);
447 status = rte_lpm_lookup(lpm, ip2, &next_hop_return);
450 TEST_LPM_ASSERT((status == 0) &&
451 (next_hop_return == next_hop_add));
453 TEST_LPM_ASSERT(status == -ENOENT);
456 status = rte_lpm_lookup(lpm, ip1, &next_hop_return);
457 TEST_LPM_ASSERT(status == -ENOENT);
459 ipx4 = vect_set_epi32(ip1, ip1, ip2, ip2);
460 rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
462 TEST_LPM_ASSERT(hop[0] == next_hop_add);
463 TEST_LPM_ASSERT(hop[1] == next_hop_add);
465 TEST_LPM_ASSERT(hop[0] == UINT32_MAX);
466 TEST_LPM_ASSERT(hop[1] == UINT32_MAX);
468 TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
469 TEST_LPM_ASSERT(hop[3] == UINT32_MAX);
478 * - Add & lookup to hit invalid TBL24 entry
479 * - Add & lookup to hit valid TBL24 entry not extended
480 * - Add & lookup to hit valid extended TBL24 entry with invalid TBL8 entry
481 * - Add & lookup to hit valid extended TBL24 entry with valid TBL8 entry
487 struct rte_lpm *lpm = NULL;
488 struct rte_lpm_config config;
490 config.max_rules = MAX_RULES;
491 config.number_tbl8s = NUMBER_TBL8S;
493 uint32_t ip, ip_1, ip_2;
494 uint8_t depth, depth_1, depth_2;
495 uint32_t next_hop_add, next_hop_add_1, next_hop_add_2, next_hop_return;
498 /* Add & lookup to hit invalid TBL24 entry */
499 ip = IPv4(128, 0, 0, 0);
503 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
504 TEST_LPM_ASSERT(lpm != NULL);
506 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
507 TEST_LPM_ASSERT(status == 0);
509 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
510 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
512 status = rte_lpm_delete(lpm, ip, depth);
513 TEST_LPM_ASSERT(status == 0);
515 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
516 TEST_LPM_ASSERT(status == -ENOENT);
518 rte_lpm_delete_all(lpm);
520 /* Add & lookup to hit valid TBL24 entry not extended */
521 ip = IPv4(128, 0, 0, 0);
525 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
526 TEST_LPM_ASSERT(status == 0);
528 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
529 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
534 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
535 TEST_LPM_ASSERT(status == 0);
537 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
538 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
542 status = rte_lpm_delete(lpm, ip, depth);
543 TEST_LPM_ASSERT(status == 0);
547 status = rte_lpm_delete(lpm, ip, depth);
548 TEST_LPM_ASSERT(status == 0);
550 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
551 TEST_LPM_ASSERT(status == -ENOENT);
553 rte_lpm_delete_all(lpm);
555 /* Add & lookup to hit valid extended TBL24 entry with invalid TBL8
557 ip = IPv4(128, 0, 0, 0);
561 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
562 TEST_LPM_ASSERT(status == 0);
564 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
565 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
567 ip = IPv4(128, 0, 0, 5);
571 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
572 TEST_LPM_ASSERT(status == 0);
574 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
575 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
577 status = rte_lpm_delete(lpm, ip, depth);
578 TEST_LPM_ASSERT(status == 0);
580 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
581 TEST_LPM_ASSERT(status == -ENOENT);
583 ip = IPv4(128, 0, 0, 0);
587 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
588 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
590 status = rte_lpm_delete(lpm, ip, depth);
591 TEST_LPM_ASSERT(status == 0);
593 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
594 TEST_LPM_ASSERT(status == -ENOENT);
596 rte_lpm_delete_all(lpm);
598 /* Add & lookup to hit valid extended TBL24 entry with valid TBL8
600 ip_1 = IPv4(128, 0, 0, 0);
602 next_hop_add_1 = 101;
604 ip_2 = IPv4(128, 0, 0, 5);
606 next_hop_add_2 = 102;
610 status = rte_lpm_add(lpm, ip_1, depth_1, next_hop_add_1);
611 TEST_LPM_ASSERT(status == 0);
613 status = rte_lpm_lookup(lpm, ip_1, &next_hop_return);
614 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
616 status = rte_lpm_add(lpm, ip_2, depth_2, next_hop_add_2);
617 TEST_LPM_ASSERT(status == 0);
619 status = rte_lpm_lookup(lpm, ip_2, &next_hop_return);
620 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_2));
622 status = rte_lpm_delete(lpm, ip_2, depth_2);
623 TEST_LPM_ASSERT(status == 0);
625 status = rte_lpm_lookup(lpm, ip_2, &next_hop_return);
626 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
628 status = rte_lpm_delete(lpm, ip_1, depth_1);
629 TEST_LPM_ASSERT(status == 0);
631 status = rte_lpm_lookup(lpm, ip_1, &next_hop_return);
632 TEST_LPM_ASSERT(status == -ENOENT);
641 * - Add rule that covers a TBL24 range previously invalid & lookup (& delete &
643 * - Add rule that extends a TBL24 invalid entry & lookup (& delete & lookup)
644 * - Add rule that extends a TBL24 valid entry & lookup for both rules (&
646 * - Add rule that updates the next hop in TBL24 & lookup (& delete & lookup)
647 * - Add rule that updates the next hop in TBL8 & lookup (& delete & lookup)
648 * - Delete a rule that is not present in the TBL24 & lookup
649 * - Delete a rule that is not present in the TBL8 & lookup
656 struct rte_lpm *lpm = NULL;
657 struct rte_lpm_config config;
659 config.max_rules = MAX_RULES;
660 config.number_tbl8s = NUMBER_TBL8S;
662 uint32_t ip, next_hop_add, next_hop_return;
666 /* Add rule that covers a TBL24 range previously invalid & lookup
667 * (& delete & lookup) */
668 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
669 TEST_LPM_ASSERT(lpm != NULL);
671 ip = IPv4(128, 0, 0, 0);
675 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
676 TEST_LPM_ASSERT(status == 0);
678 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
679 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
681 status = rte_lpm_delete(lpm, ip, depth);
682 TEST_LPM_ASSERT(status == 0);
684 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
685 TEST_LPM_ASSERT(status == -ENOENT);
687 rte_lpm_delete_all(lpm);
689 ip = IPv4(128, 0, 0, 0);
693 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
694 TEST_LPM_ASSERT(status == 0);
696 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
697 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
699 status = rte_lpm_delete(lpm, ip, depth);
700 TEST_LPM_ASSERT(status == 0);
702 rte_lpm_delete_all(lpm);
704 /* Add rule that extends a TBL24 valid entry & lookup for both rules
705 * (& delete & lookup) */
707 ip = IPv4(128, 0, 0, 0);
711 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
712 TEST_LPM_ASSERT(status == 0);
714 ip = IPv4(128, 0, 0, 10);
718 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
719 TEST_LPM_ASSERT(status == 0);
721 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
722 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
724 ip = IPv4(128, 0, 0, 0);
727 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
728 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
730 ip = IPv4(128, 0, 0, 0);
733 status = rte_lpm_delete(lpm, ip, depth);
734 TEST_LPM_ASSERT(status == 0);
736 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
737 TEST_LPM_ASSERT(status == -ENOENT);
739 ip = IPv4(128, 0, 0, 10);
742 status = rte_lpm_delete(lpm, ip, depth);
743 TEST_LPM_ASSERT(status == 0);
745 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
746 TEST_LPM_ASSERT(status == -ENOENT);
748 rte_lpm_delete_all(lpm);
750 /* Add rule that updates the next hop in TBL24 & lookup
751 * (& delete & lookup) */
753 ip = IPv4(128, 0, 0, 0);
757 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
758 TEST_LPM_ASSERT(status == 0);
760 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
761 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
765 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
766 TEST_LPM_ASSERT(status == 0);
768 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
769 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
771 status = rte_lpm_delete(lpm, ip, depth);
772 TEST_LPM_ASSERT(status == 0);
774 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
775 TEST_LPM_ASSERT(status == -ENOENT);
777 rte_lpm_delete_all(lpm);
779 /* Add rule that updates the next hop in TBL8 & lookup
780 * (& delete & lookup) */
782 ip = IPv4(128, 0, 0, 0);
786 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
787 TEST_LPM_ASSERT(status == 0);
789 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
790 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
794 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
795 TEST_LPM_ASSERT(status == 0);
797 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
798 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
800 status = rte_lpm_delete(lpm, ip, depth);
801 TEST_LPM_ASSERT(status == 0);
803 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
804 TEST_LPM_ASSERT(status == -ENOENT);
806 rte_lpm_delete_all(lpm);
808 /* Delete a rule that is not present in the TBL24 & lookup */
810 ip = IPv4(128, 0, 0, 0);
813 status = rte_lpm_delete(lpm, ip, depth);
814 TEST_LPM_ASSERT(status < 0);
816 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
817 TEST_LPM_ASSERT(status == -ENOENT);
819 rte_lpm_delete_all(lpm);
821 /* Delete a rule that is not present in the TBL8 & lookup */
823 ip = IPv4(128, 0, 0, 0);
826 status = rte_lpm_delete(lpm, ip, depth);
827 TEST_LPM_ASSERT(status < 0);
829 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
830 TEST_LPM_ASSERT(status == -ENOENT);
838 * Add two rules, lookup to hit the more specific one, lookup to hit the less
839 * specific one delete the less specific rule and lookup previous values again;
840 * add a more specific rule than the existing rule, lookup again
847 struct rte_lpm *lpm = NULL;
848 struct rte_lpm_config config;
850 config.max_rules = MAX_RULES;
851 config.number_tbl8s = NUMBER_TBL8S;
853 uint32_t ip, next_hop_add, next_hop_return;
857 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
858 TEST_LPM_ASSERT(lpm != NULL);
860 ip = IPv4(128, 0, 0, 0);
864 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
865 TEST_LPM_ASSERT(status == 0);
867 ip = IPv4(128, 0, 0, 10);
871 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
872 TEST_LPM_ASSERT(status == 0);
874 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
875 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
877 ip = IPv4(128, 0, 0, 0);
880 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
881 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
883 ip = IPv4(128, 0, 0, 0);
886 status = rte_lpm_delete(lpm, ip, depth);
887 TEST_LPM_ASSERT(status == 0);
889 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
890 TEST_LPM_ASSERT(status == -ENOENT);
892 ip = IPv4(128, 0, 0, 10);
895 status = rte_lpm_delete(lpm, ip, depth);
896 TEST_LPM_ASSERT(status == 0);
898 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
899 TEST_LPM_ASSERT(status == -ENOENT);
907 * Add an extended rule (i.e. depth greater than 24, lookup (hit), delete,
908 * lookup (miss) in a for loop of 1000 times. This will check tbl8 extension
918 struct rte_lpm *lpm = NULL;
919 struct rte_lpm_config config;
921 config.max_rules = MAX_RULES;
922 config.number_tbl8s = NUMBER_TBL8S;
924 uint32_t ip, i, next_hop_add, next_hop_return;
928 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
929 TEST_LPM_ASSERT(lpm != NULL);
931 ip = IPv4(128, 0, 0, 0);
935 for (i = 0; i < 1000; i++) {
936 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
937 TEST_LPM_ASSERT(status == 0);
939 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
940 TEST_LPM_ASSERT((status == 0) &&
941 (next_hop_return == next_hop_add));
943 ipx4 = vect_set_epi32(ip, ip + 1, ip, ip - 1);
944 rte_lpm_lookupx4(lpm, ipx4, hop, UINT32_MAX);
945 TEST_LPM_ASSERT(hop[0] == UINT32_MAX);
946 TEST_LPM_ASSERT(hop[1] == next_hop_add);
947 TEST_LPM_ASSERT(hop[2] == UINT32_MAX);
948 TEST_LPM_ASSERT(hop[3] == next_hop_add);
950 status = rte_lpm_delete(lpm, ip, depth);
951 TEST_LPM_ASSERT(status == 0);
953 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
954 TEST_LPM_ASSERT(status == -ENOENT);
963 * Add a rule to tbl24, lookup (hit), then add a rule that will extend this
964 * tbl24 entry, lookup (hit). delete the rule that caused the tbl24 extension,
965 * lookup (miss) and repeat for loop of 1000 times. This will check tbl8
966 * extension and contraction.
973 struct rte_lpm *lpm = NULL;
974 struct rte_lpm_config config;
976 config.max_rules = MAX_RULES;
977 config.number_tbl8s = NUMBER_TBL8S;
979 uint32_t ip, i, next_hop_add_1, next_hop_add_2, next_hop_return;
983 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
984 TEST_LPM_ASSERT(lpm != NULL);
986 ip = IPv4(128, 0, 0, 0);
988 next_hop_add_1 = 100;
990 status = rte_lpm_add(lpm, ip, depth, next_hop_add_1);
991 TEST_LPM_ASSERT(status == 0);
993 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
994 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
997 next_hop_add_2 = 101;
999 for (i = 0; i < 1000; i++) {
1000 status = rte_lpm_add(lpm, ip, depth, next_hop_add_2);
1001 TEST_LPM_ASSERT(status == 0);
1003 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
1004 TEST_LPM_ASSERT((status == 0) &&
1005 (next_hop_return == next_hop_add_2));
1007 status = rte_lpm_delete(lpm, ip, depth);
1008 TEST_LPM_ASSERT(status == 0);
1010 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
1011 TEST_LPM_ASSERT((status == 0) &&
1012 (next_hop_return == next_hop_add_1));
1017 status = rte_lpm_delete(lpm, ip, depth);
1018 TEST_LPM_ASSERT(status == 0);
1020 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
1021 TEST_LPM_ASSERT(status == -ENOENT);
1029 * Fore TBL8 extension exhaustion. Add 256 rules that require a tbl8 extension.
1030 * No more tbl8 extensions will be allowed. Now add one more rule that required
1031 * a tbl8 extension and get fail.
1037 /* We only use depth = 32 in the loop below so we must make sure
1038 * that we have enough storage for all rules at that depth*/
1040 struct rte_lpm *lpm = NULL;
1041 struct rte_lpm_config config;
1043 config.max_rules = 256 * 32;
1044 config.number_tbl8s = NUMBER_TBL8S;
1046 uint32_t ip, next_hop_add, next_hop_return;
1050 /* Add enough space for 256 rules for every depth */
1051 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
1052 TEST_LPM_ASSERT(lpm != NULL);
1056 ip = IPv4(0, 0, 0, 0);
1058 /* Add 256 rules that require a tbl8 extension */
1059 for (; ip <= IPv4(0, 0, 255, 0); ip += 256) {
1060 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
1061 TEST_LPM_ASSERT(status == 0);
1063 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
1064 TEST_LPM_ASSERT((status == 0) &&
1065 (next_hop_return == next_hop_add));
1068 /* All tbl8 extensions have been used above. Try to add one more and
1070 ip = IPv4(1, 0, 0, 0);
1073 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
1074 TEST_LPM_ASSERT(status < 0);
1082 * Sequence of operations for find existing lpm table
1085 * - find existing table: hit
1086 * - find non-existing table: miss
1092 struct rte_lpm *lpm = NULL, *result = NULL;
1093 struct rte_lpm_config config;
1095 config.max_rules = 256 * 32;
1096 config.number_tbl8s = NUMBER_TBL8S;
1100 lpm = rte_lpm_create("lpm_find_existing", SOCKET_ID_ANY, &config);
1101 TEST_LPM_ASSERT(lpm != NULL);
1103 /* Try to find existing lpm */
1104 result = rte_lpm_find_existing("lpm_find_existing");
1105 TEST_LPM_ASSERT(result == lpm);
1107 /* Try to find non-existing lpm */
1108 result = rte_lpm_find_existing("lpm_find_non_existing");
1109 TEST_LPM_ASSERT(result == NULL);
1112 rte_lpm_delete_all(lpm);
1119 * test failure condition of overloading the tbl8 so no more will fit
1120 * Check we get an error return value in that case
1126 struct rte_lpm_config config;
1128 config.max_rules = 256 * 32;
1129 config.number_tbl8s = NUMBER_TBL8S;
1131 struct rte_lpm *lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
1133 /* ip loops through all possibilities for top 24 bits of address */
1134 for (ip = 0; ip < 0xFFFFFF; ip++) {
1135 /* add an entry within a different tbl8 each time, since
1136 * depth >24 and the top 24 bits are different */
1137 if (rte_lpm_add(lpm, (ip << 8) + 0xF0, 30, 0) < 0)
1141 if (ip != NUMBER_TBL8S) {
1142 printf("Error, unexpected failure with filling tbl8 groups\n");
1143 printf("Failed after %u additions, expected after %u\n",
1144 (unsigned)ip, (unsigned)NUMBER_TBL8S);
1152 * Test for overwriting of tbl8:
1153 * - add rule /32 and lookup
1154 * - add new rule /24 and lookup
1155 * - add third rule /25 and lookup
1156 * - lookup /32 and /24 rule to ensure the table has not been overwritten.
1161 struct rte_lpm *lpm = NULL;
1162 struct rte_lpm_config config;
1164 config.max_rules = MAX_RULES;
1165 config.number_tbl8s = NUMBER_TBL8S;
1167 const uint32_t ip_10_32 = IPv4(10, 10, 10, 2);
1168 const uint32_t ip_10_24 = IPv4(10, 10, 10, 0);
1169 const uint32_t ip_20_25 = IPv4(10, 10, 20, 2);
1170 const uint8_t d_ip_10_32 = 32,
1173 const uint32_t next_hop_ip_10_32 = 100,
1174 next_hop_ip_10_24 = 105,
1175 next_hop_ip_20_25 = 111;
1176 uint32_t next_hop_return = 0;
1179 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
1180 TEST_LPM_ASSERT(lpm != NULL);
1182 if ((status = rte_lpm_add(lpm, ip_10_32, d_ip_10_32,
1183 next_hop_ip_10_32)) < 0)
1186 status = rte_lpm_lookup(lpm, ip_10_32, &next_hop_return);
1187 uint32_t test_hop_10_32 = next_hop_return;
1188 TEST_LPM_ASSERT(status == 0);
1189 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
1191 if ((status = rte_lpm_add(lpm, ip_10_24, d_ip_10_24,
1192 next_hop_ip_10_24)) < 0)
1195 status = rte_lpm_lookup(lpm, ip_10_24, &next_hop_return);
1196 uint32_t test_hop_10_24 = next_hop_return;
1197 TEST_LPM_ASSERT(status == 0);
1198 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
1200 if ((status = rte_lpm_add(lpm, ip_20_25, d_ip_20_25,
1201 next_hop_ip_20_25)) < 0)
1204 status = rte_lpm_lookup(lpm, ip_20_25, &next_hop_return);
1205 uint32_t test_hop_20_25 = next_hop_return;
1206 TEST_LPM_ASSERT(status == 0);
1207 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_20_25);
1209 if (test_hop_10_32 == test_hop_10_24) {
1210 printf("Next hop return equal\n");
1214 if (test_hop_10_24 == test_hop_20_25) {
1215 printf("Next hop return equal\n");
1219 status = rte_lpm_lookup(lpm, ip_10_32, &next_hop_return);
1220 TEST_LPM_ASSERT(status == 0);
1221 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
1223 status = rte_lpm_lookup(lpm, ip_10_24, &next_hop_return);
1224 TEST_LPM_ASSERT(status == 0);
1225 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
1233 * Lookup performance test
1236 #define ITERATIONS (1 << 10)
1237 #define BATCH_SIZE (1 << 12)
1238 #define BULK_SIZE 32
1241 print_route_distribution(const struct route_rule *table, uint32_t n)
1245 printf("Route distribution per prefix width: \n");
1246 printf("DEPTH QUANTITY (PERCENT)\n");
1247 printf("--------------------------- \n");
1250 for (i = 1; i <= 32; i++) {
1251 unsigned depth_counter = 0;
1252 double percent_hits;
1254 for (j = 0; j < n; j++)
1255 if (table[j].depth == (uint8_t) i)
1258 percent_hits = ((double)depth_counter)/((double)n) * 100;
1259 printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits);
1267 struct rte_lpm *lpm = NULL;
1268 struct rte_lpm_config config;
1270 config.max_rules = 1000000;
1271 config.number_tbl8s = NUMBER_TBL8S;
1273 uint64_t begin, total_time, lpm_used_entries = 0;
1275 uint32_t next_hop_add = 0xAA, next_hop_return = 0;
1277 uint64_t cache_line_counter = 0;
1280 rte_srand(rte_rdtsc());
1282 printf("No. routes = %u\n", (unsigned) NUM_ROUTE_ENTRIES);
1284 print_route_distribution(large_route_table, (uint32_t) NUM_ROUTE_ENTRIES);
1286 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
1287 TEST_LPM_ASSERT(lpm != NULL);
1290 begin = rte_rdtsc();
1292 for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
1293 if (rte_lpm_add(lpm, large_route_table[i].ip,
1294 large_route_table[i].depth, next_hop_add) == 0)
1298 total_time = rte_rdtsc() - begin;
1300 printf("Unique added entries = %d\n", status);
1301 /* Obtain add statistics. */
1302 for (i = 0; i < RTE_LPM_TBL24_NUM_ENTRIES; i++) {
1303 if (lpm->tbl24[i].valid)
1307 if ((uint64_t)count < lpm_used_entries) {
1308 cache_line_counter++;
1309 count = lpm_used_entries;
1314 printf("Used table 24 entries = %u (%g%%)\n",
1315 (unsigned) lpm_used_entries,
1316 (lpm_used_entries * 100.0) / RTE_LPM_TBL24_NUM_ENTRIES);
1317 printf("64 byte Cache entries used = %u (%u bytes)\n",
1318 (unsigned) cache_line_counter, (unsigned) cache_line_counter * 64);
1320 printf("Average LPM Add: %g cycles\n",
1321 (double)total_time / NUM_ROUTE_ENTRIES);
1323 /* Measure single Lookup */
1327 for (i = 0; i < ITERATIONS; i++) {
1328 static uint32_t ip_batch[BATCH_SIZE];
1330 for (j = 0; j < BATCH_SIZE; j++)
1331 ip_batch[j] = rte_rand();
1333 /* Lookup per batch */
1334 begin = rte_rdtsc();
1336 for (j = 0; j < BATCH_SIZE; j++) {
1337 if (rte_lpm_lookup(lpm, ip_batch[j], &next_hop_return) != 0)
1341 total_time += rte_rdtsc() - begin;
1344 printf("Average LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
1345 (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1346 (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1348 /* Measure bulk Lookup */
1351 for (i = 0; i < ITERATIONS; i++) {
1352 static uint32_t ip_batch[BATCH_SIZE];
1353 uint32_t next_hops[BULK_SIZE];
1355 /* Create array of random IP addresses */
1356 for (j = 0; j < BATCH_SIZE; j++)
1357 ip_batch[j] = rte_rand();
1359 /* Lookup per batch */
1360 begin = rte_rdtsc();
1361 for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) {
1363 rte_lpm_lookup_bulk(lpm, &ip_batch[j], next_hops, BULK_SIZE);
1364 for (k = 0; k < BULK_SIZE; k++)
1365 if (unlikely(!(next_hops[k] & RTE_LPM_LOOKUP_SUCCESS)))
1369 total_time += rte_rdtsc() - begin;
1371 printf("BULK LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
1372 (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1373 (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1375 /* Measure LookupX4 */
1378 for (i = 0; i < ITERATIONS; i++) {
1379 static uint32_t ip_batch[BATCH_SIZE];
1380 uint32_t next_hops[4];
1382 /* Create array of random IP addresses */
1383 for (j = 0; j < BATCH_SIZE; j++)
1384 ip_batch[j] = rte_rand();
1386 /* Lookup per batch */
1387 begin = rte_rdtsc();
1388 for (j = 0; j < BATCH_SIZE; j += RTE_DIM(next_hops)) {
1392 ipx4 = vect_loadu_sil128((xmm_t *)(ip_batch + j));
1393 ipx4 = *(xmm_t *)(ip_batch + j);
1394 rte_lpm_lookupx4(lpm, ipx4, next_hops, UINT32_MAX);
1395 for (k = 0; k < RTE_DIM(next_hops); k++)
1396 if (unlikely(next_hops[k] == UINT32_MAX))
1400 total_time += rte_rdtsc() - begin;
1402 printf("LPM LookupX4: %.1f cycles (fails = %.1f%%)\n",
1403 (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1404 (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1408 begin = rte_rdtsc();
1410 for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
1411 /* rte_lpm_delete(lpm, ip, depth) */
1412 status += rte_lpm_delete(lpm, large_route_table[i].ip,
1413 large_route_table[i].depth);
1416 total_time += rte_rdtsc() - begin;
1418 printf("Average LPM Delete: %g cycles\n",
1419 (double)total_time / NUM_ROUTE_ENTRIES);
1421 rte_lpm_delete_all(lpm);
1428 * Do all unit and performance tests.
1435 int status, global_status = 0;
1437 for (i = 0; i < NUM_LPM_TESTS; i++) {
1438 status = tests[i]();
1440 printf("ERROR: LPM Test %s: FAIL\n", RTE_STR(tests[i]));
1441 global_status = status;
1445 return global_status;
1448 static struct test_command lpm_cmd = {
1449 .command = "lpm_autotest",
1450 .callback = test_lpm,
1452 REGISTER_TEST_COMMAND(lpm_cmd);