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

Commit Message

Toke Høiland-Jørgensen March 7, 2024, 12:03 p.m. UTC

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 <[e-mail]>
---
 kernel/bpf/stackmap.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

Comments

Bui Quang Minh March 7, 2024, 3:55 p.m. UTC | #1

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 <[e-mail]>
> ---
>   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 <[e-mail]>

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

Thanks,
Quang Minh.

Toke Høiland-Jørgensen March 7, 2024, 4:52 p.m. UTC | #2

Bui Quang Minh <[e-mail]> 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 <[e-mail]>
>> ---
>>   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 <[e-mail]>
>
> 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

Patch

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)