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

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

Joanne Koong 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.

hmm I'm wondering if this means the memory footprint can grow without
bounds? Typically maps have an upper bound on memory established at
alloc time.

In queue_stack_map_alloc() we have,

 queue_size = sizeof(*qs) + size * attr->value_size);
 bpf_map_area_alloc(queue_size, numa_node) 

In hashmap (not preallocated)  we have, alloc_htab_elem() that will
give us an upper bound.

Is there a practical value in allowing these to grow endlessly? And
should we be charging the value memory against something? In
bpf_map_kmalloc_node we set_active_memcg() for example.
 
I'll review code as well, but think above is worth some thought.

> 
> 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>