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