On Fri, Oct 08, 2021 at 04:24:58PM -0700, Zvi Effron wrote: > On Fri, Oct 8, 2021 at 4:05 PM Andrii Nakryiko > <andrii.nakryiko@xxxxxxxxx> wrote: > > > > On Wed, Oct 6, 2021 at 3:27 PM Joanne Koong <joannekoong@xxxxxx> wrote: > > > > > > This patch adds the kernel-side changes for the implementation of > > > a bitset map with bloom filter capabilities. > > > > > > The bitset map does not have keys, only values since it is a > > > non-associative data type. When the bitset map is created, it must > > > be created with a key_size of 0, and the max_entries value should be the > > > desired size of the bitset, in number of bits. > > > > > > The bitset map supports peek (determining whether a bit is set in the > > > map), push (setting a bit in the map), and pop (clearing a bit in the > > > map) operations. These operations are exposed to userspace applications > > > through the already existing syscalls in the following way: > > > > > > BPF_MAP_UPDATE_ELEM -> bpf_map_push_elem > > > BPF_MAP_LOOKUP_ELEM -> bpf_map_peek_elem > > > BPF_MAP_LOOKUP_AND_DELETE_ELEM -> bpf_map_pop_elem > > > > > > For updates, the user will pass in a NULL key and the index of the > > > bit to set in the bitmap as the value. For lookups, the user will pass > > > in the index of the bit to check as the value. If the bit is set, 0 > > > will be returned, else -ENOENT. For clearing the bit, the user will pass > > > in the index of the bit to clear as the value. > > > > > > Since we need to pass in the index of the bit to set/clear in the bitmap > > > > While I can buy that Bloom filter doesn't have a key, bitset clearly > > has and that key is bit index. Are we all sure that this marriage of > > bit set and bloom filter is the best API design? > > > > Adding on to this, as a user of the bpf helpers, peek, push, and pop have > meaning to me as operating on data structures for which those are well defined, > such as stacks and queues. For bitsets, "push"ing a bit doesn't make sense to > me as a concept, so needing to use bpf_map_push_elem to set a bit is not > intuitive to me. bpf_map_lookup_elem, bpf_map_update_elem, and > bpf_map_delete_elem make more sense to me (though if we have update, delete is > redundant). The peek, push, and pop helpers could be given a different name like test_bit, set_bit, and clear_bit in bpf_helper_defs.h. I think this was also mentioned in the earlier discussion.
