From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 5592347CD for ; Mon, 26 Sep 2016 11:38:33 +0200 (CEST) Received: from orsmga005.jf.intel.com ([10.7.209.41]) by orsmga101.jf.intel.com with ESMTP; 26 Sep 2016 02:38:34 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.30,398,1470726000"; d="scan'208";a="13342721" Received: from dpdk4.bj.intel.com ([172.16.182.166]) by orsmga005.jf.intel.com with ESMTP; 26 Sep 2016 02:38:31 -0700 From: Wei Dai To: dev@dpdk.org, bruce.richardson@intel.com, wei.dai@intel.com Date: Mon, 26 Sep 2016 17:37:05 +0800 Message-Id: <1474882625-67916-1-git-send-email-wei.dai@intel.com> X-Mailer: git-send-email 2.7.4 Subject: [dpdk-dev] [PATCH] 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: Mon, 26 Sep 2016 09:38:33 -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 | 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 #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..5582ef4 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,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