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

[John Fastabend <john.fastabend@gmail.com>]

Joanne Koong wrote:
> On 9/1/21 10:11 PM, John Fastabend wrote:
> 
> > Andrii Nakryiko wrote:
> >> On Tue, Aug 31, 2021 at 3:51 PM Joanne Koong <joannekoong@fb.com> wrote:
> >>> Bloom filters are a space-efficient probabilistic data structure
> >>> used to quickly test whether an element exists in a set.
> >>> In a bloom filter, false positives are possible whereas false
> >>> negatives are not.
> >>>
> >>> This patch adds a bloom filter map for bpf programs.
> >>> The bloom filter map supports peek (determining whether an element
> >>> is present in the map) and push (adding an element to the map)
> >>> operations.These operations are exposed to userspace applications
> >>> through the already existing syscalls in the following way:
> >>>
> >>> BPF_MAP_LOOKUP_ELEM -> peek
> >>> BPF_MAP_UPDATE_ELEM -> push
> >>>
> >>> The bloom filter map does not have keys, only values. In light of
> >>> this, the bloom filter map's API matches that of queue stack maps:
> >>> user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM
> >>> which correspond internally to bpf_map_peek_elem/bpf_map_push_elem,
> >>> and bpf programs must use the bpf_map_peek_elem and bpf_map_push_elem
> >>> APIs to query or add an element to the bloom filter map. When the
> >>> bloom filter map is created, it must be created with a key_size of 0.
> >>>
> >>> For updates, the user will pass in the element to add to the map
> >>> as the value, wih a NULL key. For lookups, the user will pass in the
> >>> element to query in the map as the value. In the verifier layer, this
> >>> requires us to modify the argument type of a bloom filter's
> >>> BPF_FUNC_map_peek_elem call to ARG_PTR_TO_MAP_VALUE; as well, in
> >>> the syscall layer, we need to copy over the user value so that in
> >>> bpf_map_peek_elem, we know which specific value to query.
> >>>
> >>> The maximum number of entries in the bloom filter is not enforced; if
> >>> the user wishes to insert more entries into the bloom filter than they
> >>> specified as the max entries size of the bloom filter, that is permitted
> >>> but the performance of their bloom filter will have a higher false
> >>> positive rate.
> >>>
> >>> The number of hashes to use for the bloom filter is configurable from
> >>> userspace. The benchmarks later in this patchset can help compare the
> >>> performances of different number of hashes on different entry
> >>> sizes. In general, using more hashes decreases the speed of a lookup,
> >>> but increases the false positive rate of an element being detected in the
> >>> bloom filter.
> >>>
> >>> Signed-off-by: Joanne Koong <joannekoong@fb.com>

[...]

> >>> +static struct bpf_map *bloom_filter_map_alloc(union bpf_attr *attr)
> >>> +{
> >>> +       int numa_node = bpf_map_attr_numa_node(attr);
> >>> +       u32 nr_bits, bit_array_bytes, bit_array_mask;
> >>> +       struct bpf_bloom_filter *bloom_filter;
> >>> +
> >>> +       if (!bpf_capable())
> >>> +               return ERR_PTR(-EPERM);
> >>> +
> >>> +       if (attr->key_size != 0 || attr->value_size == 0 || attr->max_entries == 0 ||
> >>> +           attr->nr_hashes == 0 || attr->map_flags & ~BLOOM_FILTER_CREATE_FLAG_MASK ||
> >>> +           !bpf_map_flags_access_ok(attr->map_flags))
> >>> +               return ERR_PTR(-EINVAL);
> >>> +
> >>> +       /* 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.
> > Would it be better to return E2BIG or EINVAL here? Speculating a bit, but if I was
> > a user I might want to know that the number of bits I pushed down is not the actual
> > number?
> 
> I think if we return E2BIG or EINVAL here, this will fail to create the 
> bloom filter map
> if the max_entries exceeds some limit (~3 billion, according to my math) 
> whereas
> automatically setting the bit array size to 2^32 if the max_entries is
> extraordinarily large will still allow the user to create and use a 
> bloom filter (albeit
> one with a higher false positive rate).

It doesn't matter much to me, but I think if a user request 3+billion max entries
its ok to return E2BIG and then they can use a lower limit and know the
false positive rate is going to go up. 

> 
> > Another thought, would it be simpler to let user do this calculation and just let
> > max_elements be number of bits they want? Then we could have examples with the
> > above comment. Just a thought...
> 
> I like Martin's idea of keeping the max_entries meaning consistent 
> across all map types.
> I think that makes the interface clearer for users.

I'm convinced as well, lets keep it consistent. Thanks.

[...]

> >> Also, I wonder if ditching spinlock in favor of atomic bit set
> >> operation would improve performance in typical scenarios. Seems like
> >> set_bit() is an atomic operation, so it should be easy to test. Do you
> >> mind running benchmarks with spinlock and with set_bit()?
> > With the jhash pulled out of lock, I think it might be noticable. Curious
> > to see.
> Awesome, I will test this out and report back!

It looks like the benchmark tests were done with value size of __u64 should
we do larger entry? I guess (you tell me?) if this is used from XDP for
DDOS you would use a flow tuple and with IPv6 this could be
{dstIp, srcIp, sport, dport, proto} with roughly 44B.

> >>> +       for (i = 0; i < bloom_filter->map.nr_hashes; i++) {
> >>> +               hash = jhash(value, map->value_size, bloom_filter->hash_seed + i) &
> >>> +                       bloom_filter->bit_array_mask;
> >>> +               bitmap_set(bloom_filter->bit_array, hash, 1);
> >>> +       }
> >>> +
> >>> +       spin_unlock_irqrestore(&bloom_filter->spinlock, spinlock_flags);
> >>> +
> >>> +       return 0;
> >>> +}
> >>> +
> >> [...]
> >