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