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(uint8_t ips[16][RTE_FIB6_IPV6_ADDR_SIZE], 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][0]); 25 tmp2 = _mm512_loadu_si512(&ips[4][0]); 26 tmp3 = _mm512_loadu_si512(&ips[8][0]); 27 tmp4 = _mm512_loadu_si512(&ips[12][0]); 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(uint8_t ips[8][RTE_FIB6_IPV6_ADDR_SIZE], 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][0]); 61 tmp2 = _mm512_loadu_si512(&ips[4][0]); 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, uint8_t ips[32][RTE_FIB6_IPV6_ADDR_SIZE], 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 (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 (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 while (msk_ext_1 || msk_ext_2) { 150 idxes_1 = _mm512_maskz_slli_epi32(msk_ext_1, tmp_1, 8); 151 idxes_2 = _mm512_maskz_slli_epi32(msk_ext_2, tmp_2, 8); 152 byte_chunk_1 = (i < 8) ? 153 ((i >= 4) ? second_1 : first_1) : 154 ((i >= 12) ? fourth_1 : third_1); 155 byte_chunk_2 = (i < 8) ? 156 ((i >= 4) ? second_2 : first_2) : 157 ((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 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 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 res_1 = _mm512_mask_blend_epi32(msk_ext_1 ^ new_msk_1, res_1, 180 tmp_1); 181 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 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 trie_vec_lookup_x8x2_8b(void *p, uint8_t ips[16][RTE_FIB6_IPV6_ADDR_SIZE], 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 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 while (msk_ext_1 || msk_ext_2) { 271 idxes_1 = _mm512_maskz_slli_epi64(msk_ext_1, tmp_1, 8); 272 idxes_2 = _mm512_maskz_slli_epi64(msk_ext_2, tmp_2, 8); 273 byte_chunk_1 = (i < 8) ? first_1 : second_1; 274 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 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 res_1 = _mm512_mask_blend_epi64(msk_ext_1 ^ new_msk_1, res_1, 288 tmp_1); 289 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 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 } 307 308 void 309 rte_trie_vec_lookup_bulk_2b(void *p, uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], 310 uint64_t *next_hops, const unsigned int n) 311 { 312 uint32_t i; 313 for (i = 0; i < (n / 32); i++) { 314 trie_vec_lookup_x16x2(p, (uint8_t (*)[16])&ips[i * 32][0], 315 next_hops + i * 32, sizeof(uint16_t)); 316 } 317 rte_trie_lookup_bulk_2b(p, (uint8_t (*)[16])&ips[i * 32][0], 318 next_hops + i * 32, n - i * 32); 319 } 320 321 void 322 rte_trie_vec_lookup_bulk_4b(void *p, uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], 323 uint64_t *next_hops, const unsigned int n) 324 { 325 uint32_t i; 326 for (i = 0; i < (n / 32); i++) { 327 trie_vec_lookup_x16x2(p, (uint8_t (*)[16])&ips[i * 32][0], 328 next_hops + i * 32, sizeof(uint32_t)); 329 } 330 rte_trie_lookup_bulk_4b(p, (uint8_t (*)[16])&ips[i * 32][0], 331 next_hops + i * 32, n - i * 32); 332 } 333 334 void 335 rte_trie_vec_lookup_bulk_8b(void *p, uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], 336 uint64_t *next_hops, const unsigned int n) 337 { 338 uint32_t i; 339 for (i = 0; i < (n / 16); i++) { 340 trie_vec_lookup_x8x2_8b(p, (uint8_t (*)[16])&ips[i * 16][0], 341 next_hops + i * 16); 342 } 343 rte_trie_lookup_bulk_8b(p, (uint8_t (*)[16])&ips[i * 16][0], 344 next_hops + i * 16, n - i * 16); 345 } 346