1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
9 #define ACL_POOL_ALIGN 8
10 #define ACL_POOL_ALLOC_MIN 0x800000
12 /* number of pointers per alloc */
13 #define ACL_PTR_ALLOC 32
15 /* account for situation when all fields are 8B long */
16 #define ACL_MAX_INDEXES (2 * RTE_ACL_MAX_FIELDS)
18 /* macros for dividing rule sets heuristics */
19 #define NODE_MAX 0x4000
20 #define NODE_MIN 0x800
22 /* TALLY are statistics per field */
24 TALLY_0 = 0, /* number of rules that are 0% or more wild. */
25 TALLY_25, /* number of rules that are 25% or more wild. */
29 TALLY_DEACTIVATED, /* deactivated fields (100% wild in all rules). */
31 /* number of rules that are 100% wild for this field and higher. */
35 static const uint32_t wild_limits[TALLY_DEACTIVATED] = {0, 25, 50, 75, 100};
38 ACL_INTERSECT_NONE = 0,
39 ACL_INTERSECT_A = 1, /* set A is a superset of A and B intersect */
40 ACL_INTERSECT_B = 2, /* set B is a superset of A and B intersect */
41 ACL_INTERSECT = 4, /* sets A and B intersect */
45 ACL_PRIORITY_EQUAL = 0,
46 ACL_PRIORITY_NODE_A = 1,
47 ACL_PRIORITY_NODE_B = 2,
48 ACL_PRIORITY_MIXED = 3
52 struct acl_mem_block {
57 #define MEM_BLOCK_NUM 16
59 /* Single ACL rule, build representation.*/
60 struct rte_acl_build_rule {
61 struct rte_acl_build_rule *next;
62 struct rte_acl_config *config;
63 /**< configuration for each field in the rule. */
64 const struct rte_acl_rule *f;
68 /* Context for build phase */
69 struct acl_build_context {
70 const struct rte_acl_ctx *acx;
71 struct rte_acl_build_rule *build_rules;
72 struct rte_acl_config cfg;
77 uint32_t category_mask;
81 uint32_t num_build_rules;
83 struct tb_mem_pool pool;
84 struct rte_acl_trie tries[RTE_ACL_MAX_TRIES];
85 struct rte_acl_bld_trie bld_tries[RTE_ACL_MAX_TRIES];
86 uint32_t data_indexes[RTE_ACL_MAX_TRIES][ACL_MAX_INDEXES];
88 /* memory free lists for nodes and blocks used for node ptrs */
89 struct acl_mem_block blocks[MEM_BLOCK_NUM];
90 struct rte_acl_node *node_free_list;
93 static int acl_merge_trie(struct acl_build_context *context,
94 struct rte_acl_node *node_a, struct rte_acl_node *node_b,
95 uint32_t level, struct rte_acl_node **node_c);
98 acl_deref_ptr(struct acl_build_context *context,
99 struct rte_acl_node *node, int index);
102 acl_build_alloc(struct acl_build_context *context, size_t n, size_t s)
106 size_t alloc_size = n * s;
109 * look for memory in free lists
111 for (m = 0; m < RTE_DIM(context->blocks); m++) {
112 if (context->blocks[m].block_size ==
113 alloc_size && context->blocks[m].mem_ptr != NULL) {
114 p = context->blocks[m].mem_ptr;
115 context->blocks[m].mem_ptr = *((void **)p);
116 memset(p, 0, alloc_size);
122 * return allocation from memory pool
124 p = tb_alloc(&context->pool, alloc_size);
129 * Free memory blocks (kept in context for reuse).
132 acl_build_free(struct acl_build_context *context, size_t s, void *p)
136 for (n = 0; n < RTE_DIM(context->blocks); n++) {
137 if (context->blocks[n].block_size == s) {
138 *((void **)p) = context->blocks[n].mem_ptr;
139 context->blocks[n].mem_ptr = p;
143 for (n = 0; n < RTE_DIM(context->blocks); n++) {
144 if (context->blocks[n].block_size == 0) {
145 context->blocks[n].block_size = s;
146 *((void **)p) = NULL;
147 context->blocks[n].mem_ptr = p;
154 * Allocate and initialize a new node.
156 static struct rte_acl_node *
157 acl_alloc_node(struct acl_build_context *context, int level)
159 struct rte_acl_node *node;
161 if (context->node_free_list != NULL) {
162 node = context->node_free_list;
163 context->node_free_list = node->next;
164 memset(node, 0, sizeof(struct rte_acl_node));
166 node = acl_build_alloc(context, sizeof(struct rte_acl_node), 1);
172 node->node_type = RTE_ACL_NODE_UNDEFINED;
173 node->node_index = RTE_ACL_NODE_UNDEFINED;
174 context->num_nodes++;
175 node->id = context->node_id++;
181 * Dereference all nodes to which this node points
184 acl_free_node(struct acl_build_context *context,
185 struct rte_acl_node *node)
189 if (node->prev != NULL)
190 node->prev->next = NULL;
191 for (n = 0; n < node->num_ptrs; n++)
192 acl_deref_ptr(context, node, n);
194 /* free mrt if this is a match node */
195 if (node->mrt != NULL) {
196 acl_build_free(context, sizeof(struct rte_acl_match_results),
201 /* free transitions to other nodes */
202 if (node->ptrs != NULL) {
203 acl_build_free(context,
204 node->max_ptrs * sizeof(struct rte_acl_ptr_set),
209 /* put it on the free list */
210 context->num_nodes--;
211 node->next = context->node_free_list;
212 context->node_free_list = node;
217 * Include src bitset in dst bitset
220 acl_include(struct rte_acl_bitset *dst, struct rte_acl_bitset *src, bits_t mask)
224 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
225 dst->bits[n] = (dst->bits[n] & mask) | src->bits[n];
229 * Set dst to bits of src1 that are not in src2
232 acl_exclude(struct rte_acl_bitset *dst,
233 struct rte_acl_bitset *src1,
234 struct rte_acl_bitset *src2)
239 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
240 dst->bits[n] = src1->bits[n] & ~src2->bits[n];
241 all_bits |= dst->bits[n];
243 return all_bits != 0;
247 * Add a pointer (ptr) to a node.
250 acl_add_ptr(struct acl_build_context *context,
251 struct rte_acl_node *node,
252 struct rte_acl_node *ptr,
253 struct rte_acl_bitset *bits)
255 uint32_t n, num_ptrs;
256 struct rte_acl_ptr_set *ptrs = NULL;
259 * If there's already a pointer to the same node, just add to the bitset
261 for (n = 0; n < node->num_ptrs; n++) {
262 if (node->ptrs[n].ptr != NULL) {
263 if (node->ptrs[n].ptr == ptr) {
264 acl_include(&node->ptrs[n].values, bits, -1);
265 acl_include(&node->values, bits, -1);
271 /* if there's no room for another pointer, make room */
272 if (node->num_ptrs >= node->max_ptrs) {
273 /* add room for more pointers */
274 num_ptrs = node->max_ptrs + ACL_PTR_ALLOC;
275 ptrs = acl_build_alloc(context, num_ptrs, sizeof(*ptrs));
277 /* copy current points to new memory allocation */
278 if (node->ptrs != NULL) {
279 memcpy(ptrs, node->ptrs,
280 node->num_ptrs * sizeof(*ptrs));
281 acl_build_free(context, node->max_ptrs * sizeof(*ptrs),
285 node->max_ptrs = num_ptrs;
288 /* Find available ptr and add a new pointer to this node */
289 for (n = node->min_add; n < node->max_ptrs; n++) {
290 if (node->ptrs[n].ptr == NULL) {
291 node->ptrs[n].ptr = ptr;
292 acl_include(&node->ptrs[n].values, bits, 0);
293 acl_include(&node->values, bits, -1);
296 if (node->num_ptrs <= n)
297 node->num_ptrs = n + 1;
306 * Add a pointer for a range of values
309 acl_add_ptr_range(struct acl_build_context *context,
310 struct rte_acl_node *root,
311 struct rte_acl_node *node,
316 struct rte_acl_bitset bitset;
318 /* clear the bitset values */
319 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
322 /* for each bit in range, add bit to set */
323 for (n = 0; n < UINT8_MAX + 1; n++)
324 if (n >= low && n <= high)
325 bitset.bits[n / (sizeof(bits_t) * 8)] |=
326 1U << (n % (sizeof(bits_t) * CHAR_BIT));
328 return acl_add_ptr(context, root, node, &bitset);
332 * Generate a bitset from a byte value and mask.
335 acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
340 /* clear the bitset values */
341 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
344 /* for each bit in value/mask, add bit to set */
345 for (n = 0; n < UINT8_MAX + 1; n++) {
346 if ((n & mask) == value) {
348 bitset->bits[n / (sizeof(bits_t) * 8)] |=
349 1U << (n % (sizeof(bits_t) * CHAR_BIT));
356 * Determine how A and B intersect.
357 * Determine if A and/or B are supersets of the intersection.
360 acl_intersect_type(const struct rte_acl_bitset *a_bits,
361 const struct rte_acl_bitset *b_bits,
362 struct rte_acl_bitset *intersect)
365 bits_t intersect_bits = 0;
366 bits_t a_superset = 0;
367 bits_t b_superset = 0;
370 * calculate and store intersection and check if A and/or B have
371 * bits outside the intersection (superset)
373 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
374 intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
375 a_superset |= a_bits->bits[n] ^ intersect->bits[n];
376 b_superset |= b_bits->bits[n] ^ intersect->bits[n];
377 intersect_bits |= intersect->bits[n];
380 n = (intersect_bits == 0 ? ACL_INTERSECT_NONE : ACL_INTERSECT) |
381 (b_superset == 0 ? 0 : ACL_INTERSECT_B) |
382 (a_superset == 0 ? 0 : ACL_INTERSECT_A);
390 static struct rte_acl_node *
391 acl_dup_node(struct acl_build_context *context, struct rte_acl_node *node)
394 struct rte_acl_node *next;
396 next = acl_alloc_node(context, node->level);
398 /* allocate the pointers */
399 if (node->num_ptrs > 0) {
400 next->ptrs = acl_build_alloc(context,
402 sizeof(struct rte_acl_ptr_set));
403 next->max_ptrs = node->max_ptrs;
406 /* copy over the pointers */
407 for (n = 0; n < node->num_ptrs; n++) {
408 if (node->ptrs[n].ptr != NULL) {
409 next->ptrs[n].ptr = node->ptrs[n].ptr;
410 next->ptrs[n].ptr->ref_count++;
411 acl_include(&next->ptrs[n].values,
412 &node->ptrs[n].values, -1);
416 next->num_ptrs = node->num_ptrs;
418 /* copy over node's match results */
419 if (node->match_flag == 0)
420 next->match_flag = 0;
422 next->match_flag = -1;
423 next->mrt = acl_build_alloc(context, 1, sizeof(*next->mrt));
424 memcpy(next->mrt, node->mrt, sizeof(*next->mrt));
427 /* copy over node's bitset */
428 acl_include(&next->values, &node->values, -1);
437 * Dereference a pointer from a node
440 acl_deref_ptr(struct acl_build_context *context,
441 struct rte_acl_node *node, int index)
443 struct rte_acl_node *ref_node;
445 /* De-reference the node at the specified pointer */
446 if (node != NULL && node->ptrs[index].ptr != NULL) {
447 ref_node = node->ptrs[index].ptr;
448 ref_node->ref_count--;
449 if (ref_node->ref_count == 0)
450 acl_free_node(context, ref_node);
455 * acl_exclude rte_acl_bitset from src and copy remaining pointer to dst
458 acl_copy_ptr(struct acl_build_context *context,
459 struct rte_acl_node *dst,
460 struct rte_acl_node *src,
462 struct rte_acl_bitset *b_bits)
465 struct rte_acl_bitset bits;
468 if (!acl_exclude(&bits, &src->ptrs[index].values, b_bits))
471 rc = acl_add_ptr(context, dst, src->ptrs[index].ptr, &bits);
478 * Fill in gaps in ptrs list with the ptr at the end of the list
481 acl_compact_node_ptrs(struct rte_acl_node *node_a)
484 int min_add = node_a->min_add;
486 while (node_a->num_ptrs > 0 &&
487 node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
490 for (n = min_add; n + 1 < node_a->num_ptrs; n++) {
492 /* if this entry is empty */
493 if (node_a->ptrs[n].ptr == NULL) {
495 /* move the last pointer to this entry */
496 acl_include(&node_a->ptrs[n].values,
497 &node_a->ptrs[node_a->num_ptrs - 1].values,
499 node_a->ptrs[n].ptr =
500 node_a->ptrs[node_a->num_ptrs - 1].ptr;
503 * mark the end as empty and adjust the number
504 * of used pointer enum_tries
506 node_a->ptrs[node_a->num_ptrs - 1].ptr = NULL;
507 while (node_a->num_ptrs > 0 &&
508 node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
515 acl_resolve_leaf(struct acl_build_context *context,
516 struct rte_acl_node *node_a,
517 struct rte_acl_node *node_b,
518 struct rte_acl_node **node_c)
521 int combined_priority = ACL_PRIORITY_EQUAL;
523 for (n = 0; n < context->cfg.num_categories; n++) {
524 if (node_a->mrt->priority[n] != node_b->mrt->priority[n]) {
525 combined_priority |= (node_a->mrt->priority[n] >
526 node_b->mrt->priority[n]) ?
527 ACL_PRIORITY_NODE_A : ACL_PRIORITY_NODE_B;
532 * if node a is higher or equal priority for all categories,
533 * then return node_a.
535 if (combined_priority == ACL_PRIORITY_NODE_A ||
536 combined_priority == ACL_PRIORITY_EQUAL) {
542 * if node b is higher or equal priority for all categories,
543 * then return node_b.
545 if (combined_priority == ACL_PRIORITY_NODE_B) {
551 * mixed priorities - create a new node with the highest priority
555 /* force new duplication. */
558 *node_c = acl_dup_node(context, node_a);
559 for (n = 0; n < context->cfg.num_categories; n++) {
560 if ((*node_c)->mrt->priority[n] < node_b->mrt->priority[n]) {
561 (*node_c)->mrt->priority[n] = node_b->mrt->priority[n];
562 (*node_c)->mrt->results[n] = node_b->mrt->results[n];
569 * Merge nodes A and B together,
570 * returns a node that is the path for the intersection
572 * If match node (leaf on trie)
574 * return node = highest priority result
576 * Create C as a duplicate of A to point to child intersections
577 * If any pointers in C intersect with any in B
578 * For each intersection
580 * remove intersection from C pointer
581 * add a pointer from C to child intersection node
582 * Compact the pointers in A and B
583 * Copy any B pointers that are outside of the intersection to C
584 * If C has no references to the B trie
585 * free C and return A
586 * Else If C has no references to the A trie
587 * free C and return B
592 acl_merge_trie(struct acl_build_context *context,
593 struct rte_acl_node *node_a, struct rte_acl_node *node_b,
594 uint32_t level, struct rte_acl_node **return_c)
596 uint32_t n, m, ptrs_c, ptrs_b;
597 uint32_t min_add_c, min_add_b;
598 int node_intersect_type;
599 struct rte_acl_bitset node_intersect;
600 struct rte_acl_node *node_c;
601 struct rte_acl_node *node_a_next;
606 node_a_next = node_a->next;
609 node_a_refs = node_a->num_ptrs;
611 node_intersect_type = 0;
613 /* Resolve leaf nodes (matches) */
614 if (node_a->match_flag != 0) {
615 acl_resolve_leaf(context, node_a, node_b, return_c);
620 * Create node C as a copy of node A, and do: C = merge(A,B);
621 * If node A can be used instead (A==C), then later we'll
622 * destroy C and return A.
625 node_c = acl_dup_node(context, node_a);
628 * If the two node transitions intersect then merge the transitions.
629 * Check intersection for entire node (all pointers)
631 node_intersect_type = acl_intersect_type(&node_c->values,
635 if (node_intersect_type & ACL_INTERSECT) {
637 min_add_b = node_b->min_add;
638 node_b->min_add = node_b->num_ptrs;
639 ptrs_b = node_b->num_ptrs;
641 min_add_c = node_c->min_add;
642 node_c->min_add = node_c->num_ptrs;
643 ptrs_c = node_c->num_ptrs;
645 for (n = 0; n < ptrs_c; n++) {
646 if (node_c->ptrs[n].ptr == NULL) {
650 node_c->ptrs[n].ptr->next = NULL;
651 for (m = 0; m < ptrs_b; m++) {
653 struct rte_acl_bitset child_intersect;
654 int child_intersect_type;
655 struct rte_acl_node *child_node_c = NULL;
657 if (node_b->ptrs[m].ptr == NULL ||
658 node_c->ptrs[n].ptr ==
662 child_intersect_type = acl_intersect_type(
663 &node_c->ptrs[n].values,
664 &node_b->ptrs[m].values,
667 if ((child_intersect_type & ACL_INTERSECT) !=
669 if (acl_merge_trie(context,
676 if (child_node_c != NULL &&
678 node_c->ptrs[n].ptr) {
683 * Added link from C to
684 * child_C for all transitions
685 * in the intersection.
687 acl_add_ptr(context, node_c,
692 * inc refs if pointer is not
695 node_a_refs += (child_node_c !=
696 node_b->ptrs[m].ptr);
699 * Remove intersection from C
703 &node_c->ptrs[n].values,
704 &node_c->ptrs[n].values,
706 acl_deref_ptr(context,
708 node_c->ptrs[n].ptr =
717 /* Compact pointers */
718 node_c->min_add = min_add_c;
719 acl_compact_node_ptrs(node_c);
720 node_b->min_add = min_add_b;
721 acl_compact_node_ptrs(node_b);
725 * Copy pointers outside of the intersection from B to C
727 if ((node_intersect_type & ACL_INTERSECT_B) != 0) {
729 for (m = 0; m < node_b->num_ptrs; m++)
730 if (node_b->ptrs[m].ptr != NULL)
731 acl_copy_ptr(context, node_c,
732 node_b, m, &node_intersect);
736 * Free node C if top of trie is contained in A or B
737 * if node C is a duplicate of node A &&
738 * node C was not an existing duplicate
740 if (node_c != node_a && node_c != node_a_next) {
743 * if the intersection has no references to the
744 * B side, then it is contained in A
746 if (node_b_refs == 0) {
747 acl_free_node(context, node_c);
751 * if the intersection has no references to the
752 * A side, then it is contained in B.
754 if (node_a_refs == 0) {
755 acl_free_node(context, node_c);
761 if (return_c != NULL)
765 acl_free_node(context, node_b);
771 * Reset current runtime fields before next build:
772 * - free allocated RT memory.
773 * - reset all RT related fields to zero.
776 acl_build_reset(struct rte_acl_ctx *ctx)
779 memset(&ctx->num_categories, 0,
780 sizeof(*ctx) - offsetof(struct rte_acl_ctx, num_categories));
784 acl_gen_full_range(struct acl_build_context *context, struct rte_acl_node *root,
785 struct rte_acl_node *end, int size, int level)
787 struct rte_acl_node *node, *prev;
791 for (n = size - 1; n > 0; n--) {
792 node = acl_alloc_node(context, level++);
793 acl_add_ptr_range(context, prev, node, 0, UINT8_MAX);
796 acl_add_ptr_range(context, prev, end, 0, UINT8_MAX);
800 acl_gen_range_mdl(struct acl_build_context *context, struct rte_acl_node *root,
801 struct rte_acl_node *end, uint8_t lo, uint8_t hi, int size, int level)
803 struct rte_acl_node *node;
805 node = acl_alloc_node(context, level++);
806 acl_add_ptr_range(context, root, node, lo, hi);
807 acl_gen_full_range(context, node, end, size - 1, level);
811 acl_gen_range_low(struct acl_build_context *context, struct rte_acl_node *root,
812 struct rte_acl_node *end, const uint8_t *lo, int size, int level)
814 struct rte_acl_node *node;
819 acl_add_ptr_range(context, root, end, lo[0], UINT8_MAX);
823 node = acl_alloc_node(context, level++);
824 acl_add_ptr_range(context, root, node, lo[n], lo[n]);
826 /* generate lower-bound sub-trie */
827 acl_gen_range_low(context, node, end, lo, n, level);
829 /* generate middle sub-trie */
830 if (n > 1 && lo[n - 1] != UINT8_MAX)
831 acl_gen_range_mdl(context, node, end, lo[n - 1] + 1, UINT8_MAX,
836 acl_gen_range_high(struct acl_build_context *context, struct rte_acl_node *root,
837 struct rte_acl_node *end, const uint8_t *hi, int size, int level)
839 struct rte_acl_node *node;
844 acl_add_ptr_range(context, root, end, 0, hi[0]);
848 node = acl_alloc_node(context, level++);
849 acl_add_ptr_range(context, root, node, hi[n], hi[n]);
851 /* generate upper-bound sub-trie */
852 acl_gen_range_high(context, node, end, hi, n, level);
854 /* generate middle sub-trie */
855 if (n > 1 && hi[n - 1] != 0)
856 acl_gen_range_mdl(context, node, end, 0, hi[n - 1] - 1,
860 static struct rte_acl_node *
861 acl_gen_range_trie(struct acl_build_context *context,
862 const void *min, const void *max,
863 int size, int level, struct rte_acl_node **pend)
866 uint8_t hi_ff, lo_00;
867 struct rte_acl_node *node, *prev, *root;
874 *pend = acl_alloc_node(context, level + size);
875 root = acl_alloc_node(context, level++);
878 /* build common sub-trie till possible */
879 for (n = size - 1; n > 0 && lo[n] == hi[n]; n--) {
880 node = acl_alloc_node(context, level++);
881 acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
885 /* no branch needed, just one sub-trie */
887 acl_add_ptr_range(context, prev, *pend, lo[0], hi[0]);
891 /* gather information about divergent paths */
894 for (k = n - 1; k >= 0; k--) {
899 /* generate left (lower-bound) sub-trie */
901 acl_gen_range_low(context, prev, *pend, lo, n + 1, level);
903 /* generate right (upper-bound) sub-trie */
904 if (hi_ff != UINT8_MAX)
905 acl_gen_range_high(context, prev, *pend, hi, n + 1, level);
907 /* generate sub-trie in the middle */
908 if (lo[n] + 1 != hi[n] || lo_00 == 0 || hi_ff == UINT8_MAX) {
909 lo_00 = lo[n] + (lo_00 != 0);
910 hi_ff = hi[n] - (hi_ff != UINT8_MAX);
911 acl_gen_range_mdl(context, prev, *pend, lo_00, hi_ff,
918 static struct rte_acl_node *
919 acl_gen_mask_trie(struct acl_build_context *context,
920 const void *value, const void *mask,
921 int size, int level, struct rte_acl_node **pend)
924 struct rte_acl_node *root;
925 struct rte_acl_node *node, *prev;
926 struct rte_acl_bitset bits;
927 const uint8_t *val = value;
928 const uint8_t *msk = mask;
930 root = acl_alloc_node(context, level++);
933 for (n = size - 1; n >= 0; n--) {
934 node = acl_alloc_node(context, level++);
935 acl_gen_mask(&bits, val[n] & msk[n], msk[n]);
936 acl_add_ptr(context, prev, node, &bits);
944 static struct rte_acl_node *
945 build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
946 struct rte_acl_build_rule **last, uint32_t *count)
949 int field_index, node_count;
950 struct rte_acl_node *trie;
951 struct rte_acl_build_rule *prev, *rule;
952 struct rte_acl_node *end, *merge, *root, *end_prev;
953 const struct rte_acl_field *fld;
959 trie = acl_alloc_node(context, 0);
961 while (rule != NULL) {
963 root = acl_alloc_node(context, 0);
968 for (n = 0; n < rule->config->num_fields; n++) {
970 field_index = rule->config->defs[n].field_index;
971 fld = rule->f->field + field_index;
974 /* build a mini-trie for this field */
975 switch (rule->config->defs[n].type) {
977 case RTE_ACL_FIELD_TYPE_BITMASK:
978 merge = acl_gen_mask_trie(context,
981 rule->config->defs[n].size,
986 case RTE_ACL_FIELD_TYPE_MASK:
989 * set msb for the size of the field and
993 mask = RTE_ACL_MASKLEN_TO_BITMASK(
995 rule->config->defs[n].size);
997 /* gen a mini-trie for this field */
998 merge = acl_gen_mask_trie(context,
1001 rule->config->defs[n].size,
1007 case RTE_ACL_FIELD_TYPE_RANGE:
1008 merge = acl_gen_range_trie(context,
1009 &rule->f->field[field_index].value,
1010 &rule->f->field[field_index].mask_range,
1011 rule->config->defs[n].size,
1018 "Error in rule[%u] type - %hhu\n",
1019 rule->f->data.userdata,
1020 rule->config->defs[n].type);
1024 /* merge this field on to the end of the rule */
1025 if (acl_merge_trie(context, end_prev, merge, 0,
1031 end->match_flag = ++context->num_build_rules;
1034 * Setup the results for this rule.
1035 * The result and priority of each category.
1037 if (end->mrt == NULL)
1038 end->mrt = acl_build_alloc(context, 1,
1041 for (m = context->cfg.num_categories; 0 != m--; ) {
1042 if (rule->f->data.category_mask & (1U << m)) {
1043 end->mrt->results[m] = rule->f->data.userdata;
1044 end->mrt->priority[m] = rule->f->data.priority;
1046 end->mrt->results[m] = 0;
1047 end->mrt->priority[m] = 0;
1051 node_count = context->num_nodes;
1054 /* merge this rule into the trie */
1055 if (acl_merge_trie(context, trie, root, 0, NULL))
1058 node_count = context->num_nodes - node_count;
1059 if (node_count > context->cur_node_max) {
1073 acl_calc_wildness(struct rte_acl_build_rule *head,
1074 const struct rte_acl_config *config)
1077 struct rte_acl_build_rule *rule;
1079 for (rule = head; rule != NULL; rule = rule->next) {
1081 for (n = 0; n < config->num_fields; n++) {
1084 uint32_t bit_len = CHAR_BIT * config->defs[n].size;
1085 uint64_t msk_val = RTE_LEN2MASK(bit_len,
1087 double size = bit_len;
1088 int field_index = config->defs[n].field_index;
1089 const struct rte_acl_field *fld = rule->f->field +
1092 switch (rule->config->defs[n].type) {
1093 case RTE_ACL_FIELD_TYPE_BITMASK:
1094 wild = (size - __builtin_popcountll(
1095 fld->mask_range.u64 & msk_val)) /
1099 case RTE_ACL_FIELD_TYPE_MASK:
1100 wild = (size - fld->mask_range.u32) / size;
1103 case RTE_ACL_FIELD_TYPE_RANGE:
1104 wild = (fld->mask_range.u64 & msk_val) -
1105 (fld->value.u64 & msk_val);
1106 wild = wild / msk_val;
1110 rule->wildness[field_index] = (uint32_t)(wild * 100);
1116 acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config)
1118 struct rte_acl_build_rule *rule;
1119 uint32_t n, m, fields_deactivated = 0;
1120 uint32_t start = 0, deactivate = 0;
1121 int tally[RTE_ACL_MAX_LEVELS][TALLY_NUM];
1123 memset(tally, 0, sizeof(tally));
1125 for (rule = head; rule != NULL; rule = rule->next) {
1127 for (n = 0; n < config->num_fields; n++) {
1128 uint32_t field_index = config->defs[n].field_index;
1130 tally[n][TALLY_0]++;
1131 for (m = 1; m < RTE_DIM(wild_limits); m++) {
1132 if (rule->wildness[field_index] >=
1138 for (n = config->num_fields - 1; n > 0; n--) {
1139 uint32_t field_index = config->defs[n].field_index;
1141 if (rule->wildness[field_index] == 100)
1142 tally[n][TALLY_DEPTH]++;
1149 * Look for any field that is always wild and drop it from the config
1150 * Only deactivate if all fields for a given input loop are deactivated.
1152 for (n = 1; n < config->num_fields; n++) {
1153 if (config->defs[n].input_index !=
1154 config->defs[n - 1].input_index) {
1155 for (m = start; m < n; m++)
1156 tally[m][TALLY_DEACTIVATED] = deactivate;
1157 fields_deactivated += deactivate;
1162 /* if the field is not always completely wild */
1163 if (tally[n][TALLY_100] != tally[n][TALLY_0])
1167 for (m = start; m < n; m++)
1168 tally[m][TALLY_DEACTIVATED] = deactivate;
1170 fields_deactivated += deactivate;
1172 /* remove deactivated fields */
1173 if (fields_deactivated) {
1176 for (k = 0; k < config->num_fields; k++) {
1177 if (tally[k][TALLY_DEACTIVATED] == 0) {
1178 memmove(&tally[l][0], &tally[k][0],
1179 TALLY_NUM * sizeof(tally[0][0]));
1180 memmove(&config->defs[l++],
1182 sizeof(struct rte_acl_field_def));
1185 config->num_fields = l;
1190 rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2)
1194 for (n = 1; n < r1->config->num_fields; n++) {
1195 int field_index = r1->config->defs[n].field_index;
1197 if (r1->wildness[field_index] != r2->wildness[field_index])
1198 return r1->wildness[field_index] -
1199 r2->wildness[field_index];
1205 * Split the rte_acl_build_rule list into two lists.
1208 rule_list_split(struct rte_acl_build_rule *source,
1209 struct rte_acl_build_rule **list_a,
1210 struct rte_acl_build_rule **list_b)
1212 struct rte_acl_build_rule *fast;
1213 struct rte_acl_build_rule *slow;
1215 if (source == NULL || source->next == NULL) {
1216 /* length < 2 cases */
1221 fast = source->next;
1222 /* Advance 'fast' two nodes, and advance 'slow' one node */
1223 while (fast != NULL) {
1230 /* 'slow' is before the midpoint in the list, so split it in two
1233 *list_b = slow->next;
1239 * Merge two sorted lists.
1241 static struct rte_acl_build_rule *
1242 rule_list_sorted_merge(struct rte_acl_build_rule *a,
1243 struct rte_acl_build_rule *b)
1245 struct rte_acl_build_rule *result = NULL;
1246 struct rte_acl_build_rule **last_next = &result;
1252 } else if (b == NULL) {
1256 if (rule_cmp_wildness(a, b) >= 0) {
1258 last_next = &a->next;
1262 last_next = &b->next;
1270 * Sort list of rules based on the rules wildness.
1271 * Use recursive mergesort algorithm.
1273 static struct rte_acl_build_rule *
1274 sort_rules(struct rte_acl_build_rule *head)
1276 struct rte_acl_build_rule *a;
1277 struct rte_acl_build_rule *b;
1279 /* Base case -- length 0 or 1 */
1280 if (head == NULL || head->next == NULL)
1283 /* Split head into 'a' and 'b' sublists */
1284 rule_list_split(head, &a, &b);
1286 /* Recursively sort the sublists */
1290 /* answer = merge the two sorted lists together */
1291 return rule_list_sorted_merge(a, b);
1295 acl_build_index(const struct rte_acl_config *config, uint32_t *data_index)
1298 int32_t last_header;
1303 for (n = 0; n < config->num_fields; n++) {
1304 if (last_header != config->defs[n].input_index) {
1305 last_header = config->defs[n].input_index;
1306 data_index[m++] = config->defs[n].offset;
1307 if (config->defs[n].size > sizeof(uint32_t))
1308 data_index[m++] = config->defs[n].offset +
1316 static struct rte_acl_build_rule *
1317 build_one_trie(struct acl_build_context *context,
1318 struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],
1319 uint32_t n, int32_t node_max)
1321 struct rte_acl_build_rule *last;
1322 struct rte_acl_config *config;
1324 config = rule_sets[n]->config;
1326 acl_rule_stats(rule_sets[n], config);
1327 rule_sets[n] = sort_rules(rule_sets[n]);
1329 context->tries[n].type = RTE_ACL_FULL_TRIE;
1330 context->tries[n].count = 0;
1332 context->tries[n].num_data_indexes = acl_build_index(config,
1333 context->data_indexes[n]);
1334 context->tries[n].data_index = context->data_indexes[n];
1336 context->cur_node_max = node_max;
1338 context->bld_tries[n].trie = build_trie(context, rule_sets[n],
1339 &last, &context->tries[n].count);
1345 acl_build_tries(struct acl_build_context *context,
1346 struct rte_acl_build_rule *head)
1348 uint32_t n, num_tries;
1349 struct rte_acl_config *config;
1350 struct rte_acl_build_rule *last;
1351 struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES];
1353 config = head->config;
1354 rule_sets[0] = head;
1356 /* initialize tries */
1357 for (n = 0; n < RTE_DIM(context->tries); n++) {
1358 context->tries[n].type = RTE_ACL_UNUSED_TRIE;
1359 context->bld_tries[n].trie = NULL;
1360 context->tries[n].count = 0;
1363 context->tries[0].type = RTE_ACL_FULL_TRIE;
1365 /* calc wildness of each field of each rule */
1366 acl_calc_wildness(head, config);
1368 for (n = 0;; n = num_tries) {
1372 last = build_one_trie(context, rule_sets, n, context->node_max);
1373 if (context->bld_tries[n].trie == NULL) {
1374 RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1378 /* Build of the last trie completed. */
1382 if (num_tries == RTE_DIM(context->tries)) {
1384 "Exceeded max number of tries: %u\n",
1389 /* Trie is getting too big, split remaining rule set. */
1390 rule_sets[num_tries] = last->next;
1392 acl_free_node(context, context->bld_tries[n].trie);
1394 /* Create a new copy of config for remaining rules. */
1395 config = acl_build_alloc(context, 1, sizeof(*config));
1396 memcpy(config, rule_sets[n]->config, sizeof(*config));
1398 /* Make remaining rules use new config. */
1399 for (head = rule_sets[num_tries]; head != NULL;
1401 head->config = config;
1404 * Rebuild the trie for the reduced rule-set.
1405 * Don't try to split it any further.
1407 last = build_one_trie(context, rule_sets, n, INT32_MAX);
1408 if (context->bld_tries[n].trie == NULL || last != NULL) {
1409 RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1415 context->num_tries = num_tries;
1420 acl_build_log(const struct acl_build_context *ctx)
1424 RTE_LOG(DEBUG, ACL, "Build phase for ACL \"%s\":\n"
1425 "node limit for tree split: %u\n"
1426 "nodes created: %u\n"
1427 "memory consumed: %zu\n",
1433 for (n = 0; n < RTE_DIM(ctx->tries); n++) {
1434 if (ctx->tries[n].count != 0)
1436 "trie %u: number of rules: %u, indexes: %u\n",
1437 n, ctx->tries[n].count,
1438 ctx->tries[n].num_data_indexes);
1443 acl_build_rules(struct acl_build_context *bcx)
1445 struct rte_acl_build_rule *br, *head;
1446 const struct rte_acl_rule *rule;
1448 uint32_t fn, i, n, num;
1451 fn = bcx->cfg.num_fields;
1452 n = bcx->acx->num_rules;
1453 ofs = n * sizeof(*br);
1454 sz = ofs + n * fn * sizeof(*wp);
1456 br = tb_alloc(&bcx->pool, sz);
1458 wp = (uint32_t *)((uintptr_t)br + ofs);
1462 for (i = 0; i != n; i++) {
1463 rule = (const struct rte_acl_rule *)
1464 ((uintptr_t)bcx->acx->rules + bcx->acx->rule_sz * i);
1465 if ((rule->data.category_mask & bcx->category_mask) != 0) {
1466 br[num].next = head;
1467 br[num].config = &bcx->cfg;
1469 br[num].wildness = wp;
1476 bcx->num_rules = num;
1477 bcx->build_rules = head;
1483 * Copy data_indexes for each trie into RT location.
1486 acl_set_data_indexes(struct rte_acl_ctx *ctx)
1491 for (i = 0; i != ctx->num_tries; i++) {
1492 n = ctx->trie[i].num_data_indexes;
1493 memcpy(ctx->data_indexes + ofs, ctx->trie[i].data_index,
1494 n * sizeof(ctx->data_indexes[0]));
1495 ctx->trie[i].data_index = ctx->data_indexes + ofs;
1496 ofs += ACL_MAX_INDEXES;
1501 * Internal routine, performs 'build' phase of trie generation:
1502 * - setups build context.
1503 * - analyzes given set of rules.
1504 * - builds internal tree(s).
1507 acl_bld(struct acl_build_context *bcx, struct rte_acl_ctx *ctx,
1508 const struct rte_acl_config *cfg, uint32_t node_max)
1512 /* setup build context. */
1513 memset(bcx, 0, sizeof(*bcx));
1515 bcx->pool.alignment = ACL_POOL_ALIGN;
1516 bcx->pool.min_alloc = ACL_POOL_ALLOC_MIN;
1518 bcx->category_mask = RTE_LEN2MASK(bcx->cfg.num_categories,
1519 typeof(bcx->category_mask));
1520 bcx->node_max = node_max;
1522 rc = sigsetjmp(bcx->pool.fail, 0);
1524 /* build phase runs out of memory. */
1527 "ACL context: %s, %s() failed with error code: %d\n",
1528 bcx->acx->name, __func__, rc);
1532 /* Create a build rules copy. */
1533 rc = acl_build_rules(bcx);
1537 /* No rules to build for that context+config */
1538 if (bcx->build_rules == NULL) {
1541 /* build internal trie representation. */
1542 rc = acl_build_tries(bcx, bcx->build_rules);
1548 * Check that parameters for acl_build() are valid.
1551 acl_check_bld_param(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1553 static const size_t field_sizes[] = {
1554 sizeof(uint8_t), sizeof(uint16_t),
1555 sizeof(uint32_t), sizeof(uint64_t),
1560 if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
1561 cfg->num_categories > RTE_ACL_MAX_CATEGORIES ||
1562 cfg->num_fields == 0 ||
1563 cfg->num_fields > RTE_ACL_MAX_FIELDS)
1566 for (i = 0; i != cfg->num_fields; i++) {
1567 if (cfg->defs[i].type > RTE_ACL_FIELD_TYPE_BITMASK) {
1569 "ACL context: %s, invalid type: %hhu for %u-th field\n",
1570 ctx->name, cfg->defs[i].type, i);
1574 j != RTE_DIM(field_sizes) &&
1575 cfg->defs[i].size != field_sizes[j];
1579 if (j == RTE_DIM(field_sizes)) {
1581 "ACL context: %s, invalid size: %hhu for %u-th field\n",
1582 ctx->name, cfg->defs[i].size, i);
1591 * With current ACL implementation first field in the rule definition
1592 * has always to be one byte long. Though for optimising *classify*
1593 * implementation it might be useful to be able to use 4B reads
1594 * (as we do for rest of the fields).
1595 * This function checks input config to determine is it safe to do 4B
1596 * loads for first ACL field. For that we need to make sure that
1597 * first field in our rule definition doesn't have the biggest offset,
1598 * i.e. we still do have other fields located after the first one.
1599 * Contrary if first field has the largest offset, then it means
1600 * first field can occupy the very last byte in the input data buffer,
1601 * and we have to do single byte load for it.
1604 get_first_load_size(const struct rte_acl_config *cfg)
1606 uint32_t i, max_ofs, ofs;
1611 for (i = 0; i != cfg->num_fields; i++) {
1612 if (cfg->defs[i].field_index == 0)
1613 ofs = cfg->defs[i].offset;
1614 else if (max_ofs < cfg->defs[i].offset)
1615 max_ofs = cfg->defs[i].offset;
1618 return (ofs < max_ofs) ? sizeof(uint32_t) : sizeof(uint8_t);
1622 rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1627 struct acl_build_context bcx;
1629 rc = acl_check_bld_param(ctx, cfg);
1633 acl_build_reset(ctx);
1635 if (cfg->max_size == 0) {
1637 max_size = SIZE_MAX;
1640 max_size = cfg->max_size;
1643 for (rc = -ERANGE; n >= NODE_MIN && rc == -ERANGE; n /= 2) {
1645 /* perform build phase. */
1646 rc = acl_bld(&bcx, ctx, cfg, n);
1649 /* allocate and fill run-time structures. */
1650 rc = rte_acl_gen(ctx, bcx.tries, bcx.bld_tries,
1651 bcx.num_tries, bcx.cfg.num_categories,
1652 ACL_MAX_INDEXES * RTE_DIM(bcx.tries) *
1653 sizeof(ctx->data_indexes[0]), max_size);
1655 /* set data indexes. */
1656 acl_set_data_indexes(ctx);
1658 /* determine can we always do 4B load */
1659 ctx->first_load_sz = get_first_load_size(cfg);
1661 /* copy in build config. */
1666 acl_build_log(&bcx);
1668 /* cleanup after build. */
1669 tb_free_pool(&bcx.pool);