net/netfilter/nft_set_pipapo.h

   1 // SPDX-License-Identifier: GPL-2.0-only
   2
   3 #ifndef _NFT_SET_PIPAPO_H
   4
   5 #include <linux/log2.h>
   6 #include <net/ipv6.h>                   /* For the maximum length of a field */
   7
   8 /* Count of concatenated fields depends on count of 32-bit nftables registers */
   9 #define NFT_PIPAPO_MAX_FIELDS           NFT_REG32_COUNT
  10
  11 /* Restrict usage to multiple fields, make sure rbtree is used otherwise */
  12 #define NFT_PIPAPO_MIN_FIELDS           2
  13
  14 /* Largest supported field size */
  15 #define NFT_PIPAPO_MAX_BYTES            (sizeof(struct in6_addr))
  16 #define NFT_PIPAPO_MAX_BITS             (NFT_PIPAPO_MAX_BYTES * BITS_PER_BYTE)
  17
  18 /* Bits to be grouped together in table buckets depending on set size */
  19 #define NFT_PIPAPO_GROUP_BITS_INIT      NFT_PIPAPO_GROUP_BITS_SMALL_SET
  20 #define NFT_PIPAPO_GROUP_BITS_SMALL_SET 8
  21 #define NFT_PIPAPO_GROUP_BITS_LARGE_SET 4
  22 #define NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4                                \
  23         BUILD_BUG_ON((NFT_PIPAPO_GROUP_BITS_SMALL_SET != 8) ||          \
  24                      (NFT_PIPAPO_GROUP_BITS_LARGE_SET != 4))
  25 #define NFT_PIPAPO_GROUPS_PER_BYTE(f)   (BITS_PER_BYTE / (f)->bb)
  26
  27 /* If a lookup table gets bigger than NFT_PIPAPO_LT_SIZE_HIGH, switch to the
  28  * small group width, and switch to the big group width if the table gets
  29  * smaller than NFT_PIPAPO_LT_SIZE_LOW.
  30  *
  31  * Picking 2MiB as threshold (for a single table) avoids as much as possible
  32  * crossing page boundaries on most architectures (x86-64 and MIPS huge pages,
  33  * ARMv7 supersections, POWER "large" pages, SPARC Level 1 regions, etc.), which
  34  * keeps performance nice in case kvmalloc() gives us non-contiguous areas.
  35  */
  36 #define NFT_PIPAPO_LT_SIZE_THRESHOLD    (1 << 21)
  37 #define NFT_PIPAPO_LT_SIZE_HYSTERESIS   (1 << 16)
  38 #define NFT_PIPAPO_LT_SIZE_HIGH         NFT_PIPAPO_LT_SIZE_THRESHOLD
  39 #define NFT_PIPAPO_LT_SIZE_LOW          NFT_PIPAPO_LT_SIZE_THRESHOLD -  \
  40                                         NFT_PIPAPO_LT_SIZE_HYSTERESIS
  41
  42 /* Fields are padded to 32 bits in input registers */
  43 #define NFT_PIPAPO_GROUPS_PADDED_SIZE(f)                                \
  44         (round_up((f)->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f), sizeof(u32)))
  45 #define NFT_PIPAPO_GROUPS_PADDING(f)                                    \
  46         (NFT_PIPAPO_GROUPS_PADDED_SIZE(f) - (f)->groups /               \
  47                                             NFT_PIPAPO_GROUPS_PER_BYTE(f))
  48
  49 /* Number of buckets given by 2 ^ n, with n bucket bits */
  50 #define NFT_PIPAPO_BUCKETS(bb)          (1 << (bb))
  51
  52 /* Each n-bit range maps to up to n * 2 rules */
  53 #define NFT_PIPAPO_MAP_NBITS            (const_ilog2(NFT_PIPAPO_MAX_BITS * 2))
  54
  55 /* Use the rest of mapping table buckets for rule indices, but it makes no sense
  56  * to exceed 32 bits
  57  */
  58 #if BITS_PER_LONG == 64
  59 #define NFT_PIPAPO_MAP_TOBITS           32
  60 #else
  61 #define NFT_PIPAPO_MAP_TOBITS           (BITS_PER_LONG - NFT_PIPAPO_MAP_NBITS)
  62 #endif
  63
  64 /* ...which gives us the highest allowed index for a rule */
  65 #define NFT_PIPAPO_RULE0_MAX            ((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
  66                                         - (1UL << NFT_PIPAPO_MAP_NBITS))
  67
  68 /* Definitions for vectorised implementations */
  69 #ifdef NFT_PIPAPO_ALIGN
  70 #define NFT_PIPAPO_ALIGN_HEADROOM                                       \
  71         (NFT_PIPAPO_ALIGN - ARCH_KMALLOC_MINALIGN)
  72 #define NFT_PIPAPO_LT_ALIGN(lt)         (PTR_ALIGN((lt), NFT_PIPAPO_ALIGN))
  73 #else
  74 #define NFT_PIPAPO_ALIGN_HEADROOM       0
  75 #define NFT_PIPAPO_LT_ALIGN(lt)         (lt)
  76 #endif /* NFT_PIPAPO_ALIGN */
  77
  78 #define nft_pipapo_for_each_field(field, index, match)          \
  79         for ((field) = (match)->f, (index) = 0;                 \
  80              (index) < (match)->field_count;                    \
  81              (index)++, (field)++)
  82
  83 /**
  84  * union nft_pipapo_map_bucket - Bucket of mapping table
  85  * @to:         First rule number (in next field) this rule maps to
  86  * @n:          Number of rules (in next field) this rule maps to
  87  * @e:          If there's no next field, pointer to element this rule maps to
  88  */
  89 union nft_pipapo_map_bucket {
  90         struct {
  91 #if BITS_PER_LONG == 64
  92                 static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
  93                 u32 to;
  94
  95                 static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
  96                 u32 n;
  97 #else
  98                 unsigned long to:NFT_PIPAPO_MAP_TOBITS;
  99                 unsigned long  n:NFT_PIPAPO_MAP_NBITS;
 100 #endif
 101         };
 102         struct nft_pipapo_elem *e;
 103 };
 104
 105 /**
 106  * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
 107  * @rules:      Number of inserted rules
 108  * @bsize:      Size of each bucket in lookup table, in longs
 109  * @rules_alloc: Number of allocated rules, always >= rules
 110  * @groups:     Amount of bit groups
 111  * @bb:         Number of bits grouped together in lookup table buckets
 112  * @lt:         Lookup table: 'groups' rows of buckets
 113  * @mt:         Mapping table: one bucket per rule
 114  */
 115 struct nft_pipapo_field {
 116         unsigned int rules;
 117         unsigned int bsize;
 118         unsigned int rules_alloc;
 119         u8 groups;
 120         u8 bb;
 121         unsigned long *lt;
 122         union nft_pipapo_map_bucket *mt;
 123 };
 124
 125 /**
 126  * struct nft_pipapo_scratch - percpu data used for lookup and matching
 127  * @map_index:  Current working bitmap index, toggled between field matches
 128  * @align_off:  Offset to get the originally allocated address
 129  * @map:        store partial matching results during lookup
 130  */
 131 struct nft_pipapo_scratch {
 132         u8 map_index;
 133         u32 align_off;
 134         unsigned long map[];
 135 };
 136
 137 /**
 138  * struct nft_pipapo_match - Data used for lookup and matching
 139  * @field_count:        Amount of fields in set
 140  * @bsize_max:          Maximum lookup table bucket size of all fields, in longs
 141  * @scratch:            Preallocated per-CPU maps for partial matching results
 142  * @rcu:                Matching data is swapped on commits
 143  * @f:                  Fields, with lookup and mapping tables
 144  */
 145 struct nft_pipapo_match {
 146         u8 field_count;
 147         unsigned int bsize_max;
 148         struct nft_pipapo_scratch * __percpu *scratch;
 149         struct rcu_head rcu;
 150         struct nft_pipapo_field f[] __counted_by(field_count);
 151 };
 152
 153 /**
 154  * struct nft_pipapo - Representation of a set
 155  * @match:      Currently in-use matching data
 156  * @clone:      Copy where pending insertions and deletions are kept
 157  * @width:      Total bytes to be matched for one packet, including padding
 158  * @dirty:      Working copy has pending insertions or deletions
 159  * @last_gc:    Timestamp of last garbage collection run, jiffies
 160  */
 161 struct nft_pipapo {
 162         struct nft_pipapo_match __rcu *match;
 163         struct nft_pipapo_match *clone;
 164         int width;
 165         bool dirty;
 166         unsigned long last_gc;
 167 };
 168
 169 struct nft_pipapo_elem;
 170
 171 /**
 172  * struct nft_pipapo_elem - API-facing representation of single set element
 173  * @priv:       element placeholder
 174  * @ext:        nftables API extensions
 175  */
 176 struct nft_pipapo_elem {
 177         struct nft_elem_priv    priv;
 178         struct nft_set_ext      ext;
 179 };
 180
 181 int pipapo_refill(unsigned long *map, unsigned int len, unsigned int rules,
 182                   unsigned long *dst,
 183                   const union nft_pipapo_map_bucket *mt, bool match_only);
 184
 185 /**
 186  * pipapo_and_field_buckets_4bit() - Intersect 4-bit buckets
 187  * @f:          Field including lookup table
 188  * @dst:        Area to store result
 189  * @data:       Input data selecting table buckets
 190  */
 191 static inline void pipapo_and_field_buckets_4bit(const struct nft_pipapo_field *f,
 192                                                  unsigned long *dst,
 193                                                  const u8 *data)
 194 {
 195         unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
 196         int group;
 197
 198         for (group = 0; group < f->groups; group += BITS_PER_BYTE / 4, data++) {
 199                 u8 v;
 200
 201                 v = *data >> 4;
 202                 __bitmap_and(dst, dst, lt + v * f->bsize,
 203                              f->bsize * BITS_PER_LONG);
 204                 lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
 205
 206                 v = *data & 0x0f;
 207                 __bitmap_and(dst, dst, lt + v * f->bsize,
 208                              f->bsize * BITS_PER_LONG);
 209                 lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
 210         }
 211 }
 212
 213 /**
 214  * pipapo_and_field_buckets_8bit() - Intersect 8-bit buckets
 215  * @f:          Field including lookup table
 216  * @dst:        Area to store result
 217  * @data:       Input data selecting table buckets
 218  */
 219 static inline void pipapo_and_field_buckets_8bit(const struct nft_pipapo_field *f,
 220                                                  unsigned long *dst,
 221                                                  const u8 *data)
 222 {
 223         unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
 224         int group;
 225
 226         for (group = 0; group < f->groups; group++, data++) {
 227                 __bitmap_and(dst, dst, lt + *data * f->bsize,
 228                              f->bsize * BITS_PER_LONG);
 229                 lt += f->bsize * NFT_PIPAPO_BUCKETS(8);
 230         }
 231 }
 232
 233 /**
 234  * pipapo_estimate_size() - Estimate worst-case for set size
 235  * @desc:       Set description, element count and field description used here
 236  *
 237  * The size for this set type can vary dramatically, as it depends on the number
 238  * of rules (composing netmasks) the entries expand to. We compute the worst
 239  * case here.
 240  *
 241  * In general, for a non-ranged entry or a single composing netmask, we need
 242  * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
 243  * is, each input bit needs four bits of matching data), plus a bucket in the
 244  * mapping table for each field.
 245  *
 246  * Return: worst-case set size in bytes, 0 on any overflow
 247  */
 248 static u64 pipapo_estimate_size(const struct nft_set_desc *desc)
 249 {
 250         unsigned long entry_size;
 251         u64 size;
 252         int i;
 253
 254         for (i = 0, entry_size = 0; i < desc->field_count; i++) {
 255                 unsigned long rules;
 256
 257                 if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
 258                         return 0;
 259
 260                 /* Worst-case ranges for each concatenated field: each n-bit
 261                  * field can expand to up to n * 2 rules in each bucket, and
 262                  * each rule also needs a mapping bucket.
 263                  */
 264                 rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
 265                 entry_size += rules *
 266                               NFT_PIPAPO_BUCKETS(NFT_PIPAPO_GROUP_BITS_INIT) /
 267                               BITS_PER_BYTE;
 268                 entry_size += rules * sizeof(union nft_pipapo_map_bucket);
 269         }
 270
 271         /* Rules in lookup and mapping tables are needed for each entry */
 272         size = desc->size * entry_size;
 273         if (size && div_u64(size, desc->size) != entry_size)
 274                 return 0;
 275
 276         size += sizeof(struct nft_pipapo) + sizeof(struct nft_pipapo_match) * 2;
 277
 278         size += sizeof(struct nft_pipapo_field) * desc->field_count;
 279
 280         return size;
 281 }
 282
 283 #endif /* _NFT_SET_PIPAPO_H */