X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;ds=sidebyside;f=lib%2Flibrte_acl%2Facl_bld.c;h=d1f920b09ceb2d22280d8a3549f7702f4d41338c;hb=f74904ce98e84f48e8f3a96b7ad6b6347c3f44b6;hp=d6e0c45108f69dfd7fc807fc19f175f3b21cd712;hpb=7eef9194ab6f3b743061ffa2597ad39f27880bf8;p=dpdk.git

diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index d6e0c45108..d1f920b09c 100644
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -1,34 +1,5 @@
-/*-
- *   BSD LICENSE
- *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
- *   All rights reserved.
- *
- *   Redistribution and use in source and binary forms, with or without
- *   modification, are permitted provided that the following conditions
- *   are met:
- *
- *     * Redistributions of source code must retain the above copyright
- *       notice, this list of conditions and the following disclaimer.
- *     * Redistributions in binary form must reproduce the above copyright
- *       notice, this list of conditions and the following disclaimer in
- *       the documentation and/or other materials provided with the
- *       distribution.
- *     * Neither the name of Intel Corporation nor the names of its
- *       contributors may be used to endorse or promote products derived
- *       from this software without specific prior written permission.
- *
- *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2010-2014 Intel Corporation
  */
 
 #include <rte_acl.h>
@@ -41,10 +12,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 +67,8 @@ 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;
+	int32_t                   cur_node_max;
 	uint32_t                  node;
 	uint32_t                  num_nodes;
 	uint32_t                  category_mask;
@@ -117,11 +89,7 @@ struct acl_build_context {
 
 static int acl_merge_trie(struct acl_build_context *context,
 	struct rte_acl_node *node_a, struct rte_acl_node *node_b,
-	uint32_t level, uint32_t subtree_id, struct rte_acl_node **node_c);
-
-static int acl_merge(struct acl_build_context *context,
-	struct rte_acl_node *node_a, struct rte_acl_node *node_b,
-	int move, int a_subset, int level);
+	uint32_t level, struct rte_acl_node **node_c);
 
 static void
 acl_deref_ptr(struct acl_build_context *context,
@@ -302,8 +270,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) {
@@ -354,7 +320,7 @@ acl_add_ptr_range(struct acl_build_context *context,
 	for (n = 0; n < UINT8_MAX + 1; n++)
 		if (n >= low && n <= high)
 			bitset.bits[n / (sizeof(bits_t) * 8)] |=
-				1 << (n % (sizeof(bits_t) * 8));
+				1U << (n % (sizeof(bits_t) * CHAR_BIT));
 
 	return acl_add_ptr(context, root, node, &bitset);
 }
@@ -377,7 +343,7 @@ acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
 		if ((n & mask) == value) {
 			range++;
 			bitset->bits[n / (sizeof(bits_t) * 8)] |=
-				1 << (n % (sizeof(bits_t) * 8));
+				1U << (n % (sizeof(bits_t) * CHAR_BIT));
 		}
 	}
 	return range;
@@ -388,8 +354,8 @@ acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
  * Determine if A and/or B are supersets of the intersection.
  */
 static int
-acl_intersect_type(struct rte_acl_bitset *a_bits,
-	struct rte_acl_bitset *b_bits,
+acl_intersect_type(const struct rte_acl_bitset *a_bits,
+	const struct rte_acl_bitset *b_bits,
 	struct rte_acl_bitset *intersect)
 {
 	uint32_t n;
@@ -415,58 +381,6 @@ acl_intersect_type(struct rte_acl_bitset *a_bits,
 	return n;
 }
 
-/*
- * Check if all bits in the bitset are on
- */
-static int
-acl_full(struct rte_acl_node *node)
-{
-	uint32_t n;
-	bits_t all_bits = -1;
-
-	for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
-		all_bits &= node->values.bits[n];
-	return all_bits == -1;
-}
-
-/*
- * Check if all bits in the bitset are off
- */
-static int
-acl_empty(struct rte_acl_node *node)
-{
-	uint32_t n;
-
-	if (node->ref_count == 0) {
-		for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
-			if (0 != node->values.bits[n])
-				return 0;
-		}
-		return 1;
-	} else {
-		return 0;
-	}
-}
-
-/*
- * Compute intersection of A and B
- * return 1 if there is an intersection else 0.
- */
-static int
-acl_intersect(struct rte_acl_bitset *a_bits,
-	struct rte_acl_bitset *b_bits,
-	struct rte_acl_bitset *intersect)
-{
-	uint32_t n;
-	bits_t all_bits = 0;
-
-	for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
-		intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
-		all_bits |= intersect->bits[n];
-	}
-	return all_bits != 0;
-}
-
 /*
  * Duplicate a node
  */
@@ -477,16 +391,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;
 	}
 
@@ -538,63 +448,6 @@ acl_deref_ptr(struct acl_build_context *context,
 	}
 }
 
-/*
- * Exclude bitset from a node pointer
- * returns  0 if poiter was deref'd
- *          1 otherwise.
- */
-static int
-acl_exclude_ptr(struct acl_build_context *context,
-	struct rte_acl_node *node,
-	int index,
-	struct rte_acl_bitset *b_bits)
-{
-	int retval = 1;
-
-	/*
-	 * remove bitset from node pointer and deref
-	 * if the bitset becomes empty.
-	 */
-	if (!acl_exclude(&node->ptrs[index].values,
-			&node->ptrs[index].values,
-			b_bits)) {
-		acl_deref_ptr(context, node, index);
-		node->ptrs[index].ptr = NULL;
-		retval = 0;
-	}
-
-	/* exclude bits from the composite bits for the node */
-	acl_exclude(&node->values, &node->values, b_bits);
-	return retval;
-}
-
-/*
- * Remove a bitset from src ptr and move remaining ptr to dst
- */
-static int
-acl_move_ptr(struct acl_build_context *context,
-	struct rte_acl_node *dst,
-	struct rte_acl_node *src,
-	int index,
-	struct rte_acl_bitset *b_bits)
-{
-	int rc;
-
-	if (b_bits != NULL)
-		if (!acl_exclude_ptr(context, src, index, b_bits))
-			return 0;
-
-	/* add src pointer to dst node */
-	rc = acl_add_ptr(context, dst, src->ptrs[index].ptr,
-			&src->ptrs[index].values);
-	if (rc < 0)
-		return rc;
-
-	/* remove ptr from src */
-	acl_exclude_ptr(context, src, index, &src->ptrs[index].values);
-	return 1;
-}
-
 /*
  * acl_exclude rte_acl_bitset from src and copy remaining pointer to dst
  */
@@ -655,205 +508,6 @@ acl_compact_node_ptrs(struct rte_acl_node *node_a)
 	}
 }
 
-/*
- * acl_merge helper routine.
- */
-static int
-acl_merge_intersect(struct acl_build_context *context,
-	struct rte_acl_node *node_a, uint32_t idx_a,
-	struct rte_acl_node *node_b, uint32_t idx_b,
-	int next_move, int level,
-	struct rte_acl_bitset *intersect_ptr)
-{
-	struct rte_acl_node *node_c;
-
-	/* 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);
-
-	/*
-	 * Added link from A to C for all transitions
-	 * in the intersection
-	 */
-	if (acl_add_ptr(context, node_a, node_c, intersect_ptr) < 0)
-		return -1;
-
-	/* merge B->node into C */
-	return acl_merge(context, node_c, node_b->ptrs[idx_b].ptr, next_move,
-		0, level + 1);
-}
-
-
-/*
- * Merge the children of nodes A and B together.
- *
- * if match node
- *	For each category
- *		node A result = highest priority result
- * if any pointers in A intersect with any in B
- *	For each intersection
- *		C = copy of node that A points to
- *		remove intersection from A pointer
- *		add a pointer to A that points to C for the intersection
- *		Merge C and node that B points to
- * Compact the pointers in A and B
- * if move flag
- *	If B has only one reference
- *		Move B pointers to A
- *	else
- *		Copy B pointers to A
- */
-static int
-acl_merge(struct acl_build_context *context,
-	struct rte_acl_node *node_a, struct rte_acl_node *node_b,
-	int move, int a_subset, int level)
-{
-	uint32_t n, m, ptrs_a, ptrs_b;
-	uint32_t min_add_a, min_add_b;
-	int intersect_type;
-	int node_intersect_type;
-	int b_full, next_move, rc;
-	struct rte_acl_bitset intersect_values;
-	struct rte_acl_bitset intersect_ptr;
-
-	min_add_a = 0;
-	min_add_b = 0;
-	intersect_type = 0;
-	node_intersect_type = 0;
-
-	if (level == 0)
-		a_subset = 1;
-
-	/*
-	 *  Resolve match priorities
-	 */
-	if (node_a->match_flag != 0 || node_b->match_flag != 0) {
-
-		if (node_a->match_flag == 0 || node_b->match_flag == 0)
-			RTE_LOG(ERR, ACL, "Not both matches\n");
-
-		if (node_b->match_flag < node_a->match_flag)
-			RTE_LOG(ERR, ACL, "Not same match\n");
-
-		for (n = 0; n < context->cfg.num_categories; n++) {
-			if (node_a->mrt->priority[n] <
-					node_b->mrt->priority[n]) {
-				node_a->mrt->priority[n] =
-					node_b->mrt->priority[n];
-				node_a->mrt->results[n] =
-					node_b->mrt->results[n];
-			}
-		}
-	}
-
-	/*
-	 * If the two node transitions intersect then merge the transitions.
-	 * Check intersection for entire node (all pointers)
-	 */
-	node_intersect_type = acl_intersect_type(&node_a->values,
-		&node_b->values,
-		&intersect_values);
-
-	if (node_intersect_type & ACL_INTERSECT) {
-
-		b_full = acl_full(node_b);
-
-		min_add_b = node_b->min_add;
-		node_b->min_add = node_b->num_ptrs;
-		ptrs_b = node_b->num_ptrs;
-
-		min_add_a = node_a->min_add;
-		node_a->min_add = node_a->num_ptrs;
-		ptrs_a = node_a->num_ptrs;
-
-		for (n = 0; n < ptrs_a; n++) {
-			for (m = 0; m < ptrs_b; m++) {
-
-				if (node_a->ptrs[n].ptr == NULL ||
-						node_b->ptrs[m].ptr == NULL ||
-						node_a->ptrs[n].ptr ==
-						node_b->ptrs[m].ptr)
-						continue;
-
-				intersect_type = acl_intersect_type(
-					&node_a->ptrs[n].values,
-					&node_b->ptrs[m].values,
-					&intersect_ptr);
-
-				/* If this node is not a 'match' node */
-				if ((intersect_type & ACL_INTERSECT) &&
-					(context->cfg.num_categories != 1 ||
-					!(node_a->ptrs[n].ptr->match_flag))) {
-
-					/*
-					 * next merge is a 'move' pointer,
-					 * if this one is and B is a
-					 * subset of the intersection.
-					 */
-					next_move = move &&
-						(intersect_type &
-						ACL_INTERSECT_B) == 0;
-
-					if (a_subset && b_full) {
-						rc = acl_merge(context,
-							node_a->ptrs[n].ptr,
-							node_b->ptrs[m].ptr,
-							next_move,
-							1, level + 1);
-						if (rc != 0)
-							return rc;
-					} else {
-						rc = acl_merge_intersect(
-							context, node_a, n,
-							node_b, m, next_move,
-							level, &intersect_ptr);
-						if (rc != 0)
-							return rc;
-					}
-				}
-			}
-		}
-	}
-
-	/* Compact pointers */
-	node_a->min_add = min_add_a;
-	acl_compact_node_ptrs(node_a);
-	node_b->min_add = min_add_b;
-	acl_compact_node_ptrs(node_b);
-
-	/*
-	 *  Either COPY or MOVE pointers from B to A
-	 */
-	acl_intersect(&node_a->values, &node_b->values, &intersect_values);
-
-	if (move && node_b->ref_count == 1) {
-		for (m = 0; m < node_b->num_ptrs; m++) {
-			if (node_b->ptrs[m].ptr != NULL &&
-					acl_move_ptr(context, node_a, node_b, m,
-					&intersect_values) < 0)
-				return -1;
-		}
-	} else {
-		for (m = 0; m < node_b->num_ptrs; m++) {
-			if (node_b->ptrs[m].ptr != NULL &&
-					acl_copy_ptr(context, node_a, node_b, m,
-					&intersect_values) < 0)
-				return -1;
-		}
-	}
-
-	/*
-	 *  Free node if its empty (no longer used)
-	 */
-	if (acl_empty(node_b))
-		acl_free_node(context, node_b);
-	return 0;
-}
-
 static int
 acl_resolve_leaf(struct acl_build_context *context,
 	struct rte_acl_node *node_a,
@@ -908,94 +562,6 @@ acl_resolve_leaf(struct acl_build_context *context,
 	return 0;
 }
 
-/*
-* Within the existing trie structure, determine which nodes are
-* part of the subtree of the trie to be merged.
-*
-* For these purposes, a subtree is defined as the set of nodes that
-* are 1) not a superset of the intersection with the same level of
-* the merging tree, and 2) do not have any references from a node
-* outside of the subtree.
-*/
-static void
-mark_subtree(struct rte_acl_node *node,
-	struct rte_acl_bitset *level_bits,
-	uint32_t level,
-	uint32_t id)
-{
-	uint32_t n;
-
-	/* mark this node as part of the subtree */
-	node->subtree_id = id | RTE_ACL_SUBTREE_NODE;
-
-	for (n = 0; n < node->num_ptrs; n++) {
-
-		if (node->ptrs[n].ptr != NULL) {
-
-			struct rte_acl_bitset intersect_bits;
-			int intersect;
-
-			/*
-			* Item 1) :
-			* check if this child pointer is not a superset of the
-			* same level of the merging tree.
-			*/
-			intersect = acl_intersect_type(&node->ptrs[n].values,
-				&level_bits[level],
-				&intersect_bits);
-
-			if ((intersect & ACL_INTERSECT_A) == 0) {
-
-				struct rte_acl_node *child = node->ptrs[n].ptr;
-
-				/*
-				 * reset subtree reference if this is
-				 * the first visit by this subtree.
-				 */
-				if (child->subtree_id != id) {
-					child->subtree_id = id;
-					child->subtree_ref_count = 0;
-				}
-
-				/*
-				* Item 2) :
-				* increment the subtree reference count and if
-				* all references are from this subtree then
-				* recurse to that child
-				*/
-				child->subtree_ref_count++;
-				if (child->subtree_ref_count ==
-						child->ref_count)
-					mark_subtree(child, level_bits,
-						level + 1, id);
-			}
-		}
-	}
-}
-
-/*
- * Build the set of bits that define the set of transitions
- * for each level of a trie.
- */
-static void
-build_subset_mask(struct rte_acl_node *node,
-	struct rte_acl_bitset *level_bits,
-	int level)
-{
-	uint32_t n;
-
-	/* Add this node's transitions to the set for this level */
-	for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
-		level_bits[level].bits[n] &= node->values.bits[n];
-
-	/* For each child, add the transitions for the next level */
-	for (n = 0; n < node->num_ptrs; n++)
-		if (node->ptrs[n].ptr != NULL)
-			build_subset_mask(node->ptrs[n].ptr, level_bits,
-				level + 1);
-}
-
-
 /*
  * Merge nodes A and B together,
  *   returns a node that is the path for the intersection
@@ -1022,7 +588,7 @@ build_subset_mask(struct rte_acl_node *node,
 static int
 acl_merge_trie(struct acl_build_context *context,
 	struct rte_acl_node *node_a, struct rte_acl_node *node_b,
-	uint32_t level, uint32_t subtree_id, struct rte_acl_node **return_c)
+	uint32_t level, struct rte_acl_node **return_c)
 {
 	uint32_t n, m, ptrs_c, ptrs_b;
 	uint32_t min_add_c, min_add_b;
@@ -1048,16 +614,12 @@ acl_merge_trie(struct acl_build_context *context,
 	}
 
 	/*
-	 * Create node C as a copy of node A if node A is not part of
-	 * a subtree of the merging tree (node B side). Otherwise,
-	 * just use node A.
+	 * Create node C as a copy of node A, and do: C = merge(A,B);
+	 * If node A can be used instead (A==C), then later we'll
+	 * destroy C and return 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;
-	}
 
 	/*
 	 * If the two node transitions intersect then merge the transitions.
@@ -1104,7 +666,7 @@ acl_merge_trie(struct acl_build_context *context,
 					if (acl_merge_trie(context,
 							node_c->ptrs[n].ptr,
 							node_b->ptrs[m].ptr,
-							level + 1, subtree_id,
+							level + 1,
 							&child_node_c))
 						return 1;
 
@@ -1216,9 +778,8 @@ acl_build_reset(struct rte_acl_ctx *ctx)
 }
 
 static void
-acl_gen_range(struct acl_build_context *context,
-	const uint8_t *hi, const uint8_t *lo, int size, int level,
-	struct rte_acl_node *root, struct rte_acl_node *end)
+acl_gen_full_range(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, int size, int level)
 {
 	struct rte_acl_node *node, *prev;
 	uint32_t n;
@@ -1226,10 +787,71 @@ acl_gen_range(struct acl_build_context *context,
 	prev = root;
 	for (n = size - 1; n > 0; n--) {
 		node = acl_alloc_node(context, level++);
-		acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+		acl_add_ptr_range(context, prev, node, 0, UINT8_MAX);
 		prev = node;
 	}
-	acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
+	acl_add_ptr_range(context, prev, end, 0, UINT8_MAX);
+}
+
+static void
+acl_gen_range_mdl(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, uint8_t lo, uint8_t hi, int size, int level)
+{
+	struct rte_acl_node *node;
+
+	node = acl_alloc_node(context, level++);
+	acl_add_ptr_range(context, root, node, lo, hi);
+	acl_gen_full_range(context, node, end, size - 1, level);
+}
+
+static void
+acl_gen_range_low(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, const uint8_t *lo, int size, int level)
+{
+	struct rte_acl_node *node;
+	uint32_t n;
+
+	n = size - 1;
+	if (n == 0) {
+		acl_add_ptr_range(context, root, end, lo[0], UINT8_MAX);
+		return;
+	}
+
+	node = acl_alloc_node(context, level++);
+	acl_add_ptr_range(context, root, node, lo[n], lo[n]);
+
+	/* generate lower-bound sub-trie */
+	acl_gen_range_low(context, node, end, lo, n, level);
+
+	/* generate middle sub-trie */
+	if (n > 1 && lo[n - 1] != UINT8_MAX)
+		acl_gen_range_mdl(context, node, end, lo[n - 1] + 1, UINT8_MAX,
+			n, level);
+}
+
+static void
+acl_gen_range_high(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, const uint8_t *hi, int size, int level)
+{
+	struct rte_acl_node *node;
+	uint32_t n;
+
+	n = size - 1;
+	if (n == 0) {
+		acl_add_ptr_range(context, root, end, 0, hi[0]);
+		return;
+	}
+
+	node = acl_alloc_node(context, level++);
+	acl_add_ptr_range(context, root, node, hi[n], hi[n]);
+
+	/* generate upper-bound sub-trie */
+	acl_gen_range_high(context, node, end, hi, n, level);
+
+	/* generate middle sub-trie */
+	if (n > 1 && hi[n - 1] != 0)
+		acl_gen_range_mdl(context, node, end, 0, hi[n - 1] - 1,
+			n, level);
 }
 
 static struct rte_acl_node *
@@ -1237,52 +859,56 @@ acl_gen_range_trie(struct acl_build_context *context,
 	const void *min, const void *max,
 	int size, int level, struct rte_acl_node **pend)
 {
-	int32_t n;
-	struct rte_acl_node *root;
-	const uint8_t *lo = (const uint8_t *)min;
-	const uint8_t *hi = (const uint8_t *)max;
+	int32_t k, n;
+	uint8_t hi_ff, lo_00;
+	struct rte_acl_node *node, *prev, *root;
+	const uint8_t *lo;
+	const uint8_t *hi;
+
+	lo = min;
+	hi = max;
 
-	*pend = acl_alloc_node(context, level+size);
+	*pend = acl_alloc_node(context, level + size);
 	root = acl_alloc_node(context, level++);
+	prev = root;
 
-	if (lo[size - 1] == hi[size - 1]) {
-		acl_gen_range(context, hi, lo, size, level, root, *pend);
-	} else {
-		uint8_t limit_lo[64];
-		uint8_t limit_hi[64];
-		uint8_t hi_ff = UINT8_MAX;
-		uint8_t lo_00 = 0;
+	/* build common sub-trie till possible */
+	for (n = size - 1; n > 0 && lo[n] == hi[n]; n--) {
+		node = acl_alloc_node(context, level++);
+		acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+		prev = node;
+	}
 
-		memset(limit_lo, 0, RTE_DIM(limit_lo));
-		memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi));
+	/* no branch needed, just one sub-trie */
+	if (n == 0) {
+		acl_add_ptr_range(context, prev, *pend, lo[0], hi[0]);
+		return root;
+	}
 
-		for (n = size - 2; n >= 0; n--) {
-			hi_ff = (uint8_t)(hi_ff & hi[n]);
-			lo_00 = (uint8_t)(lo_00 | lo[n]);
-		}
+	/* gather information about divirgent paths */
+	lo_00 = 0;
+	hi_ff = UINT8_MAX;
+	for (k = n - 1; k >= 0; k--) {
+		hi_ff &= hi[k];
+		lo_00 |= lo[k];
+	}
 
-		if (hi_ff != UINT8_MAX) {
-			limit_lo[size - 1] = hi[size - 1];
-			acl_gen_range(context, hi, limit_lo, size, level,
-				root, *pend);
-		}
+	/* generate left (lower-bound) sub-trie */
+	if (lo_00 != 0)
+		acl_gen_range_low(context, prev, *pend, lo, n + 1, level);
 
-		if (lo_00 != 0) {
-			limit_hi[size - 1] = lo[size - 1];
-			acl_gen_range(context, limit_hi, lo, size, level,
-				root, *pend);
-		}
+	/* generate right (upper-bound) sub-trie */
+	if (hi_ff != UINT8_MAX)
+		acl_gen_range_high(context, prev, *pend, hi, n + 1, level);
 
-		if (hi[size - 1] - lo[size - 1] > 1 ||
-				lo_00 == 0 ||
-				hi_ff == UINT8_MAX) {
-			limit_lo[size-1] = (uint8_t)(lo[size-1] + (lo_00 != 0));
-			limit_hi[size-1] = (uint8_t)(hi[size-1] -
-				(hi_ff != UINT8_MAX));
-			acl_gen_range(context, limit_hi, limit_lo, size,
-				level, root, *pend);
-		}
+	/* generate sub-trie in the middle */
+	if (lo[n] + 1 != hi[n] || lo_00 == 0 || hi_ff == UINT8_MAX) {
+		lo_00 = lo[n] + (lo_00 != 0);
+		hi_ff = hi[n] - (hi_ff != UINT8_MAX);
+		acl_gen_range_mdl(context, prev, *pend, lo_00, hi_ff,
+			n + 1, level);
 	}
+
 	return root;
 }
 
@@ -1295,8 +921,8 @@ acl_gen_mask_trie(struct acl_build_context *context,
 	struct rte_acl_node *root;
 	struct rte_acl_node *node, *prev;
 	struct rte_acl_bitset bits;
-	const uint8_t *val = (const uint8_t *)value;
-	const uint8_t *msk = (const uint8_t *)mask;
+	const uint8_t *val = value;
+	const uint8_t *msk = mask;
 
 	root = acl_alloc_node(context, level++);
 	prev = root;
@@ -1322,20 +948,16 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
 	struct rte_acl_build_rule *prev, *rule;
 	struct rte_acl_node *end, *merge, *root, *end_prev;
 	const struct rte_acl_field *fld;
-	struct rte_acl_bitset level_bits[RTE_ACL_MAX_LEVELS];
 
 	prev = head;
 	rule = head;
+	*last = prev;
 
 	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;
@@ -1365,19 +987,9 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
 				 * all higher bits.
 				 */
 				uint64_t mask;
-
-				if (fld->mask_range.u32 == 0) {
-					mask = 0;
-
-				/*
-				 * arithmetic right shift for the length of
-				 * the mask less the msb.
-				 */
-				} else {
-					mask = -1 <<
-						(rule->config->defs[n].size *
-						CHAR_BIT - fld->mask_range.u32);
-				}
+				mask = RTE_ACL_MASKLEN_TO_BITMASK(
+					fld->mask_range.u32,
+					rule->config->defs[n].size);
 
 				/* gen a mini-trie for this field */
 				merge = acl_gen_mask_trie(context,
@@ -1408,7 +1020,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
 
 			/* merge this field on to the end of the rule */
 			if (acl_merge_trie(context, end_prev, merge, 0,
-					0, NULL) != 0) {
+					NULL) != 0) {
 				return NULL;
 			}
 		}
@@ -1419,13 +1031,12 @@ 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)) {
+		for (m = context->cfg.num_categories; 0 != m--; ) {
+			if (rule->f->data.category_mask & (1U << m)) {
 				end->mrt->results[m] = rule->f->data.userdata;
 				end->mrt->priority[m] = rule->f->data.priority;
 			} else {
@@ -1435,19 +1046,14 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
 		}
 
 		node_count = context->num_nodes;
-
-		memset(&level_bits[0], UINT8_MAX, sizeof(level_bits));
-		build_subset_mask(root, &level_bits[0], 0);
-		mark_subtree(trie, &level_bits[0], 0, end->match_flag);
 		(*count)++;
 
 		/* merge this rule into the trie */
-		if (acl_merge_trie(context, trie, root, 0, end->match_flag,
-			NULL))
+		if (acl_merge_trie(context, trie, root, 0, NULL))
 			return NULL;
 
 		node_count = context->num_nodes - node_count;
-		if (node_count > NODE_MAX) {
+		if (node_count > context->cur_node_max) {
 			*last = prev;
 			return trie;
 		}
@@ -1460,7 +1066,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
 	return trie;
 }
 
-static int
+static void
 acl_calc_wildness(struct rte_acl_build_rule *head,
 	const struct rte_acl_config *config)
 {
@@ -1472,15 +1078,18 @@ acl_calc_wildness(struct rte_acl_build_rule *head,
 		for (n = 0; n < config->num_fields; n++) {
 
 			double wild = 0;
-			double size = CHAR_BIT * config->defs[n].size;
+			uint32_t bit_len = CHAR_BIT * config->defs[n].size;
+			uint64_t msk_val = RTE_LEN2MASK(bit_len,
+				typeof(msk_val));
+			double size = bit_len;
 			int field_index = config->defs[n].field_index;
 			const struct rte_acl_field *fld = rule->f->field +
 				field_index;
 
 			switch (rule->config->defs[n].type) {
 			case RTE_ACL_FIELD_TYPE_BITMASK:
-				wild = (size - __builtin_popcount(
-					fld->mask_range.u8)) /
+				wild = (size - __builtin_popcountll(
+					fld->mask_range.u64 & msk_val)) /
 					size;
 				break;
 
@@ -1489,61 +1098,20 @@ acl_calc_wildness(struct rte_acl_build_rule *head,
 				break;
 
 			case RTE_ACL_FIELD_TYPE_RANGE:
-				switch (rule->config->defs[n].size) {
-				case sizeof(uint8_t):
-					wild = ((double)fld->mask_range.u8 -
-						fld->value.u8) / UINT8_MAX;
-					break;
-				case sizeof(uint16_t):
-					wild = ((double)fld->mask_range.u16 -
-						fld->value.u16) / UINT16_MAX;
-					break;
-				case sizeof(uint32_t):
-					wild = ((double)fld->mask_range.u32 -
-						fld->value.u32) / UINT32_MAX;
-					break;
-				case sizeof(uint64_t):
-					wild = ((double)fld->mask_range.u64 -
-						fld->value.u64) / UINT64_MAX;
-					break;
-				default:
-					RTE_LOG(ERR, ACL,
-						"%s(rule: %u) invalid %u-th "
-						"field, type: %hhu, "
-						"unknown size: %hhu\n",
-						__func__,
-						rule->f->data.userdata,
-						n,
-						rule->config->defs[n].type,
-						rule->config->defs[n].size);
-					return -EINVAL;
-				}
+				wild = (fld->mask_range.u64 & msk_val) -
+					(fld->value.u64 & msk_val);
+				wild = wild / msk_val;
 				break;
-
-			default:
-				RTE_LOG(ERR, ACL,
-					"%s(rule: %u) invalid %u-th "
-					"field, unknown type: %hhu\n",
-					__func__,
-					rule->f->data.userdata,
-					n,
-					rule->config->defs[n].type);
-					return -EINVAL;
-
 			}
 
 			rule->wildness[field_index] = (uint32_t)(wild * 100);
 		}
 	}
-
-	return 0;
 }
 
-static int
-acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config,
-	uint32_t *wild_limit)
+static void
+acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config)
 {
-	int min;
 	struct rte_acl_build_rule *rule;
 	uint32_t n, m, fields_deactivated = 0;
 	uint32_t start = 0, deactivate = 0;
@@ -1604,129 +1172,120 @@ acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config,
 
 		for (k = 0; k < config->num_fields; k++) {
 			if (tally[k][TALLY_DEACTIVATED] == 0) {
-				memcpy(&tally[l][0], &tally[k][0],
+				memmove(&tally[l][0], &tally[k][0],
 					TALLY_NUM * sizeof(tally[0][0]));
-				memcpy(&config->defs[l++],
+				memmove(&config->defs[l++],
 					&config->defs[k],
 					sizeof(struct rte_acl_field_def));
 			}
 		}
 		config->num_fields = l;
 	}
-
-	min = RTE_ACL_SINGLE_TRIE_SIZE;
-	if (config->num_fields == 2)
-		min *= 4;
-	else if (config->num_fields == 3)
-		min *= 3;
-	else if (config->num_fields == 4)
-		min *= 2;
-
-	if (tally[0][TALLY_0] < min)
-		return 0;
-	for (n = 0; n < config->num_fields; n++)
-		wild_limit[n] = 0;
-
-	/*
-	 * If trailing fields are 100% wild, group those together.
-	 * This allows the search length of the trie to be shortened.
-	 */
-	for (n = 1; n < config->num_fields; n++) {
-
-		double rule_percentage = (double)tally[n][TALLY_DEPTH] /
-			tally[n][0];
-
-		if (rule_percentage > RULE_PERCENTAGE) {
-			/* if it crosses an input boundary then round up */
-			while (config->defs[n - 1].input_index ==
-					config->defs[n].input_index)
-				n++;
-
-			/* set the limit for selecting rules */
-			while (n < config->num_fields)
-				wild_limit[n++] = 100;
-
-			if (wild_limit[n - 1] == 100)
-				return 1;
-		}
-	}
-
-	/* look for the most wild that's 40% or more of the rules */
-	for (n = 1; n < config->num_fields; n++) {
-		for (m = TALLY_100; m > 0; m--) {
-
-			double rule_percentage = (double)tally[n][m] /
-				tally[n][0];
-
-			if (tally[n][TALLY_DEACTIVATED] == 0 &&
-					tally[n][TALLY_0] >
-					RTE_ACL_SINGLE_TRIE_SIZE &&
-					rule_percentage > NODE_PERCENTAGE &&
-					rule_percentage < 0.80) {
-				wild_limit[n] = wild_limits[m];
-				return 1;
-			}
-		}
-	}
-	return 0;
 }
 
 static int
-order(struct rte_acl_build_rule **insert, struct rte_acl_build_rule *rule)
+rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2)
 {
 	uint32_t n;
-	struct rte_acl_build_rule *left = *insert;
-
-	if (left == NULL)
-		return 0;
 
-	for (n = 1; n < left->config->num_fields; n++) {
-		int field_index = left->config->defs[n].field_index;
+	for (n = 1; n < r1->config->num_fields; n++) {
+		int field_index = r1->config->defs[n].field_index;
 
-		if (left->wildness[field_index] != rule->wildness[field_index])
-			return (left->wildness[field_index] >=
-				rule->wildness[field_index]);
+		if (r1->wildness[field_index] != r2->wildness[field_index])
+			return r1->wildness[field_index] -
+				r2->wildness[field_index];
 	}
 	return 0;
 }
 
-static struct rte_acl_build_rule *
-ordered_insert_rule(struct rte_acl_build_rule *head,
-	struct rte_acl_build_rule *rule)
+/*
+ * Split the rte_acl_build_rule list into two lists.
+ */
+static void
+rule_list_split(struct rte_acl_build_rule *source,
+	struct rte_acl_build_rule **list_a,
+	struct rte_acl_build_rule **list_b)
 {
-	struct rte_acl_build_rule **insert;
-
-	if (rule == NULL)
-		return head;
+	struct rte_acl_build_rule *fast;
+	struct rte_acl_build_rule *slow;
 
-	rule->next = head;
-	if (head == NULL)
-		return rule;
+	if (source == NULL || source->next == NULL) {
+		/* length < 2 cases */
+		*list_a = source;
+		*list_b = NULL;
+	} else {
+		slow = source;
+		fast = source->next;
+		/* Advance 'fast' two nodes, and advance 'slow' one node */
+		while (fast != NULL) {
+			fast = fast->next;
+			if (fast != NULL) {
+				slow = slow->next;
+				fast = fast->next;
+			}
+		}
+		/* 'slow' is before the midpoint in the list, so split it in two
+		   at that point. */
+		*list_a = source;
+		*list_b = slow->next;
+		slow->next = NULL;
+	}
+}
 
-	insert = &head;
-	while (order(insert, rule))
-		insert = &(*insert)->next;
+/*
+ * Merge two sorted lists.
+ */
+static struct rte_acl_build_rule *
+rule_list_sorted_merge(struct rte_acl_build_rule *a,
+	struct rte_acl_build_rule *b)
+{
+	struct rte_acl_build_rule *result = NULL;
+	struct rte_acl_build_rule **last_next = &result;
 
-	rule->next = *insert;
-	*insert = rule;
-	return head;
+	while (1) {
+		if (a == NULL) {
+			*last_next = b;
+			break;
+		} else if (b == NULL) {
+			*last_next = a;
+			break;
+		}
+		if (rule_cmp_wildness(a, b) >= 0) {
+			*last_next = a;
+			last_next = &a->next;
+			a = a->next;
+		} else {
+			*last_next = b;
+			last_next = &b->next;
+			b = b->next;
+		}
+	}
+	return result;
 }
 
+/*
+ * Sort list of rules based on the rules wildness.
+ * Use recursive mergesort algorithm.
+ */
 static struct rte_acl_build_rule *
 sort_rules(struct rte_acl_build_rule *head)
 {
-	struct rte_acl_build_rule *rule, *reordered_head = NULL;
-	struct rte_acl_build_rule *last_rule = NULL;
+	struct rte_acl_build_rule *a;
+	struct rte_acl_build_rule *b;
 
-	for (rule = head; rule != NULL; rule = rule->next) {
-		reordered_head = ordered_insert_rule(reordered_head, last_rule);
-		last_rule = rule;
-	}
+	/* Base case -- length 0 or 1 */
+	if (head == NULL || head->next == NULL)
+		return head;
+
+	/* Split head into 'a' and 'b' sublists */
+	rule_list_split(head, &a, &b);
 
-	if (last_rule != reordered_head)
-		reordered_head = ordered_insert_rule(reordered_head, last_rule);
+	/* Recursively sort the sublists */
+	a = sort_rules(a);
+	b = sort_rules(b);
 
-	return reordered_head;
+	/* answer = merge the two sorted lists together */
+	return rule_list_sorted_merge(a, b);
 }
 
 static uint32_t
@@ -1748,122 +1307,103 @@ acl_build_index(const struct rte_acl_config *config, uint32_t *data_index)
 	return m;
 }
 
+static struct rte_acl_build_rule *
+build_one_trie(struct acl_build_context *context,
+	struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],
+	uint32_t n, int32_t node_max)
+{
+	struct rte_acl_build_rule *last;
+	struct rte_acl_config *config;
+
+	config = rule_sets[n]->config;
+
+	acl_rule_stats(rule_sets[n], config);
+	rule_sets[n] = sort_rules(rule_sets[n]);
+
+	context->tries[n].type = RTE_ACL_FULL_TRIE;
+	context->tries[n].count = 0;
+
+	context->tries[n].num_data_indexes = acl_build_index(config,
+		context->data_indexes[n]);
+	context->tries[n].data_index = context->data_indexes[n];
+
+	context->cur_node_max = node_max;
+
+	context->bld_tries[n].trie = build_trie(context, rule_sets[n],
+		&last, &context->tries[n].count);
+
+	return last;
+}
+
 static int
 acl_build_tries(struct acl_build_context *context,
 	struct rte_acl_build_rule *head)
 {
-	int32_t rc;
-	uint32_t n, m, num_tries;
+	uint32_t n, num_tries;
 	struct rte_acl_config *config;
-	struct rte_acl_build_rule *last, *rule;
-	uint32_t wild_limit[RTE_ACL_MAX_LEVELS];
+	struct rte_acl_build_rule *last;
 	struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES];
 
 	config = head->config;
-	rule = head;
 	rule_sets[0] = head;
-	num_tries = 1;
 
 	/* initialize tries */
 	for (n = 0; n < RTE_DIM(context->tries); n++) {
 		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;
 
 	/* calc wildness of each field of each rule */
-	rc = acl_calc_wildness(head, config);
-	if (rc != 0)
-		return rc;
+	acl_calc_wildness(head, config);
 
-	n = acl_rule_stats(head, config, &wild_limit[0]);
+	for (n = 0;; n = num_tries) {
 
-	/* put all rules that fit the wildness criteria into a seperate trie */
-	while (n > 0 && num_tries < RTE_ACL_MAX_TRIES) {
+		num_tries = n + 1;
 
-		struct rte_acl_config *new_config;
-		struct rte_acl_build_rule **prev = &rule_sets[num_tries - 1];
-		struct rte_acl_build_rule *next = head->next;
-
-		new_config = acl_build_alloc(context, 1, sizeof(*new_config));
-		if (new_config == NULL) {
-			RTE_LOG(ERR, ACL,
-				"Failed to get space for new config\n");
+		last = build_one_trie(context, rule_sets, n, context->node_max);
+		if (context->bld_tries[n].trie == NULL) {
+			RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
 			return -ENOMEM;
 		}
 
-		memcpy(new_config, config, sizeof(*new_config));
-		config = new_config;
-		rule_sets[num_tries] = NULL;
-
-		for (rule = head; rule != NULL; rule = next) {
-
-			int move = 1;
-
-			next = rule->next;
-			for (m = 0; m < config->num_fields; m++) {
-				int x = config->defs[m].field_index;
-				if (rule->wildness[x] < wild_limit[m]) {
-					move = 0;
-					break;
-				}
-			}
+		/* Build of the last trie completed. */
+		if (last == NULL)
+			break;
 
-			if (move) {
-				rule->config = new_config;
-				rule->next = rule_sets[num_tries];
-				rule_sets[num_tries] = rule;
-				*prev = next;
-			} else
-				prev = &rule->next;
+		if (num_tries == RTE_DIM(context->tries)) {
+			RTE_LOG(ERR, ACL,
+				"Exceeded max number of tries: %u\n",
+				num_tries);
+			return -ENOMEM;
 		}
 
-		head = rule_sets[num_tries];
-		n = acl_rule_stats(rule_sets[num_tries], config,
-			&wild_limit[0]);
-		num_tries++;
-	}
+		/* Trie is getting too big, split remaining rule set. */
+		rule_sets[num_tries] = last->next;
+		last->next = NULL;
+		acl_free_node(context, context->bld_tries[n].trie);
 
-	if (n > 0)
-		RTE_LOG(DEBUG, ACL,
-			"Number of tries(%d) exceeded.\n", RTE_ACL_MAX_TRIES);
+		/* Create a new copy of config for remaining rules. */
+		config = acl_build_alloc(context, 1, sizeof(*config));
+		memcpy(config, rule_sets[n]->config, sizeof(*config));
 
-	for (n = 0; n < num_tries; n++) {
+		/* Make remaining rules use new config. */
+		for (head = rule_sets[num_tries]; head != NULL;
+				head = head->next)
+			head->config = config;
 
-		rule_sets[n] = sort_rules(rule_sets[n]);
-		context->tries[n].type = RTE_ACL_FULL_TRIE;
-		context->tries[n].count = 0;
-		context->tries[n].num_data_indexes =
-			acl_build_index(rule_sets[n]->config,
-			context->data_indexes[n]);
-		context->tries[n].data_index = context->data_indexes[n];
-
-		context->bld_tries[n].trie =
-				build_trie(context, rule_sets[n],
-				&last, &context->tries[n].count);
-		if (context->bld_tries[n].trie == NULL) {
+		/*
+		 * Rebuild the trie for the reduced rule-set.
+		 * Don't try to split it any further.
+		 */
+		last = build_one_trie(context, rule_sets, n, INT32_MAX);
+		if (context->bld_tries[n].trie == NULL || last != NULL) {
 			RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
 			return -ENOMEM;
 		}
 
-		if (last != NULL) {
-			rule_sets[num_tries++] = last->next;
-			last->next = NULL;
-			acl_free_node(context, context->bld_tries[n].trie);
-			context->tries[n].count = 0;
-
-			context->bld_tries[n].trie =
-					build_trie(context, rule_sets[n],
-					&last, &context->tries[n].count);
-			if (context->bld_tries[n].trie == NULL) {
-				RTE_LOG(ERR, ACL,
-					"Build of %u-th trie failed\n", n);
-					return -ENOMEM;
-			}
-		}
 	}
 
 	context->num_tries = num_tries;
@@ -1876,15 +1416,20 @@ 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);
 
 	for (n = 0; n < RTE_DIM(ctx->tries); n++) {
 		if (ctx->tries[n].count != 0)
 			RTE_LOG(DEBUG, ACL,
-				"trie %u: number of rules: %u\n",
-				n, ctx->tries[n].count);
+				"trie %u: number of rules: %u, indexes: %u\n",
+				n, ctx->tries[n].count,
+				ctx->tries[n].num_data_indexes);
 	}
 }
 
@@ -1903,12 +1448,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;
@@ -1948,61 +1487,147 @@ acl_set_data_indexes(struct rte_acl_ctx *ctx)
 		memcpy(ctx->data_indexes + ofs, ctx->trie[i].data_index,
 			n * sizeof(ctx->data_indexes[0]));
 		ctx->trie[i].data_index = ctx->data_indexes + ofs;
-		ofs += n;
+		ofs += RTE_ACL_MAX_FIELDS;
 	}
 }
 
+/*
+ * 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;
 
-int
-rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
+	/* 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 = RTE_LEN2MASK(bcx->cfg.num_categories,
+		typeof(bcx->category_mask));
+	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;
+}
+
+/*
+ * Check that parameters for acl_build() are valid.
+ */
+static int
+acl_check_bld_param(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
 {
-	int rc;
-	struct acl_build_context bcx;
+	static const size_t field_sizes[] = {
+		sizeof(uint8_t), sizeof(uint16_t),
+		sizeof(uint32_t), sizeof(uint64_t),
+	};
+
+	uint32_t i, j;
 
 	if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
-			cfg->num_categories > RTE_ACL_MAX_CATEGORIES)
+			cfg->num_categories > RTE_ACL_MAX_CATEGORIES ||
+			cfg->num_fields == 0 ||
+			cfg->num_fields > RTE_ACL_MAX_FIELDS)
 		return -EINVAL;
 
-	acl_build_reset(ctx);
+	for (i = 0; i != cfg->num_fields; i++) {
+		if (cfg->defs[i].type > RTE_ACL_FIELD_TYPE_BITMASK) {
+			RTE_LOG(ERR, ACL,
+			"ACL context: %s, invalid type: %hhu for %u-th field\n",
+			ctx->name, cfg->defs[i].type, i);
+			return -EINVAL;
+		}
+		for (j = 0;
+				j != RTE_DIM(field_sizes) &&
+				cfg->defs[i].size != field_sizes[j];
+				j++)
+			;
+
+		if (j == RTE_DIM(field_sizes)) {
+			RTE_LOG(ERR, ACL,
+			"ACL context: %s, invalid size: %hhu for %u-th field\n",
+			ctx->name, cfg->defs[i].size, i);
+			return -EINVAL;
+		}
+	}
 
-	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);
+	return 0;
+}
 
+int
+rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
+{
+	int32_t rc;
+	uint32_t n;
+	size_t max_size;
+	struct acl_build_context bcx;
 
-	/* Create a build rules copy. */
-	rc = acl_build_rules(&bcx);
+	rc = acl_check_bld_param(ctx, cfg);
 	if (rc != 0)
 		return rc;
 
-	/* No rules to build for that context+config */
-	if (bcx.build_rules == NULL) {
-		rc = -EINVAL;
+	acl_build_reset(ctx);
 
-	/* build internal trie representation. */
-	} else if ((rc = acl_build_tries(&bcx, bcx.build_rules)) == 0) {
+	if (cfg->max_size == 0) {
+		n = NODE_MIN;
+		max_size = SIZE_MAX;
+	} else {
+		n = NODE_MAX;
+		max_size = cfg->max_size;
+	}
 
-		/* 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_IPV4VLAN_NUM * RTE_DIM(bcx.tries),
-				bcx.num_build_rules);
-		if (rc == 0) {
+	for (rc = -ERANGE; n >= NODE_MIN && rc == -ERANGE; n /= 2) {
 
-			/* set data indexes. */
-			acl_set_data_indexes(ctx);
+		/* perform build phase. */
+		rc = acl_bld(&bcx, ctx, cfg, n);
 
-			/* copy in build config. */
-			ctx->config = *cfg;
+		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]), max_size);
+			if (rc == 0) {
+				/* set data indexes. */
+				acl_set_data_indexes(ctx);
+
+				/* 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;
 }