[thirdparty/kernel/linux.git] / net / netfilter / nft_set_pipapo.h

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

#ifndef _NFT_SET_PIPAPO_H

#include <linux/log2.h>
#include <net/ipv6.h>			/* For the maximum length of a field */

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

/* Restrict usage to multiple fields, make sure rbtree is used otherwise */
#define NFT_PIPAPO_MIN_FIELDS		2

/* 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)

/* Bits to be grouped together in table buckets depending on set size */
#define NFT_PIPAPO_GROUP_BITS_INIT	NFT_PIPAPO_GROUP_BITS_SMALL_SET
#define NFT_PIPAPO_GROUP_BITS_SMALL_SET	8
#define NFT_PIPAPO_GROUP_BITS_LARGE_SET	4
#define NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4				\
	BUILD_BUG_ON((NFT_PIPAPO_GROUP_BITS_SMALL_SET != 8) ||		\
		     (NFT_PIPAPO_GROUP_BITS_LARGE_SET != 4))
#define NFT_PIPAPO_GROUPS_PER_BYTE(f)	(BITS_PER_BYTE / (f)->bb)

/* If a lookup table gets bigger than NFT_PIPAPO_LT_SIZE_HIGH, switch to the
 * small group width, and switch to the big group width if the table gets
 * smaller than NFT_PIPAPO_LT_SIZE_LOW.
 *
 * Picking 2MiB as threshold (for a single table) avoids as much as possible
 * crossing page boundaries on most architectures (x86-64 and MIPS huge pages,
 * ARMv7 supersections, POWER "large" pages, SPARC Level 1 regions, etc.), which
 * keeps performance nice in case kvmalloc() gives us non-contiguous areas.
 */
#define NFT_PIPAPO_LT_SIZE_THRESHOLD	(1 << 21)
#define NFT_PIPAPO_LT_SIZE_HYSTERESIS	(1 << 16)
#define NFT_PIPAPO_LT_SIZE_HIGH		NFT_PIPAPO_LT_SIZE_THRESHOLD
#define NFT_PIPAPO_LT_SIZE_LOW		NFT_PIPAPO_LT_SIZE_THRESHOLD -	\
					NFT_PIPAPO_LT_SIZE_HYSTERESIS

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

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

/* 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))

/* Definitions for vectorised implementations */
#ifdef NFT_PIPAPO_ALIGN
#define NFT_PIPAPO_ALIGN_HEADROOM					\
	(NFT_PIPAPO_ALIGN - ARCH_KMALLOC_MINALIGN)
#define NFT_PIPAPO_LT_ALIGN(lt)		(PTR_ALIGN((lt), NFT_PIPAPO_ALIGN))
#else
#define NFT_PIPAPO_ALIGN_HEADROOM	0
#define NFT_PIPAPO_LT_ALIGN(lt)		(lt)
#endif /* NFT_PIPAPO_ALIGN */

#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
 * @rules:	Number of inserted rules
 * @bsize:	Size of each bucket in lookup table, in longs
 * @rules_alloc: Number of allocated rules, always >= rules
 * @groups:	Amount of bit groups
 * @bb:		Number of bits grouped together in lookup table buckets
 * @lt:		Lookup table: 'groups' rows of buckets
 * @mt:		Mapping table: one bucket per rule
 */
struct nft_pipapo_field {
	unsigned int rules;
	unsigned int bsize;
	unsigned int rules_alloc;
	u8 groups;
	u8 bb;
	unsigned long *lt;
	union nft_pipapo_map_bucket *mt;
};

/**
 * struct nft_pipapo_scratch - percpu data used for lookup and matching
 * @map_index:	Current working bitmap index, toggled between field matches
 * @align_off:	Offset to get the originally allocated address
 * @map:	store partial matching results during lookup
 */
struct nft_pipapo_scratch {
	u8 map_index;
	u32 align_off;
	unsigned long map[];
};

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

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

struct nft_pipapo_elem;

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

int pipapo_refill(unsigned long *map, unsigned int len, unsigned int rules,
		  unsigned long *dst,
		  const union nft_pipapo_map_bucket *mt, bool match_only);

/**
 * pipapo_and_field_buckets_4bit() - Intersect 4-bit buckets
 * @f:		Field including lookup table
 * @dst:	Area to store result
 * @data:	Input data selecting table buckets
 */
static inline void pipapo_and_field_buckets_4bit(const struct nft_pipapo_field *f,
						 unsigned long *dst,
						 const u8 *data)
{
	unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
	int group;

	for (group = 0; group < f->groups; group += BITS_PER_BYTE / 4, data++) {
		u8 v;

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

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

/**
 * pipapo_and_field_buckets_8bit() - Intersect 8-bit buckets
 * @f:		Field including lookup table
 * @dst:	Area to store result
 * @data:	Input data selecting table buckets
 */
static inline void pipapo_and_field_buckets_8bit(const struct nft_pipapo_field *f,
						 unsigned long *dst,
						 const u8 *data)
{
	unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
	int group;

	for (group = 0; group < f->groups; group++, data++) {
		__bitmap_and(dst, dst, lt + *data * f->bsize,
			     f->bsize * BITS_PER_LONG);
		lt += f->bsize * NFT_PIPAPO_BUCKETS(8);
	}
}

/**
 * pipapo_estimate_size() - Estimate worst-case for set size
 * @desc:	Set description, element count and field description used here
 *
 * 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: worst-case set size in bytes, 0 on any overflow
 */
static u64 pipapo_estimate_size(const struct nft_set_desc *desc)
{
	unsigned long entry_size;
	u64 size;
	int i;

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

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

		/* 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(NFT_PIPAPO_GROUP_BITS_INIT) /
			      BITS_PER_BYTE;
		entry_size += rules * sizeof(union nft_pipapo_map_bucket);
	}

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

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

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

	return size;
}

#endif /* _NFT_SET_PIPAPO_H */
Commit	Line	Data
8683f4b9 SB	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
eb16933a SB	11	/* Restrict usage to multiple fields, make sure rbtree is used otherwise */
	12	#define NFT_PIPAPO_MIN_FIELDS 2
	13
8683f4b9 SB	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))
8683f4b9 SB	73	#else
	74	#define NFT_PIPAPO_ALIGN_HEADROOM 0
	75	#define NFT_PIPAPO_LT_ALIGN(lt) (lt)
8683f4b9 SB	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
8683f4b9 SB	107	* @rules: Number of inserted rules
8683f4b9 SB	108	* @bsize: Size of each bucket in lookup table, in longs
9f439bd6	109	* @rules_alloc: Number of allocated rules, always >= rules
aac14d51	110	* @groups: Amount of bit groups
8683f4b9 SB	111	* @bb: Number of bits grouped together in lookup table buckets
8683f4b9 SB	112	* @lt: Lookup table: 'groups' rows of buckets
8683f4b9 SB	113	* @mt: Mapping table: one bucket per rule
	114	*/
	115	struct nft_pipapo_field {
aac14d51 FW	116	unsigned int rules;
aac14d51 FW	117	unsigned int bsize;
9f439bd6	118	unsigned int rules_alloc;
aac14d51 FW	119	u8 groups;
aac14d51 FW	120	u8 bb;
8683f4b9 SB	121	unsigned long *lt;
	122	union nft_pipapo_map_bucket *mt;
	123	};
	124
76313d1a FW	125	/**
	126	* struct nft_pipapo_scratch - percpu data used for lookup and matching
	127	* @map_index: Current working bitmap index, toggled between field matches
5a8cdf6f	128	* @align_off: Offset to get the originally allocated address
76313d1a FW	129	* @map: store partial matching results during lookup
	130	*/
	131	struct nft_pipapo_scratch {
	132	u8 map_index;
5a8cdf6f	133	u32 align_off;
76313d1a FW	134	unsigned long map[];
	135	};
	136
8683f4b9 SB	137	/**
8683f4b9 SB	138	* struct nft_pipapo_match - Data used for lookup and matching
f6374a82	139	* @field_count: Amount of fields in set
8683f4b9	140	* @bsize_max: Maximum lookup table bucket size of all fields, in longs
aac14d51	141	* @scratch: Preallocated per-CPU maps for partial matching results
f6374a82	142	* @rcu: Matching data is swapped on commits
8683f4b9 SB	143	* @f: Fields, with lookup and mapping tables
	144	*/
	145	struct nft_pipapo_match {
aac14d51 FW	146	u8 field_count;
aac14d51 FW	147	unsigned int bsize_max;
76313d1a	148	struct nft_pipapo_scratch * __percpu *scratch;
8683f4b9	149	struct rcu_head rcu;
d51c42cd	150	struct nft_pipapo_field f[] __counted_by(field_count);
8683f4b9 SB	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
8683f4b9 SB	158	* @last_gc: Timestamp of last garbage collection run, jiffies
	159	*/
	160	struct nft_pipapo {
	161	struct nft_pipapo_match __rcu *match;
	162	struct nft_pipapo_match *clone;
	163	int width;
8683f4b9 SB	164	unsigned long last_gc;
	165	};
	166
	167	struct nft_pipapo_elem;
	168
	169	/**
	170	* struct nft_pipapo_elem - API-facing representation of single set element
9dad402b	171	* @priv: element placeholder
8683f4b9 SB	172	* @ext: nftables API extensions
	173	*/
	174	struct nft_pipapo_elem {
9dad402b PNA	175	struct nft_elem_priv priv;
9dad402b PNA	176	struct nft_set_ext ext;
8683f4b9 SB	177	};
8683f4b9 SB	178
aac14d51 FW	179	int pipapo_refill(unsigned long *map, unsigned int len, unsigned int rules,
aac14d51 FW	180	unsigned long *dst,
f04df573	181	const union nft_pipapo_map_bucket *mt, bool match_only);
8683f4b9 SB	182
	183	/**
	184	* pipapo_and_field_buckets_4bit() - Intersect 4-bit buckets
	185	* @f: Field including lookup table
	186	* @dst: Area to store result
	187	* @data: Input data selecting table buckets
	188	*/
f04df573	189	static inline void pipapo_and_field_buckets_4bit(const struct nft_pipapo_field *f,
8683f4b9 SB	190	unsigned long *dst,
	191	const u8 *data)
	192	{
	193	unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
	194	int group;
	195
	196	for (group = 0; group < f->groups; group += BITS_PER_BYTE / 4, data++) {
	197	u8 v;
	198
	199	v = *data >> 4;
	200	__bitmap_and(dst, dst, lt + v * f->bsize,
	201	f->bsize * BITS_PER_LONG);
	202	lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
	203
	204	v = *data & 0x0f;
	205	__bitmap_and(dst, dst, lt + v * f->bsize,
	206	f->bsize * BITS_PER_LONG);
	207	lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
	208	}
	209	}
	210
	211	/**
	212	* pipapo_and_field_buckets_8bit() - Intersect 8-bit buckets
	213	* @f: Field including lookup table
	214	* @dst: Area to store result
	215	* @data: Input data selecting table buckets
	216	*/
f04df573	217	static inline void pipapo_and_field_buckets_8bit(const struct nft_pipapo_field *f,
8683f4b9 SB	218	unsigned long *dst,
	219	const u8 *data)
	220	{
	221	unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
	222	int group;
	223
	224	for (group = 0; group < f->groups; group++, data++) {
	225	__bitmap_and(dst, dst, lt + data f->bsize,
	226	f->bsize * BITS_PER_LONG);
	227	lt += f->bsize * NFT_PIPAPO_BUCKETS(8);
	228	}
	229	}
	230
	231	/**
	232	* pipapo_estimate_size() - Estimate worst-case for set size
	233	* @desc: Set description, element count and field description used here
	234	*
	235	* The size for this set type can vary dramatically, as it depends on the number
	236	* of rules (composing netmasks) the entries expand to. We compute the worst
	237	* case here.
	238	*
	239	* In general, for a non-ranged entry or a single composing netmask, we need
	240	* one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
	241	* is, each input bit needs four bits of matching data), plus a bucket in the
	242	* mapping table for each field.
	243	*
	244	* Return: worst-case set size in bytes, 0 on any overflow
	245	*/
	246	static u64 pipapo_estimate_size(const struct nft_set_desc *desc)
	247	{
	248	unsigned long entry_size;
	249	u64 size;
	250	int i;
	251
	252	for (i = 0, entry_size = 0; i < desc->field_count; i++) {
	253	unsigned long rules;
	254
	255	if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
	256	return 0;
	257
	258	/* Worst-case ranges for each concatenated field: each n-bit
	259	* field can expand to up to n * 2 rules in each bucket, and
	260	* each rule also needs a mapping bucket.
	261	*/
	262	rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
	263	entry_size += rules *
	264	NFT_PIPAPO_BUCKETS(NFT_PIPAPO_GROUP_BITS_INIT) /
	265	BITS_PER_BYTE;
	266	entry_size += rules * sizeof(union nft_pipapo_map_bucket);
	267	}
	268
	269	/* Rules in lookup and mapping tables are needed for each entry */
	270	size = desc->size * entry_size;
	271	if (size && div_u64(size, desc->size) != entry_size)
	272	return 0;
	273
	274	size += sizeof(struct nft_pipapo) + sizeof(struct nft_pipapo_match) * 2;
	275
	276	size += sizeof(struct nft_pipapo_field) * desc->field_count;
	277
	278	return size;
	279	}
	280
	281	#endif /* _NFT_SET_PIPAPO_H */