net/netfilter/nft_set_pipapo.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2
   3 /* PIPAPO: PIle PAcket POlicies: set for arbitrary concatenations of ranges
   4  *
   5  * Copyright (c) 2019-2020 Red Hat GmbH
   6  *
   7  * Author: Stefano Brivio <sbrivio@redhat.com>
   8  */
   9
  10 /**
  11  * DOC: Theory of Operation
  12  *
  13  *
  14  * Problem
  15  * -------
  16  *
  17  * Match packet bytes against entries composed of ranged or non-ranged packet
  18  * field specifiers, mapping them to arbitrary references. For example:
  19  *
  20  * ::
  21  *
  22  *               --- fields --->
  23  *      |    [net],[port],[net]... => [reference]
  24  *   entries [net],[port],[net]... => [reference]
  25  *      |    [net],[port],[net]... => [reference]
  26  *      V    ...
  27  *
  28  * where [net] fields can be IP ranges or netmasks, and [port] fields are port
  29  * ranges. Arbitrary packet fields can be matched.
  30  *
  31  *
  32  * Algorithm Overview
  33  * ------------------
  34  *
  35  * This algorithm is loosely inspired by [Ligatti 2010], and fundamentally
  36  * relies on the consideration that every contiguous range in a space of b bits
  37  * can be converted into b * 2 netmasks, from Theorem 3 in [Rottenstreich 2010],
  38  * as also illustrated in Section 9 of [Kogan 2014].
  39  *
  40  * Classification against a number of entries, that require matching given bits
  41  * of a packet field, is performed by grouping those bits in sets of arbitrary
  42  * size, and classifying packet bits one group at a time.
  43  *
  44  * Example:
  45  *   to match the source port (16 bits) of a packet, we can divide those 16 bits
  46  *   in 4 groups of 4 bits each. Given the entry:
  47  *      0000 0001 0101 1001
  48  *   and a packet with source port:
  49  *      0000 0001 1010 1001
  50  *   first and second groups match, but the third doesn't. We conclude that the
  51  *   packet doesn't match the given entry.
  52  *
  53  * Translate the set to a sequence of lookup tables, one per field. Each table
  54  * has two dimensions: bit groups to be matched for a single packet field, and
  55  * all the possible values of said groups (buckets). Input entries are
  56  * represented as one or more rules, depending on the number of composing
  57  * netmasks for the given field specifier, and a group match is indicated as a
  58  * set bit, with number corresponding to the rule index, in all the buckets
  59  * whose value matches the entry for a given group.
  60  *
  61  * Rules are mapped between fields through an array of x, n pairs, with each
  62  * item mapping a matched rule to one or more rules. The position of the pair in
  63  * the array indicates the matched rule to be mapped to the next field, x
  64  * indicates the first rule index in the next field, and n the amount of
  65  * next-field rules the current rule maps to.
  66  *
  67  * The mapping array for the last field maps to the desired references.
  68  *
  69  * To match, we perform table lookups using the values of grouped packet bits,
  70  * and use a sequence of bitwise operations to progressively evaluate rule
  71  * matching.
  72  *
  73  * A stand-alone, reference implementation, also including notes about possible
  74  * future optimisations, is available at:
  75  *    https://pipapo.lameexcu.se/
  76  *
  77  * Insertion
  78  * ---------
  79  *
  80  * - For each packet field:
  81  *
  82  *   - divide the b packet bits we want to classify into groups of size t,
  83  *     obtaining ceil(b / t) groups
  84  *
  85  *      Example: match on destination IP address, with t = 4: 32 bits, 8 groups
  86  *      of 4 bits each
  87  *
  88  *   - allocate a lookup table with one column ("bucket") for each possible
  89  *     value of a group, and with one row for each group
  90  *
  91  *      Example: 8 groups, 2^4 buckets:
  92  *
  93  * ::
  94  *
  95  *                     bucket
  96  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
  97  *        0
  98  *        1
  99  *        2
 100  *        3
 101  *        4
 102  *        5
 103  *        6
 104  *        7
 105  *
 106  *   - map the bits we want to classify for the current field, for a given
 107  *     entry, to a single rule for non-ranged and netmask set items, and to one
 108  *     or multiple rules for ranges. Ranges are expanded to composing netmasks
 109  *     by pipapo_expand().
 110  *
 111  *      Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048
 112  *      - rule #0: 10.0.0.5
 113  *      - rule #1: 192.168.1.0/24
 114  *      - rule #2: 192.168.2.0/31
 115  *
 116  *   - insert references to the rules in the lookup table, selecting buckets
 117  *     according to bit values of a rule in the given group. This is done by
 118  *     pipapo_insert().
 119  *
 120  *      Example: given:
 121  *      - rule #0: 10.0.0.5 mapping to buckets
 122  *        < 0 10  0 0   0 0  0 5 >
 123  *      - rule #1: 192.168.1.0/24 mapping to buckets
 124  *        < 12 0  10 8  0 1  < 0..15 > < 0..15 > >
 125  *      - rule #2: 192.168.2.0/31 mapping to buckets
 126  *        < 12 0  10 8  0 2  0 < 0..1 > >
 127  *
 128  *      these bits are set in the lookup table:
 129  *
 130  * ::
 131  *
 132  *                     bucket
 133  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 134  *        0    0                                              1,2
 135  *        1   1,2                                      0
 136  *        2    0                                      1,2
 137  *        3    0                              1,2
 138  *        4  0,1,2
 139  *        5    0   1   2
 140  *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 141  *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
 142  *
 143  *   - if this is not the last field in the set, fill a mapping array that maps
 144  *     rules from the lookup table to rules belonging to the same entry in
 145  *     the next lookup table, done by pipapo_map().
 146  *
 147  *     Note that as rules map to contiguous ranges of rules, given how netmask
 148  *     expansion and insertion is performed, &union nft_pipapo_map_bucket stores
 149  *     this information as pairs of first rule index, rule count.
 150  *
 151  *      Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048,
 152  *      given lookup table #0 for field 0 (see example above):
 153  *
 154  * ::
 155  *
 156  *                     bucket
 157  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 158  *        0    0                                              1,2
 159  *        1   1,2                                      0
 160  *        2    0                                      1,2
 161  *        3    0                              1,2
 162  *        4  0,1,2
 163  *        5    0   1   2
 164  *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 165  *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
 166  *
 167  *      and lookup table #1 for field 1 with:
 168  *      - rule #0: 1024 mapping to buckets
 169  *        < 0  0  4  0 >
 170  *      - rule #1: 2048 mapping to buckets
 171  *        < 0  0  5  0 >
 172  *
 173  * ::
 174  *
 175  *                     bucket
 176  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 177  *        0   0,1
 178  *        1   0,1
 179  *        2                    0   1
 180  *        3   0,1
 181  *
 182  *      we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024
 183  *      in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1
 184  *      (rules #1, #2) to 2048 in lookup table #2 (rule #1):
 185  *
 186  * ::
 187  *
 188  *       rule indices in current field: 0    1    2
 189  *       map to rules in next field:    0    1    1
 190  *
 191  *   - if this is the last field in the set, fill a mapping array that maps
 192  *     rules from the last lookup table to element pointers, also done by
 193  *     pipapo_map().
 194  *
 195  *     Note that, in this implementation, we have two elements (start, end) for
 196  *     each entry. The pointer to the end element is stored in this array, and
 197  *     the pointer to the start element is linked from it.
 198  *
 199  *      Example: entry 10.0.0.5:1024 has a corresponding &struct nft_pipapo_elem
 200  *      pointer, 0x66, and element for 192.168.1.0-192.168.2.1:2048 is at 0x42.
 201  *      From the rules of lookup table #1 as mapped above:
 202  *
 203  * ::
 204  *
 205  *       rule indices in last field:    0    1
 206  *       map to elements:             0x66  0x42
 207  *
 208  *
 209  * Matching
 210  * --------
 211  *
 212  * We use a result bitmap, with the size of a single lookup table bucket, to
 213  * represent the matching state that applies at every algorithm step. This is
 214  * done by pipapo_lookup().
 215  *
 216  * - For each packet field:
 217  *
 218  *   - start with an all-ones result bitmap (res_map in pipapo_lookup())
 219  *
 220  *   - perform a lookup into the table corresponding to the current field,
 221  *     for each group, and at every group, AND the current result bitmap with
 222  *     the value from the lookup table bucket
 223  *
 224  * ::
 225  *
 226  *      Example: 192.168.1.5 < 12 0  10 8  0 1  0 5 >, with lookup table from
 227  *      insertion examples.
 228  *      Lookup table buckets are at least 3 bits wide, we'll assume 8 bits for
 229  *      convenience in this example. Initial result bitmap is 0xff, the steps
 230  *      below show the value of the result bitmap after each group is processed:
 231  *
 232  *                     bucket
 233  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 234  *        0    0                                              1,2
 235  *        result bitmap is now: 0xff & 0x6 [bucket 12] = 0x6
 236  *
 237  *        1   1,2                                      0
 238  *        result bitmap is now: 0x6 & 0x6 [bucket 0] = 0x6
 239  *
 240  *        2    0                                      1,2
 241  *        result bitmap is now: 0x6 & 0x6 [bucket 10] = 0x6
 242  *
 243  *        3    0                              1,2
 244  *        result bitmap is now: 0x6 & 0x6 [bucket 8] = 0x6
 245  *
 246  *        4  0,1,2
 247  *        result bitmap is now: 0x6 & 0x7 [bucket 0] = 0x6
 248  *
 249  *        5    0   1   2
 250  *        result bitmap is now: 0x6 & 0x2 [bucket 1] = 0x2
 251  *
 252  *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 253  *        result bitmap is now: 0x2 & 0x7 [bucket 0] = 0x2
 254  *
 255  *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
 256  *        final result bitmap for this field is: 0x2 & 0x3 [bucket 5] = 0x2
 257  *
 258  *   - at the next field, start with a new, all-zeroes result bitmap. For each
 259  *     bit set in the previous result bitmap, fill the new result bitmap
 260  *     (fill_map in pipapo_lookup()) with the rule indices from the
 261  *     corresponding buckets of the mapping field for this field, done by
 262  *     pipapo_refill()
 263  *
 264  *      Example: with mapping table from insertion examples, with the current
 265  *      result bitmap from the previous example, 0x02:
 266  *
 267  * ::
 268  *
 269  *       rule indices in current field: 0    1    2
 270  *       map to rules in next field:    0    1    1
 271  *
 272  *      the new result bitmap will be 0x02: rule 1 was set, and rule 1 will be
 273  *      set.
 274  *
 275  *      We can now extend this example to cover the second iteration of the step
 276  *      above (lookup and AND bitmap): assuming the port field is
 277  *      2048 < 0  0  5  0 >, with starting result bitmap 0x2, and lookup table
 278  *      for "port" field from pre-computation example:
 279  *
 280  * ::
 281  *
 282  *                     bucket
 283  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 284  *        0   0,1
 285  *        1   0,1
 286  *        2                    0   1
 287  *        3   0,1
 288  *
 289  *       operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5]
 290  *       & 0x3 [bucket 0], resulting bitmap is 0x2.
 291  *
 292  *   - if this is the last field in the set, look up the value from the mapping
 293  *     array corresponding to the final result bitmap
 294  *
 295  *      Example: 0x2 resulting bitmap from 192.168.1.5:2048, mapping array for
 296  *      last field from insertion example:
 297  *
 298  * ::
 299  *
 300  *       rule indices in last field:    0    1
 301  *       map to elements:             0x66  0x42
 302  *
 303  *      the matching element is at 0x42.
 304  *
 305  *
 306  * References
 307  * ----------
 308  *
 309  * [Ligatti 2010]
 310  *      A Packet-classification Algorithm for Arbitrary Bitmask Rules, with
 311  *      Automatic Time-space Tradeoffs
 312  *      Jay Ligatti, Josh Kuhn, and Chris Gage.
 313  *      Proceedings of the IEEE International Conference on Computer
 314  *      Communication Networks (ICCCN), August 2010.
 315  *      http://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf
 316  *
 317  * [Rottenstreich 2010]
 318  *      Worst-Case TCAM Rule Expansion
 319  *      Ori Rottenstreich and Isaac Keslassy.
 320  *      2010 Proceedings IEEE INFOCOM, San Diego, CA, 2010.
 321  *      http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.212.4592&rep=rep1&type=pdf
 322  *
 323  * [Kogan 2014]
 324  *      SAX-PAC (Scalable And eXpressive PAcket Classification)
 325  *      Kirill Kogan, Sergey Nikolenko, Ori Rottenstreich, William Culhane,
 326  *      and Patrick Eugster.
 327  *      Proceedings of the 2014 ACM conference on SIGCOMM, August 2014.
 328  *      http://www.sigcomm.org/sites/default/files/ccr/papers/2014/August/2619239-2626294.pdf
 329  */
 330
 331 #include <linux/kernel.h>
 332 #include <linux/init.h>
 333 #include <linux/log2.h>
 334 #include <linux/module.h>
 335 #include <linux/netlink.h>
 336 #include <linux/netfilter.h>
 337 #include <linux/netfilter/nf_tables.h>
 338 #include <net/netfilter/nf_tables_core.h>
 339 #include <uapi/linux/netfilter/nf_tables.h>
 340 #include <net/ipv6.h>                   /* For the maximum length of a field */
 341 #include <linux/bitmap.h>
 342 #include <linux/bitops.h>
 343
 344 /* Count of concatenated fields depends on count of 32-bit nftables registers */
 345 #define NFT_PIPAPO_MAX_FIELDS           NFT_REG32_COUNT
 346
 347 /* Largest supported field size */
 348 #define NFT_PIPAPO_MAX_BYTES            (sizeof(struct in6_addr))
 349 #define NFT_PIPAPO_MAX_BITS             (NFT_PIPAPO_MAX_BYTES * BITS_PER_BYTE)
 350
 351 /* Number of bits to be grouped together in lookup table buckets, arbitrary */
 352 #define NFT_PIPAPO_GROUP_BITS           4
 353 #define NFT_PIPAPO_GROUPS_PER_BYTE      (BITS_PER_BYTE / NFT_PIPAPO_GROUP_BITS)
 354
 355 /* Fields are padded to 32 bits in input registers */
 356 #define NFT_PIPAPO_GROUPS_PADDED_SIZE(x)                                \
 357         (round_up((x) / NFT_PIPAPO_GROUPS_PER_BYTE, sizeof(u32)))
 358 #define NFT_PIPAPO_GROUPS_PADDING(x)                                    \
 359         (NFT_PIPAPO_GROUPS_PADDED_SIZE((x)) - (x) / NFT_PIPAPO_GROUPS_PER_BYTE)
 360
 361 /* Number of buckets, given by 2 ^ n, with n grouped bits */
 362 #define NFT_PIPAPO_BUCKETS              (1 << NFT_PIPAPO_GROUP_BITS)
 363
 364 /* Each n-bit range maps to up to n * 2 rules */
 365 #define NFT_PIPAPO_MAP_NBITS            (const_ilog2(NFT_PIPAPO_MAX_BITS * 2))
 366
 367 /* Use the rest of mapping table buckets for rule indices, but it makes no sense
 368  * to exceed 32 bits
 369  */
 370 #if BITS_PER_LONG == 64
 371 #define NFT_PIPAPO_MAP_TOBITS           32
 372 #else
 373 #define NFT_PIPAPO_MAP_TOBITS           (BITS_PER_LONG - NFT_PIPAPO_MAP_NBITS)
 374 #endif
 375
 376 /* ...which gives us the highest allowed index for a rule */
 377 #define NFT_PIPAPO_RULE0_MAX            ((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
 378                                         - (1UL << NFT_PIPAPO_MAP_NBITS))
 379
 380 #define nft_pipapo_for_each_field(field, index, match)          \
 381         for ((field) = (match)->f, (index) = 0;                 \
 382              (index) < (match)->field_count;                    \
 383              (index)++, (field)++)
 384
 385 /**
 386  * union nft_pipapo_map_bucket - Bucket of mapping table
 387  * @to:         First rule number (in next field) this rule maps to
 388  * @n:          Number of rules (in next field) this rule maps to
 389  * @e:          If there's no next field, pointer to element this rule maps to
 390  */
 391 union nft_pipapo_map_bucket {
 392         struct {
 393 #if BITS_PER_LONG == 64
 394                 static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
 395                 u32 to;
 396
 397                 static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
 398                 u32 n;
 399 #else
 400                 unsigned long to:NFT_PIPAPO_MAP_TOBITS;
 401                 unsigned long  n:NFT_PIPAPO_MAP_NBITS;
 402 #endif
 403         };
 404         struct nft_pipapo_elem *e;
 405 };
 406
 407 /**
 408  * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
 409  * @groups:     Amount of 4-bit groups
 410  * @rules:      Number of inserted rules
 411  * @bsize:      Size of each bucket in lookup table, in longs
 412  * @lt:         Lookup table: 'groups' rows of NFT_PIPAPO_BUCKETS buckets
 413  * @mt:         Mapping table: one bucket per rule
 414  */
 415 struct nft_pipapo_field {
 416         int groups;
 417         unsigned long rules;
 418         size_t bsize;
 419         unsigned long *lt;
 420         union nft_pipapo_map_bucket *mt;
 421 };
 422
 423 /**
 424  * struct nft_pipapo_match - Data used for lookup and matching
 425  * @field_count         Amount of fields in set
 426  * @scratch:            Preallocated per-CPU maps for partial matching results
 427  * @bsize_max:          Maximum lookup table bucket size of all fields, in longs
 428  * @rcu                 Matching data is swapped on commits
 429  * @f:                  Fields, with lookup and mapping tables
 430  */
 431 struct nft_pipapo_match {
 432         int field_count;
 433         unsigned long * __percpu *scratch;
 434         size_t bsize_max;
 435         struct rcu_head rcu;
 436         struct nft_pipapo_field f[0];
 437 };
 438
 439 /* Current working bitmap index, toggled between field matches */
 440 static DEFINE_PER_CPU(bool, nft_pipapo_scratch_index);
 441
 442 /**
 443  * struct nft_pipapo - Representation of a set
 444  * @match:      Currently in-use matching data
 445  * @clone:      Copy where pending insertions and deletions are kept
 446  * @groups:     Total amount of 4-bit groups for fields in this set
 447  * @width:      Total bytes to be matched for one packet, including padding
 448  * @dirty:      Working copy has pending insertions or deletions
 449  * @last_gc:    Timestamp of last garbage collection run, jiffies
 450  */
 451 struct nft_pipapo {
 452         struct nft_pipapo_match __rcu *match;
 453         struct nft_pipapo_match *clone;
 454         int groups;
 455         int width;
 456         bool dirty;
 457         unsigned long last_gc;
 458 };
 459
 460 struct nft_pipapo_elem;
 461
 462 /**
 463  * struct nft_pipapo_elem - API-facing representation of single set element
 464  * @ext:        nftables API extensions
 465  */
 466 struct nft_pipapo_elem {
 467         struct nft_set_ext ext;
 468 };
 469
 470 /**
 471  * pipapo_refill() - For each set bit, set bits from selected mapping table item
 472  * @map:        Bitmap to be scanned for set bits
 473  * @len:        Length of bitmap in longs
 474  * @rules:      Number of rules in field
 475  * @dst:        Destination bitmap
 476  * @mt:         Mapping table containing bit set specifiers
 477  * @match_only: Find a single bit and return, don't fill
 478  *
 479  * Iteration over set bits with __builtin_ctzl(): Daniel Lemire, public domain.
 480  *
 481  * For each bit set in map, select the bucket from mapping table with index
 482  * corresponding to the position of the bit set. Use start bit and amount of
 483  * bits specified in bucket to fill region in dst.
 484  *
 485  * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
 486  */
 487 static int pipapo_refill(unsigned long *map, int len, int rules,
 488                          unsigned long *dst, union nft_pipapo_map_bucket *mt,
 489                          bool match_only)
 490 {
 491         unsigned long bitset;
 492         int k, ret = -1;
 493
 494         for (k = 0; k < len; k++) {
 495                 bitset = map[k];
 496                 while (bitset) {
 497                         unsigned long t = bitset & -bitset;
 498                         int r = __builtin_ctzl(bitset);
 499                         int i = k * BITS_PER_LONG + r;
 500
 501                         if (unlikely(i >= rules)) {
 502                                 map[k] = 0;
 503                                 return -1;
 504                         }
 505
 506                         if (match_only) {
 507                                 bitmap_clear(map, i, 1);
 508                                 return i;
 509                         }
 510
 511                         ret = 0;
 512
 513                         bitmap_set(dst, mt[i].to, mt[i].n);
 514
 515                         bitset ^= t;
 516                 }
 517                 map[k] = 0;
 518         }
 519
 520         return ret;
 521 }
 522
 523 /**
 524  * nft_pipapo_lookup() - Lookup function
 525  * @net:        Network namespace
 526  * @set:        nftables API set representation
 527  * @elem:       nftables API element representation containing key data
 528  * @ext:        nftables API extension pointer, filled with matching reference
 529  *
 530  * For more details, see DOC: Theory of Operation.
 531  *
 532  * Return: true on match, false otherwise.
 533  */
 534 static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
 535                               const u32 *key, const struct nft_set_ext **ext)
 536 {
 537         struct nft_pipapo *priv = nft_set_priv(set);
 538         unsigned long *res_map, *fill_map;
 539         u8 genmask = nft_genmask_cur(net);
 540         const u8 *rp = (const u8 *)key;
 541         struct nft_pipapo_match *m;
 542         struct nft_pipapo_field *f;
 543         bool map_index;
 544         int i;
 545
 546         local_bh_disable();
 547
 548         map_index = raw_cpu_read(nft_pipapo_scratch_index);
 549
 550         m = rcu_dereference(priv->match);
 551
 552         if (unlikely(!m || !*raw_cpu_ptr(m->scratch)))
 553                 goto out;
 554
 555         res_map  = *raw_cpu_ptr(m->scratch) + (map_index ? m->bsize_max : 0);
 556         fill_map = *raw_cpu_ptr(m->scratch) + (map_index ? 0 : m->bsize_max);
 557
 558         memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
 559
 560         nft_pipapo_for_each_field(f, i, m) {
 561                 bool last = i == m->field_count - 1;
 562                 unsigned long *lt = f->lt;
 563                 int b, group;
 564
 565                 /* For each 4-bit group: select lookup table bucket depending on
 566                  * packet bytes value, then AND bucket value
 567                  */
 568                 for (group = 0; group < f->groups; group += 2) {
 569                         u8 v;
 570
 571                         v = *rp >> 4;
 572                         __bitmap_and(res_map, res_map, lt + v * f->bsize,
 573                                      f->bsize * BITS_PER_LONG);
 574                         lt += f->bsize * NFT_PIPAPO_BUCKETS;
 575
 576                         v = *rp & 0x0f;
 577                         rp++;
 578                         __bitmap_and(res_map, res_map, lt + v * f->bsize,
 579                                      f->bsize * BITS_PER_LONG);
 580                         lt += f->bsize * NFT_PIPAPO_BUCKETS;
 581                 }
 582
 583                 /* Now populate the bitmap for the next field, unless this is
 584                  * the last field, in which case return the matched 'ext'
 585                  * pointer if any.
 586                  *
 587                  * Now res_map contains the matching bitmap, and fill_map is the
 588                  * bitmap for the next field.
 589                  */
 590 next_match:
 591                 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
 592                                   last);
 593                 if (b < 0) {
 594                         raw_cpu_write(nft_pipapo_scratch_index, map_index);
 595                         local_bh_enable();
 596
 597                         return false;
 598                 }
 599
 600                 if (last) {
 601                         *ext = &f->mt[b].e->ext;
 602                         if (unlikely(nft_set_elem_expired(*ext) ||
 603                                      !nft_set_elem_active(*ext, genmask)))
 604                                 goto next_match;
 605
 606                         /* Last field: we're just returning the key without
 607                          * filling the initial bitmap for the next field, so the
 608                          * current inactive bitmap is clean and can be reused as
 609                          * *next* bitmap (not initial) for the next packet.
 610                          */
 611                         raw_cpu_write(nft_pipapo_scratch_index, map_index);
 612                         local_bh_enable();
 613
 614                         return true;
 615                 }
 616
 617                 /* Swap bitmap indices: res_map is the initial bitmap for the
 618                  * next field, and fill_map is guaranteed to be all-zeroes at
 619                  * this point.
 620                  */
 621                 map_index = !map_index;
 622                 swap(res_map, fill_map);
 623
 624                 rp += NFT_PIPAPO_GROUPS_PADDING(f->groups);
 625         }
 626
 627 out:
 628         local_bh_enable();
 629         return false;
 630 }
 631
 632 /**
 633  * pipapo_get() - Get matching element reference given key data
 634  * @net:        Network namespace
 635  * @set:        nftables API set representation
 636  * @data:       Key data to be matched against existing elements
 637  * @genmask:    If set, check that element is active in given genmask
 638  *
 639  * This is essentially the same as the lookup function, except that it matches
 640  * key data against the uncommitted copy and doesn't use preallocated maps for
 641  * bitmap results.
 642  *
 643  * Return: pointer to &struct nft_pipapo_elem on match, error pointer otherwise.
 644  */
 645 static struct nft_pipapo_elem *pipapo_get(const struct net *net,
 646                                           const struct nft_set *set,
 647                                           const u8 *data, u8 genmask)
 648 {
 649         struct nft_pipapo_elem *ret = ERR_PTR(-ENOENT);
 650         struct nft_pipapo *priv = nft_set_priv(set);
 651         struct nft_pipapo_match *m = priv->clone;
 652         unsigned long *res_map, *fill_map = NULL;
 653         struct nft_pipapo_field *f;
 654         int i;
 655
 656         res_map = kmalloc_array(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
 657         if (!res_map) {
 658                 ret = ERR_PTR(-ENOMEM);
 659                 goto out;
 660         }
 661
 662         fill_map = kcalloc(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
 663         if (!fill_map) {
 664                 ret = ERR_PTR(-ENOMEM);
 665                 goto out;
 666         }
 667
 668         memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
 669
 670         nft_pipapo_for_each_field(f, i, m) {
 671                 bool last = i == m->field_count - 1;
 672                 unsigned long *lt = f->lt;
 673                 int b, group;
 674
 675                 /* For each 4-bit group: select lookup table bucket depending on
 676                  * packet bytes value, then AND bucket value
 677                  */
 678                 for (group = 0; group < f->groups; group++) {
 679                         u8 v;
 680
 681                         if (group % 2) {
 682                                 v = *data & 0x0f;
 683                                 data++;
 684                         } else {
 685                                 v = *data >> 4;
 686                         }
 687                         __bitmap_and(res_map, res_map, lt + v * f->bsize,
 688                                      f->bsize * BITS_PER_LONG);
 689
 690                         lt += f->bsize * NFT_PIPAPO_BUCKETS;
 691                 }
 692
 693                 /* Now populate the bitmap for the next field, unless this is
 694                  * the last field, in which case return the matched 'ext'
 695                  * pointer if any.
 696                  *
 697                  * Now res_map contains the matching bitmap, and fill_map is the
 698                  * bitmap for the next field.
 699                  */
 700 next_match:
 701                 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
 702                                   last);
 703                 if (b < 0)
 704                         goto out;
 705
 706                 if (last) {
 707                         if (nft_set_elem_expired(&f->mt[b].e->ext) ||
 708                             (genmask &&
 709                              !nft_set_elem_active(&f->mt[b].e->ext, genmask)))
 710                                 goto next_match;
 711
 712                         ret = f->mt[b].e;
 713                         goto out;
 714                 }
 715
 716                 data += NFT_PIPAPO_GROUPS_PADDING(f->groups);
 717
 718                 /* Swap bitmap indices: fill_map will be the initial bitmap for
 719                  * the next field (i.e. the new res_map), and res_map is
 720                  * guaranteed to be all-zeroes at this point, ready to be filled
 721                  * according to the next mapping table.
 722                  */
 723                 swap(res_map, fill_map);
 724         }
 725
 726 out:
 727         kfree(fill_map);
 728         kfree(res_map);
 729         return ret;
 730 }
 731
 732 /**
 733  * nft_pipapo_get() - Get matching element reference given key data
 734  * @net:        Network namespace
 735  * @set:        nftables API set representation
 736  * @elem:       nftables API element representation containing key data
 737  * @flags:      Unused
 738  */
 739 void *nft_pipapo_get(const struct net *net, const struct nft_set *set,
 740                      const struct nft_set_elem *elem, unsigned int flags)
 741 {
 742         return pipapo_get(net, set, (const u8 *)elem->key.val.data,
 743                           nft_genmask_cur(net));
 744 }
 745
 746 /**
 747  * pipapo_resize() - Resize lookup or mapping table, or both
 748  * @f:          Field containing lookup and mapping tables
 749  * @old_rules:  Previous amount of rules in field
 750  * @rules:      New amount of rules
 751  *
 752  * Increase, decrease or maintain tables size depending on new amount of rules,
 753  * and copy data over. In case the new size is smaller, throw away data for
 754  * highest-numbered rules.
 755  *
 756  * Return: 0 on success, -ENOMEM on allocation failure.
 757  */
 758 static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
 759 {
 760         long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
 761         union nft_pipapo_map_bucket *new_mt, *old_mt = f->mt;
 762         size_t new_bucket_size, copy;
 763         int group, bucket;
 764
 765         new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);
 766
 767         if (new_bucket_size == f->bsize)
 768                 goto mt;
 769
 770         if (new_bucket_size > f->bsize)
 771                 copy = f->bsize;
 772         else
 773                 copy = new_bucket_size;
 774
 775         new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS * new_bucket_size *
 776                           sizeof(*new_lt), GFP_KERNEL);
 777         if (!new_lt)
 778                 return -ENOMEM;
 779
 780         new_p = new_lt;
 781         old_p = old_lt;
 782         for (group = 0; group < f->groups; group++) {
 783                 for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS; bucket++) {
 784                         memcpy(new_p, old_p, copy * sizeof(*new_p));
 785                         new_p += copy;
 786                         old_p += copy;
 787
 788                         if (new_bucket_size > f->bsize)
 789                                 new_p += new_bucket_size - f->bsize;
 790                         else
 791                                 old_p += f->bsize - new_bucket_size;
 792                 }
 793         }
 794
 795 mt:
 796         new_mt = kvmalloc(rules * sizeof(*new_mt), GFP_KERNEL);
 797         if (!new_mt) {
 798                 kvfree(new_lt);
 799                 return -ENOMEM;
 800         }
 801
 802         memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt));
 803         if (rules > old_rules) {
 804                 memset(new_mt + old_rules, 0,
 805                        (rules - old_rules) * sizeof(*new_mt));
 806         }
 807
 808         if (new_lt) {
 809                 f->bsize = new_bucket_size;
 810                 f->lt = new_lt;
 811                 kvfree(old_lt);
 812         }
 813
 814         f->mt = new_mt;
 815         kvfree(old_mt);
 816
 817         return 0;
 818 }
 819
 820 /**
 821  * pipapo_bucket_set() - Set rule bit in bucket given group and group value
 822  * @f:          Field containing lookup table
 823  * @rule:       Rule index
 824  * @group:      Group index
 825  * @v:          Value of bit group
 826  */
 827 static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
 828                               int v)
 829 {
 830         unsigned long *pos;
 831
 832         pos = f->lt + f->bsize * NFT_PIPAPO_BUCKETS * group;
 833         pos += f->bsize * v;
 834
 835         __set_bit(rule, pos);
 836 }
 837
 838 /**
 839  * pipapo_insert() - Insert new rule in field given input key and mask length
 840  * @f:          Field containing lookup table
 841  * @k:          Input key for classification, without nftables padding
 842  * @mask_bits:  Length of mask; matches field length for non-ranged entry
 843  *
 844  * Insert a new rule reference in lookup buckets corresponding to k and
 845  * mask_bits.
 846  *
 847  * Return: 1 on success (one rule inserted), negative error code on failure.
 848  */
 849 static int pipapo_insert(struct nft_pipapo_field *f, const uint8_t *k,
 850                          int mask_bits)
 851 {
 852         int rule = f->rules++, group, ret;
 853
 854         ret = pipapo_resize(f, f->rules - 1, f->rules);
 855         if (ret)
 856                 return ret;
 857
 858         for (group = 0; group < f->groups; group++) {
 859                 int i, v;
 860                 u8 mask;
 861
 862                 if (group % 2)
 863                         v = k[group / 2] & 0x0f;
 864                 else
 865                         v = k[group / 2] >> 4;
 866
 867                 if (mask_bits >= (group + 1) * 4) {
 868                         /* Not masked */
 869                         pipapo_bucket_set(f, rule, group, v);
 870                 } else if (mask_bits <= group * 4) {
 871                         /* Completely masked */
 872                         for (i = 0; i < NFT_PIPAPO_BUCKETS; i++)
 873                                 pipapo_bucket_set(f, rule, group, i);
 874                 } else {
 875                         /* The mask limit falls on this group */
 876                         mask = 0x0f >> (mask_bits - group * 4);
 877                         for (i = 0; i < NFT_PIPAPO_BUCKETS; i++) {
 878                                 if ((i & ~mask) == (v & ~mask))
 879                                         pipapo_bucket_set(f, rule, group, i);
 880                         }
 881                 }
 882         }
 883
 884         return 1;
 885 }
 886
 887 /**
 888  * pipapo_step_diff() - Check if setting @step bit in netmask would change it
 889  * @base:       Mask we are expanding
 890  * @step:       Step bit for given expansion step
 891  * @len:        Total length of mask space (set and unset bits), bytes
 892  *
 893  * Convenience function for mask expansion.
 894  *
 895  * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
 896  */
 897 static bool pipapo_step_diff(u8 *base, int step, int len)
 898 {
 899         /* Network order, byte-addressed */
 900 #ifdef __BIG_ENDIAN__
 901         return !(BIT(step % BITS_PER_BYTE) & base[step / BITS_PER_BYTE]);
 902 #else
 903         return !(BIT(step % BITS_PER_BYTE) &
 904                  base[len - 1 - step / BITS_PER_BYTE]);
 905 #endif
 906 }
 907
 908 /**
 909  * pipapo_step_after_end() - Check if mask exceeds range end with given step
 910  * @base:       Mask we are expanding
 911  * @end:        End of range
 912  * @step:       Step bit for given expansion step, highest bit to be set
 913  * @len:        Total length of mask space (set and unset bits), bytes
 914  *
 915  * Convenience function for mask expansion.
 916  *
 917  * Return: true if mask exceeds range setting step bits, false otherwise.
 918  */
 919 static bool pipapo_step_after_end(const u8 *base, const u8 *end, int step,
 920                                   int len)
 921 {
 922         u8 tmp[NFT_PIPAPO_MAX_BYTES];
 923         int i;
 924
 925         memcpy(tmp, base, len);
 926
 927         /* Network order, byte-addressed */
 928         for (i = 0; i <= step; i++)
 929 #ifdef __BIG_ENDIAN__
 930                 tmp[i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
 931 #else
 932                 tmp[len - 1 - i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
 933 #endif
 934
 935         return memcmp(tmp, end, len) > 0;
 936 }
 937
 938 /**
 939  * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
 940  * @base:       Netmask base
 941  * @step:       Step bit to sum
 942  * @len:        Netmask length, bytes
 943  */
 944 static void pipapo_base_sum(u8 *base, int step, int len)
 945 {
 946         bool carry = false;
 947         int i;
 948
 949         /* Network order, byte-addressed */
 950 #ifdef __BIG_ENDIAN__
 951         for (i = step / BITS_PER_BYTE; i < len; i++) {
 952 #else
 953         for (i = len - 1 - step / BITS_PER_BYTE; i >= 0; i--) {
 954 #endif
 955                 if (carry)
 956                         base[i]++;
 957                 else
 958                         base[i] += 1 << (step % BITS_PER_BYTE);
 959
 960                 if (base[i])
 961                         break;
 962
 963                 carry = true;
 964         }
 965 }
 966
 967 /**
 968  * pipapo_expand() - Expand to composing netmasks, insert into lookup table
 969  * @f:          Field containing lookup table
 970  * @start:      Start of range
 971  * @end:        End of range
 972  * @len:        Length of value in bits
 973  *
 974  * Expand range to composing netmasks and insert corresponding rule references
 975  * in lookup buckets.
 976  *
 977  * Return: number of inserted rules on success, negative error code on failure.
 978  */
 979 static int pipapo_expand(struct nft_pipapo_field *f,
 980                          const u8 *start, const u8 *end, int len)
 981 {
 982         int step, masks = 0, bytes = DIV_ROUND_UP(len, BITS_PER_BYTE);
 983         u8 base[NFT_PIPAPO_MAX_BYTES];
 984
 985         memcpy(base, start, bytes);
 986         while (memcmp(base, end, bytes) <= 0) {
 987                 int err;
 988
 989                 step = 0;
 990                 while (pipapo_step_diff(base, step, bytes)) {
 991                         if (pipapo_step_after_end(base, end, step, bytes))
 992                                 break;
 993
 994                         step++;
 995                         if (step >= len) {
 996                                 if (!masks) {
 997                                         pipapo_insert(f, base, 0);
 998                                         masks = 1;
 999                                 }
1000                                 goto out;
1001                         }
1002                 }
1003
1004                 err = pipapo_insert(f, base, len - step);
1005
1006                 if (err < 0)
1007                         return err;
1008
1009                 masks++;
1010                 pipapo_base_sum(base, step, bytes);
1011         }
1012 out:
1013         return masks;
1014 }
1015
1016 /**
1017  * pipapo_map() - Insert rules in mapping tables, mapping them between fields
1018  * @m:          Matching data, including mapping table
1019  * @map:        Table of rule maps: array of first rule and amount of rules
1020  *              in next field a given rule maps to, for each field
1021  * @ext:        For last field, nft_set_ext pointer matching rules map to
1022  */
1023 static void pipapo_map(struct nft_pipapo_match *m,
1024                        union nft_pipapo_map_bucket map[NFT_PIPAPO_MAX_FIELDS],
1025                        struct nft_pipapo_elem *e)
1026 {
1027         struct nft_pipapo_field *f;
1028         int i, j;
1029
1030         for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) {
1031                 for (j = 0; j < map[i].n; j++) {
1032                         f->mt[map[i].to + j].to = map[i + 1].to;
1033                         f->mt[map[i].to + j].n = map[i + 1].n;
1034                 }
1035         }
1036
1037         /* Last field: map to ext instead of mapping to next field */
1038         for (j = 0; j < map[i].n; j++)
1039                 f->mt[map[i].to + j].e = e;
1040 }
1041
1042 /**
1043  * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
1044  * @clone:      Copy of matching data with pending insertions and deletions
1045  * @bsize_max   Maximum bucket size, scratch maps cover two buckets
1046  *
1047  * Return: 0 on success, -ENOMEM on failure.
1048  */
1049 static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
1050                                   unsigned long bsize_max)
1051 {
1052         int i;
1053
1054         for_each_possible_cpu(i) {
1055                 unsigned long *scratch;
1056
1057                 scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2,
1058                                        GFP_KERNEL, cpu_to_node(i));
1059                 if (!scratch) {
1060                         /* On failure, there's no need to undo previous
1061                          * allocations: this means that some scratch maps have
1062                          * a bigger allocated size now (this is only called on
1063                          * insertion), but the extra space won't be used by any
1064                          * CPU as new elements are not inserted and m->bsize_max
1065                          * is not updated.
1066                          */
1067                         return -ENOMEM;
1068                 }
1069
1070                 kfree(*per_cpu_ptr(clone->scratch, i));
1071
1072                 *per_cpu_ptr(clone->scratch, i) = scratch;
1073         }
1074
1075         return 0;
1076 }
1077
1078 /**
1079  * nft_pipapo_insert() - Validate and insert ranged elements
1080  * @net:        Network namespace
1081  * @set:        nftables API set representation
1082  * @elem:       nftables API element representation containing key data
1083  * @ext2:       Filled with pointer to &struct nft_set_ext in inserted element
1084  *
1085  * Return: 0 on success, error pointer on failure.
1086  */
1087 static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,
1088                              const struct nft_set_elem *elem,
1089                              struct nft_set_ext **ext2)
1090 {
1091         const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1092         union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1093         const u8 *start = (const u8 *)elem->key.val.data, *end;
1094         struct nft_pipapo_elem *e = elem->priv, *dup;
1095         struct nft_pipapo *priv = nft_set_priv(set);
1096         struct nft_pipapo_match *m = priv->clone;
1097         u8 genmask = nft_genmask_next(net);
1098         struct nft_pipapo_field *f;
1099         int i, bsize_max, err = 0;
1100
1101         dup = pipapo_get(net, set, start, genmask);
1102         if (PTR_ERR(dup) == -ENOENT) {
1103                 if (nft_set_ext_exists(ext, NFT_SET_EXT_KEY_END)) {
1104                         end = (const u8 *)nft_set_ext_key_end(ext)->data;
1105                         dup = pipapo_get(net, set, end, nft_genmask_next(net));
1106                 } else {
1107                         end = start;
1108                 }
1109         }
1110
1111         if (PTR_ERR(dup) != -ENOENT) {
1112                 if (IS_ERR(dup))
1113                         return PTR_ERR(dup);
1114                 *ext2 = &dup->ext;
1115                 return -EEXIST;
1116         }
1117
1118         /* Validate */
1119         nft_pipapo_for_each_field(f, i, m) {
1120                 const u8 *start_p = start, *end_p = end;
1121
1122                 if (f->rules >= (unsigned long)NFT_PIPAPO_RULE0_MAX)
1123                         return -ENOSPC;
1124
1125                 if (memcmp(start_p, end_p,
1126                            f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) > 0)
1127                         return -EINVAL;
1128
1129                 start_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1130                 end_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1131         }
1132
1133         /* Insert */
1134         priv->dirty = true;
1135
1136         bsize_max = m->bsize_max;
1137
1138         nft_pipapo_for_each_field(f, i, m) {
1139                 int ret;
1140
1141                 rulemap[i].to = f->rules;
1142
1143                 ret = memcmp(start, end,
1144                              f->groups / NFT_PIPAPO_GROUPS_PER_BYTE);
1145                 if (!ret) {
1146                         ret = pipapo_insert(f, start,
1147                                             f->groups * NFT_PIPAPO_GROUP_BITS);
1148                 } else {
1149                         ret = pipapo_expand(f, start, end,
1150                                             f->groups * NFT_PIPAPO_GROUP_BITS);
1151                 }
1152
1153                 if (f->bsize > bsize_max)
1154                         bsize_max = f->bsize;
1155
1156                 rulemap[i].n = ret;
1157
1158                 start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1159                 end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1160         }
1161
1162         if (!*this_cpu_ptr(m->scratch) || bsize_max > m->bsize_max) {
1163                 err = pipapo_realloc_scratch(m, bsize_max);
1164                 if (err)
1165                         return err;
1166
1167                 this_cpu_write(nft_pipapo_scratch_index, false);
1168
1169                 m->bsize_max = bsize_max;
1170         }
1171
1172         *ext2 = &e->ext;
1173
1174         pipapo_map(m, rulemap, e);
1175
1176         return 0;
1177 }
1178
1179 /**
1180  * pipapo_clone() - Clone matching data to create new working copy
1181  * @old:        Existing matching data
1182  *
1183  * Return: copy of matching data passed as 'old', error pointer on failure
1184  */
1185 static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
1186 {
1187         struct nft_pipapo_field *dst, *src;
1188         struct nft_pipapo_match *new;
1189         int i;
1190
1191         new = kmalloc(sizeof(*new) + sizeof(*dst) * old->field_count,
1192                       GFP_KERNEL);
1193         if (!new)
1194                 return ERR_PTR(-ENOMEM);
1195
1196         new->field_count = old->field_count;
1197         new->bsize_max = old->bsize_max;
1198
1199         new->scratch = alloc_percpu(*new->scratch);
1200         if (!new->scratch)
1201                 goto out_scratch;
1202
1203         rcu_head_init(&new->rcu);
1204
1205         src = old->f;
1206         dst = new->f;
1207
1208         for (i = 0; i < old->field_count; i++) {
1209                 memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
1210
1211                 dst->lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS *
1212                                    src->bsize * sizeof(*dst->lt),
1213                                    GFP_KERNEL);
1214                 if (!dst->lt)
1215                         goto out_lt;
1216
1217                 memcpy(dst->lt, src->lt,
1218                        src->bsize * sizeof(*dst->lt) *
1219                        src->groups * NFT_PIPAPO_BUCKETS);
1220
1221                 dst->mt = kvmalloc(src->rules * sizeof(*src->mt), GFP_KERNEL);
1222                 if (!dst->mt)
1223                         goto out_mt;
1224
1225                 memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt));
1226                 src++;
1227                 dst++;
1228         }
1229
1230         return new;
1231
1232 out_mt:
1233         kvfree(dst->lt);
1234 out_lt:
1235         for (dst--; i > 0; i--) {
1236                 kvfree(dst->mt);
1237                 kvfree(dst->lt);
1238                 dst--;
1239         }
1240         free_percpu(new->scratch);
1241 out_scratch:
1242         kfree(new);
1243
1244         return ERR_PTR(-ENOMEM);
1245 }
1246
1247 /**
1248  * pipapo_rules_same_key() - Get number of rules originated from the same entry
1249  * @f:          Field containing mapping table
1250  * @first:      Index of first rule in set of rules mapping to same entry
1251  *
1252  * Using the fact that all rules in a field that originated from the same entry
1253  * will map to the same set of rules in the next field, or to the same element
1254  * reference, return the cardinality of the set of rules that originated from
1255  * the same entry as the rule with index @first, @first rule included.
1256  *
1257  * In pictures:
1258  *                              rules
1259  *      field #0                0    1    2    3    4
1260  *              map to:         0    1   2-4  2-4  5-9
1261  *                              .    .    .......   . ...
1262  *                              |    |    |    | \   \
1263  *                              |    |    |    |  \   \
1264  *                              |    |    |    |   \   \
1265  *                              '    '    '    '    '   \
1266  *      in field #1             0    1    2    3    4    5 ...
1267  *
1268  * if this is called for rule 2 on field #0, it will return 3, as also rules 2
1269  * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
1270  *
1271  * For the last field in a set, we can rely on associated entries to map to the
1272  * same element references.
1273  *
1274  * Return: Number of rules that originated from the same entry as @first.
1275  */
1276 static int pipapo_rules_same_key(struct nft_pipapo_field *f, int first)
1277 {
1278         struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */
1279         int r;
1280
1281         for (r = first; r < f->rules; r++) {
1282                 if (r != first && e != f->mt[r].e)
1283                         return r - first;
1284
1285                 e = f->mt[r].e;
1286         }
1287
1288         if (r != first)
1289                 return r - first;
1290
1291         return 0;
1292 }
1293
1294 /**
1295  * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
1296  * @mt:         Mapping array
1297  * @rules:      Original amount of rules in mapping table
1298  * @start:      First rule index to be removed
1299  * @n:          Amount of rules to be removed
1300  * @to_offset:  First rule index, in next field, this group of rules maps to
1301  * @is_last:    If this is the last field, delete reference from mapping array
1302  *
1303  * This is used to unmap rules from the mapping table for a single field,
1304  * maintaining consistency and compactness for the existing ones.
1305  *
1306  * In pictures: let's assume that we want to delete rules 2 and 3 from the
1307  * following mapping array:
1308  *
1309  *                 rules
1310  *               0      1      2      3      4
1311  *      map to:  4-10   4-10   11-15  11-15  16-18
1312  *
1313  * the result will be:
1314  *
1315  *                 rules
1316  *               0      1      2
1317  *      map to:  4-10   4-10   11-13
1318  *
1319  * for fields before the last one. In case this is the mapping table for the
1320  * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
1321  *
1322  *                      rules
1323  *                        0      1      2      3      4
1324  *  element pointers:  0x42   0x42   0x33   0x33   0x44
1325  *
1326  * the result will be:
1327  *
1328  *                      rules
1329  *                        0      1      2
1330  *  element pointers:  0x42   0x42   0x44
1331  */
1332 static void pipapo_unmap(union nft_pipapo_map_bucket *mt, int rules,
1333                          int start, int n, int to_offset, bool is_last)
1334 {
1335         int i;
1336
1337         memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
1338         memset(mt + rules - n, 0, n * sizeof(*mt));
1339
1340         if (is_last)
1341                 return;
1342
1343         for (i = start; i < rules - n; i++)
1344                 mt[i].to -= to_offset;
1345 }
1346
1347 /**
1348  * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
1349  * @m:          Matching data
1350  * @rulemap     Table of rule maps, arrays of first rule and amount of rules
1351  *              in next field a given entry maps to, for each field
1352  *
1353  * For each rule in lookup table buckets mapping to this set of rules, drop
1354  * all bits set in lookup table mapping. In pictures, assuming we want to drop
1355  * rules 0 and 1 from this lookup table:
1356  *
1357  *                     bucket
1358  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1359  *        0    0                                              1,2
1360  *        1   1,2                                      0
1361  *        2    0                                      1,2
1362  *        3    0                              1,2
1363  *        4  0,1,2
1364  *        5    0   1   2
1365  *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1366  *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
1367  *
1368  * rule 2 becomes rule 0, and the result will be:
1369  *
1370  *                     bucket
1371  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1372  *        0                                                    0
1373  *        1    0
1374  *        2                                            0
1375  *        3                                    0
1376  *        4    0
1377  *        5            0
1378  *        6    0
1379  *        7    0   0
1380  *
1381  * once this is done, call unmap() to drop all the corresponding rule references
1382  * from mapping tables.
1383  */
1384 static void pipapo_drop(struct nft_pipapo_match *m,
1385                         union nft_pipapo_map_bucket rulemap[])
1386 {
1387         struct nft_pipapo_field *f;
1388         int i;
1389
1390         nft_pipapo_for_each_field(f, i, m) {
1391                 int g;
1392
1393                 for (g = 0; g < f->groups; g++) {
1394                         unsigned long *pos;
1395                         int b;
1396
1397                         pos = f->lt + g * NFT_PIPAPO_BUCKETS * f->bsize;
1398
1399                         for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
1400                                 bitmap_cut(pos, pos, rulemap[i].to,
1401                                            rulemap[i].n,
1402                                            f->bsize * BITS_PER_LONG);
1403
1404                                 pos += f->bsize;
1405                         }
1406                 }
1407
1408                 pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n,
1409                              rulemap[i + 1].n, i == m->field_count - 1);
1410                 if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) {
1411                         /* We can ignore this, a failure to shrink tables down
1412                          * doesn't make tables invalid.
1413                          */
1414                         ;
1415                 }
1416                 f->rules -= rulemap[i].n;
1417         }
1418 }
1419
1420 /**
1421  * pipapo_gc() - Drop expired entries from set, destroy start and end elements
1422  * @set:        nftables API set representation
1423  * @m:          Matching data
1424  */
1425 static void pipapo_gc(const struct nft_set *set, struct nft_pipapo_match *m)
1426 {
1427         struct nft_pipapo *priv = nft_set_priv(set);
1428         int rules_f0, first_rule = 0;
1429
1430         while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1431                 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1432                 struct nft_pipapo_field *f;
1433                 struct nft_pipapo_elem *e;
1434                 int i, start, rules_fx;
1435
1436                 start = first_rule;
1437                 rules_fx = rules_f0;
1438
1439                 nft_pipapo_for_each_field(f, i, m) {
1440                         rulemap[i].to = start;
1441                         rulemap[i].n = rules_fx;
1442
1443                         if (i < m->field_count - 1) {
1444                                 rules_fx = f->mt[start].n;
1445                                 start = f->mt[start].to;
1446                         }
1447                 }
1448
1449                 /* Pick the last field, and its last index */
1450                 f--;
1451                 i--;
1452                 e = f->mt[rulemap[i].to].e;
1453                 if (nft_set_elem_expired(&e->ext) &&
1454                     !nft_set_elem_mark_busy(&e->ext)) {
1455                         priv->dirty = true;
1456                         pipapo_drop(m, rulemap);
1457
1458                         rcu_barrier();
1459                         nft_set_elem_destroy(set, e, true);
1460
1461                         /* And check again current first rule, which is now the
1462                          * first we haven't checked.
1463                          */
1464                 } else {
1465                         first_rule += rules_f0;
1466                 }
1467         }
1468
1469         priv->last_gc = jiffies;
1470 }
1471
1472 /**
1473  * pipapo_free_fields() - Free per-field tables contained in matching data
1474  * @m:          Matching data
1475  */
1476 static void pipapo_free_fields(struct nft_pipapo_match *m)
1477 {
1478         struct nft_pipapo_field *f;
1479         int i;
1480
1481         nft_pipapo_for_each_field(f, i, m) {
1482                 kvfree(f->lt);
1483                 kvfree(f->mt);
1484         }
1485 }
1486
1487 /**
1488  * pipapo_reclaim_match - RCU callback to free fields from old matching data
1489  * @rcu:        RCU head
1490  */
1491 static void pipapo_reclaim_match(struct rcu_head *rcu)
1492 {
1493         struct nft_pipapo_match *m;
1494         int i;
1495
1496         m = container_of(rcu, struct nft_pipapo_match, rcu);
1497
1498         for_each_possible_cpu(i)
1499                 kfree(*per_cpu_ptr(m->scratch, i));
1500
1501         free_percpu(m->scratch);
1502
1503         pipapo_free_fields(m);
1504
1505         kfree(m);
1506 }
1507
1508 /**
1509  * pipapo_commit() - Replace lookup data with current working copy
1510  * @set:        nftables API set representation
1511  *
1512  * While at it, check if we should perform garbage collection on the working
1513  * copy before committing it for lookup, and don't replace the table if the
1514  * working copy doesn't have pending changes.
1515  *
1516  * We also need to create a new working copy for subsequent insertions and
1517  * deletions.
1518  */
1519 static void pipapo_commit(const struct nft_set *set)
1520 {
1521         struct nft_pipapo *priv = nft_set_priv(set);
1522         struct nft_pipapo_match *new_clone, *old;
1523
1524         if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
1525                 pipapo_gc(set, priv->clone);
1526
1527         if (!priv->dirty)
1528                 return;
1529
1530         new_clone = pipapo_clone(priv->clone);
1531         if (IS_ERR(new_clone))
1532                 return;
1533
1534         priv->dirty = false;
1535
1536         old = rcu_access_pointer(priv->match);
1537         rcu_assign_pointer(priv->match, priv->clone);
1538         if (old)
1539                 call_rcu(&old->rcu, pipapo_reclaim_match);
1540
1541         priv->clone = new_clone;
1542 }
1543
1544 /**
1545  * nft_pipapo_activate() - Mark element reference as active given key, commit
1546  * @net:        Network namespace
1547  * @set:        nftables API set representation
1548  * @elem:       nftables API element representation containing key data
1549  *
1550  * On insertion, elements are added to a copy of the matching data currently
1551  * in use for lookups, and not directly inserted into current lookup data, so
1552  * we'll take care of that by calling pipapo_commit() here. Both
1553  * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
1554  * element, hence we can't purpose either one as a real commit operation.
1555  */
1556 static void nft_pipapo_activate(const struct net *net,
1557                                 const struct nft_set *set,
1558                                 const struct nft_set_elem *elem)
1559 {
1560         struct nft_pipapo_elem *e;
1561
1562         e = pipapo_get(net, set, (const u8 *)elem->key.val.data, 0);
1563         if (IS_ERR(e))
1564                 return;
1565
1566         nft_set_elem_change_active(net, set, &e->ext);
1567         nft_set_elem_clear_busy(&e->ext);
1568
1569         pipapo_commit(set);
1570 }
1571
1572 /**
1573  * pipapo_deactivate() - Check that element is in set, mark as inactive
1574  * @net:        Network namespace
1575  * @set:        nftables API set representation
1576  * @data:       Input key data
1577  * @ext:        nftables API extension pointer, used to check for end element
1578  *
1579  * This is a convenience function that can be called from both
1580  * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same
1581  * operation.
1582  *
1583  * Return: deactivated element if found, NULL otherwise.
1584  */
1585 static void *pipapo_deactivate(const struct net *net, const struct nft_set *set,
1586                                const u8 *data, const struct nft_set_ext *ext)
1587 {
1588         struct nft_pipapo_elem *e;
1589
1590         e = pipapo_get(net, set, data, nft_genmask_next(net));
1591         if (IS_ERR(e))
1592                 return NULL;
1593
1594         nft_set_elem_change_active(net, set, &e->ext);
1595
1596         return e;
1597 }
1598
1599 /**
1600  * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive
1601  * @net:        Network namespace
1602  * @set:        nftables API set representation
1603  * @elem:       nftables API element representation containing key data
1604  *
1605  * Return: deactivated element if found, NULL otherwise.
1606  */
1607 static void *nft_pipapo_deactivate(const struct net *net,
1608                                    const struct nft_set *set,
1609                                    const struct nft_set_elem *elem)
1610 {
1611         const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1612
1613         return pipapo_deactivate(net, set, (const u8 *)elem->key.val.data, ext);
1614 }
1615
1616 /**
1617  * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive
1618  * @net:        Network namespace
1619  * @set:        nftables API set representation
1620  * @elem:       nftables API element representation containing key data
1621  *
1622  * This is functionally the same as nft_pipapo_deactivate(), with a slightly
1623  * different interface, and it's also called once for each element in a set
1624  * being flushed, so we can't implement, strictly speaking, a flush operation,
1625  * which would otherwise be as simple as allocating an empty copy of the
1626  * matching data.
1627  *
1628  * Note that we could in theory do that, mark the set as flushed, and ignore
1629  * subsequent calls, but we would leak all the elements after the first one,
1630  * because they wouldn't then be freed as result of API calls.
1631  *
1632  * Return: true if element was found and deactivated.
1633  */
1634 static bool nft_pipapo_flush(const struct net *net, const struct nft_set *set,
1635                              void *elem)
1636 {
1637         struct nft_pipapo_elem *e = elem;
1638
1639         return pipapo_deactivate(net, set, (const u8 *)nft_set_ext_key(&e->ext),
1640                                  &e->ext);
1641 }
1642
1643 /**
1644  * pipapo_get_boundaries() - Get byte interval for associated rules
1645  * @f:          Field including lookup table
1646  * @first_rule: First rule (lowest index)
1647  * @rule_count: Number of associated rules
1648  * @left:       Byte expression for left boundary (start of range)
1649  * @right:      Byte expression for right boundary (end of range)
1650  *
1651  * Given the first rule and amount of rules that originated from the same entry,
1652  * build the original range associated with the entry, and calculate the length
1653  * of the originating netmask.
1654  *
1655  * In pictures:
1656  *
1657  *                     bucket
1658  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1659  *        0                                                   1,2
1660  *        1   1,2
1661  *        2                                           1,2
1662  *        3                                   1,2
1663  *        4   1,2
1664  *        5        1   2
1665  *        6   1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1666  *        7   1,2 1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1
1667  *
1668  * this is the lookup table corresponding to the IPv4 range
1669  * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
1670  * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
1671  *
1672  * This function fills @left and @right with the byte values of the leftmost
1673  * and rightmost bucket indices for the lowest and highest rule indices,
1674  * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
1675  * nibbles:
1676  *   left:  < 12, 0, 10, 8, 0, 1, 0, 0 >
1677  *   right: < 12, 0, 10, 8, 0, 2, 2, 1 >
1678  * corresponding to bytes:
1679  *   left:  < 192, 168, 1, 0 >
1680  *   right: < 192, 168, 2, 1 >
1681  * with mask length irrelevant here, unused on return, as the range is already
1682  * defined by its start and end points. The mask length is relevant for a single
1683  * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
1684  * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
1685  * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
1686  * between leftmost and rightmost bucket indices for each group, would be 24.
1687  *
1688  * Return: mask length, in bits.
1689  */
1690 static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
1691                                  int rule_count, u8 *left, u8 *right)
1692 {
1693         u8 *l = left, *r = right;
1694         int g, mask_len = 0;
1695
1696         for (g = 0; g < f->groups; g++) {
1697                 int b, x0, x1;
1698
1699                 x0 = -1;
1700                 x1 = -1;
1701                 for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
1702                         unsigned long *pos;
1703
1704                         pos = f->lt + (g * NFT_PIPAPO_BUCKETS + b) * f->bsize;
1705                         if (test_bit(first_rule, pos) && x0 == -1)
1706                                 x0 = b;
1707                         if (test_bit(first_rule + rule_count - 1, pos))
1708                                 x1 = b;
1709                 }
1710
1711                 if (g % 2) {
1712                         *(l++) |= x0 & 0x0f;
1713                         *(r++) |= x1 & 0x0f;
1714                 } else {
1715                         *l |= x0 << 4;
1716                         *r |= x1 << 4;
1717                 }
1718
1719                 if (x1 - x0 == 0)
1720                         mask_len += 4;
1721                 else if (x1 - x0 == 1)
1722                         mask_len += 3;
1723                 else if (x1 - x0 == 3)
1724                         mask_len += 2;
1725                 else if (x1 - x0 == 7)
1726                         mask_len += 1;
1727         }
1728
1729         return mask_len;
1730 }
1731
1732 /**
1733  * pipapo_match_field() - Match rules against byte ranges
1734  * @f:          Field including the lookup table
1735  * @first_rule: First of associated rules originating from same entry
1736  * @rule_count: Amount of associated rules
1737  * @start:      Start of range to be matched
1738  * @end:        End of range to be matched
1739  *
1740  * Return: true on match, false otherwise.
1741  */
1742 static bool pipapo_match_field(struct nft_pipapo_field *f,
1743                                int first_rule, int rule_count,
1744                                const u8 *start, const u8 *end)
1745 {
1746         u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 };
1747         u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 };
1748
1749         pipapo_get_boundaries(f, first_rule, rule_count, left, right);
1750
1751         return !memcmp(start, left, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) &&
1752                !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE);
1753 }
1754
1755 /**
1756  * nft_pipapo_remove() - Remove element given key, commit
1757  * @net:        Network namespace
1758  * @set:        nftables API set representation
1759  * @elem:       nftables API element representation containing key data
1760  *
1761  * Similarly to nft_pipapo_activate(), this is used as commit operation by the
1762  * API, but it's called once per element in the pending transaction, so we can't
1763  * implement this as a single commit operation. Closest we can get is to remove
1764  * the matched element here, if any, and commit the updated matching data.
1765  */
1766 static void nft_pipapo_remove(const struct net *net, const struct nft_set *set,
1767                               const struct nft_set_elem *elem)
1768 {
1769         const u8 *data = (const u8 *)elem->key.val.data;
1770         struct nft_pipapo *priv = nft_set_priv(set);
1771         struct nft_pipapo_match *m = priv->clone;
1772         int rules_f0, first_rule = 0;
1773         struct nft_pipapo_elem *e;
1774
1775         e = pipapo_get(net, set, data, 0);
1776         if (IS_ERR(e))
1777                 return;
1778
1779         while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1780                 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1781                 const u8 *match_start, *match_end;
1782                 struct nft_pipapo_field *f;
1783                 int i, start, rules_fx;
1784
1785                 match_start = data;
1786                 match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data;
1787
1788                 start = first_rule;
1789                 rules_fx = rules_f0;
1790
1791                 nft_pipapo_for_each_field(f, i, m) {
1792                         if (!pipapo_match_field(f, start, rules_fx,
1793                                                 match_start, match_end))
1794                                 break;
1795
1796                         rulemap[i].to = start;
1797                         rulemap[i].n = rules_fx;
1798
1799                         rules_fx = f->mt[start].n;
1800                         start = f->mt[start].to;
1801
1802                         match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1803                         match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1804                 }
1805
1806                 if (i == m->field_count) {
1807                         priv->dirty = true;
1808                         pipapo_drop(m, rulemap);
1809                         pipapo_commit(set);
1810                         return;
1811                 }
1812
1813                 first_rule += rules_f0;
1814         }
1815 }
1816
1817 /**
1818  * nft_pipapo_walk() - Walk over elements
1819  * @ctx:        nftables API context
1820  * @set:        nftables API set representation
1821  * @iter:       Iterator
1822  *
1823  * As elements are referenced in the mapping array for the last field, directly
1824  * scan that array: there's no need to follow rule mappings from the first
1825  * field.
1826  */
1827 static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set,
1828                             struct nft_set_iter *iter)
1829 {
1830         struct nft_pipapo *priv = nft_set_priv(set);
1831         struct nft_pipapo_match *m;
1832         struct nft_pipapo_field *f;
1833         int i, r;
1834
1835         rcu_read_lock();
1836         m = rcu_dereference(priv->match);
1837
1838         if (unlikely(!m))
1839                 goto out;
1840
1841         for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
1842                 ;
1843
1844         for (r = 0; r < f->rules; r++) {
1845                 struct nft_pipapo_elem *e;
1846                 struct nft_set_elem elem;
1847
1848                 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
1849                         continue;
1850
1851                 if (iter->count < iter->skip)
1852                         goto cont;
1853
1854                 e = f->mt[r].e;
1855                 if (nft_set_elem_expired(&e->ext))
1856                         goto cont;
1857
1858                 elem.priv = e;
1859
1860                 iter->err = iter->fn(ctx, set, iter, &elem);
1861                 if (iter->err < 0)
1862                         goto out;
1863
1864 cont:
1865                 iter->count++;
1866         }
1867
1868 out:
1869         rcu_read_unlock();
1870 }
1871
1872 /**
1873  * nft_pipapo_privsize() - Return the size of private data for the set
1874  * @nla:        netlink attributes, ignored as size doesn't depend on them
1875  * @desc:       Set description, ignored as size doesn't depend on it
1876  *
1877  * Return: size of private data for this set implementation, in bytes
1878  */
1879 static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
1880                                const struct nft_set_desc *desc)
1881 {
1882         return sizeof(struct nft_pipapo);
1883 }
1884
1885 /**
1886  * nft_pipapo_estimate() - Estimate set size, space and lookup complexity
1887  * @desc:       Set description, element count and field description used here
1888  * @features:   Flags: NFT_SET_INTERVAL needs to be there
1889  * @est:        Storage for estimation data
1890  *
1891  * The size for this set type can vary dramatically, as it depends on the number
1892  * of rules (composing netmasks) the entries expand to. We compute the worst
1893  * case here.
1894  *
1895  * In general, for a non-ranged entry or a single composing netmask, we need
1896  * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
1897  * is, each input bit needs four bits of matching data), plus a bucket in the
1898  * mapping table for each field.
1899  *
1900  * Return: true only for compatible range concatenations
1901  */
1902 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
1903                                 struct nft_set_estimate *est)
1904 {
1905         unsigned long entry_size;
1906         int i;
1907
1908         if (!(features & NFT_SET_INTERVAL) || desc->field_count <= 1)
1909                 return false;
1910
1911         for (i = 0, entry_size = 0; i < desc->field_count; i++) {
1912                 unsigned long rules;
1913
1914                 if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
1915                         return false;
1916
1917                 /* Worst-case ranges for each concatenated field: each n-bit
1918                  * field can expand to up to n * 2 rules in each bucket, and
1919                  * each rule also needs a mapping bucket.
1920                  */
1921                 rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
1922                 entry_size += rules * NFT_PIPAPO_BUCKETS / BITS_PER_BYTE;
1923                 entry_size += rules * sizeof(union nft_pipapo_map_bucket);
1924         }
1925
1926         /* Rules in lookup and mapping tables are needed for each entry */
1927         est->size = desc->size * entry_size;
1928         if (est->size && div_u64(est->size, desc->size) != entry_size)
1929                 return false;
1930
1931         est->size += sizeof(struct nft_pipapo) +
1932                      sizeof(struct nft_pipapo_match) * 2;
1933
1934         est->size += sizeof(struct nft_pipapo_field) * desc->field_count;
1935
1936         est->lookup = NFT_SET_CLASS_O_LOG_N;
1937
1938         est->space = NFT_SET_CLASS_O_N;
1939
1940         return true;
1941 }
1942
1943 /**
1944  * nft_pipapo_init() - Initialise data for a set instance
1945  * @set:        nftables API set representation
1946  * @desc:       Set description
1947  * @nla:        netlink attributes
1948  *
1949  * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
1950  * attributes, initialise internal set parameters, current instance of matching
1951  * data and a copy for subsequent insertions.
1952  *
1953  * Return: 0 on success, negative error code on failure.
1954  */
1955 static int nft_pipapo_init(const struct nft_set *set,
1956                            const struct nft_set_desc *desc,
1957                            const struct nlattr * const nla[])
1958 {
1959         struct nft_pipapo *priv = nft_set_priv(set);
1960         struct nft_pipapo_match *m;
1961         struct nft_pipapo_field *f;
1962         int err, i;
1963
1964         if (desc->field_count > NFT_PIPAPO_MAX_FIELDS)
1965                 return -EINVAL;
1966
1967         m = kmalloc(sizeof(*priv->match) + sizeof(*f) * desc->field_count,
1968                     GFP_KERNEL);
1969         if (!m)
1970                 return -ENOMEM;
1971
1972         m->field_count = desc->field_count;
1973         m->bsize_max = 0;
1974
1975         m->scratch = alloc_percpu(unsigned long *);
1976         if (!m->scratch) {
1977                 err = -ENOMEM;
1978                 goto out_free;
1979         }
1980         for_each_possible_cpu(i)
1981                 *per_cpu_ptr(m->scratch, i) = NULL;
1982
1983         rcu_head_init(&m->rcu);
1984
1985         nft_pipapo_for_each_field(f, i, m) {
1986                 f->groups = desc->field_len[i] * NFT_PIPAPO_GROUPS_PER_BYTE;
1987                 priv->groups += f->groups;
1988
1989                 priv->width += round_up(desc->field_len[i], sizeof(u32));
1990
1991                 f->bsize = 0;
1992                 f->rules = 0;
1993                 f->lt = NULL;
1994                 f->mt = NULL;
1995         }
1996
1997         /* Create an initial clone of matching data for next insertion */
1998         priv->clone = pipapo_clone(m);
1999         if (IS_ERR(priv->clone)) {
2000                 err = PTR_ERR(priv->clone);
2001                 goto out_free;
2002         }
2003
2004         priv->dirty = false;
2005
2006         rcu_assign_pointer(priv->match, m);
2007
2008         return 0;
2009
2010 out_free:
2011         free_percpu(m->scratch);
2012         kfree(m);
2013
2014         return err;
2015 }
2016
2017 /**
2018  * nft_pipapo_destroy() - Free private data for set and all committed elements
2019  * @set:        nftables API set representation
2020  */
2021 static void nft_pipapo_destroy(const struct nft_set *set)
2022 {
2023         struct nft_pipapo *priv = nft_set_priv(set);
2024         struct nft_pipapo_match *m;
2025         struct nft_pipapo_field *f;
2026         int i, r, cpu;
2027
2028         m = rcu_dereference_protected(priv->match, true);
2029         if (m) {
2030                 rcu_barrier();
2031
2032                 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2033                         ;
2034
2035                 for (r = 0; r < f->rules; r++) {
2036                         struct nft_pipapo_elem *e;
2037
2038                         if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2039                                 continue;
2040
2041                         e = f->mt[r].e;
2042
2043                         nft_set_elem_destroy(set, e, true);
2044                 }
2045
2046                 for_each_possible_cpu(cpu)
2047                         kfree(*per_cpu_ptr(m->scratch, cpu));
2048                 free_percpu(m->scratch);
2049
2050                 pipapo_free_fields(m);
2051                 kfree(m);
2052                 priv->match = NULL;
2053         }
2054
2055         if (priv->clone) {
2056                 for_each_possible_cpu(cpu)
2057                         kfree(*per_cpu_ptr(priv->clone->scratch, cpu));
2058                 free_percpu(priv->clone->scratch);
2059
2060                 pipapo_free_fields(priv->clone);
2061                 kfree(priv->clone);
2062                 priv->clone = NULL;
2063         }
2064 }
2065
2066 /**
2067  * nft_pipapo_gc_init() - Initialise garbage collection
2068  * @set:        nftables API set representation
2069  *
2070  * Instead of actually setting up a periodic work for garbage collection, as
2071  * this operation requires a swap of matching data with the working copy, we'll
2072  * do that opportunistically with other commit operations if the interval is
2073  * elapsed, so we just need to set the current jiffies timestamp here.
2074  */
2075 static void nft_pipapo_gc_init(const struct nft_set *set)
2076 {
2077         struct nft_pipapo *priv = nft_set_priv(set);
2078
2079         priv->last_gc = jiffies;
2080 }
2081
2082 struct nft_set_type nft_set_pipapo_type __read_mostly = {
2083         .owner          = THIS_MODULE,
2084         .features       = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2085                           NFT_SET_TIMEOUT,
2086         .ops            = {
2087                 .lookup         = nft_pipapo_lookup,
2088                 .insert         = nft_pipapo_insert,
2089                 .activate       = nft_pipapo_activate,
2090                 .deactivate     = nft_pipapo_deactivate,
2091                 .flush          = nft_pipapo_flush,
2092                 .remove         = nft_pipapo_remove,
2093                 .walk           = nft_pipapo_walk,
2094                 .get            = nft_pipapo_get,
2095                 .privsize       = nft_pipapo_privsize,
2096                 .estimate       = nft_pipapo_estimate,
2097                 .init           = nft_pipapo_init,
2098                 .destroy        = nft_pipapo_destroy,
2099                 .gc_init        = nft_pipapo_gc_init,
2100                 .elemsize       = offsetof(struct nft_pipapo_elem, ext),
2101         },
2102 };