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