// SPDX-License-Identifier: GPL-2.0-only

/* PIPAPO: PIle PAcket POlicies: set for arbitrary concatenations of ranges
 *
 * Copyright (c) 2019-2020 Red Hat GmbH
 *
 * Author: Stefano Brivio <sbrivio@redhat.com>
 */

/**
 * DOC: Theory of Operation
 *
 *
 * Problem
 * -------
 *
 * Match packet bytes against entries composed of ranged or non-ranged packet
 * field specifiers, mapping them to arbitrary references. For example:
 *
 * ::
 *
 *               --- fields --->
 *      |    [net],[port],[net]... => [reference]
 *   entries [net],[port],[net]... => [reference]
 *      |    [net],[port],[net]... => [reference]
 *      V    ...
 *
 * where [net] fields can be IP ranges or netmasks, and [port] fields are port
 * ranges. Arbitrary packet fields can be matched.
 *
 *
 * Algorithm Overview
 * ------------------
 *
 * This algorithm is loosely inspired by [Ligatti 2010], and fundamentally
 * relies on the consideration that every contiguous range in a space of b bits
 * can be converted into b * 2 netmasks, from Theorem 3 in [Rottenstreich 2010],
 * as also illustrated in Section 9 of [Kogan 2014].
 *
 * Classification against a number of entries, that require matching given bits
 * of a packet field, is performed by grouping those bits in sets of arbitrary
 * size, and classifying packet bits one group at a time.
 *
 * Example:
 *   to match the source port (16 bits) of a packet, we can divide those 16 bits
 *   in 4 groups of 4 bits each. Given the entry:
 *      0000 0001 0101 1001
 *   and a packet with source port:
 *      0000 0001 1010 1001
 *   first and second groups match, but the third doesn't. We conclude that the
 *   packet doesn't match the given entry.
 *
 * Translate the set to a sequence of lookup tables, one per field. Each table
 * has two dimensions: bit groups to be matched for a single packet field, and
 * all the possible values of said groups (buckets). Input entries are
 * represented as one or more rules, depending on the number of composing
 * netmasks for the given field specifier, and a group match is indicated as a
 * set bit, with number corresponding to the rule index, in all the buckets
 * whose value matches the entry for a given group.
 *
 * Rules are mapped between fields through an array of x, n pairs, with each
 * item mapping a matched rule to one or more rules. The position of the pair in
 * the array indicates the matched rule to be mapped to the next field, x
 * indicates the first rule index in the next field, and n the amount of
 * next-field rules the current rule maps to.
 *
 * The mapping array for the last field maps to the desired references.
 *
 * To match, we perform table lookups using the values of grouped packet bits,
 * and use a sequence of bitwise operations to progressively evaluate rule
 * matching.
 *
 * A stand-alone, reference implementation, also including notes about possible
 * future optimisations, is available at:
 *    https://pipapo.lameexcu.se/
 *
 * Insertion
 * ---------
 *
 * - For each packet field:
 *
 *   - divide the b packet bits we want to classify into groups of size t,
 *     obtaining ceil(b / t) groups
 *
 *      Example: match on destination IP address, with t = 4: 32 bits, 8 groups
 *      of 4 bits each
 *
 *   - allocate a lookup table with one column ("bucket") for each possible
 *     value of a group, and with one row for each group
 *
 *      Example: 8 groups, 2^4 buckets:
 *
 * ::
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0
 *        1
 *        2
 *        3
 *        4
 *        5
 *        6
 *        7
 *
 *   - map the bits we want to classify for the current field, for a given
 *     entry, to a single rule for non-ranged and netmask set items, and to one
 *     or multiple rules for ranges. Ranges are expanded to composing netmasks
 *     by pipapo_expand().
 *
 *      Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048
 *      - rule #0: 10.0.0.5
 *      - rule #1: 192.168.1.0/24
 *      - rule #2: 192.168.2.0/31
 *
 *   - insert references to the rules in the lookup table, selecting buckets
 *     according to bit values of a rule in the given group. This is done by
 *     pipapo_insert().
 *
 *      Example: given:
 *      - rule #0: 10.0.0.5 mapping to buckets
 *        < 0 10  0 0   0 0  0 5 >
 *      - rule #1: 192.168.1.0/24 mapping to buckets
 *        < 12 0  10 8  0 1  < 0..15 > < 0..15 > >
 *      - rule #2: 192.168.2.0/31 mapping to buckets
 *        < 12 0  10 8  0 2  0 < 0..1 > >
 *
 *      these bits are set in the lookup table:
 *
 * ::
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0    0                                              1,2
 *        1   1,2                                      0
 *        2    0                                      1,2
 *        3    0                              1,2
 *        4  0,1,2
 *        5    0   1   2
 *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
 *
 *   - if this is not the last field in the set, fill a mapping array that maps
 *     rules from the lookup table to rules belonging to the same entry in
 *     the next lookup table, done by pipapo_map().
 *
 *     Note that as rules map to contiguous ranges of rules, given how netmask
 *     expansion and insertion is performed, &union nft_pipapo_map_bucket stores
 *     this information as pairs of first rule index, rule count.
 *
 *      Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048,
 *      given lookup table #0 for field 0 (see example above):
 *
 * ::
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0    0                                              1,2
 *        1   1,2                                      0
 *        2    0                                      1,2
 *        3    0                              1,2
 *        4  0,1,2
 *        5    0   1   2
 *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
 *
 *      and lookup table #1 for field 1 with:
 *      - rule #0: 1024 mapping to buckets
 *        < 0  0  4  0 >
 *      - rule #1: 2048 mapping to buckets
 *        < 0  0  5  0 >
 *
 * ::
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0   0,1
 *        1   0,1
 *        2                    0   1
 *        3   0,1
 *
 *      we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024
 *      in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1
 *      (rules #1, #2) to 2048 in lookup table #2 (rule #1):
 *
 * ::
 *
 *       rule indices in current field: 0    1    2
 *       map to rules in next field:    0    1    1
 *
 *   - if this is the last field in the set, fill a mapping array that maps
 *     rules from the last lookup table to element pointers, also done by
 *     pipapo_map().
 *
 *     Note that, in this implementation, we have two elements (start, end) for
 *     each entry. The pointer to the end element is stored in this array, and
 *     the pointer to the start element is linked from it.
 *
 *      Example: entry 10.0.0.5:1024 has a corresponding &struct nft_pipapo_elem
 *      pointer, 0x66, and element for 192.168.1.0-192.168.2.1:2048 is at 0x42.
 *      From the rules of lookup table #1 as mapped above:
 *
 * ::
 *
 *       rule indices in last field:    0    1
 *       map to elements:             0x42  0x66
 *
 *
 * Matching
 * --------
 *
 * We use a result bitmap, with the size of a single lookup table bucket, to
 * represent the matching state that applies at every algorithm step. This is
 * done by pipapo_lookup().
 *
 * - For each packet field:
 *
 *   - start with an all-ones result bitmap (res_map in pipapo_lookup())
 *
 *   - perform a lookup into the table corresponding to the current field,
 *     for each group, and at every group, AND the current result bitmap with
 *     the value from the lookup table bucket
 *
 * ::
 *
 *      Example: 192.168.1.5 < 12 0  10 8  0 1  0 5 >, with lookup table from
 *      insertion examples.
 *      Lookup table buckets are at least 3 bits wide, we'll assume 8 bits for
 *      convenience in this example. Initial result bitmap is 0xff, the steps
 *      below show the value of the result bitmap after each group is processed:
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0    0                                              1,2
 *        result bitmap is now: 0xff & 0x6 [bucket 12] = 0x6
 *
 *        1   1,2                                      0
 *        result bitmap is now: 0x6 & 0x6 [bucket 0] = 0x6
 *
 *        2    0                                      1,2
 *        result bitmap is now: 0x6 & 0x6 [bucket 10] = 0x6
 *
 *        3    0                              1,2
 *        result bitmap is now: 0x6 & 0x6 [bucket 8] = 0x6
 *
 *        4  0,1,2
 *        result bitmap is now: 0x6 & 0x7 [bucket 0] = 0x6
 *
 *        5    0   1   2
 *        result bitmap is now: 0x6 & 0x2 [bucket 1] = 0x2
 *
 *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 *        result bitmap is now: 0x2 & 0x7 [bucket 0] = 0x2
 *
 *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
 *        final result bitmap for this field is: 0x2 & 0x3 [bucket 5] = 0x2
 *
 *   - at the next field, start with a new, all-zeroes result bitmap. For each
 *     bit set in the previous result bitmap, fill the new result bitmap
 *     (fill_map in pipapo_lookup()) with the rule indices from the
 *     corresponding buckets of the mapping field for this field, done by
 *     pipapo_refill()
 *
 *      Example: with mapping table from insertion examples, with the current
 *      result bitmap from the previous example, 0x02:
 *
 * ::
 *
 *       rule indices in current field: 0    1    2
 *       map to rules in next field:    0    1    1
 *
 *      the new result bitmap will be 0x02: rule 1 was set, and rule 1 will be
 *      set.
 *
 *      We can now extend this example to cover the second iteration of the step
 *      above (lookup and AND bitmap): assuming the port field is
 *      2048 < 0  0  5  0 >, with starting result bitmap 0x2, and lookup table
 *      for "port" field from pre-computation example:
 *
 * ::
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0   0,1
 *        1   0,1
 *        2                    0   1
 *        3   0,1
 *
 *       operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5]
 *       & 0x3 [bucket 0], resulting bitmap is 0x2.
 *
 *   - if this is the last field in the set, look up the value from the mapping
 *     array corresponding to the final result bitmap
 *
 *      Example: 0x2 resulting bitmap from 192.168.1.5:2048, mapping array for
 *      last field from insertion example:
 *
 * ::
 *
 *       rule indices in last field:    0    1
 *       map to elements:             0x42  0x66
 *
 *      the matching element is at 0x42.
 *
 *
 * References
 * ----------
 *
 * [Ligatti 2010]
 *      A Packet-classification Algorithm for Arbitrary Bitmask Rules, with
 *      Automatic Time-space Tradeoffs
 *      Jay Ligatti, Josh Kuhn, and Chris Gage.
 *      Proceedings of the IEEE International Conference on Computer
 *      Communication Networks (ICCCN), August 2010.
 *      http://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf
 *
 * [Rottenstreich 2010]
 *      Worst-Case TCAM Rule Expansion
 *      Ori Rottenstreich and Isaac Keslassy.
 *      2010 Proceedings IEEE INFOCOM, San Diego, CA, 2010.
 *      http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.212.4592&rep=rep1&type=pdf
 *
 * [Kogan 2014]
 *      SAX-PAC (Scalable And eXpressive PAcket Classification)
 *      Kirill Kogan, Sergey Nikolenko, Ori Rottenstreich, William Culhane,
 *      and Patrick Eugster.
 *      Proceedings of the 2014 ACM conference on SIGCOMM, August 2014.
 *      http://www.sigcomm.org/sites/default/files/ccr/papers/2014/August/2619239-2626294.pdf
 */

#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/log2.h>
#include <linux/module.h>
#include <linux/netlink.h>
#include <linux/netfilter.h>
#include <linux/netfilter/nf_tables.h>
#include <net/netfilter/nf_tables_core.h>
#include <uapi/linux/netfilter/nf_tables.h>
#include <net/ipv6.h>                   /* For the maximum length of a field */
#include <linux/bitmap.h>
#include <linux/bitops.h>

/* Count of concatenated fields depends on count of 32-bit nftables registers */
#define NFT_PIPAPO_MAX_FIELDS           NFT_REG32_COUNT

/* Largest supported field size */
#define NFT_PIPAPO_MAX_BYTES            (sizeof(struct in6_addr))
#define NFT_PIPAPO_MAX_BITS             (NFT_PIPAPO_MAX_BYTES * BITS_PER_BYTE)

/* Number of bits to be grouped together in lookup table buckets, arbitrary */
#define NFT_PIPAPO_GROUP_BITS           4
#define NFT_PIPAPO_GROUPS_PER_BYTE      (BITS_PER_BYTE / NFT_PIPAPO_GROUP_BITS)

/* Fields are padded to 32 bits in input registers */
#define NFT_PIPAPO_GROUPS_PADDED_SIZE(x)                                \
        (round_up((x) / NFT_PIPAPO_GROUPS_PER_BYTE, sizeof(u32)))
#define NFT_PIPAPO_GROUPS_PADDING(x)                                    \
        (NFT_PIPAPO_GROUPS_PADDED_SIZE((x)) - (x) / NFT_PIPAPO_GROUPS_PER_BYTE)

/* Number of buckets, given by 2 ^ n, with n grouped bits */
#define NFT_PIPAPO_BUCKETS              (1 << NFT_PIPAPO_GROUP_BITS)

/* Each n-bit range maps to up to n * 2 rules */
#define NFT_PIPAPO_MAP_NBITS            (const_ilog2(NFT_PIPAPO_MAX_BITS * 2))

/* Use the rest of mapping table buckets for rule indices, but it makes no sense
 * to exceed 32 bits
 */
#if BITS_PER_LONG == 64
#define NFT_PIPAPO_MAP_TOBITS           32
#else
#define NFT_PIPAPO_MAP_TOBITS           (BITS_PER_LONG - NFT_PIPAPO_MAP_NBITS)
#endif

/* ...which gives us the highest allowed index for a rule */
#define NFT_PIPAPO_RULE0_MAX            ((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
                                        - (1UL << NFT_PIPAPO_MAP_NBITS))

#define nft_pipapo_for_each_field(field, index, match)          \
        for ((field) = (match)->f, (index) = 0;                 \
             (index) < (match)->field_count;                    \
             (index)++, (field)++)

/**
 * union nft_pipapo_map_bucket - Bucket of mapping table
 * @to:         First rule number (in next field) this rule maps to
 * @n:          Number of rules (in next field) this rule maps to
 * @e:          If there's no next field, pointer to element this rule maps to
 */
union nft_pipapo_map_bucket {
        struct {
#if BITS_PER_LONG == 64
                static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
                u32 to;

                static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
                u32 n;
#else
                unsigned long to:NFT_PIPAPO_MAP_TOBITS;
                unsigned long  n:NFT_PIPAPO_MAP_NBITS;
#endif
        };
        struct nft_pipapo_elem *e;
};

/**
 * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
 * @groups:     Amount of 4-bit groups
 * @rules:      Number of inserted rules
 * @bsize:      Size of each bucket in lookup table, in longs
 * @lt:         Lookup table: 'groups' rows of NFT_PIPAPO_BUCKETS buckets
 * @mt:         Mapping table: one bucket per rule
 */
struct nft_pipapo_field {
        int groups;
        unsigned long rules;
        size_t bsize;
        unsigned long *lt;
        union nft_pipapo_map_bucket *mt;
};

/**
 * struct nft_pipapo_match - Data used for lookup and matching
 * @field_count         Amount of fields in set
 * @scratch:            Preallocated per-CPU maps for partial matching results
 * @bsize_max:          Maximum lookup table bucket size of all fields, in longs
 * @rcu                 Matching data is swapped on commits
 * @f:                  Fields, with lookup and mapping tables
 */
struct nft_pipapo_match {
        int field_count;
        unsigned long * __percpu *scratch;
        size_t bsize_max;
        struct rcu_head rcu;
        struct nft_pipapo_field f[0];
};

/* Current working bitmap index, toggled between field matches */
static DEFINE_PER_CPU(bool, nft_pipapo_scratch_index);

/**
 * struct nft_pipapo - Representation of a set
 * @match:      Currently in-use matching data
 * @clone:      Copy where pending insertions and deletions are kept
 * @groups:     Total amount of 4-bit groups for fields in this set
 * @width:      Total bytes to be matched for one packet, including padding
 * @dirty:      Working copy has pending insertions or deletions
 * @last_gc:    Timestamp of last garbage collection run, jiffies
 */
struct nft_pipapo {
        struct nft_pipapo_match __rcu *match;
        struct nft_pipapo_match *clone;
        int groups;
        int width;
        bool dirty;
        unsigned long last_gc;
};

struct nft_pipapo_elem;

/**
 * struct nft_pipapo_elem - API-facing representation of single set element
 * @ext:        nftables API extensions
 */
struct nft_pipapo_elem {
        struct nft_set_ext ext;
};

/**
 * pipapo_refill() - For each set bit, set bits from selected mapping table item
 * @map:        Bitmap to be scanned for set bits
 * @len:        Length of bitmap in longs
 * @rules:      Number of rules in field
 * @dst:        Destination bitmap
 * @mt:         Mapping table containing bit set specifiers
 * @match_only: Find a single bit and return, don't fill
 *
 * Iteration over set bits with __builtin_ctzl(): Daniel Lemire, public domain.
 *
 * For each bit set in map, select the bucket from mapping table with index
 * corresponding to the position of the bit set. Use start bit and amount of
 * bits specified in bucket to fill region in dst.
 *
 * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
 */
static int pipapo_refill(unsigned long *map, int len, int rules,
                         unsigned long *dst, union nft_pipapo_map_bucket *mt,
                         bool match_only)
{
        unsigned long bitset;
        int k, ret = -1;

        for (k = 0; k < len; k++) {
                bitset = map[k];
                while (bitset) {
                        unsigned long t = bitset & -bitset;
                        int r = __builtin_ctzl(bitset);
                        int i = k * BITS_PER_LONG + r;

                        if (unlikely(i >= rules)) {
                                map[k] = 0;
                                return -1;
                        }

                        if (unlikely(match_only)) {
                                bitmap_clear(map, i, 1);
                                return i;
                        }

                        ret = 0;

                        bitmap_set(dst, mt[i].to, mt[i].n);

                        bitset ^= t;
                }
                map[k] = 0;
        }

        return ret;
}

/**
 * nft_pipapo_lookup() - Lookup function
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @elem:       nftables API element representation containing key data
 * @ext:        nftables API extension pointer, filled with matching reference
 *
 * For more details, see DOC: Theory of Operation.
 *
 * Return: true on match, false otherwise.
 */
static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
                              const u32 *key, const struct nft_set_ext **ext)
{
        struct nft_pipapo *priv = nft_set_priv(set);
        unsigned long *res_map, *fill_map;
        u8 genmask = nft_genmask_cur(net);
        const u8 *rp = (const u8 *)key;
        struct nft_pipapo_match *m;
        struct nft_pipapo_field *f;
        bool map_index;
        int i;

        local_bh_disable();

        map_index = raw_cpu_read(nft_pipapo_scratch_index);

        m = rcu_dereference(priv->match);

        if (unlikely(!m || !*raw_cpu_ptr(m->scratch)))
                goto out;

        res_map  = *raw_cpu_ptr(m->scratch) + (map_index ? m->bsize_max : 0);
        fill_map = *raw_cpu_ptr(m->scratch) + (map_index ? 0 : m->bsize_max);

        memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));

        nft_pipapo_for_each_field(f, i, m) {
                bool last = i == m->field_count - 1;
                unsigned long *lt = f->lt;
                int b, group;

                /* For each 4-bit group: select lookup table bucket depending on
                 * packet bytes value, then AND bucket value
                 */
                for (group = 0; group < f->groups; group += 2) {
                        u8 v;

                        v = *rp >> 4;
                        __bitmap_and(res_map, res_map, lt + v * f->bsize,
                                     f->bsize * BITS_PER_LONG);
                        lt += f->bsize * NFT_PIPAPO_BUCKETS;

                        v = *rp & 0x0f;
                        rp++;
                        __bitmap_and(res_map, res_map, lt + v * f->bsize,
                                     f->bsize * BITS_PER_LONG);
                        lt += f->bsize * NFT_PIPAPO_BUCKETS;
                }

                /* Now populate the bitmap for the next field, unless this is
                 * the last field, in which case return the matched 'ext'
                 * pointer if any.
                 *
                 * Now res_map contains the matching bitmap, and fill_map is the
                 * bitmap for the next field.
                 */
next_match:
                b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
                                  last);
                if (b < 0) {
                        raw_cpu_write(nft_pipapo_scratch_index, map_index);
                        local_bh_enable();

                        return false;
                }

                if (last) {
                        *ext = &f->mt[b].e->ext;
                        if (unlikely(nft_set_elem_expired(*ext) ||
                                     !nft_set_elem_active(*ext, genmask)))
                                goto next_match;

                        /* Last field: we're just returning the key without
                         * filling the initial bitmap for the next field, so the
                         * current inactive bitmap is clean and can be reused as
                         * *next* bitmap (not initial) for the next packet.
                         */
                        raw_cpu_write(nft_pipapo_scratch_index, map_index);
                        local_bh_enable();

                        return true;
                }

                /* Swap bitmap indices: res_map is the initial bitmap for the
                 * next field, and fill_map is guaranteed to be all-zeroes at
                 * this point.
                 */
                map_index = !map_index;
                swap(res_map, fill_map);

                rp += NFT_PIPAPO_GROUPS_PADDING(f->groups);
        }

out:
        local_bh_enable();
        return false;
}

/**
 * pipapo_get() - Get matching element reference given key data
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @data:       Key data to be matched against existing elements
 * @genmask:    If set, check that element is active in given genmask
 *
 * This is essentially the same as the lookup function, except that it matches
 * key data against the uncommitted copy and doesn't use preallocated maps for
 * bitmap results.
 *
 * Return: pointer to &struct nft_pipapo_elem on match, error pointer otherwise.
 */
static struct nft_pipapo_elem *pipapo_get(const struct net *net,
                                          const struct nft_set *set,
                                          const u8 *data, u8 genmask)
{
        struct nft_pipapo_elem *ret = ERR_PTR(-ENOENT);
        struct nft_pipapo *priv = nft_set_priv(set);
        struct nft_pipapo_match *m = priv->clone;
        unsigned long *res_map, *fill_map = NULL;
        struct nft_pipapo_field *f;
        int i;

        res_map = kmalloc_array(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
        if (!res_map) {
                ret = ERR_PTR(-ENOMEM);
                goto out;
        }

        fill_map = kcalloc(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
        if (!fill_map) {
                ret = ERR_PTR(-ENOMEM);
                goto out;
        }

        memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));

        nft_pipapo_for_each_field(f, i, m) {
                bool last = i == m->field_count - 1;
                unsigned long *lt = f->lt;
                int b, group;

                /* For each 4-bit group: select lookup table bucket depending on
                 * packet bytes value, then AND bucket value
                 */
                for (group = 0; group < f->groups; group++) {
                        u8 v;

                        if (group % 2) {
                                v = *data & 0x0f;
                                data++;
                        } else {
                                v = *data >> 4;
                        }
                        __bitmap_and(res_map, res_map, lt + v * f->bsize,
                                     f->bsize * BITS_PER_LONG);

                        lt += f->bsize * NFT_PIPAPO_BUCKETS;
                }

                /* Now populate the bitmap for the next field, unless this is
                 * the last field, in which case return the matched 'ext'
                 * pointer if any.
                 *
                 * Now res_map contains the matching bitmap, and fill_map is the
                 * bitmap for the next field.
                 */
next_match:
                b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
                                  last);
                if (b < 0)
                        goto out;

                if (last) {
                        if (nft_set_elem_expired(&f->mt[b].e->ext) ||
                            (genmask &&
                             !nft_set_elem_active(&f->mt[b].e->ext, genmask)))
                                goto next_match;

                        ret = f->mt[b].e;
                        goto out;
                }

                data += NFT_PIPAPO_GROUPS_PADDING(f->groups);

                /* Swap bitmap indices: fill_map will be the initial bitmap for
                 * the next field (i.e. the new res_map), and res_map is
                 * guaranteed to be all-zeroes at this point, ready to be filled
                 * according to the next mapping table.
                 */
                swap(res_map, fill_map);
        }

out:
        kfree(fill_map);
        kfree(res_map);
        return ret;
}

/**
 * nft_pipapo_get() - Get matching element reference given key data
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @elem:       nftables API element representation containing key data
 * @flags:      Unused
 */
void *nft_pipapo_get(const struct net *net, const struct nft_set *set,
                     const struct nft_set_elem *elem, unsigned int flags)
{
        return pipapo_get(net, set, (const u8 *)elem->key.val.data,
                          nft_genmask_cur(net));
}

/**
 * pipapo_resize() - Resize lookup or mapping table, or both
 * @f:          Field containing lookup and mapping tables
 * @old_rules:  Previous amount of rules in field
 * @rules:      New amount of rules
 *
 * Increase, decrease or maintain tables size depending on new amount of rules,
 * and copy data over. In case the new size is smaller, throw away data for
 * highest-numbered rules.
 *
 * Return: 0 on success, -ENOMEM on allocation failure.
 */
static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
{
        long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
        union nft_pipapo_map_bucket *new_mt, *old_mt = f->mt;
        size_t new_bucket_size, copy;
        int group, bucket;

        new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);

        if (new_bucket_size == f->bsize)
                goto mt;

        if (new_bucket_size > f->bsize)
                copy = f->bsize;
        else
                copy = new_bucket_size;

        new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS * new_bucket_size *
                          sizeof(*new_lt), GFP_KERNEL);
        if (!new_lt)
                return -ENOMEM;

        new_p = new_lt;
        old_p = old_lt;
        for (group = 0; group < f->groups; group++) {
                for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS; bucket++) {
                        memcpy(new_p, old_p, copy * sizeof(*new_p));
                        new_p += copy;
                        old_p += copy;

                        if (new_bucket_size > f->bsize)
                                new_p += new_bucket_size - f->bsize;
                        else
                                old_p += f->bsize - new_bucket_size;
                }
        }

mt:
        new_mt = kvmalloc(rules * sizeof(*new_mt), GFP_KERNEL);
        if (!new_mt) {
                kvfree(new_lt);
                return -ENOMEM;
        }

        memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt));
        if (rules > old_rules) {
                memset(new_mt + old_rules, 0,
                       (rules - old_rules) * sizeof(*new_mt));
        }

        if (new_lt) {
                f->bsize = new_bucket_size;
                f->lt = new_lt;
                kvfree(old_lt);
        }

        f->mt = new_mt;
        kvfree(old_mt);

        return 0;
}

/**
 * pipapo_bucket_set() - Set rule bit in bucket given group and group value
 * @f:          Field containing lookup table
 * @rule:       Rule index
 * @group:      Group index
 * @v:          Value of bit group
 */
static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
                              int v)
{
        unsigned long *pos;

        pos = f->lt + f->bsize * NFT_PIPAPO_BUCKETS * group;
        pos += f->bsize * v;

        __set_bit(rule, pos);
}

/**
 * pipapo_insert() - Insert new rule in field given input key and mask length
 * @f:          Field containing lookup table
 * @k:          Input key for classification, without nftables padding
 * @mask_bits:  Length of mask; matches field length for non-ranged entry
 *
 * Insert a new rule reference in lookup buckets corresponding to k and
 * mask_bits.
 *
 * Return: 1 on success (one rule inserted), negative error code on failure.
 */
static int pipapo_insert(struct nft_pipapo_field *f, const uint8_t *k,
                         int mask_bits)
{
        int rule = f->rules++, group, ret;

        ret = pipapo_resize(f, f->rules - 1, f->rules);
        if (ret)
                return ret;

        for (group = 0; group < f->groups; group++) {
                int i, v;
                u8 mask;

                if (group % 2)
                        v = k[group / 2] & 0x0f;
                else
                        v = k[group / 2] >> 4;

                if (mask_bits >= (group + 1) * 4) {
                        /* Not masked */
                        pipapo_bucket_set(f, rule, group, v);
                } else if (mask_bits <= group * 4) {
                        /* Completely masked */
                        for (i = 0; i < NFT_PIPAPO_BUCKETS; i++)
                                pipapo_bucket_set(f, rule, group, i);
                } else {
                        /* The mask limit falls on this group */
                        mask = 0x0f >> (mask_bits - group * 4);
                        for (i = 0; i < NFT_PIPAPO_BUCKETS; i++) {
                                if ((i & ~mask) == (v & ~mask))
                                        pipapo_bucket_set(f, rule, group, i);
                        }
                }
        }

        return 1;
}

/**
 * pipapo_step_diff() - Check if setting @step bit in netmask would change it
 * @base:       Mask we are expanding
 * @step:       Step bit for given expansion step
 * @len:        Total length of mask space (set and unset bits), bytes
 *
 * Convenience function for mask expansion.
 *
 * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
 */
static bool pipapo_step_diff(u8 *base, int step, int len)
{
        /* Network order, byte-addressed */
#ifdef __BIG_ENDIAN__
        return !(BIT(step % BITS_PER_BYTE) & base[step / BITS_PER_BYTE]);
#else
        return !(BIT(step % BITS_PER_BYTE) &
                 base[len - 1 - step / BITS_PER_BYTE]);
#endif
}

/**
 * pipapo_step_after_end() - Check if mask exceeds range end with given step
 * @base:       Mask we are expanding
 * @end:        End of range
 * @step:       Step bit for given expansion step, highest bit to be set
 * @len:        Total length of mask space (set and unset bits), bytes
 *
 * Convenience function for mask expansion.
 *
 * Return: true if mask exceeds range setting step bits, false otherwise.
 */
static bool pipapo_step_after_end(const u8 *base, const u8 *end, int step,
                                  int len)
{
        u8 tmp[NFT_PIPAPO_MAX_BYTES];
        int i;

        memcpy(tmp, base, len);

        /* Network order, byte-addressed */
        for (i = 0; i <= step; i++)
#ifdef __BIG_ENDIAN__
                tmp[i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
#else
                tmp[len - 1 - i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
#endif

        return memcmp(tmp, end, len) > 0;
}

/**
 * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
 * @base:       Netmask base
 * @step:       Step bit to sum
 * @len:        Netmask length, bytes
 */
static void pipapo_base_sum(u8 *base, int step, int len)
{
        bool carry = false;
        int i;

        /* Network order, byte-addressed */
#ifdef __BIG_ENDIAN__
        for (i = step / BITS_PER_BYTE; i < len; i++) {
#else
        for (i = len - 1 - step / BITS_PER_BYTE; i >= 0; i--) {
#endif
                if (carry)
                        base[i]++;
                else
                        base[i] += 1 << (step % BITS_PER_BYTE);

                if (base[i])
                        break;

                carry = true;
        }
}

/**
 * pipapo_expand() - Expand to composing netmasks, insert into lookup table
 * @f:          Field containing lookup table
 * @start:      Start of range
 * @end:        End of range
 * @len:        Length of value in bits
 *
 * Expand range to composing netmasks and insert corresponding rule references
 * in lookup buckets.
 *
 * Return: number of inserted rules on success, negative error code on failure.
 */
static int pipapo_expand(struct nft_pipapo_field *f,
                         const u8 *start, const u8 *end, int len)
{
        int step, masks = 0, bytes = DIV_ROUND_UP(len, BITS_PER_BYTE);
        u8 base[NFT_PIPAPO_MAX_BYTES];

        memcpy(base, start, bytes);
        while (memcmp(base, end, bytes) <= 0) {
                int err;

                step = 0;
                while (pipapo_step_diff(base, step, bytes)) {
                        if (pipapo_step_after_end(base, end, step, bytes))
                                break;

                        step++;
                        if (step >= len) {
                                if (!masks) {
                                        pipapo_insert(f, base, 0);
                                        masks = 1;
                                }
                                goto out;

                        }
                }

                err = pipapo_insert(f, base, len - step);

                if (err < 0)
                        return err;

                masks++;
                pipapo_base_sum(base, step, bytes);
        }
out:
        return masks;
}

/**
 * pipapo_map() - Insert rules in mapping tables, mapping them between fields
 * @m:          Matching data, including mapping table
 * @map:        Table of rule maps: array of first rule and amount of rules
 *              in next field a given rule maps to, for each field
 * @ext:        For last field, nft_set_ext pointer matching rules map to
 */
static void pipapo_map(struct nft_pipapo_match *m,
                       union nft_pipapo_map_bucket map[NFT_PIPAPO_MAX_FIELDS],
                       struct nft_pipapo_elem *e)
{
        struct nft_pipapo_field *f;
        int i, j;

        for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) {
                for (j = 0; j < map[i].n; j++) {
                        f->mt[map[i].to + j].to = map[i + 1].to;
                        f->mt[map[i].to + j].n = map[i + 1].n;
                }
        }

        /* Last field: map to ext instead of mapping to next field */
        for (j = 0; j < map[i].n; j++)
                f->mt[map[i].to + j].e = e;
}

/**
 * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
 * @clone:      Copy of matching data with pending insertions and deletions
 * @bsize_max   Maximum bucket size, scratch maps cover two buckets
 *
 * Return: 0 on success, -ENOMEM on failure.
 */
static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
                                  unsigned long bsize_max)
{
        int i;

        for_each_possible_cpu(i) {
                unsigned long *scratch;

                scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2,
                                       GFP_KERNEL, cpu_to_node(i));
                if (!scratch) {
                        /* On failure, there's no need to undo previous
                         * allocations: this means that some scratch maps have
                         * a bigger allocated size now (this is only called on
                         * insertion), but the extra space won't be used by any
                         * CPU as new elements are not inserted and m->bsize_max
                         * is not updated.
                         */
                        return -ENOMEM;
                }

                kfree(*per_cpu_ptr(clone->scratch, i));

                *per_cpu_ptr(clone->scratch, i) = scratch;
        }

        return 0;
}

/**
 * nft_pipapo_insert() - Validate and insert ranged elements
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @elem:       nftables API element representation containing key data
 * @ext2:       Filled with pointer to &struct nft_set_ext in inserted element
 *
 * Return: 0 on success, error pointer on failure.
 */
static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,
                             const struct nft_set_elem *elem,
                             struct nft_set_ext **ext2)
{
        const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
        union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
        const u8 *start = (const u8 *)elem->key.val.data, *end;
        struct nft_pipapo_elem *e = elem->priv, *dup;
        struct nft_pipapo *priv = nft_set_priv(set);
        struct nft_pipapo_match *m = priv->clone;
        u8 genmask = nft_genmask_next(net);
        struct nft_pipapo_field *f;
        int i, bsize_max, err = 0;

        dup = pipapo_get(net, set, start, genmask);
        if (PTR_ERR(dup) == -ENOENT) {
                if (nft_set_ext_exists(ext, NFT_SET_EXT_KEY_END)) {
                        end = (const u8 *)nft_set_ext_key_end(ext)->data;
                        dup = pipapo_get(net, set, end, nft_genmask_next(net));
                } else {
                        end = start;
                }
        }

        if (PTR_ERR(dup) != -ENOENT) {
                if (IS_ERR(dup))
                        return PTR_ERR(dup);
                *ext2 = &dup->ext;
                return -EEXIST;
        }

        /* Validate */
        nft_pipapo_for_each_field(f, i, m) {
                const u8 *start_p = start, *end_p = end;

                if (f->rules >= (unsigned long)NFT_PIPAPO_RULE0_MAX)
                        return -ENOSPC;

                if (memcmp(start_p, end_p,
                           f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) > 0)
                        return -EINVAL;

                start_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
                end_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
        }

        /* Insert */
        priv->dirty = true;

        bsize_max = m->bsize_max;

        nft_pipapo_for_each_field(f, i, m) {
                int ret;

                rulemap[i].to = f->rules;

                ret = memcmp(start, end,
                             f->groups / NFT_PIPAPO_GROUPS_PER_BYTE);
                if (!ret) {
                        ret = pipapo_insert(f, start,
                                            f->groups * NFT_PIPAPO_GROUP_BITS);
                } else {
                        ret = pipapo_expand(f, start, end,
                                            f->groups * NFT_PIPAPO_GROUP_BITS);
                }

                if (f->bsize > bsize_max)
                        bsize_max = f->bsize;

                rulemap[i].n = ret;

                start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
                end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
        }

        if (!*get_cpu_ptr(m->scratch) || bsize_max > m->bsize_max) {
                put_cpu_ptr(m->scratch);

                err = pipapo_realloc_scratch(m, bsize_max);
                if (err)
                        return err;

                m->bsize_max = bsize_max;
        } else {
                put_cpu_ptr(m->scratch);
        }

        *ext2 = &e->ext;

        pipapo_map(m, rulemap, e);

        return 0;
}

/**
 * pipapo_clone() - Clone matching data to create new working copy
 * @old:        Existing matching data
 *
 * Return: copy of matching data passed as 'old', error pointer on failure
 */
static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
{
        struct nft_pipapo_field *dst, *src;
        struct nft_pipapo_match *new;
        int i;

        new = kmalloc(sizeof(*new) + sizeof(*dst) * old->field_count,
                      GFP_KERNEL);
        if (!new)
                return ERR_PTR(-ENOMEM);

        new->field_count = old->field_count;
        new->bsize_max = old->bsize_max;

        new->scratch = alloc_percpu(*new->scratch);
        if (!new->scratch)
                goto out_scratch;

        for_each_possible_cpu(i)
                *per_cpu_ptr(new->scratch, i) = NULL;

        if (pipapo_realloc_scratch(new, old->bsize_max))
                goto out_scratch_realloc;

        rcu_head_init(&new->rcu);

        src = old->f;
        dst = new->f;

        for (i = 0; i < old->field_count; i++) {
                memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));

                dst->lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS *
                                   src->bsize * sizeof(*dst->lt),
                                   GFP_KERNEL);
                if (!dst->lt)
                        goto out_lt;

                memcpy(dst->lt, src->lt,
                       src->bsize * sizeof(*dst->lt) *
                       src->groups * NFT_PIPAPO_BUCKETS);

                dst->mt = kvmalloc(src->rules * sizeof(*src->mt), GFP_KERNEL);
                if (!dst->mt)
                        goto out_mt;

                memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt));
                src++;
                dst++;
        }

        return new;

out_mt:
        kvfree(dst->lt);
out_lt:
        for (dst--; i > 0; i--) {
                kvfree(dst->mt);
                kvfree(dst->lt);
                dst--;
        }
out_scratch_realloc:
        for_each_possible_cpu(i)
                kfree(*per_cpu_ptr(new->scratch, i));
out_scratch:
        free_percpu(new->scratch);
        kfree(new);

        return ERR_PTR(-ENOMEM);
}

/**
 * pipapo_rules_same_key() - Get number of rules originated from the same entry
 * @f:          Field containing mapping table
 * @first:      Index of first rule in set of rules mapping to same entry
 *
 * Using the fact that all rules in a field that originated from the same entry
 * will map to the same set of rules in the next field, or to the same element
 * reference, return the cardinality of the set of rules that originated from
 * the same entry as the rule with index @first, @first rule included.
 *
 * In pictures:
 *                              rules
 *      field #0                0    1    2    3    4
 *              map to:         0    1   2-4  2-4  5-9
 *                              .    .    .......   . ...
 *                              |    |    |    | \   \
 *                              |    |    |    |  \   \
 *                              |    |    |    |   \   \
 *                              '    '    '    '    '   \
 *      in field #1             0    1    2    3    4    5 ...
 *
 * if this is called for rule 2 on field #0, it will return 3, as also rules 2
 * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
 *
 * For the last field in a set, we can rely on associated entries to map to the
 * same element references.
 *
 * Return: Number of rules that originated from the same entry as @first.
 */
static int pipapo_rules_same_key(struct nft_pipapo_field *f, int first)
{
        struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */
        int r;

        for (r = first; r < f->rules; r++) {
                if (r != first && e != f->mt[r].e)
                        return r - first;

                e = f->mt[r].e;
        }

        if (r != first)
                return r - first;

        return 0;
}

/**
 * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
 * @mt:         Mapping array
 * @rules:      Original amount of rules in mapping table
 * @start:      First rule index to be removed
 * @n:          Amount of rules to be removed
 * @to_offset:  First rule index, in next field, this group of rules maps to
 * @is_last:    If this is the last field, delete reference from mapping array
 *
 * This is used to unmap rules from the mapping table for a single field,
 * maintaining consistency and compactness for the existing ones.
 *
 * In pictures: let's assume that we want to delete rules 2 and 3 from the
 * following mapping array:
 *
 *                 rules
 *               0      1      2      3      4
 *      map to:  4-10   4-10   11-15  11-15  16-18
 *
 * the result will be:
 *
 *                 rules
 *               0      1      2
 *      map to:  4-10   4-10   11-13
 *
 * for fields before the last one. In case this is the mapping table for the
 * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
 *
 *                      rules
 *                        0      1      2      3      4
 *  element pointers:  0x42   0x42   0x33   0x33   0x44
 *
 * the result will be:
 *
 *                      rules
 *                        0      1      2
 *  element pointers:  0x42   0x42   0x44
 */
static void pipapo_unmap(union nft_pipapo_map_bucket *mt, int rules,
                         int start, int n, int to_offset, bool is_last)
{
        int i;

        memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
        memset(mt + rules - n, 0, n * sizeof(*mt));

        if (is_last)
                return;

        for (i = start; i < rules - n; i++)
                mt[i].to -= to_offset;
}

/**
 * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
 * @m:          Matching data
 * @rulemap     Table of rule maps, arrays of first rule and amount of rules
 *              in next field a given entry maps to, for each field
 *
 * For each rule in lookup table buckets mapping to this set of rules, drop
 * all bits set in lookup table mapping. In pictures, assuming we want to drop
 * rules 0 and 1 from this lookup table:
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0    0                                              1,2
 *        1   1,2                                      0
 *        2    0                                      1,2
 *        3    0                              1,2
 *        4  0,1,2
 *        5    0   1   2
 *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
 *
 * rule 2 becomes rule 0, and the result will be:
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0                                                    0
 *        1    0
 *        2                                            0
 *        3                                    0
 *        4    0
 *        5            0
 *        6    0
 *        7    0   0
 *
 * once this is done, call unmap() to drop all the corresponding rule references
 * from mapping tables.
 */
static void pipapo_drop(struct nft_pipapo_match *m,
                        union nft_pipapo_map_bucket rulemap[])
{
        struct nft_pipapo_field *f;
        int i;

        nft_pipapo_for_each_field(f, i, m) {
                int g;

                for (g = 0; g < f->groups; g++) {
                        unsigned long *pos;
                        int b;

                        pos = f->lt + g * NFT_PIPAPO_BUCKETS * f->bsize;

                        for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
                                bitmap_cut(pos, pos, rulemap[i].to,
                                           rulemap[i].n,
                                           f->bsize * BITS_PER_LONG);

                                pos += f->bsize;
                        }
                }

                pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n,
                             rulemap[i + 1].n, i == m->field_count - 1);
                if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) {
                        /* We can ignore this, a failure to shrink tables down
                         * doesn't make tables invalid.
                         */
                        ;
                }
                f->rules -= rulemap[i].n;
        }
}

/**
 * pipapo_gc() - Drop expired entries from set, destroy start and end elements
 * @set:        nftables API set representation
 * @m:          Matching data
 */
static void pipapo_gc(const struct nft_set *set, struct nft_pipapo_match *m)
{
        struct nft_pipapo *priv = nft_set_priv(set);
        int rules_f0, first_rule = 0;

        while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
                union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
                struct nft_pipapo_field *f;
                struct nft_pipapo_elem *e;
                int i, start, rules_fx;

                start = first_rule;
                rules_fx = rules_f0;

                nft_pipapo_for_each_field(f, i, m) {
                        rulemap[i].to = start;
                        rulemap[i].n = rules_fx;

                        if (i < m->field_count - 1) {
                                rules_fx = f->mt[start].n;
                                start = f->mt[start].to;
                        }
                }

                /* Pick the last field, and its last index */
                f--;
                i--;
                e = f->mt[rulemap[i].to].e;
                if (nft_set_elem_expired(&e->ext) &&
                    !nft_set_elem_mark_busy(&e->ext)) {
                        priv->dirty = true;
                        pipapo_drop(m, rulemap);

                        rcu_barrier();
                        nft_set_elem_destroy(set, e, true);

                        /* And check again current first rule, which is now the
                         * first we haven't checked.
                         */
                } else {
                        first_rule += rules_f0;
                }
        }

        priv->last_gc = jiffies;
}

/**
 * pipapo_free_fields() - Free per-field tables contained in matching data
 * @m:          Matching data
 */
static void pipapo_free_fields(struct nft_pipapo_match *m)
{
        struct nft_pipapo_field *f;
        int i;

        nft_pipapo_for_each_field(f, i, m) {
                kvfree(f->lt);
                kvfree(f->mt);
        }
}

/**
 * pipapo_reclaim_match - RCU callback to free fields from old matching data
 * @rcu:        RCU head
 */
static void pipapo_reclaim_match(struct rcu_head *rcu)
{
        struct nft_pipapo_match *m;
        int i;

        m = container_of(rcu, struct nft_pipapo_match, rcu);

        for_each_possible_cpu(i)
                kfree(*per_cpu_ptr(m->scratch, i));

        free_percpu(m->scratch);

        pipapo_free_fields(m);

        kfree(m);
}

/**
 * pipapo_commit() - Replace lookup data with current working copy
 * @set:        nftables API set representation
 *
 * While at it, check if we should perform garbage collection on the working
 * copy before committing it for lookup, and don't replace the table if the
 * working copy doesn't have pending changes.
 *
 * We also need to create a new working copy for subsequent insertions and
 * deletions.
 */
static void pipapo_commit(const struct nft_set *set)
{
        struct nft_pipapo *priv = nft_set_priv(set);
        struct nft_pipapo_match *new_clone, *old;

        if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
                pipapo_gc(set, priv->clone);

        if (!priv->dirty)
                return;

        new_clone = pipapo_clone(priv->clone);
        if (IS_ERR(new_clone))
                return;

        priv->dirty = false;

        old = rcu_access_pointer(priv->match);
        rcu_assign_pointer(priv->match, priv->clone);
        if (old)
                call_rcu(&old->rcu, pipapo_reclaim_match);

        priv->clone = new_clone;
}

/**
 * nft_pipapo_activate() - Mark element reference as active given key, commit
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @elem:       nftables API element representation containing key data
 *
 * On insertion, elements are added to a copy of the matching data currently
 * in use for lookups, and not directly inserted into current lookup data, so
 * we'll take care of that by calling pipapo_commit() here. Both
 * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
 * element, hence we can't purpose either one as a real commit operation.
 */
static void nft_pipapo_activate(const struct net *net,
                                const struct nft_set *set,
                                const struct nft_set_elem *elem)
{
        struct nft_pipapo_elem *e;

        e = pipapo_get(net, set, (const u8 *)elem->key.val.data, 0);
        if (IS_ERR(e))
                return;

        nft_set_elem_change_active(net, set, &e->ext);
        nft_set_elem_clear_busy(&e->ext);

        pipapo_commit(set);
}

/**
 * pipapo_deactivate() - Check that element is in set, mark as inactive
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @data:       Input key data
 * @ext:        nftables API extension pointer, used to check for end element
 *
 * This is a convenience function that can be called from both
 * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same
 * operation.
 *
 * Return: deactivated element if found, NULL otherwise.
 */
static void *pipapo_deactivate(const struct net *net, const struct nft_set *set,
                               const u8 *data, const struct nft_set_ext *ext)
{
        struct nft_pipapo_elem *e;

        e = pipapo_get(net, set, data, nft_genmask_next(net));
        if (IS_ERR(e))
                return NULL;

        nft_set_elem_change_active(net, set, &e->ext);

        return e;
}

/**
 * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @elem:       nftables API element representation containing key data
 *
 * Return: deactivated element if found, NULL otherwise.
 */
static void *nft_pipapo_deactivate(const struct net *net,
                                   const struct nft_set *set,
                                   const struct nft_set_elem *elem)
{
        const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);

        return pipapo_deactivate(net, set, (const u8 *)elem->key.val.data, ext);
}

/**
 * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @elem:       nftables API element representation containing key data
 *
 * This is functionally the same as nft_pipapo_deactivate(), with a slightly
 * different interface, and it's also called once for each element in a set
 * being flushed, so we can't implement, strictly speaking, a flush operation,
 * which would otherwise be as simple as allocating an empty copy of the
 * matching data.
 *
 * Note that we could in theory do that, mark the set as flushed, and ignore
 * subsequent calls, but we would leak all the elements after the first one,
 * because they wouldn't then be freed as result of API calls.
 *
 * Return: true if element was found and deactivated.
 */
static bool nft_pipapo_flush(const struct net *net, const struct nft_set *set,
                             void *elem)
{
        struct nft_pipapo_elem *e = elem;

        return pipapo_deactivate(net, set, (const u8 *)nft_set_ext_key(&e->ext),
                                 &e->ext);
}

/**
 * pipapo_get_boundaries() - Get byte interval for associated rules
 * @f:          Field including lookup table
 * @first_rule: First rule (lowest index)
 * @rule_count: Number of associated rules
 * @left:       Byte expression for left boundary (start of range)
 * @right:      Byte expression for right boundary (end of range)
 *
 * Given the first rule and amount of rules that originated from the same entry,
 * build the original range associated with the entry, and calculate the length
 * of the originating netmask.
 *
 * In pictures:
 *
 *                     bucket
 *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 *        0                                                   1,2
 *        1   1,2
 *        2                                           1,2
 *        3                                   1,2
 *        4   1,2
 *        5        1   2
 *        6   1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 *        7   1,2 1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1
 *
 * this is the lookup table corresponding to the IPv4 range
 * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
 * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
 *
 * This function fills @left and @right with the byte values of the leftmost
 * and rightmost bucket indices for the lowest and highest rule indices,
 * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
 * nibbles:
 *   left:  < 12, 0, 10, 8, 0, 1, 0, 0 >
 *   right: < 12, 0, 10, 8, 0, 2, 2, 1 >
 * corresponding to bytes:
 *   left:  < 192, 168, 1, 0 >
 *   right: < 192, 168, 2, 1 >
 * with mask length irrelevant here, unused on return, as the range is already
 * defined by its start and end points. The mask length is relevant for a single
 * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
 * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
 * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
 * between leftmost and rightmost bucket indices for each group, would be 24.
 *
 * Return: mask length, in bits.
 */
static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
                                 int rule_count, u8 *left, u8 *right)
{
        u8 *l = left, *r = right;
        int g, mask_len = 0;

        for (g = 0; g < f->groups; g++) {
                int b, x0, x1;

                x0 = -1;
                x1 = -1;
                for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
                        unsigned long *pos;

                        pos = f->lt + (g * NFT_PIPAPO_BUCKETS + b) * f->bsize;
                        if (test_bit(first_rule, pos) && x0 == -1)
                                x0 = b;
                        if (test_bit(first_rule + rule_count - 1, pos))
                                x1 = b;
                }

                if (g % 2) {
                        *(l++) |= x0 & 0x0f;
                        *(r++) |= x1 & 0x0f;
                } else {
                        *l |= x0 << 4;
                        *r |= x1 << 4;
                }

                if (x1 - x0 == 0)
                        mask_len += 4;
                else if (x1 - x0 == 1)
                        mask_len += 3;
                else if (x1 - x0 == 3)
                        mask_len += 2;
                else if (x1 - x0 == 7)
                        mask_len += 1;
        }

        return mask_len;
}

/**
 * pipapo_match_field() - Match rules against byte ranges
 * @f:          Field including the lookup table
 * @first_rule: First of associated rules originating from same entry
 * @rule_count: Amount of associated rules
 * @start:      Start of range to be matched
 * @end:        End of range to be matched
 *
 * Return: true on match, false otherwise.
 */
static bool pipapo_match_field(struct nft_pipapo_field *f,
                               int first_rule, int rule_count,
                               const u8 *start, const u8 *end)
{
        u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 };
        u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 };

        pipapo_get_boundaries(f, first_rule, rule_count, left, right);

        return !memcmp(start, left, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) &&
               !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE);
}

/**
 * nft_pipapo_remove() - Remove element given key, commit
 * @net:        Network namespace
 * @set:        nftables API set representation
 * @elem:       nftables API element representation containing key data
 *
 * Similarly to nft_pipapo_activate(), this is used as commit operation by the
 * API, but it's called once per element in the pending transaction, so we can't
 * implement this as a single commit operation. Closest we can get is to remove
 * the matched element here, if any, and commit the updated matching data.
 */
static void nft_pipapo_remove(const struct net *net, const struct nft_set *set,
                              const struct nft_set_elem *elem)
{
        struct nft_pipapo *priv = nft_set_priv(set);
        struct nft_pipapo_match *m = priv->clone;
        struct nft_pipapo_elem *e = elem->priv;
        int rules_f0, first_rule = 0;
        const u8 *data;

        data = (const u8 *)nft_set_ext_key(&e->ext);

        e = pipapo_get(net, set, data, 0);
        if (IS_ERR(e))
                return;

        while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
                union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
                const u8 *match_start, *match_end;
                struct nft_pipapo_field *f;
                int i, start, rules_fx;

                match_start = data;
                match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data;

                start = first_rule;
                rules_fx = rules_f0;

                nft_pipapo_for_each_field(f, i, m) {
                        if (!pipapo_match_field(f, start, rules_fx,
                                                match_start, match_end))
                                break;

                        rulemap[i].to = start;
                        rulemap[i].n = rules_fx;

                        rules_fx = f->mt[start].n;
                        start = f->mt[start].to;

                        match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
                        match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
                }

                if (i == m->field_count) {
                        priv->dirty = true;
                        pipapo_drop(m, rulemap);
                        pipapo_commit(set);
                        return;
                }

                first_rule += rules_f0;
        }
}

/**
 * nft_pipapo_walk() - Walk over elements
 * @ctx:        nftables API context
 * @set:        nftables API set representation
 * @iter:       Iterator
 *
 * As elements are referenced in the mapping array for the last field, directly
 * scan that array: there's no need to follow rule mappings from the first
 * field.
 */
static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set,
                            struct nft_set_iter *iter)
{
        struct nft_pipapo *priv = nft_set_priv(set);
        struct nft_pipapo_match *m;
        struct nft_pipapo_field *f;
        int i, r;

        rcu_read_lock();
        m = rcu_dereference(priv->match);

        if (unlikely(!m))
                goto out;

        for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
                ;

        for (r = 0; r < f->rules; r++) {
                struct nft_pipapo_elem *e;
                struct nft_set_elem elem;

                if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
                        continue;

                if (iter->count < iter->skip)
                        goto cont;

                e = f->mt[r].e;
                if (nft_set_elem_expired(&e->ext))
                        goto cont;

                elem.priv = e;

                iter->err = iter->fn(ctx, set, iter, &elem);
                if (iter->err < 0)
                        goto out;

cont:
                iter->count++;
        }

out:
        rcu_read_unlock();
}

/**
 * nft_pipapo_privsize() - Return the size of private data for the set
 * @nla:        netlink attributes, ignored as size doesn't depend on them
 * @desc:       Set description, ignored as size doesn't depend on it
 *
 * Return: size of private data for this set implementation, in bytes
 */
static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
                               const struct nft_set_desc *desc)
{
        return sizeof(struct nft_pipapo);
}

/**
 * nft_pipapo_estimate() - Estimate set size, space and lookup complexity
 * @desc:       Set description, element count and field description used here
 * @features:   Flags: NFT_SET_INTERVAL needs to be there
 * @est:        Storage for estimation data
 *
 * The size for this set type can vary dramatically, as it depends on the number
 * of rules (composing netmasks) the entries expand to. We compute the worst
 * case here.
 *
 * In general, for a non-ranged entry or a single composing netmask, we need
 * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
 * is, each input bit needs four bits of matching data), plus a bucket in the
 * mapping table for each field.
 *
 * Return: true only for compatible range concatenations
 */
static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
                                struct nft_set_estimate *est)
{
        unsigned long entry_size;
        int i;

        if (!(features & NFT_SET_INTERVAL) || desc->field_count <= 1)
                return false;

        for (i = 0, entry_size = 0; i < desc->field_count; i++) {
                unsigned long rules;

                if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
                        return false;

                /* Worst-case ranges for each concatenated field: each n-bit
                 * field can expand to up to n * 2 rules in each bucket, and
                 * each rule also needs a mapping bucket.
                 */
                rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
                entry_size += rules * NFT_PIPAPO_BUCKETS / BITS_PER_BYTE;
                entry_size += rules * sizeof(union nft_pipapo_map_bucket);
        }

        /* Rules in lookup and mapping tables are needed for each entry */
        est->size = desc->size * entry_size;
        if (est->size && div_u64(est->size, desc->size) != entry_size)
                return false;

        est->size += sizeof(struct nft_pipapo) +
                     sizeof(struct nft_pipapo_match) * 2;

        est->size += sizeof(struct nft_pipapo_field) * desc->field_count;

        est->lookup = NFT_SET_CLASS_O_LOG_N;

        est->space = NFT_SET_CLASS_O_N;

        return true;
}

/**
 * nft_pipapo_init() - Initialise data for a set instance
 * @set:        nftables API set representation
 * @desc:       Set description
 * @nla:        netlink attributes
 *
 * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
 * attributes, initialise internal set parameters, current instance of matching
 * data and a copy for subsequent insertions.
 *
 * Return: 0 on success, negative error code on failure.
 */
static int nft_pipapo_init(const struct nft_set *set,
                           const struct nft_set_desc *desc,
                           const struct nlattr * const nla[])
{
        struct nft_pipapo *priv = nft_set_priv(set);
        struct nft_pipapo_match *m;
        struct nft_pipapo_field *f;
        int err, i;

        if (desc->field_count > NFT_PIPAPO_MAX_FIELDS)
                return -EINVAL;

        m = kmalloc(sizeof(*priv->match) + sizeof(*f) * desc->field_count,
                    GFP_KERNEL);
        if (!m)
                return -ENOMEM;

        m->field_count = desc->field_count;
        m->bsize_max = 0;

        m->scratch = alloc_percpu(unsigned long *);
        if (!m->scratch) {
                err = -ENOMEM;
                goto out_free;
        }
        for_each_possible_cpu(i)
                *per_cpu_ptr(m->scratch, i) = NULL;

        rcu_head_init(&m->rcu);

        nft_pipapo_for_each_field(f, i, m) {
                f->groups = desc->field_len[i] * NFT_PIPAPO_GROUPS_PER_BYTE;
                priv->groups += f->groups;

                priv->width += round_up(desc->field_len[i], sizeof(u32));

                f->bsize = 0;
                f->rules = 0;
                f->lt = NULL;
                f->mt = NULL;
        }

        /* Create an initial clone of matching data for next insertion */
        priv->clone = pipapo_clone(m);
        if (IS_ERR(priv->clone)) {
                err = PTR_ERR(priv->clone);
                goto out_free;
        }

        priv->dirty = false;

        rcu_assign_pointer(priv->match, m);

        return 0;

out_free:
        free_percpu(m->scratch);
        kfree(m);

        return err;
}

/**
 * nft_pipapo_destroy() - Free private data for set and all committed elements
 * @set:        nftables API set representation
 */
static void nft_pipapo_destroy(const struct nft_set *set)
{
        struct nft_pipapo *priv = nft_set_priv(set);
        struct nft_pipapo_match *m;
        struct nft_pipapo_field *f;
        int i, r, cpu;

        m = rcu_dereference_protected(priv->match, true);
        if (m) {
                rcu_barrier();

                for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
                        ;

                for (r = 0; r < f->rules; r++) {
                        struct nft_pipapo_elem *e;

                        if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
                                continue;

                        e = f->mt[r].e;

                        nft_set_elem_destroy(set, e, true);
                }

                for_each_possible_cpu(cpu)
                        kfree(*per_cpu_ptr(m->scratch, cpu));
                free_percpu(m->scratch);

                pipapo_free_fields(m);
                kfree(m);
                priv->match = NULL;
        }

        if (priv->clone) {
                for_each_possible_cpu(cpu)
                        kfree(*per_cpu_ptr(priv->clone->scratch, cpu));
                free_percpu(priv->clone->scratch);

                pipapo_free_fields(priv->clone);
                kfree(priv->clone);
                priv->clone = NULL;
        }
}

/**
 * nft_pipapo_gc_init() - Initialise garbage collection
 * @set:        nftables API set representation
 *
 * Instead of actually setting up a periodic work for garbage collection, as
 * this operation requires a swap of matching data with the working copy, we'll
 * do that opportunistically with other commit operations if the interval is
 * elapsed, so we just need to set the current jiffies timestamp here.
 */
static void nft_pipapo_gc_init(const struct nft_set *set)
{
        struct nft_pipapo *priv = nft_set_priv(set);

        priv->last_gc = jiffies;
}

struct nft_set_type nft_set_pipapo_type __read_mostly = {
        .owner          = THIS_MODULE,
        .features       = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
                          NFT_SET_TIMEOUT,
        .ops            = {
                .lookup         = nft_pipapo_lookup,
                .insert         = nft_pipapo_insert,
                .activate       = nft_pipapo_activate,
                .deactivate     = nft_pipapo_deactivate,
                .flush          = nft_pipapo_flush,
                .remove         = nft_pipapo_remove,
                .walk           = nft_pipapo_walk,
                .get            = nft_pipapo_get,
                .privsize       = nft_pipapo_privsize,
                .estimate       = nft_pipapo_estimate,
                .init           = nft_pipapo_init,
                .destroy        = nft_pipapo_destroy,
                .gc_init        = nft_pipapo_gc_init,
                .elemsize       = offsetof(struct nft_pipapo_elem, ext),
        },
};