Re: [PATCH v2 bpf] bpf: harden bloom filter sizing and indexing on 32-bit kernels

On Sat, Aug 1, 2026 at 1:35 AM Jérémy Jean
<[email protected]> wrote:
>
> bloom_map_alloc() has two 32-bit-specific problems when the computed
> bitmap reaches the U32_MAX fallback case.
>
> First, BITS_TO_BYTES(U32_MAX) is evaluated with 32-bit arithmetic. The
> addition performed by DIV_ROUND_UP wraps, so the map allocates only the
> fixed-size bloom filter object while keeping bitset_mask == U32_MAX.
> Subsequent updates can then write past the allocated object.
>
> Second, fixing only the allocation size is not sufficient. The bloom hash
> is a u32, but set_bit() takes a signed long bit number and x86 test_bit()
> eventually feeds the index to variable_test_bit(long, ...). On 32-bit
> kernels, hashes in [0x80000000, U32_MAX] therefore become negative bit
> offsets. x86 bt/bts with a memory operand interpret those offsets relative
> to the supplied base, so a map with bitset_mask == U32_MAX can read or
> write before bloom->bitset even after allocating the full 512 MiB bitmap.
>
> Keep the U32_MAX fallback, but split each hash into a word pointer and an
> in-word bit number before calling test_bit() or set_bit(). The bitops
> argument is then always in [0, BITS_PER_LONG - 1], while BIT_WORD(h) still
> selects the intended word in the full bitmap.
>
> Compute the bitset size from (u64)bitset_mask + 1 before passing the final
> size to bpf_map_area_alloc(). This fixes the original under-allocation and
> keeps the allocated storage consistent with the addressable bitset.
>
> Exploitation note: local privilege escalation is possible on a 32-bit x86
> kernel using the under-allocation bug from a binary with CAP_BPF.
>
> Fixes: 9330986c0300 ("bpf: Add bloom filter map implementation")
> Cc: [email protected]
> Signed-off-by: Jérémy Jean <[email protected]>
> ---
> Changes in v2:
> - Address AI reviews.
> - Split full-width hashes into a word pointer and an in-word bit number
>   before calling bitops, so upper-half u32 hashes cannot become negative
>   offsets on 32-bit kernels.
> - Drop the redundant final u64 add-overflow check; bitset_bytes is bounded
>   at 512 MiB once it is computed from bitset_mask.
>
>  kernel/bpf/bloom_filter.c | 30 +++++++++++++++++++++---------
>  1 file changed, 21 insertions(+), 9 deletions(-)
>
> diff --git a/kernel/bpf/bloom_filter.c b/kernel/bpf/bloom_filter.c
> index b73336c..f111d26 100644
> --- a/kernel/bpf/bloom_filter.c
> +++ b/kernel/bpf/bloom_filter.c
> @@ -33,6 +33,22 @@ static u32 hash(struct bpf_bloom_filter *bloom, void *value,
>         return h & bloom->bitset_mask;
>  }
>
> +/*
> + * Some 32-bit architectures take a signed long bit number in bitops. Split
> + * the full u32 hash into a word pointer and an in-word bit number so upper
> + * half hashes cannot become negative offsets.
> + */
> +static bool bloom_test_bit(struct bpf_bloom_filter *bloom, u32 bit)
> +{
> +       return test_bit(bit % BITS_PER_LONG,
> +                       bloom->bitset + BIT_WORD(bit));
> +}
> +
> +static void bloom_set_bit(struct bpf_bloom_filter *bloom, u32 bit)
> +{
> +       set_bit(bit % BITS_PER_LONG, bloom->bitset + BIT_WORD(bit));
> +}
> +

these helper functions are used in exactly one place each, just inline
the right there in peek/push elem, leaving brief note that hashes
larger than INT_MAX would be treated as negative by set_bit()

pw-bot: cr


>  static long bloom_map_peek_elem(struct bpf_map *map, void *value)
>  {
>         struct bpf_bloom_filter *bloom =
> @@ -41,7 +57,7 @@ static long bloom_map_peek_elem(struct bpf_map *map, void *value)
>
>         for (i = 0; i < bloom->nr_hash_funcs; i++) {
>                 h = hash(bloom, value, map->value_size, i);
> -               if (!test_bit(h, bloom->bitset))
> +               if (!bloom_test_bit(bloom, h))
>                         return -ENOENT;
>         }
>
> @@ -59,7 +75,7 @@ static long bloom_map_push_elem(struct bpf_map *map, void *value, u64 flags)
>
>         for (i = 0; i < bloom->nr_hash_funcs; i++) {
>                 h = hash(bloom, value, map->value_size, i);
> -               set_bit(h, bloom->bitset);
> +               bloom_set_bit(bloom, h);
>         }
>
>         return 0;
> @@ -94,9 +110,10 @@ static int bloom_map_alloc_check(union bpf_attr *attr)
>
>  static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
>  {
> -       u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
> +       u32 bitset_mask, nr_hash_funcs, nr_bits;
>         int numa_node = bpf_map_attr_numa_node(attr);
>         struct bpf_bloom_filter *bloom;
> +       u64 bitset_bytes;
>
>         if (attr->key_size != 0 || attr->value_size == 0 ||
>             attr->max_entries == 0 ||
> @@ -127,21 +144,16 @@ static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
>         if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
>             check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
>             nr_bits > (1UL << 31)) {
> -               /* The bit array size is 2^32 bits but to avoid overflowing the
> -                * u32, we use U32_MAX, which will round up to the equivalent
> -                * number of bytes
> -                */
> -               bitset_bytes = BITS_TO_BYTES(U32_MAX);
>                 bitset_mask = U32_MAX;
>         } else {
>                 if (nr_bits <= BITS_PER_LONG)
>                         nr_bits = BITS_PER_LONG;
>                 else
>                         nr_bits = roundup_pow_of_two(nr_bits);
> -               bitset_bytes = BITS_TO_BYTES(nr_bits);
>                 bitset_mask = nr_bits - 1;
>         }
>
> +       bitset_bytes = BITS_TO_BYTES((u64)bitset_mask + 1);
>         bitset_bytes = roundup(bitset_bytes, sizeof(unsigned long));

should we do just

bitset_bytes = BITS_TO_LONGS((u64)bitset_mask + 1) * sizeof(unsigned long);



>         bloom = bpf_map_area_alloc(sizeof(*bloom) + bitset_bytes, numa_node);
>
> --
> 2.47.3
>