Re: [PATCH v5 bpf-next 1/5] bpf: Add bloom filter map implementation

[Joanne Koong <joannekoong@fb.com>]

On 10/25/21 5:43 PM, Martin KaFai Lau wrote:

> On Fri, Oct 22, 2021 at 03:02:45PM -0700, Joanne Koong wrote:
>
[...]
>> +static struct bpf_map *map_alloc(union bpf_attr *attr)
>> +{
>> +	u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
>> +	int numa_node = bpf_map_attr_numa_node(attr);
>> +	struct bpf_bloom_filter *bloom;
>> +
>> +	if (!bpf_capable())
>> +		return ERR_PTR(-EPERM);
>> +
>> +	if (attr->key_size != 0 || attr->value_size == 0 ||
>> +	    attr->max_entries == 0 ||
>> +	    attr->map_flags & ~BLOOM_CREATE_FLAG_MASK ||
>> +	    !bpf_map_flags_access_ok(attr->map_flags) ||
>> +	    (attr->map_extra & ~0xF))
>> +		return ERR_PTR(-EINVAL);
>> +
>> +	/* The lower 4 bits of map_extra specify the number of hash functions */
>> +	nr_hash_funcs = attr->map_extra & 0xF;
>> +	if (nr_hash_funcs == 0)
>> +		/* Default to using 5 hash functions if unspecified */
>> +		nr_hash_funcs = 5;
>> +
>> +	/* For the bloom filter, the optimal bit array size that minimizes the
>> +	 * false positive probability is n * k / ln(2) where n is the number of
>> +	 * expected entries in the bloom filter and k is the number of hash
>> +	 * functions. We use 7 / 5 to approximate 1 / ln(2).
>> +	 *
>> +	 * We round this up to the nearest power of two to enable more efficient
>> +	 * hashing using bitmasks. The bitmask will be the bit array size - 1.
>> +	 *
>> +	 * If this overflows a u32, the bit array size will have 2^32 (4
>> +	 * GB) bits.
>> +	 */
>> +	if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
> Comparing with v4, it is using max_entries to mean number
> of values instead of bits and also not exposing
> BPF_BLOOM_FILTER_BITSET_SZ macro to calculate the number of bits.
> just want to ensure it is the intention in v5 since I don't see it
> in the change log.
Yes, this is the intention. Sorry for not making that clear in the 
change log.
I will add that to the change log!
[...]