[ovs-dev] [PATCH v6 2/2] Classifier: Track address prefixes.

Ben Pfaff blp at nicira.com
Wed Dec 11 18:38:09 UTC 2013


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 <jrajahalme at 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 <blp at 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



More information about the dev mailing list