1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
3 */
4
5 #include "acl_run.h"
6 #include "acl_vect.h"
7
8 enum {
9 SHUFFLE32_SLOT1 = 0xe5,
10 SHUFFLE32_SLOT2 = 0xe6,
11 SHUFFLE32_SLOT3 = 0xe7,
12 SHUFFLE32_SWAP64 = 0x4e,
13 };
14
15 static const rte_xmm_t xmm_shuffle_input = {
16 .u32 = {0x00000000, 0x04040404, 0x08080808, 0x0c0c0c0c},
17 };
18
19 static const rte_xmm_t xmm_ones_16 = {
20 .u16 = {1, 1, 1, 1, 1, 1, 1, 1},
21 };
22
23 static const rte_xmm_t xmm_match_mask = {
24 .u32 = {
25 RTE_ACL_NODE_MATCH,
26 RTE_ACL_NODE_MATCH,
27 RTE_ACL_NODE_MATCH,
28 RTE_ACL_NODE_MATCH,
29 },
30 };
31
32 static const rte_xmm_t xmm_index_mask = {
33 .u32 = {
34 RTE_ACL_NODE_INDEX,
35 RTE_ACL_NODE_INDEX,
36 RTE_ACL_NODE_INDEX,
37 RTE_ACL_NODE_INDEX,
38 },
39 };
40
41 static const rte_xmm_t xmm_range_base = {
42 .u32 = {
43 0xffffff00, 0xffffff04, 0xffffff08, 0xffffff0c,
44 },
45 };
46
47 /*
48 * Resolve priority for multiple results (sse version).
49 * This consists comparing the priority of the current traversal with the
50 * running set of results for the packet.
51 * For each result, keep a running array of the result (rule number) and
52 * its priority for each category.
53 */
54 static inline void
resolve_priority_sse(uint64_t transition,int n,const struct rte_acl_ctx * ctx,struct parms * parms,const struct rte_acl_match_results * p,uint32_t categories)55 resolve_priority_sse(uint64_t transition, int n, const struct rte_acl_ctx *ctx,
56 struct parms *parms, const struct rte_acl_match_results *p,
57 uint32_t categories)
58 {
59 uint32_t x;
60 xmm_t results, priority, results1, priority1, selector;
61 xmm_t *saved_results, *saved_priority;
62
63 for (x = 0; x < categories; x += RTE_ACL_RESULTS_MULTIPLIER) {
64
65 saved_results = (xmm_t *)(&parms[n].cmplt->results[x]);
66 saved_priority =
67 (xmm_t *)(&parms[n].cmplt->priority[x]);
68
69 /* get results and priorities for completed trie */
70 results = _mm_loadu_si128(
71 (const xmm_t *)&p[transition].results[x]);
72 priority = _mm_loadu_si128(
73 (const xmm_t *)&p[transition].priority[x]);
74
75 /* if this is not the first completed trie */
76 if (parms[n].cmplt->count != ctx->num_tries) {
77
78 /* get running best results and their priorities */
79 results1 = _mm_loadu_si128(saved_results);
80 priority1 = _mm_loadu_si128(saved_priority);
81
82 /* select results that are highest priority */
83 selector = _mm_cmpgt_epi32(priority1, priority);
84 results = _mm_blendv_epi8(results, results1, selector);
85 priority = _mm_blendv_epi8(priority, priority1,
86 selector);
87 }
88
89 /* save running best results and their priorities */
90 _mm_storeu_si128(saved_results, results);
91 _mm_storeu_si128(saved_priority, priority);
92 }
93 }
94
95 /*
96 * Extract transitions from an XMM register and check for any matches
97 */
98 static void
acl_process_matches(xmm_t * indices,int slot,const struct rte_acl_ctx * ctx,struct parms * parms,struct acl_flow_data * flows)99 acl_process_matches(xmm_t *indices, int slot, const struct rte_acl_ctx *ctx,
100 struct parms *parms, struct acl_flow_data *flows)
101 {
102 uint64_t transition1, transition2;
103
104 /* extract transition from low 64 bits. */
105 transition1 = _mm_cvtsi128_si64(*indices);
106
107 /* extract transition from high 64 bits. */
108 *indices = _mm_shuffle_epi32(*indices, SHUFFLE32_SWAP64);
109 transition2 = _mm_cvtsi128_si64(*indices);
110
111 transition1 = acl_match_check(transition1, slot, ctx,
112 parms, flows, resolve_priority_sse);
113 transition2 = acl_match_check(transition2, slot + 1, ctx,
114 parms, flows, resolve_priority_sse);
115
116 /* update indices with new transitions. */
117 *indices = _mm_set_epi64x(transition2, transition1);
118 }
119
120 /*
121 * Check for any match in 4 transitions (contained in 2 SSE registers)
122 */
123 static __rte_always_inline void
acl_match_check_x4(int slot,const struct rte_acl_ctx * ctx,struct parms * parms,struct acl_flow_data * flows,xmm_t * indices1,xmm_t * indices2,xmm_t match_mask)124 acl_match_check_x4(int slot, const struct rte_acl_ctx *ctx, struct parms *parms,
125 struct acl_flow_data *flows, xmm_t *indices1, xmm_t *indices2,
126 xmm_t match_mask)
127 {
128 xmm_t temp;
129
130 /* put low 32 bits of each transition into one register */
131 temp = (xmm_t)_mm_shuffle_ps((__m128)*indices1, (__m128)*indices2,
132 0x88);
133 /* test for match node */
134 temp = _mm_and_si128(match_mask, temp);
135
136 while (!_mm_testz_si128(temp, temp)) {
137 acl_process_matches(indices1, slot, ctx, parms, flows);
138 acl_process_matches(indices2, slot + 2, ctx, parms, flows);
139
140 temp = (xmm_t)_mm_shuffle_ps((__m128)*indices1,
141 (__m128)*indices2,
142 0x88);
143 temp = _mm_and_si128(match_mask, temp);
144 }
145 }
146
147 /*
148 * Process 4 transitions (in 2 XMM registers) in parallel
149 */
150 static __rte_always_inline xmm_t
transition4(xmm_t next_input,const uint64_t * trans,xmm_t * indices1,xmm_t * indices2)151 transition4(xmm_t next_input, const uint64_t *trans,
152 xmm_t *indices1, xmm_t *indices2)
153 {
154 xmm_t addr, tr_lo, tr_hi;
155 uint64_t trans0, trans2;
156
157 /* Shuffle low 32 into tr_lo and high 32 into tr_hi */
158 ACL_TR_HILO(mm, __m128, *indices1, *indices2, tr_lo, tr_hi);
159
160 /* Calculate the address (array index) for all 4 transitions. */
161 ACL_TR_CALC_ADDR(mm, 128, addr, xmm_index_mask.x, next_input,
162 xmm_shuffle_input.x, xmm_ones_16.x, xmm_range_base.x,
163 tr_lo, tr_hi);
164
165 /* Gather 64 bit transitions and pack back into 2 registers. */
166
167 trans0 = trans[_mm_cvtsi128_si32(addr)];
168
169 /* get slot 2 */
170
171 /* {x0, x1, x2, x3} -> {x2, x1, x2, x3} */
172 addr = _mm_shuffle_epi32(addr, SHUFFLE32_SLOT2);
173 trans2 = trans[_mm_cvtsi128_si32(addr)];
174
175 /* get slot 1 */
176
177 /* {x2, x1, x2, x3} -> {x1, x1, x2, x3} */
178 addr = _mm_shuffle_epi32(addr, SHUFFLE32_SLOT1);
179 *indices1 = _mm_set_epi64x(trans[_mm_cvtsi128_si32(addr)], trans0);
180
181 /* get slot 3 */
182
183 /* {x1, x1, x2, x3} -> {x3, x1, x2, x3} */
184 addr = _mm_shuffle_epi32(addr, SHUFFLE32_SLOT3);
185 *indices2 = _mm_set_epi64x(trans[_mm_cvtsi128_si32(addr)], trans2);
186
187 return _mm_srli_epi32(next_input, CHAR_BIT);
188 }
189
190 /*
191 * Execute trie traversal with 8 traversals in parallel
192 */
193 static inline int
search_sse_8(const struct rte_acl_ctx * ctx,const uint8_t ** data,uint32_t * results,uint32_t total_packets,uint32_t categories)194 search_sse_8(const struct rte_acl_ctx *ctx, const uint8_t **data,
195 uint32_t *results, uint32_t total_packets, uint32_t categories)
196 {
197 int n;
198 struct acl_flow_data flows;
199 uint64_t index_array[MAX_SEARCHES_SSE8];
200 struct completion cmplt[MAX_SEARCHES_SSE8];
201 struct parms parms[MAX_SEARCHES_SSE8];
202 xmm_t input0, input1;
203 xmm_t indices1, indices2, indices3, indices4;
204
205 acl_set_flow(&flows, cmplt, RTE_DIM(cmplt), data, results,
206 total_packets, categories, ctx->trans_table);
207
208 for (n = 0; n < MAX_SEARCHES_SSE8; n++) {
209 cmplt[n].count = 0;
210 index_array[n] = acl_start_next_trie(&flows, parms, n, ctx);
211 }
212
213 /*
214 * indices1 contains index_array[0,1]
215 * indices2 contains index_array[2,3]
216 * indices3 contains index_array[4,5]
217 * indices4 contains index_array[6,7]
218 */
219
220 indices1 = _mm_loadu_si128((xmm_t *) &index_array[0]);
221 indices2 = _mm_loadu_si128((xmm_t *) &index_array[2]);
222
223 indices3 = _mm_loadu_si128((xmm_t *) &index_array[4]);
224 indices4 = _mm_loadu_si128((xmm_t *) &index_array[6]);
225
226 /* Check for any matches. */
227 acl_match_check_x4(0, ctx, parms, &flows,
228 &indices1, &indices2, xmm_match_mask.x);
229 acl_match_check_x4(4, ctx, parms, &flows,
230 &indices3, &indices4, xmm_match_mask.x);
231
232 while (flows.started > 0) {
233
234 /* Gather 4 bytes of input data for each stream. */
235 input0 = _mm_cvtsi32_si128(GET_NEXT_4BYTES(parms, 0));
236 input1 = _mm_cvtsi32_si128(GET_NEXT_4BYTES(parms, 4));
237
238 input0 = _mm_insert_epi32(input0, GET_NEXT_4BYTES(parms, 1), 1);
239 input1 = _mm_insert_epi32(input1, GET_NEXT_4BYTES(parms, 5), 1);
240
241 input0 = _mm_insert_epi32(input0, GET_NEXT_4BYTES(parms, 2), 2);
242 input1 = _mm_insert_epi32(input1, GET_NEXT_4BYTES(parms, 6), 2);
243
244 input0 = _mm_insert_epi32(input0, GET_NEXT_4BYTES(parms, 3), 3);
245 input1 = _mm_insert_epi32(input1, GET_NEXT_4BYTES(parms, 7), 3);
246
247 /* Process the 4 bytes of input on each stream. */
248
249 input0 = transition4(input0, flows.trans,
250 &indices1, &indices2);
251 input1 = transition4(input1, flows.trans,
252 &indices3, &indices4);
253
254 input0 = transition4(input0, flows.trans,
255 &indices1, &indices2);
256 input1 = transition4(input1, flows.trans,
257 &indices3, &indices4);
258
259 input0 = transition4(input0, flows.trans,
260 &indices1, &indices2);
261 input1 = transition4(input1, flows.trans,
262 &indices3, &indices4);
263
264 input0 = transition4(input0, flows.trans,
265 &indices1, &indices2);
266 input1 = transition4(input1, flows.trans,
267 &indices3, &indices4);
268
269 /* Check for any matches. */
270 acl_match_check_x4(0, ctx, parms, &flows,
271 &indices1, &indices2, xmm_match_mask.x);
272 acl_match_check_x4(4, ctx, parms, &flows,
273 &indices3, &indices4, xmm_match_mask.x);
274 }
275
276 return 0;
277 }
278
279 /*
280 * Execute trie traversal with 4 traversals in parallel
281 */
282 static inline int
search_sse_4(const struct rte_acl_ctx * ctx,const uint8_t ** data,uint32_t * results,int total_packets,uint32_t categories)283 search_sse_4(const struct rte_acl_ctx *ctx, const uint8_t **data,
284 uint32_t *results, int total_packets, uint32_t categories)
285 {
286 int n;
287 struct acl_flow_data flows;
288 uint64_t index_array[MAX_SEARCHES_SSE4];
289 struct completion cmplt[MAX_SEARCHES_SSE4];
290 struct parms parms[MAX_SEARCHES_SSE4];
291 xmm_t input, indices1, indices2;
292
293 acl_set_flow(&flows, cmplt, RTE_DIM(cmplt), data, results,
294 total_packets, categories, ctx->trans_table);
295
296 for (n = 0; n < MAX_SEARCHES_SSE4; n++) {
297 cmplt[n].count = 0;
298 index_array[n] = acl_start_next_trie(&flows, parms, n, ctx);
299 }
300
301 indices1 = _mm_loadu_si128((xmm_t *) &index_array[0]);
302 indices2 = _mm_loadu_si128((xmm_t *) &index_array[2]);
303
304 /* Check for any matches. */
305 acl_match_check_x4(0, ctx, parms, &flows,
306 &indices1, &indices2, xmm_match_mask.x);
307
308 while (flows.started > 0) {
309
310 /* Gather 4 bytes of input data for each stream. */
311 input = _mm_cvtsi32_si128(GET_NEXT_4BYTES(parms, 0));
312 input = _mm_insert_epi32(input, GET_NEXT_4BYTES(parms, 1), 1);
313 input = _mm_insert_epi32(input, GET_NEXT_4BYTES(parms, 2), 2);
314 input = _mm_insert_epi32(input, GET_NEXT_4BYTES(parms, 3), 3);
315
316 /* Process the 4 bytes of input on each stream. */
317 input = transition4(input, flows.trans, &indices1, &indices2);
318 input = transition4(input, flows.trans, &indices1, &indices2);
319 input = transition4(input, flows.trans, &indices1, &indices2);
320 input = transition4(input, flows.trans, &indices1, &indices2);
321
322 /* Check for any matches. */
323 acl_match_check_x4(0, ctx, parms, &flows,
324 &indices1, &indices2, xmm_match_mask.x);
325 }
326
327 return 0;
328 }
329