[ovs-dev] lib: Build action_set in one scan of action_list

Message ID CAJ+yUhsEOc1-V7OncE=iLchd1L40HqwW1bitU1zySHo1a2D7jA@mail.gmail.com
State Accepted
Headers show
Series
  • [ovs-dev] lib: Build action_set in one scan of action_list
Related show

Commit Message

Kyle Simpson June 6, 2018, 2:17 p.m.
The previous implementation scans the action set of each WRITE_ACTIONS
command 13--17 times when moving the actions over. This change builds
up the list as a single scan, which should be more efficient.

Signed-off-by: Kyle Simpson <kyleandrew.simpson@gmail.com>
---
 lib/ofp-actions.c | 110 +++++++++++++++++++++++++++-------------------
 1 file changed, 65 insertions(+), 45 deletions(-)

Comments

Ben Pfaff June 15, 2018, 6:09 p.m. | #1
On Wed, Jun 06, 2018 at 03:17:59PM +0100, Kyle Simpson wrote:
> The previous implementation scans the action set of each WRITE_ACTIONS
> command 13--17 times when moving the actions over. This change builds
> up the list as a single scan, which should be more efficient.
> 
> Signed-off-by: Kyle Simpson <kyleandrew.simpson@gmail.com>

Hmm, this is interesting.

I observe that "set_queue" can be treated like a "set or move" action
since its ordering with those actions doesn't actually matter.

With that, and a few other changes, I get the following, which is pretty
simple and consolidates logic between ofpact_is_set_or_move_action() and
ofpact_is_allowed_in_actions_set(), which is nice, although it does add
preprocessor tricks.  I like how it actually deletes more lines (161)
than it adds (106).

What do you think of this version?

--8<--------------------------cut here-------------------------->8--

From: Kyle Simpson <kyleandrew.simpson@gmail.com>
Date: Wed, 6 Jun 2018 15:17:59 +0100
Subject: [PATCH] lib: Build action_set in one scan of action_list

The previous implementation scans the action set of each WRITE_ACTIONS
command 13--17 times when moving the actions over. This change builds
up the list as a single scan, which should be more efficient.

Signed-off-by: Kyle Simpson <kyleandrew.simpson@gmail.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>
---
 lib/ofp-actions.c | 267 ++++++++++++++++++++++--------------------------------
 1 file changed, 106 insertions(+), 161 deletions(-)

diff --git a/lib/ofp-actions.c b/lib/ofp-actions.c
index 87797bc9a4fd..e91e0b252390 100644
--- a/lib/ofp-actions.c
+++ b/lib/ofp-actions.c
@@ -6956,17 +6956,77 @@ ofpacts_pull_openflow_actions(struct ofpbuf *openflow,
                                            ofpacts_tlv_bitmap);
 }
 
-/* OpenFlow 1.1 actions. */
+/* OpenFlow 1.1 action sets. */
 
+/* Append ofpact 'a' onto the tail of 'out' */
+static void
+ofpact_copy(struct ofpbuf *out, const struct ofpact *a)
+{
+    ofpbuf_put(out, a, OFPACT_ALIGN(a->len));
+}
 
-/* True if an action sets the value of a field
- * in a way that is compatibile with the action set.
- * The field can be set via either a set or a move action.
- * False otherwise. */
-static bool
-ofpact_is_set_or_move_action(const struct ofpact *a)
+/* The order in which actions in an action set get executed.  This is only for
+ * the actions where only the last instance added is used. */
+#define ACTION_SET_ORDER                        \
+    SLOT(OFPACT_STRIP_VLAN)                     \
+    SLOT(OFPACT_POP_MPLS)                       \
+    SLOT(OFPACT_DECAP)                          \
+    SLOT(OFPACT_ENCAP)                          \
+    SLOT(OFPACT_PUSH_MPLS)                      \
+    SLOT(OFPACT_PUSH_VLAN)                      \
+    SLOT(OFPACT_DEC_TTL)                        \
+    SLOT(OFPACT_DEC_MPLS_TTL)                   \
+    SLOT(OFPACT_DEC_NSH_TTL)
+
+/* Priority for "final actions" in an action set.  An action set only gets
+ * executed at all if at least one of these actions is present.  If more than
+ * one is present, then only the one later in this list is executed (and if
+ * more than one of a given type, the one later in the action set). */
+#define ACTION_SET_FINAL_PRIORITY               \
+    FINAL(OFPACT_CT)                            \
+    FINAL(OFPACT_CT_CLEAR)                      \
+    FINAL(OFPACT_RESUBMIT)                      \
+    FINAL(OFPACT_OUTPUT)                        \
+    FINAL(OFPACT_GROUP)
+
+enum action_set_class {
+    /* Actions that individually can usefully appear only once in an action
+     * set.  If they do appear more than once, then only the last instance is
+     * honored. */
+#define SLOT(OFPACT) ACTION_SLOT_##OFPACT,
+    ACTION_SET_ORDER
+#undef SLOT
+
+    /* Final actions. */
+#define FINAL(OFPACT) ACTION_SLOT_##OFPACT,
+    ACTION_SET_FINAL_PRIORITY
+#undef FINAL
+
+    /* Actions that can appear in an action set more than once and are executed
+     * in order. */
+    ACTION_SLOT_SET_OR_MOVE,
+
+    /* Actions that shouldn't appear in the action set at all. */
+    ACTION_SLOT_INVALID
+};
+
+/* Count the action set slots. */
+#define SLOT(OFPACT) +1
+enum { N_ACTION_SLOTS = ACTION_SET_ORDER };
+#undef SLOT
+
+static enum action_set_class
+action_set_classify(const struct ofpact *a)
 {
     switch (a->type) {
+#define SLOT(OFPACT) case OFPACT: return ACTION_SLOT_##OFPACT;
+        ACTION_SET_ORDER
+#undef SLOT
+
+#define FINAL(OFPACT) case OFPACT: return ACTION_SLOT_##OFPACT;
+        ACTION_SET_FINAL_PRIORITY
+#undef FINAL
+
     case OFPACT_SET_FIELD:
     case OFPACT_REG_MOVE:
     case OFPACT_SET_ETH_DST:
@@ -6985,47 +7045,35 @@ ofpact_is_set_or_move_action(const struct ofpact *a)
     case OFPACT_SET_TUNNEL:
     case OFPACT_SET_VLAN_PCP:
     case OFPACT_SET_VLAN_VID:
-        return true;
+        return ACTION_SLOT_SET_OR_MOVE;
+
     case OFPACT_BUNDLE:
     case OFPACT_CLEAR_ACTIONS:
-    case OFPACT_CT:
-    case OFPACT_CT_CLEAR:
     case OFPACT_CLONE:
     case OFPACT_NAT:
     case OFPACT_CONTROLLER:
-    case OFPACT_DEC_MPLS_TTL:
-    case OFPACT_DEC_TTL:
     case OFPACT_ENQUEUE:
     case OFPACT_EXIT:
     case OFPACT_UNROLL_XLATE:
     case OFPACT_FIN_TIMEOUT:
     case OFPACT_GOTO_TABLE:
-    case OFPACT_GROUP:
     case OFPACT_LEARN:
     case OFPACT_CONJUNCTION:
     case OFPACT_METER:
     case OFPACT_MULTIPATH:
     case OFPACT_NOTE:
-    case OFPACT_OUTPUT:
     case OFPACT_OUTPUT_REG:
     case OFPACT_OUTPUT_TRUNC:
-    case OFPACT_POP_MPLS:
     case OFPACT_POP_QUEUE:
-    case OFPACT_PUSH_MPLS:
-    case OFPACT_PUSH_VLAN:
-    case OFPACT_RESUBMIT:
     case OFPACT_SAMPLE:
     case OFPACT_STACK_POP:
     case OFPACT_STACK_PUSH:
-    case OFPACT_STRIP_VLAN:
     case OFPACT_WRITE_ACTIONS:
     case OFPACT_WRITE_METADATA:
     case OFPACT_DEBUG_RECIRC:
     case OFPACT_DEBUG_SLOW:
-    case OFPACT_ENCAP:
-    case OFPACT_DECAP:
-    case OFPACT_DEC_NSH_TTL:
-        return false;
+        return ACTION_SLOT_INVALID;
+
     default:
         OVS_NOT_REACHED();
     }
@@ -7036,119 +7084,7 @@ ofpact_is_set_or_move_action(const struct ofpact *a)
 static bool
 ofpact_is_allowed_in_actions_set(const struct ofpact *a)
 {
-    switch (a->type) {
-    case OFPACT_DEC_MPLS_TTL:
-    case OFPACT_DEC_TTL:
-    case OFPACT_GROUP:
-    case OFPACT_OUTPUT:
-    case OFPACT_OUTPUT_TRUNC:
-    case OFPACT_POP_MPLS:
-    case OFPACT_PUSH_MPLS:
-    case OFPACT_PUSH_VLAN:
-    case OFPACT_REG_MOVE:
-    case OFPACT_SET_FIELD:
-    case OFPACT_SET_ETH_DST:
-    case OFPACT_SET_ETH_SRC:
-    case OFPACT_SET_IP_DSCP:
-    case OFPACT_SET_IP_ECN:
-    case OFPACT_SET_IP_TTL:
-    case OFPACT_SET_IPV4_DST:
-    case OFPACT_SET_IPV4_SRC:
-    case OFPACT_SET_L4_DST_PORT:
-    case OFPACT_SET_L4_SRC_PORT:
-    case OFPACT_SET_MPLS_LABEL:
-    case OFPACT_SET_MPLS_TC:
-    case OFPACT_SET_MPLS_TTL:
-    case OFPACT_SET_QUEUE:
-    case OFPACT_SET_TUNNEL:
-    case OFPACT_SET_VLAN_PCP:
-    case OFPACT_SET_VLAN_VID:
-    case OFPACT_STRIP_VLAN:
-    case OFPACT_ENCAP:
-    case OFPACT_DECAP:
-    case OFPACT_DEC_NSH_TTL:
-        return true;
-
-    /* In general these actions are excluded because they are not part of
-     * the OpenFlow specification nor map to actions that are defined in
-     * the specification.  Thus the order in which they should be applied
-     * in the action set is undefined. */
-    case OFPACT_BUNDLE:
-    case OFPACT_CLONE:
-    case OFPACT_CONTROLLER:
-    case OFPACT_CT:
-    case OFPACT_CT_CLEAR:
-    case OFPACT_NAT:
-    case OFPACT_ENQUEUE:
-    case OFPACT_EXIT:
-    case OFPACT_UNROLL_XLATE:
-    case OFPACT_FIN_TIMEOUT:
-    case OFPACT_LEARN:
-    case OFPACT_CONJUNCTION:
-    case OFPACT_MULTIPATH:
-    case OFPACT_NOTE:
-    case OFPACT_OUTPUT_REG:
-    case OFPACT_POP_QUEUE:
-    case OFPACT_RESUBMIT:
-    case OFPACT_SAMPLE:
-    case OFPACT_STACK_POP:
-    case OFPACT_STACK_PUSH:
-    case OFPACT_DEBUG_RECIRC:
-    case OFPACT_DEBUG_SLOW:
-
-    /* The action set may only include actions and thus
-     * may not include any instructions */
-    case OFPACT_CLEAR_ACTIONS:
-    case OFPACT_GOTO_TABLE:
-    case OFPACT_METER:
-    case OFPACT_WRITE_ACTIONS:
-    case OFPACT_WRITE_METADATA:
-        return false;
-    default:
-        OVS_NOT_REACHED();
-    }
-}
-
-/* Append ofpact 'a' onto the tail of 'out' */
-static void
-ofpact_copy(struct ofpbuf *out, const struct ofpact *a)
-{
-    ofpbuf_put(out, a, OFPACT_ALIGN(a->len));
-}
-
-/* Copies the last ofpact whose type is 'filter' from 'in' to 'out'. */
-static bool
-ofpacts_copy_last(struct ofpbuf *out, const struct ofpbuf *in,
-                  enum ofpact_type filter)
-{
-    const struct ofpact *target;
-    const struct ofpact *a;
-
-    target = NULL;
-    OFPACT_FOR_EACH (a, in->data, in->size) {
-        if (a->type == filter) {
-            target = a;
-        }
-    }
-    if (target) {
-        ofpact_copy(out, target);
-    }
-    return target != NULL;
-}
-
-/* Append all ofpacts, for which 'filter' returns true, from 'in' to 'out'.
- * The order of appended ofpacts is preserved between 'in' and 'out' */
-static void
-ofpacts_copy_all(struct ofpbuf *out, const struct ofpbuf *in,
-                 bool (*filter)(const struct ofpact *))
-{
-    const struct ofpact *a;
-
-    OFPACT_FOR_EACH (a, in->data, in->size) {
-        if (filter(a)) {
-            ofpact_copy(out, a);
-        }
-    }
+    return action_set_classify(a) != ACTION_SLOT_INVALID;
 }
 
 /* Reads 'action_set', which contains ofpacts accumulated by
@@ -7172,32 +7108,41 @@ void
 ofpacts_execute_action_set(struct ofpbuf *action_list,
                            const struct ofpbuf *action_set)
 {
-    /* The OpenFlow spec "Action Set" section specifies this order. */
-    ofpacts_copy_last(action_list, action_set, OFPACT_STRIP_VLAN);
-    ofpacts_copy_last(action_list, action_set, OFPACT_POP_MPLS);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DECAP);
-    ofpacts_copy_last(action_list, action_set, OFPACT_ENCAP);
-    ofpacts_copy_last(action_list, action_set, OFPACT_PUSH_MPLS);
-    ofpacts_copy_last(action_list, action_set, OFPACT_PUSH_VLAN);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DEC_TTL);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DEC_MPLS_TTL);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DEC_NSH_TTL);
-    ofpacts_copy_all(action_list, action_set, ofpact_is_set_or_move_action);
-    ofpacts_copy_last(action_list, action_set, OFPACT_SET_QUEUE);
-
-    /* If both OFPACT_GROUP and OFPACT_OUTPUT are present, OpenFlow says that
-     * we should execute only OFPACT_GROUP.
-     *
-     * If neither OFPACT_GROUP nor OFPACT_OUTPUT is present, then we can drop
-     * all the actions because there's no point in modifying a packet that will
-     * not be sent anywhere. */
-    if (!ofpacts_copy_last(action_list, action_set, OFPACT_GROUP) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_OUTPUT) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_RESUBMIT) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_CT_CLEAR) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_CT)) {
-        ofpbuf_clear(action_list);
+    const struct ofpact *slots[N_ACTION_SLOTS] = {NULL, };
+
+    struct ofpbuf set_or_move;
+    ofpbuf_init(&set_or_move, 0);
+
+    const struct ofpact *final_action = NULL;
+    enum action_set_class final_class = 0;
+
+    const struct ofpact *cursor;
+    OFPACT_FOR_EACH (cursor, action_set->data, action_set->size) {
+        int class = action_set_classify(cursor);
+        if (class < N_ACTION_SLOTS) {
+            slots[class] = cursor;
+        } else if (class < ACTION_SLOT_SET_OR_MOVE) {
+            if (class >= final_class) {
+                final_action = cursor;
+                final_class = class;
+            }
+        } else if (class == ACTION_SLOT_SET_OR_MOVE) {
+            ofpact_copy(&set_or_move, cursor);
+        } else {
+            ovs_assert(class == ACTION_SLOT_INVALID);
+        }
+    }
+
+    if (final_action) {
+        for (int i = 0; i < N_ACTION_SLOTS; i++) {
+            if (slots[i]) {
+                ofpact_copy(action_list, slots[i]);
+            }
+        }
+        ofpbuf_put(action_list, set_or_move.data, set_or_move.size);
+        ofpact_copy(action_list, final_action);
     }
+    ofpbuf_uninit(&set_or_move);
 }
Kyle Simpson June 16, 2018, 1:24 a.m. | #2
> I like how it actually deletes more lines (161)
> than it adds (106).

A good result. :)

> What do you think of this version?

Looks good to me, I'm not a macro person so it was strange at first glance.
It makes a lot of sense though, and it's certainly more extensible
than my mechanism and what we had before.
The unified list and classification make the action set logic far
simpler, too. I like it.

-- Kyle
web: https://mcfelix.me

Patch

diff --git a/lib/ofp-actions.c b/lib/ofp-actions.c
index 87797bc9a..6400aabf4 100644
--- a/lib/ofp-actions.c
+++ b/lib/ofp-actions.c
@@ -7116,40 +7116,43 @@  ofpact_copy(struct ofpbuf *out, const struct ofpact *a)
     ofpbuf_put(out, a, OFPACT_ALIGN(a->len));
 }

-/* Copies the last ofpact whose type is 'filter' from 'in' to 'out'. */
-static bool
-ofpacts_copy_last(struct ofpbuf *out, const struct ofpbuf *in,
-                  enum ofpact_type filter)
-{
-    const struct ofpact *target;
-    const struct ofpact *a;
-
-    target = NULL;
-    OFPACT_FOR_EACH (a, in->data, in->size) {
-        if (a->type == filter) {
-            target = a;
-        }
-    }
-    if (target) {
-        ofpact_copy(out, target);
-    }
-    return target != NULL;
-}
-
-/* Append all ofpacts, for which 'filter' returns true, from 'in' to 'out'.
+/* Append all ofpacts, from 'in' to 'out'.
  * The order of appended ofpacts is preserved between 'in' and 'out' */
 static void
-ofpacts_copy_all(struct ofpbuf *out, const struct ofpbuf *in,
-                 bool (*filter)(const struct ofpact *))
+ofpacts_copy_all(struct ofpbuf *out, const struct ofpbuf *in)
 {
     const struct ofpact *a;

     OFPACT_FOR_EACH (a, in->data, in->size) {
-        if (filter(a)) {
-            ofpact_copy(out, a);
-        }
-    }
-}
+        ofpact_copy(out, a);
+    }
+}
+
+#define ACTION_SET_MISC_POSITION 10
+#define ACTION_SET_COUNT ACTION_SET_MISC_POSITION + 6
+
+/* 1-indexed lookup table for constructing the action set.
+ * The OpenFlow spec "Action Set" section specifies this order.
+ * 0 (implicit from partial initialisation) means ignore, unless
+ * action is a "set_or_move" (and should be copied to another list) */
+static const unsigned int ofpact_action_set_order[N_OFPACTS] = {
+    [OFPACT_STRIP_VLAN]     = 1,
+    [OFPACT_POP_MPLS]       = 2,
+    [OFPACT_DECAP]          = 3,
+    [OFPACT_ENCAP]          = 4,
+    [OFPACT_PUSH_MPLS]      = 5,
+    [OFPACT_PUSH_VLAN]      = 6,
+    [OFPACT_DEC_TTL]        = 7,
+    [OFPACT_DEC_MPLS_TTL]   = 8,
+    [OFPACT_DEC_NSH_TTL]    = 9,
+    /* Space reserved for set_or_move action list. */
+    [OFPACT_SET_QUEUE]      = ACTION_SET_MISC_POSITION + 1,
+    [OFPACT_GROUP]          = ACTION_SET_MISC_POSITION + 2,
+    [OFPACT_OUTPUT]         = ACTION_SET_MISC_POSITION + 3,
+    [OFPACT_RESUBMIT]       = ACTION_SET_MISC_POSITION + 4,
+    [OFPACT_CT_CLEAR]       = ACTION_SET_MISC_POSITION + 5,
+    [OFPACT_CT]             = ACTION_SET_MISC_POSITION + 6,
+};

 /* Reads 'action_set', which contains ofpacts accumulated by
  * OFPACT_WRITE_ACTIONS instructions, and writes equivalent actions to be
@@ -7172,18 +7175,32 @@  void
 ofpacts_execute_action_set(struct ofpbuf *action_list,
                            const struct ofpbuf *action_set)
 {
-    /* The OpenFlow spec "Action Set" section specifies this order. */
-    ofpacts_copy_last(action_list, action_set, OFPACT_STRIP_VLAN);
-    ofpacts_copy_last(action_list, action_set, OFPACT_POP_MPLS);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DECAP);
-    ofpacts_copy_last(action_list, action_set, OFPACT_ENCAP);
-    ofpacts_copy_last(action_list, action_set, OFPACT_PUSH_MPLS);
-    ofpacts_copy_last(action_list, action_set, OFPACT_PUSH_VLAN);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DEC_TTL);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DEC_MPLS_TTL);
-    ofpacts_copy_last(action_list, action_set, OFPACT_DEC_NSH_TTL);
-    ofpacts_copy_all(action_list, action_set, ofpact_is_set_or_move_action);
-    ofpacts_copy_last(action_list, action_set, OFPACT_SET_QUEUE);
+    const struct ofpact *actions[ACTION_SET_COUNT] = {NULL,};
+    struct ofpbuf set_or_move_action_list;
+    ofpbuf_init(&set_or_move_action_list, 0);
+
+    const struct ofpact *cursor;
+
+    OFPACT_FOR_EACH (cursor, action_set->data, action_set->size) {
+        unsigned int loc = ofpact_action_set_order[cursor->type];
+
+        if (loc) {
+            actions[loc-1] = cursor;
+        } else if (ofpact_is_set_or_move_action(cursor)) {
+            ofpact_copy(&set_or_move_action_list, cursor);
+        }
+    }
+
+    /* Copy up to OFPACT_SET_QUEUE. */
+    for (int i = 0; i < ACTION_SET_MISC_POSITION + 1; ++i) {
+        if (i == ACTION_SET_MISC_POSITION - 1) {
+            ofpacts_copy_all(action_list, &set_or_move_action_list);
+        } else if (actions[i]) {
+            ofpact_copy(action_list, actions[i]);
+        }
+    }
+
+    ofpbuf_uninit(&set_or_move_action_list);

     /* If both OFPACT_GROUP and OFPACT_OUTPUT are present, OpenFlow says that
      * we should execute only OFPACT_GROUP.
@@ -7191,12 +7208,15 @@  ofpacts_execute_action_set(struct ofpbuf *action_list,
      * If neither OFPACT_GROUP nor OFPACT_OUTPUT is present, then we can drop
      * all the actions because there's no point in modifying a packet that will
      * not be sent anywhere. */
-    if (!ofpacts_copy_last(action_list, action_set, OFPACT_GROUP) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_OUTPUT) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_RESUBMIT) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_CT_CLEAR) &&
-        !ofpacts_copy_last(action_list, action_set, OFPACT_CT)) {
+    const struct ofpact *final_action = NULL;
+    for (int i = ACTION_SET_MISC_POSITION + 1; !final_action && i <
ACTION_SET_COUNT; ++i) {
+        final_action = actions[i];
+    }
+
+    if (!final_action) {
         ofpbuf_clear(action_list);
+    } else {
+        ofpact_copy(action_list, final_action);
     }
 }