From daff3353a0dcb6db7c1468e442f95ae22d335e88 Mon Sep 17 00:00:00 2001 From: Ethan Jackson Date: Fri, 10 Jun 2011 17:45:45 -0700 Subject: [PATCH] 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. --- include/openflow/nicira-ext.h | 74 +++++++++- lib/automake.mk | 2 + lib/bundle.c | 256 ++++++++++++++++++++++++++++++++++ lib/bundle.h | 49 +++++++ lib/ofp-parse.c | 3 + lib/ofp-print.c | 5 + lib/ofp-util.c | 7 + lib/ofp-util.h | 3 +- ofproto/ofproto-dpif.c | 44 ++++++ tests/.gitignore | 1 + tests/automake.mk | 7 + tests/bundle.at | 123 ++++++++++++++++ tests/ovs-ofctl.at | 8 ++ tests/test-bundle.c | 237 +++++++++++++++++++++++++++++++ tests/testsuite.at | 1 + utilities/ovs-ofctl.8.in | 16 +++ 16 files changed, 834 insertions(+), 2 deletions(-) create mode 100644 lib/bundle.c create mode 100644 lib/bundle.h create mode 100644 tests/bundle.at create mode 100644 tests/test-bundle.c diff --git a/include/openflow/nicira-ext.h b/include/openflow/nicira-ext.h index 006d27de..960b53fe 100644 --- a/include/openflow/nicira-ext.h +++ b/include/openflow/nicira-ext.h @@ -277,7 +277,8 @@ enum nx_action_subtype { NXAST_NOTE, /* struct nx_action_note */ NXAST_SET_TUNNEL64, /* struct nx_action_set_tunnel64 */ NXAST_MULTIPATH, /* struct nx_action_multipath */ - NXAST_AUTOPATH /* struct nx_action_autopath */ + NXAST_AUTOPATH, /* struct nx_action_autopath */ + NXAST_BUNDLE /* struct nx_action_bundle */ }; /* Header for Nicira-defined actions. */ @@ -665,6 +666,77 @@ struct nx_action_autopath { }; OFP_ASSERT(sizeof(struct nx_action_autopath) == 24); +/* Action structure for NXAST_BUNDLE. + * + * NXAST_BUNDLE chooses a slave from a supplied list of options, and outputs to + * its selection. + * + * The list of possible slaves follows the nx_action_bundle structure. The size + * of each slave is governed by its type as indicated by the 'slave_type' + * parameter. The list of slaves should be padded at its end with zeros to make + * the total length of the action a multiple of 8. + * + * Switches infer from the 'slave_type' parameter the size of each slave. All + * implementations must support the NXM_OF_IN_PORT 'slave_type' which indicates + * that the slaves are OpenFlow port numbers with NXM_LENGTH(NXM_OF_IN_PORT) == + * 2 byte width. Switches should reject actions which indicate unknown or + * unsupported slave types. + * + * Switches use a strategy dictated by the 'algorithm' parameter to choose a + * slave. If the switch does not support the specified 'algorithm' parameter, + * it should reject the action. + * + * Some slave selection strategies require the use of a hash function, in which + * case the 'fields' and 'basis' parameters should be populated. The 'fields' + * parameter (one of NX_HASH_FIELDS_*) designates which parts of the flow to + * hash. Refer to the definition of "enum nx_hash_fields" for details. The + * 'basis' parameter is used as a universal hash parameter. Different values + * of 'basis' yield different hash results. + * + * The 'zero' parameter at the end of the action structure is reserved for + * future use. Switches are required to reject actions which have nonzero + * bytes in the 'zero' field. */ +struct nx_action_bundle { + ovs_be16 type; /* OFPAT_VENDOR. */ + ovs_be16 len; /* Length including slaves. */ + ovs_be32 vendor; /* NX_VENDOR_ID. */ + ovs_be16 subtype; /* NXAST_BUNDLE. */ + + /* Slave choice algorithm to apply to hash value. */ + ovs_be16 algorithm; /* One of NX_BD_ALG_*. */ + + /* What fields to hash and how. */ + ovs_be16 fields; /* One of NX_BD_FIELDS_*. */ + ovs_be16 basis; /* Universal hash parameter. */ + + ovs_be32 slave_type; /* NXM_OF_IN_PORT. */ + ovs_be16 n_slaves; /* Number of slaves. */ + + uint8_t zero[10]; /* Reserved. Must be zero. */ +}; +OFP_ASSERT(sizeof(struct nx_action_bundle) == 32); + +/* NXAST_BUNDLE: Bundle slave choice algorithm to apply. + * + * In the descriptions below, 'slaves' is the list of possible slaves in the + * order they appear in the OpenFlow action. */ +enum nx_bd_algorithm { + /* Chooses the first live slave listed in the bundle. + * + * O(n_slaves) performance. */ + NX_BD_ALG_ACTIVE_BACKUP, + + /* for i in [0,n_slaves): + * weights[i] = hash(flow, i) + * slave = { slaves[i] such that weights[i] >= weights[j] for all j != i } + * + * Redistributes 1/n_slaves of traffic when a slave's liveness changes. + * O(n_slaves) performance. + * + * Uses the 'fields' and 'basis' parameters. */ + NX_BD_ALG_HRW /* Highest Random Weight. */ +}; + /* Flexible flow specifications (aka NXM = Nicira Extended Match). * * OpenFlow 1.0 has "struct ofp_match" for specifying flow matches. This diff --git a/lib/automake.mk b/lib/automake.mk index e3d7c3f6..8d93c7a1 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -18,6 +18,8 @@ lib_libopenvswitch_a_SOURCES = \ lib/bitmap.h \ lib/bond.c \ lib/bond.h \ + lib/bundle.c \ + lib/bundle.h \ lib/byte-order.h \ lib/byteq.c \ lib/byteq.h \ diff --git a/lib/bundle.c b/lib/bundle.c new file mode 100644 index 00000000..0b0e3617 --- /dev/null +++ b/lib/bundle.c @@ -0,0 +1,256 @@ +/* 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 + +#include "bundle.h" + +#include +#include + +#include "dynamic-string.h" +#include "multipath.h" +#include "nx-match.h" +#include "ofpbuf.h" +#include "ofp-util.h" +#include "openflow/nicira-ext.h" +#include "vlog.h" + +#define BUNDLE_MAX_SLAVES 2048 + +VLOG_DEFINE_THIS_MODULE(bundle); + +/* Executes 'nab' on 'flow'. Uses 'slave_enabled' to determine if the slave + * designated by 'ofp_port' is up. Returns the chosen slave, or OFPP_NONE if + * none of the slaves are acceptable. */ +uint16_t +bundle_execute(const struct nx_action_bundle *nab, const struct flow *flow, + bool (*slave_enabled)(uint16_t ofp_port, void *aux), void *aux) +{ + uint32_t flow_hash, best_hash; + int best, i; + + assert(nab->algorithm == htons(NX_BD_ALG_HRW)); + + flow_hash = flow_hash_fields(flow, ntohs(nab->fields), ntohs(nab->basis)); + best = -1; + + for (i = 0; i < ntohs(nab->n_slaves); i++) { + if (slave_enabled(bundle_get_slave(nab, i), aux)) { + uint32_t hash = hash_2words(i, flow_hash); + + if (best < 0 || hash > best_hash) { + best_hash = hash; + best = i; + } + } + } + + return best >= 0 ? bundle_get_slave(nab, best) : OFPP_NONE; +} + +/* Checks that 'nab' specifies a bundle action which is supported by this + * bundle module. Uses the 'max_ports' parameter to validate each port using + * ofputil_check_output_port(). Returns 0 if 'nab' is supported, otherwise an + * OpenFlow error code (as returned by ofp_mkerr()). */ +int +bundle_check(const struct nx_action_bundle *nab, int max_ports) +{ + static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5); + uint16_t n_slaves, fields, algorithm, slave_type, subtype; + size_t slaves_size, i; + int error; + + subtype = ntohs(nab->subtype); + n_slaves = ntohs(nab->n_slaves); + fields = ntohs(nab->fields); + algorithm = ntohs(nab->algorithm); + slave_type = ntohs(nab->slave_type); + slaves_size = ntohs(nab->len) - sizeof *nab; + + error = ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_ARGUMENT); + if (!flow_hash_fields_valid(fields)) { + VLOG_WARN_RL(&rl, "unsupported fields %"PRIu16, fields); + } else if (n_slaves > BUNDLE_MAX_SLAVES) { + VLOG_WARN_RL(&rl, "too may slaves"); + } else if (algorithm != NX_BD_ALG_HRW) { + VLOG_WARN_RL(&rl, "unsupported algorithm %"PRIu16, algorithm); + } else if (slave_type != NXM_OF_IN_PORT) { + VLOG_WARN_RL(&rl, "unsupported slave type %"PRIu16, slave_type); + } else { + error = 0; + } + + for (i = 0; i < sizeof(nab->zero); i++) { + if (nab->zero[i]) { + VLOG_WARN_RL(&rl, "reserved field is nonzero"); + error = ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_ARGUMENT); + } + } + + if (slaves_size < n_slaves * sizeof(ovs_be16)) { + VLOG_WARN_RL(&rl, "Nicira action %"PRIu16" only has %zu bytes " + "allocated for slaves. %zu bytes are required for " + "%"PRIu16" slaves.", subtype, slaves_size, + n_slaves * sizeof(ovs_be16), n_slaves); + error = ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_LEN); + } + + for (i = 0; i < n_slaves; i++) { + uint16_t ofp_port = bundle_get_slave(nab, i); + int ofputil_error = ofputil_check_output_port(ofp_port, max_ports); + + if (ofputil_error) { + VLOG_WARN_RL(&rl, "invalid slave %"PRIu16, ofp_port); + error = ofputil_error; + } + + /* Controller slaves are unsupported due to the lack of a max_len + * argument. This may or may not change in the future. There doesn't + * seem to be a real-world use-case for supporting it. */ + if (ofp_port == OFPP_CONTROLLER) { + VLOG_WARN_RL(&rl, "unsupported controller slave"); + error = ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_OUT_PORT); + } + } + + return error; +} + +/* Converts a bundle action string contained in 's' to an nx_action_bundle and + * stores it in 'b'. Sets 'b''s l2 pointer to NULL. */ +void +bundle_parse(struct ofpbuf *b, const char *s) +{ + char *fields, *basis, *algorithm, *slave_type, *slave_delim; + struct nx_action_bundle *nab; + char *tokstr, *save_ptr; + uint16_t n_slaves; + + save_ptr = NULL; + tokstr = xstrdup(s); + fields = strtok_r(tokstr, ", ", &save_ptr); + basis = strtok_r(NULL, ", ", &save_ptr); + algorithm = strtok_r(NULL, ", ", &save_ptr); + slave_type = strtok_r(NULL, ", ", &save_ptr); + slave_delim = strtok_r(NULL, ": ", &save_ptr); + + if (!slave_delim) { + ovs_fatal(0, "%s: not enough arguments to bundle action", s); + } + + if (strcasecmp(slave_delim, "slaves")) { + ovs_fatal(0, "%s: missing slave delimiter, expected `slaves' got `%s'", + s, slave_delim); + } + + b->l2 = ofpbuf_put_zeros(b, sizeof *nab); + + n_slaves = 0; + for (;;) { + ovs_be16 slave_be; + char *slave; + + slave = strtok_r(NULL, ", ", &save_ptr); + if (!slave || n_slaves >= BUNDLE_MAX_SLAVES) { + break; + } + + slave_be = htons(atoi(slave)); + ofpbuf_put(b, &slave_be, sizeof slave_be); + + n_slaves++; + } + + /* Slaves array must be multiple of 8 bytes long. */ + if (b->size % 8) { + ofpbuf_put_zeros(b, 8 - (b->size % 8)); + } + + nab = b->l2; + nab->type = htons(OFPAT_VENDOR); + nab->len = htons(b->size - ((char *) b->l2 - (char *) b->data)); + nab->vendor = htonl(NX_VENDOR_ID); + nab->subtype = htons(NXAST_BUNDLE); + nab->n_slaves = htons(n_slaves); + nab->basis = htons(atoi(basis)); + + if (!strcasecmp(fields, "eth_src")) { + nab->fields = htons(NX_HASH_FIELDS_ETH_SRC); + } else if (!strcasecmp(fields, "symmetric_l4")) { + nab->fields = htons(NX_HASH_FIELDS_SYMMETRIC_L4); + } else { + ovs_fatal(0, "%s: unknown fields `%s'", s, fields); + } + + if (!strcasecmp(algorithm, "active_backup")) { + nab->algorithm = htons(NX_BD_ALG_ACTIVE_BACKUP); + } else if (!strcasecmp(algorithm, "hrw")) { + nab->algorithm = htons(NX_BD_ALG_HRW); + } else { + ovs_fatal(0, "%s: unknown algorithm `%s'", s, algorithm); + } + + if (!strcasecmp(slave_type, "ofport")) { + nab->slave_type = htons(NXM_OF_IN_PORT); + } else { + ovs_fatal(0, "%s: unknown slave_type `%s'", s, slave_type); + } + + b->l2 = NULL; + free(tokstr); +} + +/* Appends a human-readable representation of 'nab' to 's'. */ +void +bundle_format(const struct nx_action_bundle *nab, struct ds *s) +{ + const char *fields, *algorithm, *slave_type; + size_t i; + + fields = flow_hash_fields_to_str(ntohs(nab->fields)); + + switch (ntohs(nab->algorithm)) { + case NX_BD_ALG_HRW: + algorithm = "hrw"; + break; + case NX_BD_ALG_ACTIVE_BACKUP: + algorithm = "active_backup"; + break; + default: + algorithm = ""; + } + + switch (ntohs(nab->slave_type)) { + case NXM_OF_IN_PORT: + slave_type = "ofport"; + break; + default: + slave_type = ""; + } + + ds_put_format(s, "bundle(%s,%"PRIu16",%s,%s,slaves:", fields, + ntohs(nab->basis), algorithm, slave_type); + + for (i = 0; i < ntohs(nab->n_slaves); i++) { + if (i) { + ds_put_cstr(s, ","); + } + + ds_put_format(s, "%"PRIu16, bundle_get_slave(nab, i)); + } + + ds_put_cstr(s, ")"); +} diff --git a/lib/bundle.h b/lib/bundle.h new file mode 100644 index 00000000..a202ade4 --- /dev/null +++ b/lib/bundle.h @@ -0,0 +1,49 @@ +/* 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. + */ + +#ifndef BUNDLE_H +#define BUNDLE_H 1 + +#include +#include +#include +#include + +#include "openflow/nicira-ext.h" +#include "openvswitch/types.h" + +struct ds; +struct flow; +struct ofpbuf; + +/* NXAST_BUNDLE helper functions. + * + * See include/openflow/nicira-ext.h for NXAST_BUNDLE specification. */ + +uint16_t bundle_execute(const struct nx_action_bundle *, const struct flow *, + bool (*slave_enabled)(uint16_t ofp_port, void *aux), + void *aux); +int bundle_check(const struct nx_action_bundle *, int max_ports); +void bundle_parse(struct ofpbuf *, const char *); +void bundle_format(const struct nx_action_bundle *, struct ds *); + +/* Returns the 'i'th slave in 'nab'. */ +static inline uint16_t +bundle_get_slave(const struct nx_action_bundle *nab, size_t i) +{ + return ntohs(((ovs_be16 *)(nab + 1))[i]); +} + +#endif /* bundle.h */ diff --git a/lib/ofp-parse.c b/lib/ofp-parse.c index 5bc04845..25056e7f 100644 --- a/lib/ofp-parse.c +++ b/lib/ofp-parse.c @@ -23,6 +23,7 @@ #include #include "autopath.h" +#include "bundle.h" #include "byte-order.h" #include "dynamic-string.h" #include "netdev.h" @@ -504,6 +505,8 @@ str_to_action(char *str, struct ofpbuf *b) struct nx_action_autopath *naa; naa = ofpbuf_put_uninit(b, sizeof *naa); autopath_parse(naa, arg); + } else if (!strcasecmp(act, "bundle")) { + bundle_parse(b, arg); } else if (!strcasecmp(act, "output")) { put_output_action(b, str_to_u32(arg)); } else if (!strcasecmp(act, "enqueue")) { diff --git a/lib/ofp-print.c b/lib/ofp-print.c index 4f4e33c5..aa3ff542 100644 --- a/lib/ofp-print.c +++ b/lib/ofp-print.c @@ -26,6 +26,7 @@ #include #include +#include "bundle.h" #include "byte-order.h" #include "compiler.h" #include "dynamic-string.h" @@ -342,6 +343,10 @@ ofp_print_action(struct ds *s, const union ofp_action *a, ds_put_char(s, ')'); break; + case OFPUTIL_NXAST_BUNDLE: + bundle_format((const struct nx_action_bundle *) a, s); + break; + default: break; } diff --git a/lib/ofp-util.c b/lib/ofp-util.c index 39bd0d1b..803b0333 100644 --- a/lib/ofp-util.c +++ b/lib/ofp-util.c @@ -21,6 +21,7 @@ #include #include #include "autopath.h" +#include "bundle.h" #include "byte-order.h" #include "classifier.h" #include "dynamic-string.h" @@ -2035,6 +2036,11 @@ validate_actions(const union ofp_action *actions, size_t n_actions, error = autopath_check((const struct nx_action_autopath *) a); break; + case OFPUTIL_NXAST_BUNDLE: + error = bundle_check((const struct nx_action_bundle *) a, + max_ports); + break; + case OFPUTIL_OFPAT_STRIP_VLAN: case OFPUTIL_OFPAT_SET_NW_SRC: case OFPUTIL_OFPAT_SET_NW_DST: @@ -2107,6 +2113,7 @@ static const struct ofputil_nxast_action nxast_actions[] = { { OFPUTIL_NXAST_SET_TUNNEL64, 24, 24 }, { OFPUTIL_NXAST_MULTIPATH, 32, 32 }, { OFPUTIL_NXAST_AUTOPATH, 24, 24 }, + { OFPUTIL_NXAST_BUNDLE, 32, UINT_MAX }, }; static int diff --git a/lib/ofp-util.h b/lib/ofp-util.h index adad087d..7938aa0c 100644 --- a/lib/ofp-util.h +++ b/lib/ofp-util.h @@ -301,7 +301,8 @@ enum ofputil_action_code { OFPUTIL_NXAST_NOTE, OFPUTIL_NXAST_SET_TUNNEL64, OFPUTIL_NXAST_MULTIPATH, - OFPUTIL_NXAST_AUTOPATH + OFPUTIL_NXAST_AUTOPATH, + OFPUTIL_NXAST_BUNDLE }; int ofputil_decode_action(const union ofp_action *); diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c index 42138b99..e50d72b6 100644 --- a/ofproto/ofproto-dpif.c +++ b/ofproto/ofproto-dpif.c @@ -22,6 +22,7 @@ #include "autopath.h" #include "bond.h" +#include "bundle.h" #include "byte-order.h" #include "connmgr.h" #include "coverage.h" @@ -332,6 +333,8 @@ struct ofproto_dpif { /* Support for debugging async flow mods. */ struct list completions; + + bool has_bundle_action; /* True when the first bundle action appears. */ }; /* Defer flow mod completion until "ovs-appctl ofproto/unclog"? (Useful only @@ -467,6 +470,8 @@ construct(struct ofproto *ofproto_) ofproto_dpif_unixctl_init(); + ofproto->has_bundle_action = false; + return 0; } @@ -1436,6 +1441,14 @@ port_run(struct ofport_dpif *ofport) enable = enable && lacp_slave_may_enable(ofport->bundle->lacp, ofport); } + if (ofport->may_enable != enable) { + struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto); + + if (ofproto->has_bundle_action) { + ofproto->need_revalidate = true; + } + } + ofport->may_enable = enable; } @@ -3047,6 +3060,28 @@ xlate_autopath(struct action_xlate_ctx *ctx, autopath_execute(naa, &ctx->flow, ofp_port); } +static bool +slave_enabled_cb(uint16_t ofp_port, void *ofproto_) +{ + struct ofproto_dpif *ofproto = ofproto_; + struct ofport_dpif *port; + + switch (ofp_port) { + case OFPP_IN_PORT: + case OFPP_TABLE: + case OFPP_NORMAL: + case OFPP_FLOOD: + case OFPP_ALL: + case OFPP_LOCAL: + return true; + case OFPP_CONTROLLER: /* Not supported by the bundle action. */ + return false; + default: + port = get_ofp_port(ofproto, ofp_port); + return port ? port->may_enable : false; + } +} + static void do_xlate_actions(const union ofp_action *in, size_t n_in, struct action_xlate_ctx *ctx) @@ -3072,6 +3107,7 @@ do_xlate_actions(const union ofp_action *in, size_t n_in, const struct nx_action_set_queue *nasq; const struct nx_action_multipath *nam; const struct nx_action_autopath *naa; + const struct nx_action_bundle *nab; enum ofputil_action_code code; ovs_be64 tun_id; @@ -3178,6 +3214,14 @@ do_xlate_actions(const union ofp_action *in, size_t n_in, naa = (const struct nx_action_autopath *) ia; xlate_autopath(ctx, naa); break; + + case OFPUTIL_NXAST_BUNDLE: + ctx->ofproto->has_bundle_action = true; + nab = (const struct nx_action_bundle *) ia; + xlate_output_action__(ctx, bundle_execute(nab, &ctx->flow, + slave_enabled_cb, + ctx->ofproto), 0); + break; } } } diff --git a/tests/.gitignore b/tests/.gitignore index e2b293c4..e945a850 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 750f420d..be09b4a6 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 00000000..063cdd31 --- /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 9e347cff..63292dbb 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 00000000..8a892925 --- /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 + +#include "bundle.h" + +#include +#include + +#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 28678932..6ec77f8c 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]) diff --git a/utilities/ovs-ofctl.8.in b/utilities/ovs-ofctl.8.in index 9e96a2b3..85723029 100644 --- a/utilities/ovs-ofctl.8.in +++ b/utilities/ovs-ofctl.8.in @@ -727,6 +727,22 @@ the normal bond selection logic will be used to choose the destination port. Otherwise, the register will be populated with \fIid\fR itself. .IP Refer to \fBnicira\-ext.h\fR for more details. +. +.IP "\fBbundle(\fIfields\fB, \fIbasis\fB, \fIalgorithm\fB, \fIslave_type\fB, slaves:[\fIs1\fB, \fIs2\fB, ...])\fR" +Hashes \fIfields\fR using \fIbasis\fR as a universal hash parameter, then +applies the bundle link selection \fIalgorithm\fR to choose one of the listed +slaves represented as \fIslave_type\fR. Currently the only supported +\fIslave_type\fR is \fBofport\fR. Thus, each \fIs1\fR through \fIsN\fR should +be an OpenFlow port number. Outputs to the selected slave. +.IP +Currently, \fIfields\fR must be either \fBeth_src\fR or \fBsymmetric_l4\fR and +\fIalgorithm\fR must be one of \fBhrw\fR and \fBactive_backup\fR. +.IP +Example: \fBbundle(eth_src,0,hrw,ofport,slaves:4,8)\fR uses an Ethernet source +hash with basis 0, to select between OpenFlow ports 4 and 8 using the Highest +Random Weight algorithm. +.IP +Refer to \fBnicira\-ext.h\fR for more details. .RE . .IP -- 2.30.2