tests/test-bundle.c

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