4 * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 #define ACL_POOL_ALIGN 8
39 #define ACL_POOL_ALLOC_MIN 0x800000
41 /* number of pointers per alloc */
42 #define ACL_PTR_ALLOC 32
44 /* macros for dividing rule sets heuristics */
45 #define NODE_MAX 0x4000
46 #define NODE_MIN 0x800
48 /* TALLY are statistics per field */
50 TALLY_0 = 0, /* number of rules that are 0% or more wild. */
51 TALLY_25, /* number of rules that are 25% or more wild. */
55 TALLY_DEACTIVATED, /* deactivated fields (100% wild in all rules). */
57 /* number of rules that are 100% wild for this field and higher. */
61 static const uint32_t wild_limits[TALLY_DEACTIVATED] = {0, 25, 50, 75, 100};
64 ACL_INTERSECT_NONE = 0,
65 ACL_INTERSECT_A = 1, /* set A is a superset of A and B intersect */
66 ACL_INTERSECT_B = 2, /* set B is a superset of A and B intersect */
67 ACL_INTERSECT = 4, /* sets A and B intersect */
71 ACL_PRIORITY_EQUAL = 0,
72 ACL_PRIORITY_NODE_A = 1,
73 ACL_PRIORITY_NODE_B = 2,
74 ACL_PRIORITY_MIXED = 3
78 struct acl_mem_block {
83 #define MEM_BLOCK_NUM 16
85 /* Single ACL rule, build representation.*/
86 struct rte_acl_build_rule {
87 struct rte_acl_build_rule *next;
88 struct rte_acl_config *config;
89 /**< configuration for each field in the rule. */
90 const struct rte_acl_rule *f;
94 /* Context for build phase */
95 struct acl_build_context {
96 const struct rte_acl_ctx *acx;
97 struct rte_acl_build_rule *build_rules;
98 struct rte_acl_config cfg;
100 int32_t cur_node_max;
103 uint32_t category_mask;
107 uint32_t num_build_rules;
109 struct tb_mem_pool pool;
110 struct rte_acl_trie tries[RTE_ACL_MAX_TRIES];
111 struct rte_acl_bld_trie bld_tries[RTE_ACL_MAX_TRIES];
112 uint32_t data_indexes[RTE_ACL_MAX_TRIES][RTE_ACL_MAX_FIELDS];
114 /* memory free lists for nodes and blocks used for node ptrs */
115 struct acl_mem_block blocks[MEM_BLOCK_NUM];
116 struct rte_acl_node *node_free_list;
119 static int acl_merge_trie(struct acl_build_context *context,
120 struct rte_acl_node *node_a, struct rte_acl_node *node_b,
121 uint32_t level, struct rte_acl_node **node_c);
123 static int acl_merge(struct acl_build_context *context,
124 struct rte_acl_node *node_a, struct rte_acl_node *node_b,
125 int move, int a_subset, int level);
128 acl_deref_ptr(struct acl_build_context *context,
129 struct rte_acl_node *node, int index);
132 acl_build_alloc(struct acl_build_context *context, size_t n, size_t s)
136 size_t alloc_size = n * s;
139 * look for memory in free lists
141 for (m = 0; m < RTE_DIM(context->blocks); m++) {
142 if (context->blocks[m].block_size ==
143 alloc_size && context->blocks[m].mem_ptr != NULL) {
144 p = context->blocks[m].mem_ptr;
145 context->blocks[m].mem_ptr = *((void **)p);
146 memset(p, 0, alloc_size);
152 * return allocation from memory pool
154 p = tb_alloc(&context->pool, alloc_size);
159 * Free memory blocks (kept in context for reuse).
162 acl_build_free(struct acl_build_context *context, size_t s, void *p)
166 for (n = 0; n < RTE_DIM(context->blocks); n++) {
167 if (context->blocks[n].block_size == s) {
168 *((void **)p) = context->blocks[n].mem_ptr;
169 context->blocks[n].mem_ptr = p;
173 for (n = 0; n < RTE_DIM(context->blocks); n++) {
174 if (context->blocks[n].block_size == 0) {
175 context->blocks[n].block_size = s;
176 *((void **)p) = NULL;
177 context->blocks[n].mem_ptr = p;
184 * Allocate and initialize a new node.
186 static struct rte_acl_node *
187 acl_alloc_node(struct acl_build_context *context, int level)
189 struct rte_acl_node *node;
191 if (context->node_free_list != NULL) {
192 node = context->node_free_list;
193 context->node_free_list = node->next;
194 memset(node, 0, sizeof(struct rte_acl_node));
196 node = acl_build_alloc(context, sizeof(struct rte_acl_node), 1);
202 node->node_type = RTE_ACL_NODE_UNDEFINED;
203 node->node_index = RTE_ACL_NODE_UNDEFINED;
204 context->num_nodes++;
205 node->id = context->node_id++;
211 * Dereference all nodes to which this node points
214 acl_free_node(struct acl_build_context *context,
215 struct rte_acl_node *node)
219 if (node->prev != NULL)
220 node->prev->next = NULL;
221 for (n = 0; n < node->num_ptrs; n++)
222 acl_deref_ptr(context, node, n);
224 /* free mrt if this is a match node */
225 if (node->mrt != NULL) {
226 acl_build_free(context, sizeof(struct rte_acl_match_results),
231 /* free transitions to other nodes */
232 if (node->ptrs != NULL) {
233 acl_build_free(context,
234 node->max_ptrs * sizeof(struct rte_acl_ptr_set),
239 /* put it on the free list */
240 context->num_nodes--;
241 node->next = context->node_free_list;
242 context->node_free_list = node;
247 * Include src bitset in dst bitset
250 acl_include(struct rte_acl_bitset *dst, struct rte_acl_bitset *src, bits_t mask)
254 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
255 dst->bits[n] = (dst->bits[n] & mask) | src->bits[n];
259 * Set dst to bits of src1 that are not in src2
262 acl_exclude(struct rte_acl_bitset *dst,
263 struct rte_acl_bitset *src1,
264 struct rte_acl_bitset *src2)
269 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
270 dst->bits[n] = src1->bits[n] & ~src2->bits[n];
271 all_bits |= dst->bits[n];
273 return all_bits != 0;
277 * Add a pointer (ptr) to a node.
280 acl_add_ptr(struct acl_build_context *context,
281 struct rte_acl_node *node,
282 struct rte_acl_node *ptr,
283 struct rte_acl_bitset *bits)
285 uint32_t n, num_ptrs;
286 struct rte_acl_ptr_set *ptrs = NULL;
289 * If there's already a pointer to the same node, just add to the bitset
291 for (n = 0; n < node->num_ptrs; n++) {
292 if (node->ptrs[n].ptr != NULL) {
293 if (node->ptrs[n].ptr == ptr) {
294 acl_include(&node->ptrs[n].values, bits, -1);
295 acl_include(&node->values, bits, -1);
301 /* if there's no room for another pointer, make room */
302 if (node->num_ptrs >= node->max_ptrs) {
303 /* add room for more pointers */
304 num_ptrs = node->max_ptrs + ACL_PTR_ALLOC;
305 ptrs = acl_build_alloc(context, num_ptrs, sizeof(*ptrs));
307 /* copy current points to new memory allocation */
308 if (node->ptrs != NULL) {
309 memcpy(ptrs, node->ptrs,
310 node->num_ptrs * sizeof(*ptrs));
311 acl_build_free(context, node->max_ptrs * sizeof(*ptrs),
315 node->max_ptrs = num_ptrs;
318 /* Find available ptr and add a new pointer to this node */
319 for (n = node->min_add; n < node->max_ptrs; n++) {
320 if (node->ptrs[n].ptr == NULL) {
321 node->ptrs[n].ptr = ptr;
322 acl_include(&node->ptrs[n].values, bits, 0);
323 acl_include(&node->values, bits, -1);
326 if (node->num_ptrs <= n)
327 node->num_ptrs = n + 1;
336 * Add a pointer for a range of values
339 acl_add_ptr_range(struct acl_build_context *context,
340 struct rte_acl_node *root,
341 struct rte_acl_node *node,
346 struct rte_acl_bitset bitset;
348 /* clear the bitset values */
349 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
352 /* for each bit in range, add bit to set */
353 for (n = 0; n < UINT8_MAX + 1; n++)
354 if (n >= low && n <= high)
355 bitset.bits[n / (sizeof(bits_t) * 8)] |=
356 1 << (n % (sizeof(bits_t) * 8));
358 return acl_add_ptr(context, root, node, &bitset);
362 * Generate a bitset from a byte value and mask.
365 acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
370 /* clear the bitset values */
371 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
374 /* for each bit in value/mask, add bit to set */
375 for (n = 0; n < UINT8_MAX + 1; n++) {
376 if ((n & mask) == value) {
378 bitset->bits[n / (sizeof(bits_t) * 8)] |=
379 1 << (n % (sizeof(bits_t) * 8));
386 * Determine how A and B intersect.
387 * Determine if A and/or B are supersets of the intersection.
390 acl_intersect_type(const struct rte_acl_bitset *a_bits,
391 const struct rte_acl_bitset *b_bits,
392 struct rte_acl_bitset *intersect)
395 bits_t intersect_bits = 0;
396 bits_t a_superset = 0;
397 bits_t b_superset = 0;
400 * calculate and store intersection and check if A and/or B have
401 * bits outside the intersection (superset)
403 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
404 intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
405 a_superset |= a_bits->bits[n] ^ intersect->bits[n];
406 b_superset |= b_bits->bits[n] ^ intersect->bits[n];
407 intersect_bits |= intersect->bits[n];
410 n = (intersect_bits == 0 ? ACL_INTERSECT_NONE : ACL_INTERSECT) |
411 (b_superset == 0 ? 0 : ACL_INTERSECT_B) |
412 (a_superset == 0 ? 0 : ACL_INTERSECT_A);
418 * Check if all bits in the bitset are on
421 acl_full(struct rte_acl_node *node)
424 bits_t all_bits = -1;
426 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
427 all_bits &= node->values.bits[n];
428 return all_bits == -1;
432 * Check if all bits in the bitset are off
435 acl_empty(struct rte_acl_node *node)
439 if (node->ref_count == 0) {
440 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
441 if (0 != node->values.bits[n])
451 * Compute intersection of A and B
452 * return 1 if there is an intersection else 0.
455 acl_intersect(struct rte_acl_bitset *a_bits,
456 struct rte_acl_bitset *b_bits,
457 struct rte_acl_bitset *intersect)
462 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
463 intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
464 all_bits |= intersect->bits[n];
466 return all_bits != 0;
472 static struct rte_acl_node *
473 acl_dup_node(struct acl_build_context *context, struct rte_acl_node *node)
476 struct rte_acl_node *next;
478 next = acl_alloc_node(context, node->level);
480 /* allocate the pointers */
481 if (node->num_ptrs > 0) {
482 next->ptrs = acl_build_alloc(context,
484 sizeof(struct rte_acl_ptr_set));
485 next->max_ptrs = node->max_ptrs;
488 /* copy over the pointers */
489 for (n = 0; n < node->num_ptrs; n++) {
490 if (node->ptrs[n].ptr != NULL) {
491 next->ptrs[n].ptr = node->ptrs[n].ptr;
492 next->ptrs[n].ptr->ref_count++;
493 acl_include(&next->ptrs[n].values,
494 &node->ptrs[n].values, -1);
498 next->num_ptrs = node->num_ptrs;
500 /* copy over node's match results */
501 if (node->match_flag == 0)
502 next->match_flag = 0;
504 next->match_flag = -1;
505 next->mrt = acl_build_alloc(context, 1, sizeof(*next->mrt));
506 memcpy(next->mrt, node->mrt, sizeof(*next->mrt));
509 /* copy over node's bitset */
510 acl_include(&next->values, &node->values, -1);
519 * Dereference a pointer from a node
522 acl_deref_ptr(struct acl_build_context *context,
523 struct rte_acl_node *node, int index)
525 struct rte_acl_node *ref_node;
527 /* De-reference the node at the specified pointer */
528 if (node != NULL && node->ptrs[index].ptr != NULL) {
529 ref_node = node->ptrs[index].ptr;
530 ref_node->ref_count--;
531 if (ref_node->ref_count == 0)
532 acl_free_node(context, ref_node);
537 * Exclude bitset from a node pointer
538 * returns 0 if poiter was deref'd
542 acl_exclude_ptr(struct acl_build_context *context,
543 struct rte_acl_node *node,
545 struct rte_acl_bitset *b_bits)
550 * remove bitset from node pointer and deref
551 * if the bitset becomes empty.
553 if (!acl_exclude(&node->ptrs[index].values,
554 &node->ptrs[index].values,
556 acl_deref_ptr(context, node, index);
557 node->ptrs[index].ptr = NULL;
561 /* exclude bits from the composite bits for the node */
562 acl_exclude(&node->values, &node->values, b_bits);
567 * Remove a bitset from src ptr and move remaining ptr to dst
570 acl_move_ptr(struct acl_build_context *context,
571 struct rte_acl_node *dst,
572 struct rte_acl_node *src,
574 struct rte_acl_bitset *b_bits)
579 if (!acl_exclude_ptr(context, src, index, b_bits))
582 /* add src pointer to dst node */
583 rc = acl_add_ptr(context, dst, src->ptrs[index].ptr,
584 &src->ptrs[index].values);
588 /* remove ptr from src */
589 acl_exclude_ptr(context, src, index, &src->ptrs[index].values);
594 * acl_exclude rte_acl_bitset from src and copy remaining pointer to dst
597 acl_copy_ptr(struct acl_build_context *context,
598 struct rte_acl_node *dst,
599 struct rte_acl_node *src,
601 struct rte_acl_bitset *b_bits)
604 struct rte_acl_bitset bits;
607 if (!acl_exclude(&bits, &src->ptrs[index].values, b_bits))
610 rc = acl_add_ptr(context, dst, src->ptrs[index].ptr, &bits);
617 * Fill in gaps in ptrs list with the ptr at the end of the list
620 acl_compact_node_ptrs(struct rte_acl_node *node_a)
623 int min_add = node_a->min_add;
625 while (node_a->num_ptrs > 0 &&
626 node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
629 for (n = min_add; n + 1 < node_a->num_ptrs; n++) {
631 /* if this entry is empty */
632 if (node_a->ptrs[n].ptr == NULL) {
634 /* move the last pointer to this entry */
635 acl_include(&node_a->ptrs[n].values,
636 &node_a->ptrs[node_a->num_ptrs - 1].values,
638 node_a->ptrs[n].ptr =
639 node_a->ptrs[node_a->num_ptrs - 1].ptr;
642 * mark the end as empty and adjust the number
643 * of used pointer enum_tries
645 node_a->ptrs[node_a->num_ptrs - 1].ptr = NULL;
646 while (node_a->num_ptrs > 0 &&
647 node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
654 * acl_merge helper routine.
657 acl_merge_intersect(struct acl_build_context *context,
658 struct rte_acl_node *node_a, uint32_t idx_a,
659 struct rte_acl_node *node_b, uint32_t idx_b,
660 int next_move, int level,
661 struct rte_acl_bitset *intersect_ptr)
663 struct rte_acl_node *node_c;
665 /* Duplicate A for intersection */
666 node_c = acl_dup_node(context, node_a->ptrs[idx_a].ptr);
668 /* Remove intersection from A */
669 acl_exclude_ptr(context, node_a, idx_a, intersect_ptr);
672 * Added link from A to C for all transitions
673 * in the intersection
675 if (acl_add_ptr(context, node_a, node_c, intersect_ptr) < 0)
678 /* merge B->node into C */
679 return acl_merge(context, node_c, node_b->ptrs[idx_b].ptr, next_move,
685 * Merge the children of nodes A and B together.
689 * node A result = highest priority result
690 * if any pointers in A intersect with any in B
691 * For each intersection
692 * C = copy of node that A points to
693 * remove intersection from A pointer
694 * add a pointer to A that points to C for the intersection
695 * Merge C and node that B points to
696 * Compact the pointers in A and B
698 * If B has only one reference
699 * Move B pointers to A
701 * Copy B pointers to A
704 acl_merge(struct acl_build_context *context,
705 struct rte_acl_node *node_a, struct rte_acl_node *node_b,
706 int move, int a_subset, int level)
708 uint32_t n, m, ptrs_a, ptrs_b;
709 uint32_t min_add_a, min_add_b;
711 int node_intersect_type;
712 int b_full, next_move, rc;
713 struct rte_acl_bitset intersect_values;
714 struct rte_acl_bitset intersect_ptr;
719 node_intersect_type = 0;
725 * Resolve match priorities
727 if (node_a->match_flag != 0 || node_b->match_flag != 0) {
729 if (node_a->match_flag == 0 || node_b->match_flag == 0)
730 RTE_LOG(ERR, ACL, "Not both matches\n");
732 if (node_b->match_flag < node_a->match_flag)
733 RTE_LOG(ERR, ACL, "Not same match\n");
735 for (n = 0; n < context->cfg.num_categories; n++) {
736 if (node_a->mrt->priority[n] <
737 node_b->mrt->priority[n]) {
738 node_a->mrt->priority[n] =
739 node_b->mrt->priority[n];
740 node_a->mrt->results[n] =
741 node_b->mrt->results[n];
747 * If the two node transitions intersect then merge the transitions.
748 * Check intersection for entire node (all pointers)
750 node_intersect_type = acl_intersect_type(&node_a->values,
754 if (node_intersect_type & ACL_INTERSECT) {
756 b_full = acl_full(node_b);
758 min_add_b = node_b->min_add;
759 node_b->min_add = node_b->num_ptrs;
760 ptrs_b = node_b->num_ptrs;
762 min_add_a = node_a->min_add;
763 node_a->min_add = node_a->num_ptrs;
764 ptrs_a = node_a->num_ptrs;
766 for (n = 0; n < ptrs_a; n++) {
767 for (m = 0; m < ptrs_b; m++) {
769 if (node_a->ptrs[n].ptr == NULL ||
770 node_b->ptrs[m].ptr == NULL ||
771 node_a->ptrs[n].ptr ==
775 intersect_type = acl_intersect_type(
776 &node_a->ptrs[n].values,
777 &node_b->ptrs[m].values,
780 /* If this node is not a 'match' node */
781 if ((intersect_type & ACL_INTERSECT) &&
782 (context->cfg.num_categories != 1 ||
783 !(node_a->ptrs[n].ptr->match_flag))) {
786 * next merge is a 'move' pointer,
787 * if this one is and B is a
788 * subset of the intersection.
792 ACL_INTERSECT_B) == 0;
794 if (a_subset && b_full) {
795 rc = acl_merge(context,
803 rc = acl_merge_intersect(
805 node_b, m, next_move,
806 level, &intersect_ptr);
815 /* Compact pointers */
816 node_a->min_add = min_add_a;
817 acl_compact_node_ptrs(node_a);
818 node_b->min_add = min_add_b;
819 acl_compact_node_ptrs(node_b);
822 * Either COPY or MOVE pointers from B to A
824 acl_intersect(&node_a->values, &node_b->values, &intersect_values);
826 if (move && node_b->ref_count == 1) {
827 for (m = 0; m < node_b->num_ptrs; m++) {
828 if (node_b->ptrs[m].ptr != NULL &&
829 acl_move_ptr(context, node_a, node_b, m,
830 &intersect_values) < 0)
834 for (m = 0; m < node_b->num_ptrs; m++) {
835 if (node_b->ptrs[m].ptr != NULL &&
836 acl_copy_ptr(context, node_a, node_b, m,
837 &intersect_values) < 0)
843 * Free node if its empty (no longer used)
845 if (acl_empty(node_b))
846 acl_free_node(context, node_b);
851 acl_resolve_leaf(struct acl_build_context *context,
852 struct rte_acl_node *node_a,
853 struct rte_acl_node *node_b,
854 struct rte_acl_node **node_c)
857 int combined_priority = ACL_PRIORITY_EQUAL;
859 for (n = 0; n < context->cfg.num_categories; n++) {
860 if (node_a->mrt->priority[n] != node_b->mrt->priority[n]) {
861 combined_priority |= (node_a->mrt->priority[n] >
862 node_b->mrt->priority[n]) ?
863 ACL_PRIORITY_NODE_A : ACL_PRIORITY_NODE_B;
868 * if node a is higher or equal priority for all categories,
869 * then return node_a.
871 if (combined_priority == ACL_PRIORITY_NODE_A ||
872 combined_priority == ACL_PRIORITY_EQUAL) {
878 * if node b is higher or equal priority for all categories,
879 * then return node_b.
881 if (combined_priority == ACL_PRIORITY_NODE_B) {
887 * mixed priorities - create a new node with the highest priority
891 /* force new duplication. */
894 *node_c = acl_dup_node(context, node_a);
895 for (n = 0; n < context->cfg.num_categories; n++) {
896 if ((*node_c)->mrt->priority[n] < node_b->mrt->priority[n]) {
897 (*node_c)->mrt->priority[n] = node_b->mrt->priority[n];
898 (*node_c)->mrt->results[n] = node_b->mrt->results[n];
905 * Merge nodes A and B together,
906 * returns a node that is the path for the intersection
908 * If match node (leaf on trie)
910 * return node = highest priority result
912 * Create C as a duplicate of A to point to child intersections
913 * If any pointers in C intersect with any in B
914 * For each intersection
916 * remove intersection from C pointer
917 * add a pointer from C to child intersection node
918 * Compact the pointers in A and B
919 * Copy any B pointers that are outside of the intersection to C
920 * If C has no references to the B trie
921 * free C and return A
922 * Else If C has no references to the A trie
923 * free C and return B
928 acl_merge_trie(struct acl_build_context *context,
929 struct rte_acl_node *node_a, struct rte_acl_node *node_b,
930 uint32_t level, struct rte_acl_node **return_c)
932 uint32_t n, m, ptrs_c, ptrs_b;
933 uint32_t min_add_c, min_add_b;
934 int node_intersect_type;
935 struct rte_acl_bitset node_intersect;
936 struct rte_acl_node *node_c;
937 struct rte_acl_node *node_a_next;
942 node_a_next = node_a->next;
945 node_a_refs = node_a->num_ptrs;
947 node_intersect_type = 0;
949 /* Resolve leaf nodes (matches) */
950 if (node_a->match_flag != 0) {
951 acl_resolve_leaf(context, node_a, node_b, return_c);
956 * Create node C as a copy of node A, and do: C = merge(A,B);
957 * If node A can be used instead (A==C), then later we'll
958 * destroy C and return A.
961 node_c = acl_dup_node(context, node_a);
964 * If the two node transitions intersect then merge the transitions.
965 * Check intersection for entire node (all pointers)
967 node_intersect_type = acl_intersect_type(&node_c->values,
971 if (node_intersect_type & ACL_INTERSECT) {
973 min_add_b = node_b->min_add;
974 node_b->min_add = node_b->num_ptrs;
975 ptrs_b = node_b->num_ptrs;
977 min_add_c = node_c->min_add;
978 node_c->min_add = node_c->num_ptrs;
979 ptrs_c = node_c->num_ptrs;
981 for (n = 0; n < ptrs_c; n++) {
982 if (node_c->ptrs[n].ptr == NULL) {
986 node_c->ptrs[n].ptr->next = NULL;
987 for (m = 0; m < ptrs_b; m++) {
989 struct rte_acl_bitset child_intersect;
990 int child_intersect_type;
991 struct rte_acl_node *child_node_c = NULL;
993 if (node_b->ptrs[m].ptr == NULL ||
994 node_c->ptrs[n].ptr ==
998 child_intersect_type = acl_intersect_type(
999 &node_c->ptrs[n].values,
1000 &node_b->ptrs[m].values,
1003 if ((child_intersect_type & ACL_INTERSECT) !=
1005 if (acl_merge_trie(context,
1006 node_c->ptrs[n].ptr,
1007 node_b->ptrs[m].ptr,
1012 if (child_node_c != NULL &&
1014 node_c->ptrs[n].ptr) {
1019 * Added link from C to
1020 * child_C for all transitions
1021 * in the intersection.
1023 acl_add_ptr(context, node_c,
1028 * inc refs if pointer is not
1031 node_a_refs += (child_node_c !=
1032 node_b->ptrs[m].ptr);
1035 * Remove intersection from C
1039 &node_c->ptrs[n].values,
1040 &node_c->ptrs[n].values,
1041 &child_intersect)) {
1042 acl_deref_ptr(context,
1044 node_c->ptrs[n].ptr =
1053 /* Compact pointers */
1054 node_c->min_add = min_add_c;
1055 acl_compact_node_ptrs(node_c);
1056 node_b->min_add = min_add_b;
1057 acl_compact_node_ptrs(node_b);
1061 * Copy pointers outside of the intersection from B to C
1063 if ((node_intersect_type & ACL_INTERSECT_B) != 0) {
1065 for (m = 0; m < node_b->num_ptrs; m++)
1066 if (node_b->ptrs[m].ptr != NULL)
1067 acl_copy_ptr(context, node_c,
1068 node_b, m, &node_intersect);
1072 * Free node C if top of trie is contained in A or B
1073 * if node C is a duplicate of node A &&
1074 * node C was not an existing duplicate
1076 if (node_c != node_a && node_c != node_a_next) {
1079 * if the intersection has no references to the
1080 * B side, then it is contained in A
1082 if (node_b_refs == 0) {
1083 acl_free_node(context, node_c);
1087 * if the intersection has no references to the
1088 * A side, then it is contained in B.
1090 if (node_a_refs == 0) {
1091 acl_free_node(context, node_c);
1097 if (return_c != NULL)
1101 acl_free_node(context, node_b);
1107 * Reset current runtime fields before next build:
1108 * - free allocated RT memory.
1109 * - reset all RT related fields to zero.
1112 acl_build_reset(struct rte_acl_ctx *ctx)
1115 memset(&ctx->num_categories, 0,
1116 sizeof(*ctx) - offsetof(struct rte_acl_ctx, num_categories));
1120 acl_gen_range(struct acl_build_context *context,
1121 const uint8_t *hi, const uint8_t *lo, int size, int level,
1122 struct rte_acl_node *root, struct rte_acl_node *end)
1124 struct rte_acl_node *node, *prev;
1128 for (n = size - 1; n > 0; n--) {
1129 node = acl_alloc_node(context, level++);
1130 acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
1133 acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
1136 static struct rte_acl_node *
1137 acl_gen_range_trie(struct acl_build_context *context,
1138 const void *min, const void *max,
1139 int size, int level, struct rte_acl_node **pend)
1142 struct rte_acl_node *root;
1143 const uint8_t *lo = (const uint8_t *)min;
1144 const uint8_t *hi = (const uint8_t *)max;
1146 *pend = acl_alloc_node(context, level+size);
1147 root = acl_alloc_node(context, level++);
1149 if (lo[size - 1] == hi[size - 1]) {
1150 acl_gen_range(context, hi, lo, size, level, root, *pend);
1152 uint8_t limit_lo[64];
1153 uint8_t limit_hi[64];
1154 uint8_t hi_ff = UINT8_MAX;
1157 memset(limit_lo, 0, RTE_DIM(limit_lo));
1158 memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi));
1160 for (n = size - 2; n >= 0; n--) {
1161 hi_ff = (uint8_t)(hi_ff & hi[n]);
1162 lo_00 = (uint8_t)(lo_00 | lo[n]);
1165 if (hi_ff != UINT8_MAX) {
1166 limit_lo[size - 1] = hi[size - 1];
1167 acl_gen_range(context, hi, limit_lo, size, level,
1172 limit_hi[size - 1] = lo[size - 1];
1173 acl_gen_range(context, limit_hi, lo, size, level,
1177 if (hi[size - 1] - lo[size - 1] > 1 ||
1179 hi_ff == UINT8_MAX) {
1180 limit_lo[size-1] = (uint8_t)(lo[size-1] + (lo_00 != 0));
1181 limit_hi[size-1] = (uint8_t)(hi[size-1] -
1182 (hi_ff != UINT8_MAX));
1183 acl_gen_range(context, limit_hi, limit_lo, size,
1184 level, root, *pend);
1190 static struct rte_acl_node *
1191 acl_gen_mask_trie(struct acl_build_context *context,
1192 const void *value, const void *mask,
1193 int size, int level, struct rte_acl_node **pend)
1196 struct rte_acl_node *root;
1197 struct rte_acl_node *node, *prev;
1198 struct rte_acl_bitset bits;
1199 const uint8_t *val = (const uint8_t *)value;
1200 const uint8_t *msk = (const uint8_t *)mask;
1202 root = acl_alloc_node(context, level++);
1205 for (n = size - 1; n >= 0; n--) {
1206 node = acl_alloc_node(context, level++);
1207 acl_gen_mask(&bits, val[n] & msk[n], msk[n]);
1208 acl_add_ptr(context, prev, node, &bits);
1216 static struct rte_acl_node *
1217 build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
1218 struct rte_acl_build_rule **last, uint32_t *count)
1221 int field_index, node_count;
1222 struct rte_acl_node *trie;
1223 struct rte_acl_build_rule *prev, *rule;
1224 struct rte_acl_node *end, *merge, *root, *end_prev;
1225 const struct rte_acl_field *fld;
1231 trie = acl_alloc_node(context, 0);
1233 while (rule != NULL) {
1235 root = acl_alloc_node(context, 0);
1237 root->ref_count = 1;
1240 for (n = 0; n < rule->config->num_fields; n++) {
1242 field_index = rule->config->defs[n].field_index;
1243 fld = rule->f->field + field_index;
1246 /* build a mini-trie for this field */
1247 switch (rule->config->defs[n].type) {
1249 case RTE_ACL_FIELD_TYPE_BITMASK:
1250 merge = acl_gen_mask_trie(context,
1253 rule->config->defs[n].size,
1258 case RTE_ACL_FIELD_TYPE_MASK:
1261 * set msb for the size of the field and
1266 if (fld->mask_range.u32 == 0) {
1270 * arithmetic right shift for the length of
1271 * the mask less the msb.
1275 (rule->config->defs[n].size *
1276 CHAR_BIT - fld->mask_range.u32);
1279 /* gen a mini-trie for this field */
1280 merge = acl_gen_mask_trie(context,
1283 rule->config->defs[n].size,
1289 case RTE_ACL_FIELD_TYPE_RANGE:
1290 merge = acl_gen_range_trie(context,
1291 &rule->f->field[field_index].value,
1292 &rule->f->field[field_index].mask_range,
1293 rule->config->defs[n].size,
1300 "Error in rule[%u] type - %hhu\n",
1301 rule->f->data.userdata,
1302 rule->config->defs[n].type);
1306 /* merge this field on to the end of the rule */
1307 if (acl_merge_trie(context, end_prev, merge, 0,
1313 end->match_flag = ++context->num_build_rules;
1316 * Setup the results for this rule.
1317 * The result and priority of each category.
1319 if (end->mrt == NULL)
1320 end->mrt = acl_build_alloc(context, 1,
1323 for (m = context->cfg.num_categories; 0 != m--; ) {
1324 if (rule->f->data.category_mask & (1 << m)) {
1325 end->mrt->results[m] = rule->f->data.userdata;
1326 end->mrt->priority[m] = rule->f->data.priority;
1328 end->mrt->results[m] = 0;
1329 end->mrt->priority[m] = 0;
1333 node_count = context->num_nodes;
1336 /* merge this rule into the trie */
1337 if (acl_merge_trie(context, trie, root, 0, NULL))
1340 node_count = context->num_nodes - node_count;
1341 if (node_count > context->cur_node_max) {
1355 acl_calc_wildness(struct rte_acl_build_rule *head,
1356 const struct rte_acl_config *config)
1359 struct rte_acl_build_rule *rule;
1361 for (rule = head; rule != NULL; rule = rule->next) {
1363 for (n = 0; n < config->num_fields; n++) {
1366 uint32_t bit_len = CHAR_BIT * config->defs[n].size;
1367 uint64_t msk_val = RTE_LEN2MASK(bit_len,
1369 double size = bit_len;
1370 int field_index = config->defs[n].field_index;
1371 const struct rte_acl_field *fld = rule->f->field +
1374 switch (rule->config->defs[n].type) {
1375 case RTE_ACL_FIELD_TYPE_BITMASK:
1376 wild = (size - __builtin_popcountll(
1377 fld->mask_range.u64 & msk_val)) /
1381 case RTE_ACL_FIELD_TYPE_MASK:
1382 wild = (size - fld->mask_range.u32) / size;
1385 case RTE_ACL_FIELD_TYPE_RANGE:
1386 wild = (fld->mask_range.u64 & msk_val) -
1387 (fld->value.u64 & msk_val);
1388 wild = wild / msk_val;
1392 rule->wildness[field_index] = (uint32_t)(wild * 100);
1398 acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config)
1400 struct rte_acl_build_rule *rule;
1401 uint32_t n, m, fields_deactivated = 0;
1402 uint32_t start = 0, deactivate = 0;
1403 int tally[RTE_ACL_MAX_LEVELS][TALLY_NUM];
1405 memset(tally, 0, sizeof(tally));
1407 for (rule = head; rule != NULL; rule = rule->next) {
1409 for (n = 0; n < config->num_fields; n++) {
1410 uint32_t field_index = config->defs[n].field_index;
1412 tally[n][TALLY_0]++;
1413 for (m = 1; m < RTE_DIM(wild_limits); m++) {
1414 if (rule->wildness[field_index] >=
1420 for (n = config->num_fields - 1; n > 0; n--) {
1421 uint32_t field_index = config->defs[n].field_index;
1423 if (rule->wildness[field_index] == 100)
1424 tally[n][TALLY_DEPTH]++;
1431 * Look for any field that is always wild and drop it from the config
1432 * Only deactivate if all fields for a given input loop are deactivated.
1434 for (n = 1; n < config->num_fields; n++) {
1435 if (config->defs[n].input_index !=
1436 config->defs[n - 1].input_index) {
1437 for (m = start; m < n; m++)
1438 tally[m][TALLY_DEACTIVATED] = deactivate;
1439 fields_deactivated += deactivate;
1444 /* if the field is not always completely wild */
1445 if (tally[n][TALLY_100] != tally[n][TALLY_0])
1449 for (m = start; m < n; m++)
1450 tally[m][TALLY_DEACTIVATED] = deactivate;
1452 fields_deactivated += deactivate;
1454 /* remove deactivated fields */
1455 if (fields_deactivated) {
1458 for (k = 0; k < config->num_fields; k++) {
1459 if (tally[k][TALLY_DEACTIVATED] == 0) {
1460 memmove(&tally[l][0], &tally[k][0],
1461 TALLY_NUM * sizeof(tally[0][0]));
1462 memmove(&config->defs[l++],
1464 sizeof(struct rte_acl_field_def));
1467 config->num_fields = l;
1472 rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2)
1476 for (n = 1; n < r1->config->num_fields; n++) {
1477 int field_index = r1->config->defs[n].field_index;
1479 if (r1->wildness[field_index] != r2->wildness[field_index])
1480 return (r1->wildness[field_index] -
1481 r2->wildness[field_index]);
1487 * Sort list of rules based on the rules wildness.
1489 static struct rte_acl_build_rule *
1490 sort_rules(struct rte_acl_build_rule *head)
1492 struct rte_acl_build_rule *new_head;
1493 struct rte_acl_build_rule *l, *r, **p;
1496 while (head != NULL) {
1498 /* remove element from the head of the old list. */
1503 /* walk through new sorted list to find a proper place. */
1506 rule_cmp_wildness(l, r) >= 0;
1510 /* insert element into the new sorted list. */
1519 acl_build_index(const struct rte_acl_config *config, uint32_t *data_index)
1522 int32_t last_header;
1527 for (n = 0; n < config->num_fields; n++) {
1528 if (last_header != config->defs[n].input_index) {
1529 last_header = config->defs[n].input_index;
1530 data_index[m++] = config->defs[n].offset;
1537 static struct rte_acl_build_rule *
1538 build_one_trie(struct acl_build_context *context,
1539 struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],
1540 uint32_t n, int32_t node_max)
1542 struct rte_acl_build_rule *last;
1543 struct rte_acl_config *config;
1545 config = rule_sets[n]->config;
1547 acl_rule_stats(rule_sets[n], config);
1548 rule_sets[n] = sort_rules(rule_sets[n]);
1550 context->tries[n].type = RTE_ACL_FULL_TRIE;
1551 context->tries[n].count = 0;
1553 context->tries[n].num_data_indexes = acl_build_index(config,
1554 context->data_indexes[n]);
1555 context->tries[n].data_index = context->data_indexes[n];
1557 context->cur_node_max = node_max;
1559 context->bld_tries[n].trie = build_trie(context, rule_sets[n],
1560 &last, &context->tries[n].count);
1566 acl_build_tries(struct acl_build_context *context,
1567 struct rte_acl_build_rule *head)
1569 uint32_t n, num_tries;
1570 struct rte_acl_config *config;
1571 struct rte_acl_build_rule *last;
1572 struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES];
1574 config = head->config;
1575 rule_sets[0] = head;
1577 /* initialize tries */
1578 for (n = 0; n < RTE_DIM(context->tries); n++) {
1579 context->tries[n].type = RTE_ACL_UNUSED_TRIE;
1580 context->bld_tries[n].trie = NULL;
1581 context->tries[n].count = 0;
1584 context->tries[0].type = RTE_ACL_FULL_TRIE;
1586 /* calc wildness of each field of each rule */
1587 acl_calc_wildness(head, config);
1589 for (n = 0;; n = num_tries) {
1593 last = build_one_trie(context, rule_sets, n, context->node_max);
1594 if (context->bld_tries[n].trie == NULL) {
1595 RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1599 /* Build of the last trie completed. */
1603 if (num_tries == RTE_DIM(context->tries)) {
1605 "Exceeded max number of tries: %u\n",
1610 /* Trie is getting too big, split remaining rule set. */
1611 rule_sets[num_tries] = last->next;
1613 acl_free_node(context, context->bld_tries[n].trie);
1615 /* Create a new copy of config for remaining rules. */
1616 config = acl_build_alloc(context, 1, sizeof(*config));
1617 memcpy(config, rule_sets[n]->config, sizeof(*config));
1619 /* Make remaining rules use new config. */
1620 for (head = rule_sets[num_tries]; head != NULL;
1622 head->config = config;
1625 * Rebuild the trie for the reduced rule-set.
1626 * Don't try to split it any further.
1628 last = build_one_trie(context, rule_sets, n, INT32_MAX);
1629 if (context->bld_tries[n].trie == NULL || last != NULL) {
1630 RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1636 context->num_tries = num_tries;
1641 acl_build_log(const struct acl_build_context *ctx)
1645 RTE_LOG(DEBUG, ACL, "Build phase for ACL \"%s\":\n"
1646 "node limit for tree split: %u\n"
1647 "nodes created: %u\n"
1648 "memory consumed: %zu\n",
1654 for (n = 0; n < RTE_DIM(ctx->tries); n++) {
1655 if (ctx->tries[n].count != 0)
1657 "trie %u: number of rules: %u, indexes: %u\n",
1658 n, ctx->tries[n].count,
1659 ctx->tries[n].num_data_indexes);
1664 acl_build_rules(struct acl_build_context *bcx)
1666 struct rte_acl_build_rule *br, *head;
1667 const struct rte_acl_rule *rule;
1669 uint32_t fn, i, n, num;
1672 fn = bcx->cfg.num_fields;
1673 n = bcx->acx->num_rules;
1674 ofs = n * sizeof(*br);
1675 sz = ofs + n * fn * sizeof(*wp);
1677 br = tb_alloc(&bcx->pool, sz);
1679 wp = (uint32_t *)((uintptr_t)br + ofs);
1683 for (i = 0; i != n; i++) {
1684 rule = (const struct rte_acl_rule *)
1685 ((uintptr_t)bcx->acx->rules + bcx->acx->rule_sz * i);
1686 if ((rule->data.category_mask & bcx->category_mask) != 0) {
1687 br[num].next = head;
1688 br[num].config = &bcx->cfg;
1690 br[num].wildness = wp;
1697 bcx->num_rules = num;
1698 bcx->build_rules = head;
1704 * Copy data_indexes for each trie into RT location.
1707 acl_set_data_indexes(struct rte_acl_ctx *ctx)
1712 for (i = 0; i != ctx->num_tries; i++) {
1713 n = ctx->trie[i].num_data_indexes;
1714 memcpy(ctx->data_indexes + ofs, ctx->trie[i].data_index,
1715 n * sizeof(ctx->data_indexes[0]));
1716 ctx->trie[i].data_index = ctx->data_indexes + ofs;
1717 ofs += RTE_ACL_MAX_FIELDS;
1722 * Internal routine, performs 'build' phase of trie generation:
1723 * - setups build context.
1724 * - analizes given set of rules.
1725 * - builds internal tree(s).
1728 acl_bld(struct acl_build_context *bcx, struct rte_acl_ctx *ctx,
1729 const struct rte_acl_config *cfg, uint32_t node_max)
1733 /* setup build context. */
1734 memset(bcx, 0, sizeof(*bcx));
1736 bcx->pool.alignment = ACL_POOL_ALIGN;
1737 bcx->pool.min_alloc = ACL_POOL_ALLOC_MIN;
1739 bcx->category_mask = RTE_LEN2MASK(bcx->cfg.num_categories,
1740 typeof(bcx->category_mask));
1741 bcx->node_max = node_max;
1743 rc = sigsetjmp(bcx->pool.fail, 0);
1745 /* build phase runs out of memory. */
1748 "ACL context: %s, %s() failed with error code: %d\n",
1749 bcx->acx->name, __func__, rc);
1753 /* Create a build rules copy. */
1754 rc = acl_build_rules(bcx);
1758 /* No rules to build for that context+config */
1759 if (bcx->build_rules == NULL) {
1762 /* build internal trie representation. */
1763 rc = acl_build_tries(bcx, bcx->build_rules);
1769 * Check that parameters for acl_build() are valid.
1772 acl_check_bld_param(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1774 static const size_t field_sizes[] = {
1775 sizeof(uint8_t), sizeof(uint16_t),
1776 sizeof(uint32_t), sizeof(uint64_t),
1781 if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
1782 cfg->num_categories > RTE_ACL_MAX_CATEGORIES ||
1783 cfg->num_fields == 0 ||
1784 cfg->num_fields > RTE_ACL_MAX_FIELDS)
1787 for (i = 0; i != cfg->num_fields; i++) {
1788 if (cfg->defs[i].type > RTE_ACL_FIELD_TYPE_BITMASK) {
1790 "ACL context: %s, invalid type: %hhu for %u-th field\n",
1791 ctx->name, cfg->defs[i].type, i);
1795 j != RTE_DIM(field_sizes) &&
1796 cfg->defs[i].size != field_sizes[j];
1800 if (j == RTE_DIM(field_sizes)) {
1802 "ACL context: %s, invalid size: %hhu for %u-th field\n",
1803 ctx->name, cfg->defs[i].size, i);
1812 rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1817 struct acl_build_context bcx;
1819 rc = acl_check_bld_param(ctx, cfg);
1823 acl_build_reset(ctx);
1825 if (cfg->max_size == 0) {
1827 max_size = SIZE_MAX;
1830 max_size = cfg->max_size;
1833 for (rc = -ERANGE; n >= NODE_MIN && rc == -ERANGE; n /= 2) {
1835 /* perform build phase. */
1836 rc = acl_bld(&bcx, ctx, cfg, n);
1839 /* allocate and fill run-time structures. */
1840 rc = rte_acl_gen(ctx, bcx.tries, bcx.bld_tries,
1841 bcx.num_tries, bcx.cfg.num_categories,
1842 RTE_ACL_MAX_FIELDS * RTE_DIM(bcx.tries) *
1843 sizeof(ctx->data_indexes[0]), max_size);
1845 /* set data indexes. */
1846 acl_set_data_indexes(ctx);
1848 /* copy in build config. */
1853 acl_build_log(&bcx);
1855 /* cleanup after build. */
1856 tb_free_pool(&bcx.pool);