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 8A6AF5AA5 for ; Tue, 20 Jan 2015 19:41:24 +0100 (CET) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga103.fm.intel.com with ESMTP; 20 Jan 2015 10:35:43 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.97,862,1389772800"; d="scan'208";a="442827088" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by FMSMGA003.fm.intel.com with ESMTP; 20 Jan 2015 10:28:05 -0800 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t0KIfLTc029514; Tue, 20 Jan 2015 18:41:21 GMT Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t0KIfLOH018898; Tue, 20 Jan 2015 18:41:21 GMT Received: (from kananye1@localhost) by sivswdev02.ir.intel.com with id t0KIfLpW018894; Tue, 20 Jan 2015 18:41:21 GMT From: Konstantin Ananyev To: dev@dpdk.org Date: Tue, 20 Jan 2015 18:41:05 +0000 Message-Id: <1421779267-18492-17-git-send-email-konstantin.ananyev@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1421779267-18492-1-git-send-email-konstantin.ananyev@intel.com> References: <1421779267-18492-1-git-send-email-konstantin.ananyev@intel.com> Subject: [dpdk-dev] [PATCH v3 16/18] libte_acl: introduce max_size into rte_acl_config. 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: Tue, 20 Jan 2015 18:41:28 -0000 If at build phase we don't make any trie splitting, then temporary build structures and resulting RT structure might be much bigger than current. >>From other side - having just one trie instead of multiple can speedup search quite significantly. >>From my measurements on rule-sets with ~10K rules: RT table up to 8 times bigger, classify() up to 80% faster than current implementation. To make it possible for the user to decide about performance/space trade-off - new parameter for build config structure (max_size) is introduced. Setting it to the value greater than zero, instructs rte_acl_build() to: - make sure that size of RT table wouldn't exceed given value. - attempt to minimise number of tries in the table. Setting it to zero maintains current behaviour. That introduces a minor change in the public API, but I think the possible performance gain is too big to ignore it. Signed-off-by: Konstantin Ananyev --- app/test-acl/main.c | 33 ++++++++---- examples/l3fwd-acl/main.c | 3 +- lib/librte_acl/acl.h | 2 +- lib/librte_acl/acl_bld.c | 134 +++++++++++++++++++++++++++++----------------- lib/librte_acl/acl_gen.c | 22 +++++--- lib/librte_acl/rte_acl.c | 1 + lib/librte_acl/rte_acl.h | 2 + 7 files changed, 131 insertions(+), 66 deletions(-) diff --git a/app/test-acl/main.c b/app/test-acl/main.c index 52f43c6..5e8db04 100644 --- a/app/test-acl/main.c +++ b/app/test-acl/main.c @@ -85,6 +85,7 @@ #define OPT_SEARCH_ALG "alg" #define OPT_BLD_CATEGORIES "bldcat" #define OPT_RUN_CATEGORIES "runcat" +#define OPT_MAX_SIZE "maxsize" #define OPT_ITER_NUM "iter" #define OPT_VERBOSE "verbose" #define OPT_IPV6 "ipv6" @@ -126,6 +127,7 @@ static struct { const char *prgname; const char *rule_file; const char *trace_file; + size_t max_size; uint32_t bld_categories; uint32_t run_categories; uint32_t nb_rules; @@ -780,6 +782,8 @@ acx_init(void) FILE *f; struct rte_acl_config cfg; + memset(&cfg, 0, sizeof(cfg)); + /* setup ACL build config. */ if (config.ipv6) { cfg.num_fields = RTE_DIM(ipv6_defs); @@ -789,6 +793,7 @@ acx_init(void) memcpy(&cfg.defs, ipv4_defs, sizeof(ipv4_defs)); } cfg.num_categories = config.bld_categories; + cfg.max_size = config.max_size; /* setup ACL creation parameters. */ prm.rule_size = RTE_ACL_RULE_SZ(cfg.num_fields); @@ -899,8 +904,8 @@ search_ip5tuples(__attribute__((unused)) void *arg) return 0; } -static uint32_t -get_uint32_opt(const char *opt, const char *name, uint32_t min, uint32_t max) +static unsigned long +get_ulong_opt(const char *opt, const char *name, size_t min, size_t max) { unsigned long val; char *end; @@ -964,6 +969,9 @@ print_usage(const char *prgname) "= " "should be either 1 or multiple of %zu, " "but not greater then %u]\n" + "[--" OPT_MAX_SIZE + "= " + "leave 0 for default behaviour]\n" "[--" OPT_ITER_NUM "=]\n" "[--" OPT_VERBOSE "=]\n" "[--" OPT_SEARCH_ALG "=%s]\n" @@ -984,6 +992,7 @@ dump_config(FILE *f) fprintf(f, "%s:%u\n", OPT_TRACE_STEP, config.trace_step); fprintf(f, "%s:%u\n", OPT_BLD_CATEGORIES, config.bld_categories); fprintf(f, "%s:%u\n", OPT_RUN_CATEGORIES, config.run_categories); + fprintf(f, "%s:%zu\n", OPT_MAX_SIZE, config.max_size); fprintf(f, "%s:%u\n", OPT_ITER_NUM, config.iter_num); fprintf(f, "%s:%u\n", OPT_VERBOSE, config.verbose); fprintf(f, "%s:%u(%s)\n", OPT_SEARCH_ALG, config.alg.alg, @@ -1010,6 +1019,7 @@ get_input_opts(int argc, char **argv) {OPT_TRACE_FILE, 1, 0, 0}, {OPT_TRACE_NUM, 1, 0, 0}, {OPT_RULE_NUM, 1, 0, 0}, + {OPT_MAX_SIZE, 1, 0, 0}, {OPT_TRACE_STEP, 1, 0, 0}, {OPT_BLD_CATEGORIES, 1, 0, 0}, {OPT_RUN_CATEGORIES, 1, 0, 0}, @@ -1034,29 +1044,32 @@ get_input_opts(int argc, char **argv) } else if (strcmp(lgopts[opt_idx].name, OPT_TRACE_FILE) == 0) { config.trace_file = optarg; } else if (strcmp(lgopts[opt_idx].name, OPT_RULE_NUM) == 0) { - config.nb_rules = get_uint32_opt(optarg, + config.nb_rules = get_ulong_opt(optarg, lgopts[opt_idx].name, 1, RTE_ACL_MAX_INDEX + 1); + } else if (strcmp(lgopts[opt_idx].name, OPT_MAX_SIZE) == 0) { + config.max_size = get_ulong_opt(optarg, + lgopts[opt_idx].name, 0, SIZE_MAX); } else if (strcmp(lgopts[opt_idx].name, OPT_TRACE_NUM) == 0) { - config.nb_traces = get_uint32_opt(optarg, + config.nb_traces = get_ulong_opt(optarg, lgopts[opt_idx].name, 1, UINT32_MAX); } else if (strcmp(lgopts[opt_idx].name, OPT_TRACE_STEP) == 0) { - config.trace_step = get_uint32_opt(optarg, + config.trace_step = get_ulong_opt(optarg, lgopts[opt_idx].name, 1, TRACE_STEP_MAX); } else if (strcmp(lgopts[opt_idx].name, OPT_BLD_CATEGORIES) == 0) { - config.bld_categories = get_uint32_opt(optarg, + config.bld_categories = get_ulong_opt(optarg, lgopts[opt_idx].name, 1, RTE_ACL_MAX_CATEGORIES); } else if (strcmp(lgopts[opt_idx].name, OPT_RUN_CATEGORIES) == 0) { - config.run_categories = get_uint32_opt(optarg, + config.run_categories = get_ulong_opt(optarg, lgopts[opt_idx].name, 1, RTE_ACL_MAX_CATEGORIES); } else if (strcmp(lgopts[opt_idx].name, OPT_ITER_NUM) == 0) { - config.iter_num = get_uint32_opt(optarg, - lgopts[opt_idx].name, 1, UINT16_MAX); + config.iter_num = get_ulong_opt(optarg, + lgopts[opt_idx].name, 1, INT32_MAX); } else if (strcmp(lgopts[opt_idx].name, OPT_VERBOSE) == 0) { - config.verbose = get_uint32_opt(optarg, + config.verbose = get_ulong_opt(optarg, lgopts[opt_idx].name, DUMP_NONE, DUMP_MAX); } else if (strcmp(lgopts[opt_idx].name, OPT_SEARCH_ALG) == 0) { diff --git a/examples/l3fwd-acl/main.c b/examples/l3fwd-acl/main.c index 022ccab..f1f7601 100644 --- a/examples/l3fwd-acl/main.c +++ b/examples/l3fwd-acl/main.c @@ -1178,8 +1178,9 @@ setup_acl(struct rte_acl_rule *route_base, rte_exit(EXIT_FAILURE, "add rules failed\n"); /* Perform builds */ - acl_build_param.num_categories = DEFAULT_MAX_CATEGORIES; + memset(&acl_build_param, 0, sizeof(acl_build_param)); + acl_build_param.num_categories = DEFAULT_MAX_CATEGORIES; acl_build_param.num_fields = dim; memcpy(&acl_build_param.defs, ipv6 ? ipv6_defs : ipv4_defs, ipv6 ? sizeof(ipv6_defs) : sizeof(ipv4_defs)); diff --git a/lib/librte_acl/acl.h b/lib/librte_acl/acl.h index d33d7ad..61b849a 100644 --- a/lib/librte_acl/acl.h +++ b/lib/librte_acl/acl.h @@ -180,7 +180,7 @@ struct rte_acl_ctx { int rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie, struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries, - uint32_t num_categories, uint32_t data_index_sz); + uint32_t num_categories, uint32_t data_index_sz, size_t max_size); typedef int (*rte_acl_classify_t) (const struct rte_acl_ctx *, const uint8_t **, uint32_t *, uint32_t, uint32_t); diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c index 1fd59ee..1fe79fb 100644 --- a/lib/librte_acl/acl_bld.c +++ b/lib/librte_acl/acl_bld.c @@ -41,10 +41,9 @@ /* number of pointers per alloc */ #define ACL_PTR_ALLOC 32 -/* variable for dividing rule sets */ -#define NODE_MAX 2500 -#define NODE_PERCENTAGE (0.40) -#define RULE_PERCENTAGE (0.40) +/* macros for dividing rule sets heuristics */ +#define NODE_MAX 0x4000 +#define NODE_MIN 0x800 /* TALLY are statistics per field */ enum { @@ -97,6 +96,7 @@ struct acl_build_context { const struct rte_acl_ctx *acx; struct rte_acl_build_rule *build_rules; struct rte_acl_config cfg; + int32_t node_max; uint32_t node; uint32_t num_nodes; uint32_t category_mask; @@ -1447,7 +1447,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, return NULL; node_count = context->num_nodes - node_count; - if (node_count > NODE_MAX) { + if (node_count > context->node_max) { *last = prev; return trie; } @@ -1628,6 +1628,9 @@ rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2) return 0; } +/* + * Sort list of rules based on the rules wildness. + */ static struct rte_acl_build_rule * sort_rules(struct rte_acl_build_rule *head) { @@ -1636,21 +1639,22 @@ sort_rules(struct rte_acl_build_rule *head) new_head = NULL; while (head != NULL) { + + /* remove element from the head of the old list. */ r = head; head = r->next; r->next = NULL; - if (new_head == NULL) { - new_head = r; - } else { - for (p = &new_head; - (l = *p) != NULL && - rule_cmp_wildness(l, r) >= 0; - p = &l->next) - ; - - r->next = *p; - *p = r; - } + + /* walk through new sorted list to find a proper place. */ + for (p = &new_head; + (l = *p) != NULL && + rule_cmp_wildness(l, r) >= 0; + p = &l->next) + ; + + /* insert element into the new sorted list. */ + r->next = *p; + *p = r; } return new_head; @@ -1789,9 +1793,11 @@ acl_build_log(const struct acl_build_context *ctx) uint32_t n; RTE_LOG(DEBUG, ACL, "Build phase for ACL \"%s\":\n" + "node limit for tree split: %u\n" "nodes created: %u\n" "memory consumed: %zu\n", ctx->acx->name, + ctx->node_max, ctx->num_nodes, ctx->pool.alloc); @@ -1868,11 +1874,48 @@ acl_set_data_indexes(struct rte_acl_ctx *ctx) } } +/* + * Internal routine, performs 'build' phase of trie generation: + * - setups build context. + * - analizes given set of rules. + * - builds internal tree(s). + */ +static int +acl_bld(struct acl_build_context *bcx, struct rte_acl_ctx *ctx, + const struct rte_acl_config *cfg, uint32_t node_max) +{ + int32_t rc; + + /* setup build context. */ + memset(bcx, 0, sizeof(*bcx)); + bcx->acx = ctx; + bcx->pool.alignment = ACL_POOL_ALIGN; + bcx->pool.min_alloc = ACL_POOL_ALLOC_MIN; + bcx->cfg = *cfg; + bcx->category_mask = LEN2MASK(bcx->cfg.num_categories); + bcx->node_max = node_max; + + /* Create a build rules copy. */ + rc = acl_build_rules(bcx); + if (rc != 0) + return rc; + + /* No rules to build for that context+config */ + if (bcx->build_rules == NULL) { + rc = -EINVAL; + } else { + /* build internal trie representation. */ + rc = acl_build_tries(bcx, bcx->build_rules); + } + return rc; +} int rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg) { - int rc; + int32_t rc; + uint32_t n; + size_t max_size; struct acl_build_context bcx; if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 || @@ -1881,44 +1924,39 @@ rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg) acl_build_reset(ctx); - memset(&bcx, 0, sizeof(bcx)); - bcx.acx = ctx; - bcx.pool.alignment = ACL_POOL_ALIGN; - bcx.pool.min_alloc = ACL_POOL_ALLOC_MIN; - bcx.cfg = *cfg; - bcx.category_mask = LEN2MASK(bcx.cfg.num_categories); - - - /* Create a build rules copy. */ - rc = acl_build_rules(&bcx); - if (rc != 0) - return rc; + if (cfg->max_size == 0) { + n = NODE_MIN; + max_size = SIZE_MAX; + } else { + n = NODE_MAX; + max_size = cfg->max_size; + } - /* No rules to build for that context+config */ - if (bcx.build_rules == NULL) { - rc = -EINVAL; + for (rc = -ERANGE; n >= NODE_MIN && rc == -ERANGE; n /= 2) { - /* build internal trie representation. */ - } else if ((rc = acl_build_tries(&bcx, bcx.build_rules)) == 0) { + /* perform build phase. */ + rc = acl_bld(&bcx, ctx, cfg, n); - /* allocate and fill run-time structures. */ - rc = rte_acl_gen(ctx, bcx.tries, bcx.bld_tries, + if (rc == 0) { + /* allocate and fill run-time structures. */ + rc = rte_acl_gen(ctx, bcx.tries, bcx.bld_tries, bcx.num_tries, bcx.cfg.num_categories, RTE_ACL_MAX_FIELDS * RTE_DIM(bcx.tries) * - sizeof(ctx->data_indexes[0])); - if (rc == 0) { + sizeof(ctx->data_indexes[0]), max_size); + if (rc == 0) { + /* set data indexes. */ + acl_set_data_indexes(ctx); - /* set data indexes. */ - acl_set_data_indexes(ctx); - - /* copy in build config. */ - ctx->config = *cfg; + /* copy in build config. */ + ctx->config = *cfg; + } } - } - acl_build_log(&bcx); + acl_build_log(&bcx); + + /* cleanup after build. */ + tb_free_pool(&bcx.pool); + } - /* cleanup after build. */ - tb_free_pool(&bcx.pool); return rc; } diff --git a/lib/librte_acl/acl_gen.c b/lib/librte_acl/acl_gen.c index d3def66..ea557ab 100644 --- a/lib/librte_acl/acl_gen.c +++ b/lib/librte_acl/acl_gen.c @@ -32,7 +32,6 @@ */ #include -#include "acl_vect.h" #include "acl.h" #define QRANGE_MIN ((uint8_t)INT8_MIN) @@ -63,7 +62,8 @@ struct rte_acl_indices { static void acl_gen_log_stats(const struct rte_acl_ctx *ctx, const struct acl_node_counters *counts, - const struct rte_acl_indices *indices) + const struct rte_acl_indices *indices, + size_t max_size) { RTE_LOG(DEBUG, ACL, "Gen phase for ACL \"%s\":\n" "runtime memory footprint on socket %d:\n" @@ -71,7 +71,8 @@ acl_gen_log_stats(const struct rte_acl_ctx *ctx, "quad nodes/vectors/bytes used: %d/%d/%zu\n" "DFA nodes/group64/bytes used: %d/%d/%zu\n" "match nodes/bytes used: %d/%zu\n" - "total: %zu bytes\n", + "total: %zu bytes\n" + "max limit: %zu bytes\n", ctx->name, ctx->socket_id, counts->single, counts->single * sizeof(uint64_t), counts->quad, counts->quad_vectors, @@ -80,7 +81,8 @@ acl_gen_log_stats(const struct rte_acl_ctx *ctx, indices->dfa_index * sizeof(uint64_t), counts->match, counts->match * sizeof(struct rte_acl_match_results), - ctx->mem_sz); + ctx->mem_sz, + max_size); } static uint64_t @@ -474,7 +476,7 @@ acl_calc_counts_indices(struct acl_node_counters *counts, int rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie, struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries, - uint32_t num_categories, uint32_t data_index_sz) + uint32_t num_categories, uint32_t data_index_sz, size_t max_size) { void *mem; size_t total_size; @@ -496,6 +498,14 @@ rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie, (counts.match + 1) * sizeof(struct rte_acl_match_results) + XMM_SIZE; + if (total_size > max_size) { + RTE_LOG(DEBUG, ACL, + "Gen phase for ACL ctx \"%s\" exceeds max_size limit, " + "bytes required: %zu, allowed: %zu\n", + ctx->name, total_size, max_size); + return -ERANGE; + } + mem = rte_zmalloc_socket(ctx->name, total_size, RTE_CACHE_LINE_SIZE, ctx->socket_id); if (mem == NULL) { @@ -546,6 +556,6 @@ rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie, ctx->trans_table = node_array; memcpy(ctx->trie, trie, sizeof(ctx->trie)); - acl_gen_log_stats(ctx, &counts, &indices); + acl_gen_log_stats(ctx, &counts, &indices, max_size); return 0; } diff --git a/lib/librte_acl/rte_acl.c b/lib/librte_acl/rte_acl.c index a9cd349..7d10301 100644 --- a/lib/librte_acl/rte_acl.c +++ b/lib/librte_acl/rte_acl.c @@ -543,6 +543,7 @@ rte_acl_ipv4vlan_build(struct rte_acl_ctx *ctx, if (ctx == NULL || layout == NULL) return -EINVAL; + memset(&cfg, 0, sizeof(cfg)); acl_ipv4vlan_config(&cfg, layout, num_categories); return rte_acl_build(ctx, &cfg); } diff --git a/lib/librte_acl/rte_acl.h b/lib/librte_acl/rte_acl.h index 652a234..30aea03 100644 --- a/lib/librte_acl/rte_acl.h +++ b/lib/librte_acl/rte_acl.h @@ -94,6 +94,8 @@ struct rte_acl_config { uint32_t num_fields; /**< Number of field definitions. */ struct rte_acl_field_def defs[RTE_ACL_MAX_FIELDS]; /**< array of field definitions. */ + size_t max_size; + /**< max memory limit for internal run-time structures. */ }; /** -- 1.8.5.3