X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_acl%2Facl_bld.c;h=9e5ad1c63e2a93d184eb8c9665d0b576ed8a5077;hb=693f715da45c48ec1ec0fe4ba2f3b5ffd11ba53e;hp=d89c66af2ee0e3182ce37f388e8974fb084ee298;hpb=4a6ce751ace3708ed33248582cf24f808933e957;p=dpdk.git

diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index d89c66af2e..9e5ad1c63e 100644
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -120,10 +120,6 @@ 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, 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);
-
 static void
 acl_deref_ptr(struct acl_build_context *context,
 	struct rte_acl_node *node, int index);
@@ -414,58 +410,6 @@ acl_intersect_type(const 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
  */
@@ -533,63 +477,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
  */
@@ -650,203 +537,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);
-
-	/* 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,
@@ -1262,19 +952,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,
@@ -1477,42 +1157,100 @@ rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2)
 		int field_index = r1->config->defs[n].field_index;
 
 		if (r1->wildness[field_index] != r2->wildness[field_index])
-			return (r1->wildness[field_index] -
-				r2->wildness[field_index]);
+			return r1->wildness[field_index] -
+				r2->wildness[field_index];
 	}
 	return 0;
 }
 
+/*
+ * 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 *fast;
+	struct rte_acl_build_rule *slow;
+
+	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;
+	}
+}
+
+/*
+ * 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;
+
+	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 *new_head;
-	struct rte_acl_build_rule *l, *r, **p;
-
-	new_head = NULL;
-	while (head != NULL) {
-
-		/* remove element from the head of the old list. */
-		r = head;
-		head = r->next;
-		r->next = NULL;
-
-		/* 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)
-			;
+	struct rte_acl_build_rule *a;
+	struct rte_acl_build_rule *b;
 
-		/* insert element into the new sorted list. */
-		r->next = *p;
-		*p = r;
-	}
+	/* 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);
+
+	/* Recursively sort the sublists */
+	a = sort_rules(a);
+	b = sort_rules(b);
 
-	return new_head;
+	/* answer = merge the two sorted lists together */
+	return rule_list_sorted_merge(a, b);
 }
 
 static uint32_t