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

From: Martin KaFai Lau <kafai@fb.com>
To: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Joanne Koong <joannekoong@fb.com>, bpf <bpf@vger.kernel.org>,
	Kernel Team <Kernel-team@fb.com>
Subject: Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Date: Wed, 22 Sep 2021 18:28:49 -0700	[thread overview]
Message-ID: <20210923012849.qfgammwxxcd47fgn@kafai-mbp.dhcp.thefacebook.com> (raw)
In-Reply-To: <CAEf4BzaQ42NTx9tcP43N-+SkXbFin9U+jSVy6HAmO8e+Cci5Dw@mail.gmail.com>

On Wed, Sep 22, 2021 at 04:07:52PM -0700, Andrii Nakryiko wrote:
> > > Please see my RFC ([0]). I don't think there is much to coordinate. It
> > > could be purely BPF-side code, or BPF + user-space initialization
> > > code, depending on the need. It's a simple and beautiful algorithm,
> > > which BPF is powerful enough to implement customly and easily.
> > >
> > >   [0] https://lore.kernel.org/bpf/20210922203224.912809-1-andrii@kernel.org/T/#t
> > In practice, the bloom filter will be populated only once by the userspace.
> >
> > The future update will be done by map-in-map to replace the whole bloom filter.
> > May be with more max_entries with more nr_hashes.  May be fewer
> > max_entries with fewer nr_hashes.
> >
> > Currently, the continuous running bpf prog using this bloom filter does
> > not need to worry about any change in the newer bloom filter
> > configure/setup.
> >
> > I wonder how that may look like in the custom bpf bloom filter in the
> > bench prog for the map-in-map usage.
> 
> You'd have to use BPF_MAP_TYPE_ARRAY for the map-in-map use case.
Right, another map is needed.  When the user space generates
a new bloom filter as inner map, it is likely that it has different
number of entries, so the map size is different.

The old and new inner array map need to at least have the same value_size,
so an one element array with different value_size will not work.

The inner array map with BPF_F_INNER_MAP can have different max_entries
but then there is no inline code lookup generation.  It may not be too
bad to call it multiple times to lookup a value considering the
array_map_lookup_elem will still be directly called without retpoline.
The next part is how to learn those "const volatile __u32 bloom_*;"
values of the new inner map.  I think the max_entires can be obtained
by map_ptr->max_entries.   Other vars (e.g. hash_cnt and seed) can
be used as non-const global, allow the update, and a brief moment of
inconsistence may be fine.

It all sounds doable but all these small need-to-pay-attention
things add up.