tests/test-bundle.c

   1 /* Copyright (c) 2011, 2012, 2013, 2014, 2017 Nicira, Inc.
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <config.h>
  17 #undef NDEBUG
  18 #include <math.h>
  19 #include <stdlib.h>
  20 #include "bundle.h"
  21 #include "flow.h"
  22 #include "openvswitch/ofp-actions.h"
  23 #include "openvswitch/ofpbuf.h"
  24 #include "ovstest.h"
  25 #include "util.h"
  26
  27 #define N_FLOWS  50000
  28 #define MAX_MEMBERS 8 /* Maximum supported by this test framework. */
  29
  30 struct member {
  31     ofp_port_t member_id;
  32
  33     bool enabled;
  34     size_t flow_count;
  35 };
  36
  37 struct member_group {
  38     size_t n_members;
  39     struct member members[MAX_MEMBERS];
  40 };
  41
  42 static struct member *
  43 member_lookup(struct member_group *sg, ofp_port_t member_id)
  44 {
  45     size_t i;
  46
  47     for (i = 0; i < sg->n_members; i++) {
  48         if (sg->members[i].member_id == member_id) {
  49             return &sg->members[i];
  50         }
  51     }
  52
  53     return NULL;
  54 }
  55
  56 static bool
  57 member_enabled_cb(ofp_port_t member_id, void *aux)
  58 {
  59     struct member *member;
  60
  61     member = member_lookup(aux, member_id);
  62     return member ? member->enabled : false;
  63 }
  64
  65 static struct ofpact_bundle *
  66 parse_bundle_actions(char *actions)
  67 {
  68     struct ofpact_bundle *bundle;
  69     struct ofpbuf ofpacts;
  70     struct ofpact *action;
  71     char *error;
  72
  73     ofpbuf_init(&ofpacts, 0);
  74     error = bundle_parse_load(actions, NULL, &ofpacts);
  75     if (error) {
  76         ovs_fatal(0, "%s", error);
  77     }
  78
  79     action = ofpacts.data;
  80     bundle = ofpact_get_BUNDLE(xmemdup(action, action->len));
  81     ofpbuf_uninit(&ofpacts);
  82
  83     if (bundle->n_members > MAX_MEMBERS) {
  84         ovs_fatal(0, "At most %u members are supported", MAX_MEMBERS);
  85     }
  86
  87     return bundle;
  88 }
  89
  90 static const char *
  91 mask_str(uint8_t mask, size_t n_bits)
  92 {
  93     static char str[9];
  94     size_t i;
  95
  96     n_bits = MIN(n_bits, 8);
  97     for (i = 0; i < n_bits; i++) {
  98         str[i] = (1 << i) & mask ? '1' : '0';
  99     }
 100     str[i] = '\0';
 101
 102     return str;
 103 }
 104
 105 static void
 106 test_bundle_main(int argc, char *argv[])
 107 {
 108     bool ok = true;
 109     struct ofpact_bundle *bundle;
 110     struct flow *flows;
 111     size_t i, n_permute, old_n_enabled;
 112     struct member_group sg;
 113     int old_active;
 114
 115     set_program_name(argv[0]);
 116
 117     if (argc != 2) {
 118         ovs_fatal(0, "usage: %s bundle_action", program_name);
 119     }
 120
 121     bundle = parse_bundle_actions(argv[1]);
 122
 123     /* Generate 'members' array. */
 124     sg.n_members = 0;
 125     for (i = 0; i < bundle->n_members; i++) {
 126         ofp_port_t member_id = bundle->members[i];
 127
 128         if (member_lookup(&sg, member_id)) {
 129             ovs_fatal(0, "Redundant members are not supported. ");
 130         }
 131
 132         sg.members[sg.n_members].member_id = member_id;
 133         sg.n_members++;
 134     }
 135
 136     /* Generate flows. */
 137     flows = xmalloc(N_FLOWS * sizeof *flows);
 138     for (i = 0; i < N_FLOWS; i++) {
 139         flow_random_hash_fields(&flows[i]);
 140         flows[i].regs[0] = ofp_to_u16(OFPP_NONE);
 141     }
 142
 143     /* Cycles through each possible liveness permutation for the given
 144      * n_members.  The initial state is equivalent to all members down, so we
 145      * skip it by starting at i = 1. We do one extra iteration to cover
 146      * transitioning from the final state back to the initial state. */
 147     old_n_enabled = 0;
 148     old_active = -1;
 149     n_permute = 1 << sg.n_members;
 150     for (i = 1; i <= n_permute + 1; i++) {
 151         struct member *member;
 152         size_t j, n_enabled, changed;
 153         double disruption, perfect;
 154         uint8_t mask;
 155         int active;
 156
 157         mask = i % n_permute;
 158
 159         /* Gray coding ensures that in each iteration exactly one member
 160          * changes its liveness.  This makes the expected disruption a bit
 161          * easier to calculate, and is likely similar to how failures will be
 162          * experienced in the wild. */
 163         mask = mask ^ (mask >> 1);
 164
 165         /* Initialize members. */
 166         n_enabled = 0;
 167         for (j = 0; j < sg.n_members; j++) {
 168             member = &sg.members[j];
 169             member->flow_count = 0;
 170             member->enabled = ((1 << j) & mask) != 0;
 171
 172             if (member->enabled) {
 173                 n_enabled++;
 174             }
 175         }
 176
 177         active = -1;
 178         for (j = 0; j < sg.n_members; j++) {
 179             if (sg.members[j].enabled) {
 180                 active = j;
 181                 break;
 182             }
 183         }
 184
 185         changed = 0;
 186         for (j = 0; j < N_FLOWS; j++) {
 187             struct flow *flow = &flows[j];
 188             ofp_port_t old_member_id, ofp_port;
 189             struct flow_wildcards wc;
 190
 191             old_member_id = u16_to_ofp(flow->regs[0]);
 192             ofp_port = bundle_execute(bundle, flow, &wc, member_enabled_cb,
 193                                       &sg);
 194             flow->regs[0] = ofp_to_u16(ofp_port);
 195
 196             if (ofp_port != OFPP_NONE) {
 197                 member_lookup(&sg, ofp_port)->flow_count++;
 198             }
 199
 200             if (old_member_id != ofp_port) {
 201                 changed++;
 202             }
 203         }
 204
 205         if (bundle->algorithm == NX_BD_ALG_ACTIVE_BACKUP) {
 206             perfect = active == old_active ? 0.0 : 1.0;
 207         } else {
 208             if (old_n_enabled || n_enabled) {
 209                 perfect = 1.0 / MAX(old_n_enabled, n_enabled);
 210             } else {
 211                 /* This will happen when 'sg.n_members' is 0. */
 212                 perfect = 0;
 213             }
 214         }
 215
 216         disruption = changed / (double)N_FLOWS;
 217         printf("%s: disruption=%.2f (perfect=%.2f)",
 218                mask_str(mask, sg.n_members), disruption, perfect);
 219
 220         for (j = 0 ; j < sg.n_members; j++) {
 221             member = &sg.members[j];
 222             double flow_percent;
 223
 224             flow_percent = member->flow_count / (double)N_FLOWS;
 225             printf( " %.2f", flow_percent);
 226
 227             if (member->enabled) {
 228                 double perfect_fp;
 229
 230                 if (bundle->algorithm == NX_BD_ALG_ACTIVE_BACKUP) {
 231                     perfect_fp = j == active ? 1.0 : 0.0;
 232                 } else {
 233                     perfect_fp = 1.0 / n_enabled;
 234                 }
 235
 236                 if (fabs(flow_percent - perfect_fp) >= .01) {
 237                     fprintf(stderr, "%s: member %d: flow_percentage=%.5f for"
 238                             " differs from perfect=%.5f by more than .01\n",
 239                             mask_str(mask, sg.n_members), member->member_id,
 240                             flow_percent, perfect_fp);
 241                     ok = false;
 242                 }
 243             } else if (member->flow_count) {
 244                 fprintf(stderr, "%s: member %d: disabled member received"
 245                         " flows.\n", mask_str(mask, sg.n_members),
 246                         member->member_id);
 247                 ok = false;
 248             }
 249         }
 250         printf("\n");
 251
 252         if (fabs(disruption - perfect) >= .01) {
 253             fprintf(stderr, "%s: disruption=%.5f differs from perfect=%.5f by"
 254                     " more than .01\n", mask_str(mask, sg.n_members),
 255                     disruption, perfect);
 256             ok = false;
 257         }
 258
 259         old_active = active;
 260         old_n_enabled = n_enabled;
 261     }
 262
 263     free(bundle);
 264     free(flows);
 265     exit(ok ? 0 : 1);
 266 }
 267
 268 OVSTEST_REGISTER("test-bundle", test_bundle_main);