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 */
 89union 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 */
115struct 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 * @bh_lock:    PREEMPT_RT local spinlock
128 * @map_index:	Current working bitmap index, toggled between field matches
129 * @__map:	store partial matching results during lookup
130 */
131struct nft_pipapo_scratch {
132	local_lock_t bh_lock;
133	u8 map_index;
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 */
145struct 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 * @last_gc:	Timestamp of last garbage collection run, jiffies
159 * @gc_head:	list of nft_trans_gc to queue up for mem reclaim
160 */
161struct nft_pipapo {
162	struct nft_pipapo_match __rcu *match;
163	struct nft_pipapo_match *clone;
164	int width;
165	unsigned long last_gc;
166	struct list_head gc_head;
167};
168
169struct 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 */
176struct nft_pipapo_elem {
177	struct nft_elem_priv	priv;
178	struct nft_set_ext	ext;
179};
180
181int 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 */
191static 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 */
219static 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 */
248static 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/**
284 * pipapo_resmap_init() - Initialise result map before first use
285 * @m:		Matching data, including mapping table
286 * @res_map:	Result map
287 *
288 * Initialize all bits covered by the first field to one, so that after
289 * the first step, only the matching bits of the first bit group remain.
290 *
291 * If other fields have a large bitmap, set remainder of res_map to 0.
292 */
293static inline void pipapo_resmap_init(const struct nft_pipapo_match *m, unsigned long *res_map)
294{
295	const struct nft_pipapo_field *f = m->f;
296	int i;
297
298	for (i = 0; i < f->bsize; i++)
299		res_map[i] = ULONG_MAX;
300
301	for (i = f->bsize; i < m->bsize_max; i++)
302		res_map[i] = 0ul;
303}
304#endif /* _NFT_SET_PIPAPO_H */