From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <wei.dai@intel.com>
Received: from mga14.intel.com (mga14.intel.com [192.55.52.115])
by dpdk.org (Postfix) with ESMTP id ECF692BAD
for <dev@dpdk.org>; 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" <wei.dai@intel.com>
To: "Richardson, Bruce" <bruce.richardson@intel.com>
CC: "dev@dpdk.org" <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 <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=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 <wei.dai@intel.com>
> 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 <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];
>=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
> <snip>
> > +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