X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_acl%2Facl_bld.c;h=9e5ad1c63e2a93d184eb8c9665d0b576ed8a5077;hb=693f715da45c48ec1ec0fe4ba2f3b5ffd11ba53e;hp=aee6ed573afc5cc4cc500f9716e743b0502dd9a7;hpb=faea1ce70c77ee5ec95fe7c2fb79265fd5b3dcb1;p=dpdk.git diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c index aee6ed573a..9e5ad1c63e 100644 --- a/lib/librte_acl/acl_bld.c +++ b/lib/librte_acl/acl_bld.c @@ -97,6 +97,7 @@ struct acl_build_context { 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; @@ -119,10 +120,6 @@ static int acl_merge_trie(struct acl_build_context *context, 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); @@ -413,58 +410,6 @@ acl_intersect_type(const struct rte_acl_bitset *a_bits, 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 */ @@ -532,63 +477,6 @@ acl_deref_ptr(struct acl_build_context *context, } } -/* - * 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 */ @@ -649,203 +537,6 @@ acl_compact_node_ptrs(struct rte_acl_node *node_a) } } -/* - * 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, @@ -1261,19 +952,9 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, * 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, @@ -1337,7 +1018,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, 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; } @@ -1350,7 +1031,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, return trie; } -static int +static void acl_calc_wildness(struct rte_acl_build_rule *head, const struct rte_acl_config *config) { @@ -1362,10 +1043,10 @@ acl_calc_wildness(struct rte_acl_build_rule *head, for (n = 0; n < config->num_fields; n++) { double wild = 0; - uint64_t msk_val = - RTE_LEN2MASK(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 = CHAR_BIT * config->defs[n].size; + double size = bit_len; int field_index = config->defs[n].field_index; const struct rte_acl_field *fld = rule->f->field + field_index; @@ -1382,54 +1063,15 @@ acl_calc_wildness(struct rte_acl_build_rule *head, 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 @@ -1515,42 +1157,100 @@ rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2) 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 @@ -1575,7 +1275,7 @@ acl_build_index(const struct rte_acl_config *config, uint32_t *data_index) 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; @@ -1592,6 +1292,8 @@ build_one_trie(struct acl_build_context *context, 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); @@ -1602,7 +1304,6 @@ static int 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; @@ -1621,15 +1322,13 @@ acl_build_tries(struct acl_build_context *context, 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; @@ -1660,8 +1359,11 @@ acl_build_tries(struct acl_build_context *context, 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; @@ -1772,7 +1474,8 @@ acl_bld(struct acl_build_context *bcx, struct rte_acl_ctx *ctx, 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); @@ -1800,6 +1503,49 @@ acl_bld(struct acl_build_context *bcx, struct rte_acl_ctx *ctx, 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) { @@ -1808,9 +1554,9 @@ 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);