lib/librte_acl/acl_gen.c

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