net/netfilter/nft_set_pipapo_avx2.c

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