doc: move FAQ
[dpdk.git] / lib / librte_acl / acl_run.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_RUN_H_
35 #define _ACL_RUN_H_
36
37 #include <rte_acl.h>
38 #include "acl.h"
39
40 #define MAX_SEARCHES_AVX16      16
41 #define MAX_SEARCHES_SSE8       8
42 #define MAX_SEARCHES_SSE4       4
43 #define MAX_SEARCHES_SCALAR     2
44
45 #define GET_NEXT_4BYTES(prm, idx)       \
46         (*((const int32_t *)((prm)[(idx)].data + *(prm)[idx].data_index++)))
47
48
49 #define RTE_ACL_NODE_INDEX      ((uint32_t)~RTE_ACL_NODE_TYPE)
50
51 #define SCALAR_QRANGE_MULT      0x01010101
52 #define SCALAR_QRANGE_MASK      0x7f7f7f7f
53 #define SCALAR_QRANGE_MIN       0x80808080
54
55 /*
56  * Structure to manage N parallel trie traversals.
57  * The runtime trie traversal routines can process 8, 4, or 2 tries
58  * in parallel. Each packet may require multiple trie traversals (up to 4).
59  * This structure is used to fill the slots (0 to n-1) for parallel processing
60  * with the trie traversals needed for each packet.
61  */
62 struct acl_flow_data {
63         uint32_t            num_packets;
64         /* number of packets processed */
65         uint32_t            started;
66         /* number of trie traversals in progress */
67         uint32_t            trie;
68         /* current trie index (0 to N-1) */
69         uint32_t            cmplt_size;
70         uint32_t            total_packets;
71         uint32_t            categories;
72         /* number of result categories per packet. */
73         /* maximum number of packets to process */
74         const uint64_t     *trans;
75         const uint8_t     **data;
76         uint32_t           *results;
77         struct completion  *last_cmplt;
78         struct completion  *cmplt_array;
79 };
80
81 /*
82  * Structure to maintain running results for
83  * a single packet (up to 4 tries).
84  */
85 struct completion {
86         uint32_t *results;                          /* running results. */
87         int32_t   priority[RTE_ACL_MAX_CATEGORIES]; /* running priorities. */
88         uint32_t  count;                            /* num of remaining tries */
89         /* true for allocated struct */
90 } __attribute__((aligned(XMM_SIZE)));
91
92 /*
93  * One parms structure for each slot in the search engine.
94  */
95 struct parms {
96         const uint8_t              *data;
97         /* input data for this packet */
98         const uint32_t             *data_index;
99         /* data indirection for this trie */
100         struct completion          *cmplt;
101         /* completion data for this packet */
102 };
103
104 /*
105  * Define an global idle node for unused engine slots
106  */
107 static const uint32_t idle[UINT8_MAX + 1];
108
109 /*
110  * Allocate a completion structure to manage the tries for a packet.
111  */
112 static inline struct completion *
113 alloc_completion(struct completion *p, uint32_t size, uint32_t tries,
114         uint32_t *results)
115 {
116         uint32_t n;
117
118         for (n = 0; n < size; n++) {
119
120                 if (p[n].count == 0) {
121
122                         /* mark as allocated and set number of tries. */
123                         p[n].count = tries;
124                         p[n].results = results;
125                         return &(p[n]);
126                 }
127         }
128
129         /* should never get here */
130         return NULL;
131 }
132
133 /*
134  * Resolve priority for a single result trie.
135  */
136 static inline void
137 resolve_single_priority(uint64_t transition, int n,
138         const struct rte_acl_ctx *ctx, struct parms *parms,
139         const struct rte_acl_match_results *p)
140 {
141         if (parms[n].cmplt->count == ctx->num_tries ||
142                         parms[n].cmplt->priority[0] <=
143                         p[transition].priority[0]) {
144
145                 parms[n].cmplt->priority[0] = p[transition].priority[0];
146                 parms[n].cmplt->results[0] = p[transition].results[0];
147         }
148 }
149
150 /*
151  * Routine to fill a slot in the parallel trie traversal array (parms) from
152  * the list of packets (flows).
153  */
154 static inline uint64_t
155 acl_start_next_trie(struct acl_flow_data *flows, struct parms *parms, int n,
156         const struct rte_acl_ctx *ctx)
157 {
158         uint64_t transition;
159
160         /* if there are any more packets to process */
161         if (flows->num_packets < flows->total_packets) {
162                 parms[n].data = flows->data[flows->num_packets];
163                 parms[n].data_index = ctx->trie[flows->trie].data_index;
164
165                 /* if this is the first trie for this packet */
166                 if (flows->trie == 0) {
167                         flows->last_cmplt = alloc_completion(flows->cmplt_array,
168                                 flows->cmplt_size, ctx->num_tries,
169                                 flows->results +
170                                 flows->num_packets * flows->categories);
171                 }
172
173                 /* set completion parameters and starting index for this slot */
174                 parms[n].cmplt = flows->last_cmplt;
175                 transition =
176                         flows->trans[parms[n].data[*parms[n].data_index++] +
177                         ctx->trie[flows->trie].root_index];
178
179                 /*
180                  * if this is the last trie for this packet,
181                  * then setup next packet.
182                  */
183                 flows->trie++;
184                 if (flows->trie >= ctx->num_tries) {
185                         flows->trie = 0;
186                         flows->num_packets++;
187                 }
188
189                 /* keep track of number of active trie traversals */
190                 flows->started++;
191
192         /* no more tries to process, set slot to an idle position */
193         } else {
194                 transition = ctx->idle;
195                 parms[n].data = (const uint8_t *)idle;
196                 parms[n].data_index = idle;
197         }
198         return transition;
199 }
200
201 static inline void
202 acl_set_flow(struct acl_flow_data *flows, struct completion *cmplt,
203         uint32_t cmplt_size, const uint8_t **data, uint32_t *results,
204         uint32_t data_num, uint32_t categories, const uint64_t *trans)
205 {
206         flows->num_packets = 0;
207         flows->started = 0;
208         flows->trie = 0;
209         flows->last_cmplt = NULL;
210         flows->cmplt_array = cmplt;
211         flows->total_packets = data_num;
212         flows->categories = categories;
213         flows->cmplt_size = cmplt_size;
214         flows->data = data;
215         flows->results = results;
216         flows->trans = trans;
217 }
218
219 typedef void (*resolve_priority_t)
220 (uint64_t transition, int n, const struct rte_acl_ctx *ctx,
221         struct parms *parms, const struct rte_acl_match_results *p,
222         uint32_t categories);
223
224 /*
225  * Detect matches. If a match node transition is found, then this trie
226  * traversal is complete and fill the slot with the next trie
227  * to be processed.
228  */
229 static inline uint64_t
230 acl_match_check(uint64_t transition, int slot,
231         const struct rte_acl_ctx *ctx, struct parms *parms,
232         struct acl_flow_data *flows, resolve_priority_t resolve_priority)
233 {
234         const struct rte_acl_match_results *p;
235
236         p = (const struct rte_acl_match_results *)
237                 (flows->trans + ctx->match_index);
238
239         if (transition & RTE_ACL_NODE_MATCH) {
240
241                 /* Remove flags from index and decrement active traversals */
242                 transition &= RTE_ACL_NODE_INDEX;
243                 flows->started--;
244
245                 /* Resolve priorities for this trie and running results */
246                 if (flows->categories == 1)
247                         resolve_single_priority(transition, slot, ctx,
248                                 parms, p);
249                 else
250                         resolve_priority(transition, slot, ctx, parms,
251                                 p, flows->categories);
252
253                 /* Count down completed tries for this search request */
254                 parms[slot].cmplt->count--;
255
256                 /* Fill the slot with the next trie or idle trie */
257                 transition = acl_start_next_trie(flows, parms, slot, ctx);
258         }
259
260         return transition;
261 }
262
263 #endif /* _ACL_RUN_H_ */