From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id ECF692BAD for ; Mon, 26 Sep 2016 15:49:56 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga103.fm.intel.com with ESMTP; 26 Sep 2016 06:49:56 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.30,399,1470726000"; d="scan'208";a="766053732" Received: from kmsmsx154.gar.corp.intel.com ([172.21.73.14]) by FMSMGA003.fm.intel.com with ESMTP; 26 Sep 2016 06:49:55 -0700 Received: from pgsmsx109.gar.corp.intel.com (10.221.44.109) by KMSMSX154.gar.corp.intel.com (172.21.73.14) with Microsoft SMTP Server (TLS) id 14.3.248.2; Mon, 26 Sep 2016 21:49:53 +0800 Received: from pgsmsx106.gar.corp.intel.com ([169.254.9.133]) by PGSMSX109.gar.corp.intel.com ([169.254.14.146]) with mapi id 14.03.0248.002; Mon, 26 Sep 2016 21:49:52 +0800 From: "Dai, Wei" To: "Richardson, Bruce" CC: "dev@dpdk.org" Thread-Topic: [PATCH] app/test: remove large lpm test head file Thread-Index: AQHSF9nDJlFiwfZNwkKrWcmcxwDtK6CLBZ8AgAC7ryA= Date: Mon, 26 Sep 2016 13:49:52 +0000 Message-ID: <49759EB36A64CF4892C1AFEC9231E8D63A2D0830@PGSMSX106.gar.corp.intel.com> References: <1474882625-67916-1-git-send-email-wei.dai@intel.com> <20160926100658.GA15828@bricha3-MOBL3> In-Reply-To: <20160926100658.GA15828@bricha3-MOBL3> Accept-Language: zh-CN, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiN2NhMTU5YWItMGU0OS00MjFmLTgxNzAtNmIwMmM5NTg2ZGM5IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX0lDIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE1LjkuNi42IiwiVHJ1c3RlZExhYmVsSGFzaCI6IkZpMGErSVBTR1RtblpZUnBoeG05XC9ETjVjV2xMV25QVFBUdWVlT0RUcmlJPSJ9 x-ctpclassification: CTP_IC x-originating-ip: [172.30.20.205] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [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 13:49:57 -0000 Hi, Bruce How about your test result for this patch ? Especially on performance of rule looking-up ? There are also some replies for your comments as below. Thanks / Wei=20 > -----Original Message----- > From: Richardson, Bruce > Sent: Monday, September 26, 2016 6:07 PM > To: Dai, Wei > Cc: dev@dpdk.org > Subject: Re: [PATCH] app/test: remove large lpm test head file >=20 > On Mon, Sep 26, 2016 at 05:37:05PM +0800, Wei Dai wrote: > > 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]; >=20 > Can you provide some comments explaining how you are generating the rules > to test with. For example, explain why have you split the sets of rules i= nto three, > a, b, and c, and how you use each of those three sets. Perhaps also provi= de a > comment alongside each member of the structure above. a/b/c means IP address class. These class doesn't count IP address for loca= l network. Because the previous large route rule table was just dumped from a real rou= ter and as to match similar performance, I design to keep similar depth and IP addr= ess coverage=20 as previous constant table. All the numbers of each depth of each IP class = are just got from previous constant table.=20 >=20 > > > +static void init_rule_count(void) > > +{ > > + uint32_t depth; > > + uint32_t count; > > + > > + rule_count.left =3D 0; > > + count =3D 0; > > + > > + for (depth =3D 1; depth <=3D RTE_LPM_MAX_DEPTH; depth++) { > > + count +=3D rule_count.a[depth-1]; > > + if (rule_count.a[depth-1]) > > + rule_count.abc[rule_count.left++] =3D depth; > > + } > > + > > + for (depth =3D 1; depth <=3D RTE_LPM_MAX_DEPTH; depth++) { > > + count +=3D rule_count.b[depth-1]; > > + if (rule_count.b[depth-1]) > > + rule_count.abc[rule_count.left++] =3D 256 + depth; > > + } > > + > > + for (depth =3D 1; depth <=3D RTE_LPM_MAX_DEPTH; depth++) { > > + count +=3D rule_count.c[depth-1]; > > + if (rule_count.c[depth-1]) > > + rule_count.abc[rule_count.left++] =3D 512 + depth; > > + } > > + rule_count.total =3D count; > > +} >=20 > Again, this needs a comment explaining what this function is doing, and > how/why it is doing so. I will give more comments to explain it in v2 patch. By the way, rule_count.abc[ ] is for quicker generation of rules. >=20 > > + > > +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 =3D depth - 1; > > + > > + if (ip_class =3D=3D 0) { /* IP Address class A */ > > + fixed_bit_num =3D IP_HEAD_BIT_NUM_A; > > + ip_head_mask =3D IP_HEAD_MASK_A; > > + rule_num =3D rule_count.a[depth_1]; > > + } else if (ip_class =3D=3D 1) { /* IP Address class B */ > > + fixed_bit_num =3D IP_HEAD_BIT_NUM_B; > > + ip_head_mask =3D IP_HEAD_MASK_B; > > + rule_num =3D rule_count.b[depth_1]; > > + } else { /* IP Address class C */ > > + fixed_bit_num =3D IP_HEAD_BIT_NUM_C; > > + ip_head_mask =3D IP_HEAD_MASK_C; > > + rule_num =3D rule_count.c[depth_1]; > > + } > > + > > + class_depth =3D depth - fixed_bit_num; > > + range =3D 1 << class_depth; > > + mask =3D range - 1; > > + if (range <=3D rule_num) > > + step =3D 1; > > + else > > + step =3D round((double)range / rule_num); > > + > > + start =3D lrand48() & mask; > > + ptr_rule =3D &large_route_table[num_route_entries]; > > + for (k =3D 0; k < rule_num; k++) { > > + ptr_rule->ip =3D (start << (RTE_LPM_MAX_DEPTH - depth)) > > + | ip_head_mask; > > + ptr_rule->depth =3D depth; > > + ptr_rule++; > > + start =3D (start + step) & mask; > > + } > > + num_route_entries +=3D rule_num; > > +} >=20 > Again, comment explaining function, please. V2 patch will give more annotations. >=20 > > + > > +static void insert_rule_in_random_pos(uint32_t ip, uint8_t depth) { > > + uint32_t pos; > > + int try_count =3D 0; > > + struct route_rule tmp; > > + > > + do { > > + pos =3D lrand48(); > > + try_count++; > > + } while ((try_count < 10) && (pos > num_route_entries)); > > + > > + if ((pos > num_route_entries) || (pos >=3D MAX_RULE_NUM)) > > + pos =3D num_route_entries >> 1; > > + > > + tmp =3D large_route_table[pos]; > > + large_route_table[pos].ip =3D ip; > > + large_route_table[pos].depth =3D depth; > > + if (num_route_entries < MAX_RULE_NUM) > > + large_route_table[num_route_entries++] =3D 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 =3D 0; > > + do { > > + depth =3D (rule_count.abc[idx] & 0xFF); > > + ip_class =3D 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); >=20 > Why are you inserting 5 rules at random positions at the end? Explanatory > comment needed, thanks. This just keeps the same local IP address class and depth as previous const= ant table. Place these local IP address in random position in the rule set rather than= the end of it or adjacent 5 lines. >=20 >=20 > When running the code with the new auto-generated table, the rule add tim= e is > 5x longer than that with the original test. Have you investigated what ca= uses > this, and is there something that can be done to work around it? I have designed a debug platform to trace each loop and each branch passed = through during rule adding, In previous constant large rule table, there are many (about ~78%) reappear= ance of same prefix=20 (same IP prefix + same depth). But auto-generated rule table has much lower= reappearance.=20 This much affect compute quantity in rule adding. To work around it, I assume that we may update the algorithm to keep same r= eappearance rate in each depth and each IP address class.=20 It will be much more complicated one and need much more efforts to tune it. As the performance of looking-up from current auto-generated rule sets is s= imilar as previous one,=20 I have not gone on to pursuit much better performance of rule adding/deleti= ng. >=20 > Regards, > /Bruce