ofproto: Add extra comments and checking for expiring a pending rule.
[openvswitch] / 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         flows[i].regs[0] = OFPP_NONE;
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     old_active = -1;
148     n_permute = 1 << sg.n_slaves;
149     for (i = 1; i <= n_permute + 1; i++) {
150         struct slave *slave;
151         size_t j, n_enabled, changed;
152         double disruption, perfect;
153         uint8_t mask;
154         int active;
155
156         mask = i % n_permute;
157
158         /* Gray coding ensures that in each iteration exactly one slave
159          * changes its liveness.  This makes the expected disruption a bit
160          * easier to calculate, and is likely similar to how failures will be
161          * experienced in the wild. */
162         mask = mask ^ (mask >> 1);
163
164         /* Initialize slaves. */
165         n_enabled = 0;
166         for (j = 0; j < sg.n_slaves; j++) {
167             slave = &sg.slaves[j];
168             slave->flow_count = 0;
169             slave->enabled = ((1 << j) & mask) != 0;
170
171             if (slave->enabled) {
172                 n_enabled++;
173             }
174         }
175
176         active = -1;
177         for (j = 0; j < sg.n_slaves; j++) {
178             if (sg.slaves[j].enabled) {
179                 active = j;
180                 break;
181             }
182         }
183
184         changed = 0;
185         for (j = 0; j < N_FLOWS; j++) {
186             struct flow *flow = &flows[j];
187             uint16_t old_slave_id, ofp_port;
188
189             old_slave_id = flow->regs[0];
190             ofp_port = bundle_execute(bundle, flow, slave_enabled_cb, &sg);
191             flow->regs[0] = ofp_port;
192
193             if (ofp_port != OFPP_NONE) {
194                 slave_lookup(&sg, ofp_port)->flow_count++;
195             }
196
197             if (old_slave_id != ofp_port) {
198                 changed++;
199             }
200         }
201
202         if (bundle->algorithm == NX_BD_ALG_ACTIVE_BACKUP) {
203             perfect = active == old_active ? 0.0 : 1.0;
204         } else {
205             if (old_n_enabled || n_enabled) {
206                 perfect = 1.0 / MAX(old_n_enabled, n_enabled);
207             } else {
208                 /* This will happen when 'sg.n_slaves' is 0. */
209                 perfect = 0;
210             }
211         }
212
213         disruption = changed / (double)N_FLOWS;
214         printf("%s: disruption=%.2f (perfect=%.2f)",
215                mask_str(mask, sg.n_slaves), disruption, perfect);
216
217         for (j = 0 ; j < sg.n_slaves; j++) {
218             struct slave *slave = &sg.slaves[j];
219             double flow_percent;
220
221             flow_percent = slave->flow_count / (double)N_FLOWS;
222             printf( " %.2f", flow_percent);
223
224             if (slave->enabled) {
225                 double perfect_fp;
226
227                 if (bundle->algorithm == NX_BD_ALG_ACTIVE_BACKUP) {
228                     perfect_fp = j == active ? 1.0 : 0.0;
229                 } else {
230                     perfect_fp = 1.0 / n_enabled;
231                 }
232
233                 if (fabs(flow_percent - perfect_fp) >= .01) {
234                     fprintf(stderr, "%s: slave %d: flow_percentage=%.5f for"
235                             " differs from perfect=%.5f by more than .01\n",
236                             mask_str(mask, sg.n_slaves), slave->slave_id,
237                             flow_percent, perfect_fp);
238                     ok = false;
239                 }
240             } else if (slave->flow_count) {
241                 fprintf(stderr, "%s: slave %d: disabled slave received"
242                         " flows.\n", mask_str(mask, sg.n_slaves),
243                         slave->slave_id);
244                 ok = false;
245             }
246         }
247         printf("\n");
248
249         if (fabs(disruption - perfect) >= .01) {
250             fprintf(stderr, "%s: disruption=%.5f differs from perfect=%.5f by"
251                     " more than .01\n", mask_str(mask, sg.n_slaves),
252                     disruption, perfect);
253             ok = false;
254         }
255
256         old_active = active;
257         old_n_enabled = n_enabled;
258     }
259
260     free(bundle);
261     free(flows);
262     return ok ? 0 : 1;
263 }