DPDK patches and discussions
 help / color / mirror / Atom feed
From: Bruce Richardson <bruce.richardson@intel.com>
To: Wei Dai <wei.dai@intel.com>
Cc: dev@dpdk.org
Subject: Re: [dpdk-dev] [PATCH] app/test: remove large lpm test head file
Date: Mon, 26 Sep 2016 11:06:58 +0100	[thread overview]
Message-ID: <20160926100658.GA15828@bricha3-MOBL3> (raw)
In-Reply-To: <1474882625-67916-1-git-send-email-wei.dai@intel.com>

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];

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
into three, a, b, and c, and how you use each of those three sets. Perhaps
also provide a comment alongside each member of the structure above.

<snip>
> +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;
> +}

Again, this needs a comment explaining what this function is doing, and
how/why it is doing so.

> +
> +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;
> +}

Again, comment explaining function, please.

> +
> +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);

Why are you inserting 5 rules at random positions at the end? Explanatory
comment needed, thanks.


When running the code with the new auto-generated table, the rule add time
is 5x longer than that with the original test. Have you investigated what
causes this, and is there something that can be done to work around it?

Regards,
/Bruce

  parent reply	other threads:[~2016-09-26 10:07 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-09-26  9:37 Wei Dai
2016-09-26  9:56 ` Thomas Monjalon
2016-09-26 13:07   ` Dai, Wei
2016-09-26 10:06 ` Bruce Richardson [this message]
2016-09-26 13:49   ` Dai, Wei
2016-09-27 17:38 ` [dpdk-dev] [PATCH v2] " Wei Dai
2016-09-28  8:41   ` Bruce Richardson
2016-09-28 15:19     ` Dai, Wei
2016-10-13 13:28   ` Thomas Monjalon

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20160926100658.GA15828@bricha3-MOBL3 \
    --to=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    --cc=wei.dai@intel.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).