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 <jrajaha...@nicira.com>
>
> 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 <b...@nicira.com>
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
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
