ofproto-dpif: Remove pointers between rules and facets.

Before this patch, facets maintained a pointer to the first rule
used when translating their actions, and rules maintained a pointer
to those facets.  This made sense before the resubmit actions which
each facet used precisely one rule.  However, today a facet may
require many rules to translate, and therefore it makes no
conceptual sense to designate one as the "owning rule".

Furthermore, as Open vSwitch becomes multithreaded, maintaining a
facet's rule pointer will become more difficult.  One thread will
do the action translation, while another will maintain the facets.
During the hand-off between these threads, it's possible the
"owning rule" will expire leaving us with a stale pointer.

This patch does have a disadvantage,  Pushing a facet's statistics
will become slightly less efficient as it will involve an
additional classifier lookup.  We can revisit this issue once
multithreading is complete, but I suspect there's much lower
hanging fruit to worry about.

Signed-off-by: Ethan Jackson <ethan@nicira.com>

diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 9ba7671..67e6c7a 100644 (file)
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -210,8 +210,7 @@ static void subfacet_uninstall(struct subfacet *);
 struct facet {
     /* Owners. */
     struct hmap_node hmap_node;  /* In owning ofproto's 'facets' hmap. */
-    struct list list_node;       /* In owning rule's 'facets' list. */
-    struct rule_dpif *rule;      /* Owning rule. */
+    struct ofproto_dpif *ofproto;
 
     /* Owned data. */
     struct list subfacets;
@@ -247,6 +246,7 @@ struct facet {
     uint8_t tcp_flags;           /* TCP flags seen for this 'rule'. */
 
     struct xlate_out xout;
+    bool fail_open;              /* Facet matched the fail open rule. */
 
     /* Storage for a single subfacet, to reduce malloc() time and space
      * overhead.  (A facet always has at least one subfacet and in the common
@@ -1544,7 +1544,7 @@ flush(struct ofproto *ofproto_)
     n_batch = 0;
     HMAP_FOR_EACH_SAFE (subfacet, next_subfacet, hmap_node,
                         &ofproto->backer->subfacets) {
-        if (ofproto_dpif_cast(subfacet->facet->rule->up.ofproto) != ofproto) {
+        if (subfacet->facet->ofproto != ofproto) {
             continue;
         }
 
@@ -3280,12 +3280,10 @@ init_flow_miss_execute_op(struct flow_miss *miss, struct ofpbuf *packet,
 /* Helper for handle_flow_miss_without_facet() and
  * handle_flow_miss_with_facet(). */
 static void
-handle_flow_miss_common(struct rule_dpif *rule,
-                        struct ofpbuf *packet, const struct flow *flow)
+handle_flow_miss_common(struct ofproto_dpif *ofproto, struct ofpbuf *packet,
+                        const struct flow *flow, bool fail_open)
 {
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
-
-    if (rule->up.cr.priority == FAIL_OPEN_PRIORITY) {
+    if (fail_open) {
         /*
          * Extra-special case for fail-open mode.
          *
@@ -3352,7 +3350,8 @@ handle_flow_miss_without_facet(struct rule_dpif *rule, struct xlate_out *xout,
 
         COVERAGE_INC(facet_suppress);
 
-        handle_flow_miss_common(rule, packet, &miss->flow);
+        handle_flow_miss_common(miss->ofproto, packet, &miss->flow,
+                                rule->up.cr.priority == FAIL_OPEN_PRIORITY);
 
         if (xout->slow) {
             struct xlate_in xin;
@@ -3392,7 +3391,6 @@ handle_flow_miss_with_facet(struct flow_miss *miss, struct facet *facet,
                             long long int now, struct dpif_flow_stats *stats,
                             struct flow_miss_op *ops, size_t *n_ops)
 {
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
     enum subfacet_path want_path;
     struct subfacet *subfacet;
     struct ofpbuf *packet;
@@ -3406,12 +3404,15 @@ handle_flow_miss_with_facet(struct flow_miss *miss, struct facet *facet,
     LIST_FOR_EACH (packet, list_node, &miss->packets) {
         struct flow_miss_op *op = &ops[*n_ops];
 
-        handle_flow_miss_common(facet->rule, packet, &miss->flow);
+        handle_flow_miss_common(miss->ofproto, packet, &miss->flow,
+                                facet->fail_open);
 
         if (want_path != SF_FAST_PATH) {
+            struct rule_dpif *rule;
             struct xlate_in xin;
 
-            xlate_in_init(&xin, ofproto, &miss->flow, facet->rule, 0, packet);
+            rule = rule_dpif_lookup(facet->ofproto, &facet->flow, NULL);
+            xlate_in_init(&xin, facet->ofproto, &miss->flow, rule, 0, packet);
             xlate_actions_for_side_effects(&xin);
         }
 
@@ -3450,7 +3451,7 @@ handle_flow_miss_with_facet(struct flow_miss *miss, struct facet *facet,
             put->actions = facet->xout.odp_actions.data;
             put->actions_len = facet->xout.odp_actions.size;
         } else {
-            compose_slow_path(ofproto, &miss->flow, facet->xout.slow,
+            compose_slow_path(facet->ofproto, &miss->flow, facet->xout.slow,
                               op->slow_stub, sizeof op->slow_stub,
                               &put->actions, &put->actions_len);
         }
@@ -4037,7 +4038,6 @@ update_subfacet_stats(struct subfacet *subfacet,
                       const struct dpif_flow_stats *stats)
 {
     struct facet *facet = subfacet->facet;
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
     struct dpif_flow_stats diff;
 
     diff.tcp_flags = stats->tcp_flags;
@@ -4057,7 +4057,7 @@ update_subfacet_stats(struct subfacet *subfacet,
         diff.n_bytes = 0;
     }
 
-    ofproto->n_hit += diff.n_packets;
+    facet->ofproto->n_hit += diff.n_packets;
     subfacet->dp_packet_count = stats->n_packets;
     subfacet->dp_byte_count = stats->n_bytes;
     subfacet_update_stats(subfacet, &diff);
@@ -4275,7 +4275,6 @@ expire_subfacets(struct dpif_backer *backer, int dp_max_idle)
 static void
 rule_expire(struct rule_dpif *rule)
 {
-    struct facet *facet, *next_facet;
     long long int now;
     uint8_t reason;
 
@@ -4298,12 +4297,6 @@ rule_expire(struct rule_dpif *rule)
 
     COVERAGE_INC(ofproto_dpif_expired);
 
-    /* Update stats.  (This is a no-op if the rule expired due to an idle
-     * timeout, because that only happens when the rule has no facets left.) */
-    LIST_FOR_EACH_SAFE (facet, next_facet, list_node, &rule->facets) {
-        facet_remove(facet);
-    }
-
     /* Get rid of the rule. */
     ofproto_rule_expire(&rule->up, reason);
 }
@@ -4330,15 +4323,14 @@ facet_create(const struct flow_miss *miss, struct rule_dpif *rule,
     struct match match;
 
     facet = xzalloc(sizeof *facet);
+    facet->ofproto = miss->ofproto;
     facet->packet_count = facet->prev_packet_count = stats->n_packets;
     facet->byte_count = facet->prev_byte_count = stats->n_bytes;
     facet->tcp_flags = stats->tcp_flags;
     facet->used = stats->used;
     facet->flow = miss->flow;
     facet->learn_rl = time_msec() + 500;
-    facet->rule = rule;
 
-    list_push_back(&facet->rule->facets, &facet->list_node);
     list_init(&facet->subfacets);
     netflow_flow_init(&facet->nf_flow);
     netflow_flow_update_time(ofproto->netflow, &facet->nf_flow, facet->used);
@@ -4350,6 +4342,7 @@ facet_create(const struct flow_miss *miss, struct rule_dpif *rule,
     classifier_insert(&ofproto->facets, &facet->cr);
 
     facet->nf_flow.output_iface = facet->xout.nf_output_iface;
+    facet->fail_open = rule->up.cr.priority == FAIL_OPEN_PRIORITY;
 
     return facet;
 }
@@ -4393,7 +4386,6 @@ execute_odp_actions(struct ofproto_dpif *ofproto, const struct flow *flow,
 static void
 facet_remove(struct facet *facet)
 {
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
     struct subfacet *subfacet, *next_subfacet;
 
     ovs_assert(!list_is_empty(&facet->subfacets));
@@ -4415,9 +4407,8 @@ facet_remove(struct facet *facet)
                         &facet->subfacets) {
         subfacet_destroy__(subfacet);
     }
-    classifier_remove(&ofproto->facets, &facet->cr);
+    classifier_remove(&facet->ofproto->facets, &facet->cr);
     cls_rule_destroy(&facet->cr);
-    list_remove(&facet->list_node);
     facet_free(facet);
 }
 
@@ -4447,13 +4438,12 @@ facet_learn(struct facet *facet)
 static void
 facet_account(struct facet *facet)
 {
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
     const struct nlattr *a;
     unsigned int left;
     ovs_be16 vlan_tci;
     uint64_t n_bytes;
 
-    if (!facet->xout.has_normal || !ofproto->has_bonded_bundles) {
+    if (!facet->xout.has_normal || !facet->ofproto->has_bonded_bundles) {
         return;
     }
     n_bytes = facet->byte_count - facet->accounted_bytes;
@@ -4474,7 +4464,7 @@ facet_account(struct facet *facet)
 
         switch (nl_attr_type(a)) {
         case OVS_ACTION_ATTR_OUTPUT:
-            port = get_odp_port(ofproto, nl_attr_get_odp_port(a));
+            port = get_odp_port(facet->ofproto, nl_attr_get_odp_port(a));
             if (port && port->bundle && port->bundle->bond) {
                 bond_account(port->bundle->bond, &facet->flow,
                              vlan_tci_to_vid(vlan_tci), n_bytes);
@@ -4500,9 +4490,11 @@ static bool
 facet_is_controller_flow(struct facet *facet)
 {
     if (facet) {
-        const struct rule *rule = &facet->rule->up;
-        const struct ofpact *ofpacts = rule->ofpacts;
-        size_t ofpacts_len = rule->ofpacts_len;
+        struct ofproto_dpif *ofproto = facet->ofproto;
+        const struct rule_dpif *rule = rule_dpif_lookup(ofproto, &facet->flow,
+                                                        NULL);
+        const struct ofpact *ofpacts = rule->up.ofpacts;
+        size_t ofpacts_len = rule->up.ofpacts_len;
 
         if (ofpacts_len > 0 &&
             ofpacts->type == OFPACT_CONTROLLER &&
@@ -4520,7 +4512,7 @@ facet_is_controller_flow(struct facet *facet)
 static void
 facet_flush_stats(struct facet *facet)
 {
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
+    struct ofproto_dpif *ofproto = facet->ofproto;
     struct subfacet *subfacet;
 
     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
@@ -4589,41 +4581,21 @@ facet_check_consistency(struct facet *facet)
 {
     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 15);
 
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
-
     struct xlate_out xout;
     struct xlate_in xin;
 
     struct rule_dpif *rule;
-    bool ok;
-
-    /* Check the rule for consistency. */
-    rule = rule_dpif_lookup(ofproto, &facet->flow, NULL);
-    if (rule != facet->rule) {
-        if (!VLOG_DROP_WARN(&rl)) {
-            struct ds s = DS_EMPTY_INITIALIZER;
-
-            flow_format(&s, &facet->flow);
-            ds_put_format(&s, ": facet associated with wrong rule (was "
-                          "table=%"PRIu8",", facet->rule->up.table_id);
-            cls_rule_format(&facet->rule->up.cr, &s);
-            ds_put_format(&s, ") (should have been table=%"PRIu8",",
-                          rule->up.table_id);
-            cls_rule_format(&rule->up.cr, &s);
-            ds_put_char(&s, ')');
-
-            VLOG_WARN("%s", ds_cstr(&s));
-            ds_destroy(&s);
-        }
-        return false;
-    }
+    bool ok, fail_open;
 
     /* Check the datapath actions for consistency. */
-    xlate_in_init(&xin, ofproto, &facet->flow, rule, 0, NULL);
+    rule = rule_dpif_lookup(facet->ofproto, &facet->flow, NULL);
+    xlate_in_init(&xin, facet->ofproto, &facet->flow, rule, 0, NULL);
     xlate_actions(&xin, &xout);
 
+    fail_open = rule->up.cr.priority == FAIL_OPEN_PRIORITY;
     ok = ofpbuf_equal(&facet->xout.odp_actions, &xout.odp_actions)
-        && facet->xout.slow == xout.slow;
+        && facet->xout.slow == xout.slow
+        && facet->fail_open == fail_open;
     if (!ok && !VLOG_DROP_WARN(&rl)) {
         struct ds s = DS_EMPTY_INITIALIZER;
 
@@ -4644,7 +4616,10 @@ facet_check_consistency(struct facet *facet)
             ds_put_format(&s, " slow path incorrect. should be %d", xout.slow);
         }
 
-        VLOG_WARN("%s", ds_cstr(&s));
+        if (facet->fail_open != fail_open) {
+            ds_put_format(&s, " fail open incorrect. should be %s",
+                          fail_open ? "true" : "false");
+        }
         ds_destroy(&s);
     }
     xlate_out_uninit(&xout);
@@ -4667,7 +4642,7 @@ facet_check_consistency(struct facet *facet)
 static bool
 facet_revalidate(struct facet *facet)
 {
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
+    struct ofproto_dpif *ofproto = facet->ofproto;
     struct rule_dpif *new_rule;
     struct subfacet *subfacet;
     struct flow_wildcards wc;
@@ -4748,15 +4723,8 @@ facet_revalidate(struct facet *facet)
     facet->xout.nf_output_iface = xout.nf_output_iface;
     facet->xout.mirrors = xout.mirrors;
     facet->nf_flow.output_iface = facet->xout.nf_output_iface;
-
-    if (facet->rule != new_rule) {
-        COVERAGE_INC(facet_changed_rule);
-        list_remove(&facet->list_node);
-        list_push_back(&new_rule->facets, &facet->list_node);
-        facet->rule = new_rule;
-        facet->used = new_rule->up.created;
-        facet->prev_used = facet->used;
-    }
+    facet->used = MAX(facet->used, new_rule->up.created);
+    facet->fail_open = new_rule->up.cr.priority == FAIL_OPEN_PRIORITY;
 
     xlate_out_uninit(&xout);
     return true;
@@ -4787,10 +4755,9 @@ facet_push_stats(struct facet *facet, bool may_learn)
     stats.tcp_flags = facet->tcp_flags;
 
     if (may_learn || stats.n_packets || facet->used > facet->prev_used) {
-        struct ofproto_dpif *ofproto =
-            ofproto_dpif_cast(facet->rule->up.ofproto);
-
+        struct ofproto_dpif *ofproto = facet->ofproto;
         struct ofport_dpif *in_port;
+        struct rule_dpif *rule;
         struct xlate_in xin;
 
         facet->prev_packet_count = facet->packet_count;
@@ -4802,15 +4769,16 @@ facet_push_stats(struct facet *facet, bool may_learn)
             netdev_vport_inc_rx(in_port->up.netdev, &stats);
         }
 
-        rule_credit_stats(facet->rule, &stats);
+        rule = rule_dpif_lookup(ofproto, &facet->flow, NULL);
+        rule_credit_stats(rule, &stats);
         netflow_flow_update_time(ofproto->netflow, &facet->nf_flow,
                                  facet->used);
         netflow_flow_update_flags(&facet->nf_flow, facet->tcp_flags);
         mirror_update_stats(ofproto->mbridge, facet->xout.mirrors,
                             stats.n_packets, stats.n_bytes);
 
-        xlate_in_init(&xin, ofproto, &facet->flow, facet->rule,
-                      stats.tcp_flags, NULL);
+        xlate_in_init(&xin, ofproto, &facet->flow, rule, stats.tcp_flags,
+                      NULL);
         xin.resubmit_stats = &stats;
         xin.may_learn = may_learn;
         xlate_actions_for_side_effects(&xin);
@@ -4933,7 +4901,7 @@ static void
 subfacet_destroy__(struct subfacet *subfacet)
 {
     struct facet *facet = subfacet->facet;
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
+    struct ofproto_dpif *ofproto = facet->ofproto;
 
     /* Update ofproto stats before uninstall the subfacet. */
     ofproto->backer->subfacet_del_count++;
@@ -4999,7 +4967,6 @@ subfacet_install(struct subfacet *subfacet, const struct ofpbuf *odp_actions,
                  struct dpif_flow_stats *stats)
 {
     struct facet *facet = subfacet->facet;
-    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
     enum subfacet_path path = facet->xout.slow ? SF_SLOW_PATH : SF_FAST_PATH;
     const struct nlattr *actions = odp_actions->data;
     size_t actions_len = odp_actions->size;
@@ -5016,7 +4983,7 @@ subfacet_install(struct subfacet *subfacet, const struct ofpbuf *odp_actions,
     }
 
     if (path == SF_SLOW_PATH) {
-        compose_slow_path(ofproto, &facet->flow, facet->xout.slow,
+        compose_slow_path(facet->ofproto, &facet->flow, facet->xout.slow,
                           slow_path_stub, sizeof slow_path_stub,
                           &actions, &actions_len);
     }
@@ -5048,8 +5015,7 @@ static void
 subfacet_uninstall(struct subfacet *subfacet)
 {
     if (subfacet->path != SF_NOT_INSTALLED) {
-        struct rule_dpif *rule = subfacet->facet->rule;
-        struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
+        struct ofproto_dpif *ofproto = subfacet->facet->ofproto;
         struct dpif_flow_stats stats;
         int error;
 
@@ -5220,28 +5186,8 @@ rule_construct(struct rule *rule_)
     rule->packet_count = 0;
     rule->byte_count = 0;
 
-    victim = rule_dpif_cast(ofoperation_get_victim(rule->up.pending));
-    if (victim && !list_is_empty(&victim->facets)) {
-        struct facet *facet;
-
-        rule->facets = victim->facets;
-        list_moved(&rule->facets);
-        LIST_FOR_EACH (facet, list_node, &rule->facets) {
-            /* XXX: We're only clearing our local counters here.  It's possible
-             * that quite a few packets are unaccounted for in the datapath
-             * statistics.  These will be accounted to the new rule instead of
-             * cleared as required.  This could be fixed by clearing out the
-             * datapath statistics for this facet, but currently it doesn't
-             * seem worth it. */
-            facet_reset_counters(facet);
-            facet->rule = rule;
-        }
-    } else {
-        /* Must avoid list_moved() in this case. */
-        list_init(&rule->facets);
-    }
-
     table_id = rule->up.table_id;
+    victim = rule_dpif_cast(ofoperation_get_victim(rule->up.pending));
     if (victim) {
         rule->tag = victim->tag;
     } else if (table_id == 0) {
@@ -5259,16 +5205,9 @@ rule_construct(struct rule *rule_)
 }
 
 static void
-rule_destruct(struct rule *rule_)
+rule_destruct(struct rule *rule)
 {
-    struct rule_dpif *rule = rule_dpif_cast(rule_);
-    struct facet *facet, *next_facet;
-
-    LIST_FOR_EACH_SAFE (facet, next_facet, list_node, &rule->facets) {
-        facet_revalidate(facet);
-    }
-
-    complete_operation(rule);
+    complete_operation(rule_dpif_cast(rule));
 }
 
 static void
@@ -6388,7 +6327,7 @@ ofproto_unixctl_dpif_dump_flows(struct unixctl_conn *conn,
     HMAP_FOR_EACH (subfacet, hmap_node, &ofproto->backer->subfacets) {
         struct facet *facet = subfacet->facet;
 
-        if (ofproto_dpif_cast(facet->rule->up.ofproto) != ofproto) {
+        if (facet->ofproto != ofproto) {
             continue;
         }
 

diff --git a/ofproto/ofproto-dpif.h b/ofproto/ofproto-dpif.h
index 3f0fd6e..b220423 100644 (file)
--- a/ofproto/ofproto-dpif.h
+++ b/ofproto/ofproto-dpif.h
@@ -47,8 +47,6 @@ struct rule_dpif {
     uint64_t byte_count;         /* Number of bytes received. */
 
     tag_type tag;                /* Caches rule_calculate_tag() result. */
-
-    struct list facets;          /* List of "struct facet"s. */
 };
 
 static inline struct rule_dpif *rule_dpif_cast(const struct rule *rule)