[ovs-dev] [PATCH 3/4] lib/classifier: Return all matching prefix lengths from trie lookup.

Jarno Rajahalme jrajahalme at nicira.com
Fri Jul 11 11:55:56 UTC 2014


Previously we only returned the last matching prefix length
encountered during a trie lookup, and skipped subtables that had
prefixes longer than that.  This patch changes the trie lookup
functions to return all matching prefix lengths seen, so that all
non-matching prefix lengths can be skipped.

Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
 lib/classifier.c |   75 ++++++++++++++++++++++++++++++------------------------
 1 file changed, 42 insertions(+), 33 deletions(-)

diff --git a/lib/classifier.c b/lib/classifier.c
index d400180..cd4de54 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -151,11 +151,10 @@ static void trie_init(struct classifier *cls, int trie_idx,
                       const struct mf_field *)
     OVS_REQUIRES(cls->mutex);
 static unsigned int trie_lookup(const struct cls_trie *, const struct flow *,
-                                unsigned int *checkbits);
+                                union mf_value *plens);
 static unsigned int trie_lookup_value(const rcu_trie_ptr *,
-                                      const ovs_be32 value[],
-                                      unsigned int value_bits,
-                                      unsigned int *checkbits);
+                                      const ovs_be32 value[], ovs_be32 plens[],
+                                      unsigned int value_bits);
 static void trie_destroy(rcu_trie_ptr *);
 static void trie_insert(struct cls_trie *, const struct cls_rule *, int mlen);
 static void trie_insert_prefix(rcu_trie_ptr *, const ovs_be32 *prefix,
@@ -877,8 +876,8 @@ struct trie_ctx {
     const struct cls_trie *trie;
     bool lookup_done;        /* Status of the lookup. */
     uint8_t be32ofs;         /* U32 offset of the field in question. */
-    unsigned int match_plen; /* Longest prefix than could possibly match. */
     unsigned int maskbits;   /* Prefix length needed to avoid false matches. */
+    union mf_value match_plens; /* Longest prefix than could possibly match. */
 };
 
 static void
@@ -1410,6 +1409,8 @@ struct range {
     uint8_t end;
 };
 
+static unsigned int be_get_bit_at(const ovs_be32 value[], unsigned int ofs);
+
 /* Return 'true' if can skip rest of the subtable based on the prefix trie
  * lookup results. */
 static inline bool
@@ -1433,14 +1434,14 @@ check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
             if (be32ofs >= ofs.start && be32ofs < ofs.end) {
                 /* On-demand trie lookup. */
                 if (!ctx->lookup_done) {
-                    ctx->match_plen = trie_lookup(ctx->trie, flow,
-                                                  &ctx->maskbits);
+                    memset(&ctx->match_plens, 0, sizeof ctx->match_plens);
+                    ctx->maskbits = trie_lookup(ctx->trie, flow,
+                                                &ctx->match_plens);
                     ctx->lookup_done = true;
                 }
                 /* Possible to skip the rest of the subtable if subtable's
-                 * prefix on the field is longer than what is known to match
-                 * based on the trie lookup. */
-                if (field_plen[j] > ctx->match_plen) {
+                 * prefix on the field is not included in the lookup result. */
+                if (!be_get_bit_at(&ctx->match_plens.be32, field_plen[j] - 1)) {
                     /* RFC: We want the trie lookup to never result in
                      * unwildcarding any bits that would not be unwildcarded
                      * otherwise.  Since the trie is shared by the whole
@@ -1629,11 +1630,11 @@ find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
          * No match was found for the ports.  Use the ports trie to figure out
          * which ports bits to unwildcard. */
         unsigned int mbits;
-        ovs_be32 value, mask;
+        ovs_be32 value, plens, mask;
 
         mask = MINIFLOW_GET_BE32(&subtable->mask.masks, tp_src);
         value = ((OVS_FORCE ovs_be32 *)flow)[TP_PORTS_OFS32] & mask;
-        trie_lookup_value(&subtable->ports_trie, &value, 32, &mbits);
+        mbits = trie_lookup_value(&subtable->ports_trie, &value, &plens, 32);
 
         ((OVS_FORCE ovs_be32 *)&wc->masks)[TP_PORTS_OFS32] |=
             mask & htonl(~0 << (32 - mbits));
@@ -1987,19 +1988,28 @@ trie_next_node(const struct trie_node *node, const ovs_be32 value[],
                       &node->edges[be_get_bit_at(value, ofs)]);
 }
 
-/* Return the prefix mask length necessary to find the longest-prefix match for
- * the '*value' in the prefix tree 'node'.
- * '*checkbits' is set to the number of bits in the prefix mask necessary to
- * determine a mismatch, in case there are longer prefixes in the tree below
- * the one that matched.
+/* Set the bit at ("MSB 0"-based) offset 'ofs'.  'ofs' can be greater than 31.
+ */
+static void
+be_set_bit_at(ovs_be32 value[], unsigned int ofs)
+{
+    ((uint8_t *)value)[ofs / 8] |= 1u << (7 - ofs % 8);
+}
+
+/* Returns the number of bits in the prefix mask necessary to determine a
+ * mismatch, in case there are longer prefixes in the tree below the one that
+ * matched.
+ * '*plens' will have a bit set for each prefix length that may have matching
+ * rules.  The caller is responsible for clearing the '*plens' prior to
+ * calling this.
  */
 static unsigned int
 trie_lookup_value(const rcu_trie_ptr *trie, const ovs_be32 value[],
-                  unsigned int n_bits, unsigned int *checkbits)
+                  ovs_be32 plens[], unsigned int n_bits)
 {
-    const struct trie_node *node = ovsrcu_get(struct trie_node *, trie);
-    unsigned int m_bits = 0, match_len = 0;
     const struct trie_node *prev = NULL;
+    const struct trie_node *node = ovsrcu_get(struct trie_node *, trie);
+    unsigned int m_bits = 0; /* Number of matching bits. */
 
     for (; node; prev = node, node = trie_next_node(node, value, m_bits)) {
         unsigned int eqbits;
@@ -2008,27 +2018,26 @@ trie_lookup_value(const rcu_trie_ptr *trie, const ovs_be32 value[],
         m_bits += eqbits;
         if (eqbits < node->n_bits) { /* Mismatch, nothing more to be found. */
             /* Bit at offset 'm_bits' differed. */
-            *checkbits = m_bits + 1; /* Includes the first mismatching bit. */
-            return match_len;
+            return m_bits + 1; /* Includes the first mismatching bit. */
         }
         /* Full match, check if rules exist at this prefix length. */
         if (node->n_rules > 0) {
-            match_len = m_bits;
+            be_set_bit_at(plens, m_bits - 1);
         }
         if (m_bits >= n_bits) {
-            *checkbits = n_bits; /* Full prefix. */
-            return match_len;
+            return n_bits; /* Full prefix. */
         }
     }
-    /* node == NULL.  Full match so far, but we came to a dead end.
-     * need to exclude the other branch if it exists. */
-    *checkbits = !prev || trie_is_leaf(prev) ? m_bits : m_bits + 1;
-    return match_len;
+    /* node == NULL.  Full match so far, but we tried to follow an
+     * non-existing branch.  Need to exclude the other branch if it exists
+     * (it does not if we were called on an empty trie or 'prev' is a leaf
+     * node). */
+    return !prev || trie_is_leaf(prev) ? m_bits : m_bits + 1;
 }
 
 static unsigned int
 trie_lookup(const struct cls_trie *trie, const struct flow *flow,
-            unsigned int *checkbits)
+            union mf_value *plens)
 {
     const struct mf_field *mf = trie->field;
 
@@ -2038,10 +2047,10 @@ trie_lookup(const struct cls_trie *trie, const struct flow *flow,
     if (mf_are_prereqs_ok(mf, flow)) {
         return trie_lookup_value(&trie->root,
                                  &((ovs_be32 *)flow)[mf->flow_be32ofs],
-                                 mf->n_bits, checkbits);
+                                 &plens->be32, mf->n_bits);
     }
-    *checkbits = 0; /* Value not used in this case. */
-    return UINT_MAX;
+    memset(plens, 0xff, sizeof *plens); /* All prefixes, no skipping. */
+    return 0; /* Value not used in this case. */
 }
 
 /* Returns the length of a prefix match mask for the field 'mf' in 'minimask'.
-- 
1.7.10.4




More information about the dev mailing list