[PATCH bpf v3 0/3] Fix hash bucket overflow checks for 32-bit arches

[PATCH bpf v3 0/3] Fix hash bucket overflow checks for 32-bit arches

[Toke Høiland-Jørgensen]

Syzbot managed to trigger a crash by creating a DEVMAP_HASH map with a
large number of buckets because the overflow check relies on
well-defined behaviour that is only correct on 64-bit arches.

Fix the overflow checks to happen before values are rounded up in all
the affected map types.

v3:
- Keep the htab->n_buckets > U32_MAX / sizeof(struct bucket) check
- Use 1UL << 31 instead of U32_MAX / 2 + 1 as the constant to check
  against
- Add patch to fix stackmap.c
v2:
- Fix off-by-one error in overflow check
- Apply the same fix to hashtab, where the devmap_hash code was copied
  from (John)

Toke Høiland-Jørgensen (3):
  bpf: Fix DEVMAP_HASH overflow check on 32-bit arches
  bpf: Fix hashtab overflow check on 32-bit arches
  bpf: Fix stackmap overflow check on 32-bit arches

 kernel/bpf/devmap.c   | 11 ++++++-----
 kernel/bpf/hashtab.c  | 14 +++++++++-----
 kernel/bpf/stackmap.c |  9 ++++++---
 3 files changed, 21 insertions(+), 13 deletions(-)

-- 
2.43.2

[PATCH bpf v3 1/3] bpf: Fix DEVMAP_HASH overflow check on 32-bit arches

[Toke Høiland-Jørgensen]

The devmap code allocates a number hash buckets equal to the next power
of two of the max_entries value provided when creating the map. When
rounding up to the next power of two, the 32-bit variable storing the
number of buckets can overflow, and the code checks for overflow by
checking if the truncated 32-bit value is equal to 0. However, on 32-bit
arches the rounding up itself can overflow mid-way through, because it
ends up doing a left-shift of 32 bits on an unsigned long value. If the
size of an unsigned long is four bytes, this is undefined behaviour, so
there is no guarantee that we'll end up with a nice and tidy 0-value at
the end.

Syzbot managed to turn this into a crash on arm32 by creating a
DEVMAP_HASH with max_entries > 0x80000000 and then trying to update it.
Fix this by moving the overflow check to before the rounding up
operation.

Fixes: 6f9d451ab1a3 ("xdp: Add devmap_hash map type for looking up devices by hashed index")
Link: https://lore.kernel.org/r/000000000000ed666a0611af6818@google.com
Reported-and-tested-by: syzbot+8cd36f6b65f3cafd400a@syzkaller.appspotmail.com
Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 kernel/bpf/devmap.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/devmap.c b/kernel/bpf/devmap.c
index a936c704d4e7..4e2cdbb5629f 100644
--- a/kernel/bpf/devmap.c
+++ b/kernel/bpf/devmap.c
@@ -130,13 +130,14 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr)
 	bpf_map_init_from_attr(&dtab->map, attr);
 
 	if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
-		dtab->n_buckets = roundup_pow_of_two(dtab->map.max_entries);
-
-		if (!dtab->n_buckets) /* Overflow check */
+		/* hash table size must be power of 2; roundup_pow_of_two() can
+		 * overflow into UB on 32-bit arches, so check that first
+		 */
+		if (dtab->map.max_entries > 1UL << 31)
 			return -EINVAL;
-	}
 
-	if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
+		dtab->n_buckets = roundup_pow_of_two(dtab->map.max_entries);
+
 		dtab->dev_index_head = dev_map_create_hash(dtab->n_buckets,
 							   dtab->map.numa_node);
 		if (!dtab->dev_index_head)
-- 
2.43.2

[PATCH bpf v3 2/3] bpf: Fix hashtab overflow check on 32-bit arches

[Toke Høiland-Jørgensen]

The hashtab code relies on roundup_pow_of_two() to compute the number of
hash buckets, and contains an overflow check by checking if the
resulting value is 0. However, on 32-bit arches, the roundup code itself
can overflow by doing a 32-bit left-shift of an unsigned long value,
which is undefined behaviour, so it is not guaranteed to truncate
neatly. This was triggered by syzbot on the DEVMAP_HASH type, which
contains the same check, copied from the hashtab code. So apply the same
fix to hashtab, by moving the overflow check to before the roundup.

Fixes: daaf427c6ab3 ("bpf: fix arraymap NULL deref and missing overflow and zero size checks")
Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 kernel/bpf/hashtab.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 03a6a2500b6a..0cac6a65235c 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -499,7 +499,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
 							  num_possible_cpus());
 	}
 
-	/* hash table size must be power of 2 */
+	/* hash table size must be power of 2; roundup_pow_of_two() can overflow
+	 * into UB on 32-bit arches, so check that first
+	 */
+	err = -E2BIG;
+	if (htab->map.max_entries > 1UL << 31)
+		goto free_htab;
+
 	htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
 
 	htab->elem_size = sizeof(struct htab_elem) +
@@ -509,10 +515,8 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
 	else
 		htab->elem_size += round_up(htab->map.value_size, 8);
 
-	err = -E2BIG;
-	/* prevent zero size kmalloc and check for u32 overflow */
-	if (htab->n_buckets == 0 ||
-	    htab->n_buckets > U32_MAX / sizeof(struct bucket))
+	/* prevent zero size kmalloc */
+	if (htab->n_buckets > U32_MAX / sizeof(struct bucket))
 		goto free_htab;
 
 	err = bpf_map_init_elem_count(&htab->map);
-- 
2.43.2

[PATCH bpf v3 3/3] bpf: Fix stackmap overflow check on 32-bit arches

[Toke Høiland-Jørgensen]

The stackmap code relies on roundup_pow_of_two() to compute the number
of hash buckets, and contains an overflow check by checking if the
resulting value is 0. However, on 32-bit arches, the roundup code itself
can overflow by doing a 32-bit left-shift of an unsigned long value,
which is undefined behaviour, so it is not guaranteed to truncate
neatly. This was triggered by syzbot on the DEVMAP_HASH type, which
contains the same check, copied from the hashtab code.

The commit in the fixes tag actually attempted to fix this, but the fix
did not account for the UB, so the fix only works on CPUs where an
overflow does result in a neat truncation to zero, which is not
guaranteed. Checking the value before rounding does not have this
problem.

Fixes: 6183f4d3a0a2 ("bpf: Check for integer overflow when using roundup_pow_of_two()")
Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 kernel/bpf/stackmap.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/stackmap.c b/kernel/bpf/stackmap.c
index dff7ba539701..c99f8e5234ac 100644
--- a/kernel/bpf/stackmap.c
+++ b/kernel/bpf/stackmap.c
@@ -91,11 +91,14 @@ static struct bpf_map *stack_map_alloc(union bpf_attr *attr)
 	} else if (value_size / 8 > sysctl_perf_event_max_stack)
 		return ERR_PTR(-EINVAL);
 
-	/* hash table size must be power of 2 */
-	n_buckets = roundup_pow_of_two(attr->max_entries);
-	if (!n_buckets)
+	/* hash table size must be power of 2; roundup_pow_of_two() can overflow
+	 * into UB on 32-bit arches, so check that first
+	 */
+	if (attr->max_entries > 1UL << 31)
 		return ERR_PTR(-E2BIG);
 
+	n_buckets = roundup_pow_of_two(attr->max_entries);
+
 	cost = n_buckets * sizeof(struct stack_map_bucket *) + sizeof(*smap);
 	smap = bpf_map_area_alloc(cost, bpf_map_attr_numa_node(attr));
 	if (!smap)
-- 
2.43.2

Re: [PATCH bpf v3 3/3] bpf: Fix stackmap overflow check on 32-bit arches

[Bui Quang Minh]

On 3/7/24 19:03, Toke Høiland-Jørgensen wrote:
> The stackmap code relies on roundup_pow_of_two() to compute the number
> of hash buckets, and contains an overflow check by checking if the
> resulting value is 0. However, on 32-bit arches, the roundup code itself
> can overflow by doing a 32-bit left-shift of an unsigned long value,
> which is undefined behaviour, so it is not guaranteed to truncate
> neatly. This was triggered by syzbot on the DEVMAP_HASH type, which
> contains the same check, copied from the hashtab code.
> 
> The commit in the fixes tag actually attempted to fix this, but the fix
> did not account for the UB, so the fix only works on CPUs where an
> overflow does result in a neat truncation to zero, which is not
> guaranteed. Checking the value before rounding does not have this
> problem.
> 
> Fixes: 6183f4d3a0a2 ("bpf: Check for integer overflow when using roundup_pow_of_two()")
> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
> ---
>   kernel/bpf/stackmap.c | 9 ++++++---
>   1 file changed, 6 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/bpf/stackmap.c b/kernel/bpf/stackmap.c
> index dff7ba539701..c99f8e5234ac 100644
> --- a/kernel/bpf/stackmap.c
> +++ b/kernel/bpf/stackmap.c
> @@ -91,11 +91,14 @@ static struct bpf_map *stack_map_alloc(union bpf_attr *attr)
>   	} else if (value_size / 8 > sysctl_perf_event_max_stack)
>   		return ERR_PTR(-EINVAL);
>   
> -	/* hash table size must be power of 2 */
> -	n_buckets = roundup_pow_of_two(attr->max_entries);
> -	if (!n_buckets)
> +	/* hash table size must be power of 2; roundup_pow_of_two() can overflow
> +	 * into UB on 32-bit arches, so check that first
> +	 */
> +	if (attr->max_entries > 1UL << 31)
>   		return ERR_PTR(-E2BIG);
>   
> +	n_buckets = roundup_pow_of_two(attr->max_entries);
> +
>   	cost = n_buckets * sizeof(struct stack_map_bucket *) + sizeof(*smap);
>   	smap = bpf_map_area_alloc(cost, bpf_map_attr_numa_node(attr));
>   	if (!smap)

Reviewed-by: Bui Quang Minh <minhquangbui99@gmail.com>

Today I learned to be more careful with UB in C.

Thanks,
Quang Minh.

Re: [PATCH bpf v3 3/3] bpf: Fix stackmap overflow check on 32-bit arches

[Toke Høiland-Jørgensen]

Bui Quang Minh <minhquangbui99@gmail.com> writes:

> On 3/7/24 19:03, Toke Høiland-Jørgensen wrote:
>> The stackmap code relies on roundup_pow_of_two() to compute the number
>> of hash buckets, and contains an overflow check by checking if the
>> resulting value is 0. However, on 32-bit arches, the roundup code itself
>> can overflow by doing a 32-bit left-shift of an unsigned long value,
>> which is undefined behaviour, so it is not guaranteed to truncate
>> neatly. This was triggered by syzbot on the DEVMAP_HASH type, which
>> contains the same check, copied from the hashtab code.
>> 
>> The commit in the fixes tag actually attempted to fix this, but the fix
>> did not account for the UB, so the fix only works on CPUs where an
>> overflow does result in a neat truncation to zero, which is not
>> guaranteed. Checking the value before rounding does not have this
>> problem.
>> 
>> Fixes: 6183f4d3a0a2 ("bpf: Check for integer overflow when using roundup_pow_of_two()")
>> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
>> ---
>>   kernel/bpf/stackmap.c | 9 ++++++---
>>   1 file changed, 6 insertions(+), 3 deletions(-)
>> 
>> diff --git a/kernel/bpf/stackmap.c b/kernel/bpf/stackmap.c
>> index dff7ba539701..c99f8e5234ac 100644
>> --- a/kernel/bpf/stackmap.c
>> +++ b/kernel/bpf/stackmap.c
>> @@ -91,11 +91,14 @@ static struct bpf_map *stack_map_alloc(union bpf_attr *attr)
>>   	} else if (value_size / 8 > sysctl_perf_event_max_stack)
>>   		return ERR_PTR(-EINVAL);
>>   
>> -	/* hash table size must be power of 2 */
>> -	n_buckets = roundup_pow_of_two(attr->max_entries);
>> -	if (!n_buckets)
>> +	/* hash table size must be power of 2; roundup_pow_of_two() can overflow
>> +	 * into UB on 32-bit arches, so check that first
>> +	 */
>> +	if (attr->max_entries > 1UL << 31)
>>   		return ERR_PTR(-E2BIG);
>>   
>> +	n_buckets = roundup_pow_of_two(attr->max_entries);
>> +
>>   	cost = n_buckets * sizeof(struct stack_map_bucket *) + sizeof(*smap);
>>   	smap = bpf_map_area_alloc(cost, bpf_map_attr_numa_node(attr));
>>   	if (!smap)
>
> Reviewed-by: Bui Quang Minh <minhquangbui99@gmail.com>
>
> Today I learned to be more careful with UB in C.

Haha, yeah, I was surprised about this one as well; UB is nasty! :)

-Toke

Re: [PATCH bpf v3 2/3] bpf: Fix hashtab overflow check on 32-bit arches

[Alexei Starovoitov]

On Thu, Mar 7, 2024 at 4:03 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> -       err = -E2BIG;
> -       /* prevent zero size kmalloc and check for u32 overflow */
> -       if (htab->n_buckets == 0 ||
> -           htab->n_buckets > U32_MAX / sizeof(struct bucket))
> +       /* prevent zero size kmalloc */
> +       if (htab->n_buckets > U32_MAX / sizeof(struct bucket))

The comment carried over the wrong half of the comment.
I fixed it up while applying... to bpf-next.
There probably will be no bpf pr,
since the merge window is about to start.

Thanks!

Re: [PATCH bpf v3 0/3] Fix hash bucket overflow checks for 32-bit arches

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Thu,  7 Mar 2024 13:03:34 +0100 you wrote:
> Syzbot managed to trigger a crash by creating a DEVMAP_HASH map with a
> large number of buckets because the overflow check relies on
> well-defined behaviour that is only correct on 64-bit arches.
> 
> Fix the overflow checks to happen before values are rounded up in all
> the affected map types.
> 
> [...]

Here is the summary with links:
  - [bpf,v3,1/3] bpf: Fix DEVMAP_HASH overflow check on 32-bit arches
    https://git.kernel.org/bpf/bpf-next/c/281d464a34f5
  - [bpf,v3,2/3] bpf: Fix hashtab overflow check on 32-bit arches
    (no matching commit)
  - [bpf,v3,3/3] bpf: Fix stackmap overflow check on 32-bit arches
    https://git.kernel.org/bpf/bpf-next/c/7a4b21250bf7

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

Re: [PATCH bpf v3 2/3] bpf: Fix hashtab overflow check on 32-bit arches

[Toke Høiland-Jørgensen]

Alexei Starovoitov <alexei.starovoitov@gmail.com> writes:

> On Thu, Mar 7, 2024 at 4:03 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>>
>> -       err = -E2BIG;
>> -       /* prevent zero size kmalloc and check for u32 overflow */
>> -       if (htab->n_buckets == 0 ||
>> -           htab->n_buckets > U32_MAX / sizeof(struct bucket))
>> +       /* prevent zero size kmalloc */
>> +       if (htab->n_buckets > U32_MAX / sizeof(struct bucket))
>
> The comment carried over the wrong half of the comment.
> I fixed it up while applying... to bpf-next.
> There probably will be no bpf pr,
> since the merge window is about to start.

Oops, yeah, completely misread that comment; thanks for fixing! :)

-Toke