tests/test-bundle.c

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