Thanks for the review Ben! Pushed to master with the changes proposed,
Jarno On Dec 11, 2013, at 10:38 AM, Ben Pfaff <[email protected]> wrote: > On Mon, Dec 09, 2013 at 06:35:58PM -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 <[email protected]> >> >> v6: Address Ben's review comments. >> >> v5: >> - Refactoring and cleaning up based on Ben's comments. >> - Ben's updated commentary on lib/classifier.h. >> - Explain the prefix offset numbering used in comments. >> - Get more of a prefix from the next word if necessary. >> - Refactor to eliminate duplicated code. >> - trie_remove(): Also prune parent nodes if possible. >> - schema: Changed "fieldspec" smap to "prefixes" set. >> - removed support for metadata field, as it has no datapath equivalent. >> - Added NEWS. >> >> v4: >> >> - Remove easily perishable comments from classifier.h >> - Make mf_field.flow_u32ofs -1 for registers, making registers not >> supported as prefix lookup fields. Registers are held in host byte >> order, whereas current implementation only works for network byte >> order. >> - Use 'u32ofs' instead of 'be32ofs' to make the above more clear. >> - Check for prefix lookup field compatibility at >> classifier_set_prefix_fields() and remove redundant checks from >> minimask_get_prefix_len(), trie_insert(), and trie_remove(). >> - Simplify minimask_get_prefix_len(), separate out >> minimatch_get_prefix(). >> - Make trie_insert() and trie_remove() take CIDR mask length as a >> parameter instead of finding the mask length again. Call >> trie_insert() or trie_remove() only with a non-zero (and positive) >> prefix length. >> - Make trie_init() destroy existing trie (if any) and accept NULL >> field, allowing classifier_set_prefix_fields() to be simplified. >> - Detect duplicate prefix fields on set-up. >> - Add "fieldspec" documentation to vswitch.xml >> - Add IPv6 trie testing, verifying that crossing 32-bit boundaries in >> masks works. > > Acked-by: Ben Pfaff <[email protected]> > > Here are some changes you may consider, but none of them is more than > cosmetic. > > diff --git a/lib/classifier.c b/lib/classifier.c > index e9a13d0..8b5c36a 100644 > --- a/lib/classifier.c > +++ b/lib/classifier.c > @@ -198,9 +198,7 @@ classifier_destroy(struct classifier *cls) > int i; > > for (i = 0; i < cls->n_tries; i++) { > - if (cls->tries[i].root) { > - trie_destroy(cls->tries[i].root); > - } > + trie_destroy(cls->tries[i].root); > } > > HMAP_FOR_EACH_SAFE (subtable, next_subtable, hmap_node, > @@ -235,7 +233,7 @@ classifier_set_prefix_fields(struct classifier *cls, > const struct mf_field *field = mf_from_id(trie_fields[i]); > if (field->flow_be32ofs < 0 || field->n_bits % 32) { > /* Incompatible field. This is the only place where we > - * Enforce these requirements, but the rest of the trie code > + * enforce these requirements, but the rest of the trie code > * depends on the flow_be32ofs to be non-negative and the > * field length to be a multiple of 32 bits. */ > continue; > @@ -268,7 +266,7 @@ trie_init(struct classifier *cls, int trie_idx, > struct cls_trie *trie = &cls->tries[trie_idx]; > struct cls_subtable *subtable; > > - if (trie_idx < cls->n_tries && trie->root) { > + if (trie_idx < cls->n_tries) { > trie_destroy(trie->root); > } > trie->root = NULL; > @@ -1353,13 +1351,11 @@ trie_node_destroy(struct trie_node *node) > static void > trie_destroy(struct trie_node *node) > { > - if (node->edges[0]) { > + if (node) { > trie_destroy(node->edges[0]); > - } > - if (node->edges[1]) { > trie_destroy(node->edges[1]); > + free(node); > } > - free(node); > } > > static bool
_______________________________________________ dev mailing list [email protected] http://openvswitch.org/mailman/listinfo/dev
