On Mon, Sep 27, 2021 at 02:14:09PM -0700, Andrii Nakryiko wrote:
> On Mon, Sep 27, 2021 at 9:41 AM Alexei Starovoitov
> <alexei.starovoitov@xxxxxxxxx> wrote:
> >
> > On Fri, Sep 24, 2021 at 04:12:11PM -0700, Andrii Nakryiko wrote:
> > >
> > > That's not what I proposed. So let's say somewhere in the kernel we
> > > have this variable:
> > >
> > > static int bpf_bloom_exists = 1;
> > >
> > > Now, for bpf_map_lookup_elem() helper we pass data as key pointer. If
> > > all its hashed bits are set in Bloom filter (it "exists"), we return
> > > &bpf_bloom_exists. So it's not a NULL pointer.
> >
> > imo that's too much of a hack.
>
> too bad, because this feels pretty natural in BPF code:
>
> int my_key = 1234;
>
> if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) {
> /* handle "maybe exists" */
> } else {
> /* handle "definitely doesn't exist" */
> }
I don't think it fits bitset map.
In the bitset the value is zero or one. It always exist.
If bloomfilter is not a special map and instead implemented on top of
generic bitset with a plain loop in a bpf program then
push -> bit_set
pop -> bit_clear
peek -> bit_test
would be a better fit for bitset map.
bpf_map_pop_elem() and peek_elem() don't have 'flags' argument.
In most cases that would be a blocker,
but in this case we can add:
.arg3_type = ARG_ANYTHING
and ignore it in case of stack/queue.
While bitset could use the flags as an additional seed into the hash.
So to do a bloomfilter the bpf prog would do:
for (i = 0; i < 5; i++)
if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))
Probably would still be an improvement to add:
static inline long bpf_bit_test(void *map, void *value, long flags)
{
return bpf_map_peek_elem(map, value, flags);
}
to some header file.
Or maybe bloomfilter and the loop can be a flavor of bitset map and
done inside the helper to spare bpf programmers doing the manual loops.
Or such loop could be another static inline function in a header file?
