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