X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=lib%2Fclassifier.c;h=ee78dadd95d80cba9bab0656359420de7d6622be;hb=a0bc29a541fc7dc6e20137d5558e2094d614e6ab;hp=f4280ef0c2c989b68538a35f7f2846f2fe723d19;hpb=a4af00400a835eb87569ba40e21874c05e872c0f;p=openvswitch

diff --git a/lib/classifier.c b/lib/classifier.c
index f4280ef0..ee78dadd 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -19,6 +19,7 @@
 #include <assert.h>
 #include <errno.h>
 #include <netinet/in.h>
+#include "dynamic-string.h"
 #include "flow.h"
 #include "hash.h"
 
@@ -48,6 +49,8 @@ static struct cls_rule *search_exact_table(const struct classifier *,
                                            size_t hash, const flow_t *);
 static bool rules_match_1wild(const struct cls_rule *fixed,
                               const struct cls_rule *wild, int field_idx);
+static bool rules_match_2wild(const struct cls_rule *wild1,
+                              const struct cls_rule *wild2, int field_idx);
 
 /* Converts the flow in 'flow' into a cls_rule in 'rule', with the given
  * 'wildcards' and 'priority'.*/
@@ -55,7 +58,7 @@ void
 cls_rule_from_flow(struct cls_rule *rule, const flow_t *flow,
                    uint32_t wildcards, unsigned int priority)
 {
-    assert(flow->reserved == 0);
+    assert(!flow->reserved[0] && !flow->reserved[1] && !flow->reserved[2]);
     rule->flow = *flow;
     flow_wildcards_init(&rule->wc, wildcards);
     rule->priority = priority;
@@ -75,6 +78,18 @@ cls_rule_from_match(struct cls_rule *rule, const struct ofp_match *match,
     rule->table_idx = table_idx_from_wildcards(rule->wc.wildcards);
 }
 
+/* Converts 'rule' to a string and returns the string.  The caller must free
+ * the string (with free()). */
+char *
+cls_rule_to_string(const struct cls_rule *rule)
+{
+    struct ds s = DS_EMPTY_INITIALIZER;
+    ds_put_format(&s, "wildcards=%x priority=%u ",
+                  rule->wc.wildcards, rule->priority);
+    flow_format(&s, &rule->flow);
+    return ds_cstr(&s);
+}
+
 /* Prints cls_rule 'rule', for debugging.
  *
  * (The output could be improved and expanded, but this was good enough to
@@ -336,6 +351,43 @@ classifier_find_rule_exactly(const struct classifier *cls,
     return NULL;
 }
 
+/* Checks if the flow defined by 'target' with 'wildcards' at 'priority' 
+ * overlaps with any other rule at the same priority in the classifier.  
+ * Two rules are considered overlapping if a packet could match both. */
+bool
+classifier_rule_overlaps(const struct classifier *cls,
+                         const flow_t *target, uint32_t wildcards,
+                         unsigned int priority)
+{
+    struct cls_rule target_rule;
+    const struct hmap *tbl;
+
+    if (!wildcards) {
+        return search_exact_table(cls, flow_hash(target, 0), target) ?
+            true : false;
+    }
+
+    cls_rule_from_flow(&target_rule, target, wildcards, priority);
+
+    for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) {
+        struct cls_bucket *bucket;
+
+        HMAP_FOR_EACH (bucket, struct cls_bucket, hmap_node, tbl) {
+            struct cls_rule *rule;
+
+            LIST_FOR_EACH (rule, struct cls_rule, node.list,
+                           &bucket->rules) {
+                if (rule->priority == priority 
+                        && rules_match_2wild(rule, &target_rule, 0)) {
+                    return true;
+                }
+            }
+        }
+    }
+
+    return false;
+}
+
 /* Ignores target->priority.
  *
  * 'callback' is allowed to delete the rule that is passed as its argument, but
@@ -588,14 +640,14 @@ bucket_insert(struct cls_bucket *bucket, struct cls_rule *rule)
 {
     struct cls_rule *pos;
     LIST_FOR_EACH (pos, struct cls_rule, node.list, &bucket->rules) {
-        if (pos->priority <= rule->priority) {
-            if (pos->priority == rule->priority
-                && pos->wc.wildcards == rule->wc.wildcards
+        if (pos->priority == rule->priority) {
+            if (pos->wc.wildcards == rule->wc.wildcards
                 && rules_match_1wild(pos, rule, rule->table_idx))
             {
                 list_replace(&rule->node.list, &pos->node.list);
                 return pos;
             }
+        } else if (pos->priority < rule->priority) {
             break;
         }
     }
@@ -764,6 +816,23 @@ rules_match_1wild(const struct cls_rule *fixed, const struct cls_rule *wild,
                        wild->wc.nw_dst_mask, field_idx);
 }
 
+/* Returns true if 'wild1' and 'wild2' match, that is, if their fields
+ * are equal modulo wildcards in 'wild1' or 'wild2'.
+ *
+ * 'field_idx' is the index of the first field to be compared; fields before
+ * 'field_idx' are assumed to match.  Always returns true if 'field_idx' is
+ * CLS_N_FIELDS. */
+static bool
+rules_match_2wild(const struct cls_rule *wild1, const struct cls_rule *wild2,
+                  int field_idx)
+{
+    return rules_match(wild1, wild2, 
+                       wild1->wc.wildcards | wild2->wc.wildcards, 
+                       wild1->wc.nw_src_mask & wild2->wc.nw_src_mask,
+                       wild1->wc.nw_dst_mask & wild2->wc.nw_dst_mask, 
+                       field_idx);
+}
+
 /* Searches 'bucket' for a rule that matches 'target'.  Returns the
  * highest-priority match, if one is found, or a null pointer if there is no
  * match.