lib/librte_acl/acl_bld.c

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