X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_acl%2Facl_bld.c;h=92a85dfb91754aa71c19e29caa67a1e768c5ba95;hb=2f372ab5c90c8e93e04f65d0fbdd34f6997f4de6;hp=22f7934183983cf61b74562441c2c31896430814;hpb=d4132664d80b312a83814368d11d098d04d9e021;p=dpdk.git

diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index 22f7934183..92a85dfb91 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;
@@ -302,8 +302,6 @@ acl_add_ptr(struct acl_build_context *context,
 		/* add room for more pointers */
 		num_ptrs = node->max_ptrs + ACL_PTR_ALLOC;
 		ptrs = acl_build_alloc(context, num_ptrs, sizeof(*ptrs));
-		if (ptrs == NULL)
-			return -ENOMEM;
 
 		/* copy current points to new memory allocation */
 		if (node->ptrs != NULL) {
@@ -477,16 +475,12 @@ acl_dup_node(struct acl_build_context *context, struct rte_acl_node *node)
 	struct rte_acl_node *next;
 
 	next = acl_alloc_node(context, node->level);
-	if (next == NULL)
-		return NULL;
 
 	/* allocate the pointers */
 	if (node->num_ptrs > 0) {
 		next->ptrs = acl_build_alloc(context,
 			node->max_ptrs,
 			sizeof(struct rte_acl_ptr_set));
-		if (next->ptrs == NULL)
-			return NULL;
 		next->max_ptrs = node->max_ptrs;
 	}
 
@@ -669,8 +663,6 @@ acl_merge_intersect(struct acl_build_context *context,
 
 	/* Duplicate A for intersection */
 	node_c = acl_dup_node(context, node_a->ptrs[idx_a].ptr);
-	if (node_c == NULL)
-		return -1;
 
 	/* Remove intersection from A */
 	acl_exclude_ptr(context, node_a, idx_a, intersect_ptr);
@@ -1052,9 +1044,7 @@ acl_merge_trie(struct acl_build_context *context,
 	 * a subtree of the merging tree (node B side). Otherwise,
 	 * just use node A.
 	 */
-	if (level > 0 &&
-			node_a->subtree_id !=
-			(subtree_id | RTE_ACL_SUBTREE_NODE)) {
+	if (level > 0) {
 		node_c = acl_dup_node(context, node_a);
 		node_c->subtree_id = subtree_id | RTE_ACL_SUBTREE_NODE;
 	}
@@ -1328,14 +1318,10 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
 	rule = head;
 
 	trie = acl_alloc_node(context, 0);
-	if (trie == NULL)
-		return NULL;
 
 	while (rule != NULL) {
 
 		root = acl_alloc_node(context, 0);
-		if (root == NULL)
-			return NULL;
 
 		root->ref_count = 1;
 		end = root;
@@ -1419,10 +1405,9 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
 		 * Setup the results for this rule.
 		 * The result and priority of each category.
 		 */
-		if (end->mrt == NULL &&
-				(end->mrt = acl_build_alloc(context, 1,
-				sizeof(*end->mrt))) == NULL)
-			return NULL;
+		if (end->mrt == NULL)
+			end->mrt = acl_build_alloc(context, 1,
+				sizeof(*end->mrt));
 
 		for (m = 0; m < context->cfg.num_categories; m++) {
 			if (rule->f->data.category_mask & (1 << m)) {
@@ -1447,7 +1432,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 +1613,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 +1624,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;
@@ -1719,7 +1708,6 @@ acl_build_tries(struct acl_build_context *context,
 		context->tries[n].type = RTE_ACL_UNUSED_TRIE;
 		context->bld_tries[n].trie = NULL;
 		context->tries[n].count = 0;
-		context->tries[n].smallest = INT32_MAX;
 	}
 
 	context->tries[0].type = RTE_ACL_FULL_TRIE;
@@ -1757,13 +1745,6 @@ acl_build_tries(struct acl_build_context *context,
 
 		/* Create a new copy of config for remaining rules. */
 		config = acl_build_alloc(context, 1, sizeof(*config));
-		if (config == NULL) {
-			RTE_LOG(ERR, ACL,
-				"New config allocation for %u-th "
-				"trie failed\n", num_tries);
-			return -ENOMEM;
-		}
-
 		memcpy(config, rule_sets[n]->config, sizeof(*config));
 
 		/* Make remaining rules use new config. */
@@ -1790,9 +1771,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);
 
@@ -1820,12 +1803,6 @@ acl_build_rules(struct acl_build_context *bcx)
 	sz = ofs + n * fn * sizeof(*wp);
 
 	br = tb_alloc(&bcx->pool, sz);
-	if (br == NULL) {
-		RTE_LOG(ERR, ACL, "ACL context %s: failed to create a copy "
-			"of %u build rules (%zu bytes)\n",
-			bcx->acx->name, n, sz);
-		return -ENOMEM;
-	}
 
 	wp = (uint32_t *)((uintptr_t)br + ofs);
 	num = 0;
@@ -1869,11 +1846,58 @@ 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;
+
+	rc = sigsetjmp(bcx->pool.fail, 0);
+
+	/* build phase runs out of memory. */
+	if (rc != 0) {
+		RTE_LOG(ERR, ACL,
+			"ACL context: %s, %s() failed with error code: %d\n",
+			bcx->acx->name, __func__, rc);
+		return rc;
+	}
+
+	/* 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 ||
@@ -1882,45 +1906,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]),
-				bcx.num_build_rules + 1);
-		if (rc == 0) {
-
-			/* set data indexes. */
-			acl_set_data_indexes(ctx);
+				sizeof(ctx->data_indexes[0]), max_size);
+			if (rc == 0) {
+				/* 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;
 }