On Fri, Sep 17, 2021 at 6:08 PM Alexei Starovoitov
<alexei.starovoitov@xxxxxxxxx> wrote:
>
> On Mon, Sep 13, 2021 at 09:04:30PM -0700, Joanne Koong wrote:
> > +
> > +/* For bloom filter maps, the next 4 bits represent how many hashes to use.
> > + * The maximum number of hash functions supported is 15. If this is not set,
> > + * the default number of hash functions used will be 5.
> > + */
> > + BPF_F_BLOOM_FILTER_HASH_BIT_1 = (1U << 13),
> > + BPF_F_BLOOM_FILTER_HASH_BIT_2 = (1U << 14),
> > + BPF_F_BLOOM_FILTER_HASH_BIT_3 = (1U << 15),
> > + BPF_F_BLOOM_FILTER_HASH_BIT_4 = (1U << 16),
>
> The bit selection is unintuitive.
> Since key_size has to be zero may be used that instead to indicate the number of hash
> functions in the rare case when 5 is not good enough?
Hm... I was initially thinking about proposing something like that,
but it felt a bit ugly at the time. But now thinking about this a bit
more, I think this would be a bit more meaningful if we change the
terminology a bit. Instead of saying that Bloom filter has values and
no keys, we actually have keys and no values. So all those bytes that
are hashed are treated as keys (which is actually how sets are
implemented on top of maps, where you have keys and no values, or at
least the value is always true).
So with that we'll have key/key_size to specify number of bytes that
needs to be hashed (and it's type info). And then we can squint a bit
and say that number of hashes are specified by value_size, as in
values are those nr_hash bits that we set in Bloom filter.
Still a bit of terminology stretch, but won't necessitate those
specialized fields just for Bloom filter map. But if default value is
going to be good enough for most cases and most cases won't need to
adjust number of hashes, this seems to be pretty clean to me.
> Or use inner_map_fd since there is no possibility of having an inner map in bloomfilter.
> It could be a union:
> __u32 max_entries; /* max number of entries in a map */
> __u32 map_flags; /* BPF_MAP_CREATE related
> * flags defined above.
> */
> union {
> __u32 inner_map_fd; /* fd pointing to the inner map */
> __u32 nr_hash_funcs; /* or number of hash functions */
> };
This works as well. A bit more Bloom filter-only terminology
throughout UAPI and libbpf, but I'd be fine with that as well.
> __u32 numa_node; /* numa node */
>
> > +struct bpf_bloom_filter {
> > + struct bpf_map map;
> > + u32 bit_array_mask;
> > + u32 hash_seed;
> > + /* If the size of the values in the bloom filter is u32 aligned,
> > + * then it is more performant to use jhash2 as the underlying hash
> > + * function, else we use jhash. This tracks the number of u32s
> > + * in an u32-aligned value size. If the value size is not u32 aligned,
> > + * this will be 0.
> > + */
> > + u32 aligned_u32_count;
>
> what is the performance difference?
> May be we enforce 4-byte sized value for simplicity?
This might be a bit too surprising, especially if keys are just some
strings, where people might not expect that it has to 4-byte multiple
size. And debugging this without extra tooling (like retsnoop) is
going to be nightmarish.
If the performance diff is huge and that if/else logic is
unacceptable, we can also internally pad with up to 3 zero bytes and
include those into the hash.
