[PATCH] app/test: remove large lpm test head file

[Wei Dai <wei.dai@intel.com>]

remove the large file app/test/test_lpm_routes.h and add codes to
auto-generate similar large route rule talbe which keeps same depth
and IP class distribution as previous one in test_lpm_routes.h .
With the rule table auto-generated at run time, the performance
of looking up keep similar to that from pervious constant talbe.

Signed-off-by: Wei Dai <wei.dai@intel.com>
---
 app/test/test_lpm.c        |       2 +-
 app/test/test_lpm_perf.c   |     268 +-
 app/test/test_lpm_routes.h | 1076861 -----------------------------------------
 3 files changed, 266 insertions(+), 1076865 deletions(-)
 delete mode 100644 app/test/test_lpm_routes.h

diff --git a/app/test/test_lpm.c b/app/test/test_lpm.c
index b6ad2eb..0952f52 100644
--- a/app/test/test_lpm.c
+++ b/app/test/test_lpm.c
@@ -35,10 +35,10 @@
 #include <stdint.h>
 #include <stdlib.h>
 
+#include <rte_ip.h>
 #include <rte_lpm.h>
 
 #include "test.h"
-#include "test_lpm_routes.h"
 #include "test_xmmt_ops.h"
 
 #define TEST_LPM_ASSERT(cond) do {                                            \
diff --git a/app/test/test_lpm_perf.c b/app/test/test_lpm_perf.c
index 58eb415..5582ef4 100644
--- a/app/test/test_lpm_perf.c
+++ b/app/test/test_lpm_perf.c
@@ -34,14 +34,15 @@
 #include <stdio.h>
 #include <stdint.h>
 #include <stdlib.h>
+#include <math.h>
 
 #include <rte_cycles.h>
 #include <rte_random.h>
 #include <rte_branch_prediction.h>
 #include <rte_lpm.h>
+#include <rte_ip.h>
 
 #include "test.h"
-#include "test_lpm_routes.h"
 #include "test_xmmt_ops.h"
 
 #define TEST_LPM_ASSERT(cond) do {                                            \
@@ -55,6 +56,265 @@
 #define BATCH_SIZE (1 << 12)
 #define BULK_SIZE 32
 
+#define MAX_RULE_NUM (1200000)
+
+struct route_rule {
+	uint32_t ip;
+	uint8_t depth;
+};
+
+struct route_rule large_route_table[MAX_RULE_NUM];
+
+static uint32_t num_route_entries;  /* NUM_ROUTE_ENTRIES */
+#define NUM_ROUTE_ENTRIES num_route_entries
+
+struct route_rule_count {
+	uint32_t total;
+	uint32_t a[RTE_LPM_MAX_DEPTH];
+	uint32_t b[RTE_LPM_MAX_DEPTH];
+	uint32_t c[RTE_LPM_MAX_DEPTH];
+	uint32_t left;
+	uint32_t abc[3*RTE_LPM_MAX_DEPTH];
+};
+
+static struct route_rule_count rule_count = {
+	.a = {
+		    0, /* depth =  1 */
+		    0, /* depth =  2 */
+		    1, /* depth =  3 */
+		    0, /* depth =  4 */
+		    2, /* depth =  5 */
+		    1, /* depth =  6 */
+		    3, /* depth =  7 */
+		  185, /* depth =  8 */
+		   26, /* depth =  9 */
+		   16, /* depth = 10 */
+		   39, /* depth = 11 */
+		  144, /* depth = 12 */
+		  233, /* depth = 13 */
+		  528, /* depth = 14 */
+		  866, /* depth = 15 */
+		 3856, /* depth = 16 */
+		 3268, /* depth = 17 */
+		 5662, /* depth = 18 */
+		17301, /* depth = 19 */
+		22226, /* depth = 20 */
+		11147, /* depth = 21 */
+		16746, /* depth = 22 */
+		17120, /* depth = 23 */
+		77578, /* depth = 24 */
+		  401, /* depth = 25 */
+		  656, /* depth = 26 */
+		 1107, /* depth = 27 */
+		 1121, /* depth = 28 */
+		 2316, /* depth = 29 */
+		  717, /* depth = 30 */
+		   10, /* depth = 31 */
+		   66  /* depth = 32 */
+	},
+	.b = {
+		    0, /* depth =  1 */
+		    0, /* depth =  2 */
+		    0, /* depth =  3 */
+		    0, /* depth =  4 */
+		    1, /* depth =  5 */
+		    1, /* depth =  6 */
+		    1, /* depth =  7 */
+		    3, /* depth =  8 */
+		    3, /* depth =  9 */
+		   30, /* depth = 10 */
+		   25, /* depth = 11 */
+		  168, /* depth = 12 */
+		  305, /* depth = 13 */
+		  569, /* depth = 14 */
+		 1129, /* depth = 15 */
+		50800, /* depth = 16 */
+		 1645, /* depth = 17 */
+		 1820, /* depth = 18 */
+		 3506, /* depth = 19 */
+		 3258, /* depth = 20 */
+		 3424, /* depth = 21 */
+		 4971, /* depth = 22 */
+		 6885, /* depth = 23 */
+		39771, /* depth = 24 */
+		  424, /* depth = 25 */
+		  170, /* depth = 26 */
+		  433, /* depth = 27 */
+		   92, /* depth = 28 */
+		  366, /* depth = 29 */
+		  377, /* depth = 30 */
+		    2, /* depth = 31 */
+		  200  /* depth = 32 */
+	},
+	.c = {
+		     0, /* depth =  1 */
+		     0, /* depth =  2 */
+		     0, /* depth =  3 */
+		     0, /* depth =  4 */
+		     0, /* depth =  5 */
+		     0, /* depth =  6 */
+		     0, /* depth =  7 */
+		    12, /* depth =  8 */
+		     8, /* depth =  9 */
+		     9, /* depth = 10 */
+		    33, /* depth = 11 */
+		    69, /* depth = 12 */
+		   237, /* depth = 13 */
+		  1007, /* depth = 14 */
+		  1717, /* depth = 15 */
+		 14663, /* depth = 16 */
+		  8070, /* depth = 17 */
+		 16185, /* depth = 18 */
+		 48261, /* depth = 19 */
+		 36870, /* depth = 20 */
+		 33960, /* depth = 21 */
+		 50638, /* depth = 22 */
+		 61422, /* depth = 23 */
+		466549, /* depth = 24 */
+		  1829, /* depth = 25 */
+		  4824, /* depth = 26 */
+		  4927, /* depth = 27 */
+		  5914, /* depth = 28 */
+		 10254, /* depth = 29 */
+		  4905, /* depth = 30 */
+		     1, /* depth = 31 */
+		   716  /* depth = 32 */
+	}
+};
+
+static void init_rule_count(void)
+{
+	uint32_t depth;
+	uint32_t count;
+
+	rule_count.left = 0;
+	count = 0;
+
+	for (depth = 1; depth <= RTE_LPM_MAX_DEPTH; depth++) {
+		count += rule_count.a[depth-1];
+		if (rule_count.a[depth-1])
+			rule_count.abc[rule_count.left++] = depth;
+	}
+
+	for (depth = 1; depth <= RTE_LPM_MAX_DEPTH; depth++) {
+		count += rule_count.b[depth-1];
+		if (rule_count.b[depth-1])
+			rule_count.abc[rule_count.left++] = 256 + depth;
+	}
+
+	for (depth = 1; depth <= RTE_LPM_MAX_DEPTH; depth++) {
+		count += rule_count.c[depth-1];
+		if (rule_count.c[depth-1])
+			rule_count.abc[rule_count.left++] = 512 + depth;
+	}
+	rule_count.total = count;
+}
+
+static void generate_random_rule_prefix(uint32_t ip_class, uint8_t depth)
+{
+#define IP_HEAD_MASK_A  0x00000000  /* 0xxx */
+#define IP_HEAD_MASK_B  0x80000000  /* 10xx */
+#define IP_HEAD_MASK_C  0xC0000000  /* 110x */
+#define IP_HEAD_BIT_NUM_A 1
+#define IP_HEAD_BIT_NUM_B 2
+#define IP_HEAD_BIT_NUM_C 3
+
+	uint32_t depth_1;
+	uint32_t class_depth;
+	uint32_t range;
+	uint32_t mask;
+	uint32_t step;
+	uint32_t start;
+	uint32_t fixed_bit_num;
+	uint32_t ip_head_mask;
+	uint32_t rule_num;
+	uint32_t k;
+	struct route_rule *ptr_rule;
+
+	depth_1 = depth - 1;
+
+	if (ip_class == 0) { /* IP Address class A */
+		fixed_bit_num = IP_HEAD_BIT_NUM_A;
+		ip_head_mask = IP_HEAD_MASK_A;
+		rule_num = rule_count.a[depth_1];
+	} else if (ip_class == 1) { /* IP Address class B */
+		fixed_bit_num = IP_HEAD_BIT_NUM_B;
+		ip_head_mask = IP_HEAD_MASK_B;
+		rule_num = rule_count.b[depth_1];
+	} else { /* IP Address class C */
+		fixed_bit_num = IP_HEAD_BIT_NUM_C;
+		ip_head_mask = IP_HEAD_MASK_C;
+		rule_num = rule_count.c[depth_1];
+	}
+
+	class_depth = depth - fixed_bit_num;
+	range = 1 << class_depth;
+	mask = range - 1;
+	if (range <= rule_num)
+		step = 1;
+	else
+		step = round((double)range / rule_num);
+
+	start = lrand48() & mask;
+	ptr_rule = &large_route_table[num_route_entries];
+	for (k = 0; k < rule_num; k++) {
+		ptr_rule->ip = (start << (RTE_LPM_MAX_DEPTH - depth))
+			| ip_head_mask;
+		ptr_rule->depth = depth;
+		ptr_rule++;
+		start = (start + step) & mask;
+	}
+	num_route_entries += rule_num;
+}
+
+static void insert_rule_in_random_pos(uint32_t ip, uint8_t depth)
+{
+	uint32_t pos;
+	int try_count = 0;
+	struct route_rule tmp;
+
+	do {
+		pos = lrand48();
+		try_count++;
+	} while ((try_count < 10) && (pos > num_route_entries));
+
+	if ((pos > num_route_entries) || (pos >= MAX_RULE_NUM))
+		pos = num_route_entries >> 1;
+
+	tmp = large_route_table[pos];
+	large_route_table[pos].ip = ip;
+	large_route_table[pos].depth = depth;
+	if (num_route_entries < MAX_RULE_NUM)
+		large_route_table[num_route_entries++] = tmp;
+}
+
+static void generate_large_route_rule_table(void)
+{
+	uint32_t idx;
+	uint32_t ip_class;
+	uint8_t  depth;
+
+	memset(large_route_table, 0, sizeof(large_route_table));
+	init_rule_count();
+
+	idx = 0;
+	do {
+		depth = (rule_count.abc[idx] & 0xFF);
+		ip_class = rule_count.abc[idx] >> 8;
+
+		generate_random_rule_prefix(ip_class, depth);
+
+		rule_count.left--;
+		idx++;
+	} while (rule_count.left > 0);
+
+	insert_rule_in_random_pos(IPv4(0, 0, 0, 0), 8);
+	insert_rule_in_random_pos(IPv4(10, 2, 23, 147), 32);
+	insert_rule_in_random_pos(IPv4(192, 168, 100, 10), 24);
+	insert_rule_in_random_pos(IPv4(192, 168, 25, 100), 24);
+	insert_rule_in_random_pos(IPv4(192, 168, 129, 124), 32);
+}
+
 static void
 print_route_distribution(const struct route_rule *table, uint32_t n)
 {
@@ -85,8 +345,8 @@ test_lpm_perf(void)
 	struct rte_lpm *lpm = NULL;
 	struct rte_lpm_config config;
 
-	config.max_rules = 1000000;
-	config.number_tbl8s = 256;
+	config.max_rules = 2000000;
+	config.number_tbl8s = 2048;
 	config.flags = 0;
 	uint64_t begin, total_time, lpm_used_entries = 0;
 	unsigned i, j;
@@ -97,6 +357,8 @@ test_lpm_perf(void)
 
 	rte_srand(rte_rdtsc());
 
+	generate_large_route_rule_table();
+
 	printf("No. routes = %u\n", (unsigned) NUM_ROUTE_ENTRIES);
 
 	print_route_distribution(large_route_table, (uint32_t) NUM_ROUTE_ENTRIES);
diff --git a/app/test/test_lpm_routes.h b/app/test/test_lpm_routes.h
deleted file mode 100644
index 023b0f9..0000000
-- 
2.7.4