Re: [PATCH nft v3 2/2] datatype: Implement binary search in symbolic_constant_print()

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

On Mon, Nov 28, 2016 at 11:12:23PM +0100, Florian Westphal wrote:
> Elise Lennion <elise.lennion@gmail.com> wrote:
> > Because a linear search is used, which is slower.
> > 
> > This approach demands that the symbol_table have a variable with its
> > size, also, it must be sorted by value.
> 
> Did Pablo put you up to this?  Bad Pablo, bad!  :-P

Yep, Elise don't feel bad, that's my fault ;-)

> because:
> 
> >  static const struct symbol_table ethertype_tbl = {
> > +	.size 		= 4,
> >  	.symbols	= {
> >  		SYMBOL("ip",		__constant_htons(ETH_P_IP)),
> > +		SYMBOL("vlan",		__constant_htons(ETH_P_8021Q)),
> >  		SYMBOL("arp",		__constant_htons(ETH_P_ARP)),
> >  		SYMBOL("ip6",		__constant_htons(ETH_P_IPV6)),
> > -		SYMBOL("vlan",		__constant_htons(ETH_P_8021Q)),
> >  		SYMBOL_LIST_END
> >  	},
> 
> This is unmaintanable.  I have no clue what value ETH_P_8021Q is, and that
> this has to be placed at spot #2 to not break things.

OK, let's try to make this a bit more maintainable, another proposal
in steps:

1) Update symbol_table definition to:

struct symbol_table {
        unsignd int                     size;
        const struct symbolic_constant  *symbols; <---
};

so we don't have a flexible array anymore. Then, split this array of
symbols from struct symbol_table so this looks like:

static cont struct symbolic_constant ethertype_symbols[] = {
 		SYMBOL("ip",		__constant_htons(ETH_P_IP)),
		SYMBOL("vlan",		__constant_htons(ETH_P_8021Q)),
 		SYMBOL("arp",		__constant_htons(ETH_P_ARP)),
  		SYMBOL("ip6",		__constant_htons(ETH_P_IPV6)),
  		SYMBOL_LIST_END
};

static const struct symbol_table ethertype_tbl = {
        .size                   = SYMTBL_SIZE(ethertype_symbols),
        .symbolic_constant      = ethertype_symbols,
};

I can see 19 symbol_tables from here at quick glace, so this would be
an initial patch to update this. SYMTBL_SIZE needs to be define too, yes.

2) Then, second patch would look like:

struct symbol_table {
        unsignd int                     size;
        bool                            qsort; <---
        const struct symbolic_constant  *symbols;
};

If qsort field if true, then we can just validate when calling
datatype_register() that the array is not sorted and spot a BUG().
Moreover, the new qsort field would restrict this qsort to the large
inet_service symbol table.

Florian, are you OK if Elise follows this approach? If this is overly
complicated and not worth, rise your hand.