doc: move FAQ
[dpdk.git] / lib / librte_acl / acl_bld.c
1 /*-
2  *   BSD LICENSE
3  *
4  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5  *   All rights reserved.
6  *
7  *   Redistribution and use in source and binary forms, with or without
8  *   modification, are permitted provided that the following conditions
9  *   are met:
10  *
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
16  *       distribution.
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.
20  *
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.
32  */
33
34 #include <rte_acl.h>
35 #include "tb_mem.h"
36 #include "acl.h"
37
38 #define ACL_POOL_ALIGN          8
39 #define ACL_POOL_ALLOC_MIN      0x800000
40
41 /* number of pointers per alloc */
42 #define ACL_PTR_ALLOC   32
43
44 /* macros for dividing rule sets heuristics */
45 #define NODE_MAX        0x4000
46 #define NODE_MIN        0x800
47
48 /* TALLY are statistics per field */
49 enum {
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. */
52         TALLY_50,
53         TALLY_75,
54         TALLY_100,
55         TALLY_DEACTIVATED, /* deactivated fields (100% wild in all rules). */
56         TALLY_DEPTH,
57         /* number of rules that are 100% wild for this field and higher. */
58         TALLY_NUM
59 };
60
61 static const uint32_t wild_limits[TALLY_DEACTIVATED] = {0, 25, 50, 75, 100};
62
63 enum {
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 */
68 };
69
70 enum {
71         ACL_PRIORITY_EQUAL = 0,
72         ACL_PRIORITY_NODE_A = 1,
73         ACL_PRIORITY_NODE_B = 2,
74         ACL_PRIORITY_MIXED = 3
75 };
76
77
78 struct acl_mem_block {
79         uint32_t block_size;
80         void     *mem_ptr;
81 };
82
83 #define MEM_BLOCK_NUM   16
84
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;
91         uint32_t                    *wildness;
92 };
93
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;
99         int32_t                   node_max;
100         int32_t                   cur_node_max;
101         uint32_t                  node;
102         uint32_t                  num_nodes;
103         uint32_t                  category_mask;
104         uint32_t                  num_rules;
105         uint32_t                  node_id;
106         uint32_t                  src_mask;
107         uint32_t                  num_build_rules;
108         uint32_t                  num_tries;
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];
113
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;
117 };
118
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);
122
123 static void
124 acl_deref_ptr(struct acl_build_context *context,
125         struct rte_acl_node *node, int index);
126
127 static void *
128 acl_build_alloc(struct acl_build_context *context, size_t n, size_t s)
129 {
130         uint32_t m;
131         void *p;
132         size_t alloc_size = n * s;
133
134         /*
135          * look for memory in free lists
136          */
137         for (m = 0; m < RTE_DIM(context->blocks); m++) {
138                 if (context->blocks[m].block_size ==
139                    alloc_size && context->blocks[m].mem_ptr != NULL) {
140                         p = context->blocks[m].mem_ptr;
141                         context->blocks[m].mem_ptr = *((void **)p);
142                         memset(p, 0, alloc_size);
143                         return p;
144                 }
145         }
146
147         /*
148          * return allocation from memory pool
149          */
150         p = tb_alloc(&context->pool, alloc_size);
151         return p;
152 }
153
154 /*
155  * Free memory blocks (kept in context for reuse).
156  */
157 static void
158 acl_build_free(struct acl_build_context *context, size_t s, void *p)
159 {
160         uint32_t n;
161
162         for (n = 0; n < RTE_DIM(context->blocks); n++) {
163                 if (context->blocks[n].block_size == s) {
164                         *((void **)p) = context->blocks[n].mem_ptr;
165                         context->blocks[n].mem_ptr = p;
166                         return;
167                 }
168         }
169         for (n = 0; n < RTE_DIM(context->blocks); n++) {
170                 if (context->blocks[n].block_size == 0) {
171                         context->blocks[n].block_size = s;
172                         *((void **)p) = NULL;
173                         context->blocks[n].mem_ptr = p;
174                         return;
175                 }
176         }
177 }
178
179 /*
180  * Allocate and initialize a new node.
181  */
182 static struct rte_acl_node *
183 acl_alloc_node(struct acl_build_context *context, int level)
184 {
185         struct rte_acl_node *node;
186
187         if (context->node_free_list != NULL) {
188                 node = context->node_free_list;
189                 context->node_free_list = node->next;
190                 memset(node, 0, sizeof(struct rte_acl_node));
191         } else {
192                 node = acl_build_alloc(context, sizeof(struct rte_acl_node), 1);
193         }
194
195         if (node != NULL) {
196                 node->num_ptrs = 0;
197                 node->level = level;
198                 node->node_type = RTE_ACL_NODE_UNDEFINED;
199                 node->node_index = RTE_ACL_NODE_UNDEFINED;
200                 context->num_nodes++;
201                 node->id = context->node_id++;
202         }
203         return node;
204 }
205
206 /*
207  * Dereference all nodes to which this node points
208  */
209 static void
210 acl_free_node(struct acl_build_context *context,
211         struct rte_acl_node *node)
212 {
213         uint32_t n;
214
215         if (node->prev != NULL)
216                 node->prev->next = NULL;
217         for (n = 0; n < node->num_ptrs; n++)
218                 acl_deref_ptr(context, node, n);
219
220         /* free mrt if this is a match node */
221         if (node->mrt != NULL) {
222                 acl_build_free(context, sizeof(struct rte_acl_match_results),
223                         node->mrt);
224                 node->mrt = NULL;
225         }
226
227         /* free transitions to other nodes */
228         if (node->ptrs != NULL) {
229                 acl_build_free(context,
230                         node->max_ptrs * sizeof(struct rte_acl_ptr_set),
231                         node->ptrs);
232                 node->ptrs = NULL;
233         }
234
235         /* put it on the free list */
236         context->num_nodes--;
237         node->next = context->node_free_list;
238         context->node_free_list = node;
239 }
240
241
242 /*
243  * Include src bitset in dst bitset
244  */
245 static void
246 acl_include(struct rte_acl_bitset *dst, struct rte_acl_bitset *src, bits_t mask)
247 {
248         uint32_t n;
249
250         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
251                 dst->bits[n] = (dst->bits[n] & mask) | src->bits[n];
252 }
253
254 /*
255  * Set dst to bits of src1 that are not in src2
256  */
257 static int
258 acl_exclude(struct rte_acl_bitset *dst,
259         struct rte_acl_bitset *src1,
260         struct rte_acl_bitset *src2)
261 {
262         uint32_t n;
263         bits_t all_bits = 0;
264
265         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
266                 dst->bits[n] = src1->bits[n] & ~src2->bits[n];
267                 all_bits |= dst->bits[n];
268         }
269         return all_bits != 0;
270 }
271
272 /*
273  * Add a pointer (ptr) to a node.
274  */
275 static int
276 acl_add_ptr(struct acl_build_context *context,
277         struct rte_acl_node *node,
278         struct rte_acl_node *ptr,
279         struct rte_acl_bitset *bits)
280 {
281         uint32_t n, num_ptrs;
282         struct rte_acl_ptr_set *ptrs = NULL;
283
284         /*
285          * If there's already a pointer to the same node, just add to the bitset
286          */
287         for (n = 0; n < node->num_ptrs; n++) {
288                 if (node->ptrs[n].ptr != NULL) {
289                         if (node->ptrs[n].ptr == ptr) {
290                                 acl_include(&node->ptrs[n].values, bits, -1);
291                                 acl_include(&node->values, bits, -1);
292                                 return 0;
293                         }
294                 }
295         }
296
297         /* if there's no room for another pointer, make room */
298         if (node->num_ptrs >= node->max_ptrs) {
299                 /* add room for more pointers */
300                 num_ptrs = node->max_ptrs + ACL_PTR_ALLOC;
301                 ptrs = acl_build_alloc(context, num_ptrs, sizeof(*ptrs));
302
303                 /* copy current points to new memory allocation */
304                 if (node->ptrs != NULL) {
305                         memcpy(ptrs, node->ptrs,
306                                 node->num_ptrs * sizeof(*ptrs));
307                         acl_build_free(context, node->max_ptrs * sizeof(*ptrs),
308                                 node->ptrs);
309                 }
310                 node->ptrs = ptrs;
311                 node->max_ptrs = num_ptrs;
312         }
313
314         /* Find available ptr and add a new pointer to this node */
315         for (n = node->min_add; n < node->max_ptrs; n++) {
316                 if (node->ptrs[n].ptr == NULL) {
317                         node->ptrs[n].ptr = ptr;
318                         acl_include(&node->ptrs[n].values, bits, 0);
319                         acl_include(&node->values, bits, -1);
320                         if (ptr != NULL)
321                                 ptr->ref_count++;
322                         if (node->num_ptrs <= n)
323                                 node->num_ptrs = n + 1;
324                         return 0;
325                 }
326         }
327
328         return 0;
329 }
330
331 /*
332  * Add a pointer for a range of values
333  */
334 static int
335 acl_add_ptr_range(struct acl_build_context *context,
336         struct rte_acl_node *root,
337         struct rte_acl_node *node,
338         uint8_t low,
339         uint8_t high)
340 {
341         uint32_t n;
342         struct rte_acl_bitset bitset;
343
344         /* clear the bitset values */
345         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
346                 bitset.bits[n] = 0;
347
348         /* for each bit in range, add bit to set */
349         for (n = 0; n < UINT8_MAX + 1; n++)
350                 if (n >= low && n <= high)
351                         bitset.bits[n / (sizeof(bits_t) * 8)] |=
352                                 1 << (n % (sizeof(bits_t) * 8));
353
354         return acl_add_ptr(context, root, node, &bitset);
355 }
356
357 /*
358  * Generate a bitset from a byte value and mask.
359  */
360 static int
361 acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
362 {
363         int range = 0;
364         uint32_t n;
365
366         /* clear the bitset values */
367         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
368                 bitset->bits[n] = 0;
369
370         /* for each bit in value/mask, add bit to set */
371         for (n = 0; n < UINT8_MAX + 1; n++) {
372                 if ((n & mask) == value) {
373                         range++;
374                         bitset->bits[n / (sizeof(bits_t) * 8)] |=
375                                 1 << (n % (sizeof(bits_t) * 8));
376                 }
377         }
378         return range;
379 }
380
381 /*
382  * Determine how A and B intersect.
383  * Determine if A and/or B are supersets of the intersection.
384  */
385 static int
386 acl_intersect_type(const struct rte_acl_bitset *a_bits,
387         const struct rte_acl_bitset *b_bits,
388         struct rte_acl_bitset *intersect)
389 {
390         uint32_t n;
391         bits_t intersect_bits = 0;
392         bits_t a_superset = 0;
393         bits_t b_superset = 0;
394
395         /*
396          * calculate and store intersection and check if A and/or B have
397          * bits outside the intersection (superset)
398          */
399         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
400                 intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
401                 a_superset |= a_bits->bits[n] ^ intersect->bits[n];
402                 b_superset |= b_bits->bits[n] ^ intersect->bits[n];
403                 intersect_bits |= intersect->bits[n];
404         }
405
406         n = (intersect_bits == 0 ? ACL_INTERSECT_NONE : ACL_INTERSECT) |
407                 (b_superset == 0 ? 0 : ACL_INTERSECT_B) |
408                 (a_superset == 0 ? 0 : ACL_INTERSECT_A);
409
410         return n;
411 }
412
413 /*
414  * Duplicate a node
415  */
416 static struct rte_acl_node *
417 acl_dup_node(struct acl_build_context *context, struct rte_acl_node *node)
418 {
419         uint32_t n;
420         struct rte_acl_node *next;
421
422         next = acl_alloc_node(context, node->level);
423
424         /* allocate the pointers */
425         if (node->num_ptrs > 0) {
426                 next->ptrs = acl_build_alloc(context,
427                         node->max_ptrs,
428                         sizeof(struct rte_acl_ptr_set));
429                 next->max_ptrs = node->max_ptrs;
430         }
431
432         /* copy over the pointers */
433         for (n = 0; n < node->num_ptrs; n++) {
434                 if (node->ptrs[n].ptr != NULL) {
435                         next->ptrs[n].ptr = node->ptrs[n].ptr;
436                         next->ptrs[n].ptr->ref_count++;
437                         acl_include(&next->ptrs[n].values,
438                                 &node->ptrs[n].values, -1);
439                 }
440         }
441
442         next->num_ptrs = node->num_ptrs;
443
444         /* copy over node's match results */
445         if (node->match_flag == 0)
446                 next->match_flag = 0;
447         else {
448                 next->match_flag = -1;
449                 next->mrt = acl_build_alloc(context, 1, sizeof(*next->mrt));
450                 memcpy(next->mrt, node->mrt, sizeof(*next->mrt));
451         }
452
453         /* copy over node's bitset */
454         acl_include(&next->values, &node->values, -1);
455
456         node->next = next;
457         next->prev = node;
458
459         return next;
460 }
461
462 /*
463  * Dereference a pointer from a node
464  */
465 static void
466 acl_deref_ptr(struct acl_build_context *context,
467         struct rte_acl_node *node, int index)
468 {
469         struct rte_acl_node *ref_node;
470
471         /* De-reference the node at the specified pointer */
472         if (node != NULL && node->ptrs[index].ptr != NULL) {
473                 ref_node = node->ptrs[index].ptr;
474                 ref_node->ref_count--;
475                 if (ref_node->ref_count == 0)
476                         acl_free_node(context, ref_node);
477         }
478 }
479
480 /*
481  * acl_exclude rte_acl_bitset from src and copy remaining pointer to dst
482  */
483 static int
484 acl_copy_ptr(struct acl_build_context *context,
485         struct rte_acl_node *dst,
486         struct rte_acl_node *src,
487         int index,
488         struct rte_acl_bitset *b_bits)
489 {
490         int rc;
491         struct rte_acl_bitset bits;
492
493         if (b_bits != NULL)
494                 if (!acl_exclude(&bits, &src->ptrs[index].values, b_bits))
495                         return 0;
496
497         rc = acl_add_ptr(context, dst, src->ptrs[index].ptr, &bits);
498         if (rc < 0)
499                 return rc;
500         return 1;
501 }
502
503 /*
504  * Fill in gaps in ptrs list with the ptr at the end of the list
505  */
506 static void
507 acl_compact_node_ptrs(struct rte_acl_node *node_a)
508 {
509         uint32_t n;
510         int min_add = node_a->min_add;
511
512         while (node_a->num_ptrs > 0  &&
513                         node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
514                 node_a->num_ptrs--;
515
516         for (n = min_add; n + 1 < node_a->num_ptrs; n++) {
517
518                 /* if this entry is empty */
519                 if (node_a->ptrs[n].ptr == NULL) {
520
521                         /* move the last pointer to this entry */
522                         acl_include(&node_a->ptrs[n].values,
523                                 &node_a->ptrs[node_a->num_ptrs - 1].values,
524                                 0);
525                         node_a->ptrs[n].ptr =
526                                 node_a->ptrs[node_a->num_ptrs - 1].ptr;
527
528                         /*
529                          * mark the end as empty and adjust the number
530                          * of used pointer enum_tries
531                          */
532                         node_a->ptrs[node_a->num_ptrs - 1].ptr = NULL;
533                         while (node_a->num_ptrs > 0  &&
534                                 node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
535                                 node_a->num_ptrs--;
536                 }
537         }
538 }
539
540 static int
541 acl_resolve_leaf(struct acl_build_context *context,
542         struct rte_acl_node *node_a,
543         struct rte_acl_node *node_b,
544         struct rte_acl_node **node_c)
545 {
546         uint32_t n;
547         int combined_priority = ACL_PRIORITY_EQUAL;
548
549         for (n = 0; n < context->cfg.num_categories; n++) {
550                 if (node_a->mrt->priority[n] != node_b->mrt->priority[n]) {
551                         combined_priority |= (node_a->mrt->priority[n] >
552                                 node_b->mrt->priority[n]) ?
553                                 ACL_PRIORITY_NODE_A : ACL_PRIORITY_NODE_B;
554                 }
555         }
556
557         /*
558          * if node a is higher or equal priority for all categories,
559          * then return node_a.
560          */
561         if (combined_priority == ACL_PRIORITY_NODE_A ||
562                         combined_priority == ACL_PRIORITY_EQUAL) {
563                 *node_c = node_a;
564                 return 0;
565         }
566
567         /*
568          * if node b is higher or equal priority for all categories,
569          * then return node_b.
570          */
571         if (combined_priority == ACL_PRIORITY_NODE_B) {
572                 *node_c = node_b;
573                 return 0;
574         }
575
576         /*
577          * mixed priorities - create a new node with the highest priority
578          * for each category.
579          */
580
581         /* force new duplication. */
582         node_a->next = NULL;
583
584         *node_c = acl_dup_node(context, node_a);
585         for (n = 0; n < context->cfg.num_categories; n++) {
586                 if ((*node_c)->mrt->priority[n] < node_b->mrt->priority[n]) {
587                         (*node_c)->mrt->priority[n] = node_b->mrt->priority[n];
588                         (*node_c)->mrt->results[n] = node_b->mrt->results[n];
589                 }
590         }
591         return 0;
592 }
593
594 /*
595  * Merge nodes A and B together,
596  *   returns a node that is the path for the intersection
597  *
598  * If match node (leaf on trie)
599  *      For each category
600  *              return node = highest priority result
601  *
602  * Create C as a duplicate of A to point to child intersections
603  * If any pointers in C intersect with any in B
604  *      For each intersection
605  *              merge children
606  *              remove intersection from C pointer
607  *              add a pointer from C to child intersection node
608  * Compact the pointers in A and B
609  * Copy any B pointers that are outside of the intersection to C
610  * If C has no references to the B trie
611  *   free C and return A
612  * Else If C has no references to the A trie
613  *   free C and return B
614  * Else
615  *   return C
616  */
617 static int
618 acl_merge_trie(struct acl_build_context *context,
619         struct rte_acl_node *node_a, struct rte_acl_node *node_b,
620         uint32_t level, struct rte_acl_node **return_c)
621 {
622         uint32_t n, m, ptrs_c, ptrs_b;
623         uint32_t min_add_c, min_add_b;
624         int node_intersect_type;
625         struct rte_acl_bitset node_intersect;
626         struct rte_acl_node *node_c;
627         struct rte_acl_node *node_a_next;
628         int node_b_refs;
629         int node_a_refs;
630
631         node_c = node_a;
632         node_a_next = node_a->next;
633         min_add_c = 0;
634         min_add_b = 0;
635         node_a_refs = node_a->num_ptrs;
636         node_b_refs = 0;
637         node_intersect_type = 0;
638
639         /* Resolve leaf nodes (matches) */
640         if (node_a->match_flag != 0) {
641                 acl_resolve_leaf(context, node_a, node_b, return_c);
642                 return 0;
643         }
644
645         /*
646          * Create node C as a copy of node A, and do: C = merge(A,B);
647          * If node A can be used instead (A==C), then later we'll
648          * destroy C and return A.
649          */
650         if (level > 0)
651                 node_c = acl_dup_node(context, node_a);
652
653         /*
654          * If the two node transitions intersect then merge the transitions.
655          * Check intersection for entire node (all pointers)
656          */
657         node_intersect_type = acl_intersect_type(&node_c->values,
658                 &node_b->values,
659                 &node_intersect);
660
661         if (node_intersect_type & ACL_INTERSECT) {
662
663                 min_add_b = node_b->min_add;
664                 node_b->min_add = node_b->num_ptrs;
665                 ptrs_b = node_b->num_ptrs;
666
667                 min_add_c = node_c->min_add;
668                 node_c->min_add = node_c->num_ptrs;
669                 ptrs_c = node_c->num_ptrs;
670
671                 for (n = 0; n < ptrs_c; n++) {
672                         if (node_c->ptrs[n].ptr == NULL) {
673                                 node_a_refs--;
674                                 continue;
675                         }
676                         node_c->ptrs[n].ptr->next = NULL;
677                         for (m = 0; m < ptrs_b; m++) {
678
679                                 struct rte_acl_bitset child_intersect;
680                                 int child_intersect_type;
681                                 struct rte_acl_node *child_node_c = NULL;
682
683                                 if (node_b->ptrs[m].ptr == NULL ||
684                                                 node_c->ptrs[n].ptr ==
685                                                 node_b->ptrs[m].ptr)
686                                                 continue;
687
688                                 child_intersect_type = acl_intersect_type(
689                                         &node_c->ptrs[n].values,
690                                         &node_b->ptrs[m].values,
691                                         &child_intersect);
692
693                                 if ((child_intersect_type & ACL_INTERSECT) !=
694                                                 0) {
695                                         if (acl_merge_trie(context,
696                                                         node_c->ptrs[n].ptr,
697                                                         node_b->ptrs[m].ptr,
698                                                         level + 1,
699                                                         &child_node_c))
700                                                 return 1;
701
702                                         if (child_node_c != NULL &&
703                                                         child_node_c !=
704                                                         node_c->ptrs[n].ptr) {
705
706                                                 node_b_refs++;
707
708                                                 /*
709                                                  * Added link from C to
710                                                  * child_C for all transitions
711                                                  * in the intersection.
712                                                  */
713                                                 acl_add_ptr(context, node_c,
714                                                         child_node_c,
715                                                         &child_intersect);
716
717                                                 /*
718                                                  * inc refs if pointer is not
719                                                  * to node b.
720                                                  */
721                                                 node_a_refs += (child_node_c !=
722                                                         node_b->ptrs[m].ptr);
723
724                                                 /*
725                                                  * Remove intersection from C
726                                                  * pointer.
727                                                  */
728                                                 if (!acl_exclude(
729                                                         &node_c->ptrs[n].values,
730                                                         &node_c->ptrs[n].values,
731                                                         &child_intersect)) {
732                                                         acl_deref_ptr(context,
733                                                                 node_c, n);
734                                                         node_c->ptrs[n].ptr =
735                                                                 NULL;
736                                                         node_a_refs--;
737                                                 }
738                                         }
739                                 }
740                         }
741                 }
742
743                 /* Compact pointers */
744                 node_c->min_add = min_add_c;
745                 acl_compact_node_ptrs(node_c);
746                 node_b->min_add = min_add_b;
747                 acl_compact_node_ptrs(node_b);
748         }
749
750         /*
751          *  Copy pointers outside of the intersection from B to C
752          */
753         if ((node_intersect_type & ACL_INTERSECT_B) != 0) {
754                 node_b_refs++;
755                 for (m = 0; m < node_b->num_ptrs; m++)
756                         if (node_b->ptrs[m].ptr != NULL)
757                                 acl_copy_ptr(context, node_c,
758                                         node_b, m, &node_intersect);
759         }
760
761         /*
762          * Free node C if top of trie is contained in A or B
763          *  if node C is a duplicate of node A &&
764          *     node C was not an existing duplicate
765          */
766         if (node_c != node_a && node_c != node_a_next) {
767
768                 /*
769                  * if the intersection has no references to the
770                  * B side, then it is contained in A
771                  */
772                 if (node_b_refs == 0) {
773                         acl_free_node(context, node_c);
774                         node_c = node_a;
775                 } else {
776                         /*
777                          * if the intersection has no references to the
778                          * A side, then it is contained in B.
779                          */
780                         if (node_a_refs == 0) {
781                                 acl_free_node(context, node_c);
782                                 node_c = node_b;
783                         }
784                 }
785         }
786
787         if (return_c != NULL)
788                 *return_c = node_c;
789
790         if (level == 0)
791                 acl_free_node(context, node_b);
792
793         return 0;
794 }
795
796 /*
797  * Reset current runtime fields before next build:
798  *  - free allocated RT memory.
799  *  - reset all RT related fields to zero.
800  */
801 static void
802 acl_build_reset(struct rte_acl_ctx *ctx)
803 {
804         rte_free(ctx->mem);
805         memset(&ctx->num_categories, 0,
806                 sizeof(*ctx) - offsetof(struct rte_acl_ctx, num_categories));
807 }
808
809 static void
810 acl_gen_range(struct acl_build_context *context,
811         const uint8_t *hi, const uint8_t *lo, int size, int level,
812         struct rte_acl_node *root, struct rte_acl_node *end)
813 {
814         struct rte_acl_node *node, *prev;
815         uint32_t n;
816
817         prev = root;
818         for (n = size - 1; n > 0; n--) {
819                 node = acl_alloc_node(context, level++);
820                 acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
821                 prev = node;
822         }
823         acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
824 }
825
826 static struct rte_acl_node *
827 acl_gen_range_trie(struct acl_build_context *context,
828         const void *min, const void *max,
829         int size, int level, struct rte_acl_node **pend)
830 {
831         int32_t n;
832         struct rte_acl_node *root;
833         const uint8_t *lo = (const uint8_t *)min;
834         const uint8_t *hi = (const uint8_t *)max;
835
836         *pend = acl_alloc_node(context, level+size);
837         root = acl_alloc_node(context, level++);
838
839         if (lo[size - 1] == hi[size - 1]) {
840                 acl_gen_range(context, hi, lo, size, level, root, *pend);
841         } else {
842                 uint8_t limit_lo[64];
843                 uint8_t limit_hi[64];
844                 uint8_t hi_ff = UINT8_MAX;
845                 uint8_t lo_00 = 0;
846
847                 memset(limit_lo, 0, RTE_DIM(limit_lo));
848                 memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi));
849
850                 for (n = size - 2; n >= 0; n--) {
851                         hi_ff = (uint8_t)(hi_ff & hi[n]);
852                         lo_00 = (uint8_t)(lo_00 | lo[n]);
853                 }
854
855                 if (hi_ff != UINT8_MAX) {
856                         limit_lo[size - 1] = hi[size - 1];
857                         acl_gen_range(context, hi, limit_lo, size, level,
858                                 root, *pend);
859                 }
860
861                 if (lo_00 != 0) {
862                         limit_hi[size - 1] = lo[size - 1];
863                         acl_gen_range(context, limit_hi, lo, size, level,
864                                 root, *pend);
865                 }
866
867                 if (hi[size - 1] - lo[size - 1] > 1 ||
868                                 lo_00 == 0 ||
869                                 hi_ff == UINT8_MAX) {
870                         limit_lo[size-1] = (uint8_t)(lo[size-1] + (lo_00 != 0));
871                         limit_hi[size-1] = (uint8_t)(hi[size-1] -
872                                 (hi_ff != UINT8_MAX));
873                         acl_gen_range(context, limit_hi, limit_lo, size,
874                                 level, root, *pend);
875                 }
876         }
877         return root;
878 }
879
880 static struct rte_acl_node *
881 acl_gen_mask_trie(struct acl_build_context *context,
882         const void *value, const void *mask,
883         int size, int level, struct rte_acl_node **pend)
884 {
885         int32_t n;
886         struct rte_acl_node *root;
887         struct rte_acl_node *node, *prev;
888         struct rte_acl_bitset bits;
889         const uint8_t *val = (const uint8_t *)value;
890         const uint8_t *msk = (const uint8_t *)mask;
891
892         root = acl_alloc_node(context, level++);
893         prev = root;
894
895         for (n = size - 1; n >= 0; n--) {
896                 node = acl_alloc_node(context, level++);
897                 acl_gen_mask(&bits, val[n] & msk[n], msk[n]);
898                 acl_add_ptr(context, prev, node, &bits);
899                 prev = node;
900         }
901
902         *pend = prev;
903         return root;
904 }
905
906 static struct rte_acl_node *
907 build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
908         struct rte_acl_build_rule **last, uint32_t *count)
909 {
910         uint32_t n, m;
911         int field_index, node_count;
912         struct rte_acl_node *trie;
913         struct rte_acl_build_rule *prev, *rule;
914         struct rte_acl_node *end, *merge, *root, *end_prev;
915         const struct rte_acl_field *fld;
916
917         prev = head;
918         rule = head;
919         *last = prev;
920
921         trie = acl_alloc_node(context, 0);
922
923         while (rule != NULL) {
924
925                 root = acl_alloc_node(context, 0);
926
927                 root->ref_count = 1;
928                 end = root;
929
930                 for (n = 0; n < rule->config->num_fields; n++) {
931
932                         field_index = rule->config->defs[n].field_index;
933                         fld = rule->f->field + field_index;
934                         end_prev = end;
935
936                         /* build a mini-trie for this field */
937                         switch (rule->config->defs[n].type) {
938
939                         case RTE_ACL_FIELD_TYPE_BITMASK:
940                                 merge = acl_gen_mask_trie(context,
941                                         &fld->value,
942                                         &fld->mask_range,
943                                         rule->config->defs[n].size,
944                                         end->level + 1,
945                                         &end);
946                                 break;
947
948                         case RTE_ACL_FIELD_TYPE_MASK:
949                         {
950                                 /*
951                                  * set msb for the size of the field and
952                                  * all higher bits.
953                                  */
954                                 uint64_t mask;
955                                 mask = RTE_ACL_MASKLEN_TO_BITMASK(
956                                         fld->mask_range.u32,
957                                         rule->config->defs[n].size);
958
959                                 /* gen a mini-trie for this field */
960                                 merge = acl_gen_mask_trie(context,
961                                         &fld->value,
962                                         (char *)&mask,
963                                         rule->config->defs[n].size,
964                                         end->level + 1,
965                                         &end);
966                         }
967                         break;
968
969                         case RTE_ACL_FIELD_TYPE_RANGE:
970                                 merge = acl_gen_range_trie(context,
971                                         &rule->f->field[field_index].value,
972                                         &rule->f->field[field_index].mask_range,
973                                         rule->config->defs[n].size,
974                                         end->level + 1,
975                                         &end);
976                                 break;
977
978                         default:
979                                 RTE_LOG(ERR, ACL,
980                                         "Error in rule[%u] type - %hhu\n",
981                                         rule->f->data.userdata,
982                                         rule->config->defs[n].type);
983                                 return NULL;
984                         }
985
986                         /* merge this field on to the end of the rule */
987                         if (acl_merge_trie(context, end_prev, merge, 0,
988                                         NULL) != 0) {
989                                 return NULL;
990                         }
991                 }
992
993                 end->match_flag = ++context->num_build_rules;
994
995                 /*
996                  * Setup the results for this rule.
997                  * The result and priority of each category.
998                  */
999                 if (end->mrt == NULL)
1000                         end->mrt = acl_build_alloc(context, 1,
1001                                 sizeof(*end->mrt));
1002
1003                 for (m = context->cfg.num_categories; 0 != m--; ) {
1004                         if (rule->f->data.category_mask & (1 << m)) {
1005                                 end->mrt->results[m] = rule->f->data.userdata;
1006                                 end->mrt->priority[m] = rule->f->data.priority;
1007                         } else {
1008                                 end->mrt->results[m] = 0;
1009                                 end->mrt->priority[m] = 0;
1010                         }
1011                 }
1012
1013                 node_count = context->num_nodes;
1014                 (*count)++;
1015
1016                 /* merge this rule into the trie */
1017                 if (acl_merge_trie(context, trie, root, 0, NULL))
1018                         return NULL;
1019
1020                 node_count = context->num_nodes - node_count;
1021                 if (node_count > context->cur_node_max) {
1022                         *last = prev;
1023                         return trie;
1024                 }
1025
1026                 prev = rule;
1027                 rule = rule->next;
1028         }
1029
1030         *last = NULL;
1031         return trie;
1032 }
1033
1034 static void
1035 acl_calc_wildness(struct rte_acl_build_rule *head,
1036         const struct rte_acl_config *config)
1037 {
1038         uint32_t n;
1039         struct rte_acl_build_rule *rule;
1040
1041         for (rule = head; rule != NULL; rule = rule->next) {
1042
1043                 for (n = 0; n < config->num_fields; n++) {
1044
1045                         double wild = 0;
1046                         uint32_t bit_len = CHAR_BIT * config->defs[n].size;
1047                         uint64_t msk_val = RTE_LEN2MASK(bit_len,
1048                                 typeof(msk_val));
1049                         double size = bit_len;
1050                         int field_index = config->defs[n].field_index;
1051                         const struct rte_acl_field *fld = rule->f->field +
1052                                 field_index;
1053
1054                         switch (rule->config->defs[n].type) {
1055                         case RTE_ACL_FIELD_TYPE_BITMASK:
1056                                 wild = (size - __builtin_popcountll(
1057                                         fld->mask_range.u64 & msk_val)) /
1058                                         size;
1059                                 break;
1060
1061                         case RTE_ACL_FIELD_TYPE_MASK:
1062                                 wild = (size - fld->mask_range.u32) / size;
1063                                 break;
1064
1065                         case RTE_ACL_FIELD_TYPE_RANGE:
1066                                 wild = (fld->mask_range.u64 & msk_val) -
1067                                         (fld->value.u64 & msk_val);
1068                                 wild = wild / msk_val;
1069                                 break;
1070                         }
1071
1072                         rule->wildness[field_index] = (uint32_t)(wild * 100);
1073                 }
1074         }
1075 }
1076
1077 static void
1078 acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config)
1079 {
1080         struct rte_acl_build_rule *rule;
1081         uint32_t n, m, fields_deactivated = 0;
1082         uint32_t start = 0, deactivate = 0;
1083         int tally[RTE_ACL_MAX_LEVELS][TALLY_NUM];
1084
1085         memset(tally, 0, sizeof(tally));
1086
1087         for (rule = head; rule != NULL; rule = rule->next) {
1088
1089                 for (n = 0; n < config->num_fields; n++) {
1090                         uint32_t field_index = config->defs[n].field_index;
1091
1092                         tally[n][TALLY_0]++;
1093                         for (m = 1; m < RTE_DIM(wild_limits); m++) {
1094                                 if (rule->wildness[field_index] >=
1095                                                 wild_limits[m])
1096                                         tally[n][m]++;
1097                         }
1098                 }
1099
1100                 for (n = config->num_fields - 1; n > 0; n--) {
1101                         uint32_t field_index = config->defs[n].field_index;
1102
1103                         if (rule->wildness[field_index] == 100)
1104                                 tally[n][TALLY_DEPTH]++;
1105                         else
1106                                 break;
1107                 }
1108         }
1109
1110         /*
1111          * Look for any field that is always wild and drop it from the config
1112          * Only deactivate if all fields for a given input loop are deactivated.
1113          */
1114         for (n = 1; n < config->num_fields; n++) {
1115                 if (config->defs[n].input_index !=
1116                                 config->defs[n - 1].input_index) {
1117                         for (m = start; m < n; m++)
1118                                 tally[m][TALLY_DEACTIVATED] = deactivate;
1119                         fields_deactivated += deactivate;
1120                         start = n;
1121                         deactivate = 1;
1122                 }
1123
1124                 /* if the field is not always completely wild */
1125                 if (tally[n][TALLY_100] != tally[n][TALLY_0])
1126                         deactivate = 0;
1127         }
1128
1129         for (m = start; m < n; m++)
1130                 tally[m][TALLY_DEACTIVATED] = deactivate;
1131
1132         fields_deactivated += deactivate;
1133
1134         /* remove deactivated fields */
1135         if (fields_deactivated) {
1136                 uint32_t k, l = 0;
1137
1138                 for (k = 0; k < config->num_fields; k++) {
1139                         if (tally[k][TALLY_DEACTIVATED] == 0) {
1140                                 memmove(&tally[l][0], &tally[k][0],
1141                                         TALLY_NUM * sizeof(tally[0][0]));
1142                                 memmove(&config->defs[l++],
1143                                         &config->defs[k],
1144                                         sizeof(struct rte_acl_field_def));
1145                         }
1146                 }
1147                 config->num_fields = l;
1148         }
1149 }
1150
1151 static int
1152 rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2)
1153 {
1154         uint32_t n;
1155
1156         for (n = 1; n < r1->config->num_fields; n++) {
1157                 int field_index = r1->config->defs[n].field_index;
1158
1159                 if (r1->wildness[field_index] != r2->wildness[field_index])
1160                         return (r1->wildness[field_index] -
1161                                 r2->wildness[field_index]);
1162         }
1163         return 0;
1164 }
1165
1166 /*
1167  * Sort list of rules based on the rules wildness.
1168  */
1169 static struct rte_acl_build_rule *
1170 sort_rules(struct rte_acl_build_rule *head)
1171 {
1172         struct rte_acl_build_rule *new_head;
1173         struct rte_acl_build_rule *l, *r, **p;
1174
1175         new_head = NULL;
1176         while (head != NULL) {
1177
1178                 /* remove element from the head of the old list. */
1179                 r = head;
1180                 head = r->next;
1181                 r->next = NULL;
1182
1183                 /* walk through new sorted list to find a proper place. */
1184                 for (p = &new_head;
1185                                 (l = *p) != NULL &&
1186                                 rule_cmp_wildness(l, r) >= 0;
1187                                 p = &l->next)
1188                         ;
1189
1190                 /* insert element into the new sorted list. */
1191                 r->next = *p;
1192                 *p = r;
1193         }
1194
1195         return new_head;
1196 }
1197
1198 static uint32_t
1199 acl_build_index(const struct rte_acl_config *config, uint32_t *data_index)
1200 {
1201         uint32_t n, m;
1202         int32_t last_header;
1203
1204         m = 0;
1205         last_header = -1;
1206
1207         for (n = 0; n < config->num_fields; n++) {
1208                 if (last_header != config->defs[n].input_index) {
1209                         last_header = config->defs[n].input_index;
1210                         data_index[m++] = config->defs[n].offset;
1211                 }
1212         }
1213
1214         return m;
1215 }
1216
1217 static struct rte_acl_build_rule *
1218 build_one_trie(struct acl_build_context *context,
1219         struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],
1220         uint32_t n, int32_t node_max)
1221 {
1222         struct rte_acl_build_rule *last;
1223         struct rte_acl_config *config;
1224
1225         config = rule_sets[n]->config;
1226
1227         acl_rule_stats(rule_sets[n], config);
1228         rule_sets[n] = sort_rules(rule_sets[n]);
1229
1230         context->tries[n].type = RTE_ACL_FULL_TRIE;
1231         context->tries[n].count = 0;
1232
1233         context->tries[n].num_data_indexes = acl_build_index(config,
1234                 context->data_indexes[n]);
1235         context->tries[n].data_index = context->data_indexes[n];
1236
1237         context->cur_node_max = node_max;
1238
1239         context->bld_tries[n].trie = build_trie(context, rule_sets[n],
1240                 &last, &context->tries[n].count);
1241
1242         return last;
1243 }
1244
1245 static int
1246 acl_build_tries(struct acl_build_context *context,
1247         struct rte_acl_build_rule *head)
1248 {
1249         uint32_t n, num_tries;
1250         struct rte_acl_config *config;
1251         struct rte_acl_build_rule *last;
1252         struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES];
1253
1254         config = head->config;
1255         rule_sets[0] = head;
1256
1257         /* initialize tries */
1258         for (n = 0; n < RTE_DIM(context->tries); n++) {
1259                 context->tries[n].type = RTE_ACL_UNUSED_TRIE;
1260                 context->bld_tries[n].trie = NULL;
1261                 context->tries[n].count = 0;
1262         }
1263
1264         context->tries[0].type = RTE_ACL_FULL_TRIE;
1265
1266         /* calc wildness of each field of each rule */
1267         acl_calc_wildness(head, config);
1268
1269         for (n = 0;; n = num_tries) {
1270
1271                 num_tries = n + 1;
1272
1273                 last = build_one_trie(context, rule_sets, n, context->node_max);
1274                 if (context->bld_tries[n].trie == NULL) {
1275                         RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1276                         return -ENOMEM;
1277                 }
1278
1279                 /* Build of the last trie completed. */
1280                 if (last == NULL)
1281                         break;
1282
1283                 if (num_tries == RTE_DIM(context->tries)) {
1284                         RTE_LOG(ERR, ACL,
1285                                 "Exceeded max number of tries: %u\n",
1286                                 num_tries);
1287                         return -ENOMEM;
1288                 }
1289
1290                 /* Trie is getting too big, split remaining rule set. */
1291                 rule_sets[num_tries] = last->next;
1292                 last->next = NULL;
1293                 acl_free_node(context, context->bld_tries[n].trie);
1294
1295                 /* Create a new copy of config for remaining rules. */
1296                 config = acl_build_alloc(context, 1, sizeof(*config));
1297                 memcpy(config, rule_sets[n]->config, sizeof(*config));
1298
1299                 /* Make remaining rules use new config. */
1300                 for (head = rule_sets[num_tries]; head != NULL;
1301                                 head = head->next)
1302                         head->config = config;
1303
1304                 /*
1305                  * Rebuild the trie for the reduced rule-set.
1306                  * Don't try to split it any further.
1307                  */
1308                 last = build_one_trie(context, rule_sets, n, INT32_MAX);
1309                 if (context->bld_tries[n].trie == NULL || last != NULL) {
1310                         RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1311                         return -ENOMEM;
1312                 }
1313
1314         }
1315
1316         context->num_tries = num_tries;
1317         return 0;
1318 }
1319
1320 static void
1321 acl_build_log(const struct acl_build_context *ctx)
1322 {
1323         uint32_t n;
1324
1325         RTE_LOG(DEBUG, ACL, "Build phase for ACL \"%s\":\n"
1326                 "node limit for tree split: %u\n"
1327                 "nodes created: %u\n"
1328                 "memory consumed: %zu\n",
1329                 ctx->acx->name,
1330                 ctx->node_max,
1331                 ctx->num_nodes,
1332                 ctx->pool.alloc);
1333
1334         for (n = 0; n < RTE_DIM(ctx->tries); n++) {
1335                 if (ctx->tries[n].count != 0)
1336                         RTE_LOG(DEBUG, ACL,
1337                                 "trie %u: number of rules: %u, indexes: %u\n",
1338                                 n, ctx->tries[n].count,
1339                                 ctx->tries[n].num_data_indexes);
1340         }
1341 }
1342
1343 static int
1344 acl_build_rules(struct acl_build_context *bcx)
1345 {
1346         struct rte_acl_build_rule *br, *head;
1347         const struct rte_acl_rule *rule;
1348         uint32_t *wp;
1349         uint32_t fn, i, n, num;
1350         size_t ofs, sz;
1351
1352         fn = bcx->cfg.num_fields;
1353         n = bcx->acx->num_rules;
1354         ofs = n * sizeof(*br);
1355         sz = ofs + n * fn * sizeof(*wp);
1356
1357         br = tb_alloc(&bcx->pool, sz);
1358
1359         wp = (uint32_t *)((uintptr_t)br + ofs);
1360         num = 0;
1361         head = NULL;
1362
1363         for (i = 0; i != n; i++) {
1364                 rule = (const struct rte_acl_rule *)
1365                         ((uintptr_t)bcx->acx->rules + bcx->acx->rule_sz * i);
1366                 if ((rule->data.category_mask & bcx->category_mask) != 0) {
1367                         br[num].next = head;
1368                         br[num].config = &bcx->cfg;
1369                         br[num].f = rule;
1370                         br[num].wildness = wp;
1371                         wp += fn;
1372                         head = br + num;
1373                         num++;
1374                 }
1375         }
1376
1377         bcx->num_rules = num;
1378         bcx->build_rules = head;
1379
1380         return 0;
1381 }
1382
1383 /*
1384  * Copy data_indexes for each trie into RT location.
1385  */
1386 static void
1387 acl_set_data_indexes(struct rte_acl_ctx *ctx)
1388 {
1389         uint32_t i, n, ofs;
1390
1391         ofs = 0;
1392         for (i = 0; i != ctx->num_tries; i++) {
1393                 n = ctx->trie[i].num_data_indexes;
1394                 memcpy(ctx->data_indexes + ofs, ctx->trie[i].data_index,
1395                         n * sizeof(ctx->data_indexes[0]));
1396                 ctx->trie[i].data_index = ctx->data_indexes + ofs;
1397                 ofs += RTE_ACL_MAX_FIELDS;
1398         }
1399 }
1400
1401 /*
1402  * Internal routine, performs 'build' phase of trie generation:
1403  * - setups build context.
1404  * - analizes given set of rules.
1405  * - builds internal tree(s).
1406  */
1407 static int
1408 acl_bld(struct acl_build_context *bcx, struct rte_acl_ctx *ctx,
1409         const struct rte_acl_config *cfg, uint32_t node_max)
1410 {
1411         int32_t rc;
1412
1413         /* setup build context. */
1414         memset(bcx, 0, sizeof(*bcx));
1415         bcx->acx = ctx;
1416         bcx->pool.alignment = ACL_POOL_ALIGN;
1417         bcx->pool.min_alloc = ACL_POOL_ALLOC_MIN;
1418         bcx->cfg = *cfg;
1419         bcx->category_mask = RTE_LEN2MASK(bcx->cfg.num_categories,
1420                 typeof(bcx->category_mask));
1421         bcx->node_max = node_max;
1422
1423         rc = sigsetjmp(bcx->pool.fail, 0);
1424
1425         /* build phase runs out of memory. */
1426         if (rc != 0) {
1427                 RTE_LOG(ERR, ACL,
1428                         "ACL context: %s, %s() failed with error code: %d\n",
1429                         bcx->acx->name, __func__, rc);
1430                 return rc;
1431         }
1432
1433         /* Create a build rules copy. */
1434         rc = acl_build_rules(bcx);
1435         if (rc != 0)
1436                 return rc;
1437
1438         /* No rules to build for that context+config */
1439         if (bcx->build_rules == NULL) {
1440                 rc = -EINVAL;
1441         } else {
1442                 /* build internal trie representation. */
1443                 rc = acl_build_tries(bcx, bcx->build_rules);
1444         }
1445         return rc;
1446 }
1447
1448 /*
1449  * Check that parameters for acl_build() are valid.
1450  */
1451 static int
1452 acl_check_bld_param(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1453 {
1454         static const size_t field_sizes[] = {
1455                 sizeof(uint8_t), sizeof(uint16_t),
1456                 sizeof(uint32_t), sizeof(uint64_t),
1457         };
1458
1459         uint32_t i, j;
1460
1461         if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
1462                         cfg->num_categories > RTE_ACL_MAX_CATEGORIES ||
1463                         cfg->num_fields == 0 ||
1464                         cfg->num_fields > RTE_ACL_MAX_FIELDS)
1465                 return -EINVAL;
1466
1467         for (i = 0; i != cfg->num_fields; i++) {
1468                 if (cfg->defs[i].type > RTE_ACL_FIELD_TYPE_BITMASK) {
1469                         RTE_LOG(ERR, ACL,
1470                         "ACL context: %s, invalid type: %hhu for %u-th field\n",
1471                         ctx->name, cfg->defs[i].type, i);
1472                         return -EINVAL;
1473                 }
1474                 for (j = 0;
1475                                 j != RTE_DIM(field_sizes) &&
1476                                 cfg->defs[i].size != field_sizes[j];
1477                                 j++)
1478                         ;
1479
1480                 if (j == RTE_DIM(field_sizes)) {
1481                         RTE_LOG(ERR, ACL,
1482                         "ACL context: %s, invalid size: %hhu for %u-th field\n",
1483                         ctx->name, cfg->defs[i].size, i);
1484                         return -EINVAL;
1485                 }
1486         }
1487
1488         return 0;
1489 }
1490
1491 int
1492 rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1493 {
1494         int32_t rc;
1495         uint32_t n;
1496         size_t max_size;
1497         struct acl_build_context bcx;
1498
1499         rc = acl_check_bld_param(ctx, cfg);
1500         if (rc != 0)
1501                 return rc;
1502
1503         acl_build_reset(ctx);
1504
1505         if (cfg->max_size == 0) {
1506                 n = NODE_MIN;
1507                 max_size = SIZE_MAX;
1508         } else {
1509                 n = NODE_MAX;
1510                 max_size = cfg->max_size;
1511         }
1512
1513         for (rc = -ERANGE; n >= NODE_MIN && rc == -ERANGE; n /= 2) {
1514
1515                 /* perform build phase. */
1516                 rc = acl_bld(&bcx, ctx, cfg, n);
1517
1518                 if (rc == 0) {
1519                         /* allocate and fill run-time  structures. */
1520                         rc = rte_acl_gen(ctx, bcx.tries, bcx.bld_tries,
1521                                 bcx.num_tries, bcx.cfg.num_categories,
1522                                 RTE_ACL_MAX_FIELDS * RTE_DIM(bcx.tries) *
1523                                 sizeof(ctx->data_indexes[0]), max_size);
1524                         if (rc == 0) {
1525                                 /* set data indexes. */
1526                                 acl_set_data_indexes(ctx);
1527
1528                                 /* copy in build config. */
1529                                 ctx->config = *cfg;
1530                         }
1531                 }
1532
1533                 acl_build_log(&bcx);
1534
1535                 /* cleanup after build. */
1536                 tb_free_pool(&bcx.pool);
1537         }
1538
1539         return rc;
1540 }