lib/librte_acl/acl_bld.c

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