1809f0800SChristian Ehrhardt/*-
2809f0800SChristian Ehrhardt *   BSD LICENSE
3809f0800SChristian Ehrhardt *
4809f0800SChristian Ehrhardt *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5809f0800SChristian Ehrhardt *   All rights reserved.
6809f0800SChristian Ehrhardt *
7809f0800SChristian Ehrhardt *   Redistribution and use in source and binary forms, with or without
8809f0800SChristian Ehrhardt *   modification, are permitted provided that the following conditions
9809f0800SChristian Ehrhardt *   are met:
10809f0800SChristian Ehrhardt *
11809f0800SChristian Ehrhardt *     * Redistributions of source code must retain the above copyright
12809f0800SChristian Ehrhardt *       notice, this list of conditions and the following disclaimer.
13809f0800SChristian Ehrhardt *     * Redistributions in binary form must reproduce the above copyright
14809f0800SChristian Ehrhardt *       notice, this list of conditions and the following disclaimer in
15809f0800SChristian Ehrhardt *       the documentation and/or other materials provided with the
16809f0800SChristian Ehrhardt *       distribution.
17809f0800SChristian Ehrhardt *     * Neither the name of Intel Corporation nor the names of its
18809f0800SChristian Ehrhardt *       contributors may be used to endorse or promote products derived
19809f0800SChristian Ehrhardt *       from this software without specific prior written permission.
20809f0800SChristian Ehrhardt *
21809f0800SChristian Ehrhardt *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22809f0800SChristian Ehrhardt *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23809f0800SChristian Ehrhardt *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24809f0800SChristian Ehrhardt *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25809f0800SChristian Ehrhardt *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26809f0800SChristian Ehrhardt *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27809f0800SChristian Ehrhardt *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28809f0800SChristian Ehrhardt *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29809f0800SChristian Ehrhardt *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30809f0800SChristian Ehrhardt *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31809f0800SChristian Ehrhardt *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32809f0800SChristian Ehrhardt */
33809f0800SChristian Ehrhardt
34809f0800SChristian Ehrhardt#include <stdio.h>
35809f0800SChristian Ehrhardt#include <stdint.h>
36809f0800SChristian Ehrhardt#include <stdlib.h>
373d9b7210SChristian Ehrhardt#include <math.h>
38809f0800SChristian Ehrhardt
39809f0800SChristian Ehrhardt#include <rte_cycles.h>
40809f0800SChristian Ehrhardt#include <rte_random.h>
41809f0800SChristian Ehrhardt#include <rte_branch_prediction.h>
423d9b7210SChristian Ehrhardt#include <rte_ip.h>
43809f0800SChristian Ehrhardt#include <rte_lpm.h>
44809f0800SChristian Ehrhardt
45809f0800SChristian Ehrhardt#include "test.h"
46809f0800SChristian Ehrhardt#include "test_xmmt_ops.h"
47809f0800SChristian Ehrhardt
48809f0800SChristian Ehrhardt#define TEST_LPM_ASSERT(cond) do {                                            \
49809f0800SChristian Ehrhardt	if (!(cond)) {                                                        \
50809f0800SChristian Ehrhardt		printf("Error at line %d: \n", __LINE__);                     \
51809f0800SChristian Ehrhardt		return -1;                                                    \
52809f0800SChristian Ehrhardt	}                                                                     \
53809f0800SChristian Ehrhardt} while(0)
54809f0800SChristian Ehrhardt
55809f0800SChristian Ehrhardt#define ITERATIONS (1 << 10)
56809f0800SChristian Ehrhardt#define BATCH_SIZE (1 << 12)
57809f0800SChristian Ehrhardt#define BULK_SIZE 32
58809f0800SChristian Ehrhardt
593d9b7210SChristian Ehrhardt#define MAX_RULE_NUM (1200000)
603d9b7210SChristian Ehrhardt
613d9b7210SChristian Ehrhardtstruct route_rule {
623d9b7210SChristian Ehrhardt	uint32_t ip;
633d9b7210SChristian Ehrhardt	uint8_t depth;
643d9b7210SChristian Ehrhardt};
653d9b7210SChristian Ehrhardt
663d9b7210SChristian Ehrhardtstruct route_rule large_route_table[MAX_RULE_NUM];
673d9b7210SChristian Ehrhardt
683d9b7210SChristian Ehrhardtstatic uint32_t num_route_entries;
693d9b7210SChristian Ehrhardt#define NUM_ROUTE_ENTRIES num_route_entries
703d9b7210SChristian Ehrhardt
713d9b7210SChristian Ehrhardtenum {
723d9b7210SChristian Ehrhardt	IP_CLASS_A,
733d9b7210SChristian Ehrhardt	IP_CLASS_B,
743d9b7210SChristian Ehrhardt	IP_CLASS_C
753d9b7210SChristian Ehrhardt};
763d9b7210SChristian Ehrhardt
773d9b7210SChristian Ehrhardt/* struct route_rule_count defines the total number of rules in following a/b/c
783d9b7210SChristian Ehrhardt * each item in a[]/b[]/c[] is the number of common IP address class A/B/C, not
793d9b7210SChristian Ehrhardt * including the ones for private local network.
803d9b7210SChristian Ehrhardt */
813d9b7210SChristian Ehrhardtstruct route_rule_count {
823d9b7210SChristian Ehrhardt	uint32_t a[RTE_LPM_MAX_DEPTH];
833d9b7210SChristian Ehrhardt	uint32_t b[RTE_LPM_MAX_DEPTH];
843d9b7210SChristian Ehrhardt	uint32_t c[RTE_LPM_MAX_DEPTH];
853d9b7210SChristian Ehrhardt};
863d9b7210SChristian Ehrhardt
873d9b7210SChristian Ehrhardt/* All following numbers of each depth of each common IP class are just
883d9b7210SChristian Ehrhardt * got from previous large constant table in app/test/test_lpm_routes.h .
893d9b7210SChristian Ehrhardt * In order to match similar performance, they keep same depth and IP
903d9b7210SChristian Ehrhardt * address coverage as previous constant table. These numbers don't
913d9b7210SChristian Ehrhardt * include any private local IP address. As previous large const rule
923d9b7210SChristian Ehrhardt * table was just dumped from a real router, there are no any IP address
933d9b7210SChristian Ehrhardt * in class C or D.
943d9b7210SChristian Ehrhardt */
953d9b7210SChristian Ehrhardtstatic struct route_rule_count rule_count = {
963d9b7210SChristian Ehrhardt	.a = { /* IP class A in which the most significant bit is 0 */
973d9b7210SChristian Ehrhardt		    0, /* depth =  1 */
983d9b7210SChristian Ehrhardt		    0, /* depth =  2 */
993d9b7210SChristian Ehrhardt		    1, /* depth =  3 */
1003d9b7210SChristian Ehrhardt		    0, /* depth =  4 */
1013d9b7210SChristian Ehrhardt		    2, /* depth =  5 */
1023d9b7210SChristian Ehrhardt		    1, /* depth =  6 */
1033d9b7210SChristian Ehrhardt		    3, /* depth =  7 */
1043d9b7210SChristian Ehrhardt		  185, /* depth =  8 */
1053d9b7210SChristian Ehrhardt		   26, /* depth =  9 */
1063d9b7210SChristian Ehrhardt		   16, /* depth = 10 */
1073d9b7210SChristian Ehrhardt		   39, /* depth = 11 */
1083d9b7210SChristian Ehrhardt		  144, /* depth = 12 */
1093d9b7210SChristian Ehrhardt		  233, /* depth = 13 */
1103d9b7210SChristian Ehrhardt		  528, /* depth = 14 */
1113d9b7210SChristian Ehrhardt		  866, /* depth = 15 */
1123d9b7210SChristian Ehrhardt		 3856, /* depth = 16 */
1133d9b7210SChristian Ehrhardt		 3268, /* depth = 17 */
1143d9b7210SChristian Ehrhardt		 5662, /* depth = 18 */
1153d9b7210SChristian Ehrhardt		17301, /* depth = 19 */
1163d9b7210SChristian Ehrhardt		22226, /* depth = 20 */
1173d9b7210SChristian Ehrhardt		11147, /* depth = 21 */
1183d9b7210SChristian Ehrhardt		16746, /* depth = 22 */
1193d9b7210SChristian Ehrhardt		17120, /* depth = 23 */
1203d9b7210SChristian Ehrhardt		77578, /* depth = 24 */
1213d9b7210SChristian Ehrhardt		  401, /* depth = 25 */
1223d9b7210SChristian Ehrhardt		  656, /* depth = 26 */
1233d9b7210SChristian Ehrhardt		 1107, /* depth = 27 */
1243d9b7210SChristian Ehrhardt		 1121, /* depth = 28 */
1253d9b7210SChristian Ehrhardt		 2316, /* depth = 29 */
1263d9b7210SChristian Ehrhardt		  717, /* depth = 30 */
1273d9b7210SChristian Ehrhardt		   10, /* depth = 31 */
1283d9b7210SChristian Ehrhardt		   66  /* depth = 32 */
1293d9b7210SChristian Ehrhardt	},
1303d9b7210SChristian Ehrhardt	.b = { /* IP class A in which the most 2 significant bits are 10 */
1313d9b7210SChristian Ehrhardt		    0, /* depth =  1 */
1323d9b7210SChristian Ehrhardt		    0, /* depth =  2 */
1333d9b7210SChristian Ehrhardt		    0, /* depth =  3 */
1343d9b7210SChristian Ehrhardt		    0, /* depth =  4 */
1353d9b7210SChristian Ehrhardt		    1, /* depth =  5 */
1363d9b7210SChristian Ehrhardt		    1, /* depth =  6 */
1373d9b7210SChristian Ehrhardt		    1, /* depth =  7 */
1383d9b7210SChristian Ehrhardt		    3, /* depth =  8 */
1393d9b7210SChristian Ehrhardt		    3, /* depth =  9 */
1403d9b7210SChristian Ehrhardt		   30, /* depth = 10 */
1413d9b7210SChristian Ehrhardt		   25, /* depth = 11 */
1423d9b7210SChristian Ehrhardt		  168, /* depth = 12 */
1433d9b7210SChristian Ehrhardt		  305, /* depth = 13 */
1443d9b7210SChristian Ehrhardt		  569, /* depth = 14 */
1453d9b7210SChristian Ehrhardt		 1129, /* depth = 15 */
1463d9b7210SChristian Ehrhardt		50800, /* depth = 16 */
1473d9b7210SChristian Ehrhardt		 1645, /* depth = 17 */
1483d9b7210SChristian Ehrhardt		 1820, /* depth = 18 */
1493d9b7210SChristian Ehrhardt		 3506, /* depth = 19 */
1503d9b7210SChristian Ehrhardt		 3258, /* depth = 20 */
1513d9b7210SChristian Ehrhardt		 3424, /* depth = 21 */
1523d9b7210SChristian Ehrhardt		 4971, /* depth = 22 */
1533d9b7210SChristian Ehrhardt		 6885, /* depth = 23 */
1543d9b7210SChristian Ehrhardt		39771, /* depth = 24 */
1553d9b7210SChristian Ehrhardt		  424, /* depth = 25 */
1563d9b7210SChristian Ehrhardt		  170, /* depth = 26 */
1573d9b7210SChristian Ehrhardt		  433, /* depth = 27 */
1583d9b7210SChristian Ehrhardt		   92, /* depth = 28 */
1593d9b7210SChristian Ehrhardt		  366, /* depth = 29 */
1603d9b7210SChristian Ehrhardt		  377, /* depth = 30 */
1613d9b7210SChristian Ehrhardt		    2, /* depth = 31 */
1623d9b7210SChristian Ehrhardt		  200  /* depth = 32 */
1633d9b7210SChristian Ehrhardt	},
1643d9b7210SChristian Ehrhardt	.c = { /* IP class A in which the most 3 significant bits are 110 */
1653d9b7210SChristian Ehrhardt		     0, /* depth =  1 */
1663d9b7210SChristian Ehrhardt		     0, /* depth =  2 */
1673d9b7210SChristian Ehrhardt		     0, /* depth =  3 */
1683d9b7210SChristian Ehrhardt		     0, /* depth =  4 */
1693d9b7210SChristian Ehrhardt		     0, /* depth =  5 */
1703d9b7210SChristian Ehrhardt		     0, /* depth =  6 */
1713d9b7210SChristian Ehrhardt		     0, /* depth =  7 */
1723d9b7210SChristian Ehrhardt		    12, /* depth =  8 */
1733d9b7210SChristian Ehrhardt		     8, /* depth =  9 */
1743d9b7210SChristian Ehrhardt		     9, /* depth = 10 */
1753d9b7210SChristian Ehrhardt		    33, /* depth = 11 */
1763d9b7210SChristian Ehrhardt		    69, /* depth = 12 */
1773d9b7210SChristian Ehrhardt		   237, /* depth = 13 */
1783d9b7210SChristian Ehrhardt		  1007, /* depth = 14 */
1793d9b7210SChristian Ehrhardt		  1717, /* depth = 15 */
1803d9b7210SChristian Ehrhardt		 14663, /* depth = 16 */
1813d9b7210SChristian Ehrhardt		  8070, /* depth = 17 */
1823d9b7210SChristian Ehrhardt		 16185, /* depth = 18 */
1833d9b7210SChristian Ehrhardt		 48261, /* depth = 19 */
1843d9b7210SChristian Ehrhardt		 36870, /* depth = 20 */
1853d9b7210SChristian Ehrhardt		 33960, /* depth = 21 */
1863d9b7210SChristian Ehrhardt		 50638, /* depth = 22 */
1873d9b7210SChristian Ehrhardt		 61422, /* depth = 23 */
1883d9b7210SChristian Ehrhardt		466549, /* depth = 24 */
1893d9b7210SChristian Ehrhardt		  1829, /* depth = 25 */
1903d9b7210SChristian Ehrhardt		  4824, /* depth = 26 */
1913d9b7210SChristian Ehrhardt		  4927, /* depth = 27 */
1923d9b7210SChristian Ehrhardt		  5914, /* depth = 28 */
1933d9b7210SChristian Ehrhardt		 10254, /* depth = 29 */
1943d9b7210SChristian Ehrhardt		  4905, /* depth = 30 */
1953d9b7210SChristian Ehrhardt		     1, /* depth = 31 */
1963d9b7210SChristian Ehrhardt		   716  /* depth = 32 */
1973d9b7210SChristian Ehrhardt	}
1983d9b7210SChristian Ehrhardt};
1993d9b7210SChristian Ehrhardt
2003d9b7210SChristian Ehrhardtstatic void generate_random_rule_prefix(uint32_t ip_class, uint8_t depth)
2013d9b7210SChristian Ehrhardt{
2023d9b7210SChristian Ehrhardt/* IP address class A, the most significant bit is 0 */
2033d9b7210SChristian Ehrhardt#define IP_HEAD_MASK_A			0x00000000
2043d9b7210SChristian Ehrhardt#define IP_HEAD_BIT_NUM_A		1
2053d9b7210SChristian Ehrhardt
2063d9b7210SChristian Ehrhardt/* IP address class B, the most significant 2 bits are 10 */
2073d9b7210SChristian Ehrhardt#define IP_HEAD_MASK_B			0x80000000
2083d9b7210SChristian Ehrhardt#define IP_HEAD_BIT_NUM_B		2
2093d9b7210SChristian Ehrhardt
2103d9b7210SChristian Ehrhardt/* IP address class C, the most significant 3 bits are 110 */
2113d9b7210SChristian Ehrhardt#define IP_HEAD_MASK_C			0xC0000000
2123d9b7210SChristian Ehrhardt#define IP_HEAD_BIT_NUM_C		3
2133d9b7210SChristian Ehrhardt
2143d9b7210SChristian Ehrhardt	uint32_t class_depth;
2153d9b7210SChristian Ehrhardt	uint32_t range;
2163d9b7210SChristian Ehrhardt	uint32_t mask;
2173d9b7210SChristian Ehrhardt	uint32_t step;
2183d9b7210SChristian Ehrhardt	uint32_t start;
2193d9b7210SChristian Ehrhardt	uint32_t fixed_bit_num;
2203d9b7210SChristian Ehrhardt	uint32_t ip_head_mask;
2213d9b7210SChristian Ehrhardt	uint32_t rule_num;
2223d9b7210SChristian Ehrhardt	uint32_t k;
2233d9b7210SChristian Ehrhardt	struct route_rule *ptr_rule;
2243d9b7210SChristian Ehrhardt
2253d9b7210SChristian Ehrhardt	if (ip_class == IP_CLASS_A) {        /* IP Address class A */
2263d9b7210SChristian Ehrhardt		fixed_bit_num = IP_HEAD_BIT_NUM_A;
2273d9b7210SChristian Ehrhardt		ip_head_mask = IP_HEAD_MASK_A;
2283d9b7210SChristian Ehrhardt		rule_num = rule_count.a[depth - 1];
2293d9b7210SChristian Ehrhardt	} else if (ip_class == IP_CLASS_B) { /* IP Address class B */
2303d9b7210SChristian Ehrhardt		fixed_bit_num = IP_HEAD_BIT_NUM_B;
2313d9b7210SChristian Ehrhardt		ip_head_mask = IP_HEAD_MASK_B;
2323d9b7210SChristian Ehrhardt		rule_num = rule_count.b[depth - 1];
2333d9b7210SChristian Ehrhardt	} else {                             /* IP Address class C */
2343d9b7210SChristian Ehrhardt		fixed_bit_num = IP_HEAD_BIT_NUM_C;
2353d9b7210SChristian Ehrhardt		ip_head_mask = IP_HEAD_MASK_C;
2363d9b7210SChristian Ehrhardt		rule_num = rule_count.c[depth - 1];
2373d9b7210SChristian Ehrhardt	}
2383d9b7210SChristian Ehrhardt
2393d9b7210SChristian Ehrhardt	if (rule_num == 0)
2403d9b7210SChristian Ehrhardt		return;
2413d9b7210SChristian Ehrhardt
2423d9b7210SChristian Ehrhardt	/* the number of rest bits which don't include the most significant
2433d9b7210SChristian Ehrhardt	 * fixed bits for this IP address class
2443d9b7210SChristian Ehrhardt	 */
2453d9b7210SChristian Ehrhardt	class_depth = depth - fixed_bit_num;
2463d9b7210SChristian Ehrhardt
2473d9b7210SChristian Ehrhardt	/* range is the maximum number of rules for this depth and
2483d9b7210SChristian Ehrhardt	 * this IP address class
2493d9b7210SChristian Ehrhardt	 */
2503d9b7210SChristian Ehrhardt	range = 1 << class_depth;
2513d9b7210SChristian Ehrhardt
2523d9b7210SChristian Ehrhardt	/* only mask the most depth significant generated bits
2533d9b7210SChristian Ehrhardt	 * except fixed bits for IP address class
2543d9b7210SChristian Ehrhardt	 */
2553d9b7210SChristian Ehrhardt	mask = range - 1;
2563d9b7210SChristian Ehrhardt
2573d9b7210SChristian Ehrhardt	/* Widen coverage of IP address in generated rules */
2583d9b7210SChristian Ehrhardt	if (range <= rule_num)
2593d9b7210SChristian Ehrhardt		step = 1;
2603d9b7210SChristian Ehrhardt	else
2613d9b7210SChristian Ehrhardt		step = round((double)range / rule_num);
2623d9b7210SChristian Ehrhardt
2633d9b7210SChristian Ehrhardt	/* Only generate rest bits except the most significant
2643d9b7210SChristian Ehrhardt	 * fixed bits for IP address class
2653d9b7210SChristian Ehrhardt	 */
2663d9b7210SChristian Ehrhardt	start = lrand48() & mask;
2673d9b7210SChristian Ehrhardt	ptr_rule = &large_route_table[num_route_entries];
2683d9b7210SChristian Ehrhardt	for (k = 0; k < rule_num; k++) {
2693d9b7210SChristian Ehrhardt		ptr_rule->ip = (start << (RTE_LPM_MAX_DEPTH - depth))
2703d9b7210SChristian Ehrhardt			| ip_head_mask;
2713d9b7210SChristian Ehrhardt		ptr_rule->depth = depth;
2723d9b7210SChristian Ehrhardt		ptr_rule++;
2733d9b7210SChristian Ehrhardt		start = (start + step) & mask;
2743d9b7210SChristian Ehrhardt	}
2753d9b7210SChristian Ehrhardt	num_route_entries += rule_num;
2763d9b7210SChristian Ehrhardt}
2773d9b7210SChristian Ehrhardt
2783d9b7210SChristian Ehrhardtstatic void insert_rule_in_random_pos(uint32_t ip, uint8_t depth)
2793d9b7210SChristian Ehrhardt{
2803d9b7210SChristian Ehrhardt	uint32_t pos;
2813d9b7210SChristian Ehrhardt	int try_count = 0;
2823d9b7210SChristian Ehrhardt	struct route_rule tmp;
2833d9b7210SChristian Ehrhardt
2843d9b7210SChristian Ehrhardt	do {
2853d9b7210SChristian Ehrhardt		pos = lrand48();
2863d9b7210SChristian Ehrhardt		try_count++;
2873d9b7210SChristian Ehrhardt	} while ((try_count < 10) && (pos > num_route_entries));
2883d9b7210SChristian Ehrhardt
2893d9b7210SChristian Ehrhardt	if ((pos > num_route_entries) || (pos >= MAX_RULE_NUM))
2903d9b7210SChristian Ehrhardt		pos = num_route_entries >> 1;
2913d9b7210SChristian Ehrhardt
2923d9b7210SChristian Ehrhardt	tmp = large_route_table[pos];
2933d9b7210SChristian Ehrhardt	large_route_table[pos].ip = ip;
2943d9b7210SChristian Ehrhardt	large_route_table[pos].depth = depth;
2953d9b7210SChristian Ehrhardt	if (num_route_entries < MAX_RULE_NUM)
2963d9b7210SChristian Ehrhardt		large_route_table[num_route_entries++] = tmp;
2973d9b7210SChristian Ehrhardt}
2983d9b7210SChristian Ehrhardt
2993d9b7210SChristian Ehrhardtstatic void generate_large_route_rule_table(void)
3003d9b7210SChristian Ehrhardt{
3013d9b7210SChristian Ehrhardt	uint32_t ip_class;
3023d9b7210SChristian Ehrhardt	uint8_t  depth;
3033d9b7210SChristian Ehrhardt
3043d9b7210SChristian Ehrhardt	num_route_entries = 0;
3053d9b7210SChristian Ehrhardt	memset(large_route_table, 0, sizeof(large_route_table));
3063d9b7210SChristian Ehrhardt
3073d9b7210SChristian Ehrhardt	for (ip_class = IP_CLASS_A; ip_class <= IP_CLASS_C; ip_class++) {
3083d9b7210SChristian Ehrhardt		for (depth = 1; depth <= RTE_LPM_MAX_DEPTH; depth++) {
3093d9b7210SChristian Ehrhardt			generate_random_rule_prefix(ip_class, depth);
3103d9b7210SChristian Ehrhardt		}
3113d9b7210SChristian Ehrhardt	}
3123d9b7210SChristian Ehrhardt
3133d9b7210SChristian Ehrhardt	/* Add following rules to keep same as previous large constant table,
3143d9b7210SChristian Ehrhardt	 * they are 4 rules with private local IP address and 1 all-zeros prefix
3153d9b7210SChristian Ehrhardt	 * with depth = 8.
3163d9b7210SChristian Ehrhardt	 */
3173d9b7210SChristian Ehrhardt	insert_rule_in_random_pos(IPv4(0, 0, 0, 0), 8);
3183d9b7210SChristian Ehrhardt	insert_rule_in_random_pos(IPv4(10, 2, 23, 147), 32);
3193d9b7210SChristian Ehrhardt	insert_rule_in_random_pos(IPv4(192, 168, 100, 10), 24);
3203d9b7210SChristian Ehrhardt	insert_rule_in_random_pos(IPv4(192, 168, 25, 100), 24);
3213d9b7210SChristian Ehrhardt	insert_rule_in_random_pos(IPv4(192, 168, 129, 124), 32);
3223d9b7210SChristian Ehrhardt}
3233d9b7210SChristian Ehrhardt
324809f0800SChristian Ehrhardtstatic void
325809f0800SChristian Ehrhardtprint_route_distribution(const struct route_rule *table, uint32_t n)
326809f0800SChristian Ehrhardt{
327809f0800SChristian Ehrhardt	unsigned i, j;
328809f0800SChristian Ehrhardt
329809f0800SChristian Ehrhardt	printf("Route distribution per prefix width: \n");
330809f0800SChristian Ehrhardt	printf("DEPTH    QUANTITY (PERCENT)\n");
331809f0800SChristian Ehrhardt	printf("--------------------------- \n");
332809f0800SChristian Ehrhardt
333809f0800SChristian Ehrhardt	/* Count depths. */
334809f0800SChristian Ehrhardt	for (i = 1; i <= 32; i++) {
335809f0800SChristian Ehrhardt		unsigned depth_counter = 0;
336809f0800SChristian Ehrhardt		double percent_hits;
337809f0800SChristian Ehrhardt
338809f0800SChristian Ehrhardt		for (j = 0; j < n; j++)
339809f0800SChristian Ehrhardt			if (table[j].depth == (uint8_t) i)
340809f0800SChristian Ehrhardt				depth_counter++;
341809f0800SChristian Ehrhardt
342809f0800SChristian Ehrhardt		percent_hits = ((double)depth_counter)/((double)n) * 100;
343809f0800SChristian Ehrhardt		printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits);
344809f0800SChristian Ehrhardt	}
345809f0800SChristian Ehrhardt	printf("\n");
346809f0800SChristian Ehrhardt}
347809f0800SChristian Ehrhardt
348809f0800SChristian Ehrhardtstatic int
349809f0800SChristian Ehrhardttest_lpm_perf(void)
350809f0800SChristian Ehrhardt{
351809f0800SChristian Ehrhardt	struct rte_lpm *lpm = NULL;
352809f0800SChristian Ehrhardt	struct rte_lpm_config config;
353809f0800SChristian Ehrhardt
3543d9b7210SChristian Ehrhardt	config.max_rules = 2000000;
3553d9b7210SChristian Ehrhardt	config.number_tbl8s = 2048;
356809f0800SChristian Ehrhardt	config.flags = 0;
357809f0800SChristian Ehrhardt	uint64_t begin, total_time, lpm_used_entries = 0;
358809f0800SChristian Ehrhardt	unsigned i, j;
359809f0800SChristian Ehrhardt	uint32_t next_hop_add = 0xAA, next_hop_return = 0;
360809f0800SChristian Ehrhardt	int status = 0;
361809f0800SChristian Ehrhardt	uint64_t cache_line_counter = 0;
362809f0800SChristian Ehrhardt	int64_t count = 0;
363809f0800SChristian Ehrhardt
364809f0800SChristian Ehrhardt	rte_srand(rte_rdtsc());
365809f0800SChristian Ehrhardt
3663d9b7210SChristian Ehrhardt	generate_large_route_rule_table();
3673d9b7210SChristian Ehrhardt
368809f0800SChristian Ehrhardt	printf("No. routes = %u\n", (unsigned) NUM_ROUTE_ENTRIES);
369809f0800SChristian Ehrhardt
370809f0800SChristian Ehrhardt	print_route_distribution(large_route_table, (uint32_t) NUM_ROUTE_ENTRIES);
371809f0800SChristian Ehrhardt
372809f0800SChristian Ehrhardt	lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
373809f0800SChristian Ehrhardt	TEST_LPM_ASSERT(lpm != NULL);
374809f0800SChristian Ehrhardt
375809f0800SChristian Ehrhardt	/* Measue add. */
376809f0800SChristian Ehrhardt	begin = rte_rdtsc();
377809f0800SChristian Ehrhardt
378809f0800SChristian Ehrhardt	for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
379809f0800SChristian Ehrhardt		if (rte_lpm_add(lpm, large_route_table[i].ip,
380809f0800SChristian Ehrhardt				large_route_table[i].depth, next_hop_add) == 0)
381809f0800SChristian Ehrhardt			status++;
382809f0800SChristian Ehrhardt	}
383809f0800SChristian Ehrhardt	/* End Timer. */
384809f0800SChristian Ehrhardt	total_time = rte_rdtsc() - begin;
385809f0800SChristian Ehrhardt
386809f0800SChristian Ehrhardt	printf("Unique added entries = %d\n", status);
387809f0800SChristian Ehrhardt	/* Obtain add statistics. */
388809f0800SChristian Ehrhardt	for (i = 0; i < RTE_LPM_TBL24_NUM_ENTRIES; i++) {
389809f0800SChristian Ehrhardt		if (lpm->tbl24[i].valid)
390809f0800SChristian Ehrhardt			lpm_used_entries++;
391809f0800SChristian Ehrhardt
392809f0800SChristian Ehrhardt		if (i % 32 == 0) {
393809f0800SChristian Ehrhardt			if ((uint64_t)count < lpm_used_entries) {
394809f0800SChristian Ehrhardt				cache_line_counter++;
395809f0800SChristian Ehrhardt				count = lpm_used_entries;
396809f0800SChristian Ehrhardt			}
397809f0800SChristian Ehrhardt		}
398809f0800SChristian Ehrhardt	}
399809f0800SChristian Ehrhardt
400809f0800SChristian Ehrhardt	printf("Used table 24 entries = %u (%g%%)\n",
401809f0800SChristian Ehrhardt			(unsigned) lpm_used_entries,
402809f0800SChristian Ehrhardt			(lpm_used_entries * 100.0) / RTE_LPM_TBL24_NUM_ENTRIES);
403809f0800SChristian Ehrhardt	printf("64 byte Cache entries used = %u (%u bytes)\n",
404809f0800SChristian Ehrhardt			(unsigned) cache_line_counter, (unsigned) cache_line_counter * 64);
405809f0800SChristian Ehrhardt
406809f0800SChristian Ehrhardt	printf("Average LPM Add: %g cycles\n",
407809f0800SChristian Ehrhardt			(double)total_time / NUM_ROUTE_ENTRIES);
408809f0800SChristian Ehrhardt
409809f0800SChristian Ehrhardt	/* Measure single Lookup */
410809f0800SChristian Ehrhardt	total_time = 0;
411809f0800SChristian Ehrhardt	count = 0;
412809f0800SChristian Ehrhardt
413809f0800SChristian Ehrhardt	for (i = 0; i < ITERATIONS; i++) {
414809f0800SChristian Ehrhardt		static uint32_t ip_batch[BATCH_SIZE];
415809f0800SChristian Ehrhardt
416809f0800SChristian Ehrhardt		for (j = 0; j < BATCH_SIZE; j++)
417809f0800SChristian Ehrhardt			ip_batch[j] = rte_rand();
418809f0800SChristian Ehrhardt
419809f0800SChristian Ehrhardt		/* Lookup per batch */
420809f0800SChristian Ehrhardt		begin = rte_rdtsc();
421809f0800SChristian Ehrhardt
422809f0800SChristian Ehrhardt		for (j = 0; j < BATCH_SIZE; j++) {
423809f0800SChristian Ehrhardt			if (rte_lpm_lookup(lpm, ip_batch[j], &next_hop_return) != 0)
424809f0800SChristian Ehrhardt				count++;
425809f0800SChristian Ehrhardt		}
426809f0800SChristian Ehrhardt
427809f0800SChristian Ehrhardt		total_time += rte_rdtsc() - begin;
428809f0800SChristian Ehrhardt
429809f0800SChristian Ehrhardt	}
430809f0800SChristian Ehrhardt	printf("Average LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
431809f0800SChristian Ehrhardt			(double)total_time / ((double)ITERATIONS * BATCH_SIZE),
432809f0800SChristian Ehrhardt			(count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
433809f0800SChristian Ehrhardt
434809f0800SChristian Ehrhardt	/* Measure bulk Lookup */
435809f0800SChristian Ehrhardt	total_time = 0;
436809f0800SChristian Ehrhardt	count = 0;
437809f0800SChristian Ehrhardt	for (i = 0; i < ITERATIONS; i++) {
438809f0800SChristian Ehrhardt		static uint32_t ip_batch[BATCH_SIZE];
439809f0800SChristian Ehrhardt		uint32_t next_hops[BULK_SIZE];
440809f0800SChristian Ehrhardt
441809f0800SChristian Ehrhardt		/* Create array of random IP addresses */
442809f0800SChristian Ehrhardt		for (j = 0; j < BATCH_SIZE; j++)
443809f0800SChristian Ehrhardt			ip_batch[j] = rte_rand();
444809f0800SChristian Ehrhardt
445809f0800SChristian Ehrhardt		/* Lookup per batch */
446809f0800SChristian Ehrhardt		begin = rte_rdtsc();
447809f0800SChristian Ehrhardt		for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) {
448809f0800SChristian Ehrhardt			unsigned k;
449809f0800SChristian Ehrhardt			rte_lpm_lookup_bulk(lpm, &ip_batch[j], next_hops, BULK_SIZE);
450809f0800SChristian Ehrhardt			for (k = 0; k < BULK_SIZE; k++)
451809f0800SChristian Ehrhardt				if (unlikely(!(next_hops[k] & RTE_LPM_LOOKUP_SUCCESS)))
452809f0800SChristian Ehrhardt					count++;
453809f0800SChristian Ehrhardt		}
454809f0800SChristian Ehrhardt
455809f0800SChristian Ehrhardt		total_time += rte_rdtsc() - begin;
456809f0800SChristian Ehrhardt	}
457809f0800SChristian Ehrhardt	printf("BULK LPM Lookup: %.1f cycles (fails = %.1f%%)\n",
458809f0800SChristian Ehrhardt			(double)total_time / ((double)ITERATIONS * BATCH_SIZE),
459809f0800SChristian Ehrhardt			(count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
460809f0800SChristian Ehrhardt
461809f0800SChristian Ehrhardt	/* Measure LookupX4 */
462809f0800SChristian Ehrhardt	total_time = 0;
463809f0800SChristian Ehrhardt	count = 0;
464809f0800SChristian Ehrhardt	for (i = 0; i < ITERATIONS; i++) {
465809f0800SChristian Ehrhardt		static uint32_t ip_batch[BATCH_SIZE];
466809f0800SChristian Ehrhardt		uint32_t next_hops[4];
467809f0800SChristian Ehrhardt
468809f0800SChristian Ehrhardt		/* Create array of random IP addresses */
469809f0800SChristian Ehrhardt		for (j = 0; j < BATCH_SIZE; j++)
470809f0800SChristian Ehrhardt			ip_batch[j] = rte_rand();
471809f0800SChristian Ehrhardt
472809f0800SChristian Ehrhardt		/* Lookup per batch */
473809f0800SChristian Ehrhardt		begin = rte_rdtsc();
474809f0800SChristian Ehrhardt		for (j = 0; j < BATCH_SIZE; j += RTE_DIM(next_hops)) {
475809f0800SChristian Ehrhardt			unsigned k;
476809f0800SChristian Ehrhardt			xmm_t ipx4;
477809f0800SChristian Ehrhardt
478809f0800SChristian Ehrhardt			ipx4 = vect_loadu_sil128((xmm_t *)(ip_batch + j));
479809f0800SChristian Ehrhardt			ipx4 = *(xmm_t *)(ip_batch + j);
480809f0800SChristian Ehrhardt			rte_lpm_lookupx4(lpm, ipx4, next_hops, UINT32_MAX);
481809f0800SChristian Ehrhardt			for (k = 0; k < RTE_DIM(next_hops); k++)
482809f0800SChristian Ehrhardt				if (unlikely(next_hops[k] == UINT32_MAX))
483809f0800SChristian Ehrhardt					count++;
484809f0800SChristian Ehrhardt		}
485809f0800SChristian Ehrhardt
486809f0800SChristian Ehrhardt		total_time += rte_rdtsc() - begin;
487809f0800SChristian Ehrhardt	}
488809f0800SChristian Ehrhardt	printf("LPM LookupX4: %.1f cycles (fails = %.1f%%)\n",
489809f0800SChristian Ehrhardt			(double)total_time / ((double)ITERATIONS * BATCH_SIZE),
490809f0800SChristian Ehrhardt			(count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
491809f0800SChristian Ehrhardt
492809f0800SChristian Ehrhardt	/* Delete */
493809f0800SChristian Ehrhardt	status = 0;
494809f0800SChristian Ehrhardt	begin = rte_rdtsc();
495809f0800SChristian Ehrhardt
496809f0800SChristian Ehrhardt	for (i = 0; i < NUM_ROUTE_ENTRIES; i++) {
497809f0800SChristian Ehrhardt		/* rte_lpm_delete(lpm, ip, depth) */
498809f0800SChristian Ehrhardt		status += rte_lpm_delete(lpm, large_route_table[i].ip,
499809f0800SChristian Ehrhardt				large_route_table[i].depth);
500809f0800SChristian Ehrhardt	}
501809f0800SChristian Ehrhardt
502809f0800SChristian Ehrhardt	total_time += rte_rdtsc() - begin;
503809f0800SChristian Ehrhardt
504809f0800SChristian Ehrhardt	printf("Average LPM Delete: %g cycles\n",
505809f0800SChristian Ehrhardt			(double)total_time / NUM_ROUTE_ENTRIES);
506809f0800SChristian Ehrhardt
507809f0800SChristian Ehrhardt	rte_lpm_delete_all(lpm);
508809f0800SChristian Ehrhardt	rte_lpm_free(lpm);
509809f0800SChristian Ehrhardt
510809f0800SChristian Ehrhardt	return 0;
511809f0800SChristian Ehrhardt}
512809f0800SChristian Ehrhardt
5139ecc306dSRicardo SalvetiREGISTER_TEST_COMMAND(lpm_perf_autotest, test_lpm_perf);
514