-/*-
- * BSD LICENSE
- *
- * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- * * Neither the name of Intel Corporation nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2010-2014 Intel Corporation
*/
#include <rte_acl.h>
struct rte_acl_build_rule *build_rules;
struct rte_acl_config cfg;
int32_t node_max;
+ int32_t cur_node_max;
uint32_t node;
uint32_t num_nodes;
uint32_t category_mask;
struct rte_acl_node *node_a, struct rte_acl_node *node_b,
uint32_t level, struct rte_acl_node **node_c);
-static int acl_merge(struct acl_build_context *context,
- struct rte_acl_node *node_a, struct rte_acl_node *node_b,
- int move, int a_subset, int level);
-
static void
acl_deref_ptr(struct acl_build_context *context,
struct rte_acl_node *node, int index);
for (n = 0; n < UINT8_MAX + 1; n++)
if (n >= low && n <= high)
bitset.bits[n / (sizeof(bits_t) * 8)] |=
- 1 << (n % (sizeof(bits_t) * 8));
+ 1U << (n % (sizeof(bits_t) * CHAR_BIT));
return acl_add_ptr(context, root, node, &bitset);
}
if ((n & mask) == value) {
range++;
bitset->bits[n / (sizeof(bits_t) * 8)] |=
- 1 << (n % (sizeof(bits_t) * 8));
+ 1U << (n % (sizeof(bits_t) * CHAR_BIT));
}
}
return range;
return n;
}
-/*
- * Check if all bits in the bitset are on
- */
-static int
-acl_full(struct rte_acl_node *node)
-{
- uint32_t n;
- bits_t all_bits = -1;
-
- for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
- all_bits &= node->values.bits[n];
- return all_bits == -1;
-}
-
-/*
- * Check if all bits in the bitset are off
- */
-static int
-acl_empty(struct rte_acl_node *node)
-{
- uint32_t n;
-
- if (node->ref_count == 0) {
- for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
- if (0 != node->values.bits[n])
- return 0;
- }
- return 1;
- } else {
- return 0;
- }
-}
-
-/*
- * Compute intersection of A and B
- * return 1 if there is an intersection else 0.
- */
-static int
-acl_intersect(struct rte_acl_bitset *a_bits,
- struct rte_acl_bitset *b_bits,
- struct rte_acl_bitset *intersect)
-{
- uint32_t n;
- bits_t all_bits = 0;
-
- for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) {
- intersect->bits[n] = a_bits->bits[n] & b_bits->bits[n];
- all_bits |= intersect->bits[n];
- }
- return all_bits != 0;
-}
-
/*
* Duplicate a node
*/
}
}
-/*
- * Exclude bitset from a node pointer
- * returns 0 if poiter was deref'd
- * 1 otherwise.
- */
-static int
-acl_exclude_ptr(struct acl_build_context *context,
- struct rte_acl_node *node,
- int index,
- struct rte_acl_bitset *b_bits)
-{
- int retval = 1;
-
- /*
- * remove bitset from node pointer and deref
- * if the bitset becomes empty.
- */
- if (!acl_exclude(&node->ptrs[index].values,
- &node->ptrs[index].values,
- b_bits)) {
- acl_deref_ptr(context, node, index);
- node->ptrs[index].ptr = NULL;
- retval = 0;
- }
-
- /* exclude bits from the composite bits for the node */
- acl_exclude(&node->values, &node->values, b_bits);
- return retval;
-}
-
-/*
- * Remove a bitset from src ptr and move remaining ptr to dst
- */
-static int
-acl_move_ptr(struct acl_build_context *context,
- struct rte_acl_node *dst,
- struct rte_acl_node *src,
- int index,
- struct rte_acl_bitset *b_bits)
-{
- int rc;
-
- if (b_bits != NULL)
- if (!acl_exclude_ptr(context, src, index, b_bits))
- return 0;
-
- /* add src pointer to dst node */
- rc = acl_add_ptr(context, dst, src->ptrs[index].ptr,
- &src->ptrs[index].values);
- if (rc < 0)
- return rc;
-
- /* remove ptr from src */
- acl_exclude_ptr(context, src, index, &src->ptrs[index].values);
- return 1;
-}
-
/*
* acl_exclude rte_acl_bitset from src and copy remaining pointer to dst
*/
}
}
-/*
- * acl_merge helper routine.
- */
-static int
-acl_merge_intersect(struct acl_build_context *context,
- struct rte_acl_node *node_a, uint32_t idx_a,
- struct rte_acl_node *node_b, uint32_t idx_b,
- int next_move, int level,
- struct rte_acl_bitset *intersect_ptr)
-{
- struct rte_acl_node *node_c;
-
- /* Duplicate A for intersection */
- node_c = acl_dup_node(context, node_a->ptrs[idx_a].ptr);
-
- /* Remove intersection from A */
- acl_exclude_ptr(context, node_a, idx_a, intersect_ptr);
-
- /*
- * Added link from A to C for all transitions
- * in the intersection
- */
- if (acl_add_ptr(context, node_a, node_c, intersect_ptr) < 0)
- return -1;
-
- /* merge B->node into C */
- return acl_merge(context, node_c, node_b->ptrs[idx_b].ptr, next_move,
- 0, level + 1);
-}
-
-
-/*
- * Merge the children of nodes A and B together.
- *
- * if match node
- * For each category
- * node A result = highest priority result
- * if any pointers in A intersect with any in B
- * For each intersection
- * C = copy of node that A points to
- * remove intersection from A pointer
- * add a pointer to A that points to C for the intersection
- * Merge C and node that B points to
- * Compact the pointers in A and B
- * if move flag
- * If B has only one reference
- * Move B pointers to A
- * else
- * Copy B pointers to A
- */
-static int
-acl_merge(struct acl_build_context *context,
- struct rte_acl_node *node_a, struct rte_acl_node *node_b,
- int move, int a_subset, int level)
-{
- uint32_t n, m, ptrs_a, ptrs_b;
- uint32_t min_add_a, min_add_b;
- int intersect_type;
- int node_intersect_type;
- int b_full, next_move, rc;
- struct rte_acl_bitset intersect_values;
- struct rte_acl_bitset intersect_ptr;
-
- min_add_a = 0;
- min_add_b = 0;
- intersect_type = 0;
- node_intersect_type = 0;
-
- if (level == 0)
- a_subset = 1;
-
- /*
- * Resolve match priorities
- */
- if (node_a->match_flag != 0 || node_b->match_flag != 0) {
-
- if (node_a->match_flag == 0 || node_b->match_flag == 0)
- RTE_LOG(ERR, ACL, "Not both matches\n");
-
- if (node_b->match_flag < node_a->match_flag)
- RTE_LOG(ERR, ACL, "Not same match\n");
-
- for (n = 0; n < context->cfg.num_categories; n++) {
- if (node_a->mrt->priority[n] <
- node_b->mrt->priority[n]) {
- node_a->mrt->priority[n] =
- node_b->mrt->priority[n];
- node_a->mrt->results[n] =
- node_b->mrt->results[n];
- }
- }
- }
-
- /*
- * If the two node transitions intersect then merge the transitions.
- * Check intersection for entire node (all pointers)
- */
- node_intersect_type = acl_intersect_type(&node_a->values,
- &node_b->values,
- &intersect_values);
-
- if (node_intersect_type & ACL_INTERSECT) {
-
- b_full = acl_full(node_b);
-
- min_add_b = node_b->min_add;
- node_b->min_add = node_b->num_ptrs;
- ptrs_b = node_b->num_ptrs;
-
- min_add_a = node_a->min_add;
- node_a->min_add = node_a->num_ptrs;
- ptrs_a = node_a->num_ptrs;
-
- for (n = 0; n < ptrs_a; n++) {
- for (m = 0; m < ptrs_b; m++) {
-
- if (node_a->ptrs[n].ptr == NULL ||
- node_b->ptrs[m].ptr == NULL ||
- node_a->ptrs[n].ptr ==
- node_b->ptrs[m].ptr)
- continue;
-
- intersect_type = acl_intersect_type(
- &node_a->ptrs[n].values,
- &node_b->ptrs[m].values,
- &intersect_ptr);
-
- /* If this node is not a 'match' node */
- if ((intersect_type & ACL_INTERSECT) &&
- (context->cfg.num_categories != 1 ||
- !(node_a->ptrs[n].ptr->match_flag))) {
-
- /*
- * next merge is a 'move' pointer,
- * if this one is and B is a
- * subset of the intersection.
- */
- next_move = move &&
- (intersect_type &
- ACL_INTERSECT_B) == 0;
-
- if (a_subset && b_full) {
- rc = acl_merge(context,
- node_a->ptrs[n].ptr,
- node_b->ptrs[m].ptr,
- next_move,
- 1, level + 1);
- if (rc != 0)
- return rc;
- } else {
- rc = acl_merge_intersect(
- context, node_a, n,
- node_b, m, next_move,
- level, &intersect_ptr);
- if (rc != 0)
- return rc;
- }
- }
- }
- }
- }
-
- /* Compact pointers */
- node_a->min_add = min_add_a;
- acl_compact_node_ptrs(node_a);
- node_b->min_add = min_add_b;
- acl_compact_node_ptrs(node_b);
-
- /*
- * Either COPY or MOVE pointers from B to A
- */
- acl_intersect(&node_a->values, &node_b->values, &intersect_values);
-
- if (move && node_b->ref_count == 1) {
- for (m = 0; m < node_b->num_ptrs; m++) {
- if (node_b->ptrs[m].ptr != NULL &&
- acl_move_ptr(context, node_a, node_b, m,
- &intersect_values) < 0)
- return -1;
- }
- } else {
- for (m = 0; m < node_b->num_ptrs; m++) {
- if (node_b->ptrs[m].ptr != NULL &&
- acl_copy_ptr(context, node_a, node_b, m,
- &intersect_values) < 0)
- return -1;
- }
- }
-
- /*
- * Free node if its empty (no longer used)
- */
- if (acl_empty(node_b))
- acl_free_node(context, node_b);
- return 0;
-}
-
static int
acl_resolve_leaf(struct acl_build_context *context,
struct rte_acl_node *node_a,
}
static void
-acl_gen_range(struct acl_build_context *context,
- const uint8_t *hi, const uint8_t *lo, int size, int level,
- struct rte_acl_node *root, struct rte_acl_node *end)
+acl_gen_full_range(struct acl_build_context *context, struct rte_acl_node *root,
+ struct rte_acl_node *end, int size, int level)
{
struct rte_acl_node *node, *prev;
uint32_t n;
prev = root;
for (n = size - 1; n > 0; n--) {
node = acl_alloc_node(context, level++);
- acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+ acl_add_ptr_range(context, prev, node, 0, UINT8_MAX);
prev = node;
}
- acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
+ acl_add_ptr_range(context, prev, end, 0, UINT8_MAX);
+}
+
+static void
+acl_gen_range_mdl(struct acl_build_context *context, struct rte_acl_node *root,
+ struct rte_acl_node *end, uint8_t lo, uint8_t hi, int size, int level)
+{
+ struct rte_acl_node *node;
+
+ node = acl_alloc_node(context, level++);
+ acl_add_ptr_range(context, root, node, lo, hi);
+ acl_gen_full_range(context, node, end, size - 1, level);
+}
+
+static void
+acl_gen_range_low(struct acl_build_context *context, struct rte_acl_node *root,
+ struct rte_acl_node *end, const uint8_t *lo, int size, int level)
+{
+ struct rte_acl_node *node;
+ uint32_t n;
+
+ n = size - 1;
+ if (n == 0) {
+ acl_add_ptr_range(context, root, end, lo[0], UINT8_MAX);
+ return;
+ }
+
+ node = acl_alloc_node(context, level++);
+ acl_add_ptr_range(context, root, node, lo[n], lo[n]);
+
+ /* generate lower-bound sub-trie */
+ acl_gen_range_low(context, node, end, lo, n, level);
+
+ /* generate middle sub-trie */
+ if (n > 1 && lo[n - 1] != UINT8_MAX)
+ acl_gen_range_mdl(context, node, end, lo[n - 1] + 1, UINT8_MAX,
+ n, level);
+}
+
+static void
+acl_gen_range_high(struct acl_build_context *context, struct rte_acl_node *root,
+ struct rte_acl_node *end, const uint8_t *hi, int size, int level)
+{
+ struct rte_acl_node *node;
+ uint32_t n;
+
+ n = size - 1;
+ if (n == 0) {
+ acl_add_ptr_range(context, root, end, 0, hi[0]);
+ return;
+ }
+
+ node = acl_alloc_node(context, level++);
+ acl_add_ptr_range(context, root, node, hi[n], hi[n]);
+
+ /* generate upper-bound sub-trie */
+ acl_gen_range_high(context, node, end, hi, n, level);
+
+ /* generate middle sub-trie */
+ if (n > 1 && hi[n - 1] != 0)
+ acl_gen_range_mdl(context, node, end, 0, hi[n - 1] - 1,
+ n, level);
}
static struct rte_acl_node *
const void *min, const void *max,
int size, int level, struct rte_acl_node **pend)
{
- int32_t n;
- struct rte_acl_node *root;
- const uint8_t *lo = (const uint8_t *)min;
- const uint8_t *hi = (const uint8_t *)max;
+ int32_t k, n;
+ uint8_t hi_ff, lo_00;
+ struct rte_acl_node *node, *prev, *root;
+ const uint8_t *lo;
+ const uint8_t *hi;
+
+ lo = min;
+ hi = max;
- *pend = acl_alloc_node(context, level+size);
+ *pend = acl_alloc_node(context, level + size);
root = acl_alloc_node(context, level++);
+ prev = root;
- if (lo[size - 1] == hi[size - 1]) {
- acl_gen_range(context, hi, lo, size, level, root, *pend);
- } else {
- uint8_t limit_lo[64];
- uint8_t limit_hi[64];
- uint8_t hi_ff = UINT8_MAX;
- uint8_t lo_00 = 0;
+ /* build common sub-trie till possible */
+ for (n = size - 1; n > 0 && lo[n] == hi[n]; n--) {
+ node = acl_alloc_node(context, level++);
+ acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+ prev = node;
+ }
- memset(limit_lo, 0, RTE_DIM(limit_lo));
- memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi));
+ /* no branch needed, just one sub-trie */
+ if (n == 0) {
+ acl_add_ptr_range(context, prev, *pend, lo[0], hi[0]);
+ return root;
+ }
- for (n = size - 2; n >= 0; n--) {
- hi_ff = (uint8_t)(hi_ff & hi[n]);
- lo_00 = (uint8_t)(lo_00 | lo[n]);
- }
+ /* gather information about divirgent paths */
+ lo_00 = 0;
+ hi_ff = UINT8_MAX;
+ for (k = n - 1; k >= 0; k--) {
+ hi_ff &= hi[k];
+ lo_00 |= lo[k];
+ }
- if (hi_ff != UINT8_MAX) {
- limit_lo[size - 1] = hi[size - 1];
- acl_gen_range(context, hi, limit_lo, size, level,
- root, *pend);
- }
+ /* generate left (lower-bound) sub-trie */
+ if (lo_00 != 0)
+ acl_gen_range_low(context, prev, *pend, lo, n + 1, level);
- if (lo_00 != 0) {
- limit_hi[size - 1] = lo[size - 1];
- acl_gen_range(context, limit_hi, lo, size, level,
- root, *pend);
- }
+ /* generate right (upper-bound) sub-trie */
+ if (hi_ff != UINT8_MAX)
+ acl_gen_range_high(context, prev, *pend, hi, n + 1, level);
- if (hi[size - 1] - lo[size - 1] > 1 ||
- lo_00 == 0 ||
- hi_ff == UINT8_MAX) {
- limit_lo[size-1] = (uint8_t)(lo[size-1] + (lo_00 != 0));
- limit_hi[size-1] = (uint8_t)(hi[size-1] -
- (hi_ff != UINT8_MAX));
- acl_gen_range(context, limit_hi, limit_lo, size,
- level, root, *pend);
- }
+ /* generate sub-trie in the middle */
+ if (lo[n] + 1 != hi[n] || lo_00 == 0 || hi_ff == UINT8_MAX) {
+ lo_00 = lo[n] + (lo_00 != 0);
+ hi_ff = hi[n] - (hi_ff != UINT8_MAX);
+ acl_gen_range_mdl(context, prev, *pend, lo_00, hi_ff,
+ n + 1, level);
}
+
return root;
}
struct rte_acl_node *root;
struct rte_acl_node *node, *prev;
struct rte_acl_bitset bits;
- const uint8_t *val = (const uint8_t *)value;
- const uint8_t *msk = (const uint8_t *)mask;
+ const uint8_t *val = value;
+ const uint8_t *msk = mask;
root = acl_alloc_node(context, level++);
prev = root;
* all higher bits.
*/
uint64_t mask;
-
- if (fld->mask_range.u32 == 0) {
- mask = 0;
-
- /*
- * arithmetic right shift for the length of
- * the mask less the msb.
- */
- } else {
- mask = -1 <<
- (rule->config->defs[n].size *
- CHAR_BIT - fld->mask_range.u32);
- }
+ mask = RTE_ACL_MASKLEN_TO_BITMASK(
+ fld->mask_range.u32,
+ rule->config->defs[n].size);
/* gen a mini-trie for this field */
merge = acl_gen_mask_trie(context,
sizeof(*end->mrt));
for (m = context->cfg.num_categories; 0 != m--; ) {
- if (rule->f->data.category_mask & (1 << m)) {
+ if (rule->f->data.category_mask & (1U << m)) {
end->mrt->results[m] = rule->f->data.userdata;
end->mrt->priority[m] = rule->f->data.priority;
} else {
return NULL;
node_count = context->num_nodes - node_count;
- if (node_count > context->node_max) {
+ if (node_count > context->cur_node_max) {
*last = prev;
return trie;
}
return trie;
}
-static int
+static void
acl_calc_wildness(struct rte_acl_build_rule *head,
const struct rte_acl_config *config)
{
for (n = 0; n < config->num_fields; n++) {
double wild = 0;
- double size = CHAR_BIT * config->defs[n].size;
+ uint32_t bit_len = CHAR_BIT * config->defs[n].size;
+ uint64_t msk_val = RTE_LEN2MASK(bit_len,
+ typeof(msk_val));
+ double size = bit_len;
int field_index = config->defs[n].field_index;
const struct rte_acl_field *fld = rule->f->field +
field_index;
switch (rule->config->defs[n].type) {
case RTE_ACL_FIELD_TYPE_BITMASK:
- wild = (size - __builtin_popcount(
- fld->mask_range.u8)) /
+ wild = (size - __builtin_popcountll(
+ fld->mask_range.u64 & msk_val)) /
size;
break;
break;
case RTE_ACL_FIELD_TYPE_RANGE:
- switch (rule->config->defs[n].size) {
- case sizeof(uint8_t):
- wild = ((double)fld->mask_range.u8 -
- fld->value.u8) / UINT8_MAX;
- break;
- case sizeof(uint16_t):
- wild = ((double)fld->mask_range.u16 -
- fld->value.u16) / UINT16_MAX;
- break;
- case sizeof(uint32_t):
- wild = ((double)fld->mask_range.u32 -
- fld->value.u32) / UINT32_MAX;
- break;
- case sizeof(uint64_t):
- wild = ((double)fld->mask_range.u64 -
- fld->value.u64) / UINT64_MAX;
- break;
- default:
- RTE_LOG(ERR, ACL,
- "%s(rule: %u) invalid %u-th "
- "field, type: %hhu, "
- "unknown size: %hhu\n",
- __func__,
- rule->f->data.userdata,
- n,
- rule->config->defs[n].type,
- rule->config->defs[n].size);
- return -EINVAL;
- }
+ wild = (fld->mask_range.u64 & msk_val) -
+ (fld->value.u64 & msk_val);
+ wild = wild / msk_val;
break;
-
- default:
- RTE_LOG(ERR, ACL,
- "%s(rule: %u) invalid %u-th "
- "field, unknown type: %hhu\n",
- __func__,
- rule->f->data.userdata,
- n,
- rule->config->defs[n].type);
- return -EINVAL;
-
}
rule->wildness[field_index] = (uint32_t)(wild * 100);
}
}
-
- return 0;
}
static void
int field_index = r1->config->defs[n].field_index;
if (r1->wildness[field_index] != r2->wildness[field_index])
- return (r1->wildness[field_index] -
- r2->wildness[field_index]);
+ return r1->wildness[field_index] -
+ r2->wildness[field_index];
}
return 0;
}
+/*
+ * Split the rte_acl_build_rule list into two lists.
+ */
+static void
+rule_list_split(struct rte_acl_build_rule *source,
+ struct rte_acl_build_rule **list_a,
+ struct rte_acl_build_rule **list_b)
+{
+ struct rte_acl_build_rule *fast;
+ struct rte_acl_build_rule *slow;
+
+ if (source == NULL || source->next == NULL) {
+ /* length < 2 cases */
+ *list_a = source;
+ *list_b = NULL;
+ } else {
+ slow = source;
+ fast = source->next;
+ /* Advance 'fast' two nodes, and advance 'slow' one node */
+ while (fast != NULL) {
+ fast = fast->next;
+ if (fast != NULL) {
+ slow = slow->next;
+ fast = fast->next;
+ }
+ }
+ /* 'slow' is before the midpoint in the list, so split it in two
+ at that point. */
+ *list_a = source;
+ *list_b = slow->next;
+ slow->next = NULL;
+ }
+}
+
+/*
+ * Merge two sorted lists.
+ */
+static struct rte_acl_build_rule *
+rule_list_sorted_merge(struct rte_acl_build_rule *a,
+ struct rte_acl_build_rule *b)
+{
+ struct rte_acl_build_rule *result = NULL;
+ struct rte_acl_build_rule **last_next = &result;
+
+ while (1) {
+ if (a == NULL) {
+ *last_next = b;
+ break;
+ } else if (b == NULL) {
+ *last_next = a;
+ break;
+ }
+ if (rule_cmp_wildness(a, b) >= 0) {
+ *last_next = a;
+ last_next = &a->next;
+ a = a->next;
+ } else {
+ *last_next = b;
+ last_next = &b->next;
+ b = b->next;
+ }
+ }
+ return result;
+}
+
/*
* Sort list of rules based on the rules wildness.
+ * Use recursive mergesort algorithm.
*/
static struct rte_acl_build_rule *
sort_rules(struct rte_acl_build_rule *head)
{
- struct rte_acl_build_rule *new_head;
- struct rte_acl_build_rule *l, *r, **p;
-
- new_head = NULL;
- while (head != NULL) {
-
- /* remove element from the head of the old list. */
- r = head;
- head = r->next;
- r->next = NULL;
-
- /* walk through new sorted list to find a proper place. */
- for (p = &new_head;
- (l = *p) != NULL &&
- rule_cmp_wildness(l, r) >= 0;
- p = &l->next)
- ;
+ struct rte_acl_build_rule *a;
+ struct rte_acl_build_rule *b;
- /* insert element into the new sorted list. */
- r->next = *p;
- *p = r;
- }
+ /* Base case -- length 0 or 1 */
+ if (head == NULL || head->next == NULL)
+ return head;
+
+ /* Split head into 'a' and 'b' sublists */
+ rule_list_split(head, &a, &b);
- return new_head;
+ /* Recursively sort the sublists */
+ a = sort_rules(a);
+ b = sort_rules(b);
+
+ /* answer = merge the two sorted lists together */
+ return rule_list_sorted_merge(a, b);
}
static uint32_t
static struct rte_acl_build_rule *
build_one_trie(struct acl_build_context *context,
struct rte_acl_build_rule *rule_sets[RTE_ACL_MAX_TRIES],
- uint32_t n)
+ uint32_t n, int32_t node_max)
{
struct rte_acl_build_rule *last;
struct rte_acl_config *config;
context->data_indexes[n]);
context->tries[n].data_index = context->data_indexes[n];
+ context->cur_node_max = node_max;
+
context->bld_tries[n].trie = build_trie(context, rule_sets[n],
&last, &context->tries[n].count);
acl_build_tries(struct acl_build_context *context,
struct rte_acl_build_rule *head)
{
- int32_t rc;
uint32_t n, num_tries;
struct rte_acl_config *config;
struct rte_acl_build_rule *last;
context->tries[0].type = RTE_ACL_FULL_TRIE;
/* calc wildness of each field of each rule */
- rc = acl_calc_wildness(head, config);
- if (rc != 0)
- return rc;
+ acl_calc_wildness(head, config);
for (n = 0;; n = num_tries) {
num_tries = n + 1;
- last = build_one_trie(context, rule_sets, n);
+ last = build_one_trie(context, rule_sets, n, context->node_max);
if (context->bld_tries[n].trie == NULL) {
RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
return -ENOMEM;
head = head->next)
head->config = config;
- /* Rebuild the trie for the reduced rule-set. */
- last = build_one_trie(context, rule_sets, n);
+ /*
+ * Rebuild the trie for the reduced rule-set.
+ * Don't try to split it any further.
+ */
+ last = build_one_trie(context, rule_sets, n, INT32_MAX);
if (context->bld_tries[n].trie == NULL || last != NULL) {
RTE_LOG(ERR, ACL, "Build of %u-th trie failed\n", n);
return -ENOMEM;
bcx->pool.alignment = ACL_POOL_ALIGN;
bcx->pool.min_alloc = ACL_POOL_ALLOC_MIN;
bcx->cfg = *cfg;
- bcx->category_mask = LEN2MASK(bcx->cfg.num_categories);
+ bcx->category_mask = RTE_LEN2MASK(bcx->cfg.num_categories,
+ typeof(bcx->category_mask));
bcx->node_max = node_max;
rc = sigsetjmp(bcx->pool.fail, 0);
return rc;
}
+/*
+ * Check that parameters for acl_build() are valid.
+ */
+static int
+acl_check_bld_param(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
+{
+ static const size_t field_sizes[] = {
+ sizeof(uint8_t), sizeof(uint16_t),
+ sizeof(uint32_t), sizeof(uint64_t),
+ };
+
+ uint32_t i, j;
+
+ if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
+ cfg->num_categories > RTE_ACL_MAX_CATEGORIES ||
+ cfg->num_fields == 0 ||
+ cfg->num_fields > RTE_ACL_MAX_FIELDS)
+ return -EINVAL;
+
+ for (i = 0; i != cfg->num_fields; i++) {
+ if (cfg->defs[i].type > RTE_ACL_FIELD_TYPE_BITMASK) {
+ RTE_LOG(ERR, ACL,
+ "ACL context: %s, invalid type: %hhu for %u-th field\n",
+ ctx->name, cfg->defs[i].type, i);
+ return -EINVAL;
+ }
+ for (j = 0;
+ j != RTE_DIM(field_sizes) &&
+ cfg->defs[i].size != field_sizes[j];
+ j++)
+ ;
+
+ if (j == RTE_DIM(field_sizes)) {
+ RTE_LOG(ERR, ACL,
+ "ACL context: %s, invalid size: %hhu for %u-th field\n",
+ ctx->name, cfg->defs[i].size, i);
+ return -EINVAL;
+ }
+ }
+
+ return 0;
+}
+
int
rte_acl_build(struct rte_acl_ctx *ctx, const struct rte_acl_config *cfg)
{
size_t max_size;
struct acl_build_context bcx;
- if (ctx == NULL || cfg == NULL || cfg->num_categories == 0 ||
- cfg->num_categories > RTE_ACL_MAX_CATEGORIES)
- return -EINVAL;
+ rc = acl_check_bld_param(ctx, cfg);
+ if (rc != 0)
+ return rc;
acl_build_reset(ctx);
git.droids-corp.org / dpdk.git / blobdiff