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 /* variable for dividing rule sets */
  45 #define NODE_MAX        2500
  46 #define NODE_PERCENTAGE (0.40)
  47 #define RULE_PERCENTAGE (0.40)
  48
  49 /* TALLY are statistics per field */
  50 enum {
  51         TALLY_0 = 0,        /* number of rules that are 0% or more wild. */
  52         TALLY_25,           /* number of rules that are 25% or more wild. */
  53         TALLY_50,
  54         TALLY_75,
  55         TALLY_100,
  56         TALLY_DEACTIVATED, /* deactivated fields (100% wild in all rules). */
  57         TALLY_DEPTH,
  58         /* number of rules that are 100% wild for this field and higher. */
  59         TALLY_NUM
  60 };
  61
  62 static const uint32_t wild_limits[TALLY_DEACTIVATED] = {0, 25, 50, 75, 100};
  63
  64 enum {
  65         ACL_INTERSECT_NONE = 0,
  66         ACL_INTERSECT_A = 1,    /* set A is a superset of A and B intersect */
  67         ACL_INTERSECT_B = 2,    /* set B is a superset of A and B intersect */
  68         ACL_INTERSECT = 4,      /* sets A and B intersect */
  69 };
  70
  71 enum {
  72         ACL_PRIORITY_EQUAL = 0,
  73         ACL_PRIORITY_NODE_A = 1,
  74         ACL_PRIORITY_NODE_B = 2,
  75         ACL_PRIORITY_MIXED = 3
  76 };
  77
  78
  79 struct acl_mem_block {
  80         uint32_t block_size;
  81         void     *mem_ptr;
  82 };
  83
  84 #define MEM_BLOCK_NUM   16
  85
  86 /* Single ACL rule, build representation.*/
  87 struct rte_acl_build_rule {
  88         struct rte_acl_build_rule   *next;
  89         struct rte_acl_config       *config;
  90         /**< configuration for each field in the rule. */
  91         const struct rte_acl_rule   *f;
  92         uint32_t                    *wildness;
  93 };
  94
  95 /* Context for build phase */
  96 struct acl_build_context {
  97         const struct rte_acl_ctx *acx;
  98         struct rte_acl_build_rule *build_rules;
  99         struct rte_acl_config     cfg;
 100         uint32_t                  node;
 101         uint32_t                  num_nodes;
 102         uint32_t                  category_mask;
 103         uint32_t                  num_rules;
 104         uint32_t                  node_id;
 105         uint32_t                  src_mask;
 106         uint32_t                  num_build_rules;
 107         uint32_t                  num_tries;
 108         struct tb_mem_pool        pool;
 109         struct rte_acl_trie       tries[RTE_ACL_MAX_TRIES];
 110         struct rte_acl_bld_trie   bld_tries[RTE_ACL_MAX_TRIES];
 111         uint32_t            data_indexes[RTE_ACL_MAX_TRIES][RTE_ACL_MAX_FIELDS];
 112
 113         /* memory free lists for nodes and blocks used for node ptrs */
 114         struct acl_mem_block      blocks[MEM_BLOCK_NUM];
 115         struct rte_acl_node       *node_free_list;
 116 };
 117
 118 static int acl_merge_trie(struct acl_build_context *context,
 119         struct rte_acl_node *node_a, struct rte_acl_node *node_b,
 120         uint32_t level, uint32_t subtree_id, struct rte_acl_node **node_c);
 121
 122 static int acl_merge(struct acl_build_context *context,
 123         struct rte_acl_node *node_a, struct rte_acl_node *node_b,
 124         int move, int a_subset, int level);
 125
 126 static void
 127 acl_deref_ptr(struct acl_build_context *context,
 128         struct rte_acl_node *node, int index);
 129
 130 static void *
 131 acl_build_alloc(struct acl_build_context *context, size_t n, size_t s)
 132 {
 133         uint32_t m;
 134         void *p;
 135         size_t alloc_size = n * s;
 136
 137         /*
 138          * look for memory in free lists
 139          */
 140         for (m = 0; m < RTE_DIM(context->blocks); m++) {
 141                 if (context->blocks[m].block_size ==
 142                    alloc_size && context->blocks[m].mem_ptr != NULL) {
 143                         p = context->blocks[m].mem_ptr;
 144                         context->blocks[m].mem_ptr = *((void **)p);
 145                         memset(p, 0, alloc_size);
 146                         return p;
 147                 }
 148         }
 149
 150         /*
 151          * return allocation from memory pool
 152          */
 153         p = tb_alloc(&context->pool, alloc_size);
 154         return p;
 155 }
 156
 157 /*
 158  * Free memory blocks (kept in context for reuse).
 159  */
 160 static void
 161 acl_build_free(struct acl_build_context *context, size_t s, void *p)
 162 {
 163         uint32_t n;
 164
 165         for (n = 0; n < RTE_DIM(context->blocks); n++) {
 166                 if (context->blocks[n].block_size == s) {
 167                         *((void **)p) = context->blocks[n].mem_ptr;
 168                         context->blocks[n].mem_ptr = p;
 169                         return;
 170                 }
 171         }
 172         for (n = 0; n < RTE_DIM(context->blocks); n++) {
 173                 if (context->blocks[n].block_size == 0) {
 174                         context->blocks[n].block_size = s;
 175                         *((void **)p) = NULL;
 176                         context->blocks[n].mem_ptr = p;
 177                         return;
 178                 }
 179         }
 180 }
 181
 182 /*
 183  * Allocate and initialize a new node.
 184  */
 185 static struct rte_acl_node *
 186 acl_alloc_node(struct acl_build_context *context, int level)
 187 {
 188         struct rte_acl_node *node;
 189
 190         if (context->node_free_list != NULL) {
 191                 node = context->node_free_list;
 192                 context->node_free_list = node->next;
 193                 memset(node, 0, sizeof(struct rte_acl_node));
 194         } else {
 195                 node = acl_build_alloc(context, sizeof(struct rte_acl_node), 1);
 196         }
 197
 198         if (node != NULL) {
 199                 node->num_ptrs = 0;
 200                 node->level = level;
 201                 node->node_type = RTE_ACL_NODE_UNDEFINED;
 202                 node->node_index = RTE_ACL_NODE_UNDEFINED;
 203                 context->num_nodes++;
 204                 node->id = context->node_id++;
 205         }
 206         return node;
 207 }
 208
 209 /*
 210  * Dereference all nodes to which this node points
 211  */
 212 static void
 213 acl_free_node(struct acl_build_context *context,
 214         struct rte_acl_node *node)
 215 {
 216         uint32_t n;
 217
 218         if (node->prev != NULL)
 219                 node->prev->next = NULL;
 220         for (n = 0; n < node->num_ptrs; n++)
 221                 acl_deref_ptr(context, node, n);
 222
 223         /* free mrt if this is a match node */
 224         if (node->mrt != NULL) {
 225                 acl_build_free(context, sizeof(struct rte_acl_match_results),
 226                         node->mrt);
 227                 node->mrt = NULL;
 228         }
 229
 230         /* free transitions to other nodes */
 231         if (node->ptrs != NULL) {
 232                 acl_build_free(context,
 233                         node->max_ptrs * sizeof(struct rte_acl_ptr_set),
 234                         node->ptrs);
 235                 node->ptrs = NULL;
 236         }
 237
 238         /* put it on the free list */
 239         context->num_nodes--;
 240         node->next = context->node_free_list;
 241         context->node_free_list = node;
 242 }
 243
 244
 245 /*
 246  * Include src bitset in dst bitset
 247  */
 248 static void
 249 acl_include(struct rte_acl_bitset *dst, struct rte_acl_bitset *src, bits_t mask)
 250 {
 251         uint32_t n;
 252
 253         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
 254                 dst->bits[n] = (dst->bits[n] & mask) | src->bits[n];
 255 }
 256
 257 /*
 258  * Set dst to bits of src1 that are not in src2
 259  */
 260 static int
 261 acl_exclude(struct rte_acl_bitset *dst,
 262         struct rte_acl_bitset *src1,
 263         struct rte_acl_bitset *src2)
 264 {
 265         uint32_t n;
 266         bits_t all_bits = 0;
 267
 268         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
 269                 dst->bits[n] = src1->bits[n] & ~src2->bits[n];
 270                 all_bits |= dst->bits[n];
 271         }
 272         return all_bits != 0;
 273 }
 274
 275 /*
 276  * Add a pointer (ptr) to a node.
 277  */
 278 static int
 279 acl_add_ptr(struct acl_build_context *context,
 280         struct rte_acl_node *node,
 281         struct rte_acl_node *ptr,
 282         struct rte_acl_bitset *bits)
 283 {
 284         uint32_t n, num_ptrs;
 285         struct rte_acl_ptr_set *ptrs = NULL;
 286
 287         /*
 288          * If there's already a pointer to the same node, just add to the bitset
 289          */
 290         for (n = 0; n < node->num_ptrs; n++) {
 291                 if (node->ptrs[n].ptr != NULL) {
 292                         if (node->ptrs[n].ptr == ptr) {
 293                                 acl_include(&node->ptrs[n].values, bits, -1);
 294                                 acl_include(&node->values, bits, -1);
 295                                 return 0;
 296                         }
 297                 }
 298         }
 299
 300         /* if there's no room for another pointer, make room */
 301         if (node->num_ptrs >= node->max_ptrs) {
 302                 /* add room for more pointers */
 303                 num_ptrs = node->max_ptrs + ACL_PTR_ALLOC;
 304                 ptrs = acl_build_alloc(context, num_ptrs, sizeof(*ptrs));
 305                 if (ptrs == NULL)
 306                         return -ENOMEM;
 307
 308                 /* copy current points to new memory allocation */
 309                 if (node->ptrs != NULL) {
 310                         memcpy(ptrs, node->ptrs,
 311                                 node->num_ptrs * sizeof(*ptrs));
 312                         acl_build_free(context, node->max_ptrs * sizeof(*ptrs),
 313                                 node->ptrs);
 314                 }
 315                 node->ptrs = ptrs;
 316                 node->max_ptrs = num_ptrs;
 317         }
 318
 319         /* Find available ptr and add a new pointer to this node */
 320         for (n = node->min_add; n < node->max_ptrs; n++) {
 321                 if (node->ptrs[n].ptr == NULL) {
 322                         node->ptrs[n].ptr = ptr;
 323                         acl_include(&node->ptrs[n].values, bits, 0);
 324                         acl_include(&node->values, bits, -1);
 325                         if (ptr != NULL)
 326                                 ptr->ref_count++;
 327                         if (node->num_ptrs <= n)
 328                                 node->num_ptrs = n + 1;
 329                         return 0;
 330                 }
 331         }
 332
 333         return 0;
 334 }
 335
 336 /*
 337  * Add a pointer for a range of values
 338  */
 339 static int
 340 acl_add_ptr_range(struct acl_build_context *context,
 341         struct rte_acl_node *root,
 342         struct rte_acl_node *node,
 343         uint8_t low,
 344         uint8_t high)
 345 {
 346         uint32_t n;
 347         struct rte_acl_bitset bitset;
 348
 349         /* clear the bitset values */
 350         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
 351                 bitset.bits[n] = 0;
 352
 353         /* for each bit in range, add bit to set */
 354         for (n = 0; n < UINT8_MAX + 1; n++)
 355                 if (n >= low && n <= high)
 356                         bitset.bits[n / (sizeof(bits_t) * 8)] |=
 357                                 1 << (n % (sizeof(bits_t) * 8));
 358
 359         return acl_add_ptr(context, root, node, &bitset);
 360 }
 361
 362 /*
 363  * Generate a bitset from a byte value and mask.
 364  */
 365 static int
 366 acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
 367 {
 368         int range = 0;
 369         uint32_t n;
 370
 371         /* clear the bitset values */
 372         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
 373                 bitset->bits[n] = 0;
 374
 375         /* for each bit in value/mask, add bit to set */
 376         for (n = 0; n < UINT8_MAX + 1; n++) {
 377                 if ((n & mask) == value) {
 378                         range++;
 379                         bitset->bits[n / (sizeof(bits_t) * 8)] |=
 380                                 1 << (n % (sizeof(bits_t) * 8));
 381                 }
 382         }
 383         return range;
 384 }
 385
 386 /*
 387  * Determine how A and B intersect.
 388  * Determine if A and/or B are supersets of the intersection.
 389  */
 390 static int
 391 acl_intersect_type(struct rte_acl_bitset *a_bits,
 392         struct rte_acl_bitset *b_bits,
 393         struct rte_acl_bitset *intersect)
 394 {
 395         uint32_t n;
 396         bits_t intersect_bits = 0;
 397         bits_t a_superset = 0;
 398         bits_t b_superset = 0;
 399
 400         /*
 401          * calculate and store intersection and check if A and/or B have
 402          * bits outside the intersection (superset)
 403          */
 404         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
 405                 intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
 406                 a_superset |= a_bits->bits[n] ^ intersect->bits[n];
 407                 b_superset |= b_bits->bits[n] ^ intersect->bits[n];
 408                 intersect_bits |= intersect->bits[n];
 409         }
 410
 411         n = (intersect_bits == 0 ? ACL_INTERSECT_NONE : ACL_INTERSECT) |
 412                 (b_superset == 0 ? 0 : ACL_INTERSECT_B) |
 413                 (a_superset == 0 ? 0 : ACL_INTERSECT_A);
 414
 415         return n;
 416 }
 417
 418 /*
 419  * Check if all bits in the bitset are on
 420  */
 421 static int
 422 acl_full(struct rte_acl_node *node)
 423 {
 424         uint32_t n;
 425         bits_t all_bits = -1;
 426
 427         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
 428                 all_bits &= node->values.bits[n];
 429         return all_bits == -1;
 430 }
 431
 432 /*
 433  * Check if all bits in the bitset are off
 434  */
 435 static int
 436 acl_empty(struct rte_acl_node *node)
 437 {
 438         uint32_t n;
 439
 440         if (node->ref_count == 0) {
 441                 for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
 442                         if (0 != node->values.bits[n])
 443                                 return 0;
 444                 }
 445                 return 1;
 446         } else {
 447                 return 0;
 448         }
 449 }
 450
 451 /*
 452  * Compute intersection of A and B
 453  * return 1 if there is an intersection else 0.
 454  */
 455 static int
 456 acl_intersect(struct rte_acl_bitset *a_bits,
 457         struct rte_acl_bitset *b_bits,
 458         struct rte_acl_bitset *intersect)
 459 {
 460         uint32_t n;
 461         bits_t all_bits = 0;
 462
 463         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
 464                 intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
 465                 all_bits |= intersect->bits[n];
 466         }
 467         return all_bits != 0;
 468 }
 469
 470 /*
 471  * Duplicate a node
 472  */
 473 static struct rte_acl_node *
 474 acl_dup_node(struct acl_build_context *context, struct rte_acl_node *node)
 475 {
 476         uint32_t n;
 477         struct rte_acl_node *next;
 478
 479         next = acl_alloc_node(context, node->level);
 480         if (next == NULL)
 481                 return NULL;
 482
 483         /* allocate the pointers */
 484         if (node->num_ptrs > 0) {
 485                 next->ptrs = acl_build_alloc(context,
 486                         node->max_ptrs,
 487                         sizeof(struct rte_acl_ptr_set));
 488                 if (next->ptrs == NULL)
 489                         return NULL;
 490                 next->max_ptrs = node->max_ptrs;
 491         }
 492
 493         /* copy over the pointers */
 494         for (n = 0; n < node->num_ptrs; n++) {
 495                 if (node->ptrs[n].ptr != NULL) {
 496                         next->ptrs[n].ptr = node->ptrs[n].ptr;
 497                         next->ptrs[n].ptr->ref_count++;
 498                         acl_include(&next->ptrs[n].values,
 499                                 &node->ptrs[n].values, -1);
 500                 }
 501         }
 502
 503         next->num_ptrs = node->num_ptrs;
 504
 505         /* copy over node's match results */
 506         if (node->match_flag == 0)
 507                 next->match_flag = 0;
 508         else {
 509                 next->match_flag = -1;
 510                 next->mrt = acl_build_alloc(context, 1, sizeof(*next->mrt));
 511                 memcpy(next->mrt, node->mrt, sizeof(*next->mrt));
 512         }
 513
 514         /* copy over node's bitset */
 515         acl_include(&next->values, &node->values, -1);
 516
 517         node->next = next;
 518         next->prev = node;
 519
 520         return next;
 521 }
 522
 523 /*
 524  * Dereference a pointer from a node
 525  */
 526 static void
 527 acl_deref_ptr(struct acl_build_context *context,
 528         struct rte_acl_node *node, int index)
 529 {
 530         struct rte_acl_node *ref_node;
 531
 532         /* De-reference the node at the specified pointer */
 533         if (node != NULL && node->ptrs[index].ptr != NULL) {
 534                 ref_node = node->ptrs[index].ptr;
 535                 ref_node->ref_count--;
 536                 if (ref_node->ref_count == 0)
 537                         acl_free_node(context, ref_node);
 538         }
 539 }
 540
 541 /*
 542  * Exclude bitset from a node pointer
 543  * returns  0 if poiter was deref'd
 544  *          1 otherwise.
 545  */
 546 static int
 547 acl_exclude_ptr(struct acl_build_context *context,
 548         struct rte_acl_node *node,
 549         int index,
 550         struct rte_acl_bitset *b_bits)
 551 {
 552         int retval = 1;
 553
 554         /*
 555          * remove bitset from node pointer and deref
 556          * if the bitset becomes empty.
 557          */
 558         if (!acl_exclude(&node->ptrs[index].values,
 559                         &node->ptrs[index].values,
 560                         b_bits)) {
 561                 acl_deref_ptr(context, node, index);
 562                 node->ptrs[index].ptr = NULL;
 563                 retval = 0;
 564         }
 565
 566         /* exclude bits from the composite bits for the node */
 567         acl_exclude(&node->values, &node->values, b_bits);
 568         return retval;
 569 }
 570
 571 /*
 572  * Remove a bitset from src ptr and move remaining ptr to dst
 573  */
 574 static int
 575 acl_move_ptr(struct acl_build_context *context,
 576         struct rte_acl_node *dst,
 577         struct rte_acl_node *src,
 578         int index,
 579         struct rte_acl_bitset *b_bits)
 580 {
 581         int rc;
 582
 583         if (b_bits != NULL)
 584                 if (!acl_exclude_ptr(context, src, index, b_bits))
 585                         return 0;
 586
 587         /* add src pointer to dst node */
 588         rc = acl_add_ptr(context, dst, src->ptrs[index].ptr,
 589                         &src->ptrs[index].values);
 590         if (rc < 0)
 591                 return rc;
 592
 593         /* remove ptr from src */
 594         acl_exclude_ptr(context, src, index, &src->ptrs[index].values);
 595         return 1;
 596 }
 597
 598 /*
 599  * acl_exclude rte_acl_bitset from src and copy remaining pointer to dst
 600  */
 601 static int
 602 acl_copy_ptr(struct acl_build_context *context,
 603         struct rte_acl_node *dst,
 604         struct rte_acl_node *src,
 605         int index,
 606         struct rte_acl_bitset *b_bits)
 607 {
 608         int rc;
 609         struct rte_acl_bitset bits;
 610
 611         if (b_bits != NULL)
 612                 if (!acl_exclude(&bits, &src->ptrs[index].values, b_bits))
 613                         return 0;
 614
 615         rc = acl_add_ptr(context, dst, src->ptrs[index].ptr, &bits);
 616         if (rc < 0)
 617                 return rc;
 618         return 1;
 619 }
 620
 621 /*
 622  * Fill in gaps in ptrs list with the ptr at the end of the list
 623  */
 624 static void
 625 acl_compact_node_ptrs(struct rte_acl_node *node_a)
 626 {
 627         uint32_t n;
 628         int min_add = node_a->min_add;
 629
 630         while (node_a->num_ptrs > 0  &&
 631                         node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
 632                 node_a->num_ptrs--;
 633
 634         for (n = min_add; n + 1 < node_a->num_ptrs; n++) {
 635
 636                 /* if this entry is empty */
 637                 if (node_a->ptrs[n].ptr == NULL) {
 638
 639                         /* move the last pointer to this entry */
 640                         acl_include(&node_a->ptrs[n].values,
 641                                 &node_a->ptrs[node_a->num_ptrs - 1].values,
 642                                 0);
 643                         node_a->ptrs[n].ptr =
 644                                 node_a->ptrs[node_a->num_ptrs - 1].ptr;
 645
 646                         /*
 647                          * mark the end as empty and adjust the number
 648                          * of used pointer enum_tries
 649                          */
 650                         node_a->ptrs[node_a->num_ptrs - 1].ptr = NULL;
 651                         while (node_a->num_ptrs > 0  &&
 652                                 node_a->ptrs[node_a->num_ptrs - 1].ptr == NULL)
 653                                 node_a->num_ptrs--;
 654                 }
 655         }
 656 }
 657
 658 /*
 659  * acl_merge helper routine.
 660  */
 661 static int
 662 acl_merge_intersect(struct acl_build_context *context,
 663         struct rte_acl_node *node_a, uint32_t idx_a,
 664         struct rte_acl_node *node_b, uint32_t idx_b,
 665         int next_move, int level,
 666         struct rte_acl_bitset *intersect_ptr)
 667 {
 668         struct rte_acl_node *node_c;
 669
 670         /* Duplicate A for intersection */
 671         node_c = acl_dup_node(context, node_a->ptrs[idx_a].ptr);
 672         if (node_c == NULL)
 673                 return -1;
 674
 675         /* Remove intersection from A */
 676         acl_exclude_ptr(context, node_a, idx_a, intersect_ptr);
 677
 678         /*
 679          * Added link from A to C for all transitions
 680          * in the intersection
 681          */
 682         if (acl_add_ptr(context, node_a, node_c, intersect_ptr) < 0)
 683                 return -1;
 684
 685         /* merge B->node into C */
 686         return acl_merge(context, node_c, node_b->ptrs[idx_b].ptr, next_move,
 687                 0, level + 1);
 688 }
 689
 690
 691 /*
 692  * Merge the children of nodes A and B together.
 693  *
 694  * if match node
 695  *      For each category
 696  *              node A result = highest priority result
 697  * if any pointers in A intersect with any in B
 698  *      For each intersection
 699  *              C = copy of node that A points to
 700  *              remove intersection from A pointer
 701  *              add a pointer to A that points to C for the intersection
 702  *              Merge C and node that B points to
 703  * Compact the pointers in A and B
 704  * if move flag
 705  *      If B has only one reference
 706  *              Move B pointers to A
 707  *      else
 708  *              Copy B pointers to A
 709  */
 710 static int
 711 acl_merge(struct acl_build_context *context,
 712         struct rte_acl_node *node_a, struct rte_acl_node *node_b,
 713         int move, int a_subset, int level)
 714 {
 715         uint32_t n, m, ptrs_a, ptrs_b;
 716         uint32_t min_add_a, min_add_b;
 717         int intersect_type;
 718         int node_intersect_type;
 719         int b_full, next_move, rc;
 720         struct rte_acl_bitset intersect_values;
 721         struct rte_acl_bitset intersect_ptr;
 722
 723         min_add_a = 0;
 724         min_add_b = 0;
 725         intersect_type = 0;
 726         node_intersect_type = 0;
 727
 728         if (level == 0)
 729                 a_subset = 1;
 730
 731         /*
 732          *  Resolve match priorities
 733          */
 734         if (node_a->match_flag != 0 || node_b->match_flag != 0) {
 735
 736                 if (node_a->match_flag == 0 || node_b->match_flag == 0)
 737                         RTE_LOG(ERR, ACL, "Not both matches\n");
 738
 739                 if (node_b->match_flag < node_a->match_flag)
 740                         RTE_LOG(ERR, ACL, "Not same match\n");
 741
 742                 for (n = 0; n < context->cfg.num_categories; n++) {
 743                         if (node_a->mrt->priority[n] <
 744                                         node_b->mrt->priority[n]) {
 745                                 node_a->mrt->priority[n] =
 746                                         node_b->mrt->priority[n];
 747                                 node_a->mrt->results[n] =
 748                                         node_b->mrt->results[n];
 749                         }
 750                 }
 751         }
 752
 753         /*
 754          * If the two node transitions intersect then merge the transitions.
 755          * Check intersection for entire node (all pointers)
 756          */
 757         node_intersect_type = acl_intersect_type(&node_a->values,
 758                 &node_b->values,
 759                 &intersect_values);
 760
 761         if (node_intersect_type & ACL_INTERSECT) {
 762
 763                 b_full = acl_full(node_b);
 764
 765                 min_add_b = node_b->min_add;
 766                 node_b->min_add = node_b->num_ptrs;
 767                 ptrs_b = node_b->num_ptrs;
 768
 769                 min_add_a = node_a->min_add;
 770                 node_a->min_add = node_a->num_ptrs;
 771                 ptrs_a = node_a->num_ptrs;
 772
 773                 for (n = 0; n < ptrs_a; n++) {
 774                         for (m = 0; m < ptrs_b; m++) {
 775
 776                                 if (node_a->ptrs[n].ptr == NULL ||
 777                                                 node_b->ptrs[m].ptr == NULL ||
 778                                                 node_a->ptrs[n].ptr ==
 779                                                 node_b->ptrs[m].ptr)
 780                                                 continue;
 781
 782                                 intersect_type = acl_intersect_type(
 783                                         &node_a->ptrs[n].values,
 784                                         &node_b->ptrs[m].values,
 785                                         &intersect_ptr);
 786
 787                                 /* If this node is not a 'match' node */
 788                                 if ((intersect_type & ACL_INTERSECT) &&
 789                                         (context->cfg.num_categories != 1 ||
 790                                         !(node_a->ptrs[n].ptr->match_flag))) {
 791
 792                                         /*
 793                                          * next merge is a 'move' pointer,
 794                                          * if this one is and B is a
 795                                          * subset of the intersection.
 796                                          */
 797                                         next_move = move &&
 798                                                 (intersect_type &
 799                                                 ACL_INTERSECT_B) == 0;
 800
 801                                         if (a_subset && b_full) {
 802                                                 rc = acl_merge(context,
 803                                                         node_a->ptrs[n].ptr,
 804                                                         node_b->ptrs[m].ptr,
 805                                                         next_move,
 806                                                         1, level + 1);
 807                                                 if (rc != 0)
 808                                                         return rc;
 809                                         } else {
 810                                                 rc = acl_merge_intersect(
 811                                                         context, node_a, n,
 812                                                         node_b, m, next_move,
 813                                                         level, &intersect_ptr);
 814                                                 if (rc != 0)
 815                                                         return rc;
 816                                         }
 817                                 }
 818                         }
 819                 }
 820         }
 821
 822         /* Compact pointers */
 823         node_a->min_add = min_add_a;
 824         acl_compact_node_ptrs(node_a);
 825         node_b->min_add = min_add_b;
 826         acl_compact_node_ptrs(node_b);
 827
 828         /*
 829          *  Either COPY or MOVE pointers from B to A
 830          */
 831         acl_intersect(&node_a->values, &node_b->values, &intersect_values);
 832
 833         if (move && node_b->ref_count == 1) {
 834                 for (m = 0; m < node_b->num_ptrs; m++) {
 835                         if (node_b->ptrs[m].ptr != NULL &&
 836                                         acl_move_ptr(context, node_a, node_b, m,
 837                                         &intersect_values) < 0)
 838                                 return -1;
 839                 }
 840         } else {
 841                 for (m = 0; m < node_b->num_ptrs; m++) {
 842                         if (node_b->ptrs[m].ptr != NULL &&
 843                                         acl_copy_ptr(context, node_a, node_b, m,
 844                                         &intersect_values) < 0)
 845                                 return -1;
 846                 }
 847         }
 848
 849         /*
 850          *  Free node if its empty (no longer used)
 851          */
 852         if (acl_empty(node_b))
 853                 acl_free_node(context, node_b);
 854         return 0;
 855 }
 856
 857 static int
 858 acl_resolve_leaf(struct acl_build_context *context,
 859         struct rte_acl_node *node_a,
 860         struct rte_acl_node *node_b,
 861         struct rte_acl_node **node_c)
 862 {
 863         uint32_t n;
 864         int combined_priority = ACL_PRIORITY_EQUAL;
 865
 866         for (n = 0; n < context->cfg.num_categories; n++) {
 867                 if (node_a->mrt->priority[n] != node_b->mrt->priority[n]) {
 868                         combined_priority |= (node_a->mrt->priority[n] >
 869                                 node_b->mrt->priority[n]) ?
 870                                 ACL_PRIORITY_NODE_A : ACL_PRIORITY_NODE_B;
 871                 }
 872         }
 873
 874         /*
 875          * if node a is higher or equal priority for all categories,
 876          * then return node_a.
 877          */
 878         if (combined_priority == ACL_PRIORITY_NODE_A ||
 879                         combined_priority == ACL_PRIORITY_EQUAL) {
 880                 *node_c = node_a;
 881                 return 0;
 882         }
 883
 884         /*
 885          * if node b is higher or equal priority for all categories,
 886          * then return node_b.
 887          */
 888         if (combined_priority == ACL_PRIORITY_NODE_B) {
 889                 *node_c = node_b;
 890                 return 0;
 891         }
 892
 893         /*
 894          * mixed priorities - create a new node with the highest priority
 895          * for each category.
 896          */
 897
 898         /* force new duplication. */
 899         node_a->next = NULL;
 900
 901         *node_c = acl_dup_node(context, node_a);
 902         for (n = 0; n < context->cfg.num_categories; n++) {
 903                 if ((*node_c)->mrt->priority[n] < node_b->mrt->priority[n]) {
 904                         (*node_c)->mrt->priority[n] = node_b->mrt->priority[n];
 905                         (*node_c)->mrt->results[n] = node_b->mrt->results[n];
 906                 }
 907         }
 908         return 0;
 909 }
 910
 911 /*
 912 * Within the existing trie structure, determine which nodes are
 913 * part of the subtree of the trie to be merged.
 914 *
 915 * For these purposes, a subtree is defined as the set of nodes that
 916 * are 1) not a superset of the intersection with the same level of
 917 * the merging tree, and 2) do not have any references from a node
 918 * outside of the subtree.
 919 */
 920 static void
 921 mark_subtree(struct rte_acl_node *node,
 922         struct rte_acl_bitset *level_bits,
 923         uint32_t level,
 924         uint32_t id)
 925 {
 926         uint32_t n;
 927
 928         /* mark this node as part of the subtree */
 929         node->subtree_id = id | RTE_ACL_SUBTREE_NODE;
 930
 931         for (n = 0; n < node->num_ptrs; n++) {
 932
 933                 if (node->ptrs[n].ptr != NULL) {
 934
 935                         struct rte_acl_bitset intersect_bits;
 936                         int intersect;
 937
 938                         /*
 939                         * Item 1) :
 940                         * check if this child pointer is not a superset of the
 941                         * same level of the merging tree.
 942                         */
 943                         intersect = acl_intersect_type(&node->ptrs[n].values,
 944                                 &level_bits[level],
 945                                 &intersect_bits);
 946
 947                         if ((intersect & ACL_INTERSECT_A) == 0) {
 948
 949                                 struct rte_acl_node *child = node->ptrs[n].ptr;
 950
 951                                 /*
 952                                  * reset subtree reference if this is
 953                                  * the first visit by this subtree.
 954                                  */
 955                                 if (child->subtree_id != id) {
 956                                         child->subtree_id = id;
 957                                         child->subtree_ref_count = 0;
 958                                 }
 959
 960                                 /*
 961                                 * Item 2) :
 962                                 * increment the subtree reference count and if
 963                                 * all references are from this subtree then
 964                                 * recurse to that child
 965                                 */
 966                                 child->subtree_ref_count++;
 967                                 if (child->subtree_ref_count ==
 968                                                 child->ref_count)
 969                                         mark_subtree(child, level_bits,
 970                                                 level + 1, id);
 971                         }
 972                 }
 973         }
 974 }
 975
 976 /*
 977  * Build the set of bits that define the set of transitions
 978  * for each level of a trie.
 979  */
 980 static void
 981 build_subset_mask(struct rte_acl_node *node,
 982         struct rte_acl_bitset *level_bits,
 983         int level)
 984 {
 985         uint32_t n;
 986
 987         /* Add this node's transitions to the set for this level */
 988         for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
 989                 level_bits[level].bits[n] &= node->values.bits[n];
 990
 991         /* For each child, add the transitions for the next level */
 992         for (n = 0; n < node->num_ptrs; n++)
 993                 if (node->ptrs[n].ptr != NULL)
 994                         build_subset_mask(node->ptrs[n].ptr, level_bits,
 995                                 level + 1);
 996 }
 997
 998
 999 /*
1000  * Merge nodes A and B together,
1001  *   returns a node that is the path for the intersection
1002  *
1003  * If match node (leaf on trie)
1004  *      For each category
1005  *              return node = highest priority result
1006  *
1007  * Create C as a duplicate of A to point to child intersections
1008  * If any pointers in C intersect with any in B
1009  *      For each intersection
1010  *              merge children
1011  *              remove intersection from C pointer
1012  *              add a pointer from C to child intersection node
1013  * Compact the pointers in A and B
1014  * Copy any B pointers that are outside of the intersection to C
1015  * If C has no references to the B trie
1016  *   free C and return A
1017  * Else If C has no references to the A trie
1018  *   free C and return B
1019  * Else
1020  *   return C
1021  */
1022 static int
1023 acl_merge_trie(struct acl_build_context *context,
1024         struct rte_acl_node *node_a, struct rte_acl_node *node_b,
1025         uint32_t level, uint32_t subtree_id, struct rte_acl_node **return_c)
1026 {
1027         uint32_t n, m, ptrs_c, ptrs_b;
1028         uint32_t min_add_c, min_add_b;
1029         int node_intersect_type;
1030         struct rte_acl_bitset node_intersect;
1031         struct rte_acl_node *node_c;
1032         struct rte_acl_node *node_a_next;
1033         int node_b_refs;
1034         int node_a_refs;
1035
1036         node_c = node_a;
1037         node_a_next = node_a->next;
1038         min_add_c = 0;
1039         min_add_b = 0;
1040         node_a_refs = node_a->num_ptrs;
1041         node_b_refs = 0;
1042         node_intersect_type = 0;
1043
1044         /* Resolve leaf nodes (matches) */
1045         if (node_a->match_flag != 0) {
1046                 acl_resolve_leaf(context, node_a, node_b, return_c);
1047                 return 0;
1048         }
1049
1050         /*
1051          * Create node C as a copy of node A if node A is not part of
1052          * a subtree of the merging tree (node B side). Otherwise,
1053          * just use node A.
1054          */
1055         if (level > 0 &&
1056                         node_a->subtree_id !=
1057                         (subtree_id | RTE_ACL_SUBTREE_NODE)) {
1058                 node_c = acl_dup_node(context, node_a);
1059                 node_c->subtree_id = subtree_id | RTE_ACL_SUBTREE_NODE;
1060         }
1061
1062         /*
1063          * If the two node transitions intersect then merge the transitions.
1064          * Check intersection for entire node (all pointers)
1065          */
1066         node_intersect_type = acl_intersect_type(&node_c->values,
1067                 &node_b->values,
1068                 &node_intersect);
1069
1070         if (node_intersect_type & ACL_INTERSECT) {
1071
1072                 min_add_b = node_b->min_add;
1073                 node_b->min_add = node_b->num_ptrs;
1074                 ptrs_b = node_b->num_ptrs;
1075
1076                 min_add_c = node_c->min_add;
1077                 node_c->min_add = node_c->num_ptrs;
1078                 ptrs_c = node_c->num_ptrs;
1079
1080                 for (n = 0; n < ptrs_c; n++) {
1081                         if (node_c->ptrs[n].ptr == NULL) {
1082                                 node_a_refs--;
1083                                 continue;
1084                         }
1085                         node_c->ptrs[n].ptr->next = NULL;
1086                         for (m = 0; m < ptrs_b; m++) {
1087
1088                                 struct rte_acl_bitset child_intersect;
1089                                 int child_intersect_type;
1090                                 struct rte_acl_node *child_node_c = NULL;
1091
1092                                 if (node_b->ptrs[m].ptr == NULL ||
1093                                                 node_c->ptrs[n].ptr ==
1094                                                 node_b->ptrs[m].ptr)
1095                                                 continue;
1096
1097                                 child_intersect_type = acl_intersect_type(
1098                                         &node_c->ptrs[n].values,
1099                                         &node_b->ptrs[m].values,
1100                                         &child_intersect);
1101
1102                                 if ((child_intersect_type & ACL_INTERSECT) !=
1103                                                 0) {
1104                                         if (acl_merge_trie(context,
1105                                                         node_c->ptrs[n].ptr,
1106                                                         node_b->ptrs[m].ptr,
1107                                                         level + 1, subtree_id,
1108                                                         &child_node_c))
1109                                                 return 1;
1110
1111                                         if (child_node_c != NULL &&
1112                                                         child_node_c !=
1113                                                         node_c->ptrs[n].ptr) {
1114
1115                                                 node_b_refs++;
1116
1117                                                 /*
1118                                                  * Added link from C to
1119                                                  * child_C for all transitions
1120                                                  * in the intersection.
1121                                                  */
1122                                                 acl_add_ptr(context, node_c,
1123                                                         child_node_c,
1124                                                         &child_intersect);
1125
1126                                                 /*
1127                                                  * inc refs if pointer is not
1128                                                  * to node b.
1129                                                  */
1130                                                 node_a_refs += (child_node_c !=
1131                                                         node_b->ptrs[m].ptr);
1132
1133                                                 /*
1134                                                  * Remove intersection from C
1135                                                  * pointer.
1136                                                  */
1137                                                 if (!acl_exclude(
1138                                                         &node_c->ptrs[n].values,
1139                                                         &node_c->ptrs[n].values,
1140                                                         &child_intersect)) {
1141                                                         acl_deref_ptr(context,
1142                                                                 node_c, n);
1143                                                         node_c->ptrs[n].ptr =
1144                                                                 NULL;
1145                                                         node_a_refs--;
1146                                                 }
1147                                         }
1148                                 }
1149                         }
1150                 }
1151
1152                 /* Compact pointers */
1153                 node_c->min_add = min_add_c;
1154                 acl_compact_node_ptrs(node_c);
1155                 node_b->min_add = min_add_b;
1156                 acl_compact_node_ptrs(node_b);
1157         }
1158
1159         /*
1160          *  Copy pointers outside of the intersection from B to C
1161          */
1162         if ((node_intersect_type & ACL_INTERSECT_B) != 0) {
1163                 node_b_refs++;
1164                 for (m = 0; m < node_b->num_ptrs; m++)
1165                         if (node_b->ptrs[m].ptr != NULL)
1166                                 acl_copy_ptr(context, node_c,
1167                                         node_b, m, &node_intersect);
1168         }
1169
1170         /*
1171          * Free node C if top of trie is contained in A or B
1172          *  if node C is a duplicate of node A &&
1173          *     node C was not an existing duplicate
1174          */
1175         if (node_c != node_a && node_c != node_a_next) {
1176
1177                 /*
1178                  * if the intersection has no references to the
1179                  * B side, then it is contained in A
1180                  */
1181                 if (node_b_refs == 0) {
1182                         acl_free_node(context, node_c);
1183                         node_c = node_a;
1184                 } else {
1185                         /*
1186                          * if the intersection has no references to the
1187                          * A side, then it is contained in B.
1188                          */
1189                         if (node_a_refs == 0) {
1190                                 acl_free_node(context, node_c);
1191                                 node_c = node_b;
1192                         }
1193                 }
1194         }
1195
1196         if (return_c != NULL)
1197                 *return_c = node_c;
1198
1199         if (level == 0)
1200                 acl_free_node(context, node_b);
1201
1202         return 0;
1203 }
1204
1205 /*
1206  * Reset current runtime fields before next build:
1207  *  - free allocated RT memory.
1208  *  - reset all RT related fields to zero.
1209  */
1210 static void
1211 acl_build_reset(struct rte_acl_ctx *ctx)
1212 {
1213         rte_free(ctx->mem);
1214         memset(&ctx->num_categories, 0,
1215                 sizeof(*ctx) - offsetof(struct rte_acl_ctx, num_categories));
1216 }
1217
1218 static void
1219 acl_gen_range(struct acl_build_context *context,
1220         const uint8_t *hi, const uint8_t *lo, int size, int level,
1221         struct rte_acl_node *root, struct rte_acl_node *end)
1222 {
1223         struct rte_acl_node *node, *prev;
1224         uint32_t n;
1225
1226         prev = root;
1227         for (n = size - 1; n > 0; n--) {
1228                 node = acl_alloc_node(context, level++);
1229                 acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
1230                 prev = node;
1231         }
1232         acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
1233 }
1234
1235 static struct rte_acl_node *
1236 acl_gen_range_trie(struct acl_build_context *context,
1237         const void *min, const void *max,
1238         int size, int level, struct rte_acl_node **pend)
1239 {
1240         int32_t n;
1241         struct rte_acl_node *root;
1242         const uint8_t *lo = (const uint8_t *)min;
1243         const uint8_t *hi = (const uint8_t *)max;
1244
1245         *pend = acl_alloc_node(context, level+size);
1246         root = acl_alloc_node(context, level++);
1247
1248         if (lo[size - 1] == hi[size - 1]) {
1249                 acl_gen_range(context, hi, lo, size, level, root, *pend);
1250         } else {
1251                 uint8_t limit_lo[64];
1252                 uint8_t limit_hi[64];
1253                 uint8_t hi_ff = UINT8_MAX;
1254                 uint8_t lo_00 = 0;
1255
1256                 memset(limit_lo, 0, RTE_DIM(limit_lo));
1257                 memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi));
1258
1259                 for (n = size - 2; n >= 0; n--) {
1260                         hi_ff = (uint8_t)(hi_ff & hi[n]);
1261                         lo_00 = (uint8_t)(lo_00 | lo[n]);
1262                 }
1263
1264                 if (hi_ff != UINT8_MAX) {
1265                         limit_lo[size - 1] = hi[size - 1];
1266                         acl_gen_range(context, hi, limit_lo, size, level,
1267                                 root, *pend);
1268                 }
1269
1270                 if (lo_00 != 0) {
1271                         limit_hi[size - 1] = lo[size - 1];
1272                         acl_gen_range(context, limit_hi, lo, size, level,
1273                                 root, *pend);
1274                 }
1275
1276                 if (hi[size - 1] - lo[size - 1] > 1 ||
1277                                 lo_00 == 0 ||
1278                                 hi_ff == UINT8_MAX) {
1279                         limit_lo[size-1] = (uint8_t)(lo[size-1] + (lo_00 != 0));
1280                         limit_hi[size-1] = (uint8_t)(hi[size-1] -
1281                                 (hi_ff != UINT8_MAX));
1282                         acl_gen_range(context, limit_hi, limit_lo, size,
1283                                 level, root, *pend);
1284                 }
1285         }
1286         return root;
1287 }
1288
1289 static struct rte_acl_node *
1290 acl_gen_mask_trie(struct acl_build_context *context,
1291         const void *value, const void *mask,
1292         int size, int level, struct rte_acl_node **pend)
1293 {
1294         int32_t n;
1295         struct rte_acl_node *root;
1296         struct rte_acl_node *node, *prev;
1297         struct rte_acl_bitset bits;
1298         const uint8_t *val = (const uint8_t *)value;
1299         const uint8_t *msk = (const uint8_t *)mask;
1300
1301         root = acl_alloc_node(context, level++);
1302         prev = root;
1303
1304         for (n = size - 1; n >= 0; n--) {
1305                 node = acl_alloc_node(context, level++);
1306                 acl_gen_mask(&bits, val[n] & msk[n], msk[n]);
1307                 acl_add_ptr(context, prev, node, &bits);
1308                 prev = node;
1309         }
1310
1311         *pend = prev;
1312         return root;
1313 }
1314
1315 static struct rte_acl_node *
1316 build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
1317         struct rte_acl_build_rule **last, uint32_t *count)
1318 {
1319         uint32_t n, m;
1320         int field_index, node_count;
1321         struct rte_acl_node *trie;
1322         struct rte_acl_build_rule *prev, *rule;
1323         struct rte_acl_node *end, *merge, *root, *end_prev;
1324         const struct rte_acl_field *fld;
1325         struct rte_acl_bitset level_bits[RTE_ACL_MAX_LEVELS];
1326
1327         prev = head;
1328         rule = head;
1329
1330         trie = acl_alloc_node(context, 0);
1331         if (trie == NULL)
1332                 return NULL;
1333
1334         while (rule != NULL) {
1335
1336                 root = acl_alloc_node(context, 0);
1337                 if (root == NULL)
1338                         return NULL;
1339
1340                 root->ref_count = 1;
1341                 end = root;
1342
1343                 for (n = 0; n < rule->config->num_fields; n++) {
1344
1345                         field_index = rule->config->defs[n].field_index;
1346                         fld = rule->f->field + field_index;
1347                         end_prev = end;
1348
1349                         /* build a mini-trie for this field */
1350                         switch (rule->config->defs[n].type) {
1351
1352                         case RTE_ACL_FIELD_TYPE_BITMASK:
1353                                 merge = acl_gen_mask_trie(context,
1354                                         &fld->value,
1355                                         &fld->mask_range,
1356                                         rule->config->defs[n].size,
1357                                         end->level + 1,
1358                                         &end);
1359                                 break;
1360
1361                         case RTE_ACL_FIELD_TYPE_MASK:
1362                         {
1363                                 /*
1364                                  * set msb for the size of the field and
1365                                  * all higher bits.
1366                                  */
1367                                 uint64_t mask;
1368
1369                                 if (fld->mask_range.u32 == 0) {
1370                                         mask = 0;
1371
1372                                 /*
1373                                  * arithmetic right shift for the length of
1374                                  * the mask less the msb.
1375                                  */
1376                                 } else {
1377                                         mask = -1 <<
1378                                                 (rule->config->defs[n].size *
1379                                                 CHAR_BIT - fld->mask_range.u32);
1380                                 }
1381
1382                                 /* gen a mini-trie for this field */
1383                                 merge = acl_gen_mask_trie(context,
1384                                         &fld->value,
1385                                         (char *)&mask,
1386                                         rule->config->defs[n].size,
1387                                         end->level + 1,
1388                                         &end);
1389                         }
1390                         break;
1391
1392                         case RTE_ACL_FIELD_TYPE_RANGE:
1393                                 merge = acl_gen_range_trie(context,
1394                                         &rule->f->field[field_index].value,
1395                                         &rule->f->field[field_index].mask_range,
1396                                         rule->config->defs[n].size,
1397                                         end->level + 1,
1398                                         &end);
1399                                 break;
1400
1401                         default:
1402                                 RTE_LOG(ERR, ACL,
1403                                         "Error in rule[%u] type - %hhu\n",
1404                                         rule->f->data.userdata,
1405                                         rule->config->defs[n].type);
1406                                 return NULL;
1407                         }
1408
1409                         /* merge this field on to the end of the rule */
1410                         if (acl_merge_trie(context, end_prev, merge, 0,
1411                                         0, NULL) != 0) {
1412                                 return NULL;
1413                         }
1414                 }
1415
1416                 end->match_flag = ++context->num_build_rules;
1417
1418                 /*
1419                  * Setup the results for this rule.
1420                  * The result and priority of each category.
1421                  */
1422                 if (end->mrt == NULL &&
1423                                 (end->mrt = acl_build_alloc(context, 1,
1424                                 sizeof(*end->mrt))) == NULL)
1425                         return NULL;
1426
1427                 for (m = 0; m < context->cfg.num_categories; m++) {
1428                         if (rule->f->data.category_mask & (1 << m)) {
1429                                 end->mrt->results[m] = rule->f->data.userdata;
1430                                 end->mrt->priority[m] = rule->f->data.priority;
1431                         } else {
1432                                 end->mrt->results[m] = 0;
1433                                 end->mrt->priority[m] = 0;
1434                         }
1435                 }
1436
1437                 node_count = context->num_nodes;
1438
1439                 memset(&level_bits[0], UINT8_MAX, sizeof(level_bits));
1440                 build_subset_mask(root, &level_bits[0], 0);
1441                 mark_subtree(trie, &level_bits[0], 0, end->match_flag);
1442                 (*count)++;
1443
1444                 /* merge this rule into the trie */
1445                 if (acl_merge_trie(context, trie, root, 0, end->match_flag,
1446                         NULL))
1447                         return NULL;
1448
1449                 node_count = context->num_nodes - node_count;
1450                 if (node_count > NODE_MAX) {
1451                         *last = prev;
1452                         return trie;
1453                 }
1454
1455                 prev = rule;
1456                 rule = rule->next;
1457         }
1458
1459         *last = NULL;
1460         return trie;
1461 }
1462
1463 static int
1464 acl_calc_wildness(struct rte_acl_build_rule *head,
1465         const struct rte_acl_config *config)
1466 {
1467         uint32_t n;
1468         struct rte_acl_build_rule *rule;
1469
1470         for (rule = head; rule != NULL; rule = rule->next) {
1471
1472                 for (n = 0; n < config->num_fields; n++) {
1473
1474                         double wild = 0;
1475                         double size = CHAR_BIT * config->defs[n].size;
1476                         int field_index = config->defs[n].field_index;
1477                         const struct rte_acl_field *fld = rule->f->field +
1478                                 field_index;
1479
1480                         switch (rule->config->defs[n].type) {
1481                         case RTE_ACL_FIELD_TYPE_BITMASK:
1482                                 wild = (size - __builtin_popcount(
1483                                         fld->mask_range.u8)) /
1484                                         size;
1485                                 break;
1486
1487                         case RTE_ACL_FIELD_TYPE_MASK:
1488                                 wild = (size - fld->mask_range.u32) / size;
1489                                 break;
1490
1491                         case RTE_ACL_FIELD_TYPE_RANGE:
1492                                 switch (rule->config->defs[n].size) {
1493                                 case sizeof(uint8_t):
1494                                         wild = ((double)fld->mask_range.u8 -
1495                                                 fld->value.u8) / UINT8_MAX;
1496                                         break;
1497                                 case sizeof(uint16_t):
1498                                         wild = ((double)fld->mask_range.u16 -
1499                                                 fld->value.u16) / UINT16_MAX;
1500                                         break;
1501                                 case sizeof(uint32_t):
1502                                         wild = ((double)fld->mask_range.u32 -
1503                                                 fld->value.u32) / UINT32_MAX;
1504                                         break;
1505                                 case sizeof(uint64_t):
1506                                         wild = ((double)fld->mask_range.u64 -
1507                                                 fld->value.u64) / UINT64_MAX;
1508                                         break;
1509                                 default:
1510                                         RTE_LOG(ERR, ACL,
1511                                                 "%s(rule: %u) invalid %u-th "
1512                                                 "field, type: %hhu, "
1513                                                 "unknown size: %hhu\n",
1514                                                 __func__,
1515                                                 rule->f->data.userdata,
1516                                                 n,
1517                                                 rule->config->defs[n].type,
1518                                                 rule->config->defs[n].size);
1519                                         return -EINVAL;
1520                                 }
1521                                 break;
1522
1523                         default:
1524                                 RTE_LOG(ERR, ACL,
1525                                         "%s(rule: %u) invalid %u-th "
1526                                         "field, unknown type: %hhu\n",
1527                                         __func__,
1528                                         rule->f->data.userdata,
1529                                         n,
1530                                         rule->config->defs[n].type);
1531                                         return -EINVAL;
1532
1533                         }
1534
1535                         rule->wildness[field_index] = (uint32_t)(wild * 100);
1536                 }
1537         }
1538
1539         return 0;
1540 }
1541
1542 static void
1543 acl_rule_stats(struct rte_acl_build_rule *head, struct rte_acl_config *config)
1544 {
1545         struct rte_acl_build_rule *rule;
1546         uint32_t n, m, fields_deactivated = 0;
1547         uint32_t start = 0, deactivate = 0;
1548         int tally[RTE_ACL_MAX_LEVELS][TALLY_NUM];
1549
1550         memset(tally, 0, sizeof(tally));
1551
1552         for (rule = head; rule != NULL; rule = rule->next) {
1553
1554                 for (n = 0; n < config->num_fields; n++) {
1555                         uint32_t field_index = config->defs[n].field_index;
1556
1557                         tally[n][TALLY_0]++;
1558                         for (m = 1; m < RTE_DIM(wild_limits); m++) {
1559                                 if (rule->wildness[field_index] >=
1560                                                 wild_limits[m])
1561                                         tally[n][m]++;
1562                         }
1563                 }
1564
1565                 for (n = config->num_fields - 1; n > 0; n--) {
1566                         uint32_t field_index = config->defs[n].field_index;
1567
1568                         if (rule->wildness[field_index] == 100)
1569                                 tally[n][TALLY_DEPTH]++;
1570                         else
1571                                 break;
1572                 }
1573         }
1574
1575         /*
1576          * Look for any field that is always wild and drop it from the config
1577          * Only deactivate if all fields for a given input loop are deactivated.
1578          */
1579         for (n = 1; n < config->num_fields; n++) {
1580                 if (config->defs[n].input_index !=
1581                                 config->defs[n - 1].input_index) {
1582                         for (m = start; m < n; m++)
1583                                 tally[m][TALLY_DEACTIVATED] = deactivate;
1584                         fields_deactivated += deactivate;
1585                         start = n;
1586                         deactivate = 1;
1587                 }
1588
1589                 /* if the field is not always completely wild */
1590                 if (tally[n][TALLY_100] != tally[n][TALLY_0])
1591                         deactivate = 0;
1592         }
1593
1594         for (m = start; m < n; m++)
1595                 tally[m][TALLY_DEACTIVATED] = deactivate;
1596
1597         fields_deactivated += deactivate;
1598
1599         /* remove deactivated fields */
1600         if (fields_deactivated) {
1601                 uint32_t k, l = 0;
1602
1603                 for (k = 0; k < config->num_fields; k++) {
1604                         if (tally[k][TALLY_DEACTIVATED] == 0) {
1605                                 memmove(&tally[l][0], &tally[k][0],
1606                                         TALLY_NUM * sizeof(tally[0][0]));
1607                                 memmove(&config->defs[l++],
1608                                         &config->defs[k],
1609                                         sizeof(struct rte_acl_field_def));
1610                         }
1611                 }
1612                 config->num_fields = l;
1613         }
1614 }
1615
1616 static int
1617 rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2)
1618 {
1619         uint32_t n;
1620
1621         for (n = 1; n < r1->config->num_fields; n++) {
1622                 int field_index = r1->config->defs[n].field_index;
1623
1624                 if (r1->wildness[field_index] != r2->wildness[field_index])
1625                         return (r1->wildness[field_index] -
1626                                 r2->wildness[field_index]);
1627         }
1628         return 0;
1629 }
1630
1631 static struct rte_acl_build_rule *
1632 sort_rules(struct rte_acl_build_rule *head)
1633 {
1634         struct rte_acl_build_rule *new_head;
1635         struct rte_acl_build_rule *l, *r, **p;
1636
1637         new_head = NULL;
1638         while (head != NULL) {
1639                 r = head;
1640                 head = r->next;
1641                 r->next = NULL;
1642                 if (new_head == NULL) {
1643                         new_head = r;
1644                 } else {
1645                         for (p = &new_head;
1646                                         (l = *p) != NULL &&
1647                                         rule_cmp_wildness(l, r) >= 0;
1648                                         p = &l->next)
1649                                 ;
1650
1651                         r->next = *p;
1652                         *p = r;
1653                 }
1654         }
1655
1656         return new_head;
1657 }
1658
1659 static uint32_t
1660 acl_build_index(const struct rte_acl_config *config, uint32_t *data_index)
1661 {
1662         uint32_t n, m;
1663         int32_t last_header;
1664
1665         m = 0;
1666         last_header = -1;
1667
1668         for (n = 0; n < config->num_fields; n++) {
1669                 if (last_header != config->defs[n].input_index) {
1670                         last_header = config->defs[n].input_index;
1671                         data_index[m++] = config->defs[n].offset;
1672                 }
1673         }
1674
1675         return m;
1676 }
1677
1678 static struct rte_acl_build_rule *
1679 build_one_trie(struct acl_build_context *context,
1680         struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],
1681         uint32_t n)
1682 {
1683         struct rte_acl_build_rule *last;
1684         struct rte_acl_config *config;
1685
1686         config = rule_sets[n]->config;
1687
1688         acl_rule_stats(rule_sets[n], config);
1689         rule_sets[n] = sort_rules(rule_sets[n]);
1690
1691         context->tries[n].type = RTE_ACL_FULL_TRIE;
1692         context->tries[n].count = 0;
1693
1694         context->tries[n].num_data_indexes = acl_build_index(config,
1695                 context->data_indexes[n]);
1696         context->tries[n].data_index = context->data_indexes[n];
1697
1698         context->bld_tries[n].trie = build_trie(context, rule_sets[n],
1699                 &last, &context->tries[n].count);
1700
1701         return last;
1702 }
1703
1704 static int
1705 acl_build_tries(struct acl_build_context *context,
1706         struct rte_acl_build_rule *head)
1707 {
1708         int32_t rc;
1709         uint32_t n, num_tries;
1710         struct rte_acl_config *config;
1711         struct rte_acl_build_rule *last;
1712         struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES];
1713
1714         config = head->config;
1715         rule_sets[0] = head;
1716
1717         /* initialize tries */
1718         for (n = 0; n < RTE_DIM(context->tries); n++) {
1719                 context->tries[n].type = RTE_ACL_UNUSED_TRIE;
1720                 context->bld_tries[n].trie = NULL;
1721                 context->tries[n].count = 0;
1722                 context->tries[n].smallest = INT32_MAX;
1723         }
1724
1725         context->tries[0].type = RTE_ACL_FULL_TRIE;
1726
1727         /* calc wildness of each field of each rule */
1728         rc = acl_calc_wildness(head, config);
1729         if (rc != 0)
1730                 return rc;
1731
1732         for (n = 0;; n = num_tries) {
1733
1734                 num_tries = n + 1;
1735
1736                 last = build_one_trie(context, rule_sets, n);
1737                 if (context->bld_tries[n].trie == NULL) {
1738                         RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1739                         return -ENOMEM;
1740                 }
1741
1742                 /* Build of the last trie completed. */
1743                 if (last == NULL)
1744                         break;
1745
1746                 if (num_tries == RTE_DIM(context->tries)) {
1747                         RTE_LOG(ERR, ACL,
1748                                 "Exceeded max number of tries: %u\n",
1749                                 num_tries);
1750                         return -ENOMEM;
1751                 }
1752
1753                 /* Trie is getting too big, split remaining rule set. */
1754                 rule_sets[num_tries] = last->next;
1755                 last->next = NULL;
1756                 acl_free_node(context, context->bld_tries[n].trie);
1757
1758                 /* Create a new copy of config for remaining rules. */
1759                 config = acl_build_alloc(context, 1, sizeof(*config));
1760                 if (config == NULL) {
1761                         RTE_LOG(ERR, ACL,
1762                                 "New config allocation for %u-th "
1763                                 "trie failed\n", num_tries);
1764                         return -ENOMEM;
1765                 }
1766
1767                 memcpy(config, rule_sets[n]->config, sizeof(*config));
1768
1769                 /* Make remaining rules use new config. */
1770                 for (head = rule_sets[num_tries]; head != NULL;
1771                                 head = head->next)
1772                         head->config = config;
1773
1774                 /* Rebuild the trie for the reduced rule-set. */
1775                 last = build_one_trie(context, rule_sets, n);
1776                 if (context->bld_tries[n].trie == NULL || last != NULL) {
1777                         RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
1778                         return -ENOMEM;
1779                 }
1780
1781         }
1782
1783         context->num_tries = num_tries;
1784         return 0;
1785 }
1786
1787 static void
1788 acl_build_log(const struct acl_build_context *ctx)
1789 {
1790         uint32_t n;
1791
1792         RTE_LOG(DEBUG, ACL, "Build phase for ACL \"%s\":\n"
1793                 "nodes created: %u\n"
1794                 "memory consumed: %zu\n",
1795                 ctx->acx->name,
1796                 ctx->num_nodes,
1797                 ctx->pool.alloc);
1798
1799         for (n = 0; n < RTE_DIM(ctx->tries); n++) {
1800                 if (ctx->tries[n].count != 0)
1801                         RTE_LOG(DEBUG, ACL,
1802                                 "trie %u: number of rules: %u, indexes: %u\n",
1803                                 n, ctx->tries[n].count,
1804                                 ctx->tries[n].num_data_indexes);
1805         }
1806 }
1807
1808 static int
1809 acl_build_rules(struct acl_build_context *bcx)
1810 {
1811         struct rte_acl_build_rule *br, *head;
1812         const struct rte_acl_rule *rule;
1813         uint32_t *wp;
1814         uint32_t fn, i, n, num;
1815         size_t ofs, sz;
1816
1817         fn = bcx->cfg.num_fields;
1818         n = bcx->acx->num_rules;
1819         ofs = n * sizeof(*br);
1820         sz = ofs + n * fn * sizeof(*wp);
1821
1822         br = tb_alloc(&bcx->pool, sz);
1823         if (br == NULL) {
1824                 RTE_LOG(ERR, ACL, "ACL context %s: failed to create a copy "
1825                         "of %u build rules (%zu bytes)\n",
1826                         bcx->acx->name, n, sz);
1827                 return -ENOMEM;
1828         }
1829
1830         wp = (uint32_t *)((uintptr_t)br + ofs);
1831         num = 0;
1832         head = NULL;
1833
1834         for (i = 0; i != n; i++) {
1835                 rule = (const struct rte_acl_rule *)
1836                         ((uintptr_t)bcx->acx->rules + bcx->acx->rule_sz * i);
1837                 if ((rule->data.category_mask & bcx->category_mask) != 0) {
1838                         br[num].next = head;
1839                         br[num].config = &bcx->cfg;
1840                         br[num].f = rule;
1841                         br[num].wildness = wp;
1842                         wp += fn;
1843                         head = br + num;
1844                         num++;
1845                 }
1846         }
1847
1848         bcx->num_rules = num;
1849         bcx->build_rules = head;
1850
1851         return 0;
1852 }
1853
1854 /*
1855  * Copy data_indexes for each trie into RT location.
1856  */
1857 static void
1858 acl_set_data_indexes(struct rte_acl_ctx *ctx)
1859 {
1860         uint32_t i, n, ofs;
1861
1862         ofs = 0;
1863         for (i = 0; i != ctx->num_tries; i++) {
1864                 n = ctx->trie[i].num_data_indexes;
1865                 memcpy(ctx->data_indexes + ofs, ctx->trie[i].data_index,
1866                         n * sizeof(ctx->data_indexes[0]));
1867                 ctx->trie[i].data_index = ctx->data_indexes + ofs;
1868                 ofs += RTE_ACL_MAX_FIELDS;
1869         }
1870 }
1871
1872
1873 int
1874 rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
1875 {
1876         int rc;
1877         struct acl_build_context bcx;
1878
1879         if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
1880                         cfg->num_categories > RTE_ACL_MAX_CATEGORIES)
1881                 return -EINVAL;
1882
1883         acl_build_reset(ctx);
1884
1885         memset(&bcx, 0, sizeof(bcx));
1886         bcx.acx = ctx;
1887         bcx.pool.alignment = ACL_POOL_ALIGN;
1888         bcx.pool.min_alloc = ACL_POOL_ALLOC_MIN;
1889         bcx.cfg = *cfg;
1890         bcx.category_mask = LEN2MASK(bcx.cfg.num_categories);
1891
1892
1893         /* Create a build rules copy. */
1894         rc = acl_build_rules(&bcx);
1895         if (rc != 0)
1896                 return rc;
1897
1898         /* No rules to build for that context+config */
1899         if (bcx.build_rules == NULL) {
1900                 rc = -EINVAL;
1901
1902         /* build internal trie representation. */
1903         } else if ((rc = acl_build_tries(&bcx, bcx.build_rules)) == 0) {
1904
1905                 /* allocate and fill run-time  structures. */
1906                 rc = rte_acl_gen(ctx, bcx.tries, bcx.bld_tries,
1907                                 bcx.num_tries, bcx.cfg.num_categories,
1908                                 RTE_ACL_MAX_FIELDS * RTE_DIM(bcx.tries) *
1909                                 sizeof(ctx->data_indexes[0]),
1910                                 bcx.num_build_rules + 1);
1911                 if (rc == 0) {
1912
1913                         /* set data indexes. */
1914                         acl_set_data_indexes(ctx);
1915
1916                         /* copy in build config. */
1917                         ctx->config = *cfg;
1918                 }
1919         }
1920
1921         acl_build_log(&bcx);
1922
1923         /* cleanup after build. */
1924         tb_free_pool(&bcx.pool);
1925         return rc;
1926 }