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