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