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