4 * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 #endif /* __cplusplus */
41 #define RTE_ACL_QUAD_MAX 5
42 #define RTE_ACL_QUAD_SIZE 4
43 #define RTE_ACL_QUAD_SINGLE UINT64_C(0x7f7f7f7f00000000)
45 #define RTE_ACL_SINGLE_TRIE_SIZE 2000
47 #define RTE_ACL_DFA_MAX UINT8_MAX
48 #define RTE_ACL_DFA_SIZE (UINT8_MAX + 1)
52 #define RTE_ACL_BIT_SET_SIZE ((UINT8_MAX + 1) / (sizeof(bits_t) * CHAR_BIT))
54 struct rte_acl_bitset {
55 bits_t bits[RTE_ACL_BIT_SET_SIZE];
58 #define RTE_ACL_NODE_DFA (0 << RTE_ACL_TYPE_SHIFT)
59 #define RTE_ACL_NODE_SINGLE (1U << RTE_ACL_TYPE_SHIFT)
60 #define RTE_ACL_NODE_QEXACT (2U << RTE_ACL_TYPE_SHIFT)
61 #define RTE_ACL_NODE_QRANGE (3U << RTE_ACL_TYPE_SHIFT)
62 #define RTE_ACL_NODE_MATCH (4U << RTE_ACL_TYPE_SHIFT)
63 #define RTE_ACL_NODE_TYPE (7U << RTE_ACL_TYPE_SHIFT)
64 #define RTE_ACL_NODE_UNDEFINED UINT32_MAX
67 * Structure of a node is a set of ptrs and each ptr has a bit map
68 * of values associated with this transition.
70 struct rte_acl_ptr_set {
71 struct rte_acl_bitset values; /* input values associated with ptr */
72 struct rte_acl_node *ptr; /* transition to next node */
75 struct rte_acl_classifier_results {
76 int results[RTE_ACL_MAX_CATEGORIES];
79 struct rte_acl_match_results {
80 uint32_t results[RTE_ACL_MAX_CATEGORIES];
81 int32_t priority[RTE_ACL_MAX_CATEGORIES];
85 uint64_t node_index; /* index for this node */
86 uint32_t level; /* level 0-n in the trie */
87 uint32_t ref_count; /* ref count for this node */
88 struct rte_acl_bitset values;
89 /* set of all values that map to another node
90 * (union of bits in each transition.
92 uint32_t num_ptrs; /* number of ptr_set in use */
93 uint32_t max_ptrs; /* number of allocated ptr_set */
94 uint32_t min_add; /* number of ptr_set per allocation */
95 struct rte_acl_ptr_set *ptrs; /* transitions array for this node */
97 int32_t match_index; /* index to match data */
100 /* number of ranges (transitions w/ consecutive bits) */
102 struct rte_acl_match_results *mrt; /* only valid when match_flag != 0 */
103 char transitions[RTE_ACL_QUAD_SIZE];
104 /* boundaries for ranged node */
105 struct rte_acl_node *next;
106 /* free list link or pointer to duplicate node during merge */
107 struct rte_acl_node *prev;
108 /* points to node from which this node was duplicated */
111 uint32_t subtree_ref_count;
115 RTE_ACL_SUBTREE_NODE = 0x80000000
119 * Types of tries used to generate runtime structure(s)
122 RTE_ACL_FULL_TRIE = 0,
123 RTE_ACL_NOSRC_TRIE = 1,
124 RTE_ACL_NODST_TRIE = 2,
125 RTE_ACL_NOPORTS_TRIE = 4,
126 RTE_ACL_NOVLAN_TRIE = 8,
127 RTE_ACL_UNUSED_TRIE = 0x80000000
131 /** MAX number of tries per one ACL context.*/
132 #define RTE_ACL_MAX_TRIES 8
134 /** Max number of characters in PM name.*/
135 #define RTE_ACL_NAMESIZE 32
138 struct rte_acl_trie {
141 int32_t smallest; /* smallest rule in this trie */
143 const uint32_t *data_index;
144 uint32_t num_data_indexes;
147 struct rte_acl_bld_trie {
148 struct rte_acl_node *trie;
152 char name[RTE_ACL_NAMESIZE];
153 /** Name of the ACL context. */
155 /** Socket ID to allocate memory from. */
156 enum rte_acl_classify_alg alg;
161 uint32_t num_categories;
163 uint32_t match_index;
166 uint64_t *trans_table;
167 uint32_t *data_indexes;
168 struct rte_acl_trie trie[RTE_ACL_MAX_TRIES];
171 struct rte_acl_config config; /* copy of build config. */
174 int rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie,
175 struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
176 uint32_t num_categories, uint32_t data_index_sz, int match_num);
178 typedef int (*rte_acl_classify_t)
179 (const struct rte_acl_ctx *, const uint8_t **, uint32_t *, uint32_t, uint32_t);
182 * Different implementations of ACL classify.
185 rte_acl_classify_scalar(const struct rte_acl_ctx *ctx, const uint8_t **data,
186 uint32_t *results, uint32_t num, uint32_t categories);
189 rte_acl_classify_sse(const struct rte_acl_ctx *ctx, const uint8_t **data,
190 uint32_t *results, uint32_t num, uint32_t categories);
194 #endif /* __cplusplus */