1 // SPDX-License-Identifier: GPL-2.0-only 2 3 /* PIPAPO: PIle PAcket POlicies: AVX2 packet lookup routines 4 * 5 * Copyright (c) 2019-2020 Red Hat GmbH 6 * 7 * Author: Stefano Brivio <sbrivio@redhat.com> 8 */ 9 10 #include <linux/kernel.h> 11 #include <linux/init.h> 12 #include <linux/module.h> 13 #include <linux/netlink.h> 14 #include <linux/netfilter.h> 15 #include <linux/netfilter/nf_tables.h> 16 #include <net/netfilter/nf_tables_core.h> 17 #include <uapi/linux/netfilter/nf_tables.h> 18 #include <linux/bitmap.h> 19 #include <linux/bitops.h> 20 21 #include <linux/compiler.h> 22 #include <asm/fpu/api.h> 23 24 #include "nft_set_pipapo_avx2.h" 25 #include "nft_set_pipapo.h" 26 27 #define NFT_PIPAPO_LONGS_PER_M256 (XSAVE_YMM_SIZE / BITS_PER_LONG) 28 29 /* Load from memory into YMM register with non-temporal hint ("stream load"), 30 * that is, don't fetch lines from memory into the cache. This avoids pushing 31 * precious packet data out of the cache hierarchy, and is appropriate when: 32 * 33 * - loading buckets from lookup tables, as they are not going to be used 34 * again before packets are entirely classified 35 * 36 * - loading the result bitmap from the previous field, as it's never used 37 * again 38 */ 39 #define NFT_PIPAPO_AVX2_LOAD(reg, loc) \ 40 asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc)) 41 42 /* Stream a single lookup table bucket into YMM register given lookup table, 43 * group index, value of packet bits, bucket size. 44 */ 45 #define NFT_PIPAPO_AVX2_BUCKET_LOAD4(reg, lt, group, v, bsize) \ 46 NFT_PIPAPO_AVX2_LOAD(reg, \ 47 lt[((group) * NFT_PIPAPO_BUCKETS(4) + \ 48 (v)) * (bsize)]) 49 #define NFT_PIPAPO_AVX2_BUCKET_LOAD8(reg, lt, group, v, bsize) \ 50 NFT_PIPAPO_AVX2_LOAD(reg, \ 51 lt[((group) * NFT_PIPAPO_BUCKETS(8) + \ 52 (v)) * (bsize)]) 53 54 /* Bitwise AND: the staple operation of this algorithm */ 55 #define NFT_PIPAPO_AVX2_AND(dst, a, b) \ 56 asm volatile("vpand %ymm" #a ", %ymm" #b ", %ymm" #dst) 57 58 /* Jump to label if @reg is zero */ 59 #define NFT_PIPAPO_AVX2_NOMATCH_GOTO(reg, label) \ 60 asm_volatile_goto("vptest %%ymm" #reg ", %%ymm" #reg ";" \ 61 "je %l[" #label "]" : : : : label) 62 63 /* Store 256 bits from YMM register into memory. Contrary to bucket load 64 * operation, we don't bypass the cache here, as stored matching results 65 * are always used shortly after. 66 */ 67 #define NFT_PIPAPO_AVX2_STORE(loc, reg) \ 68 asm volatile("vmovdqa %%ymm" #reg ", %0" : "=m" (loc)) 69 70 /* Zero out a complete YMM register, @reg */ 71 #define NFT_PIPAPO_AVX2_ZERO(reg) \ 72 asm volatile("vpxor %ymm" #reg ", %ymm" #reg ", %ymm" #reg) 73 74 /* Current working bitmap index, toggled between field matches */ 75 static DEFINE_PER_CPU(bool, nft_pipapo_avx2_scratch_index); 76 77 /** 78 * nft_pipapo_avx2_prepare() - Prepare before main algorithm body 79 * 80 * This zeroes out ymm15, which is later used whenever we need to clear a 81 * memory location, by storing its content into memory. 82 */ 83 static void nft_pipapo_avx2_prepare(void) 84 { 85 NFT_PIPAPO_AVX2_ZERO(15); 86 } 87 88 /** 89 * nft_pipapo_avx2_fill() - Fill a bitmap region with ones 90 * @data: Base memory area 91 * @start: First bit to set 92 * @len: Count of bits to fill 93 * 94 * This is nothing else than a version of bitmap_set(), as used e.g. by 95 * pipapo_refill(), tailored for the microarchitectures using it and better 96 * suited for the specific usage: it's very likely that we'll set a small number 97 * of bits, not crossing a word boundary, and correct branch prediction is 98 * critical here. 99 * 100 * This function doesn't actually use any AVX2 instruction. 101 */ 102 static void nft_pipapo_avx2_fill(unsigned long *data, int start, int len) 103 { 104 int offset = start % BITS_PER_LONG; 105 unsigned long mask; 106 107 data += start / BITS_PER_LONG; 108 109 if (likely(len == 1)) { 110 *data |= BIT(offset); 111 return; 112 } 113 114 if (likely(len < BITS_PER_LONG || offset)) { 115 if (likely(len + offset <= BITS_PER_LONG)) { 116 *data |= GENMASK(len - 1 + offset, offset); 117 return; 118 } 119 120 *data |= ~0UL << offset; 121 len -= BITS_PER_LONG - offset; 122 data++; 123 124 if (len <= BITS_PER_LONG) { 125 mask = ~0UL >> (BITS_PER_LONG - len); 126 *data |= mask; 127 return; 128 } 129 } 130 131 memset(data, 0xff, len / BITS_PER_BYTE); 132 data += len / BITS_PER_LONG; 133 134 len %= BITS_PER_LONG; 135 if (len) 136 *data |= ~0UL >> (BITS_PER_LONG - len); 137 } 138 139 /** 140 * nft_pipapo_avx2_refill() - Scan bitmap, select mapping table item, set bits 141 * @offset: Start from given bitmap (equivalent to bucket) offset, in longs 142 * @map: Bitmap to be scanned for set bits 143 * @dst: Destination bitmap 144 * @mt: Mapping table containing bit set specifiers 145 * @len: Length of bitmap in longs 146 * @last: Return index of first set bit, if this is the last field 147 * 148 * This is an alternative implementation of pipapo_refill() suitable for usage 149 * with AVX2 lookup routines: we know there are four words to be scanned, at 150 * a given offset inside the map, for each matching iteration. 151 * 152 * This function doesn't actually use any AVX2 instruction. 153 * 154 * Return: first set bit index if @last, index of first filled word otherwise. 155 */ 156 static int nft_pipapo_avx2_refill(int offset, unsigned long *map, 157 unsigned long *dst, 158 union nft_pipapo_map_bucket *mt, bool last) 159 { 160 int ret = -1; 161 162 #define NFT_PIPAPO_AVX2_REFILL_ONE_WORD(x) \ 163 do { \ 164 while (map[(x)]) { \ 165 int r = __builtin_ctzl(map[(x)]); \ 166 int i = (offset + (x)) * BITS_PER_LONG + r; \ 167 \ 168 if (last) \ 169 return i; \ 170 \ 171 nft_pipapo_avx2_fill(dst, mt[i].to, mt[i].n); \ 172 \ 173 if (ret == -1) \ 174 ret = mt[i].to; \ 175 \ 176 map[(x)] &= ~(1UL << r); \ 177 } \ 178 } while (0) 179 180 NFT_PIPAPO_AVX2_REFILL_ONE_WORD(0); 181 NFT_PIPAPO_AVX2_REFILL_ONE_WORD(1); 182 NFT_PIPAPO_AVX2_REFILL_ONE_WORD(2); 183 NFT_PIPAPO_AVX2_REFILL_ONE_WORD(3); 184 #undef NFT_PIPAPO_AVX2_REFILL_ONE_WORD 185 186 return ret; 187 } 188 189 /** 190 * nft_pipapo_avx2_lookup_4b_2() - AVX2-based lookup for 2 four-bit groups 191 * @map: Previous match result, used as initial bitmap 192 * @fill: Destination bitmap to be filled with current match result 193 * @f: Field, containing lookup and mapping tables 194 * @offset: Ignore buckets before the given index, no bits are filled there 195 * @pkt: Packet data, pointer to input nftables register 196 * @first: If this is the first field, don't source previous result 197 * @last: Last field: stop at the first match and return bit index 198 * 199 * Load buckets from lookup table corresponding to the values of each 4-bit 200 * group of packet bytes, and perform a bitwise intersection between them. If 201 * this is the first field in the set, simply AND the buckets together 202 * (equivalent to using an all-ones starting bitmap), use the provided starting 203 * bitmap otherwise. Then call nft_pipapo_avx2_refill() to generate the next 204 * working bitmap, @fill. 205 * 206 * This is used for 8-bit fields (i.e. protocol numbers). 207 * 208 * Out-of-order (and superscalar) execution is vital here, so it's critical to 209 * avoid false data dependencies. CPU and compiler could (mostly) take care of 210 * this on their own, but the operation ordering is explicitly given here with 211 * a likely execution order in mind, to highlight possible stalls. That's why 212 * a number of logically distinct operations (i.e. loading buckets, intersecting 213 * buckets) are interleaved. 214 * 215 * Return: -1 on no match, rule index of match if @last, otherwise first long 216 * word index to be checked next (i.e. first filled word). 217 */ 218 static int nft_pipapo_avx2_lookup_4b_2(unsigned long *map, unsigned long *fill, 219 struct nft_pipapo_field *f, int offset, 220 const u8 *pkt, bool first, bool last) 221 { 222 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 223 u8 pg[2] = { pkt[0] >> 4, pkt[0] & 0xf }; 224 unsigned long *lt = f->lt, bsize = f->bsize; 225 226 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 227 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 228 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 229 230 if (first) { 231 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize); 232 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize); 233 NFT_PIPAPO_AVX2_AND(4, 0, 1); 234 } else { 235 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize); 236 NFT_PIPAPO_AVX2_LOAD(2, map[i_ul]); 237 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize); 238 NFT_PIPAPO_AVX2_NOMATCH_GOTO(2, nothing); 239 NFT_PIPAPO_AVX2_AND(3, 0, 1); 240 NFT_PIPAPO_AVX2_AND(4, 2, 3); 241 } 242 243 NFT_PIPAPO_AVX2_NOMATCH_GOTO(4, nomatch); 244 NFT_PIPAPO_AVX2_STORE(map[i_ul], 4); 245 246 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 247 if (last) 248 return b; 249 250 if (unlikely(ret == -1)) 251 ret = b / XSAVE_YMM_SIZE; 252 253 continue; 254 nomatch: 255 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 256 nothing: 257 ; 258 } 259 260 return ret; 261 } 262 263 /** 264 * nft_pipapo_avx2_lookup_4b_4() - AVX2-based lookup for 4 four-bit groups 265 * @map: Previous match result, used as initial bitmap 266 * @fill: Destination bitmap to be filled with current match result 267 * @f: Field, containing lookup and mapping tables 268 * @offset: Ignore buckets before the given index, no bits are filled there 269 * @pkt: Packet data, pointer to input nftables register 270 * @first: If this is the first field, don't source previous result 271 * @last: Last field: stop at the first match and return bit index 272 * 273 * See nft_pipapo_avx2_lookup_4b_2(). 274 * 275 * This is used for 16-bit fields (i.e. ports). 276 * 277 * Return: -1 on no match, rule index of match if @last, otherwise first long 278 * word index to be checked next (i.e. first filled word). 279 */ 280 static int nft_pipapo_avx2_lookup_4b_4(unsigned long *map, unsigned long *fill, 281 struct nft_pipapo_field *f, int offset, 282 const u8 *pkt, bool first, bool last) 283 { 284 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 285 u8 pg[4] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf }; 286 unsigned long *lt = f->lt, bsize = f->bsize; 287 288 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 289 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 290 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 291 292 if (first) { 293 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize); 294 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize); 295 NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 2, pg[2], bsize); 296 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 3, pg[3], bsize); 297 NFT_PIPAPO_AVX2_AND(4, 0, 1); 298 NFT_PIPAPO_AVX2_AND(5, 2, 3); 299 NFT_PIPAPO_AVX2_AND(7, 4, 5); 300 } else { 301 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize); 302 303 NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]); 304 305 NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize); 306 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize); 307 NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize); 308 NFT_PIPAPO_AVX2_AND(5, 0, 1); 309 310 NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing); 311 312 NFT_PIPAPO_AVX2_AND(6, 2, 3); 313 NFT_PIPAPO_AVX2_AND(7, 4, 5); 314 /* Stall */ 315 NFT_PIPAPO_AVX2_AND(7, 6, 7); 316 } 317 318 /* Stall */ 319 NFT_PIPAPO_AVX2_NOMATCH_GOTO(7, nomatch); 320 NFT_PIPAPO_AVX2_STORE(map[i_ul], 7); 321 322 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 323 if (last) 324 return b; 325 326 if (unlikely(ret == -1)) 327 ret = b / XSAVE_YMM_SIZE; 328 329 continue; 330 nomatch: 331 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 332 nothing: 333 ; 334 } 335 336 return ret; 337 } 338 339 /** 340 * nft_pipapo_avx2_lookup_4b_8() - AVX2-based lookup for 8 four-bit groups 341 * @map: Previous match result, used as initial bitmap 342 * @fill: Destination bitmap to be filled with current match result 343 * @f: Field, containing lookup and mapping tables 344 * @offset: Ignore buckets before the given index, no bits are filled there 345 * @pkt: Packet data, pointer to input nftables register 346 * @first: If this is the first field, don't source previous result 347 * @last: Last field: stop at the first match and return bit index 348 * 349 * See nft_pipapo_avx2_lookup_4b_2(). 350 * 351 * This is used for 32-bit fields (i.e. IPv4 addresses). 352 * 353 * Return: -1 on no match, rule index of match if @last, otherwise first long 354 * word index to be checked next (i.e. first filled word). 355 */ 356 static int nft_pipapo_avx2_lookup_4b_8(unsigned long *map, unsigned long *fill, 357 struct nft_pipapo_field *f, int offset, 358 const u8 *pkt, bool first, bool last) 359 { 360 u8 pg[8] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf, 361 pkt[2] >> 4, pkt[2] & 0xf, pkt[3] >> 4, pkt[3] & 0xf, 362 }; 363 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 364 unsigned long *lt = f->lt, bsize = f->bsize; 365 366 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 367 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 368 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 369 370 if (first) { 371 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize); 372 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize); 373 NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 2, pg[2], bsize); 374 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 3, pg[3], bsize); 375 NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 4, pg[4], bsize); 376 NFT_PIPAPO_AVX2_AND(5, 0, 1); 377 NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 5, pg[5], bsize); 378 NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 6, pg[6], bsize); 379 NFT_PIPAPO_AVX2_AND(8, 2, 3); 380 NFT_PIPAPO_AVX2_AND(9, 4, 5); 381 NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 7, pg[7], bsize); 382 NFT_PIPAPO_AVX2_AND(11, 6, 7); 383 NFT_PIPAPO_AVX2_AND(12, 8, 9); 384 NFT_PIPAPO_AVX2_AND(13, 10, 11); 385 386 /* Stall */ 387 NFT_PIPAPO_AVX2_AND(1, 12, 13); 388 } else { 389 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize); 390 NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]); 391 NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize); 392 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize); 393 NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize); 394 395 NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing); 396 397 NFT_PIPAPO_AVX2_AND(5, 0, 1); 398 NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 4, pg[4], bsize); 399 NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 5, pg[5], bsize); 400 NFT_PIPAPO_AVX2_AND(8, 2, 3); 401 NFT_PIPAPO_AVX2_BUCKET_LOAD4(9, lt, 6, pg[6], bsize); 402 NFT_PIPAPO_AVX2_AND(10, 4, 5); 403 NFT_PIPAPO_AVX2_BUCKET_LOAD4(11, lt, 7, pg[7], bsize); 404 NFT_PIPAPO_AVX2_AND(12, 6, 7); 405 NFT_PIPAPO_AVX2_AND(13, 8, 9); 406 NFT_PIPAPO_AVX2_AND(14, 10, 11); 407 408 /* Stall */ 409 NFT_PIPAPO_AVX2_AND(1, 12, 13); 410 NFT_PIPAPO_AVX2_AND(1, 1, 14); 411 } 412 413 NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nomatch); 414 NFT_PIPAPO_AVX2_STORE(map[i_ul], 1); 415 416 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 417 if (last) 418 return b; 419 420 if (unlikely(ret == -1)) 421 ret = b / XSAVE_YMM_SIZE; 422 423 continue; 424 425 nomatch: 426 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 427 nothing: 428 ; 429 } 430 431 return ret; 432 } 433 434 /** 435 * nft_pipapo_avx2_lookup_4b_12() - AVX2-based lookup for 12 four-bit groups 436 * @map: Previous match result, used as initial bitmap 437 * @fill: Destination bitmap to be filled with current match result 438 * @f: Field, containing lookup and mapping tables 439 * @offset: Ignore buckets before the given index, no bits are filled there 440 * @pkt: Packet data, pointer to input nftables register 441 * @first: If this is the first field, don't source previous result 442 * @last: Last field: stop at the first match and return bit index 443 * 444 * See nft_pipapo_avx2_lookup_4b_2(). 445 * 446 * This is used for 48-bit fields (i.e. MAC addresses/EUI-48). 447 * 448 * Return: -1 on no match, rule index of match if @last, otherwise first long 449 * word index to be checked next (i.e. first filled word). 450 */ 451 static int nft_pipapo_avx2_lookup_4b_12(unsigned long *map, unsigned long *fill, 452 struct nft_pipapo_field *f, int offset, 453 const u8 *pkt, bool first, bool last) 454 { 455 u8 pg[12] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf, 456 pkt[2] >> 4, pkt[2] & 0xf, pkt[3] >> 4, pkt[3] & 0xf, 457 pkt[4] >> 4, pkt[4] & 0xf, pkt[5] >> 4, pkt[5] & 0xf, 458 }; 459 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 460 unsigned long *lt = f->lt, bsize = f->bsize; 461 462 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 463 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 464 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 465 466 if (!first) 467 NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]); 468 469 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 0, pg[0], bsize); 470 NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize); 471 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize); 472 473 if (!first) { 474 NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing); 475 NFT_PIPAPO_AVX2_AND(1, 1, 0); 476 } 477 478 NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize); 479 NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 4, pg[4], bsize); 480 NFT_PIPAPO_AVX2_AND(6, 2, 3); 481 NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 5, pg[5], bsize); 482 NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 6, pg[6], bsize); 483 NFT_PIPAPO_AVX2_AND(9, 1, 4); 484 NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 7, pg[7], bsize); 485 NFT_PIPAPO_AVX2_AND(11, 5, 6); 486 NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 8, pg[8], bsize); 487 NFT_PIPAPO_AVX2_AND(13, 7, 8); 488 NFT_PIPAPO_AVX2_BUCKET_LOAD4(14, lt, 9, pg[9], bsize); 489 490 NFT_PIPAPO_AVX2_AND(0, 9, 10); 491 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 10, pg[10], bsize); 492 NFT_PIPAPO_AVX2_AND(2, 11, 12); 493 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 11, pg[11], bsize); 494 NFT_PIPAPO_AVX2_AND(4, 13, 14); 495 NFT_PIPAPO_AVX2_AND(5, 0, 1); 496 497 NFT_PIPAPO_AVX2_AND(6, 2, 3); 498 499 /* Stalls */ 500 NFT_PIPAPO_AVX2_AND(7, 4, 5); 501 NFT_PIPAPO_AVX2_AND(8, 6, 7); 502 503 NFT_PIPAPO_AVX2_NOMATCH_GOTO(8, nomatch); 504 NFT_PIPAPO_AVX2_STORE(map[i_ul], 8); 505 506 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 507 if (last) 508 return b; 509 510 if (unlikely(ret == -1)) 511 ret = b / XSAVE_YMM_SIZE; 512 513 continue; 514 nomatch: 515 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 516 nothing: 517 ; 518 } 519 520 return ret; 521 } 522 523 /** 524 * nft_pipapo_avx2_lookup_4b_32() - AVX2-based lookup for 32 four-bit groups 525 * @map: Previous match result, used as initial bitmap 526 * @fill: Destination bitmap to be filled with current match result 527 * @f: Field, containing lookup and mapping tables 528 * @offset: Ignore buckets before the given index, no bits are filled there 529 * @pkt: Packet data, pointer to input nftables register 530 * @first: If this is the first field, don't source previous result 531 * @last: Last field: stop at the first match and return bit index 532 * 533 * See nft_pipapo_avx2_lookup_4b_2(). 534 * 535 * This is used for 128-bit fields (i.e. IPv6 addresses). 536 * 537 * Return: -1 on no match, rule index of match if @last, otherwise first long 538 * word index to be checked next (i.e. first filled word). 539 */ 540 static int nft_pipapo_avx2_lookup_4b_32(unsigned long *map, unsigned long *fill, 541 struct nft_pipapo_field *f, int offset, 542 const u8 *pkt, bool first, bool last) 543 { 544 u8 pg[32] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf, 545 pkt[2] >> 4, pkt[2] & 0xf, pkt[3] >> 4, pkt[3] & 0xf, 546 pkt[4] >> 4, pkt[4] & 0xf, pkt[5] >> 4, pkt[5] & 0xf, 547 pkt[6] >> 4, pkt[6] & 0xf, pkt[7] >> 4, pkt[7] & 0xf, 548 pkt[8] >> 4, pkt[8] & 0xf, pkt[9] >> 4, pkt[9] & 0xf, 549 pkt[10] >> 4, pkt[10] & 0xf, pkt[11] >> 4, pkt[11] & 0xf, 550 pkt[12] >> 4, pkt[12] & 0xf, pkt[13] >> 4, pkt[13] & 0xf, 551 pkt[14] >> 4, pkt[14] & 0xf, pkt[15] >> 4, pkt[15] & 0xf, 552 }; 553 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 554 unsigned long *lt = f->lt, bsize = f->bsize; 555 556 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 557 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 558 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 559 560 if (!first) 561 NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]); 562 563 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 0, pg[0], bsize); 564 NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize); 565 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize); 566 NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize); 567 if (!first) { 568 NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing); 569 NFT_PIPAPO_AVX2_AND(1, 1, 0); 570 } 571 572 NFT_PIPAPO_AVX2_AND(5, 2, 3); 573 NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 4, pg[4], bsize); 574 NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 5, pg[5], bsize); 575 NFT_PIPAPO_AVX2_AND(8, 1, 4); 576 NFT_PIPAPO_AVX2_BUCKET_LOAD4(9, lt, 6, pg[6], bsize); 577 NFT_PIPAPO_AVX2_AND(10, 5, 6); 578 NFT_PIPAPO_AVX2_BUCKET_LOAD4(11, lt, 7, pg[7], bsize); 579 NFT_PIPAPO_AVX2_AND(12, 7, 8); 580 NFT_PIPAPO_AVX2_BUCKET_LOAD4(13, lt, 8, pg[8], bsize); 581 NFT_PIPAPO_AVX2_AND(14, 9, 10); 582 583 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 9, pg[9], bsize); 584 NFT_PIPAPO_AVX2_AND(1, 11, 12); 585 NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 10, pg[10], bsize); 586 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 11, pg[11], bsize); 587 NFT_PIPAPO_AVX2_AND(4, 13, 14); 588 NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 12, pg[12], bsize); 589 NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 13, pg[13], bsize); 590 NFT_PIPAPO_AVX2_AND(7, 0, 1); 591 NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 14, pg[14], bsize); 592 NFT_PIPAPO_AVX2_AND(9, 2, 3); 593 NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 15, pg[15], bsize); 594 NFT_PIPAPO_AVX2_AND(11, 4, 5); 595 NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 16, pg[16], bsize); 596 NFT_PIPAPO_AVX2_AND(13, 6, 7); 597 NFT_PIPAPO_AVX2_BUCKET_LOAD4(14, lt, 17, pg[17], bsize); 598 599 NFT_PIPAPO_AVX2_AND(0, 8, 9); 600 NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 18, pg[18], bsize); 601 NFT_PIPAPO_AVX2_AND(2, 10, 11); 602 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 19, pg[19], bsize); 603 NFT_PIPAPO_AVX2_AND(4, 12, 13); 604 NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 20, pg[20], bsize); 605 NFT_PIPAPO_AVX2_AND(6, 14, 0); 606 NFT_PIPAPO_AVX2_AND(7, 1, 2); 607 NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 21, pg[21], bsize); 608 NFT_PIPAPO_AVX2_AND(9, 3, 4); 609 NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 22, pg[22], bsize); 610 NFT_PIPAPO_AVX2_AND(11, 5, 6); 611 NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 23, pg[23], bsize); 612 NFT_PIPAPO_AVX2_AND(13, 7, 8); 613 614 NFT_PIPAPO_AVX2_BUCKET_LOAD4(14, lt, 24, pg[24], bsize); 615 NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 25, pg[25], bsize); 616 NFT_PIPAPO_AVX2_AND(1, 9, 10); 617 NFT_PIPAPO_AVX2_AND(2, 11, 12); 618 NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 26, pg[26], bsize); 619 NFT_PIPAPO_AVX2_AND(4, 13, 14); 620 NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 27, pg[27], bsize); 621 NFT_PIPAPO_AVX2_AND(6, 0, 1); 622 NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 28, pg[28], bsize); 623 NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 29, pg[29], bsize); 624 NFT_PIPAPO_AVX2_AND(9, 2, 3); 625 NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 30, pg[30], bsize); 626 NFT_PIPAPO_AVX2_AND(11, 4, 5); 627 NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 31, pg[31], bsize); 628 629 NFT_PIPAPO_AVX2_AND(0, 6, 7); 630 NFT_PIPAPO_AVX2_AND(1, 8, 9); 631 NFT_PIPAPO_AVX2_AND(2, 10, 11); 632 NFT_PIPAPO_AVX2_AND(3, 12, 0); 633 634 /* Stalls */ 635 NFT_PIPAPO_AVX2_AND(4, 1, 2); 636 NFT_PIPAPO_AVX2_AND(5, 3, 4); 637 638 NFT_PIPAPO_AVX2_NOMATCH_GOTO(5, nomatch); 639 NFT_PIPAPO_AVX2_STORE(map[i_ul], 5); 640 641 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 642 if (last) 643 return b; 644 645 if (unlikely(ret == -1)) 646 ret = b / XSAVE_YMM_SIZE; 647 648 continue; 649 nomatch: 650 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 651 nothing: 652 ; 653 } 654 655 return ret; 656 } 657 658 /** 659 * nft_pipapo_avx2_lookup_8b_1() - AVX2-based lookup for one eight-bit group 660 * @map: Previous match result, used as initial bitmap 661 * @fill: Destination bitmap to be filled with current match result 662 * @f: Field, containing lookup and mapping tables 663 * @offset: Ignore buckets before the given index, no bits are filled there 664 * @pkt: Packet data, pointer to input nftables register 665 * @first: If this is the first field, don't source previous result 666 * @last: Last field: stop at the first match and return bit index 667 * 668 * See nft_pipapo_avx2_lookup_4b_2(). 669 * 670 * This is used for 8-bit fields (i.e. protocol numbers). 671 * 672 * Return: -1 on no match, rule index of match if @last, otherwise first long 673 * word index to be checked next (i.e. first filled word). 674 */ 675 static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill, 676 struct nft_pipapo_field *f, int offset, 677 const u8 *pkt, bool first, bool last) 678 { 679 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 680 unsigned long *lt = f->lt, bsize = f->bsize; 681 682 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 683 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 684 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 685 686 if (first) { 687 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 0, pkt[0], bsize); 688 } else { 689 NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize); 690 NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]); 691 NFT_PIPAPO_AVX2_AND(2, 0, 1); 692 NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing); 693 } 694 695 NFT_PIPAPO_AVX2_NOMATCH_GOTO(2, nomatch); 696 NFT_PIPAPO_AVX2_STORE(map[i_ul], 2); 697 698 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 699 if (last) 700 return b; 701 702 if (unlikely(ret == -1)) 703 ret = b / XSAVE_YMM_SIZE; 704 705 continue; 706 nomatch: 707 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 708 nothing: 709 ; 710 } 711 712 return ret; 713 } 714 715 /** 716 * nft_pipapo_avx2_lookup_8b_2() - AVX2-based lookup for 2 eight-bit groups 717 * @map: Previous match result, used as initial bitmap 718 * @fill: Destination bitmap to be filled with current match result 719 * @f: Field, containing lookup and mapping tables 720 * @offset: Ignore buckets before the given index, no bits are filled there 721 * @pkt: Packet data, pointer to input nftables register 722 * @first: If this is the first field, don't source previous result 723 * @last: Last field: stop at the first match and return bit index 724 * 725 * See nft_pipapo_avx2_lookup_4b_2(). 726 * 727 * This is used for 16-bit fields (i.e. ports). 728 * 729 * Return: -1 on no match, rule index of match if @last, otherwise first long 730 * word index to be checked next (i.e. first filled word). 731 */ 732 static int nft_pipapo_avx2_lookup_8b_2(unsigned long *map, unsigned long *fill, 733 struct nft_pipapo_field *f, int offset, 734 const u8 *pkt, bool first, bool last) 735 { 736 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 737 unsigned long *lt = f->lt, bsize = f->bsize; 738 739 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 740 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 741 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 742 743 if (first) { 744 NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize); 745 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 1, pkt[1], bsize); 746 NFT_PIPAPO_AVX2_AND(4, 0, 1); 747 } else { 748 NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]); 749 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 0, pkt[0], bsize); 750 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize); 751 752 /* Stall */ 753 NFT_PIPAPO_AVX2_AND(3, 0, 1); 754 NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing); 755 NFT_PIPAPO_AVX2_AND(4, 3, 2); 756 } 757 758 /* Stall */ 759 NFT_PIPAPO_AVX2_NOMATCH_GOTO(4, nomatch); 760 NFT_PIPAPO_AVX2_STORE(map[i_ul], 4); 761 762 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 763 if (last) 764 return b; 765 766 if (unlikely(ret == -1)) 767 ret = b / XSAVE_YMM_SIZE; 768 769 continue; 770 nomatch: 771 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 772 nothing: 773 ; 774 } 775 776 return ret; 777 } 778 779 /** 780 * nft_pipapo_avx2_lookup_8b_4() - AVX2-based lookup for 4 eight-bit groups 781 * @map: Previous match result, used as initial bitmap 782 * @fill: Destination bitmap to be filled with current match result 783 * @f: Field, containing lookup and mapping tables 784 * @offset: Ignore buckets before the given index, no bits are filled there 785 * @pkt: Packet data, pointer to input nftables register 786 * @first: If this is the first field, don't source previous result 787 * @last: Last field: stop at the first match and return bit index 788 * 789 * See nft_pipapo_avx2_lookup_4b_2(). 790 * 791 * This is used for 32-bit fields (i.e. IPv4 addresses). 792 * 793 * Return: -1 on no match, rule index of match if @last, otherwise first long 794 * word index to be checked next (i.e. first filled word). 795 */ 796 static int nft_pipapo_avx2_lookup_8b_4(unsigned long *map, unsigned long *fill, 797 struct nft_pipapo_field *f, int offset, 798 const u8 *pkt, bool first, bool last) 799 { 800 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 801 unsigned long *lt = f->lt, bsize = f->bsize; 802 803 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 804 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 805 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 806 807 if (first) { 808 NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize); 809 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 1, pkt[1], bsize); 810 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 2, pkt[2], bsize); 811 NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 3, pkt[3], bsize); 812 813 /* Stall */ 814 NFT_PIPAPO_AVX2_AND(4, 0, 1); 815 NFT_PIPAPO_AVX2_AND(5, 2, 3); 816 NFT_PIPAPO_AVX2_AND(0, 4, 5); 817 } else { 818 NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize); 819 NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]); 820 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize); 821 NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 2, pkt[2], bsize); 822 NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 3, pkt[3], bsize); 823 824 NFT_PIPAPO_AVX2_AND(5, 0, 1); 825 NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing); 826 NFT_PIPAPO_AVX2_AND(6, 2, 3); 827 828 /* Stall */ 829 NFT_PIPAPO_AVX2_AND(7, 4, 5); 830 NFT_PIPAPO_AVX2_AND(0, 6, 7); 831 } 832 833 NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nomatch); 834 NFT_PIPAPO_AVX2_STORE(map[i_ul], 0); 835 836 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 837 if (last) 838 return b; 839 840 if (unlikely(ret == -1)) 841 ret = b / XSAVE_YMM_SIZE; 842 843 continue; 844 845 nomatch: 846 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 847 nothing: 848 ; 849 } 850 851 return ret; 852 } 853 854 /** 855 * nft_pipapo_avx2_lookup_8b_6() - AVX2-based lookup for 6 eight-bit groups 856 * @map: Previous match result, used as initial bitmap 857 * @fill: Destination bitmap to be filled with current match result 858 * @f: Field, containing lookup and mapping tables 859 * @offset: Ignore buckets before the given index, no bits are filled there 860 * @pkt: Packet data, pointer to input nftables register 861 * @first: If this is the first field, don't source previous result 862 * @last: Last field: stop at the first match and return bit index 863 * 864 * See nft_pipapo_avx2_lookup_4b_2(). 865 * 866 * This is used for 48-bit fields (i.e. MAC addresses/EUI-48). 867 * 868 * Return: -1 on no match, rule index of match if @last, otherwise first long 869 * word index to be checked next (i.e. first filled word). 870 */ 871 static int nft_pipapo_avx2_lookup_8b_6(unsigned long *map, unsigned long *fill, 872 struct nft_pipapo_field *f, int offset, 873 const u8 *pkt, bool first, bool last) 874 { 875 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 876 unsigned long *lt = f->lt, bsize = f->bsize; 877 878 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 879 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 880 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 881 882 if (first) { 883 NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize); 884 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 1, pkt[1], bsize); 885 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 2, pkt[2], bsize); 886 NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 3, pkt[3], bsize); 887 NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 4, pkt[4], bsize); 888 889 NFT_PIPAPO_AVX2_AND(5, 0, 1); 890 NFT_PIPAPO_AVX2_BUCKET_LOAD8(6, lt, 6, pkt[5], bsize); 891 NFT_PIPAPO_AVX2_AND(7, 2, 3); 892 893 /* Stall */ 894 NFT_PIPAPO_AVX2_AND(0, 4, 5); 895 NFT_PIPAPO_AVX2_AND(1, 6, 7); 896 NFT_PIPAPO_AVX2_AND(4, 0, 1); 897 } else { 898 NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize); 899 NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]); 900 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize); 901 NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 2, pkt[2], bsize); 902 NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 3, pkt[3], bsize); 903 904 NFT_PIPAPO_AVX2_AND(5, 0, 1); 905 NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing); 906 907 NFT_PIPAPO_AVX2_AND(6, 2, 3); 908 NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 4, pkt[4], bsize); 909 NFT_PIPAPO_AVX2_AND(0, 4, 5); 910 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 5, pkt[5], bsize); 911 NFT_PIPAPO_AVX2_AND(2, 6, 7); 912 913 /* Stall */ 914 NFT_PIPAPO_AVX2_AND(3, 0, 1); 915 NFT_PIPAPO_AVX2_AND(4, 2, 3); 916 } 917 918 NFT_PIPAPO_AVX2_NOMATCH_GOTO(4, nomatch); 919 NFT_PIPAPO_AVX2_STORE(map[i_ul], 4); 920 921 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 922 if (last) 923 return b; 924 925 if (unlikely(ret == -1)) 926 ret = b / XSAVE_YMM_SIZE; 927 928 continue; 929 930 nomatch: 931 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 932 nothing: 933 ; 934 } 935 936 return ret; 937 } 938 939 /** 940 * nft_pipapo_avx2_lookup_8b_16() - AVX2-based lookup for 16 eight-bit groups 941 * @map: Previous match result, used as initial bitmap 942 * @fill: Destination bitmap to be filled with current match result 943 * @f: Field, containing lookup and mapping tables 944 * @offset: Ignore buckets before the given index, no bits are filled there 945 * @pkt: Packet data, pointer to input nftables register 946 * @first: If this is the first field, don't source previous result 947 * @last: Last field: stop at the first match and return bit index 948 * 949 * See nft_pipapo_avx2_lookup_4b_2(). 950 * 951 * This is used for 128-bit fields (i.e. IPv6 addresses). 952 * 953 * Return: -1 on no match, rule index of match if @last, otherwise first long 954 * word index to be checked next (i.e. first filled word). 955 */ 956 static int nft_pipapo_avx2_lookup_8b_16(unsigned long *map, unsigned long *fill, 957 struct nft_pipapo_field *f, int offset, 958 const u8 *pkt, bool first, bool last) 959 { 960 int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b; 961 unsigned long *lt = f->lt, bsize = f->bsize; 962 963 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 964 for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) { 965 int i_ul = i * NFT_PIPAPO_LONGS_PER_M256; 966 967 if (!first) 968 NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]); 969 970 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 0, pkt[0], bsize); 971 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize); 972 NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 2, pkt[2], bsize); 973 if (!first) { 974 NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing); 975 NFT_PIPAPO_AVX2_AND(1, 1, 0); 976 } 977 NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 3, pkt[3], bsize); 978 979 NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt, 4, pkt[4], bsize); 980 NFT_PIPAPO_AVX2_AND(6, 1, 2); 981 NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 5, pkt[5], bsize); 982 NFT_PIPAPO_AVX2_AND(0, 3, 4); 983 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 6, pkt[6], bsize); 984 985 NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 7, pkt[7], bsize); 986 NFT_PIPAPO_AVX2_AND(3, 5, 6); 987 NFT_PIPAPO_AVX2_AND(4, 0, 1); 988 NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt, 8, pkt[8], bsize); 989 990 NFT_PIPAPO_AVX2_AND(6, 2, 3); 991 NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 9, pkt[9], bsize); 992 NFT_PIPAPO_AVX2_AND(0, 4, 5); 993 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 10, pkt[10], bsize); 994 NFT_PIPAPO_AVX2_AND(2, 6, 7); 995 NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 11, pkt[11], bsize); 996 NFT_PIPAPO_AVX2_AND(4, 0, 1); 997 NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt, 12, pkt[12], bsize); 998 NFT_PIPAPO_AVX2_AND(6, 2, 3); 999 NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 13, pkt[13], bsize); 1000 NFT_PIPAPO_AVX2_AND(0, 4, 5); 1001 NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 14, pkt[14], bsize); 1002 NFT_PIPAPO_AVX2_AND(2, 6, 7); 1003 NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 15, pkt[15], bsize); 1004 NFT_PIPAPO_AVX2_AND(4, 0, 1); 1005 1006 /* Stall */ 1007 NFT_PIPAPO_AVX2_AND(5, 2, 3); 1008 NFT_PIPAPO_AVX2_AND(6, 4, 5); 1009 1010 NFT_PIPAPO_AVX2_NOMATCH_GOTO(6, nomatch); 1011 NFT_PIPAPO_AVX2_STORE(map[i_ul], 6); 1012 1013 b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last); 1014 if (last) 1015 return b; 1016 1017 if (unlikely(ret == -1)) 1018 ret = b / XSAVE_YMM_SIZE; 1019 1020 continue; 1021 1022 nomatch: 1023 NFT_PIPAPO_AVX2_STORE(map[i_ul], 15); 1024 nothing: 1025 ; 1026 } 1027 1028 return ret; 1029 } 1030 1031 /** 1032 * nft_pipapo_avx2_lookup_slow() - Fallback function for uncommon field sizes 1033 * @map: Previous match result, used as initial bitmap 1034 * @fill: Destination bitmap to be filled with current match result 1035 * @f: Field, containing lookup and mapping tables 1036 * @offset: Ignore buckets before the given index, no bits are filled there 1037 * @pkt: Packet data, pointer to input nftables register 1038 * @first: If this is the first field, don't source previous result 1039 * @last: Last field: stop at the first match and return bit index 1040 * 1041 * This function should never be called, but is provided for the case the field 1042 * size doesn't match any of the known data types. Matching rate is 1043 * substantially lower than AVX2 routines. 1044 * 1045 * Return: -1 on no match, rule index of match if @last, otherwise first long 1046 * word index to be checked next (i.e. first filled word). 1047 */ 1048 static int nft_pipapo_avx2_lookup_slow(unsigned long *map, unsigned long *fill, 1049 struct nft_pipapo_field *f, int offset, 1050 const u8 *pkt, bool first, bool last) 1051 { 1052 unsigned long *lt = f->lt, bsize = f->bsize; 1053 int i, ret = -1, b; 1054 1055 lt += offset * NFT_PIPAPO_LONGS_PER_M256; 1056 1057 if (first) 1058 memset(map, 0xff, bsize * sizeof(*map)); 1059 1060 for (i = offset; i < bsize; i++) { 1061 if (f->bb == 8) 1062 pipapo_and_field_buckets_8bit(f, map, pkt); 1063 else 1064 pipapo_and_field_buckets_4bit(f, map, pkt); 1065 NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4; 1066 1067 b = pipapo_refill(map, bsize, f->rules, fill, f->mt, last); 1068 1069 if (last) 1070 return b; 1071 1072 if (ret == -1) 1073 ret = b / XSAVE_YMM_SIZE; 1074 } 1075 1076 return ret; 1077 } 1078 1079 /** 1080 * nft_pipapo_avx2_estimate() - Set size, space and lookup complexity 1081 * @desc: Set description, element count and field description used 1082 * @features: Flags: NFT_SET_INTERVAL needs to be there 1083 * @est: Storage for estimation data 1084 * 1085 * Return: true if set is compatible and AVX2 available, false otherwise. 1086 */ 1087 bool nft_pipapo_avx2_estimate(const struct nft_set_desc *desc, u32 features, 1088 struct nft_set_estimate *est) 1089 { 1090 if (!(features & NFT_SET_INTERVAL) || 1091 desc->field_count < NFT_PIPAPO_MIN_FIELDS) 1092 return false; 1093 1094 if (!boot_cpu_has(X86_FEATURE_AVX2) || !boot_cpu_has(X86_FEATURE_AVX)) 1095 return false; 1096 1097 est->size = pipapo_estimate_size(desc); 1098 if (!est->size) 1099 return false; 1100 1101 est->lookup = NFT_SET_CLASS_O_LOG_N; 1102 1103 est->space = NFT_SET_CLASS_O_N; 1104 1105 return true; 1106 } 1107 1108 /** 1109 * nft_pipapo_avx2_lookup() - Lookup function for AVX2 implementation 1110 * @net: Network namespace 1111 * @set: nftables API set representation 1112 * @elem: nftables API element representation containing key data 1113 * @ext: nftables API extension pointer, filled with matching reference 1114 * 1115 * For more details, see DOC: Theory of Operation in nft_set_pipapo.c. 1116 * 1117 * This implementation exploits the repetitive characteristic of the algorithm 1118 * to provide a fast, vectorised version using the AVX2 SIMD instruction set. 1119 * 1120 * Return: true on match, false otherwise. 1121 */ 1122 bool nft_pipapo_avx2_lookup(const struct net *net, const struct nft_set *set, 1123 const u32 *key, const struct nft_set_ext **ext) 1124 { 1125 struct nft_pipapo *priv = nft_set_priv(set); 1126 unsigned long *res, *fill, *scratch; 1127 u8 genmask = nft_genmask_cur(net); 1128 const u8 *rp = (const u8 *)key; 1129 struct nft_pipapo_match *m; 1130 struct nft_pipapo_field *f; 1131 bool map_index; 1132 int i, ret = 0; 1133 1134 m = rcu_dereference(priv->match); 1135 1136 /* This also protects access to all data related to scratch maps */ 1137 kernel_fpu_begin(); 1138 1139 scratch = *raw_cpu_ptr(m->scratch_aligned); 1140 if (unlikely(!scratch)) { 1141 kernel_fpu_end(); 1142 return false; 1143 } 1144 map_index = raw_cpu_read(nft_pipapo_avx2_scratch_index); 1145 1146 res = scratch + (map_index ? m->bsize_max : 0); 1147 fill = scratch + (map_index ? 0 : m->bsize_max); 1148 1149 /* Starting map doesn't need to be set for this implementation */ 1150 1151 nft_pipapo_avx2_prepare(); 1152 1153 next_match: 1154 nft_pipapo_for_each_field(f, i, m) { 1155 bool last = i == m->field_count - 1, first = !i; 1156 1157 #define NFT_SET_PIPAPO_AVX2_LOOKUP(b, n) \ 1158 (ret = nft_pipapo_avx2_lookup_##b##b_##n(res, fill, f, \ 1159 ret, rp, \ 1160 first, last)) 1161 1162 if (likely(f->bb == 8)) { 1163 if (f->groups == 1) { 1164 NFT_SET_PIPAPO_AVX2_LOOKUP(8, 1); 1165 } else if (f->groups == 2) { 1166 NFT_SET_PIPAPO_AVX2_LOOKUP(8, 2); 1167 } else if (f->groups == 4) { 1168 NFT_SET_PIPAPO_AVX2_LOOKUP(8, 4); 1169 } else if (f->groups == 6) { 1170 NFT_SET_PIPAPO_AVX2_LOOKUP(8, 6); 1171 } else if (f->groups == 16) { 1172 NFT_SET_PIPAPO_AVX2_LOOKUP(8, 16); 1173 } else { 1174 ret = nft_pipapo_avx2_lookup_slow(res, fill, f, 1175 ret, rp, 1176 first, last); 1177 } 1178 } else { 1179 if (f->groups == 2) { 1180 NFT_SET_PIPAPO_AVX2_LOOKUP(4, 2); 1181 } else if (f->groups == 4) { 1182 NFT_SET_PIPAPO_AVX2_LOOKUP(4, 4); 1183 } else if (f->groups == 8) { 1184 NFT_SET_PIPAPO_AVX2_LOOKUP(4, 8); 1185 } else if (f->groups == 12) { 1186 NFT_SET_PIPAPO_AVX2_LOOKUP(4, 12); 1187 } else if (f->groups == 32) { 1188 NFT_SET_PIPAPO_AVX2_LOOKUP(4, 32); 1189 } else { 1190 ret = nft_pipapo_avx2_lookup_slow(res, fill, f, 1191 ret, rp, 1192 first, last); 1193 } 1194 } 1195 NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4; 1196 1197 #undef NFT_SET_PIPAPO_AVX2_LOOKUP 1198 1199 if (ret < 0) 1200 goto out; 1201 1202 if (last) { 1203 *ext = &f->mt[ret].e->ext; 1204 if (unlikely(nft_set_elem_expired(*ext) || 1205 !nft_set_elem_active(*ext, genmask))) { 1206 ret = 0; 1207 goto next_match; 1208 } 1209 1210 goto out; 1211 } 1212 1213 swap(res, fill); 1214 rp += NFT_PIPAPO_GROUPS_PADDED_SIZE(f); 1215 } 1216 1217 out: 1218 if (i % 2) 1219 raw_cpu_write(nft_pipapo_avx2_scratch_index, !map_index); 1220 kernel_fpu_end(); 1221 1222 return ret >= 0; 1223 } 1224