Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2254/?format=api
{ "id": 2254, "url": "https://patches.dpdk.org/api/patches/2254/?format=api", "web_url": "https://patches.dpdk.org/project/dpdk/patch/1421090181-17150-5-git-send-email-konstantin.ananyev@intel.com/", "project": { "id": 1, "url": "https://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<1421090181-17150-5-git-send-email-konstantin.ananyev@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1421090181-17150-5-git-send-email-konstantin.ananyev@intel.com", "date": "2015-01-12T19:16:08", "name": "[dpdk-dev,v2,04/17] librte_acl: remove build phase heuristsic with negative perfomance effect.", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "849078ef13168059f1ea943f47dfefcebf5a515b", "submitter": { "id": 33, "url": "https://patches.dpdk.org/api/people/33/?format=api", "name": "Ananyev, Konstantin", "email": "konstantin.ananyev@intel.com" }, "delegate": null, "mbox": "https://patches.dpdk.org/project/dpdk/patch/1421090181-17150-5-git-send-email-konstantin.ananyev@intel.com/mbox/", "series": [], "comments": "https://patches.dpdk.org/api/patches/2254/comments/", "check": "pending", "checks": "https://patches.dpdk.org/api/patches/2254/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [IPv6:::1])\n\tby dpdk.org (Postfix) with ESMTP id 3CCCC5A9E;\n\tMon, 12 Jan 2015 20:17:00 +0100 (CET)", "from mga11.intel.com (mga11.intel.com [192.55.52.93])\n\tby dpdk.org (Postfix) with ESMTP id 859D35A83\n\tfor <dev@dpdk.org>; Mon, 12 Jan 2015 20:16:38 +0100 (CET)", "from orsmga002.jf.intel.com ([10.7.209.21])\n\tby fmsmga102.fm.intel.com with ESMTP; 12 Jan 2015 11:16:37 -0800", "from irvmail001.ir.intel.com ([163.33.26.43])\n\tby orsmga002.jf.intel.com with ESMTP; 12 Jan 2015 11:16:35 -0800", "from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com\n\t[10.237.217.46])\n\tby irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id\n\tt0CJGZ1I008620; Mon, 12 Jan 2015 19:16:35 GMT", "from sivswdev02.ir.intel.com (localhost [127.0.0.1])\n\tby sivswdev02.ir.intel.com with ESMTP id t0CJGZUn017228;\n\tMon, 12 Jan 2015 19:16:35 GMT", "(from kananye1@localhost)\n\tby sivswdev02.ir.intel.com with id t0CJGZLS017224;\n\tMon, 12 Jan 2015 19:16:35 GMT" ], "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.07,745,1413270000\"; d=\"scan'208\";a=\"668605486\"", "From": "Konstantin Ananyev <konstantin.ananyev@intel.com>", "To": "dev@dpdk.org", "Date": "Mon, 12 Jan 2015 19:16:08 +0000", "Message-Id": "<1421090181-17150-5-git-send-email-konstantin.ananyev@intel.com>", "X-Mailer": "git-send-email 1.7.4.1", "In-Reply-To": "<1421090181-17150-1-git-send-email-konstantin.ananyev@intel.com>", "References": "<1421090181-17150-1-git-send-email-konstantin.ananyev@intel.com>", "Subject": "[dpdk-dev] [PATCH v2 04/17] librte_acl: remove build phase\n\theuristsic with negative perfomance effect.", "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>,\n\t<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>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "Current rule-wildness based heuristsics can cause unnecessary splits of\nthe ruleset.\nThat might have negative perfomance effect:\nmore tries to traverse, bigger RT tables.\nAfter removing it, on some test-cases with big rulesets (~10K)\nobserved ~50% speedup.\nNo difference for smaller rulesets.\n\nSigned-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>\n---\n lib/librte_acl/acl_bld.c | 277 +++++++++++++++++------------------------------\n 1 file changed, 97 insertions(+), 180 deletions(-)", "diff": "diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c\nindex c5a674a..8bf4a54 100644\n--- a/lib/librte_acl/acl_bld.c\n+++ b/lib/librte_acl/acl_bld.c\n@@ -1539,11 +1539,9 @@ acl_calc_wildness(struct rte_acl_build_rule *head,\n \treturn 0;\n }\n \n-static int\n-acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config,\n-\tuint32_t *wild_limit)\n+static void\n+acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config)\n {\n-\tint min;\n \tstruct rte_acl_build_rule *rule;\n \tuint32_t n, m, fields_deactivated = 0;\n \tuint32_t start = 0, deactivate = 0;\n@@ -1604,129 +1602,58 @@ acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config,\n \n \t\tfor (k = 0; k < config->num_fields; k++) {\n \t\t\tif (tally[k][TALLY_DEACTIVATED] == 0) {\n-\t\t\t\tmemcpy(&tally[l][0], &tally[k][0],\n+\t\t\t\tmemmove(&tally[l][0], &tally[k][0],\n \t\t\t\t\tTALLY_NUM * sizeof(tally[0][0]));\n-\t\t\t\tmemcpy(&config->defs[l++],\n+\t\t\t\tmemmove(&config->defs[l++],\n \t\t\t\t\t&config->defs[k],\n \t\t\t\t\tsizeof(struct rte_acl_field_def));\n \t\t\t}\n \t\t}\n \t\tconfig->num_fields = l;\n \t}\n-\n-\tmin = RTE_ACL_SINGLE_TRIE_SIZE;\n-\tif (config->num_fields == 2)\n-\t\tmin *= 4;\n-\telse if (config->num_fields == 3)\n-\t\tmin *= 3;\n-\telse if (config->num_fields == 4)\n-\t\tmin *= 2;\n-\n-\tif (tally[0][TALLY_0] < min)\n-\t\treturn 0;\n-\tfor (n = 0; n < config->num_fields; n++)\n-\t\twild_limit[n] = 0;\n-\n-\t/*\n-\t * If trailing fields are 100% wild, group those together.\n-\t * This allows the search length of the trie to be shortened.\n-\t */\n-\tfor (n = 1; n < config->num_fields; n++) {\n-\n-\t\tdouble rule_percentage = (double)tally[n][TALLY_DEPTH] /\n-\t\t\ttally[n][0];\n-\n-\t\tif (rule_percentage > RULE_PERCENTAGE) {\n-\t\t\t/* if it crosses an input boundary then round up */\n-\t\t\twhile (config->defs[n - 1].input_index ==\n-\t\t\t\t\tconfig->defs[n].input_index)\n-\t\t\t\tn++;\n-\n-\t\t\t/* set the limit for selecting rules */\n-\t\t\twhile (n < config->num_fields)\n-\t\t\t\twild_limit[n++] = 100;\n-\n-\t\t\tif (wild_limit[n - 1] == 100)\n-\t\t\t\treturn 1;\n-\t\t}\n-\t}\n-\n-\t/* look for the most wild that's 40% or more of the rules */\n-\tfor (n = 1; n < config->num_fields; n++) {\n-\t\tfor (m = TALLY_100; m > 0; m--) {\n-\n-\t\t\tdouble rule_percentage = (double)tally[n][m] /\n-\t\t\t\ttally[n][0];\n-\n-\t\t\tif (tally[n][TALLY_DEACTIVATED] == 0 &&\n-\t\t\t\t\ttally[n][TALLY_0] >\n-\t\t\t\t\tRTE_ACL_SINGLE_TRIE_SIZE &&\n-\t\t\t\t\trule_percentage > NODE_PERCENTAGE &&\n-\t\t\t\t\trule_percentage < 0.80) {\n-\t\t\t\twild_limit[n] = wild_limits[m];\n-\t\t\t\treturn 1;\n-\t\t\t}\n-\t\t}\n-\t}\n-\treturn 0;\n }\n \n static int\n-order(struct rte_acl_build_rule **insert, struct rte_acl_build_rule *rule)\n+rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2)\n {\n \tuint32_t n;\n-\tstruct rte_acl_build_rule *left = *insert;\n-\n-\tif (left == NULL)\n-\t\treturn 0;\n \n-\tfor (n = 1; n < left->config->num_fields; n++) {\n-\t\tint field_index = left->config->defs[n].field_index;\n+\tfor (n = 1; n < r1->config->num_fields; n++) {\n+\t\tint field_index = r1->config->defs[n].field_index;\n \n-\t\tif (left->wildness[field_index] != rule->wildness[field_index])\n-\t\t\treturn (left->wildness[field_index] >=\n-\t\t\t\trule->wildness[field_index]);\n+\t\tif (r1->wildness[field_index] != r2->wildness[field_index])\n+\t\t\treturn (r1->wildness[field_index] -\n+\t\t\t\tr2->wildness[field_index]);\n \t}\n \treturn 0;\n }\n \n static struct rte_acl_build_rule *\n-ordered_insert_rule(struct rte_acl_build_rule *head,\n-\tstruct rte_acl_build_rule *rule)\n-{\n-\tstruct rte_acl_build_rule **insert;\n-\n-\tif (rule == NULL)\n-\t\treturn head;\n-\n-\trule->next = head;\n-\tif (head == NULL)\n-\t\treturn rule;\n-\n-\tinsert = &head;\n-\twhile (order(insert, rule))\n-\t\tinsert = &(*insert)->next;\n-\n-\trule->next = *insert;\n-\t*insert = rule;\n-\treturn head;\n-}\n-\n-static struct rte_acl_build_rule *\n sort_rules(struct rte_acl_build_rule *head)\n {\n-\tstruct rte_acl_build_rule *rule, *reordered_head = NULL;\n-\tstruct rte_acl_build_rule *last_rule = NULL;\n-\n-\tfor (rule = head; rule != NULL; rule = rule->next) {\n-\t\treordered_head = ordered_insert_rule(reordered_head, last_rule);\n-\t\tlast_rule = rule;\n+\tstruct rte_acl_build_rule *new_head;\n+\tstruct rte_acl_build_rule *l, *r, **p;\n+\n+\tnew_head = NULL;\n+\twhile (head != NULL) {\n+\t\tr = head;\n+\t\thead = r->next;\n+\t\tr->next = NULL;\n+\t\tif (new_head == NULL) {\n+\t\t\tnew_head = r;\n+\t\t} else {\n+\t\t\tfor (p = &new_head;\n+\t\t\t\t\t(l = *p) != NULL &&\n+\t\t\t\t\trule_cmp_wildness(l, r) >= 0;\n+\t\t\t\t\tp = &l->next)\n+\t\t\t\t;\n+\n+\t\t\tr->next = *p;\n+\t\t\t*p = r;\n+\t\t}\n \t}\n \n-\tif (last_rule != reordered_head)\n-\t\treordered_head = ordered_insert_rule(reordered_head, last_rule);\n-\n-\treturn reordered_head;\n+\treturn new_head;\n }\n \n static uint32_t\n@@ -1748,21 +1675,44 @@ acl_build_index(const struct rte_acl_config *config, uint32_t *data_index)\n \treturn m;\n }\n \n+static struct rte_acl_build_rule *\n+build_one_trie(struct acl_build_context *context,\n+\tstruct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],\n+\tuint32_t n)\n+{\n+\tstruct rte_acl_build_rule *last;\n+\tstruct rte_acl_config *config;\n+\n+\tconfig = rule_sets[n]->config;\n+\n+\tacl_rule_stats(rule_sets[n], config);\n+\trule_sets[n] = sort_rules(rule_sets[n]);\n+\n+\tcontext->tries[n].type = RTE_ACL_FULL_TRIE;\n+\tcontext->tries[n].count = 0;\n+\n+\tcontext->tries[n].num_data_indexes = acl_build_index(config,\n+\t\tcontext->data_indexes[n]);\n+\tcontext->tries[n].data_index = context->data_indexes[n];\n+\n+\tcontext->bld_tries[n].trie = build_trie(context, rule_sets[n],\n+\t\t&last, &context->tries[n].count);\n+\n+\treturn last;\n+}\n+\n static int\n acl_build_tries(struct acl_build_context *context,\n \tstruct rte_acl_build_rule *head)\n {\n \tint32_t rc;\n-\tuint32_t n, m, num_tries;\n+\tuint32_t n, num_tries;\n \tstruct rte_acl_config *config;\n-\tstruct rte_acl_build_rule *last, *rule;\n-\tuint32_t wild_limit[RTE_ACL_MAX_LEVELS];\n+\tstruct rte_acl_build_rule *last;\n \tstruct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES];\n \n \tconfig = head->config;\n-\trule = head;\n \trule_sets[0] = head;\n-\tnum_tries = 1;\n \n \t/* initialize tries */\n \tfor (n = 0; n < RTE_DIM(context->tries); n++) {\n@@ -1779,91 +1729,55 @@ acl_build_tries(struct acl_build_context *context,\n \tif (rc != 0)\n \t\treturn rc;\n \n-\tn = acl_rule_stats(head, config, &wild_limit[0]);\n-\n-\t/* put all rules that fit the wildness criteria into a seperate trie */\n-\twhile (n > 0 && num_tries < RTE_ACL_MAX_TRIES) {\n+\tfor (n = 0;; n = num_tries) {\n \n-\t\tstruct rte_acl_config *new_config;\n-\t\tstruct rte_acl_build_rule **prev = &rule_sets[num_tries - 1];\n-\t\tstruct rte_acl_build_rule *next = head->next;\n+\t\tnum_tries = n + 1;\n \n-\t\tnew_config = acl_build_alloc(context, 1, sizeof(*new_config));\n-\t\tif (new_config == NULL) {\n-\t\t\tRTE_LOG(ERR, ACL,\n-\t\t\t\t\"Failed to get space for new config\\n\");\n+\t\tlast = build_one_trie(context, rule_sets, n);\n+\t\tif (context->bld_tries[n].trie == NULL) {\n+\t\t\tRTE_LOG(ERR, ACL, \"Build of %u-th trie failed\\n\", n);\n \t\t\treturn -ENOMEM;\n \t\t}\n \n-\t\tmemcpy(new_config, config, sizeof(*new_config));\n-\t\tconfig = new_config;\n-\t\trule_sets[num_tries] = NULL;\n-\n-\t\tfor (rule = head; rule != NULL; rule = next) {\n+\t\t/* Build of the last trie completed. */\n+\t\tif (last == NULL)\n+\t\t\tbreak;\n \n-\t\t\tint move = 1;\n+\t\tif (num_tries == RTE_DIM(context->tries)) {\n+\t\t\tRTE_LOG(ERR, ACL,\n+\t\t\t\t\"Exceeded max number of tries: %u\\n\",\n+\t\t\t\tnum_tries);\n+\t\t\treturn -ENOMEM;\n+\t\t}\n \n-\t\t\tnext = rule->next;\n-\t\t\tfor (m = 0; m < config->num_fields; m++) {\n-\t\t\t\tint x = config->defs[m].field_index;\n-\t\t\t\tif (rule->wildness[x] < wild_limit[m]) {\n-\t\t\t\t\tmove = 0;\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t}\n+\t\t/* Trie is getting too big, split remaining rule set. */\n+\t\trule_sets[num_tries] = last->next;\n+\t\tlast->next = NULL;\n+\t\tacl_free_node(context, context->bld_tries[n].trie);\n \n-\t\t\tif (move) {\n-\t\t\t\trule->config = new_config;\n-\t\t\t\trule->next = rule_sets[num_tries];\n-\t\t\t\trule_sets[num_tries] = rule;\n-\t\t\t\t*prev = next;\n-\t\t\t} else\n-\t\t\t\tprev = &rule->next;\n+\t\t/* Create a new copy of config for remaining rules. */\n+\t\tconfig = acl_build_alloc(context, 1, sizeof(*config));\n+\t\tif (config == NULL) {\n+\t\t\tRTE_LOG(ERR, ACL,\n+\t\t\t\t\"New config allocation for %u-th \"\n+\t\t\t\t\"trie failed\\n\", num_tries);\n+\t\t\treturn -ENOMEM;\n \t\t}\n \n-\t\thead = rule_sets[num_tries];\n-\t\tn = acl_rule_stats(rule_sets[num_tries], config,\n-\t\t\t&wild_limit[0]);\n-\t\tnum_tries++;\n-\t}\n-\n-\tif (n > 0)\n-\t\tRTE_LOG(DEBUG, ACL,\n-\t\t\t\"Number of tries(%d) exceeded.\\n\", RTE_ACL_MAX_TRIES);\n+\t\tmemcpy(config, rule_sets[n]->config, sizeof(*config));\n \n-\tfor (n = 0; n < num_tries; n++) {\n+\t\t/* Make remaining rules use new config. */\n+\t\tfor (head = rule_sets[num_tries]; head != NULL;\n+\t\t\t\thead = head->next)\n+\t\t\thead->config = config;\n \n-\t\trule_sets[n] = sort_rules(rule_sets[n]);\n-\t\tcontext->tries[n].type = RTE_ACL_FULL_TRIE;\n-\t\tcontext->tries[n].count = 0;\n-\t\tcontext->tries[n].num_data_indexes =\n-\t\t\tacl_build_index(rule_sets[n]->config,\n-\t\t\tcontext->data_indexes[n]);\n-\t\tcontext->tries[n].data_index = context->data_indexes[n];\n-\n-\t\tcontext->bld_tries[n].trie =\n-\t\t\t\tbuild_trie(context, rule_sets[n],\n-\t\t\t\t&last, &context->tries[n].count);\n-\t\tif (context->bld_tries[n].trie == NULL) {\n+\t\t/* Rebuild the trie for the reduced rule-set. */\n+\t\tlast = build_one_trie(context, rule_sets, n);\n+\t\tif (context->bld_tries[n].trie == NULL || last != NULL) {\n \t\t\tRTE_LOG(ERR, ACL, \"Build of %u-th trie failed\\n\", n);\n \t\t\treturn -ENOMEM;\n \t\t}\n \n-\t\tif (last != NULL) {\n-\t\t\trule_sets[num_tries++] = last->next;\n-\t\t\tlast->next = NULL;\n-\t\t\tacl_free_node(context, context->bld_tries[n].trie);\n-\t\t\tcontext->tries[n].count = 0;\n-\n-\t\t\tcontext->bld_tries[n].trie =\n-\t\t\t\t\tbuild_trie(context, rule_sets[n],\n-\t\t\t\t\t&last, &context->tries[n].count);\n-\t\t\tif (context->bld_tries[n].trie == NULL) {\n-\t\t\t\tRTE_LOG(ERR, ACL,\n-\t\t\t\t\t\"Build of %u-th trie failed\\n\", n);\n-\t\t\t\t\treturn -ENOMEM;\n-\t\t\t}\n-\t\t}\n \t}\n \n \tcontext->num_tries = num_tries;\n@@ -1876,15 +1790,18 @@ acl_build_log(const struct acl_build_context *ctx)\n \tuint32_t n;\n \n \tRTE_LOG(DEBUG, ACL, \"Build phase for ACL \\\"%s\\\":\\n\"\n+\t\t\"nodes created: %u\\n\"\n \t\t\"memory consumed: %zu\\n\",\n \t\tctx->acx->name,\n+\t\tctx->num_nodes,\n \t\tctx->pool.alloc);\n \n \tfor (n = 0; n < RTE_DIM(ctx->tries); n++) {\n \t\tif (ctx->tries[n].count != 0)\n \t\t\tRTE_LOG(DEBUG, ACL,\n-\t\t\t\t\"trie %u: number of rules: %u\\n\",\n-\t\t\t\tn, ctx->tries[n].count);\n+\t\t\t\t\"trie %u: number of rules: %u, indexes: %u\\n\",\n+\t\t\t\tn, ctx->tries[n].count,\n+\t\t\t\tctx->tries[n].num_data_indexes);\n \t}\n }\n \n", "prefixes": [ "dpdk-dev", "v2", "04/17" ] }