From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id E8F2D2BA4 for ; Tue, 27 Sep 2016 19:40:23 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by orsmga102.jf.intel.com with ESMTP; 27 Sep 2016 10:39:56 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.30,405,1470726000"; d="scan'208";a="766499851" Received: from dpdk4.bj.intel.com ([172.16.182.166]) by FMSMGA003.fm.intel.com with ESMTP; 27 Sep 2016 10:39:55 -0700 From: Wei Dai To: dev@dpdk.org, bruce.richardson@intel.com, wei.dai@intel.com Date: Wed, 28 Sep 2016 01:38:27 +0800 Message-Id: <1474997907-24982-1-git-send-email-wei.dai@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1474882625-67916-1-git-send-email-wei.dai@intel.com> References: <1474882625-67916-1-git-send-email-wei.dai@intel.com> Subject: [dpdk-dev] [PATCH v2] app/test: remove large lpm test head file X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 27 Sep 2016 17:40:24 -0000 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 --- app/test/test_lpm.c | 2 +- app/test/test_lpm_perf.c | 273 +- app/test/test_lpm_routes.h | 1076861 ----------------------------------------- 3 files changed, 271 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 #include +#include #include #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..2912df9 100644 --- a/app/test/test_lpm_perf.c +++ b/app/test/test_lpm_perf.c @@ -34,14 +34,15 @@ #include #include #include +#include #include #include #include +#include #include #include "test.h" -#include "test_lpm_routes.h" #include "test_xmmt_ops.h" #define TEST_LPM_ASSERT(cond) do { \ @@ -55,6 +56,270 @@ #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; +#define NUM_ROUTE_ENTRIES num_route_entries + +enum { + IP_CLASS_A, + IP_CLASS_B, + IP_CLASS_C +}; + +/* struct route_rule_count defines the total number of rules in following a/b/c + * each item in a[]/b[]/c[] is the number of common IP address class A/B/C, not + * including the ones for private local network. + */ +struct route_rule_count { + uint32_t a[RTE_LPM_MAX_DEPTH]; + uint32_t b[RTE_LPM_MAX_DEPTH]; + uint32_t c[RTE_LPM_MAX_DEPTH]; +}; + +/* All following numbers of each depth of each common IP class are just + * got from previous large constant table in app/test/test_lpm_routes.h . + * In order to match simliar performance, they keep same depth and IP + * address coverage as previous constant table. These numbers don't + * include any private local IP address. As previous large const rule + * table was just dumped from a real router, there are no any IP address + * in class C or D. + */ +static struct route_rule_count rule_count = { + .a = { /* IP class A in which the most significant bit is 0 */ + 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 = { /* IP class A in which the most 2 significant bits are 10 */ + 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 = { /* IP class A in which the most 3 significant bits are 110 */ + 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 generate_random_rule_prefix(uint32_t ip_class, uint8_t depth) +{ +/* IP address class A, the most significant bit is 0 */ +#define IP_HEAD_MASK_A 0x00000000 +#define IP_HEAD_BIT_NUM_A 1 + +/* IP address class B, the most significant 2 bits are 10 */ +#define IP_HEAD_MASK_B 0x80000000 +#define IP_HEAD_BIT_NUM_B 2 + +/* IP address class C, the most significant 3 bits are 110 */ +#define IP_HEAD_MASK_C 0xC0000000 +#define IP_HEAD_BIT_NUM_C 3 + + 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; + + if (ip_class == IP_CLASS_A) { /* 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 == IP_CLASS_B) { /* 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]; + } + + if (rule_num == 0) + return; + + /* the number of rest bits which don't include the most significant + * fixed bits for this IP address class + */ + class_depth = depth - fixed_bit_num; + + /* range is the maximum number of rules for this depth and + * this IP address class + */ + range = 1 << class_depth; + + /* only mask the most depth significant generated bits + * except fixed bits for IP address class + */ + mask = range - 1; + + /* Widen coverage of IP address in generated rules */ + if (range <= rule_num) + step = 1; + else + step = round((double)range / rule_num); + + /* Only generate rest bits except the most significant + * fixed bits for IP address class + */ + 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 ip_class; + uint8_t depth; + + memset(large_route_table, 0, sizeof(large_route_table)); + + for (ip_class = IP_CLASS_A; ip_class <= IP_CLASS_C; ip_class++) { + for (depth = 1; depth <= RTE_LPM_MAX_DEPTH; depth++) { + generate_random_rule_prefix(ip_class, depth); + } + } + + /* Add following rules to keep same as previous large constant table, + * they are 4 rules with private local IP address and 1 all-zeros prefix + * with depth = 8. + */ + 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 +350,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 +362,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