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