diff options
Diffstat (limited to 'lib/librte_acl/acl.h')
| -rw-r--r-- | lib/librte_acl/acl.h | 241 |
1 files changed, 241 insertions, 0 deletions
diff --git a/lib/librte_acl/acl.h b/lib/librte_acl/acl.h new file mode 100644 index 00000000..09d67841 --- /dev/null +++ b/lib/librte_acl/acl.h @@ -0,0 +1,241 @@ +/*- + * 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. + */ + +#ifndef _ACL_H_ +#define _ACL_H_ + +#ifdef __cplusplus +extern"C" { +#endif /* __cplusplus */ + +#define RTE_ACL_QUAD_MAX 5 +#define RTE_ACL_QUAD_SIZE 4 +#define RTE_ACL_QUAD_SINGLE UINT64_C(0x7f7f7f7f00000000) + +#define RTE_ACL_SINGLE_TRIE_SIZE 2000 + +#define RTE_ACL_DFA_MAX UINT8_MAX +#define RTE_ACL_DFA_SIZE (UINT8_MAX + 1) + +#define RTE_ACL_DFA_GR64_SIZE 64 +#define RTE_ACL_DFA_GR64_NUM (RTE_ACL_DFA_SIZE / RTE_ACL_DFA_GR64_SIZE) +#define RTE_ACL_DFA_GR64_BIT \ + (CHAR_BIT * sizeof(uint32_t) / RTE_ACL_DFA_GR64_NUM) + +typedef int bits_t; + +#define RTE_ACL_BIT_SET_SIZE ((UINT8_MAX + 1) / (sizeof(bits_t) * CHAR_BIT)) + +struct rte_acl_bitset { + bits_t bits[RTE_ACL_BIT_SET_SIZE]; +}; + +#define RTE_ACL_NODE_DFA (0 << RTE_ACL_TYPE_SHIFT) +#define RTE_ACL_NODE_SINGLE (1U << RTE_ACL_TYPE_SHIFT) +#define RTE_ACL_NODE_QRANGE (3U << RTE_ACL_TYPE_SHIFT) +#define RTE_ACL_NODE_MATCH (4U << RTE_ACL_TYPE_SHIFT) +#define RTE_ACL_NODE_TYPE (7U << RTE_ACL_TYPE_SHIFT) +#define RTE_ACL_NODE_UNDEFINED UINT32_MAX + +/* + * ACL RT structure is a set of multibit tries (with stride == 8) + * represented by an array of transitions. The next position is calculated + * based on the current position and the input byte. + * Each transition is 64 bit value with the following format: + * | node_type_specific : 32 | node_type : 3 | node_addr : 29 | + * For all node types except RTE_ACL_NODE_MATCH, node_addr is an index + * to the start of the node in the transtions array. + * Few different node types are used: + * RTE_ACL_NODE_MATCH: + * node_addr value is and index into an array that contains the return value + * and its priority for each category. + * Upper 32 bits of the transition value are not used for that node type. + * RTE_ACL_NODE_QRANGE: + * that node consist of up to 5 transitions. + * Upper 32 bits are interpreted as 4 signed character values which + * are ordered from smallest(INT8_MIN) to largest (INT8_MAX). + * These values define 5 ranges: + * INT8_MIN <= range[0] <= ((int8_t *)&transition)[4] + * ((int8_t *)&transition)[4] < range[1] <= ((int8_t *)&transition)[5] + * ((int8_t *)&transition)[5] < range[2] <= ((int8_t *)&transition)[6] + * ((int8_t *)&transition)[6] < range[3] <= ((int8_t *)&transition)[7] + * ((int8_t *)&transition)[7] < range[4] <= INT8_MAX + * So for input byte value within range[i] i-th transition within that node + * will be used. + * RTE_ACL_NODE_SINGLE: + * always transitions to the same node regardless of the input value. + * RTE_ACL_NODE_DFA: + * that node consits of up to 256 transitions. + * In attempt to conserve space all transitions are divided into 4 consecutive + * groups, by 64 transitions per group: + * group64[i] contains transitions[i * 64, .. i * 64 + 63]. + * Upper 32 bits are interpreted as 4 unsigned character values one per group, + * which contain index to the start of the given group within the node. + * So to calculate transition index within the node for given input byte value: + * input_byte - ((uint8_t *)&transition)[4 + input_byte / 64]. + */ + +/* + * Structure of a node is a set of ptrs and each ptr has a bit map + * of values associated with this transition. + */ +struct rte_acl_ptr_set { + struct rte_acl_bitset values; /* input values associated with ptr */ + struct rte_acl_node *ptr; /* transition to next node */ +}; + +struct rte_acl_classifier_results { + int results[RTE_ACL_MAX_CATEGORIES]; +}; + +struct rte_acl_match_results { + uint32_t results[RTE_ACL_MAX_CATEGORIES]; + int32_t priority[RTE_ACL_MAX_CATEGORIES]; +}; + +struct rte_acl_node { + uint64_t node_index; /* index for this node */ + uint32_t level; /* level 0-n in the trie */ + uint32_t ref_count; /* ref count for this node */ + struct rte_acl_bitset values; + /* set of all values that map to another node + * (union of bits in each transition. + */ + uint32_t num_ptrs; /* number of ptr_set in use */ + uint32_t max_ptrs; /* number of allocated ptr_set */ + uint32_t min_add; /* number of ptr_set per allocation */ + struct rte_acl_ptr_set *ptrs; /* transitions array for this node */ + int32_t match_flag; + int32_t match_index; /* index to match data */ + uint32_t node_type; + int32_t fanout; + /* number of ranges (transitions w/ consecutive bits) */ + int32_t id; + struct rte_acl_match_results *mrt; /* only valid when match_flag != 0 */ + union { + char transitions[RTE_ACL_QUAD_SIZE]; + /* boundaries for ranged node */ + uint8_t dfa_gr64[RTE_ACL_DFA_GR64_NUM]; + }; + struct rte_acl_node *next; + /* free list link or pointer to duplicate node during merge */ + struct rte_acl_node *prev; + /* points to node from which this node was duplicated */ +}; + +/* + * Types of tries used to generate runtime structure(s) + */ +enum { + RTE_ACL_FULL_TRIE = 0, + RTE_ACL_NOSRC_TRIE = 1, + RTE_ACL_NODST_TRIE = 2, + RTE_ACL_NOPORTS_TRIE = 4, + RTE_ACL_NOVLAN_TRIE = 8, + RTE_ACL_UNUSED_TRIE = 0x80000000 +}; + + +/** MAX number of tries per one ACL context.*/ +#define RTE_ACL_MAX_TRIES 8 + +/** Max number of characters in PM name.*/ +#define RTE_ACL_NAMESIZE 32 + + +struct rte_acl_trie { + uint32_t type; + uint32_t count; + uint32_t root_index; + const uint32_t *data_index; + uint32_t num_data_indexes; +}; + +struct rte_acl_bld_trie { + struct rte_acl_node *trie; +}; + +struct rte_acl_ctx { + char name[RTE_ACL_NAMESIZE]; + /** Name of the ACL context. */ + int32_t socket_id; + /** Socket ID to allocate memory from. */ + enum rte_acl_classify_alg alg; + void *rules; + uint32_t max_rules; + uint32_t rule_sz; + uint32_t num_rules; + uint32_t num_categories; + uint32_t num_tries; + uint32_t match_index; + uint64_t no_match; + uint64_t idle; + uint64_t *trans_table; + uint32_t *data_indexes; + struct rte_acl_trie trie[RTE_ACL_MAX_TRIES]; + void *mem; + size_t mem_sz; + struct rte_acl_config config; /* copy of build config. */ +}; + +int rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie, + struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries, + uint32_t num_categories, uint32_t data_index_sz, size_t max_size); + +typedef int (*rte_acl_classify_t) +(const struct rte_acl_ctx *, const uint8_t **, uint32_t *, uint32_t, uint32_t); + +/* + * Different implementations of ACL classify. + */ +int +rte_acl_classify_scalar(const struct rte_acl_ctx *ctx, const uint8_t **data, + uint32_t *results, uint32_t num, uint32_t categories); + +int +rte_acl_classify_sse(const struct rte_acl_ctx *ctx, const uint8_t **data, + uint32_t *results, uint32_t num, uint32_t categories); + +int +rte_acl_classify_avx2(const struct rte_acl_ctx *ctx, const uint8_t **data, + uint32_t *results, uint32_t num, uint32_t categories); + +int +rte_acl_classify_neon(const struct rte_acl_ctx *ctx, const uint8_t **data, + uint32_t *results, uint32_t num, uint32_t categories); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* _ACL_H_ */ |