Skip to contentSkip to conversation

netfilter: nft_set_pipapo: prevent overflow in lookup table allocation

PATCH Superseded Pablo Neira Ayuso 2 participants 4 messages Apr 10, 2025

Subsystems (2)
lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH v2 1/2 netfilter: nft_set_pipapo: prevent overflow in lookup table allocation

When calculating the lookup table size, ensure the following multiplication does not overflow:

- desc->field_len[] maximum value is U8_MAX multiplied by NFT_PIPAPO_GROUPS_PER_BYTE(f) that can be 2, worst case.
- NFT_PIPAPO_BUCKETS(f->bb) is 2^8, worst case.
- sizeof(unsigned long), from sizeof(*f->lt), lt in struct nft_pipapo_field.

Then, use check_mul_overflow() to multiply by bucket size and then use check_add_overflow() to the alignment for avx2 (if needed). Finally, add lt_size_check_overflow() helper and use it to consolidate this.

While at it, replace leftover allocation using the GFP_KERNEL to GFP_KERNEL_ACCOUNT for consistency, in pipapo_resize().

Fixes 3c4287f62044 ("nf_tables: Add set type for arbitrary concatenation of ranges")

---
v2: detach chunk to ensure allocation below INT_MAX.

 net/netfilter/nft_set_pipapo.c | 48 +++++++++++++++++++++++++---------
 1 file changed, 35 insertions(+), 13 deletions(-)
net/netfilter/nft_set_pipapo.c +35 -13
index 7be342b495f5..1b5c498468c5 100644
@@ -683,6 +683,22 @@ static int pipapo_realloc_mt(struct nft_pipapo_field *f,
 	return 0;
 }
 
+static bool lt_size_check_overflow(unsigned int groups, unsigned int bb,
+				   unsigned int bsize, size_t size,
+				   size_t *lt_size)
+{
+	*lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * size;
+
+	if (check_mul_overflow(*lt_size, bsize, lt_size))
+		return true;
+	if (check_add_overflow(*lt_size, NFT_PIPAPO_ALIGN_HEADROOM, lt_size))
+		return true;
+	if (*lt_size > INT_MAX)
+		return true;
+
+	return false;
+}
+
 /**
  * pipapo_resize() - Resize lookup or mapping table, or both
  * @f:		Field containing lookup and mapping tables
@@ -701,6 +717,7 @@ static int pipapo_resize(struct nft_pipapo_field *f,
 	long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
 	unsigned int new_bucket_size, copy;
 	int group, bucket, err;
+	size_t lt_size;
 
 	if (rules >= NFT_PIPAPO_RULE0_MAX)
 		return -ENOSPC;
@@ -719,10 +736,11 @@ static int pipapo_resize(struct nft_pipapo_field *f,
 	else
 		copy = new_bucket_size;
 
-	new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS(f->bb) *
-			  new_bucket_size * sizeof(*new_lt) +
-			  NFT_PIPAPO_ALIGN_HEADROOM,
-			  GFP_KERNEL);
+	if (lt_size_check_overflow(f->groups, f->bb, new_bucket_size,
+				   sizeof(*new_lt), &lt_size))
+		return -ENOMEM;
+
+	new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
 	if (!new_lt)
 		return -ENOMEM;
 
@@ -917,15 +935,17 @@ static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
 		groups = f->groups * 2;
 		bb = NFT_PIPAPO_GROUP_BITS_LARGE_SET;
 
-		lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
-			  sizeof(*f->lt);
+		if (lt_size_check_overflow(groups, bb, f->bsize,
+					   sizeof(*f->lt), &lt_size))
+			return;
 	} else if (f->bb == NFT_PIPAPO_GROUP_BITS_LARGE_SET &&
 		   lt_size < NFT_PIPAPO_LT_SIZE_LOW) {
 		groups = f->groups / 2;
 		bb = NFT_PIPAPO_GROUP_BITS_SMALL_SET;
 
-		lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
-			  sizeof(*f->lt);
+		if (lt_size_check_overflow(groups, bb, f->bsize,
+					   sizeof(*f->lt), &lt_size))
+			return;
 
 		/* Don't increase group width if the resulting lookup table size
 		 * would exceed the upper size threshold for a "small" set.
@@ -936,7 +956,7 @@ static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
 		return;
 	}
 
-	new_lt = kvzalloc(lt_size + NFT_PIPAPO_ALIGN_HEADROOM, GFP_KERNEL_ACCOUNT);
+	new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
 	if (!new_lt)
 		return;
 
@@ -1451,13 +1471,15 @@ static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
 
 	for (i = 0; i < old->field_count; i++) {
 		unsigned long *new_lt;
+		size_t lt_size;
 
 		memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
 
-		new_lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS(src->bb) *
-				  src->bsize * sizeof(*dst->lt) +
-				  NFT_PIPAPO_ALIGN_HEADROOM,
-				  GFP_KERNEL_ACCOUNT);
+		if (lt_size_check_overflow(src->groups, src->bb, src->bsize,
+					   sizeof(*dst->lt), &lt_size))
+			goto out_lt;
+
+		new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
 		if (!new_lt)
 			goto out_lt;
 
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

PATCH v2 2/2 netfilter: nft_set_pipapo: clamp maximum map bucket size to INT_MAX

Otherwise, it is possible to hit WARN_ON_ONCE in __kvmalloc_node_noprof() when resizing hashtable because __GFP_NOWARN is unset.

Similar to:

b541ba7d1f5a ("netfilter: conntrack: clamp maximum hashtable size to INT_MAX")

---
v2: detached from patch 1/2 posted as v1.

 net/netfilter/nft_set_pipapo.c | 6 ++++++
 1 file changed, 6 insertions(+)
net/netfilter/nft_set_pipapo.c +6 -0
index 1b5c498468c5..ffb8c3623a93 100644
@@ -663,6 +663,9 @@ static int pipapo_realloc_mt(struct nft_pipapo_field *f,
 	    check_add_overflow(rules, extra, &rules_alloc))
 		return -EOVERFLOW;
 
+	if (rules_alloc > (INT_MAX / sizeof(*new_mt)))
+		return -ENOMEM;
+
 	new_mt = kvmalloc_array(rules_alloc, sizeof(*new_mt), GFP_KERNEL_ACCOUNT);
 	if (!new_mt)
 		return -ENOMEM;
@@ -1491,6 +1494,9 @@ static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
 		       src->groups * NFT_PIPAPO_BUCKETS(src->bb));
 
 		if (src->rules > 0) {
+			if (src->rules_alloc > (INT_MAX / sizeof(*src->mt)))
+				goto out_mt;
+
 			dst->mt = kvmalloc_array(src->rules_alloc,
 						 sizeof(*src->mt),
 						 GFP_KERNEL_ACCOUNT);
Signature · 1 line
2.30.2
Reviewed-by on v2 2/2
#2 lore raw

Re: [PATCH nf-next,v2 2/2] netfilter: nft_set_pipapo: clamp maximum map bucket size to INT_MAX

Quoted 8 lines · On Thu, 10 Apr 2025 12:04:56 +0200 Pablo Neira Ayuso <[email protected]>…

Otherwise, it is possible to hit WARN_ON_ONCE in __kvmalloc_node_noprof() when resizing hashtable because __GFP_NOWARN is unset.

Similar to:

b541ba7d1f5a ("netfilter: conntrack: clamp maximum hashtable size to INT_MAX")

Signature · 1 line
Stefano
#3 lore raw
In reply to Pablo Neira Ayuso
Quoted 29 lines · On Thu, 10 Apr 2025 12:04:55 +0200 Pablo Neira Ayuso <[email protected]>…

When calculating the lookup table size, ensure the following multiplication does not overflow:

- desc->field_len[] maximum value is U8_MAX multiplied by NFT_PIPAPO_GROUPS_PER_BYTE(f) that can be 2, worst case.
- NFT_PIPAPO_BUCKETS(f->bb) is 2^8, worst case.
- sizeof(unsigned long), from sizeof(*f->lt), lt in struct nft_pipapo_field.

Then, use check_mul_overflow() to multiply by bucket size and then use check_add_overflow() to the alignment for avx2 (if needed). Finally, add lt_size_check_overflow() helper and use it to consolidate this.

While at it, replace leftover allocation using the GFP_KERNEL to GFP_KERNEL_ACCOUNT for consistency, in pipapo_resize().

Fixes 3c4287f62044 ("nf_tables: Add set type for arbitrary concatenation of ranges")

---
v2: detach chunk to ensure allocation below INT_MAX.

 net/netfilter/nft_set_pipapo.c | 48 +++++++++++++++++++++++++---------
 1 file changed, 35 insertions(+), 13 deletions(-)
net/netfilter/nft_set_pipapo.c +0 -0
index 7be342b495f5..1b5c498468c5 100644

net/netfilter/nft_set_pipapo.c static int pipapo_realloc_mt(struct nft_pipapo_field *f, · line 688

Quoted 6 lines
net/netfilter/nft_set_pipapo.c +3 -0
@@ -683,6 +683,22 @@ static int pipapo_realloc_mt(struct nft_pipapo_field *f,
 	return 0;
 }
 
+static bool lt_size_check_overflow(unsigned int groups, unsigned int bb,
+				   unsigned int bsize, size_t size,
+				   size_t *lt_size)

It looks good to me except for one consideration: I found it quite confusing that this changes lt_size but at a first glance it appears to check things only, so I've been wondering for a while if you accidentally dropped the alignment headroom.

By the way, 'size' is always sizeof(long) (because 'bsize' is in longs).

I haven't tested this (not even build tested, sorry), but what about:

/**
* lt_calculate_size() - Get storage size for lookup table with overflow check
* @groups: Amount of bit groups
* @bb: Number of bits grouped together in lookup table buckets
* @bsize: Size of each bucket in lookup table, in longs
*
* Return: allocation size including alignment overhead, negative on overflow */
static ssize_t lt_size_check_overflow(unsigned int groups, unsigned int bb,
unsigned int bsize)

{
	ssize_t ret = groups * NFT_PIPAPO_BUCKETS(bb) * sizeof(long);

	if (check_mul_overflow(ret, bsize, &ret))
		return -1;
	if (check_add_overflow(ret, NFT_PIPAPO_ALIGN_HEADROOM, &ret))
		return -1;
	if (ret > INT_MAX)
		return -1;

	return ret;
}

?

Quoted 81 lines
net/netfilter/nft_set_pipapo.c +27 -11
+{
+	*lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * size;
+
+	if (check_mul_overflow(*lt_size, bsize, lt_size))
+		return true;
+	if (check_add_overflow(*lt_size, NFT_PIPAPO_ALIGN_HEADROOM, lt_size))
+		return true;
+	if (*lt_size > INT_MAX)
+		return true;
+
+	return false;
+}
+
 /**
  * pipapo_resize() - Resize lookup or mapping table, or both
  * @f:		Field containing lookup and mapping tables
@@ -701,6 +717,7 @@ static int pipapo_resize(struct nft_pipapo_field *f,
 	long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
 	unsigned int new_bucket_size, copy;
 	int group, bucket, err;
+	size_t lt_size;
 
 	if (rules >= NFT_PIPAPO_RULE0_MAX)
 		return -ENOSPC;
@@ -719,10 +736,11 @@ static int pipapo_resize(struct nft_pipapo_field *f,
 	else
 		copy = new_bucket_size;
 
-	new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS(f->bb) *
-			  new_bucket_size * sizeof(*new_lt) +
-			  NFT_PIPAPO_ALIGN_HEADROOM,
-			  GFP_KERNEL);
+	if (lt_size_check_overflow(f->groups, f->bb, new_bucket_size,
+				   sizeof(*new_lt), &lt_size))
+		return -ENOMEM;
+
+	new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
 	if (!new_lt)
 		return -ENOMEM;
 
@@ -917,15 +935,17 @@ static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
 		groups = f->groups * 2;
 		bb = NFT_PIPAPO_GROUP_BITS_LARGE_SET;
 
-		lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
-			  sizeof(*f->lt);
+		if (lt_size_check_overflow(groups, bb, f->bsize,
+					   sizeof(*f->lt), &lt_size))
+			return;
 	} else if (f->bb == NFT_PIPAPO_GROUP_BITS_LARGE_SET &&
 		   lt_size < NFT_PIPAPO_LT_SIZE_LOW) {
 		groups = f->groups / 2;
 		bb = NFT_PIPAPO_GROUP_BITS_SMALL_SET;
 
-		lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
-			  sizeof(*f->lt);
+		if (lt_size_check_overflow(groups, bb, f->bsize,
+					   sizeof(*f->lt), &lt_size))
+			return;
 
 		/* Don't increase group width if the resulting lookup table size
 		 * would exceed the upper size threshold for a "small" set.
@@ -936,7 +956,7 @@ static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
 		return;
 	}
 
-	new_lt = kvzalloc(lt_size + NFT_PIPAPO_ALIGN_HEADROOM, GFP_KERNEL_ACCOUNT);
+	new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
 	if (!new_lt)
 		return;
 
@@ -1451,13 +1471,15 @@ static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
 
 	for (i = 0; i < old->field_count; i++) {
 		unsigned long *new_lt;
+		size_t lt_size;
 
 		memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
 
-		new_lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS(src->bb) *
-				  src->bsize * sizeof(*dst->lt) +

net/netfilter/nft_set_pipapo.c static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old) · line 1485

Quoted 10 lines
net/netfilter/nft_set_pipapo.c +5 -2
-				  NFT_PIPAPO_ALIGN_HEADROOM,
-				  GFP_KERNEL_ACCOUNT);
+		if (lt_size_check_overflow(src->groups, src->bb, src->bsize,
+					   sizeof(*dst->lt), &lt_size))
+			goto out_lt;
+
+		new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
 		if (!new_lt)
 			goto out_lt;
 

The rest looks good to me, thanks for fixing this!

Signature · 1 line
Stefano