doc: move FAQ
[dpdk.git] / lib / librte_acl / acl.h
1 /*-
2  *   BSD LICENSE
3  *
4  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5  *   All rights reserved.
6  *
7  *   Redistribution and use in source and binary forms, with or without
8  *   modification, are permitted provided that the following conditions
9  *   are met:
10  *
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
16  *       distribution.
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.
20  *
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.
32  */
33
34 #ifndef _ACL_H_
35 #define _ACL_H_
36
37 #ifdef __cplusplus
38 extern"C" {
39 #endif /* __cplusplus */
40
41 #define RTE_ACL_QUAD_MAX        5
42 #define RTE_ACL_QUAD_SIZE       4
43 #define RTE_ACL_QUAD_SINGLE     UINT64_C(0x7f7f7f7f00000000)
44
45 #define RTE_ACL_SINGLE_TRIE_SIZE        2000
46
47 #define RTE_ACL_DFA_MAX         UINT8_MAX
48 #define RTE_ACL_DFA_SIZE        (UINT8_MAX + 1)
49
50 #define RTE_ACL_DFA_GR64_SIZE   64
51 #define RTE_ACL_DFA_GR64_NUM    (RTE_ACL_DFA_SIZE / RTE_ACL_DFA_GR64_SIZE)
52 #define RTE_ACL_DFA_GR64_BIT    \
53         (CHAR_BIT * sizeof(uint32_t) / RTE_ACL_DFA_GR64_NUM)
54
55 typedef int bits_t;
56
57 #define RTE_ACL_BIT_SET_SIZE    ((UINT8_MAX + 1) / (sizeof(bits_t) * CHAR_BIT))
58
59 struct rte_acl_bitset {
60         bits_t             bits[RTE_ACL_BIT_SET_SIZE];
61 };
62
63 #define RTE_ACL_NODE_DFA        (0 << RTE_ACL_TYPE_SHIFT)
64 #define RTE_ACL_NODE_SINGLE     (1U << RTE_ACL_TYPE_SHIFT)
65 #define RTE_ACL_NODE_QRANGE     (3U << RTE_ACL_TYPE_SHIFT)
66 #define RTE_ACL_NODE_MATCH      (4U << RTE_ACL_TYPE_SHIFT)
67 #define RTE_ACL_NODE_TYPE       (7U << RTE_ACL_TYPE_SHIFT)
68 #define RTE_ACL_NODE_UNDEFINED  UINT32_MAX
69
70 /*
71  * ACL RT structure is a set of multibit tries (with stride == 8)
72  * represented by an array of transitions. The next position is calculated
73  * based on the current position and the input byte.
74  * Each transition is 64 bit value with the following format:
75  * | node_type_specific : 32 | node_type : 3 | node_addr : 29 |
76  * For all node types except RTE_ACL_NODE_MATCH, node_addr is an index
77  * to the start of the node in the transtions array.
78  * Few different node types are used:
79  * RTE_ACL_NODE_MATCH:
80  * node_addr value is and index into an array that contains the return value
81  * and its priority for each category.
82  * Upper 32 bits of the transition value are not used for that node type.
83  * RTE_ACL_NODE_QRANGE:
84  * that node consist of up to 5 transitions.
85  * Upper 32 bits are interpreted as 4 signed character values which
86  * are ordered from smallest(INT8_MIN) to largest (INT8_MAX).
87  * These values define 5 ranges:
88  * INT8_MIN <= range[0]  <= ((int8_t *)&transition)[4]
89  * ((int8_t *)&transition)[4] < range[1] <= ((int8_t *)&transition)[5]
90  * ((int8_t *)&transition)[5] < range[2] <= ((int8_t *)&transition)[6]
91  * ((int8_t *)&transition)[6] < range[3] <= ((int8_t *)&transition)[7]
92  * ((int8_t *)&transition)[7] < range[4] <= INT8_MAX
93  * So for input byte value within range[i] i-th transition within that node
94  * will be used.
95  * RTE_ACL_NODE_SINGLE:
96  * always transitions to the same node regardless of the input value.
97  * RTE_ACL_NODE_DFA:
98  * that node consits of up to 256 transitions.
99  * In attempt to conserve space all transitions are divided into 4 consecutive
100  * groups, by 64 transitions per group:
101  * group64[i] contains transitions[i * 64, .. i * 64 + 63].
102  * Upper 32 bits are interpreted as 4 unsigned character values one per group,
103  * which contain index to the start of the given group within the node.
104  * So to calculate transition index within the node for given input byte value:
105  * input_byte - ((uint8_t *)&transition)[4 + input_byte / 64].
106  */
107
108 /*
109  * Structure of a node is a set of ptrs and each ptr has a bit map
110  * of values associated with this transition.
111  */
112 struct rte_acl_ptr_set {
113         struct rte_acl_bitset values;   /* input values associated with ptr */
114         struct rte_acl_node  *ptr;      /* transition to next node */
115 };
116
117 struct rte_acl_classifier_results {
118         int results[RTE_ACL_MAX_CATEGORIES];
119 };
120
121 struct rte_acl_match_results {
122         uint32_t results[RTE_ACL_MAX_CATEGORIES];
123         int32_t priority[RTE_ACL_MAX_CATEGORIES];
124 };
125
126 struct rte_acl_node {
127         uint64_t node_index;  /* index for this node */
128         uint32_t level;       /* level 0-n in the trie */
129         uint32_t ref_count;   /* ref count for this node */
130         struct rte_acl_bitset  values;
131         /* set of all values that map to another node
132          * (union of bits in each transition.
133          */
134         uint32_t                num_ptrs; /* number of ptr_set in use */
135         uint32_t                max_ptrs; /* number of allocated ptr_set */
136         uint32_t                min_add;  /* number of ptr_set per allocation */
137         struct rte_acl_ptr_set *ptrs;     /* transitions array for this node */
138         int32_t                 match_flag;
139         int32_t                 match_index; /* index to match data */
140         uint32_t                node_type;
141         int32_t                 fanout;
142         /* number of ranges (transitions w/ consecutive bits) */
143         int32_t                 id;
144         struct rte_acl_match_results *mrt; /* only valid when match_flag != 0 */
145         union {
146                 char            transitions[RTE_ACL_QUAD_SIZE];
147                 /* boundaries for ranged node */
148                 uint8_t         dfa_gr64[RTE_ACL_DFA_GR64_NUM];
149         };
150         struct rte_acl_node     *next;
151         /* free list link or pointer to duplicate node during merge */
152         struct rte_acl_node     *prev;
153         /* points to node from which this node was duplicated */
154 };
155
156 /*
157  * Types of tries used to generate runtime structure(s)
158  */
159 enum {
160         RTE_ACL_FULL_TRIE = 0,
161         RTE_ACL_NOSRC_TRIE = 1,
162         RTE_ACL_NODST_TRIE = 2,
163         RTE_ACL_NOPORTS_TRIE = 4,
164         RTE_ACL_NOVLAN_TRIE = 8,
165         RTE_ACL_UNUSED_TRIE = 0x80000000
166 };
167
168
169 /** MAX number of tries per one ACL context.*/
170 #define RTE_ACL_MAX_TRIES       8
171
172 /** Max number of characters in PM name.*/
173 #define RTE_ACL_NAMESIZE        32
174
175
176 struct rte_acl_trie {
177         uint32_t        type;
178         uint32_t        count;
179         uint32_t        root_index;
180         const uint32_t *data_index;
181         uint32_t        num_data_indexes;
182 };
183
184 struct rte_acl_bld_trie {
185         struct rte_acl_node *trie;
186 };
187
188 struct rte_acl_ctx {
189         char                name[RTE_ACL_NAMESIZE];
190         /** Name of the ACL context. */
191         int32_t             socket_id;
192         /** Socket ID to allocate memory from. */
193         enum rte_acl_classify_alg alg;
194         void               *rules;
195         uint32_t            max_rules;
196         uint32_t            rule_sz;
197         uint32_t            num_rules;
198         uint32_t            num_categories;
199         uint32_t            num_tries;
200         uint32_t            match_index;
201         uint64_t            no_match;
202         uint64_t            idle;
203         uint64_t           *trans_table;
204         uint32_t           *data_indexes;
205         struct rte_acl_trie trie[RTE_ACL_MAX_TRIES];
206         void               *mem;
207         size_t              mem_sz;
208         struct rte_acl_config config; /* copy of build config. */
209 };
210
211 int rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie,
212         struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
213         uint32_t num_categories, uint32_t data_index_sz, size_t max_size);
214
215 typedef int (*rte_acl_classify_t)
216 (const struct rte_acl_ctx *, const uint8_t **, uint32_t *, uint32_t, uint32_t);
217
218 /*
219  * Different implementations of ACL classify.
220  */
221 int
222 rte_acl_classify_scalar(const struct rte_acl_ctx *ctx, const uint8_t **data,
223         uint32_t *results, uint32_t num, uint32_t categories);
224
225 int
226 rte_acl_classify_sse(const struct rte_acl_ctx *ctx, const uint8_t **data,
227         uint32_t *results, uint32_t num, uint32_t categories);
228
229 int
230 rte_acl_classify_avx2(const struct rte_acl_ctx *ctx, const uint8_t **data,
231         uint32_t *results, uint32_t num, uint32_t categories);
232
233 #ifdef __cplusplus
234 }
235 #endif /* __cplusplus */
236
237 #endif /* _ACL_H_ */