~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/netfilter/nft_set_pipapo.h

Version: ~ [ linux-5.18 ] ~ [ linux-5.17.9 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.41 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.117 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.195 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.244 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.280 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.315 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 #define NFT_PIPAPO_LT_ASSIGN(field, x)                                  \
 74         do {                                                            \
 75                 (field)->lt_aligned = NFT_PIPAPO_LT_ALIGN(x);           \
 76                 (field)->lt = (x);                                      \
 77         } while (0)
 78 #else
 79 #define NFT_PIPAPO_ALIGN_HEADROOM       0
 80 #define NFT_PIPAPO_LT_ALIGN(lt)         (lt)
 81 #define NFT_PIPAPO_LT_ASSIGN(field, x)  ((field)->lt = (x))
 82 #endif /* NFT_PIPAPO_ALIGN */
 83 
 84 #define nft_pipapo_for_each_field(field, index, match)          \
 85         for ((field) = (match)->f, (index) = 0;                 \
 86              (index) < (match)->field_count;                    \
 87              (index)++, (field)++)
 88 
 89 /**
 90  * union nft_pipapo_map_bucket - Bucket of mapping table
 91  * @to:         First rule number (in next field) this rule maps to
 92  * @n:          Number of rules (in next field) this rule maps to
 93  * @e:          If there's no next field, pointer to element this rule maps to
 94  */
 95 union nft_pipapo_map_bucket {
 96         struct {
 97 #if BITS_PER_LONG == 64
 98                 static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
 99                 u32 to;
100 
101                 static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
102                 u32 n;
103 #else
104                 unsigned long to:NFT_PIPAPO_MAP_TOBITS;
105                 unsigned long  n:NFT_PIPAPO_MAP_NBITS;
106 #endif
107         };
108         struct nft_pipapo_elem *e;
109 };
110 
111 /**
112  * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
113  * @groups:     Amount of bit groups
114  * @rules:      Number of inserted rules
115  * @bsize:      Size of each bucket in lookup table, in longs
116  * @bb:         Number of bits grouped together in lookup table buckets
117  * @lt:         Lookup table: 'groups' rows of buckets
118  * @lt_aligned: Version of @lt aligned to NFT_PIPAPO_ALIGN bytes
119  * @mt:         Mapping table: one bucket per rule
120  */
121 struct nft_pipapo_field {
122         int groups;
123         unsigned long rules;
124         size_t bsize;
125         int bb;
126 #ifdef NFT_PIPAPO_ALIGN
127         unsigned long *lt_aligned;
128 #endif
129         unsigned long *lt;
130         union nft_pipapo_map_bucket *mt;
131 };
132 
133 /**
134  * struct nft_pipapo_match - Data used for lookup and matching
135  * @field_count         Amount of fields in set
136  * @scratch:            Preallocated per-CPU maps for partial matching results
137  * @scratch_aligned:    Version of @scratch aligned to NFT_PIPAPO_ALIGN bytes
138  * @bsize_max:          Maximum lookup table bucket size of all fields, in longs
139  * @rcu                 Matching data is swapped on commits
140  * @f:                  Fields, with lookup and mapping tables
141  */
142 struct nft_pipapo_match {
143         int field_count;
144 #ifdef NFT_PIPAPO_ALIGN
145         unsigned long * __percpu *scratch_aligned;
146 #endif
147         unsigned long * __percpu *scratch;
148         size_t bsize_max;
149         struct rcu_head rcu;
150         struct nft_pipapo_field f[];
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  * @ext:        nftables API extensions
174  */
175 struct nft_pipapo_elem {
176         struct nft_set_ext ext;
177 };
178 
179 int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
180                   union nft_pipapo_map_bucket *mt, bool match_only);
181 
182 /**
183  * pipapo_and_field_buckets_4bit() - Intersect 4-bit buckets
184  * @f:          Field including lookup table
185  * @dst:        Area to store result
186  * @data:       Input data selecting table buckets
187  */
188 static inline void pipapo_and_field_buckets_4bit(struct nft_pipapo_field *f,
189                                                  unsigned long *dst,
190                                                  const u8 *data)
191 {
192         unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
193         int group;
194 
195         for (group = 0; group < f->groups; group += BITS_PER_BYTE / 4, data++) {
196                 u8 v;
197 
198                 v = *data >> 4;
199                 __bitmap_and(dst, dst, lt + v * f->bsize,
200                              f->bsize * BITS_PER_LONG);
201                 lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
202 
203                 v = *data & 0x0f;
204                 __bitmap_and(dst, dst, lt + v * f->bsize,
205                              f->bsize * BITS_PER_LONG);
206                 lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
207         }
208 }
209 
210 /**
211  * pipapo_and_field_buckets_8bit() - Intersect 8-bit buckets
212  * @f:          Field including lookup table
213  * @dst:        Area to store result
214  * @data:       Input data selecting table buckets
215  */
216 static inline void pipapo_and_field_buckets_8bit(struct nft_pipapo_field *f,
217                                                  unsigned long *dst,
218                                                  const u8 *data)
219 {
220         unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
221         int group;
222 
223         for (group = 0; group < f->groups; group++, data++) {
224                 __bitmap_and(dst, dst, lt + *data * f->bsize,
225                              f->bsize * BITS_PER_LONG);
226                 lt += f->bsize * NFT_PIPAPO_BUCKETS(8);
227         }
228 }
229 
230 /**
231  * pipapo_estimate_size() - Estimate worst-case for set size
232  * @desc:       Set description, element count and field description used here
233  *
234  * The size for this set type can vary dramatically, as it depends on the number
235  * of rules (composing netmasks) the entries expand to. We compute the worst
236  * case here.
237  *
238  * In general, for a non-ranged entry or a single composing netmask, we need
239  * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
240  * is, each input bit needs four bits of matching data), plus a bucket in the
241  * mapping table for each field.
242  *
243  * Return: worst-case set size in bytes, 0 on any overflow
244  */
245 static u64 pipapo_estimate_size(const struct nft_set_desc *desc)
246 {
247         unsigned long entry_size;
248         u64 size;
249         int i;
250 
251         for (i = 0, entry_size = 0; i < desc->field_count; i++) {
252                 unsigned long rules;
253 
254                 if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
255                         return 0;
256 
257                 /* Worst-case ranges for each concatenated field: each n-bit
258                  * field can expand to up to n * 2 rules in each bucket, and
259                  * each rule also needs a mapping bucket.
260                  */
261                 rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
262                 entry_size += rules *
263                               NFT_PIPAPO_BUCKETS(NFT_PIPAPO_GROUP_BITS_INIT) /
264                               BITS_PER_BYTE;
265                 entry_size += rules * sizeof(union nft_pipapo_map_bucket);
266         }
267 
268         /* Rules in lookup and mapping tables are needed for each entry */
269         size = desc->size * entry_size;
270         if (size && div_u64(size, desc->size) != entry_size)
271                 return 0;
272 
273         size += sizeof(struct nft_pipapo) + sizeof(struct nft_pipapo_match) * 2;
274 
275         size += sizeof(struct nft_pipapo_field) * desc->field_count;
276 
277         return size;
278 }
279 
280 #endif /* _NFT_SET_PIPAPO_H */
281 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp