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