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_ALTIVEC8 8
43 #define MAX_SEARCHES_SSE4 4
44 #define MAX_SEARCHES_ALTIVEC4 4
45 #define MAX_SEARCHES_SCALAR 2
47 #define GET_NEXT_4BYTES(prm, idx) \
48 (*((const int32_t *)((prm)[(idx)].data + *(prm)[idx].data_index++)))
51 #define RTE_ACL_NODE_INDEX ((uint32_t)~RTE_ACL_NODE_TYPE)
53 #define SCALAR_QRANGE_MULT 0x01010101
54 #define SCALAR_QRANGE_MASK 0x7f7f7f7f
55 #define SCALAR_QRANGE_MIN 0x80808080
58 * Structure to manage N parallel trie traversals.
59 * The runtime trie traversal routines can process 8, 4, or 2 tries
60 * in parallel. Each packet may require multiple trie traversals (up to 4).
61 * This structure is used to fill the slots (0 to n-1) for parallel processing
62 * with the trie traversals needed for each packet.
64 struct acl_flow_data
{
66 /* number of packets processed */
68 /* number of trie traversals in progress */
70 /* current trie index (0 to N-1) */
72 uint32_t total_packets
;
74 /* number of result categories per packet. */
75 /* maximum number of packets to process */
76 const uint64_t *trans
;
79 struct completion
*last_cmplt
;
80 struct completion
*cmplt_array
;
84 * Structure to maintain running results for
85 * a single packet (up to 4 tries).
88 uint32_t *results
; /* running results. */
89 int32_t priority
[RTE_ACL_MAX_CATEGORIES
]; /* running priorities. */
90 uint32_t count
; /* num of remaining tries */
91 /* true for allocated struct */
92 } __attribute__((aligned(XMM_SIZE
)));
95 * One parms structure for each slot in the search engine.
99 /* input data for this packet */
100 const uint32_t *data_index
;
101 /* data indirection for this trie */
102 struct completion
*cmplt
;
103 /* completion data for this packet */
107 * Define an global idle node for unused engine slots
109 static const uint32_t idle
[UINT8_MAX
+ 1];
112 * Allocate a completion structure to manage the tries for a packet.
114 static inline struct completion
*
115 alloc_completion(struct completion
*p
, uint32_t size
, uint32_t tries
,
120 for (n
= 0; n
< size
; n
++) {
122 if (p
[n
].count
== 0) {
124 /* mark as allocated and set number of tries. */
126 p
[n
].results
= results
;
131 /* should never get here */
136 * Resolve priority for a single result trie.
139 resolve_single_priority(uint64_t transition
, int n
,
140 const struct rte_acl_ctx
*ctx
, struct parms
*parms
,
141 const struct rte_acl_match_results
*p
)
143 if (parms
[n
].cmplt
->count
== ctx
->num_tries
||
144 parms
[n
].cmplt
->priority
[0] <=
145 p
[transition
].priority
[0]) {
147 parms
[n
].cmplt
->priority
[0] = p
[transition
].priority
[0];
148 parms
[n
].cmplt
->results
[0] = p
[transition
].results
[0];
153 * Routine to fill a slot in the parallel trie traversal array (parms) from
154 * the list of packets (flows).
156 static inline uint64_t
157 acl_start_next_trie(struct acl_flow_data
*flows
, struct parms
*parms
, int n
,
158 const struct rte_acl_ctx
*ctx
)
162 /* if there are any more packets to process */
163 if (flows
->num_packets
< flows
->total_packets
) {
164 parms
[n
].data
= flows
->data
[flows
->num_packets
];
165 parms
[n
].data_index
= ctx
->trie
[flows
->trie
].data_index
;
167 /* if this is the first trie for this packet */
168 if (flows
->trie
== 0) {
169 flows
->last_cmplt
= alloc_completion(flows
->cmplt_array
,
170 flows
->cmplt_size
, ctx
->num_tries
,
172 flows
->num_packets
* flows
->categories
);
175 /* set completion parameters and starting index for this slot */
176 parms
[n
].cmplt
= flows
->last_cmplt
;
178 flows
->trans
[parms
[n
].data
[*parms
[n
].data_index
++] +
179 ctx
->trie
[flows
->trie
].root_index
];
182 * if this is the last trie for this packet,
183 * then setup next packet.
186 if (flows
->trie
>= ctx
->num_tries
) {
188 flows
->num_packets
++;
191 /* keep track of number of active trie traversals */
194 /* no more tries to process, set slot to an idle position */
196 transition
= ctx
->idle
;
197 parms
[n
].data
= (const uint8_t *)idle
;
198 parms
[n
].data_index
= idle
;
204 acl_set_flow(struct acl_flow_data
*flows
, struct completion
*cmplt
,
205 uint32_t cmplt_size
, const uint8_t **data
, uint32_t *results
,
206 uint32_t data_num
, uint32_t categories
, const uint64_t *trans
)
208 flows
->num_packets
= 0;
211 flows
->last_cmplt
= NULL
;
212 flows
->cmplt_array
= cmplt
;
213 flows
->total_packets
= data_num
;
214 flows
->categories
= categories
;
215 flows
->cmplt_size
= cmplt_size
;
217 flows
->results
= results
;
218 flows
->trans
= trans
;
221 typedef void (*resolve_priority_t
)
222 (uint64_t transition
, int n
, const struct rte_acl_ctx
*ctx
,
223 struct parms
*parms
, const struct rte_acl_match_results
*p
,
224 uint32_t categories
);
227 * Detect matches. If a match node transition is found, then this trie
228 * traversal is complete and fill the slot with the next trie
231 static inline uint64_t
232 acl_match_check(uint64_t transition
, int slot
,
233 const struct rte_acl_ctx
*ctx
, struct parms
*parms
,
234 struct acl_flow_data
*flows
, resolve_priority_t resolve_priority
)
236 const struct rte_acl_match_results
*p
;
238 p
= (const struct rte_acl_match_results
*)
239 (flows
->trans
+ ctx
->match_index
);
241 if (transition
& RTE_ACL_NODE_MATCH
) {
243 /* Remove flags from index and decrement active traversals */
244 transition
&= RTE_ACL_NODE_INDEX
;
247 /* Resolve priorities for this trie and running results */
248 if (flows
->categories
== 1)
249 resolve_single_priority(transition
, slot
, ctx
,
252 resolve_priority(transition
, slot
, ctx
, parms
,
253 p
, flows
->categories
);
255 /* Count down completed tries for this search request */
256 parms
[slot
].cmplt
->count
--;
258 /* Fill the slot with the next trie or idle trie */
259 transition
= acl_start_next_trie(flows
, parms
, slot
, ctx
);
265 #endif /* _ACL_RUN_H_ */