net/netfilter/nft_set_pipapo.h

0001 // SPDX-License-Identifier: GPL-2.0-only
0002
0003 #ifndef _NFT_SET_PIPAPO_H
0004
0005 #include <linux/log2.h>
0006 #include <net/ipv6.h>           /* For the maximum length of a field */
0007
0008 /* Count of concatenated fields depends on count of 32-bit nftables registers */
0009 #define NFT_PIPAPO_MAX_FIELDS       NFT_REG32_COUNT
0010
0011 /* Restrict usage to multiple fields, make sure rbtree is used otherwise */
0012 #define NFT_PIPAPO_MIN_FIELDS       2
0013
0014 /* Largest supported field size */
0015 #define NFT_PIPAPO_MAX_BYTES        (sizeof(struct in6_addr))
0016 #define NFT_PIPAPO_MAX_BITS     (NFT_PIPAPO_MAX_BYTES * BITS_PER_BYTE)
0017
0018 /* Bits to be grouped together in table buckets depending on set size */
0019 #define NFT_PIPAPO_GROUP_BITS_INIT  NFT_PIPAPO_GROUP_BITS_SMALL_SET
0020 #define NFT_PIPAPO_GROUP_BITS_SMALL_SET 8
0021 #define NFT_PIPAPO_GROUP_BITS_LARGE_SET 4
0022 #define NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4                \
0023     BUILD_BUG_ON((NFT_PIPAPO_GROUP_BITS_SMALL_SET != 8) ||      \
0024              (NFT_PIPAPO_GROUP_BITS_LARGE_SET != 4))
0025 #define NFT_PIPAPO_GROUPS_PER_BYTE(f)   (BITS_PER_BYTE / (f)->bb)
0026
0027 /* If a lookup table gets bigger than NFT_PIPAPO_LT_SIZE_HIGH, switch to the
0028  * small group width, and switch to the big group width if the table gets
0029  * smaller than NFT_PIPAPO_LT_SIZE_LOW.
0030  *
0031  * Picking 2MiB as threshold (for a single table) avoids as much as possible
0032  * crossing page boundaries on most architectures (x86-64 and MIPS huge pages,
0033  * ARMv7 supersections, POWER "large" pages, SPARC Level 1 regions, etc.), which
0034  * keeps performance nice in case kvmalloc() gives us non-contiguous areas.
0035  */
0036 #define NFT_PIPAPO_LT_SIZE_THRESHOLD    (1 << 21)
0037 #define NFT_PIPAPO_LT_SIZE_HYSTERESIS   (1 << 16)
0038 #define NFT_PIPAPO_LT_SIZE_HIGH     NFT_PIPAPO_LT_SIZE_THRESHOLD
0039 #define NFT_PIPAPO_LT_SIZE_LOW      NFT_PIPAPO_LT_SIZE_THRESHOLD -  \
0040                     NFT_PIPAPO_LT_SIZE_HYSTERESIS
0041
0042 /* Fields are padded to 32 bits in input registers */
0043 #define NFT_PIPAPO_GROUPS_PADDED_SIZE(f)                \
0044     (round_up((f)->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f), sizeof(u32)))
0045 #define NFT_PIPAPO_GROUPS_PADDING(f)                    \
0046     (NFT_PIPAPO_GROUPS_PADDED_SIZE(f) - (f)->groups /       \
0047                         NFT_PIPAPO_GROUPS_PER_BYTE(f))
0048
0049 /* Number of buckets given by 2 ^ n, with n bucket bits */
0050 #define NFT_PIPAPO_BUCKETS(bb)      (1 << (bb))
0051
0052 /* Each n-bit range maps to up to n * 2 rules */
0053 #define NFT_PIPAPO_MAP_NBITS        (const_ilog2(NFT_PIPAPO_MAX_BITS * 2))
0054
0055 /* Use the rest of mapping table buckets for rule indices, but it makes no sense
0056  * to exceed 32 bits
0057  */
0058 #if BITS_PER_LONG == 64
0059 #define NFT_PIPAPO_MAP_TOBITS       32
0060 #else
0061 #define NFT_PIPAPO_MAP_TOBITS       (BITS_PER_LONG - NFT_PIPAPO_MAP_NBITS)
0062 #endif
0063
0064 /* ...which gives us the highest allowed index for a rule */
0065 #define NFT_PIPAPO_RULE0_MAX        ((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
0066                     - (1UL << NFT_PIPAPO_MAP_NBITS))
0067
0068 /* Definitions for vectorised implementations */
0069 #ifdef NFT_PIPAPO_ALIGN
0070 #define NFT_PIPAPO_ALIGN_HEADROOM                   \
0071     (NFT_PIPAPO_ALIGN - ARCH_KMALLOC_MINALIGN)
0072 #define NFT_PIPAPO_LT_ALIGN(lt)     (PTR_ALIGN((lt), NFT_PIPAPO_ALIGN))
0073 #define NFT_PIPAPO_LT_ASSIGN(field, x)                  \
0074     do {                                \
0075         (field)->lt_aligned = NFT_PIPAPO_LT_ALIGN(x);       \
0076         (field)->lt = (x);                  \
0077     } while (0)
0078 #else
0079 #define NFT_PIPAPO_ALIGN_HEADROOM   0
0080 #define NFT_PIPAPO_LT_ALIGN(lt)     (lt)
0081 #define NFT_PIPAPO_LT_ASSIGN(field, x)  ((field)->lt = (x))
0082 #endif /* NFT_PIPAPO_ALIGN */
0083
0084 #define nft_pipapo_for_each_field(field, index, match)      \
0085     for ((field) = (match)->f, (index) = 0;         \
0086          (index) < (match)->field_count;            \
0087          (index)++, (field)++)
0088
0089 /**
0090  * union nft_pipapo_map_bucket - Bucket of mapping table
0091  * @to:     First rule number (in next field) this rule maps to
0092  * @n:      Number of rules (in next field) this rule maps to
0093  * @e:      If there's no next field, pointer to element this rule maps to
0094  */
0095 union nft_pipapo_map_bucket {
0096     struct {
0097 #if BITS_PER_LONG == 64
0098         static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
0099         u32 to;
0100
0101         static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
0102         u32 n;
0103 #else
0104         unsigned long to:NFT_PIPAPO_MAP_TOBITS;
0105         unsigned long  n:NFT_PIPAPO_MAP_NBITS;
0106 #endif
0107     };
0108     struct nft_pipapo_elem *e;
0109 };
0110
0111 /**
0112  * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
0113  * @groups: Amount of bit groups
0114  * @rules:  Number of inserted rules
0115  * @bsize:  Size of each bucket in lookup table, in longs
0116  * @bb:     Number of bits grouped together in lookup table buckets
0117  * @lt:     Lookup table: 'groups' rows of buckets
0118  * @lt_aligned: Version of @lt aligned to NFT_PIPAPO_ALIGN bytes
0119  * @mt:     Mapping table: one bucket per rule
0120  */
0121 struct nft_pipapo_field {
0122     int groups;
0123     unsigned long rules;
0124     size_t bsize;
0125     int bb;
0126 #ifdef NFT_PIPAPO_ALIGN
0127     unsigned long *lt_aligned;
0128 #endif
0129     unsigned long *lt;
0130     union nft_pipapo_map_bucket *mt;
0131 };
0132
0133 /**
0134  * struct nft_pipapo_match - Data used for lookup and matching
0135  * @field_count     Amount of fields in set
0136  * @scratch:        Preallocated per-CPU maps for partial matching results
0137  * @scratch_aligned:    Version of @scratch aligned to NFT_PIPAPO_ALIGN bytes
0138  * @bsize_max:      Maximum lookup table bucket size of all fields, in longs
0139  * @rcu         Matching data is swapped on commits
0140  * @f:          Fields, with lookup and mapping tables
0141  */
0142 struct nft_pipapo_match {
0143     int field_count;
0144 #ifdef NFT_PIPAPO_ALIGN
0145     unsigned long * __percpu *scratch_aligned;
0146 #endif
0147     unsigned long * __percpu *scratch;
0148     size_t bsize_max;
0149     struct rcu_head rcu;
0150     struct nft_pipapo_field f[];
0151 };
0152
0153 /**
0154  * struct nft_pipapo - Representation of a set
0155  * @match:  Currently in-use matching data
0156  * @clone:  Copy where pending insertions and deletions are kept
0157  * @width:  Total bytes to be matched for one packet, including padding
0158  * @dirty:  Working copy has pending insertions or deletions
0159  * @last_gc:    Timestamp of last garbage collection run, jiffies
0160  */
0161 struct nft_pipapo {
0162     struct nft_pipapo_match __rcu *match;
0163     struct nft_pipapo_match *clone;
0164     int width;
0165     bool dirty;
0166     unsigned long last_gc;
0167 };
0168
0169 struct nft_pipapo_elem;
0170
0171 /**
0172  * struct nft_pipapo_elem - API-facing representation of single set element
0173  * @ext:    nftables API extensions
0174  */
0175 struct nft_pipapo_elem {
0176     struct nft_set_ext ext;
0177 };
0178
0179 int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
0180           union nft_pipapo_map_bucket *mt, bool match_only);
0181
0182 /**
0183  * pipapo_and_field_buckets_4bit() - Intersect 4-bit buckets
0184  * @f:      Field including lookup table
0185  * @dst:    Area to store result
0186  * @data:   Input data selecting table buckets
0187  */
0188 static inline void pipapo_and_field_buckets_4bit(struct nft_pipapo_field *f,
0189                          unsigned long *dst,
0190                          const u8 *data)
0191 {
0192     unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
0193     int group;
0194
0195     for (group = 0; group < f->groups; group += BITS_PER_BYTE / 4, data++) {
0196         u8 v;
0197
0198         v = *data >> 4;
0199         __bitmap_and(dst, dst, lt + v * f->bsize,
0200                  f->bsize * BITS_PER_LONG);
0201         lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
0202
0203         v = *data & 0x0f;
0204         __bitmap_and(dst, dst, lt + v * f->bsize,
0205                  f->bsize * BITS_PER_LONG);
0206         lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
0207     }
0208 }
0209
0210 /**
0211  * pipapo_and_field_buckets_8bit() - Intersect 8-bit buckets
0212  * @f:      Field including lookup table
0213  * @dst:    Area to store result
0214  * @data:   Input data selecting table buckets
0215  */
0216 static inline void pipapo_and_field_buckets_8bit(struct nft_pipapo_field *f,
0217                          unsigned long *dst,
0218                          const u8 *data)
0219 {
0220     unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
0221     int group;
0222
0223     for (group = 0; group < f->groups; group++, data++) {
0224         __bitmap_and(dst, dst, lt + *data * f->bsize,
0225                  f->bsize * BITS_PER_LONG);
0226         lt += f->bsize * NFT_PIPAPO_BUCKETS(8);
0227     }
0228 }
0229
0230 /**
0231  * pipapo_estimate_size() - Estimate worst-case for set size
0232  * @desc:   Set description, element count and field description used here
0233  *
0234  * The size for this set type can vary dramatically, as it depends on the number
0235  * of rules (composing netmasks) the entries expand to. We compute the worst
0236  * case here.
0237  *
0238  * In general, for a non-ranged entry or a single composing netmask, we need
0239  * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
0240  * is, each input bit needs four bits of matching data), plus a bucket in the
0241  * mapping table for each field.
0242  *
0243  * Return: worst-case set size in bytes, 0 on any overflow
0244  */
0245 static u64 pipapo_estimate_size(const struct nft_set_desc *desc)
0246 {
0247     unsigned long entry_size;
0248     u64 size;
0249     int i;
0250
0251     for (i = 0, entry_size = 0; i < desc->field_count; i++) {
0252         unsigned long rules;
0253
0254         if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
0255             return 0;
0256
0257         /* Worst-case ranges for each concatenated field: each n-bit
0258          * field can expand to up to n * 2 rules in each bucket, and
0259          * each rule also needs a mapping bucket.
0260          */
0261         rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
0262         entry_size += rules *
0263                   NFT_PIPAPO_BUCKETS(NFT_PIPAPO_GROUP_BITS_INIT) /
0264                   BITS_PER_BYTE;
0265         entry_size += rules * sizeof(union nft_pipapo_map_bucket);
0266     }
0267
0268     /* Rules in lookup and mapping tables are needed for each entry */
0269     size = desc->size * entry_size;
0270     if (size && div_u64(size, desc->size) != entry_size)
0271         return 0;
0272
0273     size += sizeof(struct nft_pipapo) + sizeof(struct nft_pipapo_match) * 2;
0274
0275     size += sizeof(struct nft_pipapo_field) * desc->field_count;
0276
0277     return size;
0278 }
0279
0280 #endif /* _NFT_SET_PIPAPO_H */