]>
Commit | Line | Data |
---|---|---|
f25d0cf3 | 1 | /* Copyright (c) 2011, 2012 Nicira, Inc. |
daff3353 EJ |
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" | |
f25d0cf3 | 24 | #include "ofp-actions.h" |
daff3353 EJ |
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 | ||
f25d0cf3 | 68 | static struct ofpact_bundle * |
daff3353 EJ |
69 | parse_bundle_actions(char *actions) |
70 | { | |
f25d0cf3 BP |
71 | struct ofpact_bundle *bundle; |
72 | struct ofpbuf ofpacts; | |
73 | struct ofpact *action; | |
daff3353 | 74 | |
f25d0cf3 BP |
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); | |
daff3353 | 80 | |
f25d0cf3 | 81 | if (bundle->n_slaves > MAX_SLAVES) { |
daff3353 EJ |
82 | ovs_fatal(0, "At most %u slaves are supported", MAX_SLAVES); |
83 | } | |
84 | ||
f25d0cf3 | 85 | return bundle; |
daff3353 EJ |
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; | |
f25d0cf3 | 107 | struct ofpact_bundle *bundle; |
daff3353 EJ |
108 | struct flow *flows; |
109 | size_t i, n_permute, old_n_enabled; | |
110 | struct slave_group sg; | |
04a85497 | 111 | int old_active; |
daff3353 EJ |
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 | ||
f25d0cf3 | 120 | bundle = parse_bundle_actions(argv[1]); |
daff3353 EJ |
121 | |
122 | /* Generate 'slaves' array. */ | |
123 | sg.n_slaves = 0; | |
f25d0cf3 BP |
124 | for (i = 0; i < bundle->n_slaves; i++) { |
125 | uint16_t slave_id = bundle->slaves[i]; | |
daff3353 EJ |
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]); | |
3b21e387 | 139 | memset(flows[i].zeros, 0, sizeof flows[i].zeros); |
b02475c5 | 140 | flows[i].mpls_depth = 0; |
daff3353 EJ |
141 | flows[i].regs[0] = OFPP_NONE; |
142 | } | |
143 | ||
144 | /* Cycles through each possible liveness permutation for the given | |
145 | * n_slaves. The initial state is equivalent to all slaves down, so we | |
146 | * skip it by starting at i = 1. We do one extra iteration to cover | |
147 | * transitioning from the final state back to the initial state. */ | |
148 | old_n_enabled = 0; | |
04a85497 | 149 | old_active = -1; |
daff3353 EJ |
150 | n_permute = 1 << sg.n_slaves; |
151 | for (i = 1; i <= n_permute + 1; i++) { | |
152 | struct slave *slave; | |
153 | size_t j, n_enabled, changed; | |
154 | double disruption, perfect; | |
155 | uint8_t mask; | |
04a85497 | 156 | int active; |
daff3353 EJ |
157 | |
158 | mask = i % n_permute; | |
159 | ||
160 | /* Gray coding ensures that in each iteration exactly one slave | |
161 | * changes its liveness. This makes the expected disruption a bit | |
162 | * easier to calculate, and is likely similar to how failures will be | |
163 | * experienced in the wild. */ | |
164 | mask = mask ^ (mask >> 1); | |
165 | ||
166 | /* Initialize slaves. */ | |
167 | n_enabled = 0; | |
168 | for (j = 0; j < sg.n_slaves; j++) { | |
169 | slave = &sg.slaves[j]; | |
170 | slave->flow_count = 0; | |
171 | slave->enabled = ((1 << j) & mask) != 0; | |
172 | ||
173 | if (slave->enabled) { | |
174 | n_enabled++; | |
175 | } | |
176 | } | |
177 | ||
04a85497 EJ |
178 | active = -1; |
179 | for (j = 0; j < sg.n_slaves; j++) { | |
180 | if (sg.slaves[j].enabled) { | |
181 | active = j; | |
182 | break; | |
183 | } | |
184 | } | |
185 | ||
daff3353 EJ |
186 | changed = 0; |
187 | for (j = 0; j < N_FLOWS; j++) { | |
188 | struct flow *flow = &flows[j]; | |
a368bb53 | 189 | uint16_t old_slave_id, ofp_port; |
bcd2633a | 190 | struct flow_wildcards wc; |
daff3353 EJ |
191 | |
192 | old_slave_id = flow->regs[0]; | |
bcd2633a JP |
193 | ofp_port = bundle_execute(bundle, flow, &wc, slave_enabled_cb, |
194 | &sg); | |
f25d0cf3 | 195 | flow->regs[0] = ofp_port; |
daff3353 | 196 | |
f25d0cf3 BP |
197 | if (ofp_port != OFPP_NONE) { |
198 | slave_lookup(&sg, ofp_port)->flow_count++; | |
daff3353 EJ |
199 | } |
200 | ||
f25d0cf3 | 201 | if (old_slave_id != ofp_port) { |
daff3353 EJ |
202 | changed++; |
203 | } | |
204 | } | |
205 | ||
f25d0cf3 | 206 | if (bundle->algorithm == NX_BD_ALG_ACTIVE_BACKUP) { |
04a85497 | 207 | perfect = active == old_active ? 0.0 : 1.0; |
daff3353 | 208 | } else { |
04a85497 EJ |
209 | if (old_n_enabled || n_enabled) { |
210 | perfect = 1.0 / MAX(old_n_enabled, n_enabled); | |
211 | } else { | |
212 | /* This will happen when 'sg.n_slaves' is 0. */ | |
213 | perfect = 0; | |
214 | } | |
daff3353 EJ |
215 | } |
216 | ||
217 | disruption = changed / (double)N_FLOWS; | |
04a85497 | 218 | printf("%s: disruption=%.2f (perfect=%.2f)", |
daff3353 EJ |
219 | mask_str(mask, sg.n_slaves), disruption, perfect); |
220 | ||
221 | for (j = 0 ; j < sg.n_slaves; j++) { | |
222 | struct slave *slave = &sg.slaves[j]; | |
223 | double flow_percent; | |
224 | ||
225 | flow_percent = slave->flow_count / (double)N_FLOWS; | |
04a85497 | 226 | printf( " %.2f", flow_percent); |
daff3353 EJ |
227 | |
228 | if (slave->enabled) { | |
04a85497 EJ |
229 | double perfect_fp; |
230 | ||
f25d0cf3 | 231 | if (bundle->algorithm == NX_BD_ALG_ACTIVE_BACKUP) { |
04a85497 EJ |
232 | perfect_fp = j == active ? 1.0 : 0.0; |
233 | } else { | |
234 | perfect_fp = 1.0 / n_enabled; | |
235 | } | |
daff3353 EJ |
236 | |
237 | if (fabs(flow_percent - perfect_fp) >= .01) { | |
238 | fprintf(stderr, "%s: slave %d: flow_percentage=%.5f for" | |
239 | " differs from perfect=%.5f by more than .01\n", | |
240 | mask_str(mask, sg.n_slaves), slave->slave_id, | |
241 | flow_percent, perfect_fp); | |
242 | ok = false; | |
243 | } | |
244 | } else if (slave->flow_count) { | |
245 | fprintf(stderr, "%s: slave %d: disabled slave received" | |
246 | " flows.\n", mask_str(mask, sg.n_slaves), | |
247 | slave->slave_id); | |
248 | ok = false; | |
249 | } | |
250 | } | |
251 | printf("\n"); | |
252 | ||
253 | if (fabs(disruption - perfect) >= .01) { | |
254 | fprintf(stderr, "%s: disruption=%.5f differs from perfect=%.5f by" | |
255 | " more than .01\n", mask_str(mask, sg.n_slaves), | |
256 | disruption, perfect); | |
257 | ok = false; | |
258 | } | |
259 | ||
04a85497 | 260 | old_active = active; |
daff3353 EJ |
261 | old_n_enabled = n_enabled; |
262 | } | |
263 | ||
f25d0cf3 | 264 | free(bundle); |
daff3353 EJ |
265 | free(flows); |
266 | return ok ? 0 : 1; | |
267 | } |