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