Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2020 Intel Corporation
3 : : */
4 : :
5 : : #include <rte_vect.h>
6 : : #include <rte_fib6.h>
7 : :
8 : : #include "trie.h"
9 : : #include "trie_avx512.h"
10 : :
11 : : static __rte_always_inline void
12 : : transpose_x16(const struct rte_ipv6_addr *ips,
13 : : __m512i *first, __m512i *second, __m512i *third, __m512i *fourth)
14 : : {
15 : : __m512i tmp1, tmp2, tmp3, tmp4;
16 : : __m512i tmp5, tmp6, tmp7, tmp8;
17 : : const __rte_x86_zmm_t perm_idxes = {
18 : : .u32 = { 0, 4, 8, 12, 2, 6, 10, 14,
19 : : 1, 5, 9, 13, 3, 7, 11, 15
20 : : },
21 : : };
22 : :
23 : : /* load all ip addresses */
24 : : tmp1 = _mm512_loadu_si512(&ips[0]);
25 : : tmp2 = _mm512_loadu_si512(&ips[4]);
26 : : tmp3 = _mm512_loadu_si512(&ips[8]);
27 : : tmp4 = _mm512_loadu_si512(&ips[12]);
28 : :
29 : : /* transpose 4 byte chunks of 16 ips */
30 : : tmp5 = _mm512_unpacklo_epi32(tmp1, tmp2);
31 : : tmp7 = _mm512_unpackhi_epi32(tmp1, tmp2);
32 : : tmp6 = _mm512_unpacklo_epi32(tmp3, tmp4);
33 : : tmp8 = _mm512_unpackhi_epi32(tmp3, tmp4);
34 : :
35 : : tmp1 = _mm512_unpacklo_epi32(tmp5, tmp6);
36 : : tmp3 = _mm512_unpackhi_epi32(tmp5, tmp6);
37 : : tmp2 = _mm512_unpacklo_epi32(tmp7, tmp8);
38 : : tmp4 = _mm512_unpackhi_epi32(tmp7, tmp8);
39 : :
40 : : /* first 4-byte chunks of ips[] */
41 : : *first = _mm512_permutexvar_epi32(perm_idxes.z, tmp1);
42 : : /* second 4-byte chunks of ips[] */
43 : : *second = _mm512_permutexvar_epi32(perm_idxes.z, tmp3);
44 : : /* third 4-byte chunks of ips[] */
45 : : *third = _mm512_permutexvar_epi32(perm_idxes.z, tmp2);
46 : : /* fourth 4-byte chunks of ips[] */
47 : : *fourth = _mm512_permutexvar_epi32(perm_idxes.z, tmp4);
48 : : }
49 : :
50 : : static __rte_always_inline void
51 : : transpose_x8(const struct rte_ipv6_addr *ips,
52 : : __m512i *first, __m512i *second)
53 : : {
54 : : __m512i tmp1, tmp2, tmp3, tmp4;
55 : : const __rte_x86_zmm_t perm_idxes = {
56 : : .u64 = { 0, 2, 4, 6, 1, 3, 5, 7
57 : : },
58 : : };
59 : :
60 : : tmp1 = _mm512_loadu_si512(&ips[0]);
61 : : tmp2 = _mm512_loadu_si512(&ips[4]);
62 : :
63 : : tmp3 = _mm512_unpacklo_epi64(tmp1, tmp2);
64 : : *first = _mm512_permutexvar_epi64(perm_idxes.z, tmp3);
65 : : tmp4 = _mm512_unpackhi_epi64(tmp1, tmp2);
66 : : *second = _mm512_permutexvar_epi64(perm_idxes.z, tmp4);
67 : : }
68 : :
69 : : static __rte_always_inline void
70 : : trie_vec_lookup_x16x2(void *p, const struct rte_ipv6_addr *ips,
71 : : uint64_t *next_hops, int size)
72 : : {
73 : : struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;
74 : : const __m512i zero = _mm512_set1_epi32(0);
75 : : const __m512i lsb = _mm512_set1_epi32(1);
76 : : const __m512i two_lsb = _mm512_set1_epi32(3);
77 : : /* IPv6 four byte chunks */
78 : : __m512i first_1, second_1, third_1, fourth_1;
79 : : __m512i first_2, second_2, third_2, fourth_2;
80 : : __m512i idxes_1, res_1;
81 : : __m512i idxes_2, res_2;
82 : : __m512i shuf_idxes;
83 : : __m512i tmp_1, tmp2_1, bytes_1, byte_chunk_1;
84 : : __m512i tmp_2, tmp2_2, bytes_2, byte_chunk_2;
85 : : __m512i base_idxes;
86 : : /* used to mask gather values if size is 2 (16 bit next hops) */
87 : : const __m512i res_msk = _mm512_set1_epi32(UINT16_MAX);
88 : : const __rte_x86_zmm_t bswap = {
89 : : .u8 = { 2, 1, 0, 255, 6, 5, 4, 255,
90 : : 10, 9, 8, 255, 14, 13, 12, 255,
91 : : 2, 1, 0, 255, 6, 5, 4, 255,
92 : : 10, 9, 8, 255, 14, 13, 12, 255,
93 : : 2, 1, 0, 255, 6, 5, 4, 255,
94 : : 10, 9, 8, 255, 14, 13, 12, 255,
95 : : 2, 1, 0, 255, 6, 5, 4, 255,
96 : : 10, 9, 8, 255, 14, 13, 12, 255
97 : : },
98 : : };
99 : : const __mmask64 k = 0x1111111111111111;
100 : : int i = 3;
101 : : __mmask16 msk_ext_1, new_msk_1;
102 : : __mmask16 msk_ext_2, new_msk_2;
103 : : __mmask16 exp_msk = 0x5555;
104 : :
105 : : transpose_x16(ips, &first_1, &second_1, &third_1, &fourth_1);
106 : : transpose_x16(ips + 16, &first_2, &second_2, &third_2, &fourth_2);
107 : :
108 : : /* get_tbl24_idx() for every 4 byte chunk */
109 : : idxes_1 = _mm512_shuffle_epi8(first_1, bswap.z);
110 : : idxes_2 = _mm512_shuffle_epi8(first_2, bswap.z);
111 : :
112 : : /**
113 : : * lookup in tbl24
114 : : * Put it inside branch to make compiller happy with -O0
115 : : */
116 : : if (size == sizeof(uint16_t)) {
117 : : res_1 = _mm512_i32gather_epi32(idxes_1,
118 : 0 : (const int *)dp->tbl24, 2);
119 : : res_2 = _mm512_i32gather_epi32(idxes_2,
120 : : (const int *)dp->tbl24, 2);
121 : : res_1 = _mm512_and_epi32(res_1, res_msk);
122 : : res_2 = _mm512_and_epi32(res_2, res_msk);
123 : : } else {
124 : : res_1 = _mm512_i32gather_epi32(idxes_1,
125 : 0 : (const int *)dp->tbl24, 4);
126 : : res_2 = _mm512_i32gather_epi32(idxes_2,
127 : : (const int *)dp->tbl24, 4);
128 : : }
129 : :
130 : : /* get extended entries indexes */
131 : : msk_ext_1 = _mm512_test_epi32_mask(res_1, lsb);
132 : : msk_ext_2 = _mm512_test_epi32_mask(res_2, lsb);
133 : :
134 : : tmp_1 = _mm512_srli_epi32(res_1, 1);
135 : : tmp_2 = _mm512_srli_epi32(res_2, 1);
136 : :
137 : : /* idxes to retrieve bytes */
138 : : shuf_idxes = _mm512_setr_epi32(3, 7, 11, 15,
139 : : 19, 23, 27, 31,
140 : : 35, 39, 43, 47,
141 : : 51, 55, 59, 63);
142 : :
143 : : base_idxes = _mm512_setr_epi32(0, 4, 8, 12,
144 : : 16, 20, 24, 28,
145 : : 32, 36, 40, 44,
146 : : 48, 52, 56, 60);
147 : :
148 : : /* traverse down the trie */
149 [ # # # # ]: 0 : while (msk_ext_1 || msk_ext_2) {
150 [ # # # # ]: 0 : idxes_1 = _mm512_maskz_slli_epi32(msk_ext_1, tmp_1, 8);
151 : 0 : idxes_2 = _mm512_maskz_slli_epi32(msk_ext_2, tmp_2, 8);
152 : : byte_chunk_1 = (i < 8) ?
153 [ # # # # : 0 : ((i >= 4) ? second_1 : first_1) :
# # # # ]
154 [ # # # # ]: 0 : ((i >= 12) ? fourth_1 : third_1);
155 : : byte_chunk_2 = (i < 8) ?
156 [ # # # # : 0 : ((i >= 4) ? second_2 : first_2) :
# # # # ]
157 [ # # # # ]: 0 : ((i >= 12) ? fourth_2 : third_2);
158 : : bytes_1 = _mm512_maskz_shuffle_epi8(k, byte_chunk_1,
159 : : shuf_idxes);
160 : : bytes_2 = _mm512_maskz_shuffle_epi8(k, byte_chunk_2,
161 : : shuf_idxes);
162 : : idxes_1 = _mm512_maskz_add_epi32(msk_ext_1, idxes_1, bytes_1);
163 : : idxes_2 = _mm512_maskz_add_epi32(msk_ext_2, idxes_2, bytes_2);
164 : : if (size == sizeof(uint16_t)) {
165 : : tmp_1 = _mm512_mask_i32gather_epi32(zero, msk_ext_1,
166 : 0 : idxes_1, (const int *)dp->tbl8, 2);
167 : : tmp_2 = _mm512_mask_i32gather_epi32(zero, msk_ext_2,
168 : : idxes_2, (const int *)dp->tbl8, 2);
169 : : tmp_1 = _mm512_and_epi32(tmp_1, res_msk);
170 : : tmp_2 = _mm512_and_epi32(tmp_2, res_msk);
171 : : } else {
172 : : tmp_1 = _mm512_mask_i32gather_epi32(zero, msk_ext_1,
173 : 0 : idxes_1, (const int *)dp->tbl8, 4);
174 : : tmp_2 = _mm512_mask_i32gather_epi32(zero, msk_ext_2,
175 : : idxes_2, (const int *)dp->tbl8, 4);
176 : : }
177 : : new_msk_1 = _mm512_test_epi32_mask(tmp_1, lsb);
178 : : new_msk_2 = _mm512_test_epi32_mask(tmp_2, lsb);
179 : 0 : res_1 = _mm512_mask_blend_epi32(msk_ext_1 ^ new_msk_1, res_1,
180 : : tmp_1);
181 : 0 : res_2 = _mm512_mask_blend_epi32(msk_ext_2 ^ new_msk_2, res_2,
182 : : tmp_2);
183 : : tmp_1 = _mm512_srli_epi32(tmp_1, 1);
184 : : tmp_2 = _mm512_srli_epi32(tmp_2, 1);
185 : : msk_ext_1 = new_msk_1;
186 : : msk_ext_2 = new_msk_2;
187 : :
188 : : shuf_idxes = _mm512_maskz_add_epi8(k, shuf_idxes, lsb);
189 : : shuf_idxes = _mm512_and_epi32(shuf_idxes, two_lsb);
190 : : shuf_idxes = _mm512_maskz_add_epi8(k, shuf_idxes, base_idxes);
191 : 0 : i++;
192 : : }
193 : :
194 : : /* get rid of 1 LSB, now we have HN in every epi32 */
195 : : res_1 = _mm512_srli_epi32(res_1, 1);
196 : : res_2 = _mm512_srli_epi32(res_2, 1);
197 : : /* extract first half of NH's each in epi64 chunk */
198 : : tmp_1 = _mm512_maskz_expand_epi32(exp_msk, res_1);
199 : : tmp_2 = _mm512_maskz_expand_epi32(exp_msk, res_2);
200 : : /* extract second half of NH's */
201 : : __m256i tmp256_1, tmp256_2;
202 : : tmp256_1 = _mm512_extracti32x8_epi32(res_1, 1);
203 : : tmp256_2 = _mm512_extracti32x8_epi32(res_2, 1);
204 : : tmp2_1 = _mm512_maskz_expand_epi32(exp_msk,
205 : : _mm512_castsi256_si512(tmp256_1));
206 : : tmp2_2 = _mm512_maskz_expand_epi32(exp_msk,
207 : : _mm512_castsi256_si512(tmp256_2));
208 : : /* return NH's from two sets of registers */
209 : : _mm512_storeu_si512(next_hops, tmp_1);
210 : : _mm512_storeu_si512(next_hops + 8, tmp2_1);
211 : : _mm512_storeu_si512(next_hops + 16, tmp_2);
212 : : _mm512_storeu_si512(next_hops + 24, tmp2_2);
213 : : }
214 : :
215 : : static void
216 : 0 : trie_vec_lookup_x8x2_8b(void *p, const struct rte_ipv6_addr *ips,
217 : : uint64_t *next_hops)
218 : : {
219 : : struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;
220 : : const __m512i zero = _mm512_set1_epi32(0);
221 : : const __m512i lsb = _mm512_set1_epi32(1);
222 : : const __m512i three_lsb = _mm512_set1_epi32(7);
223 : : /* IPv6 eight byte chunks */
224 : : __m512i first_1, second_1;
225 : : __m512i first_2, second_2;
226 : : __m512i idxes_1, res_1;
227 : : __m512i idxes_2, res_2;
228 : : __m512i shuf_idxes, base_idxes;
229 : : __m512i tmp_1, bytes_1, byte_chunk_1;
230 : : __m512i tmp_2, bytes_2, byte_chunk_2;
231 : : const __rte_x86_zmm_t bswap = {
232 : : .u8 = { 2, 1, 0, 255, 255, 255, 255, 255,
233 : : 10, 9, 8, 255, 255, 255, 255, 255,
234 : : 2, 1, 0, 255, 255, 255, 255, 255,
235 : : 10, 9, 8, 255, 255, 255, 255, 255,
236 : : 2, 1, 0, 255, 255, 255, 255, 255,
237 : : 10, 9, 8, 255, 255, 255, 255, 255,
238 : : 2, 1, 0, 255, 255, 255, 255, 255,
239 : : 10, 9, 8, 255, 255, 255, 255, 255
240 : : },
241 : : };
242 : : const __mmask64 k = 0x101010101010101;
243 : : int i = 3;
244 : : __mmask8 msk_ext_1, new_msk_1;
245 : : __mmask8 msk_ext_2, new_msk_2;
246 : :
247 : : transpose_x8(ips, &first_1, &second_1);
248 : : transpose_x8(ips + 8, &first_2, &second_2);
249 : :
250 : : /* get_tbl24_idx() for every 4 byte chunk */
251 : : idxes_1 = _mm512_shuffle_epi8(first_1, bswap.z);
252 : : idxes_2 = _mm512_shuffle_epi8(first_2, bswap.z);
253 : :
254 : : /* lookup in tbl24 */
255 : 0 : res_1 = _mm512_i64gather_epi64(idxes_1, (const void *)dp->tbl24, 8);
256 : : res_2 = _mm512_i64gather_epi64(idxes_2, (const void *)dp->tbl24, 8);
257 : : /* get extended entries indexes */
258 : : msk_ext_1 = _mm512_test_epi64_mask(res_1, lsb);
259 : : msk_ext_2 = _mm512_test_epi64_mask(res_2, lsb);
260 : :
261 : : tmp_1 = _mm512_srli_epi64(res_1, 1);
262 : : tmp_2 = _mm512_srli_epi64(res_2, 1);
263 : :
264 : : /* idxes to retrieve bytes */
265 : : shuf_idxes = _mm512_setr_epi64(3, 11, 19, 27, 35, 43, 51, 59);
266 : :
267 : : base_idxes = _mm512_setr_epi64(0, 8, 16, 24, 32, 40, 48, 56);
268 : :
269 : : /* traverse down the trie */
270 [ # # ]: 0 : while (msk_ext_1 || msk_ext_2) {
271 [ # # ]: 0 : idxes_1 = _mm512_maskz_slli_epi64(msk_ext_1, tmp_1, 8);
272 : 0 : idxes_2 = _mm512_maskz_slli_epi64(msk_ext_2, tmp_2, 8);
273 [ # # ]: 0 : byte_chunk_1 = (i < 8) ? first_1 : second_1;
274 [ # # ]: 0 : byte_chunk_2 = (i < 8) ? first_2 : second_2;
275 : : bytes_1 = _mm512_maskz_shuffle_epi8(k, byte_chunk_1,
276 : : shuf_idxes);
277 : : bytes_2 = _mm512_maskz_shuffle_epi8(k, byte_chunk_2,
278 : : shuf_idxes);
279 : : idxes_1 = _mm512_maskz_add_epi64(msk_ext_1, idxes_1, bytes_1);
280 : : idxes_2 = _mm512_maskz_add_epi64(msk_ext_2, idxes_2, bytes_2);
281 : : tmp_1 = _mm512_mask_i64gather_epi64(zero, msk_ext_1,
282 : 0 : idxes_1, (const void *)dp->tbl8, 8);
283 : : tmp_2 = _mm512_mask_i64gather_epi64(zero, msk_ext_2,
284 : : idxes_2, (const void *)dp->tbl8, 8);
285 : : new_msk_1 = _mm512_test_epi64_mask(tmp_1, lsb);
286 : : new_msk_2 = _mm512_test_epi64_mask(tmp_2, lsb);
287 : 0 : res_1 = _mm512_mask_blend_epi64(msk_ext_1 ^ new_msk_1, res_1,
288 : : tmp_1);
289 : 0 : res_2 = _mm512_mask_blend_epi64(msk_ext_2 ^ new_msk_2, res_2,
290 : : tmp_2);
291 : : tmp_1 = _mm512_srli_epi64(tmp_1, 1);
292 : : tmp_2 = _mm512_srli_epi64(tmp_2, 1);
293 : : msk_ext_1 = new_msk_1;
294 : : msk_ext_2 = new_msk_2;
295 : :
296 : : shuf_idxes = _mm512_maskz_add_epi8(k, shuf_idxes, lsb);
297 : : shuf_idxes = _mm512_and_epi64(shuf_idxes, three_lsb);
298 : : shuf_idxes = _mm512_maskz_add_epi8(k, shuf_idxes, base_idxes);
299 : 0 : i++;
300 : : }
301 : :
302 : : res_1 = _mm512_srli_epi64(res_1, 1);
303 : : res_2 = _mm512_srli_epi64(res_2, 1);
304 : : _mm512_storeu_si512(next_hops, res_1);
305 : : _mm512_storeu_si512(next_hops + 8, res_2);
306 : 0 : }
307 : :
308 : : void
309 : 0 : rte_trie_vec_lookup_bulk_2b(void *p, const struct rte_ipv6_addr *ips,
310 : : uint64_t *next_hops, const unsigned int n)
311 : : {
312 : : uint32_t i;
313 [ # # ]: 0 : for (i = 0; i < (n / 32); i++) {
314 : 0 : trie_vec_lookup_x16x2(p, &ips[i * 32],
315 : 0 : next_hops + i * 32, sizeof(uint16_t));
316 : : }
317 : 0 : rte_trie_lookup_bulk_2b(p, &ips[i * 32],
318 : 0 : next_hops + i * 32, n - i * 32);
319 : 0 : }
320 : :
321 : : void
322 : 0 : rte_trie_vec_lookup_bulk_4b(void *p, const struct rte_ipv6_addr *ips,
323 : : uint64_t *next_hops, const unsigned int n)
324 : : {
325 : : uint32_t i;
326 [ # # ]: 0 : for (i = 0; i < (n / 32); i++) {
327 : 0 : trie_vec_lookup_x16x2(p, &ips[i * 32],
328 : 0 : next_hops + i * 32, sizeof(uint32_t));
329 : : }
330 : 0 : rte_trie_lookup_bulk_4b(p, &ips[i * 32],
331 : 0 : next_hops + i * 32, n - i * 32);
332 : 0 : }
333 : :
334 : : void
335 : 0 : rte_trie_vec_lookup_bulk_8b(void *p, const struct rte_ipv6_addr *ips,
336 : : uint64_t *next_hops, const unsigned int n)
337 : : {
338 : : uint32_t i;
339 [ # # ]: 0 : for (i = 0; i < (n / 16); i++) {
340 : 0 : trie_vec_lookup_x8x2_8b(p, &ips[i * 16],
341 : 0 : next_hops + i * 16);
342 : : }
343 : 0 : rte_trie_lookup_bulk_8b(p, &ips[i * 16],
344 : 0 : next_hops + i * 16, n - i * 16);
345 : 0 : }
|
