[ovs-dev] [PATCH v5 4/4] Classifier: Track address prefixes.

[Ben Pfaff]

On Fri, Dec 06, 2013 at 01:26:16PM -0800, Jarno Rajahalme wrote:
> 
> On Dec 6, 2013, at 11:02 AM, Ben Pfaff <blp at nicira.com> wrote:
> 
> > On Thu, Dec 05, 2013 at 04:27:26PM -0800, Jarno Rajahalme wrote:
> >> Add a prefix tree (trie) structure for tracking the used address
> >> space, enabling skipping classifier tables containing longer masks
> >> than necessary for an address field value in a packet header being
> >> classified.  This enables less unwildcarding for datapath flows in
> >> parts of the address space without host routes.
> >> 
> >> Trie lookup is interwoven to the staged lookup, so that a trie is
> >> searched only when the configured trie field becomes relevant
> >> for the lookup.  The trie lookup results are retained so that each
> >> trie is checked at most once for each classifier lookup.
> >> 
> >> This implementation tracks the number of rules at each address prefix
> >> for the whole classifier.  More aggressive table skipping would be
> >> possible by maintaining lists of tables that have prefixes at the
> >> lengths encountered on tree traversal, or by maintaining separate
> >> tries for subsets of rules separated by metadata fields.
> >> 
> >> Prefix tracking is configured via OVSDB.  A new column "prefixes" is
> >> added to the database table "Flow_Table".  "prefixes" is a set of
> >> string values listing the field names for which prefix lookup should
> >> be used.
> >> 
> >> As of now, the fields for which prefix lookup can be enabled are:
> >> - tun_id, tun_src, tun_dst
> >> - nw_src, nw_dst (or aliases ip_src and ip_dst)
> >> - ipv6_src, ipv6_dst
> >> 
> >> There is a maximum number of fields that can be enabled for any one
> >> flow table.  Currently this limit is 3.
> >> 
> >> Examples:
> >> 
> >> ovs-vsctl set Bridge br0 flow_tables:0=@N1 -- \
> >> --id=@N1 create Flow_Table name=table0
> >> ovs-vsctl set Bridge br0 flow_tables:1=@N1 -- \
> >> --id=@N1 create Flow_Table name=table1
> >> 
> >> ovs-vsctl set Flow_Table table0 prefixes=ip_dst,ip_src
> >> ovs-vsctl set Flow_Table table1 prefixes=[]
> >> 
> >> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> > 
> > Clang reports:
> >    ../lib/classifier.c:1570:40: error: bad constant expression
> > referring to this line in trie_remove():
> >    struct trie_node *nodes[trie->field->n_bytes];
> > 
> 
> Mine is not doing that, running clang 1:3.4~svn193316-1~exp1. Anyway
> allocating variable sized arrays from stack is a C99 feature that
> CodingStyle does not seem to mention. I guess it would be better
> avoiding it then and replace the size with the biggest possible
> (sizeof(union mf_value) * 8) (and I was missing the ?* 8? multiplier
> from it anyway, the size needs to be the max possible depth of the
> tree!

I find the message really puzzling too, since I'd expect Clang to
support VLAs.  But I doubt that, say, MSVC supports VLAs, so I'd
recommend using the biggest possible size.