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 /* 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 }