[ovs-dev] [PATCH 2/2] ofproto-dpif: Do not count resubmit to later tables against limit.

Ben Pfaff blp at ovn.org
Thu Apr 14 04:45:10 UTC 2016


Open vSwitch must ensure that flow translation takes a finite amount of
time.  Until now it has implemented this by limiting the depth of
recursion.  The initial limit, in version 1.0.1, was no recursion at all,
and then over the years it has increased to 8 levels, then 16, then 32,
and 64 for the last few years.  Now reports are coming in that 64 levels
are inadequate for some OVN setups.  The natural inclination would be to
double the limit again to 128 levels.

This commit attempts another approach.  Instead of increasing the limit,
it reduces the class of resubmits that count against the limit.  Since the
goal for the depth limit is to prevent an infinite amount of work, it's
not necessary to count resubmits that can't lead to infinite work.  In
particular, a resubmit from a table numbered x to a table y > x cannot do
this, because any OpenFlow switch has a finite number of tables.  Because
in fact a resubmit (or goto_table) from one table to a later table is the
most common form of an OpenFlow pipeline, I suspect that this will greatly
alleviate the pressure to increase the depth limit.

Reported-by: Guru Shetty <guru at ovn.org>
Signed-off-by: Ben Pfaff <blp at ovn.org>
---
 lib/ofp-actions.c            | 19 +++++++++++--
 ofproto/ofproto-dpif-xlate.c | 64 +++++++++++++++++++++++++++++++++++---------
 ofproto/ofproto-dpif-xlate.h | 23 +++++++++-------
 ofproto/ofproto-dpif.c       |  5 ++--
 ofproto/ofproto-dpif.h       |  3 ++-
 tests/ofproto-dpif.at        | 41 +++++++++++++++++++++++++++-
 utilities/ovs-ofctl.8.in     | 28 ++++++++++++++++---
 7 files changed, 151 insertions(+), 32 deletions(-)

diff --git a/lib/ofp-actions.c b/lib/ofp-actions.c
index 106ebc8..323bee1 100644
--- a/lib/ofp-actions.c
+++ b/lib/ofp-actions.c
@@ -3738,8 +3738,23 @@ format_FIN_TIMEOUT(const struct ofpact_fin_timeout *a, struct ds *s)
  *
  * Resubmit actions may be used any number of times within a set of actions.
  *
- * Resubmit actions may nest to an implementation-defined depth.  Beyond this
- * implementation-defined depth, further resubmit actions are simply ignored.
+ * Resubmit actions may nest.  To prevent infinite loops and excessive resource
+ * use, the implementation may limit nesting depth and the total number of
+ * resubmits:
+ *
+ *    - Open vSwitch 1.0.1 and earlier did not support recursion.
+ *
+ *    - Open vSwitch 1.0.2 and 1.0.3 limited recursion to 8 levels.
+ *
+ *    - Open vSwitch 1.1 and 1.2 limited recursion to 16 levels.
+ *
+ *    - Open vSwitch 1.2 through 1.8 limited recursion to 32 levels.
+ *
+ *    - Open vSwitch 1.9 through 2.0 limited recursion to 64 levels.
+ *
+ *    - Open vSwitch 2.1 through 2.5 limited recursion to 64 levels and impose
+ *      a total limit of 4,096 resubmits per flow translation (earlier versions
+ *      did not impose any total limit).
  *
  * NXAST_RESUBMIT ignores 'table' and 'pad'.  NXAST_RESUBMIT_TABLE requires
  * 'pad' to be all-bits-zero.
diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c
index 8cf6ea2..47556ed 100644
--- a/ofproto/ofproto-dpif-xlate.c
+++ b/ofproto/ofproto-dpif-xlate.c
@@ -67,14 +67,22 @@ COVERAGE_DEFINE(xlate_actions_too_many_output);
 VLOG_DEFINE_THIS_MODULE(ofproto_dpif_xlate);
 
 /* Maximum depth of flow table recursion (due to resubmit actions) in a
- * flow translation. */
-#define MAX_RESUBMIT_RECURSION 64
-#define MAX_INTERNAL_RESUBMITS 1   /* Max resbmits allowed using rules in
-                                      internal table. */
+ * flow translation.
+ *
+ * The goal of limiting the depth of resubmits is to ensure that flow
+ * translation eventually terminates.  Only resubmits to the same table or an
+ * earlier table count against the maximum depth.  This is because resubmits to
+ * strictly monotonically increasing table IDs will eventually terminate, since
+ * any OpenFlow switch has a finite number of tables.  OpenFlow tables are most
+ * commonly traversed in numerically increasing order, so this limit has little
+ * effect on conventionally designed OpenFlow pipelines.
+ *
+ * Outputs to patch ports and to groups also count against the depth limit. */
+#define MAX_DEPTH 64
 
 /* Maximum number of resubmit actions in a flow translation, whether they are
  * recursive or not. */
-#define MAX_RESUBMITS (MAX_RESUBMIT_RECURSION * MAX_RESUBMIT_RECURSION)
+#define MAX_RESUBMITS (MAX_DEPTH * MAX_DEPTH)
 
 struct xbridge {
     struct hmap_node hmap_node;   /* Node in global 'xbridges' map. */
@@ -195,8 +203,31 @@ struct xlate_ctx {
      * wants actions. */
     struct ofpbuf *odp_actions;
 
-    /* Resubmit statistics, via xlate_table_action(). */
-    int indentation;            /* Current resubmit nesting depth. */
+    /* Statistics maintained by xlate_table_action().
+     *
+     * 'indentation' is the nesting level for resubmits.  It is used to indent
+     * the output of resubmit_hook (e.g. for the "ofproto/trace" feature).
+     *
+     * The other statistics limit the amount of work that a single flow
+     * translation can perform.  The goal of the first of these, 'depth', is
+     * primarily to prevent translation from performing an infinite amount of
+     * work.  It counts the current depth of nested "resubmit"s (and a few
+     * other activities); when a resubmit returns, it decreases.  Resubmits to
+     * tables in strictly monotonically increasing order don't contribute to
+     * 'depth' because they cannot cause a flow translation to take an infinite
+     * amount of time (because the number of tables is finite).  Translation
+     * aborts when 'depth' exceeds MAX_DEPTH.
+     *
+     * 'resubmits', on the other hand, prevents flow translation from
+     * performing an extraordinarily large while still finite amount of work.
+     * It counts the total number of resubmits (and a few other activities)
+     * that have been executed.  Returning from a resubmit does not affect this
+     * counter.  Thus, this limits the amount of work that a particular
+     * translation can perform.  Translation aborts when 'resubmits' exceeds
+     * MAX_RESUBMITS (which is much larger than MAX_DEPTH).
+     */
+    int indentation;            /* Indentation level for resubmit_hook. */
+    int depth;                  /* Current resubmit nesting depth. */
     int resubmits;              /* Total number of resubmits. */
     bool in_group;              /* Currently translating ofgroup, if true. */
     bool in_action_set;         /* Currently translating action_set, if true. */
@@ -2805,7 +2836,8 @@ compose_table_xlate(struct xlate_ctx *ctx, const struct xport *out_dev,
 
     return ofproto_dpif_execute_actions__(xbridge->ofproto, &flow, NULL,
                                           &output.ofpact, sizeof output,
-                                          ctx->indentation, ctx->resubmits, packet);
+                                          ctx->indentation, ctx->depth,
+                                          ctx->resubmits, packet);
 }
 
 static void
@@ -3211,7 +3243,7 @@ compose_output_action(struct xlate_ctx *ctx, ofp_port_t ofp_port,
 }
 
 static void
-xlate_recursively(struct xlate_ctx *ctx, struct rule_dpif *rule)
+xlate_recursively(struct xlate_ctx *ctx, struct rule_dpif *rule, bool deepens)
 {
     struct rule_dpif *old_rule = ctx->rule;
     ovs_be64 old_cookie = ctx->rule_cookie;
@@ -3222,24 +3254,26 @@ xlate_recursively(struct xlate_ctx *ctx, struct rule_dpif *rule)
     }
 
     ctx->resubmits++;
+
     ctx->indentation++;
+    ctx->depth += deepens;
     ctx->rule = rule;
     ctx->rule_cookie = rule_dpif_get_flow_cookie(rule);
     actions = rule_dpif_get_actions(rule);
     do_xlate_actions(actions->ofpacts, actions->ofpacts_len, ctx);
     ctx->rule_cookie = old_cookie;
     ctx->rule = old_rule;
+    ctx->depth -= deepens;
     ctx->indentation--;
 }
 
 static bool
 xlate_resubmit_resource_check(struct xlate_ctx *ctx)
 {
-    if (ctx->indentation >= MAX_RESUBMIT_RECURSION + MAX_INTERNAL_RESUBMITS) {
-        XLATE_REPORT_ERROR(ctx, "resubmit actions recursed over %d times",
-                           MAX_RESUBMIT_RECURSION);
+    if (ctx->depth >= MAX_DEPTH) {
+        XLATE_REPORT_ERROR(ctx, "over max translation depth %d", MAX_DEPTH);
         ctx->error = XLATE_RECURSION_TOO_DEEP;
-    } else if (ctx->resubmits >= MAX_RESUBMITS + MAX_INTERNAL_RESUBMITS) {
+    } else if (ctx->resubmits >= MAX_RESUBMITS) {
         XLATE_REPORT_ERROR(ctx, "over %d resubmit actions", MAX_RESUBMITS);
         ctx->error = XLATE_TOO_MANY_RESUBMITS;
     } else if (ctx->odp_actions->size > UINT16_MAX) {
@@ -3324,7 +3358,9 @@ xlate_group_bucket(struct xlate_ctx *ctx, struct ofputil_bucket *bucket)
 
     ofpacts_execute_action_set(&action_list, &action_set);
     ctx->indentation++;
+    ctx->depth++;
     do_xlate_actions(action_list.data, action_list.size, ctx);
+    ctx->depth--;
     ctx->indentation--;
 
     ofpbuf_uninit(&action_list);
@@ -4825,6 +4861,7 @@ xlate_in_init(struct xlate_in *xin, struct ofproto_dpif *ofproto,
     xin->report_hook = NULL;
     xin->resubmit_stats = NULL;
     xin->indentation = 0;
+    xin->depth = 0;
     xin->resubmits = 0;
     xin->wc = wc;
     xin->odp_actions = odp_actions;
@@ -5090,6 +5127,7 @@ xlate_actions(struct xlate_in *xin, struct xlate_out *xout)
         .odp_actions = xin->odp_actions ? xin->odp_actions : &scratch_actions,
 
         .indentation = xin->indentation,
+        .depth = xin->depth,
         .resubmits = xin->resubmits,
         .in_group = false,
         .in_action_set = false,
diff --git a/ofproto/ofproto-dpif-xlate.h b/ofproto/ofproto-dpif-xlate.h
index 4453072..d1df722 100644
--- a/ofproto/ofproto-dpif-xlate.h
+++ b/ofproto/ofproto-dpif-xlate.h
@@ -105,18 +105,23 @@ struct xlate_in {
      * calling xlate_in_init(). */
     const struct dpif_flow_stats *resubmit_stats;
 
-    /* Indentation and resubmission levels carried over from a pre-existing
-     * translation of a related flow. An example of when this can occur is
-     * the translation of an ARP packet that was generated as the result of
-     * outputting to a tunnel port. In this case, the original flow going to
-     * the tunnel is the related flow. Since the two flows are different, they
-     * should not use the same xlate_ctx structure. However, we still need
-     * limit the maximum recursion across the entire translation.
+    /* Counters carried over from a pre-existing translation of a related flow.
+     * This can occur due to, e.g., the translation of an ARP packet that was
+     * generated as the result of outputting to a tunnel port.  In that case,
+     * the original flow going to the tunnel is the related flow.  Since the
+     * two flows are different, they should not use the same xlate_ctx
+     * structure.  However, we still need limit the maximum recursion across
+     * the entire translation.
      *
      * These fields are normally set to zero, so the client has to set them
-     * manually after calling xlate_in_init(). In that case, they should be
-     * copied from the same-named fields in the related flow's xlate_ctx. */
+     * manually after calling xlate_in_init().  In that case, they should be
+     * copied from the same-named fields in the related flow's xlate_ctx.
+     *
+     * These fields are really implementation details; the client doesn't care
+     * about what they mean.  See the corresponding fields in xlate_ctx for
+     * real documentation. */
     int indentation;
+    int depth;
     int resubmits;
 
     /* If nonnull, flow translation populates this cache with references to all
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index e7e07ae..50f721f 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -3706,7 +3706,7 @@ ofproto_dpif_execute_actions__(struct ofproto_dpif *ofproto,
                                const struct flow *flow,
                                struct rule_dpif *rule,
                                const struct ofpact *ofpacts, size_t ofpacts_len,
-                               int indentation, int resubmits,
+                               int indentation, int depth, int resubmits,
                                struct dp_packet *packet)
 {
     struct dpif_flow_stats stats;
@@ -3732,6 +3732,7 @@ ofproto_dpif_execute_actions__(struct ofproto_dpif *ofproto,
     xin.ofpacts_len = ofpacts_len;
     xin.resubmit_stats = &stats;
     xin.indentation = indentation;
+    xin.depth = depth;
     xin.resubmits = resubmits;
     if (xlate_actions(&xin, &xout) != XLATE_OK) {
         error = EINVAL;
@@ -3772,7 +3773,7 @@ ofproto_dpif_execute_actions(struct ofproto_dpif *ofproto,
                              struct dp_packet *packet)
 {
     return ofproto_dpif_execute_actions__(ofproto, flow, rule, ofpacts,
-                                          ofpacts_len, 0, 0, packet);
+                                          ofpacts_len, 0, 0, 0, packet);
 }
 
 void
diff --git a/ofproto/ofproto-dpif.h b/ofproto/ofproto-dpif.h
index a2363e5..cccf1b7 100644
--- a/ofproto/ofproto-dpif.h
+++ b/ofproto/ofproto-dpif.h
@@ -156,7 +156,8 @@ int ofproto_dpif_execute_actions(struct ofproto_dpif *, const struct flow *,
 int ofproto_dpif_execute_actions__(struct ofproto_dpif *, const struct flow *,
                                    struct rule_dpif *, const struct ofpact *,
                                    size_t ofpacts_len, int indentation,
-                                   int resubmits, struct dp_packet *);
+                                   int depth, int resubmits,
+                                   struct dp_packet *);
 void ofproto_dpif_send_async_msg(struct ofproto_dpif *,
                                  struct ofproto_async_msg *);
 bool ofproto_dpif_wants_packet_in_on_miss(struct ofproto_dpif *);
diff --git a/tests/ofproto-dpif.at b/tests/ofproto-dpif.at
index da29ac2..7c4e6be 100644
--- a/tests/ofproto-dpif.at
+++ b/tests/ofproto-dpif.at
@@ -6960,6 +6960,45 @@ AT_CLEANUP
 
 AT_BANNER([ofproto-dpif - flow translation resource limits])
 
+dnl Resubmits to later tables do not count against the depth limit, so we
+dnl can do 99 of them even though the maximum depth is 64.
+AT_SETUP([ofproto-dpif - forward resubmit])
+OVS_VSWITCHD_START
+(for i in `seq 0 99`; do
+    j=`expr $i + 1`
+    echo "table=$i, actions=resubmit(,$j)"
+ done
+ echo "table=100, actions=local") > flows
+AT_CHECK([ovs-ofctl add-flows br0 flows])
+AT_CHECK([ovs-appctl -vpoll_loop:off ofproto/trace br0 'eth_dst=ff:ff:ff:ff:ff:ff'],
+  [0], [stdout])
+AT_CHECK([tail -1 stdout], [0], [Datapath actions: 100
+])
+OVS_VSWITCHD_STOP
+AT_CLEANUP
+
+dnl Resubmits to the same or an earlier table count against the depth limit,
+dnl so only 64 of them are allowed.
+AT_SETUP([ofproto-dpif - backward resubmit])
+OVS_VSWITCHD_START
+(echo "table=0, actions=resubmit(,66)"
+ for i in `seq 2 66`; do
+    j=`expr $i - 1`
+    echo "table=$i, actions=resubmit(,$j)"
+ done
+ echo "table=1, actions=local") > flows
+AT_CHECK([ovs-ofctl add-flows br0 flows])
+AT_CHECK([ovs-appctl -vpoll_loop:off ofproto/trace br0 'eth_dst=ff:ff:ff:ff:ff:ff'],
+  [0], [stdout])
+AT_CHECK([tail -1 stdout], [0],
+  [Translation failed (Recursion too deep), packet is dropped.
+])
+AT_CHECK([grep -c 'over max translation depth 64' stdout],
+  [0], [1
+])
+OVS_VSWITCHD_STOP(["/resubmit actions recursed/d"])
+AT_CLEANUP
+
 AT_SETUP([ofproto-dpif - infinite resubmit])
 OVS_VSWITCHD_START
 AT_CHECK([ovs-ofctl add-flow br0 actions=resubmit:1,resubmit:2,output:3])
@@ -6968,7 +7007,7 @@ AT_CHECK([ovs-appctl -vpoll_loop:off ofproto/trace br0 'eth_dst=ff:ff:ff:ff:ff:f
 AT_CHECK([tail -1 stdout], [0],
   [Translation failed (Recursion too deep), packet is dropped.
 ])
-AT_CHECK([grep -c 'resubmit actions recursed over 64 times' stdout],
+AT_CHECK([grep -c 'over max translation depth 64' stdout],
   [0], [1
 ])
 OVS_VSWITCHD_STOP(["/resubmit actions recursed/d"])
diff --git a/utilities/ovs-ofctl.8.in b/utilities/ovs-ofctl.8.in
index 6e26132..ff45567 100644
--- a/utilities/ovs-ofctl.8.in
+++ b/utilities/ovs-ofctl.8.in
@@ -1661,10 +1661,30 @@ specified by \fItable\fR) with the \fBin_port\fR field replaced by
 \fIport\fR (if \fIport\fR is specified) and executes the actions
 found, if any, in addition to any other actions in this flow entry.
 .IP
-Recursive \fBresubmit\fR actions are obeyed up to an
-implementation-defined maximum depth.  Open vSwitch 1.0.1 and earlier
-did not support recursion; Open vSwitch before 1.2.90 did not support
-\fItable\fR.
+Recursive \fBresubmit\fR actions are obeyed up to
+implementation-defined limits:
+.RS
+.IP \(bu
+Open vSwitch 1.0.1 and earlier did not support recursion.
+.IP \(bu
+Open vSwitch 1.0.2 and 1.0.3 limited recursion to 8 levels.
+.IP \(bu
+Open vSwitch 1.1 and 1.2 limited recursion to 16 levels.
+.IP \(bu
+Open vSwitch 1.2 through 1.8 limited recursion to 32 levels.
+.IP \(bu
+Open vSwitch 1.9 through 2.0 limited recursion to 64 levels.
+.IP \(bu
+Open vSwitch 2.1 through 2.5 limited recursion to 64 levels and impose
+a total limit of 4,096 resubmits per flow translation (earlier versions
+did not impose any total limit).
+.IP \(bu
+Open vSwitch 2.6 and later imposes the same limits as 2.5, with one
+exception: \fBresubmit\fR from table \fIx\fR to any table \fIy\fR >
+\fIx\fR does not count against the recursion limit.
+.RE
+.IP
+Open vSwitch before 1.2.90 did not support \fItable\fR.
 .
 .IP \fBset_tunnel\fB:\fIid\fR
 .IQ \fBset_tunnel64\fB:\fIid\fR
-- 
2.1.3




More information about the dev mailing list