Re: [PATCH 1/2 nf] netfilter: nft_set_bitmap: keep a list of dummy elements

[Pablo Neira Ayuso <pablo@netfilter.org>]

Hi Liping,

On Mon, Mar 13, 2017 at 10:23:53PM +0800, Liping Zhang wrote:
> Hi Pablo,
> 
> 2017-03-13 20:27 GMT+08:00 Pablo Neira Ayuso <pablo@netfilter.org>:
> > Element comments may come without any prior set flag, so we have to keep
> > a list of dummy struct nft_set_ext to keep this information around. This
> > is only useful for set dumps to userspace. From the packet path, this
> > set type relies on the bitmap representation. This patch simplifies the
> > logic since we don't need to allocate the dummy nft_set_ext structure
> > anymore on the fly at the cost of increasing memory consumption because
> > of the list of dummy struct nft_set_ext.
> 
> If I didn't misunderstand it, I think after introducing the dummy nft_set_ext,
> the nft_bitmap_estimate() should also be updated? i.e.:
> 
> 1. est->size should be recalculated
> 2. est->space should be changed to NFT_SET_CLASS_O_N

I would like this only describes the representation that is exposed to
the packet path, not the real memory consumption of it. I know I'm
kind of cheating, but with this I'm also giving this bitmap an
advantage over the hashtable representation, the performance numbers I
gathered here when evaluating it are better.

Anyway, I'll be fine if this triggers some discussions on the set
backend selection at some point, as well as more detailed performance
evaluation. Note this big O notation just tell about the scalability.
Size provides an accurate way to measure how much memory this consumes
but only if userspace tells us how many elements we're going to add
beforehand. On the CPU side, we have no such specific metric as the
memory size. Probably we can introduce some generic cycle metric that
represents the cost of the lookup path, this won't be simple as this
number is not deterministic since there are many things to consider,
so we have to agree on how we calculate this pseudo-metric.