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