[ovs-dev] [mirror 13/13] ofproto-dpif: Get rid of "struct dst".

Ben Pfaff blp at nicira.com
Wed Oct 26 17:09:46 UTC 2011


struct dst is an intermediate form for OFPP_NORMAL translation that
has existed since the beginning of Open vSwitch development.  It
has always been a bit ugly, since ideally we wouldn't need any intermediate
form at all.  This commit eliminates it, which speeds up OFPP_NORMAL
translation.

struct dst was used earlier to eliminate duplicate packets in OFPP_NORMAL
output.  Now, we have rules that eliminate duplicate packets in a cheaper
way.

OFPP_NORMAL outputs packets for two different reasons, forwarding and
mirroring, so those are the two possible sources of packet duplication.
Forwarding by itself never outputs two copies of a packet to a single port
on a given VLAN, and this is also true of mirroring by itself since commit
"ofproto-dpif: Improve RSPAN translation performance from O(n**2) to O(n)".

The only remaining possibility, then, is that forwarding and mirroring
between them duplicate an output packet.  However, the algorithms are now
designed to prevent this.  Forwarding will never output to a mirroring
destination output port.  Forwarding will only output to a mirroring
output VLAN if the packet arrived on a mirroring output VLAN, and in that
case mirroring is disabled.

This commit has the side effect of improving behavior for VLAN output.
Previously, a packet that arrived with an 802.1Q tag with both VID and PCP
of 0 would be output with a similar tag in some cases; now it is
consistently stripped.  This change is reflected in the unit test change.

We really need some unit tests for mirroring.  I have not tested mirroring
behavior, only theorized about it (see above).
---
 ofproto/ofproto-dpif.c |  315 +++++++++++++++++-------------------------------
 tests/ofproto-dpif.at  |   12 +-
 2 files changed, 115 insertions(+), 212 deletions(-)

diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 37381f9..5951f18 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -412,12 +412,9 @@ static struct ofport_dpif *get_odp_port(struct ofproto_dpif *,
 static void update_learning_table(struct ofproto_dpif *,
                                   const struct flow *, int vlan,
                                   struct ofbundle *);
-static bool is_admissible(struct ofproto_dpif *, const struct flow *,
-                          bool have_packet, tag_type *, int *vlanp,
-                          struct ofbundle **in_bundlep);
-
 /* Upcalls. */
 #define FLOW_MISS_MAX_BATCH 50
+
 static void handle_upcall(struct ofproto_dpif *, struct dpif_upcall *);
 static void handle_miss_upcalls(struct ofproto_dpif *,
                                 struct dpif_upcall *, size_t n);
@@ -4378,21 +4375,6 @@ xlate_actions(struct action_xlate_ctx *ctx,
 
 /* OFPP_NORMAL implementation. */
 
-struct dst {
-    struct ofport_dpif *port;
-    uint16_t vid;
-};
-
-struct dst_set {
-    struct dst builtin[32];
-    struct dst *dsts;
-    size_t n, allocated;
-};
-
-static void dst_set_init(struct dst_set *);
-static void dst_set_add(struct dst_set *, const struct dst *);
-static void dst_set_free(struct dst_set *);
-
 static struct ofport_dpif *ofbundle_get_a_port(const struct ofbundle *);
 
 /* Given 'vid', the VID obtained from the 802.1Q header that was received as
@@ -4499,20 +4481,34 @@ output_vlan_to_vid(const struct ofbundle *out_bundle, uint16_t vlan)
     }
 }
 
-static bool
-set_dst(struct action_xlate_ctx *ctx, struct dst *dst,
-        const struct ofbundle *in_bundle, const struct ofbundle *out_bundle)
+static void
+output_normal(struct action_xlate_ctx *ctx, const struct ofbundle *out_bundle,
+              uint16_t vlan)
 {
-    uint16_t vlan;
+    struct ofport_dpif *port;
+    uint16_t vid;
+    ovs_be16 tci;
 
-    vlan = input_vid_to_vlan(in_bundle, vlan_tci_to_vid(ctx->flow.vlan_tci));
-    dst->vid = output_vlan_to_vid(out_bundle, vlan);
+    vid = output_vlan_to_vid(out_bundle, vlan);
+    if (!out_bundle->bond) {
+        port = ofbundle_get_a_port(out_bundle);
+    } else {
+        port = bond_choose_output_slave(out_bundle->bond, &ctx->flow,
+                                        vid, &ctx->tags);
+        if (!port) {
+            /* No slaves enabled, so drop packet. */
+            return;
+        }
+    }
 
-    dst->port = (!out_bundle->bond
-                 ? ofbundle_get_a_port(out_bundle)
-                 : bond_choose_output_slave(out_bundle->bond, &ctx->flow,
-                                            dst->vid, &ctx->tags));
-    return dst->port != NULL;
+    tci = htons(vid) | (ctx->flow.vlan_tci & htons(VLAN_PCP_MASK));
+    if (tci) {
+        tci |= htons(VLAN_CFI);
+    }
+    commit_vlan_action(ctx, tci);
+
+    compose_output_action(ctx, port->odp_port);
+    ctx->nf_output_iface = port->odp_port;
 }
 
 static int
@@ -4522,41 +4518,6 @@ mirror_mask_ffs(mirror_mask_t mask)
     return ffs(mask);
 }
 
-static void
-dst_set_init(struct dst_set *set)
-{
-    set->dsts = set->builtin;
-    set->n = 0;
-    set->allocated = ARRAY_SIZE(set->builtin);
-}
-
-static void
-dst_set_add(struct dst_set *set, const struct dst *dst)
-{
-    if (set->n >= set->allocated) {
-        size_t new_allocated;
-        struct dst *new_dsts;
-
-        new_allocated = set->allocated * 2;
-        new_dsts = xmalloc(new_allocated * sizeof *new_dsts);
-        memcpy(new_dsts, set->dsts, set->n * sizeof *new_dsts);
-
-        dst_set_free(set);
-
-        set->dsts = new_dsts;
-        set->allocated = new_allocated;
-    }
-    set->dsts[set->n++] = *dst;
-}
-
-static void
-dst_set_free(struct dst_set *set)
-{
-    if (set->dsts != set->builtin) {
-        free(set->dsts);
-    }
-}
-
 static bool
 ofbundle_trunks_vlan(const struct ofbundle *bundle, uint16_t vlan)
 {
@@ -4578,12 +4539,12 @@ ofbundle_get_a_port(const struct ofbundle *bundle)
                         struct ofport_dpif, bundle_node);
 }
 
-static void
+static mirror_mask_t
 compose_dsts(struct action_xlate_ctx *ctx, uint16_t vlan,
              const struct ofbundle *in_bundle,
-             const struct ofbundle *out_bundle, struct dst_set *set)
+             const struct ofbundle *out_bundle)
 {
-    struct dst dst;
+    mirror_mask_t dst_mirrors = 0;
 
     if (out_bundle == OFBUNDLE_FLOOD) {
         struct ofbundle *bundle;
@@ -4592,16 +4553,18 @@ compose_dsts(struct action_xlate_ctx *ctx, uint16_t vlan,
             if (bundle != in_bundle
                 && ofbundle_includes_vlan(bundle, vlan)
                 && bundle->floodable
-                && !bundle->mirror_out
-                && set_dst(ctx, &dst, in_bundle, bundle)) {
-                dst_set_add(set, &dst);
+                && !bundle->mirror_out) {
+                output_normal(ctx, bundle, vlan);
+                dst_mirrors |= bundle->dst_mirrors;
             }
         }
         ctx->nf_output_iface = NF_OUT_FLOOD;
-    } else if (out_bundle && set_dst(ctx, &dst, in_bundle, out_bundle)) {
-        dst_set_add(set, &dst);
-        ctx->nf_output_iface = dst.port->odp_port;
+    } else if (out_bundle) {
+        output_normal(ctx, out_bundle, vlan);
+        dst_mirrors = out_bundle->dst_mirrors;
     }
+
+    return dst_mirrors;
 }
 
 static bool
@@ -4652,20 +4615,15 @@ eth_dst_may_rspan(const uint8_t dst[ETH_ADDR_LEN])
 }
 
 static void
-compose_mirror_dsts(struct action_xlate_ctx *ctx,
-                    uint16_t vlan, const struct ofbundle *in_bundle,
-                    struct dst_set *set)
+output_mirrors(struct action_xlate_ctx *ctx,
+               uint16_t vlan, const struct ofbundle *in_bundle,
+               mirror_mask_t dst_mirrors)
 {
     struct ofproto_dpif *ofproto = ctx->ofproto;
     mirror_mask_t mirrors;
     uint16_t flow_vid;
-    size_t i;
-
-    mirrors = in_bundle->src_mirrors;
-    for (i = 0; i < set->n; i++) {
-        mirrors |= set->dsts[i].port->bundle->dst_mirrors;
-    }
 
+    mirrors = in_bundle->src_mirrors | dst_mirrors;
     if (!mirrors) {
         return;
     }
@@ -4673,7 +4631,6 @@ compose_mirror_dsts(struct action_xlate_ctx *ctx,
     flow_vid = vlan_tci_to_vid(ctx->flow.vlan_tci);
     while (mirrors) {
         struct ofmirror *m;
-        struct dst dst;
 
         m = ofproto->mirrors[mirror_mask_ffs(mirrors) - 1];
 
@@ -4684,84 +4641,21 @@ compose_mirror_dsts(struct action_xlate_ctx *ctx,
 
         mirrors &= ~m->dup_mirrors;
         if (m->out) {
-            if (set_dst(ctx, &dst, in_bundle, m->out)) {
-                dst_set_add(set, &dst);
-            }
+            output_normal(ctx, m->out, vlan);
         } else if (eth_dst_may_rspan(ctx->flow.dl_dst)
                    && vlan != m->out_vlan) {
             struct ofbundle *bundle;
 
             HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
                 if (ofbundle_includes_vlan(bundle, m->out_vlan)
-                    && !bundle->mirror_out
-                    && set_dst(ctx, &dst, in_bundle, bundle))
-                {
-                    /* set_dst() got dst->vid from the input packet's VLAN,
-                     * not from m->out_vlan, so recompute it. */
-                    dst.vid = output_vlan_to_vid(bundle, m->out_vlan);
-
-                    if (bundle == in_bundle && dst.vid == flow_vid) {
-                        /* Don't send out input port on same VLAN. */
-                        continue;
-                    }
-                    dst_set_add(set, &dst);
+                    && !bundle->mirror_out) {
+                    output_normal(ctx, bundle, m->out_vlan);
                 }
             }
         }
     }
 }
 
-static void
-compose_actions(struct action_xlate_ctx *ctx, uint16_t vlan,
-                const struct ofbundle *in_bundle,
-                const struct ofbundle *out_bundle)
-{
-    uint16_t initial_vid, cur_vid;
-    const struct dst *dst;
-    struct dst_set set;
-
-    dst_set_init(&set);
-    compose_dsts(ctx, vlan, in_bundle, out_bundle, &set);
-    compose_mirror_dsts(ctx, vlan, in_bundle, &set);
-    if (!set.n) {
-        dst_set_free(&set);
-        return;
-    }
-
-    /* Output all the packets we can without having to change the VLAN. */
-    commit_odp_actions(ctx);
-    initial_vid = vlan_tci_to_vid(ctx->flow.vlan_tci);
-    for (dst = set.dsts; dst < &set.dsts[set.n]; dst++) {
-        if (dst->vid != initial_vid) {
-            continue;
-        }
-        compose_output_action(ctx, dst->port->odp_port);
-    }
-
-    /* Then output the rest. */
-    cur_vid = initial_vid;
-    for (dst = set.dsts; dst < &set.dsts[set.n]; dst++) {
-        if (dst->vid == initial_vid) {
-            continue;
-        }
-        if (dst->vid != cur_vid) {
-            ovs_be16 tci;
-
-            tci = htons(dst->vid);
-            tci |= ctx->flow.vlan_tci & htons(VLAN_PCP_MASK);
-            if (tci) {
-                tci |= htons(VLAN_CFI);
-            }
-            commit_vlan_action(ctx, tci);
-
-            cur_vid = dst->vid;
-        }
-        compose_output_action(ctx, dst->port->odp_port);
-    }
-
-    dst_set_free(&set);
-}
-
 /* A VM broadcasts a gratuitous ARP to indicate that it has resumed after
  * migration.  Older Citrix-patched Linux DomU used gratuitous ARP replies to
  * indicate this; newer upstream kernels use gratuitous ARP requests. */
@@ -4812,6 +4706,36 @@ update_learning_table(struct ofproto_dpif *ofproto,
     }
 }
 
+static struct ofport_dpif *
+lookup_input_bundle(struct ofproto_dpif *ofproto, uint16_t in_port, bool warn)
+{
+    struct ofport_dpif *ofport;
+
+    /* Find the port and bundle for the received packet. */
+    ofport = get_ofp_port(ofproto, in_port);
+    if (ofport && ofport->bundle) {
+        return ofport;
+    }
+
+    /* Odd.  A few possible reasons here:
+     *
+     * - We deleted a port but there are still a few packets queued up
+     *   from it.
+     *
+     * - Someone externally added a port (e.g. "ovs-dpctl add-if") that
+     *   we don't know about.
+     *
+     * - The ofproto client didn't configure the port as part of a bundle.
+     */
+    if (warn) {
+        static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
+
+        VLOG_WARN_RL(&rl, "bridge %s: received packet on unknown "
+                     "port %"PRIu16, ofproto->up.name, in_port);
+    }
+    return NULL;
+}
+
 /* Determines whether packets in 'flow' within 'br' should be forwarded or
  * dropped.  Returns true if they may be forwarded, false if they should be
  * dropped.
@@ -4834,57 +4758,20 @@ update_learning_table(struct ofproto_dpif *ofproto,
  */
 static bool
 is_admissible(struct ofproto_dpif *ofproto, const struct flow *flow,
-              bool have_packet,
-              tag_type *tags, int *vlanp, struct ofbundle **in_bundlep)
+              struct ofport_dpif *in_port, uint16_t vlan, bool warn,
+              tag_type *tags)
 {
-    struct ofport_dpif *in_port;
-    struct ofbundle *in_bundle;
-    uint16_t vid;
-    int vlan;
+    struct ofbundle *in_bundle = in_port->bundle;
 
-    /* Find the port and bundle for the received packet. */
-    in_port = get_ofp_port(ofproto, flow->in_port);
-    *in_bundlep = in_bundle = in_port ? in_port->bundle : NULL;
-    if (!in_port || !in_bundle) {
-        /* No interface?  Something fishy... */
-        if (have_packet) {
-            /* Odd.  A few possible reasons here:
-             *
-             * - We deleted a port but there are still a few packets queued up
-             *   from it.
-             *
-             * - Someone externally added a port (e.g. "ovs-dpctl add-if") that
-             *   we don't know about.
-             *
-             * - Packet arrived on the local port but the local port is not
-             *   part of a bundle.
-             */
-            static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
-
-            VLOG_WARN_RL(&rl, "bridge %s: received packet on unknown "
-                         "port %"PRIu16,
-                         ofproto->up.name, flow->in_port);
-        }
-        *vlanp = -1;
-        return false;
-    }
-
-    vid = vlan_tci_to_vid(flow->vlan_tci);
-    if (!input_vid_is_valid(vid, in_bundle, have_packet)) {
-        *vlanp = -1;
-        return false;
-    }
-    *vlanp = vlan = input_vid_to_vlan(in_bundle, vid);
-
-    /* Drop frames for reserved multicast addresses only if forward_bpdu
-     * option is absent. */
+    /* Drop frames for reserved multicast addresses
+     * only if forward_bpdu option is absent. */
     if (eth_addr_is_reserved(flow->dl_dst) && !ofproto->up.forward_bpdu) {
         return false;
     }
 
     /* Drop frames on bundles reserved for mirroring. */
     if (in_bundle->mirror_out) {
-        if (have_packet) {
+        if (warn) {
             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
             VLOG_WARN_RL(&rl, "bridge %s: dropping packet received on port "
                          "%s, which is reserved exclusively for mirroring",
@@ -4921,18 +4808,38 @@ is_admissible(struct ofproto_dpif *ofproto, const struct flow *flow,
 static void
 xlate_normal(struct action_xlate_ctx *ctx)
 {
+    mirror_mask_t dst_mirrors = 0;
+    struct ofport_dpif *in_port;
     struct ofbundle *in_bundle;
     struct ofbundle *out_bundle;
     struct mac_entry *mac;
-    int vlan;
+    uint16_t vlan;
+    uint16_t vid;
 
     ctx->has_normal = true;
 
-    /* Check whether we should drop packets in this flow. */
-    if (!is_admissible(ctx->ofproto, &ctx->flow, ctx->packet != NULL,
-                       &ctx->tags, &vlan, &in_bundle)) {
-        out_bundle = NULL;
-        goto done;
+    /* Obtain in_port from ctx->flow.in_port.
+     *
+     * lookup_input_bundle() also ensures that in_port belongs to a bundle. */
+    in_port = lookup_input_bundle(ctx->ofproto, ctx->flow.in_port,
+                                  ctx->packet != NULL);
+    if (!in_port) {
+        return;
+    }
+    in_bundle = in_port->bundle;
+
+    /* Check VLAN. */
+    vid = vlan_tci_to_vid(ctx->flow.vlan_tci);
+    if (!input_vid_is_valid(vid, in_bundle, ctx->packet != NULL)) {
+        return;
+    }
+    vlan = input_vid_to_vlan(in_bundle, vid);
+
+    /* Check other admissibility requirements. */
+    if (!is_admissible(ctx->ofproto, &ctx->flow, in_port, vlan,
+                       ctx->packet != NULL, &ctx->tags)) {
+        output_mirrors(ctx, vlan, in_bundle, 0);
+        return;
     }
 
     /* Learn source MAC. */
@@ -4958,14 +4865,10 @@ xlate_normal(struct action_xlate_ctx *ctx)
     }
 
     /* Don't send packets out their input bundles. */
-    if (in_bundle == out_bundle) {
-        out_bundle = NULL;
-    }
-
-done:
-    if (in_bundle) {
-        compose_actions(ctx, vlan, in_bundle, out_bundle);
+    if (in_bundle != out_bundle) {
+        compose_dsts(ctx, vlan, in_bundle, out_bundle);
     }
+    output_mirrors(ctx, vlan, in_bundle, dst_mirrors);
 }
 
 /* Optimized flow revalidation.
diff --git a/tests/ofproto-dpif.at b/tests/ofproto-dpif.at
index 312ec1f..668b1bd 100644
--- a/tests/ofproto-dpif.at
+++ b/tests/ofproto-dpif.at
@@ -150,7 +150,7 @@ for tuple in \
         "p2  12   0 drop" \
         "p2  12   1 drop" \
         "p3  none 0 p4,p7,p8,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
-        "p3  0    0 p4,p7,p8,pop(vlan),push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
+        "p3  0    0 pop(vlan),p4,p7,p8,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
         "p3  0    1 p4,p7,p8,pop(vlan),push(vlan(vid=12,pcp=1)),br0,p1,p5,p6" \
         "p3  10   0 drop" \
         "p3  10   1 drop" \
@@ -159,7 +159,7 @@ for tuple in \
         "p3  12   0 drop" \
         "p3  12   1 drop" \
         "p4  none 0 p3,p7,p8,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
-        "p4  0    0 p3,p7,p8,pop(vlan),push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
+        "p4  0    0 pop(vlan),p3,p7,p8,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
         "p4  0    1 p3,p7,p8,pop(vlan),push(vlan(vid=12,pcp=1)),br0,p1,p5,p6" \
         "p4  10   0 drop" \
         "p4  10   1 drop" \
@@ -168,7 +168,7 @@ for tuple in \
         "p4  12   0 drop" \
         "p4  12   1 drop" \
         "p5  none 0 p2,push(vlan(vid=10,pcp=0)),br0,p1,p6,p7,p8" \
-        "p5  0    0 p2,pop(vlan),push(vlan(vid=10,pcp=0)),br0,p1,p6,p7,p8" \
+        "p5  0    0 pop(vlan),p2,push(vlan(vid=10,pcp=0)),br0,p1,p6,p7,p8" \
         "p5  0    1 p2,pop(vlan),push(vlan(vid=10,pcp=1)),br0,p1,p6,p7,p8" \
         "p5  10   0 br0,p1,p6,p7,p8,pop(vlan),p2" \
         "p5  10   1 br0,p1,p6,p7,p8,pop(vlan),push(vlan(vid=0,pcp=1)),p2" \
@@ -177,7 +177,7 @@ for tuple in \
         "p5  12   0 br0,p1,p6,pop(vlan),p3,p4,p7,p8" \
         "p5  12   1 br0,p1,p6,pop(vlan),push(vlan(vid=0,pcp=1)),p3,p4,p7,p8" \
         "p6  none 0 p2,push(vlan(vid=10,pcp=0)),br0,p1,p5,p7,p8" \
-        "p6  0    0 p2,pop(vlan),push(vlan(vid=10,pcp=0)),br0,p1,p5,p7,p8" \
+        "p6  0    0 pop(vlan),p2,push(vlan(vid=10,pcp=0)),br0,p1,p5,p7,p8" \
         "p6  0    1 p2,pop(vlan),push(vlan(vid=10,pcp=1)),br0,p1,p5,p7,p8" \
         "p6  10   0 br0,p1,p5,p7,p8,pop(vlan),p2" \
         "p6  10   1 br0,p1,p5,p7,p8,pop(vlan),push(vlan(vid=0,pcp=1)),p2" \
@@ -186,7 +186,7 @@ for tuple in \
         "p6  12   0 br0,p1,p5,pop(vlan),p3,p4,p7,p8" \
         "p6  12   1 br0,p1,p5,pop(vlan),push(vlan(vid=0,pcp=1)),p3,p4,p7,p8" \
         "p7  none 0 p3,p4,p8,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
-        "p7  0    0 p3,p4,p8,pop(vlan),push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
+        "p7  0    0 pop(vlan),p3,p4,p8,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
         "p7  0    1 p3,p4,p8,pop(vlan),push(vlan(vid=12,pcp=1)),br0,p1,p5,p6" \
         "p7  10   0 br0,p1,p5,p6,p8,pop(vlan),p2" \
         "p7  10   1 br0,p1,p5,p6,p8,pop(vlan),push(vlan(vid=0,pcp=1)),p2" \
@@ -195,7 +195,7 @@ for tuple in \
         "p7  12   0 br0,p1,p5,p6,pop(vlan),p3,p4,p8" \
         "p7  12   1 br0,p1,p5,p6,pop(vlan),push(vlan(vid=0,pcp=1)),p3,p4,p8" \
         "p8  none 0 p3,p4,p7,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
-        "p8  0    0 p3,p4,p7,pop(vlan),push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
+        "p8  0    0 pop(vlan),p3,p4,p7,push(vlan(vid=12,pcp=0)),br0,p1,p5,p6" \
         "p8  0    1 p3,p4,p7,pop(vlan),push(vlan(vid=12,pcp=1)),br0,p1,p5,p6" \
         "p8  10   0 br0,p1,p5,p6,p7,pop(vlan),p2" \
         "p8  10   1 br0,p1,p5,p6,p7,pop(vlan),push(vlan(vid=0,pcp=1)),p2" \
-- 
1.7.2.5




More information about the dev mailing list