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.
40 #define MAX_SEARCHES_AVX16 16
41 #define MAX_SEARCHES_SSE8 8
42 #define MAX_SEARCHES_SSE4 4
43 #define MAX_SEARCHES_SSE2 2
44 #define MAX_SEARCHES_SCALAR 2
46 #define GET_NEXT_4BYTES(prm, idx) \
47 (*((const int32_t *)((prm)[(idx)].data + *(prm)[idx].data_index++)))
50 #define RTE_ACL_NODE_INDEX ((uint32_t)~RTE_ACL_NODE_TYPE)
52 #define SCALAR_QRANGE_MULT 0x01010101
53 #define SCALAR_QRANGE_MASK 0x7f7f7f7f
54 #define SCALAR_QRANGE_MIN 0x80808080
57 * Structure to manage N parallel trie traversals.
58 * The runtime trie traversal routines can process 8, 4, or 2 tries
59 * in parallel. Each packet may require multiple trie traversals (up to 4).
60 * This structure is used to fill the slots (0 to n-1) for parallel processing
61 * with the trie traversals needed for each packet.
63 struct acl_flow_data {
65 /* number of packets processed */
67 /* number of trie traversals in progress */
69 /* current trie index (0 to N-1) */
71 uint32_t total_packets;
73 /* number of result categories per packet. */
74 /* maximum number of packets to process */
75 const uint64_t *trans;
78 struct completion *last_cmplt;
79 struct completion *cmplt_array;
83 * Structure to maintain running results for
84 * a single packet (up to 4 tries).
87 uint32_t *results; /* running results. */
88 int32_t priority[RTE_ACL_MAX_CATEGORIES]; /* running priorities. */
89 uint32_t count; /* num of remaining tries */
90 /* true for allocated struct */
91 } __attribute__((aligned(XMM_SIZE)));
94 * One parms structure for each slot in the search engine.
98 /* input data for this packet */
99 const uint32_t *data_index;
100 /* data indirection for this trie */
101 struct completion *cmplt;
102 /* completion data for this packet */
106 * Define an global idle node for unused engine slots
108 static const uint32_t idle[UINT8_MAX + 1];
111 * Allocate a completion structure to manage the tries for a packet.
113 static inline struct completion *
114 alloc_completion(struct completion *p, uint32_t size, uint32_t tries,
119 for (n = 0; n < size; n++) {
121 if (p[n].count == 0) {
123 /* mark as allocated and set number of tries. */
125 p[n].results = results;
130 /* should never get here */
135 * Resolve priority for a single result trie.
138 resolve_single_priority(uint64_t transition, int n,
139 const struct rte_acl_ctx *ctx, struct parms *parms,
140 const struct rte_acl_match_results *p)
142 if (parms[n].cmplt->count == ctx->num_tries ||
143 parms[n].cmplt->priority[0] <=
144 p[transition].priority[0]) {
146 parms[n].cmplt->priority[0] = p[transition].priority[0];
147 parms[n].cmplt->results[0] = p[transition].results[0];
152 * Routine to fill a slot in the parallel trie traversal array (parms) from
153 * the list of packets (flows).
155 static inline uint64_t
156 acl_start_next_trie(struct acl_flow_data *flows, struct parms *parms, int n,
157 const struct rte_acl_ctx *ctx)
161 /* if there are any more packets to process */
162 if (flows->num_packets < flows->total_packets) {
163 parms[n].data = flows->data[flows->num_packets];
164 parms[n].data_index = ctx->trie[flows->trie].data_index;
166 /* if this is the first trie for this packet */
167 if (flows->trie == 0) {
168 flows->last_cmplt = alloc_completion(flows->cmplt_array,
169 flows->cmplt_size, ctx->num_tries,
171 flows->num_packets * flows->categories);
174 /* set completion parameters and starting index for this slot */
175 parms[n].cmplt = flows->last_cmplt;
177 flows->trans[parms[n].data[*parms[n].data_index++] +
178 ctx->trie[flows->trie].root_index];
181 * if this is the last trie for this packet,
182 * then setup next packet.
185 if (flows->trie >= ctx->num_tries) {
187 flows->num_packets++;
190 /* keep track of number of active trie traversals */
193 /* no more tries to process, set slot to an idle position */
195 transition = ctx->idle;
196 parms[n].data = (const uint8_t *)idle;
197 parms[n].data_index = idle;
203 acl_set_flow(struct acl_flow_data *flows, struct completion *cmplt,
204 uint32_t cmplt_size, const uint8_t **data, uint32_t *results,
205 uint32_t data_num, uint32_t categories, const uint64_t *trans)
207 flows->num_packets = 0;
210 flows->last_cmplt = NULL;
211 flows->cmplt_array = cmplt;
212 flows->total_packets = data_num;
213 flows->categories = categories;
214 flows->cmplt_size = cmplt_size;
216 flows->results = results;
217 flows->trans = trans;
220 typedef void (*resolve_priority_t)
221 (uint64_t transition, int n, const struct rte_acl_ctx *ctx,
222 struct parms *parms, const struct rte_acl_match_results *p,
223 uint32_t categories);
226 * Detect matches. If a match node transition is found, then this trie
227 * traversal is complete and fill the slot with the next trie
230 static inline uint64_t
231 acl_match_check(uint64_t transition, int slot,
232 const struct rte_acl_ctx *ctx, struct parms *parms,
233 struct acl_flow_data *flows, resolve_priority_t resolve_priority)
235 const struct rte_acl_match_results *p;
237 p = (const struct rte_acl_match_results *)
238 (flows->trans + ctx->match_index);
240 if (transition & RTE_ACL_NODE_MATCH) {
242 /* Remove flags from index and decrement active traversals */
243 transition &= RTE_ACL_NODE_INDEX;
246 /* Resolve priorities for this trie and running results */
247 if (flows->categories == 1)
248 resolve_single_priority(transition, slot, ctx,
251 resolve_priority(transition, slot, ctx, parms,
252 p, flows->categories);
254 /* Count down completed tries for this search request */
255 parms[slot].cmplt->count--;
257 /* Fill the slot with the next trie or idle trie */
258 transition = acl_start_next_trie(flows, parms, slot, ctx);
264 #endif /* _ACL_RUN_H_ */