1 /*- 2 * BSD LICENSE 3 * 4 * Copyright(c) 2010-2014 Intel Corporation. All rights reserved. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name of Intel Corporation nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #include <rte_acl.h> 35 #include "acl.h" 36 37 #define QRANGE_MIN ((uint8_t)INT8_MIN) 38 39 #define RTE_ACL_VERIFY(exp) do { \ 40 if (!(exp)) \ 41 rte_panic("line %d\tassert \"" #exp "\" failed\n", __LINE__); \ 42 } while (0) 43 44 struct acl_node_counters { 45 int32_t match; 46 int32_t match_used; 47 int32_t single; 48 int32_t quad; 49 int32_t quad_vectors; 50 int32_t dfa; 51 int32_t dfa_gr64; 52 }; 53 54 struct rte_acl_indices { 55 int32_t dfa_index; 56 int32_t quad_index; 57 int32_t single_index; 58 int32_t match_index; 59 int32_t match_start; 60 }; 61 62 static void 63 acl_gen_log_stats(const struct rte_acl_ctx *ctx, 64 const struct acl_node_counters *counts, 65 const struct rte_acl_indices *indices, 66 size_t max_size) 67 { 68 RTE_LOG(DEBUG, ACL, "Gen phase for ACL \"%s\":\n" 69 "runtime memory footprint on socket %d:\n" 70 "single nodes/bytes used: %d/%zu\n" 71 "quad nodes/vectors/bytes used: %d/%d/%zu\n" 72 "DFA nodes/group64/bytes used: %d/%d/%zu\n" 73 "match nodes/bytes used: %d/%zu\n" 74 "total: %zu bytes\n" 75 "max limit: %zu bytes\n", 76 ctx->name, ctx->socket_id, 77 counts->single, counts->single * sizeof(uint64_t), 78 counts->quad, counts->quad_vectors, 79 (indices->quad_index - indices->dfa_index) * sizeof(uint64_t), 80 counts->dfa, counts->dfa_gr64, 81 indices->dfa_index * sizeof(uint64_t), 82 counts->match, 83 counts->match * sizeof(struct rte_acl_match_results), 84 ctx->mem_sz, 85 max_size); 86 } 87 88 static uint64_t 89 acl_dfa_gen_idx(const struct rte_acl_node *node, uint32_t index) 90 { 91 uint64_t idx; 92 uint32_t i; 93 94 idx = 0; 95 for (i = 0; i != RTE_DIM(node->dfa_gr64); i++) { 96 RTE_ACL_VERIFY(node->dfa_gr64[i] < RTE_ACL_DFA_GR64_NUM); 97 RTE_ACL_VERIFY(node->dfa_gr64[i] < node->fanout); 98 idx |= (i - node->dfa_gr64[i]) << 99 (6 + RTE_ACL_DFA_GR64_BIT * i); 100 } 101 102 return idx << (CHAR_BIT * sizeof(index)) | index | node->node_type; 103 } 104 105 static void 106 acl_dfa_fill_gr64(const struct rte_acl_node *node, 107 const uint64_t src[RTE_ACL_DFA_SIZE], uint64_t dst[RTE_ACL_DFA_SIZE]) 108 { 109 uint32_t i; 110 111 for (i = 0; i != RTE_DIM(node->dfa_gr64); i++) { 112 memcpy(dst + node->dfa_gr64[i] * RTE_ACL_DFA_GR64_SIZE, 113 src + i * RTE_ACL_DFA_GR64_SIZE, 114 RTE_ACL_DFA_GR64_SIZE * sizeof(dst[0])); 115 } 116 } 117 118 static uint32_t 119 acl_dfa_count_gr64(const uint64_t array_ptr[RTE_ACL_DFA_SIZE], 120 uint8_t gr64[RTE_ACL_DFA_GR64_NUM]) 121 { 122 uint32_t i, j, k; 123 124 k = 0; 125 for (i = 0; i != RTE_ACL_DFA_GR64_NUM; i++) { 126 gr64[i] = i; 127 for (j = 0; j != i; j++) { 128 if (memcmp(array_ptr + i * RTE_ACL_DFA_GR64_SIZE, 129 array_ptr + j * RTE_ACL_DFA_GR64_SIZE, 130 RTE_ACL_DFA_GR64_SIZE * 131 sizeof(array_ptr[0])) == 0) 132 break; 133 } 134 gr64[i] = (j != i) ? gr64[j] : k++; 135 } 136 137 return k; 138 } 139 140 static uint32_t 141 acl_node_fill_dfa(const struct rte_acl_node *node, 142 uint64_t dfa[RTE_ACL_DFA_SIZE], uint64_t no_match, int32_t resolved) 143 { 144 uint32_t n, x; 145 uint32_t ranges, last_bit; 146 struct rte_acl_node *child; 147 struct rte_acl_bitset *bits; 148 149 ranges = 0; 150 last_bit = 0; 151 152 for (n = 0; n < RTE_ACL_DFA_SIZE; n++) 153 dfa[n] = no_match; 154 155 for (x = 0; x < node->num_ptrs; x++) { 156 157 child = node->ptrs[x].ptr; 158 if (child == NULL) 159 continue; 160 161 bits = &node->ptrs[x].values; 162 for (n = 0; n < RTE_ACL_DFA_SIZE; n++) { 163 164 if (bits->bits[n / (sizeof(bits_t) * CHAR_BIT)] & 165 (1 << (n % (sizeof(bits_t) * CHAR_BIT)))) { 166 167 dfa[n] = resolved ? child->node_index : x; 168 ranges += (last_bit == 0); 169 last_bit = 1; 170 } else { 171 last_bit = 0; 172 } 173 } 174 } 175 176 return ranges; 177 } 178 179 /* 180 * Counts the number of groups of sequential bits that are 181 * either 0 or 1, as specified by the zero_one parameter. This is used to 182 * calculate the number of ranges in a node to see if it fits in a quad range 183 * node. 184 */ 185 static int 186 acl_count_sequential_groups(struct rte_acl_bitset *bits, int zero_one) 187 { 188 int n, ranges, last_bit; 189 190 ranges = 0; 191 last_bit = zero_one ^ 1; 192 193 for (n = QRANGE_MIN; n < UINT8_MAX + 1; n++) { 194 if (bits->bits[n / (sizeof(bits_t) * 8)] & 195 (1 << (n % (sizeof(bits_t) * 8)))) { 196 if (zero_one == 1 && last_bit != 1) 197 ranges++; 198 last_bit = 1; 199 } else { 200 if (zero_one == 0 && last_bit != 0) 201 ranges++; 202 last_bit = 0; 203 } 204 } 205 for (n = 0; n < QRANGE_MIN; n++) { 206 if (bits->bits[n / (sizeof(bits_t) * 8)] & 207 (1 << (n % (sizeof(bits_t) * 8)))) { 208 if (zero_one == 1 && last_bit != 1) 209 ranges++; 210 last_bit = 1; 211 } else { 212 if (zero_one == 0 && last_bit != 0) 213 ranges++; 214 last_bit = 0; 215 } 216 } 217 218 return ranges; 219 } 220 221 /* 222 * Count number of ranges spanned by the node's pointers 223 */ 224 static int 225 acl_count_fanout(struct rte_acl_node *node) 226 { 227 uint32_t n; 228 int ranges; 229 230 if (node->fanout != 0) 231 return node->fanout; 232 233 ranges = acl_count_sequential_groups(&node->values, 0); 234 235 for (n = 0; n < node->num_ptrs; n++) { 236 if (node->ptrs[n].ptr != NULL) 237 ranges += acl_count_sequential_groups( 238 &node->ptrs[n].values, 1); 239 } 240 241 node->fanout = ranges; 242 return node->fanout; 243 } 244 245 /* 246 * Determine the type of nodes and count each type 247 */ 248 static void 249 acl_count_trie_types(struct acl_node_counters *counts, 250 struct rte_acl_node *node, uint64_t no_match, int force_dfa) 251 { 252 uint32_t n; 253 int num_ptrs; 254 uint64_t dfa[RTE_ACL_DFA_SIZE]; 255 256 /* skip if this node has been counted */ 257 if (node->node_type != (uint32_t)RTE_ACL_NODE_UNDEFINED) 258 return; 259 260 if (node->match_flag != 0 || node->num_ptrs == 0) { 261 counts->match++; 262 node->node_type = RTE_ACL_NODE_MATCH; 263 return; 264 } 265 266 num_ptrs = acl_count_fanout(node); 267 268 /* Force type to dfa */ 269 if (force_dfa) 270 num_ptrs = RTE_ACL_DFA_SIZE; 271 272 /* determine node type based on number of ranges */ 273 if (num_ptrs == 1) { 274 counts->single++; 275 node->node_type = RTE_ACL_NODE_SINGLE; 276 } else if (num_ptrs <= RTE_ACL_QUAD_MAX) { 277 counts->quad++; 278 counts->quad_vectors += node->fanout; 279 node->node_type = RTE_ACL_NODE_QRANGE; 280 } else { 281 counts->dfa++; 282 node->node_type = RTE_ACL_NODE_DFA; 283 if (force_dfa != 0) { 284 /* always expand to a max number of nodes. */ 285 for (n = 0; n != RTE_DIM(node->dfa_gr64); n++) 286 node->dfa_gr64[n] = n; 287 node->fanout = n; 288 } else { 289 acl_node_fill_dfa(node, dfa, no_match, 0); 290 node->fanout = acl_dfa_count_gr64(dfa, node->dfa_gr64); 291 } 292 counts->dfa_gr64 += node->fanout; 293 } 294 295 /* 296 * recursively count the types of all children 297 */ 298 for (n = 0; n < node->num_ptrs; n++) { 299 if (node->ptrs[n].ptr != NULL) 300 acl_count_trie_types(counts, node->ptrs[n].ptr, 301 no_match, 0); 302 } 303 } 304 305 static void 306 acl_add_ptrs(struct rte_acl_node *node, uint64_t *node_array, uint64_t no_match, 307 int resolved) 308 { 309 uint32_t x; 310 int32_t m; 311 uint64_t *node_a, index, dfa[RTE_ACL_DFA_SIZE]; 312 313 acl_node_fill_dfa(node, dfa, no_match, resolved); 314 315 /* 316 * Rather than going from 0 to 256, the range count and 317 * the layout are from 80-ff then 0-7f due to signed compare 318 * for SSE (cmpgt). 319 */ 320 if (node->node_type == RTE_ACL_NODE_QRANGE) { 321 322 m = 0; 323 node_a = node_array; 324 index = dfa[QRANGE_MIN]; 325 *node_a++ = index; 326 327 for (x = QRANGE_MIN + 1; x < UINT8_MAX + 1; x++) { 328 if (dfa[x] != index) { 329 index = dfa[x]; 330 *node_a++ = index; 331 node->transitions[m++] = (uint8_t)(x - 1); 332 } 333 } 334 335 for (x = 0; x < INT8_MAX + 1; x++) { 336 if (dfa[x] != index) { 337 index = dfa[x]; 338 *node_a++ = index; 339 node->transitions[m++] = (uint8_t)(x - 1); 340 } 341 } 342 343 /* fill unused locations with max value - nothing is greater */ 344 for (; m < RTE_ACL_QUAD_SIZE; m++) 345 node->transitions[m] = INT8_MAX; 346 347 RTE_ACL_VERIFY(m <= RTE_ACL_QUAD_SIZE); 348 349 } else if (node->node_type == RTE_ACL_NODE_DFA && resolved) { 350 acl_dfa_fill_gr64(node, dfa, node_array); 351 } 352 } 353 354 /* 355 * Routine that allocates space for this node and recursively calls 356 * to allocate space for each child. Once all the children are allocated, 357 * then resolve all transitions for this node. 358 */ 359 static void 360 acl_gen_node(struct rte_acl_node *node, uint64_t *node_array, 361 uint64_t no_match, struct rte_acl_indices *index, int num_categories) 362 { 363 uint32_t n, sz, *qtrp; 364 uint64_t *array_ptr; 365 struct rte_acl_match_results *match; 366 367 if (node->node_index != RTE_ACL_NODE_UNDEFINED) 368 return; 369 370 array_ptr = NULL; 371 372 switch (node->node_type) { 373 case RTE_ACL_NODE_DFA: 374 array_ptr = &node_array[index->dfa_index]; 375 node->node_index = acl_dfa_gen_idx(node, index->dfa_index); 376 sz = node->fanout * RTE_ACL_DFA_GR64_SIZE; 377 index->dfa_index += sz; 378 for (n = 0; n < sz; n++) 379 array_ptr[n] = no_match; 380 break; 381 case RTE_ACL_NODE_SINGLE: 382 node->node_index = RTE_ACL_QUAD_SINGLE | index->single_index | 383 node->node_type; 384 array_ptr = &node_array[index->single_index]; 385 index->single_index += 1; 386 array_ptr[0] = no_match; 387 break; 388 case RTE_ACL_NODE_QRANGE: 389 array_ptr = &node_array[index->quad_index]; 390 acl_add_ptrs(node, array_ptr, no_match, 0); 391 qtrp = (uint32_t *)node->transitions; 392 node->node_index = qtrp[0]; 393 node->node_index <<= sizeof(index->quad_index) * CHAR_BIT; 394 node->node_index |= index->quad_index | node->node_type; 395 index->quad_index += node->fanout; 396 break; 397 case RTE_ACL_NODE_MATCH: 398 match = ((struct rte_acl_match_results *) 399 (node_array + index->match_start)); 400 for (n = 0; n != RTE_DIM(match->results); n++) 401 RTE_ACL_VERIFY(match->results[0] == 0); 402 memcpy(match + index->match_index, node->mrt, 403 sizeof(*node->mrt)); 404 node->node_index = index->match_index | node->node_type; 405 index->match_index += 1; 406 break; 407 case RTE_ACL_NODE_UNDEFINED: 408 RTE_ACL_VERIFY(node->node_type != 409 (uint32_t)RTE_ACL_NODE_UNDEFINED); 410 break; 411 } 412 413 /* recursively allocate space for all children */ 414 for (n = 0; n < node->num_ptrs; n++) { 415 if (node->ptrs[n].ptr != NULL) 416 acl_gen_node(node->ptrs[n].ptr, 417 node_array, 418 no_match, 419 index, 420 num_categories); 421 } 422 423 /* All children are resolved, resolve this node's pointers */ 424 switch (node->node_type) { 425 case RTE_ACL_NODE_DFA: 426 acl_add_ptrs(node, array_ptr, no_match, 1); 427 break; 428 case RTE_ACL_NODE_SINGLE: 429 for (n = 0; n < node->num_ptrs; n++) { 430 if (node->ptrs[n].ptr != NULL) 431 array_ptr[0] = node->ptrs[n].ptr->node_index; 432 } 433 break; 434 case RTE_ACL_NODE_QRANGE: 435 acl_add_ptrs(node, array_ptr, no_match, 1); 436 break; 437 case RTE_ACL_NODE_MATCH: 438 break; 439 case RTE_ACL_NODE_UNDEFINED: 440 RTE_ACL_VERIFY(node->node_type != 441 (uint32_t)RTE_ACL_NODE_UNDEFINED); 442 break; 443 } 444 } 445 446 static void 447 acl_calc_counts_indices(struct acl_node_counters *counts, 448 struct rte_acl_indices *indices, 449 struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries, 450 uint64_t no_match) 451 { 452 uint32_t n; 453 454 memset(indices, 0, sizeof(*indices)); 455 memset(counts, 0, sizeof(*counts)); 456 457 /* Get stats on nodes */ 458 for (n = 0; n < num_tries; n++) { 459 acl_count_trie_types(counts, node_bld_trie[n].trie, 460 no_match, 1); 461 } 462 463 indices->dfa_index = RTE_ACL_DFA_SIZE + 1; 464 indices->quad_index = indices->dfa_index + 465 counts->dfa_gr64 * RTE_ACL_DFA_GR64_SIZE; 466 indices->single_index = indices->quad_index + counts->quad_vectors; 467 indices->match_start = indices->single_index + counts->single + 1; 468 indices->match_start = RTE_ALIGN(indices->match_start, 469 (XMM_SIZE / sizeof(uint64_t))); 470 indices->match_index = 1; 471 } 472 473 /* 474 * Generate the runtime structure using build structure 475 */ 476 int 477 rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie, 478 struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries, 479 uint32_t num_categories, uint32_t data_index_sz, size_t max_size) 480 { 481 void *mem; 482 size_t total_size; 483 uint64_t *node_array, no_match; 484 uint32_t n, match_index; 485 struct rte_acl_match_results *match; 486 struct acl_node_counters counts; 487 struct rte_acl_indices indices; 488 489 no_match = RTE_ACL_NODE_MATCH; 490 491 /* Fill counts and indices arrays from the nodes. */ 492 acl_calc_counts_indices(&counts, &indices, 493 node_bld_trie, num_tries, no_match); 494 495 /* Allocate runtime memory (align to cache boundary) */ 496 total_size = RTE_ALIGN(data_index_sz, RTE_CACHE_LINE_SIZE) + 497 indices.match_start * sizeof(uint64_t) + 498 (counts.match + 1) * sizeof(struct rte_acl_match_results) + 499 XMM_SIZE; 500 501 if (total_size > max_size) { 502 RTE_LOG(DEBUG, ACL, 503 "Gen phase for ACL ctx \"%s\" exceeds max_size limit, " 504 "bytes required: %zu, allowed: %zu\n", 505 ctx->name, total_size, max_size); 506 return -ERANGE; 507 } 508 509 mem = rte_zmalloc_socket(ctx->name, total_size, RTE_CACHE_LINE_SIZE, 510 ctx->socket_id); 511 if (mem == NULL) { 512 RTE_LOG(ERR, ACL, 513 "allocation of %zu bytes on socket %d for %s failed\n", 514 total_size, ctx->socket_id, ctx->name); 515 return -ENOMEM; 516 } 517 518 /* Fill the runtime structure */ 519 match_index = indices.match_start; 520 node_array = (uint64_t *)((uintptr_t)mem + 521 RTE_ALIGN(data_index_sz, RTE_CACHE_LINE_SIZE)); 522 523 /* 524 * Setup the NOMATCH node (a SINGLE at the 525 * highest index, that points to itself) 526 */ 527 528 node_array[RTE_ACL_DFA_SIZE] = RTE_ACL_DFA_SIZE | RTE_ACL_NODE_SINGLE; 529 530 for (n = 0; n < RTE_ACL_DFA_SIZE; n++) 531 node_array[n] = no_match; 532 533 /* NOMATCH result at index 0 */ 534 match = ((struct rte_acl_match_results *)(node_array + match_index)); 535 memset(match, 0, sizeof(*match)); 536 537 for (n = 0; n < num_tries; n++) { 538 539 acl_gen_node(node_bld_trie[n].trie, node_array, no_match, 540 &indices, num_categories); 541 542 if (node_bld_trie[n].trie->node_index == no_match) 543 trie[n].root_index = 0; 544 else 545 trie[n].root_index = node_bld_trie[n].trie->node_index; 546 } 547 548 ctx->mem = mem; 549 ctx->mem_sz = total_size; 550 ctx->data_indexes = mem; 551 ctx->num_tries = num_tries; 552 ctx->num_categories = num_categories; 553 ctx->match_index = match_index; 554 ctx->no_match = no_match; 555 ctx->idle = node_array[RTE_ACL_DFA_SIZE]; 556 ctx->trans_table = node_array; 557 memcpy(ctx->trie, trie, sizeof(ctx->trie)); 558 559 acl_gen_log_stats(ctx, &counts, &indices, max_size); 560 return 0; 561 } 562