vswitch: Implement bundle action.
[openvswitch] / 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     /* Cycles through each possible liveness permutation for the given
139      * n_slaves.  The initial state is equivalent to all slaves down, so we
140      * skip it by starting at i = 1. We do one extra iteration to cover
141      * transitioning from the final state back to the initial state. */
142     old_n_enabled = 0;
143     n_permute = 1 << sg.n_slaves;
144     for (i = 1; i <= n_permute + 1; i++) {
145         struct slave *slave;
146         size_t j, n_enabled, changed;
147         double disruption, perfect;
148         uint8_t mask;
149
150         mask = i % n_permute;
151
152         /* Gray coding ensures that in each iteration exactly one slave
153          * changes its liveness.  This makes the expected disruption a bit
154          * easier to calculate, and is likely similar to how failures will be
155          * experienced in the wild. */
156         mask = mask ^ (mask >> 1);
157
158         /* Initialize slaves. */
159         n_enabled = 0;
160         for (j = 0; j < sg.n_slaves; j++) {
161             slave = &sg.slaves[j];
162             slave->flow_count = 0;
163             slave->enabled = ((1 << j) & mask) != 0;
164
165             if (slave->enabled) {
166                 n_enabled++;
167             }
168         }
169
170         changed = 0;
171         for (j = 0; j < N_FLOWS; j++) {
172             struct flow *flow = &flows[j];
173             uint16_t old_slave_id;
174
175             old_slave_id = flow->regs[0];
176             flow->regs[0] = bundle_execute(nab, flow, slave_enabled_cb, &sg);
177
178             if (flow->regs[0] != OFPP_NONE) {
179                 slave_lookup(&sg, flow->regs[0])->flow_count++;
180             }
181
182             if (old_slave_id != flow->regs[0]) {
183                 changed++;
184             }
185         }
186
187         if (old_n_enabled || n_enabled) {
188             perfect = 1.0 / MAX(old_n_enabled, n_enabled);
189         } else {
190             /* This will happen when 'sg.n_slaves' is 0. */
191             perfect = 0;
192         }
193
194         disruption = changed / (double)N_FLOWS;
195         printf("%s: disruption=%.2f (perfect=%.2f) ",
196                mask_str(mask, sg.n_slaves), disruption, perfect);
197
198         for (j = 0 ; j < sg.n_slaves; j++) {
199             struct slave *slave = &sg.slaves[j];
200             double flow_percent;
201
202             flow_percent = slave->flow_count / (double)N_FLOWS;
203             printf("%.2f ", flow_percent);
204
205             if (slave->enabled) {
206                 double perfect_fp = 1.0 / n_enabled;
207
208                 if (fabs(flow_percent - perfect_fp) >= .01) {
209                     fprintf(stderr, "%s: slave %d: flow_percentage=%.5f for"
210                             " differs from perfect=%.5f by more than .01\n",
211                             mask_str(mask, sg.n_slaves), slave->slave_id,
212                             flow_percent, perfect_fp);
213                     ok = false;
214                 }
215             } else if (slave->flow_count) {
216                 fprintf(stderr, "%s: slave %d: disabled slave received"
217                         " flows.\n", mask_str(mask, sg.n_slaves),
218                         slave->slave_id);
219                 ok = false;
220             }
221         }
222         printf("\n");
223
224         if (fabs(disruption - perfect) >= .01) {
225             fprintf(stderr, "%s: disruption=%.5f differs from perfect=%.5f by"
226                     " more than .01\n", mask_str(mask, sg.n_slaves),
227                     disruption, perfect);
228             ok = false;
229         }
230
231         old_n_enabled = n_enabled;
232     }
233
234     free(nab);
235     free(flows);
236     return ok ? 0 : 1;
237 }