[ovs-dev] [PATCH v5 4/4] Classifier: Track address prefixes.
Jarno Rajahalme
jrajahalme at nicira.com
Fri Dec 6 21:26:16 UTC 2013
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>
More information about the dev
mailing list