/* 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 {
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;
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,
/* 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) {
* 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;
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
*/
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;
}
}
}
-/*
- * 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
*/
}
}
-/*
- * 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,
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
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;
}
/*
- * 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.
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;
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;
* 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,
/* 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;
}
}
* 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++) {
+ for (m = context->cfg.num_categories; 0 != m--; ) {
if (rule->f->data.category_mask & (1 << m)) {
end->mrt->results[m] = rule->f->data.userdata;
end->mrt->priority[m] = rule->f->data.priority;
}
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;
}
return trie;
}
-static int
+static void
acl_calc_wildness(struct rte_acl_build_rule *head,
const struct rte_acl_config *config)
{
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 -
- _mm_popcnt_u32(fld->mask_range.u8)) /
+ wild = (size - __builtin_popcountll(
+ fld->mask_range.u64 & msk_val)) /
size;
break;
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;
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;
+ struct rte_acl_build_rule *fast;
+ struct rte_acl_build_rule *slow;
- if (rule == NULL)
- return head;
-
- 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;
- if (last_rule != reordered_head)
- reordered_head = ordered_insert_rule(reordered_head, last_rule);
+ /* Split head into 'a' and 'b' sublists */
+ rule_list_split(head, &a, &b);
- return reordered_head;
+ /* Recursively sort the sublists */
+ a = sort_rules(a);
+ b = sort_rules(b);
+
+ /* answer = merge the two sorted lists together */
+ return rule_list_sorted_merge(a, b);
}
static uint32_t
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;
-
- n = acl_rule_stats(head, config, &wild_limit[0]);
+ acl_calc_wildness(head, config);
- /* put all rules that fit the wildness criteria into a seperate trie */
- while (n > 0 && num_tries < RTE_ACL_MAX_TRIES) {
+ for (n = 0;; n = num_tries) {
- 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;
+ num_tries = n + 1;
- new_config = acl_build_alloc(context, 1, sizeof(*new_config));
- if (new_config == NULL) {
- RTE_LOG(ERR, ACL,
- "Failed to geti 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;
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);
}
}
sz = ofs + n * fn * sizeof(*wp);
br = tb_alloc(&bcx->pool, sz);
- if (br == NULL) {
- RTE_LOG(ERR, ACL, "ACL conext %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;
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 buid 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;
}
git.droids-corp.org / dpdk.git / blobdiff