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  * Split the rte_acl_build_rule list into two lists.
1168  */
1169 static void
1170 rule_list_split(struct rte_acl_build_rule *source,
1171         struct rte_acl_build_rule **list_a,
1172         struct rte_acl_build_rule **list_b)
1173 {
1174         struct rte_acl_build_rule *fast;
1175         struct rte_acl_build_rule *slow;
1176
1177         if (source == NULL || source->next == NULL) {
1178                 /* length < 2 cases */
1179                 *list_a = source;
1180                 *list_b = NULL;
1181         } else {
1182                 slow = source;
1183                 fast = source->next;
1184                 /* Advance 'fast' two nodes, and advance 'slow' one node */
1185                 while (fast != NULL) {
1186                         fast = fast->next;
1187                         if (fast != NULL) {
1188                                 slow = slow->next;
1189                                 fast = fast->next;
1190                         }
1191                 }
1192                 /* 'slow' is before the midpoint in the list, so split it in two
1193                    at that point. */
1194                 *list_a = source;
1195                 *list_b = slow->next;
1196                 slow->next = NULL;
1197         }
1198 }
1199
1200 /*
1201  * Merge two sorted lists.
1202  */
1203 static struct rte_acl_build_rule *
1204 rule_list_sorted_merge(struct rte_acl_build_rule *a,
1205         struct rte_acl_build_rule *b)
1206 {
1207         struct rte_acl_build_rule *result = NULL;
1208         struct rte_acl_build_rule **last_next = &result;
1209
1210         while (1) {
1211                 if (a == NULL) {
1212                         *last_next = b;
1213                         break;
1214                 } else if (b == NULL) {
1215                         *last_next = a;
1216                         break;
1217                 }
1218                 if (rule_cmp_wildness(a, b) >= 0) {
1219                         *last_next = a;
1220                         last_next = &a->next;
1221                         a = a->next;
1222                 } else {
1223                         *last_next = b;
1224                         last_next = &b->next;
1225                         b = b->next;
1226                 }
1227         }
1228         return result;
1229 }
1230
1231 /*
1232  * Sort list of rules based on the rules wildness.
1233  * Use recursive mergesort algorithm.
1234  */
1235 static struct rte_acl_build_rule *
1236 sort_rules(struct rte_acl_build_rule *head)
1237 {
1238         struct rte_acl_build_rule *a;
1239         struct rte_acl_build_rule *b;
1240
1241         /* Base case -- length 0 or 1 */
1242         if (head == NULL || head->next == NULL)
1243                 return head;
1244
1245         /* Split head into 'a' and 'b' sublists */
1246         rule_list_split(head, &a, &b);
1247
1248         /* Recursively sort the sublists */
1249         a = sort_rules(a);
1250         b = sort_rules(b);
1251
1252         /* answer = merge the two sorted lists together */
1253         return rule_list_sorted_merge(a, b);
1254 }
1255
1256 static uint32_t
1257 acl_build_index(const struct rte_acl_config *config, uint32_t *data_index)
1258 {
1259         uint32_t n, m;
1260         int32_t last_header;
1261
1262         m = 0;
1263         last_header = -1;
1264
1265         for (n = 0; n < config->num_fields; n++) {
1266                 if (last_header != config->defs[n].input_index) {
1267                         last_header = config->defs[n].input_index;
1268                         data_index[m++] = config->defs[n].offset;
1269                 }
1270         }
1271
1272         return m;
1273 }
1274
1275 static struct rte_acl_build_rule *
1276 build_one_trie(struct acl_build_context *context,
1277         struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],
1278         uint32_t n, int32_t node_max)
1279 {
1280         struct rte_acl_build_rule *last;
1281         struct rte_acl_config *config;
1282
1283         config = rule_sets[n]->config;
1284
1285         acl_rule_stats(rule_sets[n], config);
1286         rule_sets[n] = sort_rules(rule_sets[n]);
1287
1288         context->tries[n].type = RTE_ACL_FULL_TRIE;
1289         context->tries[n].count = 0;
1290
1291         context->tries[n].num_data_indexes = acl_build_index(config,
1292                 context->data_indexes[n]);
1293         context->tries[n].data_index = context->data_indexes[n];
1294
1295         context->cur_node_max = node_max;
1296
1297         context->bld_tries[n].trie = build_trie(context, rule_sets[n],
1298                 &last, &context->tries[n].count);
1299
1300         return last;
1301 }
1302
1303 static int
1304 acl_build_tries(struct acl_build_context *context,
1305         struct rte_acl_build_rule *head)
1306 {
1307         uint32_t n, num_tries;
1308         struct rte_acl_config *config;
1309         struct rte_acl_build_rule *last;
1310         struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES];
1311
1312         config = head->config;
1313         rule_sets[0] = head;
1314
1315         /* initialize tries */
1316         for (n = 0; n < RTE_DIM(context->tries); n++) {
1317                 context->tries[n].type = RTE_ACL_UNUSED_TRIE;
1318                 context->bld_tries[n].trie = NULL;
1319                 context->tries[n].count = 0;
1320         }
1321
1322         context->tries[0].type = RTE_ACL_FULL_TRIE;
1323
1324         /* calc wildness of each field of each rule */
1325         acl_calc_wildness(head, config);
1326
1327         for (n = 0;; n = num_tries) {
1328
1329                 num_tries = n + 1;
1330
1331                 last = build_one_trie(context, rule_sets, n, context->node_max);
1332                 if (context->bld_tries[n].trie == NULL) {
1333                         RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1334                         return -ENOMEM;
1335                 }
1336
1337                 /* Build of the last trie completed. */
1338                 if (last == NULL)
1339                         break;
1340
1341                 if (num_tries == RTE_DIM(context->tries)) {
1342                         RTE_LOG(ERR, ACL,
1343                                 "Exceeded max number of tries: %u\n",
1344                                 num_tries);
1345                         return -ENOMEM;
1346                 }
1347
1348                 /* Trie is getting too big, split remaining rule set. */
1349                 rule_sets[num_tries] = last->next;
1350                 last->next = NULL;
1351                 acl_free_node(context, context->bld_tries[n].trie);
1352
1353                 /* Create a new copy of config for remaining rules. */
1354                 config = acl_build_alloc(context, 1, sizeof(*config));
1355                 memcpy(config, rule_sets[n]->config, sizeof(*config));
1356
1357                 /* Make remaining rules use new config. */
1358                 for (head = rule_sets[num_tries]; head != NULL;
1359                                 head = head->next)
1360                         head->config = config;
1361
1362                 /*
1363                  * Rebuild the trie for the reduced rule-set.
1364                  * Don't try to split it any further.
1365                  */
1366                 last = build_one_trie(context, rule_sets, n, INT32_MAX);
1367                 if (context->bld_tries[n].trie == NULL || last != NULL) {
1368                         RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1369                         return -ENOMEM;
1370                 }
1371
1372         }
1373
1374         context->num_tries = num_tries;
1375         return 0;
1376 }
1377
1378 static void
1379 acl_build_log(const struct acl_build_context *ctx)
1380 {
1381         uint32_t n;
1382
1383         RTE_LOG(DEBUG, ACL, "Build phase for ACL \"%s\":\n"
1384                 "node limit for tree split: %u\n"
1385                 "nodes created: %u\n"
1386                 "memory consumed: %zu\n",
1387                 ctx->acx->name,
1388                 ctx->node_max,
1389                 ctx->num_nodes,
1390                 ctx->pool.alloc);
1391
1392         for (n = 0; n < RTE_DIM(ctx->tries); n++) {
1393                 if (ctx->tries[n].count != 0)
1394                         RTE_LOG(DEBUG, ACL,
1395                                 "trie %u: number of rules: %u, indexes: %u\n",
1396                                 n, ctx->tries[n].count,
1397                                 ctx->tries[n].num_data_indexes);
1398         }
1399 }
1400
1401 static int
1402 acl_build_rules(struct acl_build_context *bcx)
1403 {
1404         struct rte_acl_build_rule *br, *head;
1405         const struct rte_acl_rule *rule;
1406         uint32_t *wp;
1407         uint32_t fn, i, n, num;
1408         size_t ofs, sz;
1409
1410         fn = bcx->cfg.num_fields;
1411         n = bcx->acx->num_rules;
1412         ofs = n * sizeof(*br);
1413         sz = ofs + n * fn * sizeof(*wp);
1414
1415         br = tb_alloc(&bcx->pool, sz);
1416
1417         wp = (uint32_t *)((uintptr_t)br + ofs);
1418         num = 0;
1419         head = NULL;
1420
1421         for (i = 0; i != n; i++) {
1422                 rule = (const struct rte_acl_rule *)
1423                         ((uintptr_t)bcx->acx->rules + bcx->acx->rule_sz * i);
1424                 if ((rule->data.category_mask & bcx->category_mask) != 0) {
1425                         br[num].next = head;
1426                         br[num].config = &bcx->cfg;
1427                         br[num].f = rule;
1428                         br[num].wildness = wp;
1429                         wp += fn;
1430                         head = br + num;
1431                         num++;
1432                 }
1433         }
1434
1435         bcx->num_rules = num;
1436         bcx->build_rules = head;
1437
1438         return 0;
1439 }
1440
1441 /*
1442  * Copy data_indexes for each trie into RT location.
1443  */
1444 static void
1445 acl_set_data_indexes(struct rte_acl_ctx *ctx)
1446 {
1447         uint32_t i, n, ofs;
1448
1449         ofs = 0;
1450         for (i = 0; i != ctx->num_tries; i++) {
1451                 n = ctx->trie[i].num_data_indexes;
1452                 memcpy(ctx->data_indexes + ofs, ctx->trie[i].data_index,
1453                         n * sizeof(ctx->data_indexes[0]));
1454                 ctx->trie[i].data_index = ctx->data_indexes + ofs;
1455                 ofs += RTE_ACL_MAX_FIELDS;
1456         }
1457 }
1458
1459 /*
1460  * Internal routine, performs 'build' phase of trie generation:
1461  * - setups build context.
1462  * - analizes given set of rules.
1463  * - builds internal tree(s).
1464  */
1465 static int
1466 acl_bld(struct acl_build_context *bcx, struct rte_acl_ctx *ctx,
1467         const struct rte_acl_config *cfg, uint32_t node_max)
1468 {
1469         int32_t rc;
1470
1471         /* setup build context. */
1472         memset(bcx, 0, sizeof(*bcx));
1473         bcx->acx = ctx;
1474         bcx->pool.alignment = ACL_POOL_ALIGN;
1475         bcx->pool.min_alloc = ACL_POOL_ALLOC_MIN;
1476         bcx->cfg = *cfg;
1477         bcx->category_mask = RTE_LEN2MASK(bcx->cfg.num_categories,
1478                 typeof(bcx->category_mask));
1479         bcx->node_max = node_max;
1480
1481         rc = sigsetjmp(bcx->pool.fail, 0);
1482
1483         /* build phase runs out of memory. */
1484         if (rc != 0) {
1485                 RTE_LOG(ERR, ACL,
1486                         "ACL context: %s, %s() failed with error code: %d\n",
1487                         bcx->acx->name, __func__, rc);
1488                 return rc;
1489         }
1490
1491         /* Create a build rules copy. */
1492         rc = acl_build_rules(bcx);
1493         if (rc != 0)
1494                 return rc;
1495
1496         /* No rules to build for that context+config */
1497         if (bcx->build_rules == NULL) {
1498                 rc = -EINVAL;
1499         } else {
1500                 /* build internal trie representation. */
1501                 rc = acl_build_tries(bcx, bcx->build_rules);
1502         }
1503         return rc;
1504 }
1505
1506 /*
1507  * Check that parameters for acl_build() are valid.
1508  */
1509 static int
1510 acl_check_bld_param(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1511 {
1512         static const size_t field_sizes[] = {
1513                 sizeof(uint8_t), sizeof(uint16_t),
1514                 sizeof(uint32_t), sizeof(uint64_t),
1515         };
1516
1517         uint32_t i, j;
1518
1519         if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
1520                         cfg->num_categories > RTE_ACL_MAX_CATEGORIES ||
1521                         cfg->num_fields == 0 ||
1522                         cfg->num_fields > RTE_ACL_MAX_FIELDS)
1523                 return -EINVAL;
1524
1525         for (i = 0; i != cfg->num_fields; i++) {
1526                 if (cfg->defs[i].type > RTE_ACL_FIELD_TYPE_BITMASK) {
1527                         RTE_LOG(ERR, ACL,
1528                         "ACL context: %s, invalid type: %hhu for %u-th field\n",
1529                         ctx->name, cfg->defs[i].type, i);
1530                         return -EINVAL;
1531                 }
1532                 for (j = 0;
1533                                 j != RTE_DIM(field_sizes) &&
1534                                 cfg->defs[i].size != field_sizes[j];
1535                                 j++)
1536                         ;
1537
1538                 if (j == RTE_DIM(field_sizes)) {
1539                         RTE_LOG(ERR, ACL,
1540                         "ACL context: %s, invalid size: %hhu for %u-th field\n",
1541                         ctx->name, cfg->defs[i].size, i);
1542                         return -EINVAL;
1543                 }
1544         }
1545
1546         return 0;
1547 }
1548
1549 int
1550 rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1551 {
1552         int32_t rc;
1553         uint32_t n;
1554         size_t max_size;
1555         struct acl_build_context bcx;
1556
1557         rc = acl_check_bld_param(ctx, cfg);
1558         if (rc != 0)
1559                 return rc;
1560
1561         acl_build_reset(ctx);
1562
1563         if (cfg->max_size == 0) {
1564                 n = NODE_MIN;
1565                 max_size = SIZE_MAX;
1566         } else {
1567                 n = NODE_MAX;
1568                 max_size = cfg->max_size;
1569         }
1570
1571         for (rc = -ERANGE; n >= NODE_MIN && rc == -ERANGE; n /= 2) {
1572
1573                 /* perform build phase. */
1574                 rc = acl_bld(&bcx, ctx, cfg, n);
1575
1576                 if (rc == 0) {
1577                         /* allocate and fill run-time  structures. */
1578                         rc = rte_acl_gen(ctx, bcx.tries, bcx.bld_tries,
1579                                 bcx.num_tries, bcx.cfg.num_categories,
1580                                 RTE_ACL_MAX_FIELDS * RTE_DIM(bcx.tries) *
1581                                 sizeof(ctx->data_indexes[0]), max_size);
1582                         if (rc == 0) {
1583                                 /* set data indexes. */
1584                                 acl_set_data_indexes(ctx);
1585
1586                                 /* copy in build config. */
1587                                 ctx->config = *cfg;
1588                         }
1589                 }
1590
1591                 acl_build_log(&bcx);
1592
1593                 /* cleanup after build. */
1594                 tb_free_pool(&bcx.pool);
1595         }
1596
1597         return rc;
1598 }