/*- * 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. */ #include #include "tb_mem.h" #include "acl.h" #define ACL_POOL_ALIGN 8 #define ACL_POOL_ALLOC_MIN 0x800000 /* 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) /* TALLY are statistics per field */ enum { TALLY_0 = 0, /* number of rules that are 0% or more wild. */ TALLY_25, /* number of rules that are 25% or more wild. */ TALLY_50, TALLY_75, TALLY_100, TALLY_DEACTIVATED, /* deactivated fields (100% wild in all rules). */ TALLY_DEPTH, /* number of rules that are 100% wild for this field and higher. */ TALLY_NUM }; static const uint32_t wild_limits[TALLY_DEACTIVATED] = {0, 25, 50, 75, 100}; enum { ACL_INTERSECT_NONE = 0, ACL_INTERSECT_A = 1, /* set A is a superset of A and B intersect */ ACL_INTERSECT_B = 2, /* set B is a superset of A and B intersect */ ACL_INTERSECT = 4, /* sets A and B intersect */ }; enum { ACL_PRIORITY_EQUAL = 0, ACL_PRIORITY_NODE_A = 1, ACL_PRIORITY_NODE_B = 2, ACL_PRIORITY_MIXED = 3 }; struct acl_mem_block { uint32_t block_size; void *mem_ptr; }; #define MEM_BLOCK_NUM 16 /* Single ACL rule, build representation.*/ struct rte_acl_build_rule { struct rte_acl_build_rule *next; struct rte_acl_config *config; /**< configuration for each field in the rule. */ const struct rte_acl_rule *f; uint32_t *wildness; }; /* Context for build phase */ struct acl_build_context { const struct rte_acl_ctx *acx; struct rte_acl_build_rule *build_rules; struct rte_acl_config cfg; uint32_t node; uint32_t num_nodes; uint32_t category_mask; uint32_t num_rules; uint32_t node_id; uint32_t src_mask; uint32_t num_build_rules; uint32_t num_tries; struct tb_mem_pool pool; struct rte_acl_trie tries[RTE_ACL_MAX_TRIES]; struct rte_acl_bld_trie bld_tries[RTE_ACL_MAX_TRIES]; uint32_t data_indexes[RTE_ACL_MAX_TRIES][RTE_ACL_MAX_FIELDS]; /* memory free lists for nodes and blocks used for node ptrs */ struct acl_mem_block blocks[MEM_BLOCK_NUM]; struct rte_acl_node *node_free_list; }; 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); static void acl_deref_ptr(struct acl_build_context *context, struct rte_acl_node *node, int index); static void * acl_build_alloc(struct acl_build_context *context, size_t n, size_t s) { uint32_t m; void *p; size_t alloc_size = n * s; /* * look for memory in free lists */ for (m = 0; m < RTE_DIM(context->blocks); m++) { if (context->blocks[m].block_size == alloc_size && context->blocks[m].mem_ptr != NULL) { p = context->blocks[m].mem_ptr; context->blocks[m].mem_ptr = *((void **)p); memset(p, 0, alloc_size); return p; } } /* * return allocation from memory pool */ p = tb_alloc(&context->pool, alloc_size); return p; } /* * Free memory blocks (kept in context for reuse). */ static void acl_build_free(struct acl_build_context *context, size_t s, void *p) { uint32_t n; for (n = 0; n < RTE_DIM(context->blocks); n++) { if (context->blocks[n].block_size == s) { *((void **)p) = context->blocks[n].mem_ptr; context->blocks[n].mem_ptr = p; return; } } for (n = 0; n < RTE_DIM(context->blocks); n++) { if (context->blocks[n].block_size == 0) { context->blocks[n].block_size = s; *((void **)p) = NULL; context->blocks[n].mem_ptr = p; return; } } } /* * Allocate and initialize a new node. */ static struct rte_acl_node * acl_alloc_node(struct acl_build_context *context, int level) { struct rte_acl_node *node; if (context->node_free_list != NULL) { node = context->node_free_list; context->node_free_list = node->next; memset(node, 0, sizeof(struct rte_acl_node)); } else { node = acl_build_alloc(context, sizeof(struct rte_acl_node), 1); } if (node != NULL) { node->num_ptrs = 0; node->level = level; node->node_type = RTE_ACL_NODE_UNDEFINED; node->node_index = RTE_ACL_NODE_UNDEFINED; context->num_nodes++; node->id = context->node_id++; } return node; } /* * Dereference all nodes to which this node points */ static void acl_free_node(struct acl_build_context *context, struct rte_acl_node *node) { uint32_t n; if (node->prev != NULL) node->prev->next = NULL; for (n = 0; n < node->num_ptrs; n++) acl_deref_ptr(context, node, n); /* free mrt if this is a match node */ if (node->mrt != NULL) { acl_build_free(context, sizeof(struct rte_acl_match_results), node->mrt); node->mrt = NULL; } /* free transitions to other nodes */ if (node->ptrs != NULL) { acl_build_free(context, node->max_ptrs * sizeof(struct rte_acl_ptr_set), node->ptrs); node->ptrs = NULL; } /* put it on the free list */ context->num_nodes--; node->next = context->node_free_list; context->node_free_list = node; } /* * Include src bitset in dst bitset */ static void acl_include(struct rte_acl_bitset *dst, struct rte_acl_bitset *src, bits_t mask) { uint32_t n; for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) dst->bits[n] = (dst->bits[n] & mask) | src->bits[n]; } /* * Set dst to bits of src1 that are not in src2 */ static int acl_exclude(struct rte_acl_bitset *dst, struct rte_acl_bitset *src1, struct rte_acl_bitset *src2) { uint32_t n; bits_t all_bits = 0; for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) { dst->bits[n] = src1->bits[n] & ~src2->bits[n]; all_bits |= dst->bits[n]; } return all_bits != 0; } /* * Add a pointer (ptr) to a node. */ static int acl_add_ptr(struct acl_build_context *context, struct rte_acl_node *node, struct rte_acl_node *ptr, struct rte_acl_bitset *bits) { uint32_t n, num_ptrs; struct rte_acl_ptr_set *ptrs = NULL; /* * If there's already a pointer to the same node, just add to the bitset */ for (n = 0; n < node->num_ptrs; n++) { if (node->ptrs[n].ptr != NULL) { if (node->ptrs[n].ptr == ptr) { acl_include(&node->ptrs[n].values, bits, -1); acl_include(&node->values, bits, -1); return 0; } } } /* if there's no room for another pointer, make room */ if (node->num_ptrs >= node->max_ptrs) { /* 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) { memcpy(ptrs, node->ptrs, node->num_ptrs * sizeof(*ptrs)); acl_build_free(context, node->max_ptrs * sizeof(*ptrs), node->ptrs); } node->ptrs = ptrs; node->max_ptrs = num_ptrs; } /* Find available ptr and add a new pointer to this node */ for (n = node->min_add; n < node->max_ptrs; n++) { if (node->ptrs[n].ptr == NULL) { node->ptrs[n].ptr = ptr; acl_include(&node->ptrs[n].values, bits, 0); acl_include(&node->values, bits, -1); if (ptr != NULL) ptr->ref_count++; if (node->num_ptrs <= n) node->num_ptrs = n + 1; return 0; } } return 0; } /* * Add a pointer for a range of values */ static int acl_add_ptr_range(struct acl_build_context *context, struct rte_acl_node *root, struct rte_acl_node *node, uint8_t low, uint8_t high) { uint32_t n; struct rte_acl_bitset bitset; /* clear the bitset values */ for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) bitset.bits[n] = 0; /* for each bit in range, add bit to set */ 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)); return acl_add_ptr(context, root, node, &bitset); } /* * Generate a bitset from a byte value and mask. */ static int acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask) { int range = 0; uint32_t n; /* clear the bitset values */ for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) bitset->bits[n] = 0; /* for each bit in value/mask, add bit to set */ for (n = 0; n < UINT8_MAX + 1; n++) { if ((n & mask) == value) { range++; bitset->bits[n / (sizeof(bits_t) * 8)] |= 1 << (n % (sizeof(bits_t) * 8)); } } return range; } /* * Determine how A and B intersect. * 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, struct rte_acl_bitset *intersect) { uint32_t n; bits_t intersect_bits = 0; bits_t a_superset = 0; bits_t b_superset = 0; /* * calculate and store intersection and check if A and/or B have * bits outside the intersection (superset) */ for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) { intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n]; a_superset |= a_bits->bits[n] ^ intersect->bits[n]; b_superset |= b_bits->bits[n] ^ intersect->bits[n]; intersect_bits |= intersect->bits[n]; } n = (intersect_bits == 0 ? ACL_INTERSECT_NONE : ACL_INTERSECT) | (b_superset == 0 ? 0 : ACL_INTERSECT_B) | (a_superset == 0 ? 0 : ACL_INTERSECT_A); 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 */ static struct rte_acl_node * acl_dup_node(struct acl_build_context *context, struct rte_acl_node *node) { uint32_t n; 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; } /* copy over the pointers */ for (n = 0; n < node->num_ptrs; n++) { if (node->ptrs[n].ptr != NULL) { next->ptrs[n].ptr = node->ptrs[n].ptr; next->ptrs[n].ptr->ref_count++; acl_include(&next->ptrs[n].values, &node->ptrs[n].values, -1); } } next->num_ptrs = node->num_ptrs; /* copy over node's match results */ if (node->match_flag == 0) next->match_flag = 0; else { next->match_flag = -1; next->mrt = acl_build_alloc(context, 1, sizeof(*next->mrt)); memcpy(next->mrt, node->mrt, sizeof(*next->mrt)); } /* copy over node's bitset */ acl_include(&next->values, &node->values, -1); node->next = next; next->prev = node; return next; } /* * Dereference a pointer from a node */ static void acl_deref_ptr(struct acl_build_context *context, struct rte_acl_node *node, int index) { struct rte_acl_node *ref_node; /* De-reference the node at the specified pointer */ if (node != NULL && node->ptrs[index].ptr != NULL) { ref_node = node->ptrs[index].ptr; ref_node->ref_count--; if (ref_node->ref_count == 0) acl_free_node(context, ref_node); } } /* * 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 */ static int acl_copy_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; struct rte_acl_bitset bits; if (b_bits != NULL) if (!acl_exclude(&bits, &src->ptrs[index].values, b_bits)) return 0; rc = acl_add_ptr(context, dst, src->ptrs[index].ptr, &bits); if (rc < 0) return rc; return 1; } /* * Fill in gaps in ptrs list with the ptr at the end of the list */ static void acl_compact_node_ptrs(struct rte_acl_node *node_a) { uint32_t n; int min_add = node_a->min_add; while (node_a->num_ptrs > 0 && node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL) node_a->num_ptrs--; for (n = min_add; n + 1 < node_a->num_ptrs; n++) { /* if this entry is empty */ if (node_a->ptrs[n].ptr == NULL) { /* move the last pointer to this entry */ acl_include(&node_a->ptrs[n].values, &node_a->ptrs[node_a->num_ptrs - 1].values, 0); node_a->ptrs[n].ptr = node_a->ptrs[node_a->num_ptrs - 1].ptr; /* * mark the end as empty and adjust the number * of used pointer enum_tries */ node_a->ptrs[node_a->num_ptrs - 1].ptr = NULL; while (node_a->num_ptrs > 0 && node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL) node_a->num_ptrs--; } } } /* * 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, struct rte_acl_node *node_b, struct rte_acl_node **node_c) { uint32_t n; int combined_priority = ACL_PRIORITY_EQUAL; for (n = 0; n < context->cfg.num_categories; n++) { if (node_a->mrt->priority[n] != node_b->mrt->priority[n]) { combined_priority |= (node_a->mrt->priority[n] > node_b->mrt->priority[n]) ? ACL_PRIORITY_NODE_A : ACL_PRIORITY_NODE_B; } } /* * if node a is higher or equal priority for all categories, * then return node_a. */ if (combined_priority == ACL_PRIORITY_NODE_A || combined_priority == ACL_PRIORITY_EQUAL) { *node_c = node_a; return 0; } /* * if node b is higher or equal priority for all categories, * then return node_b. */ if (combined_priority == ACL_PRIORITY_NODE_B) { *node_c = node_b; return 0; } /* * mixed priorities - create a new node with the highest priority * for each category. */ /* force new duplication. */ node_a->next = NULL; *node_c = acl_dup_node(context, node_a); for (n = 0; n < context->cfg.num_categories; n++) { if ((*node_c)->mrt->priority[n] < node_b->mrt->priority[n]) { (*node_c)->mrt->priority[n] = node_b->mrt->priority[n]; (*node_c)->mrt->results[n] = node_b->mrt->results[n]; } } 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 * * If match node (leaf on trie) * For each category * return node = highest priority result * * Create C as a duplicate of A to point to child intersections * If any pointers in C intersect with any in B * For each intersection * merge children * remove intersection from C pointer * add a pointer from C to child intersection node * Compact the pointers in A and B * Copy any B pointers that are outside of the intersection to C * If C has no references to the B trie * free C and return A * Else If C has no references to the A trie * free C and return B * Else * return C */ 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 n, m, ptrs_c, ptrs_b; uint32_t min_add_c, min_add_b; int node_intersect_type; struct rte_acl_bitset node_intersect; struct rte_acl_node *node_c; struct rte_acl_node *node_a_next; int node_b_refs; int node_a_refs; node_c = node_a; node_a_next = node_a->next; min_add_c = 0; min_add_b = 0; node_a_refs = node_a->num_ptrs; node_b_refs = 0; node_intersect_type = 0; /* Resolve leaf nodes (matches) */ if (node_a->match_flag != 0) { acl_resolve_leaf(context, node_a, node_b, return_c); return 0; } /* * 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. */ if (level > 0 && node_a->subtree_id != (subtree_id | RTE_ACL_SUBTREE_NODE)) { 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. * Check intersection for entire node (all pointers) */ node_intersect_type = acl_intersect_type(&node_c->values, &node_b->values, &node_intersect); if (node_intersect_type & ACL_INTERSECT) { min_add_b = node_b->min_add; node_b->min_add = node_b->num_ptrs; ptrs_b = node_b->num_ptrs; min_add_c = node_c->min_add; node_c->min_add = node_c->num_ptrs; ptrs_c = node_c->num_ptrs; for (n = 0; n < ptrs_c; n++) { if (node_c->ptrs[n].ptr == NULL) { node_a_refs--; continue; } node_c->ptrs[n].ptr->next = NULL; for (m = 0; m < ptrs_b; m++) { struct rte_acl_bitset child_intersect; int child_intersect_type; struct rte_acl_node *child_node_c = NULL; if (node_b->ptrs[m].ptr == NULL || node_c->ptrs[n].ptr == node_b->ptrs[m].ptr) continue; child_intersect_type = acl_intersect_type( &node_c->ptrs[n].values, &node_b->ptrs[m].values, &child_intersect); if ((child_intersect_type & ACL_INTERSECT) != 0) { if (acl_merge_trie(context, node_c->ptrs[n].ptr, node_b->ptrs[m].ptr, level + 1, subtree_id, &child_node_c)) return 1; if (child_node_c != NULL && child_node_c != node_c->ptrs[n].ptr) { node_b_refs++; /* * Added link from C to * child_C for all transitions * in the intersection. */ acl_add_ptr(context, node_c, child_node_c, &child_intersect); /* * inc refs if pointer is not * to node b. */ node_a_refs += (child_node_c != node_b->ptrs[m].ptr); /* * Remove intersection from C * pointer. */ if (!acl_exclude( &node_c->ptrs[n].values, &node_c->ptrs[n].values, &child_intersect)) { acl_deref_ptr(context, node_c, n); node_c->ptrs[n].ptr = NULL; node_a_refs--; } } } } } /* Compact pointers */ node_c->min_add = min_add_c; acl_compact_node_ptrs(node_c); node_b->min_add = min_add_b; acl_compact_node_ptrs(node_b); } /* * Copy pointers outside of the intersection from B to C */ if ((node_intersect_type & ACL_INTERSECT_B) != 0) { node_b_refs++; for (m = 0; m < node_b->num_ptrs; m++) if (node_b->ptrs[m].ptr != NULL) acl_copy_ptr(context, node_c, node_b, m, &node_intersect); } /* * Free node C if top of trie is contained in A or B * if node C is a duplicate of node A && * node C was not an existing duplicate */ if (node_c != node_a && node_c != node_a_next) { /* * if the intersection has no references to the * B side, then it is contained in A */ if (node_b_refs == 0) { acl_free_node(context, node_c); node_c = node_a; } else { /* * if the intersection has no references to the * A side, then it is contained in B. */ if (node_a_refs == 0) { acl_free_node(context, node_c); node_c = node_b; } } } if (return_c != NULL) *return_c = node_c; if (level == 0) acl_free_node(context, node_b); return 0; } /* * Reset current runtime fields before next build: * - free allocated RT memory. * - reset all RT related fields to zero. */ static void acl_build_reset(struct rte_acl_ctx *ctx) { rte_free(ctx->mem); memset(&ctx->num_categories, 0, sizeof(*ctx) - offsetof(struct rte_acl_ctx, num_categories)); } 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) { struct rte_acl_node *node, *prev; uint32_t n; 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]); prev = node; } acl_add_ptr_range(context, prev, end, lo[0], hi[0]); } static struct rte_acl_node * 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; *pend = acl_alloc_node(context, level+size); root = acl_alloc_node(context, level++); 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; memset(limit_lo, 0, RTE_DIM(limit_lo)); memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi)); for (n = size - 2; n >= 0; n--) { hi_ff = (uint8_t)(hi_ff & hi[n]); lo_00 = (uint8_t)(lo_00 | lo[n]); } if (hi_ff != UINT8_MAX) { limit_lo[size - 1] = hi[size - 1]; acl_gen_range(context, hi, limit_lo, size, level, root, *pend); } if (lo_00 != 0) { limit_hi[size - 1] = lo[size - 1]; acl_gen_range(context, limit_hi, lo, size, level, root, *pend); } 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); } } return root; } static struct rte_acl_node * acl_gen_mask_trie(struct acl_build_context *context, const void *value, const void *mask, int size, int level, struct rte_acl_node **pend) { int32_t n; 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; root = acl_alloc_node(context, level++); prev = root; for (n = size - 1; n >= 0; n--) { node = acl_alloc_node(context, level++); acl_gen_mask(&bits, val[n] & msk[n], msk[n]); acl_add_ptr(context, prev, node, &bits); prev = node; } *pend = prev; return root; } static struct rte_acl_node * build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, struct rte_acl_build_rule **last, uint32_t *count) { uint32_t n, m; int field_index, node_count; struct rte_acl_node *trie; 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; 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; for (n = 0; n < rule->config->num_fields; n++) { field_index = rule->config->defs[n].field_index; fld = rule->f->field + field_index; end_prev = end; /* build a mini-trie for this field */ switch (rule->config->defs[n].type) { case RTE_ACL_FIELD_TYPE_BITMASK: merge = acl_gen_mask_trie(context, &fld->value, &fld->mask_range, rule->config->defs[n].size, end->level + 1, &end); break; case RTE_ACL_FIELD_TYPE_MASK: { /* * set msb for the size of the field and * 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); } /* gen a mini-trie for this field */ merge = acl_gen_mask_trie(context, &fld->value, (char *)&mask, rule->config->defs[n].size, end->level + 1, &end); } break; case RTE_ACL_FIELD_TYPE_RANGE: merge = acl_gen_range_trie(context, &rule->f->field[field_index].value, &rule->f->field[field_index].mask_range, rule->config->defs[n].size, end->level + 1, &end); break; default: RTE_LOG(ERR, ACL, "Error in rule[%u] type - %hhu\n", rule->f->data.userdata, rule->config->defs[n].type); return NULL; } /* merge this field on to the end of the rule */ if (acl_merge_trie(context, end_prev, merge, 0, 0, NULL) != 0) { return NULL; } } end->match_flag = ++context->num_build_rules; /* * 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; for (m = 0; m < context->cfg.num_categories; 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; } else { end->mrt->results[m] = 0; end->mrt->priority[m] = 0; } } 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)) return NULL; node_count = context->num_nodes - node_count; if (node_count > NODE_MAX) { *last = prev; return trie; } prev = rule; rule = rule->next; } *last = NULL; return trie; } static int acl_calc_wildness(struct rte_acl_build_rule *head, const struct rte_acl_config *config) { uint32_t n; struct rte_acl_build_rule *rule; for (rule = head; rule != NULL; rule = rule->next) { for (n = 0; n < config->num_fields; n++) { double wild = 0; double size = CHAR_BIT * config->defs[n].size; 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)) / size; break; case RTE_ACL_FIELD_TYPE_MASK: wild = (size - fld->mask_range.u32) / size; 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; } 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) { int min; struct rte_acl_build_rule *rule; uint32_t n, m, fields_deactivated = 0; uint32_t start = 0, deactivate = 0; int tally[RTE_ACL_MAX_LEVELS][TALLY_NUM]; memset(tally, 0, sizeof(tally)); for (rule = head; rule != NULL; rule = rule->next) { for (n = 0; n < config->num_fields; n++) { uint32_t field_index = config->defs[n].field_index; tally[n][TALLY_0]++; for (m = 1; m < RTE_DIM(wild_limits); m++) { if (rule->wildness[field_index] >= wild_limits[m]) tally[n][m]++; } } for (n = config->num_fields - 1; n > 0; n--) { uint32_t field_index = config->defs[n].field_index; if (rule->wildness[field_index] == 100) tally[n][TALLY_DEPTH]++; else break; } } /* * Look for any field that is always wild and drop it from the config * Only deactivate if all fields for a given input loop are deactivated. */ for (n = 1; n < config->num_fields; n++) { if (config->defs[n].input_index != config->defs[n - 1].input_index) { for (m = start; m < n; m++) tally[m][TALLY_DEACTIVATED] = deactivate; fields_deactivated += deactivate; start = n; deactivate = 1; } /* if the field is not always completely wild */ if (tally[n][TALLY_100] != tally[n][TALLY_0]) deactivate = 0; } for (m = start; m < n; m++) tally[m][TALLY_DEACTIVATED] = deactivate; fields_deactivated += deactivate; /* remove deactivated fields */ if (fields_deactivated) { uint32_t k, l = 0; for (k = 0; k < config->num_fields; k++) { if (tally[k][TALLY_DEACTIVATED] == 0) { memcpy(&tally[l][0], &tally[k][0], TALLY_NUM * sizeof(tally[0][0])); memcpy(&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) { 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; if (left->wildness[field_index] != rule->wildness[field_index]) return (left->wildness[field_index] >= rule->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) { struct rte_acl_build_rule **insert; if (rule == NULL) return head; rule->next = head; if (head == NULL) return rule; insert = &head; while (order(insert, rule)) insert = &(*insert)->next; rule->next = *insert; *insert = rule; return head; } 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; for (rule = head; rule != NULL; rule = rule->next) { reordered_head = ordered_insert_rule(reordered_head, last_rule); last_rule = rule; } if (last_rule != reordered_head) reordered_head = ordered_insert_rule(reordered_head, last_rule); return reordered_head; } static uint32_t acl_build_index(const struct rte_acl_config *config, uint32_t *data_index) { uint32_t n, m; int32_t last_header; m = 0; last_header = -1; for (n = 0; n < config->num_fields; n++) { if (last_header != config->defs[n].input_index) { last_header = config->defs[n].input_index; data_index[m++] = config->defs[n].offset; } } return m; } 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; 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 *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]); /* put all rules that fit the wildness criteria into a seperate trie */ while (n > 0 && num_tries < RTE_ACL_MAX_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; 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"); 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; } } if (move) { rule->config = new_config; rule->next = rule_sets[num_tries]; rule_sets[num_tries] = rule; *prev = next; } else prev = &rule->next; } head = rule_sets[num_tries]; n = acl_rule_stats(rule_sets[num_tries], config, &wild_limit[0]); num_tries++; } if (n > 0) RTE_LOG(DEBUG, ACL, "Number of tries(%d) exceeded.\n", RTE_ACL_MAX_TRIES); for (n = 0; n < num_tries; n++) { 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) { 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; return 0; } static void acl_build_log(const struct acl_build_context *ctx) { uint32_t n; RTE_LOG(DEBUG, ACL, "Build phase for ACL \"%s\":\n" "memory consumed: %zu\n", ctx->acx->name, 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); } } static int acl_build_rules(struct acl_build_context *bcx) { struct rte_acl_build_rule *br, *head; const struct rte_acl_rule *rule; uint32_t *wp; uint32_t fn, i, n, num; size_t ofs, sz; fn = bcx->cfg.num_fields; n = bcx->acx->num_rules; ofs = n * sizeof(*br); 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; head = NULL; for (i = 0; i != n; i++) { rule = (const struct rte_acl_rule *) ((uintptr_t)bcx->acx->rules + bcx->acx->rule_sz * i); if ((rule->data.category_mask & bcx->category_mask) != 0) { br[num].next = head; br[num].config = &bcx->cfg; br[num].f = rule; br[num].wildness = wp; wp += fn; head = br + num; num++; } } bcx->num_rules = num; bcx->build_rules = head; return 0; } /* * Copy data_indexes for each trie into RT location. */ static void acl_set_data_indexes(struct rte_acl_ctx *ctx) { uint32_t i, n, ofs; ofs = 0; for (i = 0; i != ctx->num_tries; i++) { n = ctx->trie[i].num_data_indexes; 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; } } int rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg) { int rc; struct acl_build_context bcx; if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 || cfg->num_categories > RTE_ACL_MAX_CATEGORIES) return -EINVAL; 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; /* No rules to build for that context+config */ if (bcx.build_rules == NULL) { rc = -EINVAL; /* build internal trie representation. */ } else if ((rc = acl_build_tries(&bcx, bcx.build_rules)) == 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_IPV4VLAN_NUM * RTE_DIM(bcx.tries), bcx.num_build_rules); if (rc == 0) { /* set data indexes. */ acl_set_data_indexes(ctx); /* copy in build config. */ ctx->config = *cfg; } } acl_build_log(&bcx); /* cleanup after build. */ tb_free_pool(&bcx.pool); return rc; }