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

[Jarno Rajahalme]

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'll have more comments later today.

OK, thanks!

  Jarno

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-dev/attachments/20131206/c548e29e/attachment-0003.html>