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>
39 #include <cmdline_parse.h>
41 #include <rte_common.h>
42 #include <rte_cycles.h>
43 #include <rte_memory.h>
44 #include <rte_random.h>
45 #include <rte_branch_prediction.h>
54 #include "test_lpm_routes.h"
56 #define TEST_LPM_ASSERT(cond) do { \
58 printf("Error at line %d: \n", __LINE__); \
63 typedef int32_t (* rte_lpm_test)(void);
65 static int32_t test0(void);
66 static int32_t test1(void);
67 static int32_t test2(void);
68 static int32_t test3(void);
69 static int32_t test4(void);
70 static int32_t test5(void);
71 static int32_t test6(void);
72 static int32_t test7(void);
73 static int32_t test8(void);
74 static int32_t test9(void);
75 static int32_t test10(void);
76 static int32_t test11(void);
77 static int32_t test12(void);
78 static int32_t test13(void);
79 static int32_t test14(void);
80 static int32_t test15(void);
81 static int32_t test16(void);
82 static int32_t test17(void);
83 static int32_t perf_test(void);
85 rte_lpm_test tests[] = {
108 #define NUM_LPM_TESTS (sizeof(tests)/sizeof(tests[0]))
110 #define MAX_RULES 256
114 * Check that rte_lpm_create fails gracefully for incorrect user input
120 struct rte_lpm *lpm = NULL;
122 /* rte_lpm_create: lpm name == NULL */
123 lpm = rte_lpm_create(NULL, SOCKET_ID_ANY, MAX_RULES, 0);
124 TEST_LPM_ASSERT(lpm == NULL);
126 /* rte_lpm_create: max_rules = 0 */
127 /* Note: __func__ inserts the function name, in this case "test0". */
128 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, 0, 0);
129 TEST_LPM_ASSERT(lpm == NULL);
131 /* socket_id < -1 is invalid */
132 lpm = rte_lpm_create(__func__, -2, MAX_RULES, 0);
133 TEST_LPM_ASSERT(lpm == NULL);
139 * Create lpm table then delete lpm table 100 times
140 * Use a slightly different rules size each time
145 struct rte_lpm *lpm = NULL;
148 /* rte_lpm_free: Free NULL */
149 for (i = 0; i < 100; i++) {
150 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES - i, 0);
151 TEST_LPM_ASSERT(lpm != NULL);
156 /* Can not test free so return success */
161 * Call rte_lpm_free for NULL pointer user input. Note: free has no return and
162 * therefore it is impossible to check for failure but this test is added to
163 * increase function coverage metrics and to validate that freeing null does
169 struct rte_lpm *lpm = NULL;
171 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, RTE_LPM_HEAP);
172 TEST_LPM_ASSERT(lpm != NULL);
180 * Check that rte_lpm_add fails gracefully for incorrect user input arguments
185 struct rte_lpm *lpm = NULL;
186 uint32_t ip = IPv4(0, 0, 0, 0);
187 uint8_t depth = 24, next_hop = 100;
190 /* rte_lpm_add: lpm == NULL */
191 status = rte_lpm_add(NULL, ip, depth, next_hop);
192 TEST_LPM_ASSERT(status < 0);
194 /*Create vaild lpm to use in rest of test. */
195 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
196 TEST_LPM_ASSERT(lpm != NULL);
198 /* rte_lpm_add: depth < 1 */
199 status = rte_lpm_add(lpm, ip, 0, next_hop);
200 TEST_LPM_ASSERT(status < 0);
202 /* rte_lpm_add: depth > MAX_DEPTH */
203 status = rte_lpm_add(lpm, ip, (MAX_DEPTH + 1), next_hop);
204 TEST_LPM_ASSERT(status < 0);
212 * Check that rte_lpm_delete fails gracefully for incorrect user input
218 struct rte_lpm *lpm = NULL;
219 uint32_t ip = IPv4(0, 0, 0, 0);
223 /* rte_lpm_delete: lpm == NULL */
224 status = rte_lpm_delete(NULL, ip, depth);
225 TEST_LPM_ASSERT(status < 0);
227 /*Create vaild lpm to use in rest of test. */
228 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
229 TEST_LPM_ASSERT(lpm != NULL);
231 /* rte_lpm_delete: depth < 1 */
232 status = rte_lpm_delete(lpm, ip, 0);
233 TEST_LPM_ASSERT(status < 0);
235 /* rte_lpm_delete: depth > MAX_DEPTH */
236 status = rte_lpm_delete(lpm, ip, (MAX_DEPTH + 1));
237 TEST_LPM_ASSERT(status < 0);
245 * Check that rte_lpm_lookup fails gracefully for incorrect user input
251 #if defined(RTE_LIBRTE_LPM_DEBUG)
252 struct rte_lpm *lpm = NULL;
253 uint32_t ip = IPv4(0, 0, 0, 0);
254 uint8_t next_hop_return = 0;
257 /* rte_lpm_lookup: lpm == NULL */
258 status = rte_lpm_lookup(NULL, ip, &next_hop_return);
259 TEST_LPM_ASSERT(status < 0);
261 /*Create vaild lpm to use in rest of test. */
262 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
263 TEST_LPM_ASSERT(lpm != NULL);
265 /* rte_lpm_lookup: depth < 1 */
266 status = rte_lpm_lookup(lpm, ip, NULL);
267 TEST_LPM_ASSERT(status < 0);
277 * Call add, lookup and delete for a single rule with depth <= 24
282 struct rte_lpm *lpm = NULL;
283 uint32_t ip = IPv4(0, 0, 0, 0);
284 uint8_t depth = 24, next_hop_add = 100, next_hop_return = 0;
287 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
288 TEST_LPM_ASSERT(lpm != NULL);
290 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
291 TEST_LPM_ASSERT(status == 0);
293 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
294 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
296 status = rte_lpm_delete(lpm, ip, depth);
297 TEST_LPM_ASSERT(status == 0);
299 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
300 TEST_LPM_ASSERT(status == -ENOENT);
308 * Call add, lookup and delete for a single rule with depth > 24
314 struct rte_lpm *lpm = NULL;
315 uint32_t ip = IPv4(0, 0, 0, 0);
316 uint8_t depth = 32, next_hop_add = 100, next_hop_return = 0;
319 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
320 TEST_LPM_ASSERT(lpm != NULL);
322 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
323 TEST_LPM_ASSERT(status == 0);
325 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
326 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
328 status = rte_lpm_delete(lpm, ip, depth);
329 TEST_LPM_ASSERT(status == 0);
331 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
332 TEST_LPM_ASSERT(status == -ENOENT);
340 * Use rte_lpm_add to add rules which effect only the second half of the lpm
341 * table. Use all possible depths ranging from 1..32. Set the next hop = to the
342 * depth. Check lookup hit for on every add and check for lookup miss on the
343 * first half of the lpm table after each add. Finally delete all rules going
344 * backwards (i.e. from depth = 32 ..1) and carry out a lookup after each
345 * delete. The lookup should return the next_hop_add value related to the
346 * previous depth value (i.e. depth -1).
351 struct rte_lpm *lpm = NULL;
352 uint32_t ip1 = IPv4(127, 255, 255, 255), ip2 = IPv4(128, 0, 0, 0);
353 uint8_t depth, next_hop_add, next_hop_return;
356 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
357 TEST_LPM_ASSERT(lpm != NULL);
359 /* Loop with rte_lpm_add. */
360 for (depth = 1; depth <= 32; depth++) {
361 /* Let the next_hop_add value = depth. Just for change. */
362 next_hop_add = depth;
364 status = rte_lpm_add(lpm, ip2, depth, next_hop_add);
365 TEST_LPM_ASSERT(status == 0);
367 /* Check IP in first half of tbl24 which should be empty. */
368 status = rte_lpm_lookup(lpm, ip1, &next_hop_return);
369 TEST_LPM_ASSERT(status == -ENOENT);
371 status = rte_lpm_lookup(lpm, ip2, &next_hop_return);
372 TEST_LPM_ASSERT((status == 0) &&
373 (next_hop_return == next_hop_add));
376 /* Loop with rte_lpm_delete. */
377 for (depth = 32; depth >= 1; depth--) {
378 next_hop_add = (uint8_t) (depth - 1);
380 status = rte_lpm_delete(lpm, ip2, depth);
381 TEST_LPM_ASSERT(status == 0);
383 status = rte_lpm_lookup(lpm, ip2, &next_hop_return);
386 TEST_LPM_ASSERT((status == 0) &&
387 (next_hop_return == next_hop_add));
390 TEST_LPM_ASSERT(status == -ENOENT);
393 status = rte_lpm_lookup(lpm, ip1, &next_hop_return);
394 TEST_LPM_ASSERT(status == -ENOENT);
403 * - Add & lookup to hit invalid TBL24 entry
404 * - Add & lookup to hit valid TBL24 entry not extended
405 * - Add & lookup to hit valid extended TBL24 entry with invalid TBL8 entry
406 * - Add & lookup to hit valid extended TBL24 entry with valid TBL8 entry
412 struct rte_lpm *lpm = NULL;
413 uint32_t ip, ip_1, ip_2;
414 uint8_t depth, depth_1, depth_2, next_hop_add, next_hop_add_1,
415 next_hop_add_2, next_hop_return;
418 /* Add & lookup to hit invalid TBL24 entry */
419 ip = IPv4(128, 0, 0, 0);
423 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
424 TEST_LPM_ASSERT(lpm != NULL);
426 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
427 TEST_LPM_ASSERT(status == 0);
429 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
430 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
432 status = rte_lpm_delete(lpm, ip, depth);
433 TEST_LPM_ASSERT(status == 0);
435 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
436 TEST_LPM_ASSERT(status == -ENOENT);
438 rte_lpm_delete_all(lpm);
440 /* Add & lookup to hit valid TBL24 entry not extended */
441 ip = IPv4(128, 0, 0, 0);
445 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
446 TEST_LPM_ASSERT(status == 0);
448 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
449 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
454 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
455 TEST_LPM_ASSERT(status == 0);
457 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
458 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
462 status = rte_lpm_delete(lpm, ip, depth);
463 TEST_LPM_ASSERT(status == 0);
467 status = rte_lpm_delete(lpm, ip, depth);
468 TEST_LPM_ASSERT(status == 0);
470 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
471 TEST_LPM_ASSERT(status == -ENOENT);
473 rte_lpm_delete_all(lpm);
475 /* Add & lookup to hit valid extended TBL24 entry with invalid TBL8
477 ip = IPv4(128, 0, 0, 0);
481 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
482 TEST_LPM_ASSERT(status == 0);
484 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
485 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
487 ip = IPv4(128, 0, 0, 5);
491 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
492 TEST_LPM_ASSERT(status == 0);
494 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
495 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
497 status = rte_lpm_delete(lpm, ip, depth);
498 TEST_LPM_ASSERT(status == 0);
500 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
501 TEST_LPM_ASSERT(status == -ENOENT);
503 ip = IPv4(128, 0, 0, 0);
507 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
508 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
510 status = rte_lpm_delete(lpm, ip, depth);
511 TEST_LPM_ASSERT(status == 0);
513 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
514 TEST_LPM_ASSERT(status == -ENOENT);
516 rte_lpm_delete_all(lpm);
518 /* Add & lookup to hit valid extended TBL24 entry with valid TBL8
520 ip_1 = IPv4(128, 0, 0, 0);
522 next_hop_add_1 = 101;
524 ip_2 = IPv4(128, 0, 0, 5);
526 next_hop_add_2 = 102;
530 status = rte_lpm_add(lpm, ip_1, depth_1, next_hop_add_1);
531 TEST_LPM_ASSERT(status == 0);
533 status = rte_lpm_lookup(lpm, ip_1, &next_hop_return);
534 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
536 status = rte_lpm_add(lpm, ip_2, depth_2, next_hop_add_2);
537 TEST_LPM_ASSERT(status == 0);
539 status = rte_lpm_lookup(lpm, ip_2, &next_hop_return);
540 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_2));
542 status = rte_lpm_delete(lpm, ip_2, depth_2);
543 TEST_LPM_ASSERT(status == 0);
545 status = rte_lpm_lookup(lpm, ip_2, &next_hop_return);
546 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
548 status = rte_lpm_delete(lpm, ip_1, depth_1);
549 TEST_LPM_ASSERT(status == 0);
551 status = rte_lpm_lookup(lpm, ip_1, &next_hop_return);
552 TEST_LPM_ASSERT(status == -ENOENT);
561 * - Add rule that covers a TBL24 range previously invalid & lookup (& delete &
563 * - Add rule that extends a TBL24 invalid entry & lookup (& delete & lookup)
564 * - Add rule that extends a TBL24 valid entry & lookup for both rules (&
566 * - Add rule that updates the next hop in TBL24 & lookup (& delete & lookup)
567 * - Add rule that updates the next hop in TBL8 & lookup (& delete & lookup)
568 * - Delete a rule that is not present in the TBL24 & lookup
569 * - Delete a rule that is not present in the TBL8 & lookup
576 struct rte_lpm *lpm = NULL;
578 uint8_t depth, next_hop_add, next_hop_return;
581 /* Add rule that covers a TBL24 range previously invalid & lookup
582 * (& delete & lookup) */
583 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, RTE_LPM_HEAP);
584 TEST_LPM_ASSERT(lpm != NULL);
586 ip = IPv4(128, 0, 0, 0);
590 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
591 TEST_LPM_ASSERT(status == 0);
593 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
594 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
596 status = rte_lpm_delete(lpm, ip, depth);
597 TEST_LPM_ASSERT(status == 0);
599 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
600 TEST_LPM_ASSERT(status == -ENOENT);
602 rte_lpm_delete_all(lpm);
604 ip = IPv4(128, 0, 0, 0);
608 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
609 TEST_LPM_ASSERT(status == 0);
611 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
612 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
614 status = rte_lpm_delete(lpm, ip, depth);
615 TEST_LPM_ASSERT(status == 0);
617 rte_lpm_delete_all(lpm);
619 /* Add rule that extends a TBL24 valid entry & lookup for both rules
620 * (& delete & lookup) */
622 ip = IPv4(128, 0, 0, 0);
626 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
627 TEST_LPM_ASSERT(status == 0);
629 ip = IPv4(128, 0, 0, 10);
633 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
634 TEST_LPM_ASSERT(status == 0);
636 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
637 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
639 ip = IPv4(128, 0, 0, 0);
642 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
643 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
645 ip = IPv4(128, 0, 0, 0);
648 status = rte_lpm_delete(lpm, ip, depth);
649 TEST_LPM_ASSERT(status == 0);
651 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
652 TEST_LPM_ASSERT(status == -ENOENT);
654 ip = IPv4(128, 0, 0, 10);
657 status = rte_lpm_delete(lpm, ip, depth);
658 TEST_LPM_ASSERT(status == 0);
660 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
661 TEST_LPM_ASSERT(status == -ENOENT);
663 rte_lpm_delete_all(lpm);
665 /* Add rule that updates the next hop in TBL24 & lookup
666 * (& delete & lookup) */
668 ip = IPv4(128, 0, 0, 0);
672 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
673 TEST_LPM_ASSERT(status == 0);
675 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
676 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
680 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
681 TEST_LPM_ASSERT(status == 0);
683 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
684 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
686 status = rte_lpm_delete(lpm, ip, depth);
687 TEST_LPM_ASSERT(status == 0);
689 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
690 TEST_LPM_ASSERT(status == -ENOENT);
692 rte_lpm_delete_all(lpm);
694 /* Add rule that updates the next hop in TBL8 & lookup
695 * (& delete & lookup) */
697 ip = IPv4(128, 0, 0, 0);
701 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
702 TEST_LPM_ASSERT(status == 0);
704 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
705 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
709 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
710 TEST_LPM_ASSERT(status == 0);
712 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
713 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
715 status = rte_lpm_delete(lpm, ip, depth);
716 TEST_LPM_ASSERT(status == 0);
718 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
719 TEST_LPM_ASSERT(status == -ENOENT);
721 rte_lpm_delete_all(lpm);
723 /* Delete a rule that is not present in the TBL24 & lookup */
725 ip = IPv4(128, 0, 0, 0);
728 status = rte_lpm_delete(lpm, ip, depth);
729 TEST_LPM_ASSERT(status < 0);
731 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
732 TEST_LPM_ASSERT(status == -ENOENT);
734 rte_lpm_delete_all(lpm);
736 /* Delete a rule that is not present in the TBL8 & lookup */
738 ip = IPv4(128, 0, 0, 0);
741 status = rte_lpm_delete(lpm, ip, depth);
742 TEST_LPM_ASSERT(status < 0);
744 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
745 TEST_LPM_ASSERT(status == -ENOENT);
753 * Add two rules, lookup to hit the more specific one, lookup to hit the less
754 * specific one delete the less specific rule and lookup previous values again;
755 * add a more specific rule than the existing rule, lookup again
762 struct rte_lpm *lpm = NULL;
764 uint8_t depth, next_hop_add, next_hop_return;
767 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
768 TEST_LPM_ASSERT(lpm != NULL);
770 ip = IPv4(128, 0, 0, 0);
774 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
775 TEST_LPM_ASSERT(status == 0);
777 ip = IPv4(128, 0, 0, 10);
781 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
782 TEST_LPM_ASSERT(status == 0);
784 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
785 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
787 ip = IPv4(128, 0, 0, 0);
790 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
791 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add));
793 ip = IPv4(128, 0, 0, 0);
796 status = rte_lpm_delete(lpm, ip, depth);
797 TEST_LPM_ASSERT(status == 0);
799 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
800 TEST_LPM_ASSERT(status == -ENOENT);
802 ip = IPv4(128, 0, 0, 10);
805 status = rte_lpm_delete(lpm, ip, depth);
806 TEST_LPM_ASSERT(status == 0);
808 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
809 TEST_LPM_ASSERT(status == -ENOENT);
817 * Add an extended rule (i.e. depth greater than 24, lookup (hit), delete,
818 * lookup (miss) in a for loop of 1000 times. This will check tbl8 extension
826 struct rte_lpm *lpm = NULL;
828 uint8_t depth, next_hop_add, next_hop_return;
831 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
832 TEST_LPM_ASSERT(lpm != NULL);
834 ip = IPv4(128, 0, 0, 0);
838 for (i = 0; i < 1000; i++) {
839 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
840 TEST_LPM_ASSERT(status == 0);
842 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
843 TEST_LPM_ASSERT((status == 0) &&
844 (next_hop_return == next_hop_add));
846 status = rte_lpm_delete(lpm, ip, depth);
847 TEST_LPM_ASSERT(status == 0);
849 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
850 TEST_LPM_ASSERT(status == -ENOENT);
859 * Add a rule to tbl24, lookup (hit), then add a rule that will extend this
860 * tbl24 entry, lookup (hit). delete the rule that caused the tbl24 extension,
861 * lookup (miss) and repeat for loop of 1000 times. This will check tbl8
862 * extension and contraction.
869 struct rte_lpm *lpm = NULL;
871 uint8_t depth, next_hop_add_1, next_hop_add_2, next_hop_return;
874 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
875 TEST_LPM_ASSERT(lpm != NULL);
877 ip = IPv4(128, 0, 0, 0);
879 next_hop_add_1 = 100;
881 status = rte_lpm_add(lpm, ip, depth, next_hop_add_1);
882 TEST_LPM_ASSERT(status == 0);
884 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
885 TEST_LPM_ASSERT((status == 0) && (next_hop_return == next_hop_add_1));
888 next_hop_add_2 = 101;
890 for (i = 0; i < 1000; i++) {
891 status = rte_lpm_add(lpm, ip, depth, next_hop_add_2);
892 TEST_LPM_ASSERT(status == 0);
894 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
895 TEST_LPM_ASSERT((status == 0) &&
896 (next_hop_return == next_hop_add_2));
898 status = rte_lpm_delete(lpm, ip, depth);
899 TEST_LPM_ASSERT(status == 0);
901 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
902 TEST_LPM_ASSERT((status == 0) &&
903 (next_hop_return == next_hop_add_1));
908 status = rte_lpm_delete(lpm, ip, depth);
909 TEST_LPM_ASSERT(status == 0);
911 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
912 TEST_LPM_ASSERT(status == -ENOENT);
920 * Fore TBL8 extension exhaustion. Add 256 rules that require a tbl8 extension.
921 * No more tbl8 extensions will be allowed. Now add one more rule that required
922 * a tbl8 extension and get fail.
928 /* We only use depth = 32 in the loop below so we must make sure
929 * that we have enough storage for all rules at that depth*/
931 struct rte_lpm *lpm = NULL;
933 uint8_t depth, next_hop_add, next_hop_return;
936 /* Add enough space for 256 rules for every depth */
937 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, 256 * 32, 0);
938 TEST_LPM_ASSERT(lpm != NULL);
942 ip = IPv4(0, 0, 0, 0);
944 /* Add 256 rules that require a tbl8 extension */
945 for (; ip <= IPv4(0, 0, 255, 0); ip += 256) {
946 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
947 TEST_LPM_ASSERT(status == 0);
949 status = rte_lpm_lookup(lpm, ip, &next_hop_return);
950 TEST_LPM_ASSERT((status == 0) &&
951 (next_hop_return == next_hop_add));
954 /* All tbl8 extensions have been used above. Try to add one more and
956 ip = IPv4(1, 0, 0, 0);
959 status = rte_lpm_add(lpm, ip, depth, next_hop_add);
960 TEST_LPM_ASSERT(status < 0);
968 * Sequence of operations for find existing lpm table
971 * - find existing table: hit
972 * - find non-existing table: miss
978 struct rte_lpm *lpm = NULL, *result = NULL;
981 lpm = rte_lpm_create("lpm_find_existing", SOCKET_ID_ANY, 256 * 32, 0);
982 TEST_LPM_ASSERT(lpm != NULL);
984 /* Try to find existing lpm */
985 result = rte_lpm_find_existing("lpm_find_existing");
986 TEST_LPM_ASSERT(result == lpm);
988 /* Try to find non-existing lpm */
989 result = rte_lpm_find_existing("lpm_find_non_existing");
990 TEST_LPM_ASSERT(result == NULL);
993 rte_lpm_delete_all(lpm);
1000 * test failure condition of overloading the tbl8 so no more will fit
1001 * Check we get an error return value in that case
1007 struct rte_lpm *lpm = rte_lpm_create(__func__, SOCKET_ID_ANY,
1010 /* ip loops through all possibilities for top 24 bits of address */
1011 for (ip = 0; ip < 0xFFFFFF; ip++){
1012 /* add an entry within a different tbl8 each time, since
1013 * depth >24 and the top 24 bits are different */
1014 if (rte_lpm_add(lpm, (ip << 8) + 0xF0, 30, 0) < 0)
1018 if (ip != RTE_LPM_TBL8_NUM_GROUPS) {
1019 printf("Error, unexpected failure with filling tbl8 groups\n");
1020 printf("Failed after %u additions, expected after %u\n",
1021 (unsigned)ip, (unsigned)RTE_LPM_TBL8_NUM_GROUPS);
1029 * Test for overwriting of tbl8:
1030 * - add rule /32 and lookup
1031 * - add new rule /24 and lookup
1032 * - add third rule /25 and lookup
1033 * - lookup /32 and /24 rule to ensure the table has not been overwritten.
1038 struct rte_lpm *lpm = NULL;
1039 const uint32_t ip_10_32 = IPv4(10, 10, 10, 2);
1040 const uint32_t ip_10_24 = IPv4(10, 10, 10, 0);
1041 const uint32_t ip_20_25 = IPv4(10, 10, 20, 2);
1042 const uint8_t d_ip_10_32 = 32,
1045 const uint8_t next_hop_ip_10_32 = 100,
1046 next_hop_ip_10_24 = 105,
1047 next_hop_ip_20_25 = 111;
1048 uint8_t next_hop_return = 0;
1051 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, MAX_RULES, 0);
1052 TEST_LPM_ASSERT(lpm != NULL);
1054 if ((status = rte_lpm_add(lpm, ip_10_32, d_ip_10_32,
1055 next_hop_ip_10_32)) < 0)
1058 status = rte_lpm_lookup(lpm, ip_10_32, &next_hop_return);
1059 uint8_t test_hop_10_32 = next_hop_return;
1060 TEST_LPM_ASSERT(status == 0);
1061 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
1063 if ((status = rte_lpm_add(lpm, ip_10_24, d_ip_10_24,
1064 next_hop_ip_10_24)) < 0)
1067 status = rte_lpm_lookup(lpm, ip_10_24, &next_hop_return);
1068 uint8_t test_hop_10_24 = next_hop_return;
1069 TEST_LPM_ASSERT(status == 0);
1070 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
1072 if ((status = rte_lpm_add(lpm, ip_20_25, d_ip_20_25,
1073 next_hop_ip_20_25)) < 0)
1076 status = rte_lpm_lookup(lpm, ip_20_25, &next_hop_return);
1077 uint8_t test_hop_20_25 = next_hop_return;
1078 TEST_LPM_ASSERT(status == 0);
1079 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_20_25);
1081 if (test_hop_10_32 == test_hop_10_24) {
1082 printf("Next hop return equal\n");
1086 if (test_hop_10_24 == test_hop_20_25){
1087 printf("Next hop return equal\n");
1091 status = rte_lpm_lookup(lpm, ip_10_32, &next_hop_return);
1092 TEST_LPM_ASSERT(status == 0);
1093 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
1095 status = rte_lpm_lookup(lpm, ip_10_24, &next_hop_return);
1096 TEST_LPM_ASSERT(status == 0);
1097 TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
1105 * Lookup performance test
1108 #define ITERATIONS (1 << 10)
1109 #define BATCH_SIZE (1 << 12)
1110 #define BULK_SIZE 32
1113 print_route_distribution(const struct route_rule *table, uint32_t n)
1117 printf("Route distribution per prefix width: \n");
1118 printf("DEPTH QUANTITY (PERCENT)\n");
1119 printf("--------------------------- \n");
1122 for(i = 1; i <= 32; i++) {
1123 unsigned depth_counter = 0;
1124 double percent_hits;
1126 for (j = 0; j < n; j++)
1127 if (table[j].depth == (uint8_t) i)
1130 percent_hits = ((double)depth_counter)/((double)n) * 100;
1131 printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits);
1139 struct rte_lpm *lpm = NULL;
1140 uint64_t begin, total_time, lpm_used_entries = 0;
1142 uint8_t next_hop_add = 0xAA, next_hop_return = 0;
1144 uint64_t cache_line_counter = 0;
1147 rte_srand(rte_rdtsc());
1149 printf("No. routes = %u\n", (unsigned) NUM_ROUTE_ENTRIES);
1151 print_route_distribution(large_route_table, (uint32_t) NUM_ROUTE_ENTRIES);
1153 lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, 1000000, 0);
1154 TEST_LPM_ASSERT(lpm != NULL);
1157 begin = rte_rdtsc();
1159 for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
1160 if (rte_lpm_add(lpm, large_route_table[i].ip,
1161 large_route_table[i].depth, next_hop_add) == 0)
1165 total_time = rte_rdtsc() - begin;
1167 printf("Unique added entries = %d\n", status);
1168 /* Obtain add statistics. */
1169 for (i = 0; i < RTE_LPM_TBL24_NUM_ENTRIES; i++) {
1170 if (lpm->tbl24[i].valid)
1174 if ((uint64_t)count < lpm_used_entries) {
1175 cache_line_counter++;
1176 count = lpm_used_entries;
1181 printf("Used table 24 entries = %u (%g%%)\n",
1182 (unsigned) lpm_used_entries,
1183 (lpm_used_entries * 100.0) / RTE_LPM_TBL24_NUM_ENTRIES);
1184 printf("64 byte Cache entries used = %u (%u bytes)\n",
1185 (unsigned) cache_line_counter, (unsigned) cache_line_counter * 64);
1187 printf("Average LPM Add: %g cycles\n", (double)total_time / NUM_ROUTE_ENTRIES);
1189 /* Measure single Lookup */
1193 for (i = 0; i < ITERATIONS; i ++) {
1194 static uint32_t ip_batch[BATCH_SIZE];
1196 for (j = 0; j < BATCH_SIZE; j ++)
1197 ip_batch[j] = rte_rand();
1199 /* Lookup per batch */
1200 begin = rte_rdtsc();
1202 for (j = 0; j < BATCH_SIZE; j ++) {
1203 if (rte_lpm_lookup(lpm, ip_batch[j], &next_hop_return) != 0)
1207 total_time += rte_rdtsc() - begin;
1210 printf("Average LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
1211 (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1212 (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1214 /* Measure bulk Lookup */
1217 for (i = 0; i < ITERATIONS; i ++) {
1218 static uint32_t ip_batch[BATCH_SIZE];
1219 uint16_t next_hops[BULK_SIZE];
1221 /* Create array of random IP addresses */
1222 for (j = 0; j < BATCH_SIZE; j ++)
1223 ip_batch[j] = rte_rand();
1225 /* Lookup per batch */
1226 begin = rte_rdtsc();
1227 for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) {
1229 rte_lpm_lookup_bulk(lpm, &ip_batch[j], next_hops, BULK_SIZE);
1230 for (k = 0; k < BULK_SIZE; k++)
1231 if (unlikely(!(next_hops[k] & RTE_LPM_LOOKUP_SUCCESS)))
1235 total_time += rte_rdtsc() - begin;
1237 printf("BULK LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
1238 (double)total_time / ((double)ITERATIONS * BATCH_SIZE),
1239 (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
1243 begin = rte_rdtsc();
1245 for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
1246 /* rte_lpm_delete(lpm, ip, depth) */
1247 status += rte_lpm_delete(lpm, large_route_table[i].ip,
1248 large_route_table[i].depth);
1251 total_time += rte_rdtsc() - begin;
1253 printf("Average LPM Delete: %g cycles\n",
1254 (double)total_time / NUM_ROUTE_ENTRIES);
1256 rte_lpm_delete_all(lpm);
1263 * Do all unit and performance tests.
1270 int status, global_status = 0;
1272 for (i = 0; i < NUM_LPM_TESTS; i++) {
1273 status = tests[i]();
1275 printf("ERROR: LPM Test %s: FAIL\n", RTE_STR(tests[i]));
1276 global_status = status;
1280 return global_status;
1283 #else /* RTE_LIBRTE_LPM */
1288 printf("The LPM library is not included in this build\n");
1292 #endif /* RTE_LIBRTE_LPM */