vswitch: Implement bundle action.

This patch creates a new action called "bundle".  Bundles are a way
to implement a simple form of multipath in OpenFlow by grouping
several ports in a single output-like action.

6 files changed, 377 insertions, 0 deletions

diff --git a/tests/.gitignore b/tests/.gitignore
index e2b293c4f..e945a8507 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -9,6 +9,7 @@
 /ovs-pki.log
 /pki/
 /test-aes128
+/test-bundle
 /test-byte-order
 /test-classifier
 /test-csum
diff --git a/tests/automake.mk b/tests/automake.mk
index 750f420de..be09b4a6c 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -8,6 +8,7 @@ TESTSUITE_AT = \
 	tests/testsuite.at \
 	tests/ovsdb-macros.at \
 	tests/library.at \
+	tests/bundle.at \
 	tests/classifier.at \
 	tests/check-structs.at \
 	tests/daemon.at \
@@ -66,6 +67,7 @@ lcov_wrappers = \
 	tests/lcov/ovsdb-server \
 	tests/lcov/ovsdb-tool \
 	tests/lcov/test-aes128 \
+	tests/lcov/test-bundle \
 	tests/lcov/test-byte-order \
 	tests/lcov/test-classifier \
 	tests/lcov/test-csum \
@@ -118,6 +120,7 @@ valgrind_wrappers = \
 	tests/valgrind/ovsdb-server \
 	tests/valgrind/ovsdb-tool \
 	tests/valgrind/test-aes128 \
+	tests/valgrind/test-bundle \
 	tests/valgrind/test-byte-order \
 	tests/valgrind/test-classifier \
 	tests/valgrind/test-csum \
@@ -185,6 +188,10 @@ noinst_PROGRAMS += tests/test-aes128
 tests_test_aes128_SOURCES = tests/test-aes128.c
 tests_test_aes128_LDADD = lib/libopenvswitch.a
 
+noinst_PROGRAMS += tests/test-bundle
+tests_test_bundle_SOURCES = tests/test-bundle.c
+tests_test_bundle_LDADD = lib/libopenvswitch.a
+
 noinst_PROGRAMS += tests/test-classifier
 tests_test_classifier_SOURCES = tests/test-classifier.c
 tests_test_classifier_LDADD = lib/libopenvswitch.a
diff --git a/tests/bundle.at b/tests/bundle.at
new file mode 100644
index 000000000..063cdd312
--- /dev/null
+++ b/tests/bundle.at
@@ -0,0 +1,123 @@
+AT_BANNER([bundle link selection])
+
+# The test-bundle program prints a lot of output on stdout, but each of the
+# tests below ignores it because it will vary a bit depending on endianness and
+# floating point precision.  test-bundle will output an error message on
+# stderr and return with exit code 1 if anything really goes wrong.  In each
+# case, we list the (approximate) expected output in a comment to aid debugging
+# if the test does fail.
+
+AT_SETUP([hrw bundle link selection])
+AT_CHECK([[test-bundle 'symmetric_l4,60,hrw,ofport,slaves:1,2,3,4,5,6']],
+  [0], [ignore])
+# 100000: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00
+# 110000: disruption=0.50 (perfect=0.50) 0.50 0.50 0.00 0.00 0.00 0.00
+# 010000: disruption=0.50 (perfect=0.50) 0.00 1.00 0.00 0.00 0.00 0.00
+# 011000: disruption=0.50 (perfect=0.50) 0.00 0.50 0.50 0.00 0.00 0.00
+# 111000: disruption=0.33 (perfect=0.33) 0.33 0.33 0.34 0.00 0.00 0.00
+# 101000: disruption=0.33 (perfect=0.33) 0.50 0.00 0.50 0.00 0.00 0.00
+# 001000: disruption=0.50 (perfect=0.50) 0.00 0.00 1.00 0.00 0.00 0.00
+# 001100: disruption=0.50 (perfect=0.50) 0.00 0.00 0.50 0.50 0.00 0.00
+# 101100: disruption=0.33 (perfect=0.33) 0.33 0.00 0.34 0.33 0.00 0.00
+# 111100: disruption=0.25 (perfect=0.25) 0.25 0.25 0.25 0.25 0.00 0.00
+# 011100: disruption=0.25 (perfect=0.25) 0.00 0.33 0.33 0.33 0.00 0.00
+# 010100: disruption=0.33 (perfect=0.33) 0.00 0.50 0.00 0.50 0.00 0.00
+# 110100: disruption=0.33 (perfect=0.33) 0.33 0.33 0.00 0.34 0.00 0.00
+# 100100: disruption=0.33 (perfect=0.33) 0.50 0.00 0.00 0.50 0.00 0.00
+# 000100: disruption=0.50 (perfect=0.50) 0.00 0.00 0.00 1.00 0.00 0.00
+# 000110: disruption=0.50 (perfect=0.50) 0.00 0.00 0.00 0.50 0.50 0.00
+# 100110: disruption=0.33 (perfect=0.33) 0.33 0.00 0.00 0.33 0.33 0.00
+# 110110: disruption=0.25 (perfect=0.25) 0.25 0.25 0.00 0.25 0.25 0.00
+# 010110: disruption=0.25 (perfect=0.25) 0.00 0.34 0.00 0.33 0.33 0.00
+# 011110: disruption=0.25 (perfect=0.25) 0.00 0.25 0.25 0.25 0.25 0.00
+# 111110: disruption=0.20 (perfect=0.20) 0.20 0.20 0.20 0.20 0.20 0.00
+# 101110: disruption=0.20 (perfect=0.20) 0.25 0.00 0.25 0.25 0.25 0.00
+# 001110: disruption=0.25 (perfect=0.25) 0.00 0.00 0.34 0.33 0.33 0.00
+# 001010: disruption=0.33 (perfect=0.33) 0.00 0.00 0.50 0.00 0.50 0.00
+# 101010: disruption=0.33 (perfect=0.33) 0.33 0.00 0.34 0.00 0.33 0.00
+# 111010: disruption=0.25 (perfect=0.25) 0.25 0.25 0.25 0.00 0.25 0.00
+# 011010: disruption=0.25 (perfect=0.25) 0.00 0.33 0.34 0.00 0.33 0.00
+# 010010: disruption=0.34 (perfect=0.33) 0.00 0.50 0.00 0.00 0.50 0.00
+# 110010: disruption=0.33 (perfect=0.33) 0.33 0.33 0.00 0.00 0.33 0.00
+# 100010: disruption=0.33 (perfect=0.33) 0.50 0.00 0.00 0.00 0.50 0.00
+# 000010: disruption=0.50 (perfect=0.50) 0.00 0.00 0.00 0.00 1.00 0.00
+# 000011: disruption=0.50 (perfect=0.50) 0.00 0.00 0.00 0.00 0.50 0.50
+# 100011: disruption=0.33 (perfect=0.33) 0.33 0.00 0.00 0.00 0.33 0.33
+# 110011: disruption=0.25 (perfect=0.25) 0.25 0.25 0.00 0.00 0.25 0.25
+# 010011: disruption=0.25 (perfect=0.25) 0.00 0.33 0.00 0.00 0.33 0.33
+# 011011: disruption=0.25 (perfect=0.25) 0.00 0.25 0.25 0.00 0.25 0.25
+# 111011: disruption=0.20 (perfect=0.20) 0.20 0.20 0.20 0.00 0.20 0.20
+# 101011: disruption=0.20 (perfect=0.20) 0.25 0.00 0.25 0.00 0.25 0.25
+# 001011: disruption=0.25 (perfect=0.25) 0.00 0.00 0.34 0.00 0.33 0.33
+# 001111: disruption=0.25 (perfect=0.25) 0.00 0.00 0.25 0.25 0.25 0.25
+# 101111: disruption=0.20 (perfect=0.20) 0.20 0.00 0.20 0.20 0.20 0.20
+# 111111: disruption=0.17 (perfect=0.17) 0.17 0.17 0.17 0.17 0.17 0.17
+# 011111: disruption=0.17 (perfect=0.17) 0.00 0.20 0.20 0.20 0.20 0.20
+# 010111: disruption=0.20 (perfect=0.20) 0.00 0.25 0.00 0.25 0.25 0.25
+# 110111: disruption=0.20 (perfect=0.20) 0.20 0.20 0.00 0.20 0.20 0.20
+# 100111: disruption=0.20 (perfect=0.20) 0.25 0.00 0.00 0.25 0.25 0.25
+# 000111: disruption=0.25 (perfect=0.25) 0.00 0.00 0.00 0.33 0.33 0.33
+# 000101: disruption=0.33 (perfect=0.33) 0.00 0.00 0.00 0.50 0.00 0.50
+# 100101: disruption=0.33 (perfect=0.33) 0.33 0.00 0.00 0.33 0.00 0.33
+# 110101: disruption=0.25 (perfect=0.25) 0.25 0.25 0.00 0.25 0.00 0.25
+# 010101: disruption=0.25 (perfect=0.25) 0.00 0.33 0.00 0.33 0.00 0.33
+# 011101: disruption=0.25 (perfect=0.25) 0.00 0.25 0.25 0.25 0.00 0.25
+# 111101: disruption=0.20 (perfect=0.20) 0.20 0.20 0.20 0.20 0.00 0.20
+# 101101: disruption=0.20 (perfect=0.20) 0.25 0.00 0.25 0.25 0.00 0.25
+# 001101: disruption=0.25 (perfect=0.25) 0.00 0.00 0.33 0.33 0.00 0.33
+# 001001: disruption=0.33 (perfect=0.33) 0.00 0.00 0.50 0.00 0.00 0.50
+# 101001: disruption=0.33 (perfect=0.33) 0.33 0.00 0.33 0.00 0.00 0.33
+# 111001: disruption=0.25 (perfect=0.25) 0.25 0.25 0.25 0.00 0.00 0.25
+# 011001: disruption=0.25 (perfect=0.25) 0.00 0.33 0.34 0.00 0.00 0.33
+# 010001: disruption=0.34 (perfect=0.33) 0.00 0.50 0.00 0.00 0.00 0.50
+# 110001: disruption=0.33 (perfect=0.33) 0.33 0.33 0.00 0.00 0.00 0.34
+# 100001: disruption=0.33 (perfect=0.33) 0.50 0.00 0.00 0.00 0.00 0.50
+# 000001: disruption=0.50 (perfect=0.50) 0.00 0.00 0.00 0.00 0.00 1.00
+# 000000: disruption=1.00 (perfect=1.00) 0.00 0.00 0.00 0.00 0.00 0.00
+# 100000: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00
+AT_CLEANUP
+
+AT_SETUP([hrw bundle single link selection])
+AT_CHECK([[test-bundle 'symmetric_l4,60,hrw,ofport,slaves:1']],
+  [0], [ignore])
+# 1: disruption=1.00 (perfect=1.00) 1.00
+# 0: disruption=1.00 (perfect=1.00) 0.00
+# 1: disruption=1.00 (perfect=1.00) 1.00
+AT_CLEANUP
+
+AT_SETUP([hrw bundle no link selection])
+AT_CHECK([[test-bundle 'symmetric_l4,60,hrw,ofport,slaves:']],
+  [0], [ignore])
+AT_CLEANUP
+#: disruption=0.00 (perfect=0.00)
+#: disruption=0.00 (perfect=0.00)
+
+AT_SETUP([bundle action missing argument])
+AT_CHECK([ovs-ofctl parse-flow actions=bundle], [1], [],
+  [ovs-ofctl: : not enough arguments to bundle action
+])
+AT_CLEANUP
+
+AT_SETUP([bundle action bad fields])
+AT_CHECK([ovs-ofctl parse-flow 'actions=bundle(xyzzy,60,hrw,ofport,slaves:1,2))'], [1], [],
+  [ovs-ofctl: xyzzy,60,hrw,ofport,slaves:1,2: unknown fields `xyzzy'
+])
+AT_CLEANUP
+
+AT_SETUP([bundle action bad algorithm])
+AT_CHECK([ovs-ofctl parse-flow 'actions=bundle(symmetric_l4,60,fubar,ofport,slaves:1,2))'], [1], [],
+  [ovs-ofctl: symmetric_l4,60,fubar,ofport,slaves:1,2: unknown algorithm `fubar'
+])
+AT_CLEANUP
+
+AT_SETUP([bundle action bad slave type])
+AT_CHECK([ovs-ofctl parse-flow 'actions=bundle(symmetric_l4,60,hrw,robot,slaves:1,2))'], [1], [],
+  [ovs-ofctl: symmetric_l4,60,hrw,robot,slaves:1,2: unknown slave_type `robot'
+])
+AT_CLEANUP
+
+AT_SETUP([bundle action bad slave delimiter])
+AT_CHECK([ovs-ofctl parse-flow 'actions=bundle(symmetric_l4,60,hrw,ofport,robot:1,2))'], [1], [],
+  [ovs-ofctl: symmetric_l4,60,hrw,ofport,robot:1,2: missing slave delimiter, expected `slaves' got `robot'
+])
+AT_CLEANUP
diff --git a/tests/ovs-ofctl.at b/tests/ovs-ofctl.at
index 9e347cfff..63292dbb4 100644
--- a/tests/ovs-ofctl.at
+++ b/tests/ovs-ofctl.at
@@ -15,6 +15,10 @@ actions=set_tunnel:0x1234,set_tunnel64:0x9876,set_tunnel:0x123456789
 actions=multipath(eth_src, 50, hrw, 12, 0, NXM_NX_REG0[0..3]),multipath(symmetric_l4, 1024, iter_hash, 5000, 5050, NXM_NX_REG0[0..12])
 table=1,actions=drop
 tun_id=0x1234000056780000/0xffff0000ffff0000,actions=drop
+actions=bundle(eth_src,50,active_backup,ofport,slaves:1)
+actions=bundle(symmetric_l4,60,hrw,ofport,slaves:2,3)
+actions=bundle(symmetric_l4,60,hrw,ofport,slaves:)
+actions=output:1,bundle(eth_src,0,hrw,ofport,slaves:1),output:2
 ]])
 AT_CHECK([ovs-ofctl parse-flows flows.txt
 ], [0], [stdout])
@@ -33,6 +37,10 @@ NXT_FLOW_MOD: ADD actions=multipath(eth_src,50,hrw,12,0,NXM_NX_REG0[0..3]),multi
 NXT_FLOW_MOD_TABLE_ID: enable
 NXT_FLOW_MOD: ADD table:1 actions=drop
 NXT_FLOW_MOD: ADD table:255 tun_id=0x1234000056780000/0xffff0000ffff0000 actions=drop
+NXT_FLOW_MOD: ADD table:255 actions=bundle(eth_src,50,active_backup,ofport,slaves:1)
+NXT_FLOW_MOD: ADD table:255 actions=bundle(symmetric_l4,60,hrw,ofport,slaves:2,3)
+NXT_FLOW_MOD: ADD table:255 actions=bundle(symmetric_l4,60,hrw,ofport,slaves:)
+NXT_FLOW_MOD: ADD table:255 actions=output:1,bundle(eth_src,0,hrw,ofport,slaves:1),output:2
 ]])
 AT_CLEANUP
 
diff --git a/tests/test-bundle.c b/tests/test-bundle.c
new file mode 100644
index 000000000..8a892925e
--- /dev/null
+++ b/tests/test-bundle.c
@@ -0,0 +1,237 @@
+/* Copyright (c) 2011 Nicira Networks.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include "bundle.h"
+
+#include <math.h>
+#include <stdlib.h>
+
+#include "flow.h"
+#include "ofpbuf.h"
+#include "random.h"
+
+#include "util.h"
+
+#define N_FLOWS  50000
+#define MAX_SLAVES 8 /* Maximum supported by this test framework. */
+
+struct slave {
+    uint16_t slave_id;
+
+    bool enabled;
+    size_t flow_count;
+};
+
+struct slave_group {
+    size_t n_slaves;
+    struct slave slaves[MAX_SLAVES];
+};
+
+static struct slave *
+slave_lookup(struct slave_group *sg, uint16_t slave_id)
+{
+    size_t i;
+
+    for (i = 0; i < sg->n_slaves; i++) {
+        if (sg->slaves[i].slave_id == slave_id) {
+            return &sg->slaves[i];
+        }
+    }
+
+    return NULL;
+}
+
+static bool
+slave_enabled_cb(uint16_t slave_id, void *aux)
+{
+    struct slave *slave;
+
+    slave = slave_lookup(aux, slave_id);
+    return slave ? slave->enabled : false;
+}
+
+static struct nx_action_bundle *
+parse_bundle_actions(char *actions)
+{
+    struct nx_action_bundle *nab;
+    struct ofpbuf b;
+
+    ofpbuf_init(&b, 0);
+    bundle_parse(&b, actions);
+    nab = ofpbuf_steal_data(&b);
+    ofpbuf_uninit(&b);
+
+    if (ntohs(nab->n_slaves) > MAX_SLAVES) {
+        ovs_fatal(0, "At most %u slaves are supported", MAX_SLAVES);
+    }
+
+    return nab;
+}
+
+static const char *
+mask_str(uint8_t mask, size_t n_bits)
+{
+    static char str[9];
+    size_t i;
+
+    n_bits = MIN(n_bits, 8);
+    for (i = 0; i < n_bits; i++) {
+        str[i] = (1 << i) & mask ? '1' : '0';
+    }
+    str[i] = '\0';
+
+    return str;
+}
+
+int
+main(int argc, char *argv[])
+{
+    bool ok = true;
+    struct nx_action_bundle *nab;
+    struct flow *flows;
+    size_t i, n_permute, old_n_enabled;
+    struct slave_group sg;
+
+    set_program_name(argv[0]);
+    random_init();
+
+    if (argc != 2) {
+        ovs_fatal(0, "usage: %s bundle_action", program_name);
+    }
+
+    nab = parse_bundle_actions(argv[1]);
+
+    /* Generate 'slaves' array. */
+    sg.n_slaves = 0;
+    for (i = 0; i < ntohs(nab->n_slaves); i++) {
+        uint16_t slave_id = bundle_get_slave(nab, i);
+
+        if (slave_lookup(&sg, slave_id)) {
+            ovs_fatal(0, "Redundant slaves are not supported. ");
+        }
+
+        sg.slaves[sg.n_slaves].slave_id = slave_id;
+        sg.n_slaves++;
+    }
+
+    /* Generate flows. */
+    flows = xmalloc(N_FLOWS * sizeof *flows);
+    for (i = 0; i < N_FLOWS; i++) {
+        random_bytes(&flows[i], sizeof flows[i]);
+        flows[i].regs[0] = OFPP_NONE;
+    }
+
+    /* Cycles through each possible liveness permutation for the given
+     * n_slaves.  The initial state is equivalent to all slaves down, so we
+     * skip it by starting at i = 1. We do one extra iteration to cover
+     * transitioning from the final state back to the initial state. */
+    old_n_enabled = 0;
+    n_permute = 1 << sg.n_slaves;
+    for (i = 1; i <= n_permute + 1; i++) {
+        struct slave *slave;
+        size_t j, n_enabled, changed;
+        double disruption, perfect;
+        uint8_t mask;
+
+        mask = i % n_permute;
+
+        /* Gray coding ensures that in each iteration exactly one slave
+         * changes its liveness.  This makes the expected disruption a bit
+         * easier to calculate, and is likely similar to how failures will be
+         * experienced in the wild. */
+        mask = mask ^ (mask >> 1);
+
+        /* Initialize slaves. */
+        n_enabled = 0;
+        for (j = 0; j < sg.n_slaves; j++) {
+            slave = &sg.slaves[j];
+            slave->flow_count = 0;
+            slave->enabled = ((1 << j) & mask) != 0;
+
+            if (slave->enabled) {
+                n_enabled++;
+            }
+        }
+
+        changed = 0;
+        for (j = 0; j < N_FLOWS; j++) {
+            struct flow *flow = &flows[j];
+            uint16_t old_slave_id;
+
+            old_slave_id = flow->regs[0];
+            flow->regs[0] = bundle_execute(nab, flow, slave_enabled_cb, &sg);
+
+            if (flow->regs[0] != OFPP_NONE) {
+                slave_lookup(&sg, flow->regs[0])->flow_count++;
+            }
+
+            if (old_slave_id != flow->regs[0]) {
+                changed++;
+            }
+        }
+
+        if (old_n_enabled || n_enabled) {
+            perfect = 1.0 / MAX(old_n_enabled, n_enabled);
+        } else {
+            /* This will happen when 'sg.n_slaves' is 0. */
+            perfect = 0;
+        }
+
+        disruption = changed / (double)N_FLOWS;
+        printf("%s: disruption=%.2f (perfect=%.2f) ",
+               mask_str(mask, sg.n_slaves), disruption, perfect);
+
+        for (j = 0 ; j < sg.n_slaves; j++) {
+            struct slave *slave = &sg.slaves[j];
+            double flow_percent;
+
+            flow_percent = slave->flow_count / (double)N_FLOWS;
+            printf("%.2f ", flow_percent);
+
+            if (slave->enabled) {
+                double perfect_fp = 1.0 / n_enabled;
+
+                if (fabs(flow_percent - perfect_fp) >= .01) {
+                    fprintf(stderr, "%s: slave %d: flow_percentage=%.5f for"
+                            " differs from perfect=%.5f by more than .01\n",
+                            mask_str(mask, sg.n_slaves), slave->slave_id,
+                            flow_percent, perfect_fp);
+                    ok = false;
+                }
+            } else if (slave->flow_count) {
+                fprintf(stderr, "%s: slave %d: disabled slave received"
+                        " flows.\n", mask_str(mask, sg.n_slaves),
+                        slave->slave_id);
+                ok = false;
+            }
+        }
+        printf("\n");
+
+        if (fabs(disruption - perfect) >= .01) {
+            fprintf(stderr, "%s: disruption=%.5f differs from perfect=%.5f by"
+                    " more than .01\n", mask_str(mask, sg.n_slaves),
+                    disruption, perfect);
+            ok = false;
+        }
+
+        old_n_enabled = n_enabled;
+    }
+
+    free(nab);
+    free(flows);
+    return ok ? 0 : 1;
+}
diff --git a/tests/testsuite.at b/tests/testsuite.at
index 286789327..6ec77f8cf 100644
--- a/tests/testsuite.at
+++ b/tests/testsuite.at
@@ -39,6 +39,7 @@ m4_include([tests/ovsdb-macros.at])
 m4_include([tests/ofproto-macros.at])
 
 m4_include([tests/library.at])
+m4_include([tests/bundle.at])
 m4_include([tests/classifier.at])
 m4_include([tests/check-structs.at])
 m4_include([tests/daemon.at])