]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
da9cfca6 | 2 | * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
064af421 | 7 | * |
a14bc59f BP |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
064af421 BP |
15 | */ |
16 | ||
17 | /* "White box" tests for classifier. | |
18 | * | |
19 | * With very few exceptions, these tests obtain complete coverage of every | |
20 | * basic block and every branch in the classifier implementation, e.g. a clean | |
21 | * report from "gcov -b". (Covering the exceptions would require finding | |
22 | * collisions in the hash function used for flow data, etc.) | |
23 | * | |
24 | * This test should receive a clean report from "valgrind --leak-check=full": | |
25 | * it frees every heap block that it allocates. | |
26 | */ | |
27 | ||
28 | #include <config.h> | |
38c449e0 | 29 | #undef NDEBUG |
3f636c7e | 30 | #include "classifier.h" |
38c449e0 | 31 | #include <assert.h> |
064af421 BP |
32 | #include <errno.h> |
33 | #include <limits.h> | |
10a24935 | 34 | #include "byte-order.h" |
38c449e0 | 35 | #include "classifier-private.h" |
3223e977 | 36 | #include "command-line.h" |
1add079e | 37 | #include "fatal-signal.h" |
064af421 | 38 | #include "flow.h" |
f4248336 | 39 | #include "openvswitch/ofp-util.h" |
3f636c7e | 40 | #include "ovstest.h" |
1add079e JR |
41 | #include "ovs-atomic.h" |
42 | #include "ovs-thread.h" | |
064af421 | 43 | #include "packets.h" |
b028db44 | 44 | #include "random.h" |
1add079e | 45 | #include "timeval.h" |
c0a56d9f | 46 | #include "unaligned.h" |
38c449e0 | 47 | #include "util.h" |
3d91d909 | 48 | |
3bbe9a1f JR |
49 | static bool versioned = false; |
50 | ||
b5d97350 | 51 | /* Fields in a rule. */ |
efe2037e WT |
52 | #define CLS_FIELDS \ |
53 | /* struct flow all-caps */ \ | |
54 | /* member name name */ \ | |
55 | /* ----------- -------- */ \ | |
56 | CLS_FIELD(tunnel.tun_id, TUN_ID) \ | |
57 | CLS_FIELD(metadata, METADATA) \ | |
58 | CLS_FIELD(nw_src, NW_SRC) \ | |
59 | CLS_FIELD(nw_dst, NW_DST) \ | |
60 | CLS_FIELD(in_port.ofp_port, IN_PORT) \ | |
61 | CLS_FIELD(vlan_tci, VLAN_TCI) \ | |
62 | CLS_FIELD(dl_type, DL_TYPE) \ | |
63 | CLS_FIELD(tp_src, TP_SRC) \ | |
64 | CLS_FIELD(tp_dst, TP_DST) \ | |
65 | CLS_FIELD(dl_src, DL_SRC) \ | |
66 | CLS_FIELD(dl_dst, DL_DST) \ | |
67 | CLS_FIELD(nw_proto, NW_PROTO) \ | |
68 | CLS_FIELD(nw_tos, NW_DSCP) | |
b5d97350 BP |
69 | |
70 | /* Field indexes. | |
71 | * | |
72 | * (These are also indexed into struct classifier's 'tables' array.) */ | |
73 | enum { | |
0bdc4bec | 74 | #define CLS_FIELD(MEMBER, NAME) CLS_F_IDX_##NAME, |
b5d97350 BP |
75 | CLS_FIELDS |
76 | #undef CLS_FIELD | |
77 | CLS_N_FIELDS | |
78 | }; | |
79 | ||
80 | /* Field information. */ | |
81 | struct cls_field { | |
82 | int ofs; /* Offset in struct flow. */ | |
83 | int len; /* Length in bytes. */ | |
b5d97350 BP |
84 | const char *name; /* Name (for debugging). */ |
85 | }; | |
86 | ||
87 | static const struct cls_field cls_fields[CLS_N_FIELDS] = { | |
0bdc4bec | 88 | #define CLS_FIELD(MEMBER, NAME) \ |
b5d97350 BP |
89 | { offsetof(struct flow, MEMBER), \ |
90 | sizeof ((struct flow *)0)->MEMBER, \ | |
b5d97350 BP |
91 | #NAME }, |
92 | CLS_FIELDS | |
93 | #undef CLS_FIELD | |
94 | }; | |
95 | ||
064af421 | 96 | struct test_rule { |
3bbe9a1f | 97 | struct ovs_list list_node; |
064af421 BP |
98 | int aux; /* Auxiliary data. */ |
99 | struct cls_rule cls_rule; /* Classifier rule data. */ | |
100 | }; | |
101 | ||
102 | static struct test_rule * | |
103 | test_rule_from_cls_rule(const struct cls_rule *rule) | |
104 | { | |
105 | return rule ? CONTAINER_OF(rule, struct test_rule, cls_rule) : NULL; | |
106 | } | |
107 | ||
f2f3f5cb BP |
108 | static void |
109 | test_rule_destroy(struct test_rule *rule) | |
110 | { | |
111 | if (rule) { | |
112 | cls_rule_destroy(&rule->cls_rule); | |
113 | free(rule); | |
114 | } | |
115 | } | |
116 | ||
bd53aa17 | 117 | static struct test_rule *make_rule(int wc_fields, int priority, int value_pat); |
48d28ac1 BP |
118 | static void free_rule(struct test_rule *); |
119 | static struct test_rule *clone_rule(const struct test_rule *); | |
120 | ||
064af421 BP |
121 | /* Trivial (linear) classifier. */ |
122 | struct tcls { | |
123 | size_t n_rules; | |
124 | size_t allocated_rules; | |
125 | struct test_rule **rules; | |
126 | }; | |
127 | ||
128 | static void | |
129 | tcls_init(struct tcls *tcls) | |
130 | { | |
131 | tcls->n_rules = 0; | |
132 | tcls->allocated_rules = 0; | |
133 | tcls->rules = NULL; | |
134 | } | |
135 | ||
136 | static void | |
137 | tcls_destroy(struct tcls *tcls) | |
138 | { | |
139 | if (tcls) { | |
140 | size_t i; | |
141 | ||
142 | for (i = 0; i < tcls->n_rules; i++) { | |
f2f3f5cb | 143 | test_rule_destroy(tcls->rules[i]); |
064af421 BP |
144 | } |
145 | free(tcls->rules); | |
146 | } | |
147 | } | |
148 | ||
064af421 BP |
149 | static bool |
150 | tcls_is_empty(const struct tcls *tcls) | |
151 | { | |
152 | return tcls->n_rules == 0; | |
153 | } | |
154 | ||
155 | static struct test_rule * | |
156 | tcls_insert(struct tcls *tcls, const struct test_rule *rule) | |
157 | { | |
158 | size_t i; | |
159 | ||
064af421 BP |
160 | for (i = 0; i < tcls->n_rules; i++) { |
161 | const struct cls_rule *pos = &tcls->rules[i]->cls_rule; | |
193eb874 BP |
162 | if (cls_rule_equal(pos, &rule->cls_rule)) { |
163 | /* Exact match. */ | |
42767cce | 164 | ovsrcu_postpone(free_rule, tcls->rules[i]); |
48d28ac1 | 165 | tcls->rules[i] = clone_rule(rule); |
064af421 | 166 | return tcls->rules[i]; |
af7b73f4 | 167 | } else if (pos->priority < rule->cls_rule.priority) { |
064af421 BP |
168 | break; |
169 | } | |
170 | } | |
171 | ||
172 | if (tcls->n_rules >= tcls->allocated_rules) { | |
173 | tcls->rules = x2nrealloc(tcls->rules, &tcls->allocated_rules, | |
174 | sizeof *tcls->rules); | |
175 | } | |
176 | if (i != tcls->n_rules) { | |
177 | memmove(&tcls->rules[i + 1], &tcls->rules[i], | |
178 | sizeof *tcls->rules * (tcls->n_rules - i)); | |
179 | } | |
48d28ac1 | 180 | tcls->rules[i] = clone_rule(rule); |
064af421 BP |
181 | tcls->n_rules++; |
182 | return tcls->rules[i]; | |
183 | } | |
184 | ||
185 | static void | |
186 | tcls_remove(struct tcls *cls, const struct test_rule *rule) | |
187 | { | |
188 | size_t i; | |
189 | ||
190 | for (i = 0; i < cls->n_rules; i++) { | |
191 | struct test_rule *pos = cls->rules[i]; | |
192 | if (pos == rule) { | |
f2f3f5cb BP |
193 | test_rule_destroy(pos); |
194 | ||
064af421 BP |
195 | memmove(&cls->rules[i], &cls->rules[i + 1], |
196 | sizeof *cls->rules * (cls->n_rules - i - 1)); | |
f2f3f5cb | 197 | |
064af421 BP |
198 | cls->n_rules--; |
199 | return; | |
200 | } | |
201 | } | |
428b2edd | 202 | OVS_NOT_REACHED(); |
064af421 BP |
203 | } |
204 | ||
064af421 | 205 | static bool |
5cb7a798 | 206 | match(const struct cls_rule *wild_, const struct flow *fixed) |
064af421 | 207 | { |
5cb7a798 | 208 | struct match wild; |
064af421 BP |
209 | int f_idx; |
210 | ||
5cb7a798 | 211 | minimatch_expand(&wild_->match, &wild); |
064af421 | 212 | for (f_idx = 0; f_idx < CLS_N_FIELDS; f_idx++) { |
d8ae4d67 BP |
213 | bool eq; |
214 | ||
0bdc4bec | 215 | if (f_idx == CLS_F_IDX_NW_SRC) { |
5cb7a798 BP |
216 | eq = !((fixed->nw_src ^ wild.flow.nw_src) |
217 | & wild.wc.masks.nw_src); | |
d8ae4d67 | 218 | } else if (f_idx == CLS_F_IDX_NW_DST) { |
5cb7a798 BP |
219 | eq = !((fixed->nw_dst ^ wild.flow.nw_dst) |
220 | & wild.wc.masks.nw_dst); | |
73f33563 | 221 | } else if (f_idx == CLS_F_IDX_TP_SRC) { |
5cb7a798 BP |
222 | eq = !((fixed->tp_src ^ wild.flow.tp_src) |
223 | & wild.wc.masks.tp_src); | |
73f33563 | 224 | } else if (f_idx == CLS_F_IDX_TP_DST) { |
5cb7a798 BP |
225 | eq = !((fixed->tp_dst ^ wild.flow.tp_dst) |
226 | & wild.wc.masks.tp_dst); | |
73c0ce34 | 227 | } else if (f_idx == CLS_F_IDX_DL_SRC) { |
5cb7a798 BP |
228 | eq = eth_addr_equal_except(fixed->dl_src, wild.flow.dl_src, |
229 | wild.wc.masks.dl_src); | |
73c0ce34 | 230 | } else if (f_idx == CLS_F_IDX_DL_DST) { |
5cb7a798 BP |
231 | eq = eth_addr_equal_except(fixed->dl_dst, wild.flow.dl_dst, |
232 | wild.wc.masks.dl_dst); | |
66642cb4 | 233 | } else if (f_idx == CLS_F_IDX_VLAN_TCI) { |
5cb7a798 BP |
234 | eq = !((fixed->vlan_tci ^ wild.flow.vlan_tci) |
235 | & wild.wc.masks.vlan_tci); | |
8368c090 | 236 | } else if (f_idx == CLS_F_IDX_TUN_ID) { |
296e07ac JG |
237 | eq = !((fixed->tunnel.tun_id ^ wild.flow.tunnel.tun_id) |
238 | & wild.wc.masks.tunnel.tun_id); | |
7525e578 | 239 | } else if (f_idx == CLS_F_IDX_METADATA) { |
5cb7a798 BP |
240 | eq = !((fixed->metadata ^ wild.flow.metadata) |
241 | & wild.wc.masks.metadata); | |
2486e66a | 242 | } else if (f_idx == CLS_F_IDX_NW_DSCP) { |
5cb7a798 BP |
243 | eq = !((fixed->nw_tos ^ wild.flow.nw_tos) & |
244 | (wild.wc.masks.nw_tos & IP_DSCP_MASK)); | |
851d3105 | 245 | } else if (f_idx == CLS_F_IDX_NW_PROTO) { |
5cb7a798 BP |
246 | eq = !((fixed->nw_proto ^ wild.flow.nw_proto) |
247 | & wild.wc.masks.nw_proto); | |
e2170cff | 248 | } else if (f_idx == CLS_F_IDX_DL_TYPE) { |
5cb7a798 BP |
249 | eq = !((fixed->dl_type ^ wild.flow.dl_type) |
250 | & wild.wc.masks.dl_type); | |
0bdc4bec | 251 | } else if (f_idx == CLS_F_IDX_IN_PORT) { |
4e022ec0 AW |
252 | eq = !((fixed->in_port.ofp_port |
253 | ^ wild.flow.in_port.ofp_port) | |
254 | & wild.wc.masks.in_port.ofp_port); | |
d8ae4d67 | 255 | } else { |
428b2edd | 256 | OVS_NOT_REACHED(); |
064af421 BP |
257 | } |
258 | ||
d8ae4d67 BP |
259 | if (!eq) { |
260 | return false; | |
064af421 | 261 | } |
064af421 BP |
262 | } |
263 | return true; | |
264 | } | |
265 | ||
266 | static struct cls_rule * | |
3c4486a5 | 267 | tcls_lookup(const struct tcls *cls, const struct flow *flow) |
064af421 BP |
268 | { |
269 | size_t i; | |
270 | ||
271 | for (i = 0; i < cls->n_rules; i++) { | |
272 | struct test_rule *pos = cls->rules[i]; | |
3c4486a5 | 273 | if (match(&pos->cls_rule, flow)) { |
064af421 BP |
274 | return &pos->cls_rule; |
275 | } | |
276 | } | |
277 | return NULL; | |
278 | } | |
279 | ||
280 | static void | |
3c4486a5 | 281 | tcls_delete_matches(struct tcls *cls, const struct cls_rule *target) |
064af421 BP |
282 | { |
283 | size_t i; | |
284 | ||
285 | for (i = 0; i < cls->n_rules; ) { | |
286 | struct test_rule *pos = cls->rules[i]; | |
8fd47924 JR |
287 | if (!minimask_has_extra(pos->cls_rule.match.mask, |
288 | target->match.mask)) { | |
5cb7a798 BP |
289 | struct flow flow; |
290 | ||
8fd47924 | 291 | miniflow_expand(pos->cls_rule.match.flow, &flow); |
5cb7a798 BP |
292 | if (match(target, &flow)) { |
293 | tcls_remove(cls, pos); | |
294 | continue; | |
295 | } | |
064af421 | 296 | } |
5cb7a798 | 297 | i++; |
064af421 BP |
298 | } |
299 | } | |
300 | \f | |
3c4486a5 | 301 | static ovs_be32 nw_src_values[] = { CONSTANT_HTONL(0xc0a80001), |
965f03d8 | 302 | CONSTANT_HTONL(0xc0a04455) }; |
3c4486a5 | 303 | static ovs_be32 nw_dst_values[] = { CONSTANT_HTONL(0xc0a80002), |
965f03d8 | 304 | CONSTANT_HTONL(0xc0a04455) }; |
b9298d3f BP |
305 | static ovs_be64 tun_id_values[] = { |
306 | 0, | |
307 | CONSTANT_HTONLL(UINT64_C(0xfedcba9876543210)) }; | |
7525e578 JS |
308 | static ovs_be64 metadata_values[] = { |
309 | 0, | |
310 | CONSTANT_HTONLL(UINT64_C(0xfedcba9876543210)) }; | |
4e022ec0 | 311 | static ofp_port_t in_port_values[] = { OFP_PORT_C(1), OFPP_LOCAL }; |
66642cb4 | 312 | static ovs_be16 vlan_tci_values[] = { CONSTANT_HTONS(101), CONSTANT_HTONS(0) }; |
3c4486a5 | 313 | static ovs_be16 dl_type_values[] |
965f03d8 | 314 | = { CONSTANT_HTONS(ETH_TYPE_IP), CONSTANT_HTONS(ETH_TYPE_ARP) }; |
3c4486a5 | 315 | static ovs_be16 tp_src_values[] = { CONSTANT_HTONS(49362), |
965f03d8 | 316 | CONSTANT_HTONS(80) }; |
3c4486a5 | 317 | static ovs_be16 tp_dst_values[] = { CONSTANT_HTONS(6667), CONSTANT_HTONS(22) }; |
74ff3298 JR |
318 | static struct eth_addr dl_src_values[] = { |
319 | { { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 } } }, | |
320 | { { { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } } } }; | |
321 | static struct eth_addr dl_dst_values[] = { | |
322 | { { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 } } }, | |
323 | { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } } } }; | |
6767a2cc | 324 | static uint8_t nw_proto_values[] = { IPPROTO_TCP, IPPROTO_ICMP }; |
2486e66a | 325 | static uint8_t nw_dscp_values[] = { 48, 0 }; |
064af421 BP |
326 | |
327 | static void *values[CLS_N_FIELDS][2]; | |
328 | ||
329 | static void | |
330 | init_values(void) | |
331 | { | |
659586ef JG |
332 | values[CLS_F_IDX_TUN_ID][0] = &tun_id_values[0]; |
333 | values[CLS_F_IDX_TUN_ID][1] = &tun_id_values[1]; | |
334 | ||
7525e578 JS |
335 | values[CLS_F_IDX_METADATA][0] = &metadata_values[0]; |
336 | values[CLS_F_IDX_METADATA][1] = &metadata_values[1]; | |
337 | ||
064af421 BP |
338 | values[CLS_F_IDX_IN_PORT][0] = &in_port_values[0]; |
339 | values[CLS_F_IDX_IN_PORT][1] = &in_port_values[1]; | |
340 | ||
66642cb4 BP |
341 | values[CLS_F_IDX_VLAN_TCI][0] = &vlan_tci_values[0]; |
342 | values[CLS_F_IDX_VLAN_TCI][1] = &vlan_tci_values[1]; | |
959a2ecd | 343 | |
74ff3298 JR |
344 | values[CLS_F_IDX_DL_SRC][0] = &dl_src_values[0]; |
345 | values[CLS_F_IDX_DL_SRC][1] = &dl_src_values[1]; | |
064af421 | 346 | |
74ff3298 JR |
347 | values[CLS_F_IDX_DL_DST][0] = &dl_dst_values[0]; |
348 | values[CLS_F_IDX_DL_DST][1] = &dl_dst_values[1]; | |
064af421 BP |
349 | |
350 | values[CLS_F_IDX_DL_TYPE][0] = &dl_type_values[0]; | |
351 | values[CLS_F_IDX_DL_TYPE][1] = &dl_type_values[1]; | |
352 | ||
353 | values[CLS_F_IDX_NW_SRC][0] = &nw_src_values[0]; | |
354 | values[CLS_F_IDX_NW_SRC][1] = &nw_src_values[1]; | |
355 | ||
356 | values[CLS_F_IDX_NW_DST][0] = &nw_dst_values[0]; | |
357 | values[CLS_F_IDX_NW_DST][1] = &nw_dst_values[1]; | |
358 | ||
359 | values[CLS_F_IDX_NW_PROTO][0] = &nw_proto_values[0]; | |
360 | values[CLS_F_IDX_NW_PROTO][1] = &nw_proto_values[1]; | |
361 | ||
2486e66a JP |
362 | values[CLS_F_IDX_NW_DSCP][0] = &nw_dscp_values[0]; |
363 | values[CLS_F_IDX_NW_DSCP][1] = &nw_dscp_values[1]; | |
834377ea | 364 | |
064af421 BP |
365 | values[CLS_F_IDX_TP_SRC][0] = &tp_src_values[0]; |
366 | values[CLS_F_IDX_TP_SRC][1] = &tp_src_values[1]; | |
367 | ||
368 | values[CLS_F_IDX_TP_DST][0] = &tp_dst_values[0]; | |
369 | values[CLS_F_IDX_TP_DST][1] = &tp_dst_values[1]; | |
370 | } | |
371 | ||
372 | #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values) | |
373 | #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values) | |
659586ef | 374 | #define N_TUN_ID_VALUES ARRAY_SIZE(tun_id_values) |
7525e578 | 375 | #define N_METADATA_VALUES ARRAY_SIZE(metadata_values) |
064af421 | 376 | #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values) |
66642cb4 | 377 | #define N_VLAN_TCI_VALUES ARRAY_SIZE(vlan_tci_values) |
064af421 BP |
378 | #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values) |
379 | #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values) | |
380 | #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values) | |
381 | #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values) | |
382 | #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values) | |
383 | #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values) | |
2486e66a | 384 | #define N_NW_DSCP_VALUES ARRAY_SIZE(nw_dscp_values) |
064af421 BP |
385 | |
386 | #define N_FLOW_VALUES (N_NW_SRC_VALUES * \ | |
387 | N_NW_DST_VALUES * \ | |
659586ef | 388 | N_TUN_ID_VALUES * \ |
064af421 | 389 | N_IN_PORT_VALUES * \ |
66642cb4 | 390 | N_VLAN_TCI_VALUES * \ |
064af421 BP |
391 | N_DL_TYPE_VALUES * \ |
392 | N_TP_SRC_VALUES * \ | |
393 | N_TP_DST_VALUES * \ | |
394 | N_DL_SRC_VALUES * \ | |
395 | N_DL_DST_VALUES * \ | |
834377ea | 396 | N_NW_PROTO_VALUES * \ |
2486e66a | 397 | N_NW_DSCP_VALUES) |
064af421 BP |
398 | |
399 | static unsigned int | |
400 | get_value(unsigned int *x, unsigned n_values) | |
401 | { | |
402 | unsigned int rem = *x % n_values; | |
403 | *x /= n_values; | |
404 | return rem; | |
405 | } | |
406 | ||
064af421 | 407 | static void |
3bbe9a1f | 408 | compare_classifiers(struct classifier *cls, size_t n_invisible_rules, |
44e0c35d | 409 | ovs_version_t version, struct tcls *tcls) |
064af421 | 410 | { |
70d3fbe7 | 411 | static const int confidence = 500; |
064af421 BP |
412 | unsigned int i; |
413 | ||
3bbe9a1f | 414 | assert(classifier_count(cls) == tcls->n_rules + n_invisible_rules); |
70d3fbe7 | 415 | for (i = 0; i < confidence; i++) { |
dfea28b3 | 416 | const struct cls_rule *cr0, *cr1, *cr2; |
ae412e7d | 417 | struct flow flow; |
476f36e8 | 418 | struct flow_wildcards wc; |
064af421 | 419 | unsigned int x; |
064af421 | 420 | |
476f36e8 | 421 | flow_wildcards_init_catchall(&wc); |
b028db44 | 422 | x = random_range(N_FLOW_VALUES); |
51c14ddd | 423 | memset(&flow, 0, sizeof flow); |
064af421 BP |
424 | flow.nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)]; |
425 | flow.nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)]; | |
296e07ac | 426 | flow.tunnel.tun_id = tun_id_values[get_value(&x, N_TUN_ID_VALUES)]; |
7525e578 | 427 | flow.metadata = metadata_values[get_value(&x, N_METADATA_VALUES)]; |
4e022ec0 AW |
428 | flow.in_port.ofp_port = in_port_values[get_value(&x, |
429 | N_IN_PORT_VALUES)]; | |
66642cb4 | 430 | flow.vlan_tci = vlan_tci_values[get_value(&x, N_VLAN_TCI_VALUES)]; |
064af421 BP |
431 | flow.dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)]; |
432 | flow.tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)]; | |
433 | flow.tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)]; | |
74ff3298 JR |
434 | flow.dl_src = dl_src_values[get_value(&x, N_DL_SRC_VALUES)]; |
435 | flow.dl_dst = dl_dst_values[get_value(&x, N_DL_DST_VALUES)]; | |
064af421 | 436 | flow.nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)]; |
2486e66a | 437 | flow.nw_tos = nw_dscp_values[get_value(&x, N_NW_DSCP_VALUES)]; |
064af421 | 438 | |
c424c2f7 | 439 | /* This assertion is here to suppress a GCC 4.9 array-bounds warning */ |
e48eccd1 | 440 | ovs_assert(cls->n_tries <= CLS_MAX_TRIES); |
c424c2f7 | 441 | |
3bbe9a1f | 442 | cr0 = classifier_lookup(cls, version, &flow, &wc); |
3c4486a5 BP |
443 | cr1 = tcls_lookup(tcls, &flow); |
444 | assert((cr0 == NULL) == (cr1 == NULL)); | |
445 | if (cr0 != NULL) { | |
446 | const struct test_rule *tr0 = test_rule_from_cls_rule(cr0); | |
447 | const struct test_rule *tr1 = test_rule_from_cls_rule(cr1); | |
448 | ||
193eb874 | 449 | assert(cls_rule_equal(cr0, cr1)); |
3c4486a5 | 450 | assert(tr0->aux == tr1->aux); |
3bbe9a1f JR |
451 | |
452 | /* Make sure the rule should have been visible. */ | |
5e27fe97 | 453 | assert(cls_rule_visible_in_version(cr0, version)); |
064af421 | 454 | } |
3bbe9a1f | 455 | cr2 = classifier_lookup(cls, version, &flow, NULL); |
476f36e8 | 456 | assert(cr2 == cr0); |
064af421 BP |
457 | } |
458 | } | |
459 | ||
064af421 BP |
460 | static void |
461 | destroy_classifier(struct classifier *cls) | |
462 | { | |
78c8df12 | 463 | struct test_rule *rule; |
5ecc9d81 | 464 | |
802f84ff | 465 | classifier_defer(cls); |
de4ad4a2 | 466 | CLS_FOR_EACH (rule, cls_rule, cls) { |
42767cce JR |
467 | if (classifier_remove(cls, &rule->cls_rule)) { |
468 | ovsrcu_postpone(free_rule, rule); | |
469 | } | |
5ecc9d81 | 470 | } |
064af421 BP |
471 | classifier_destroy(cls); |
472 | } | |
473 | ||
fe7cfa5c | 474 | static void |
da9cfca6 | 475 | pvector_verify(const struct pvector *pvec) |
fe7cfa5c JR |
476 | { |
477 | void *ptr OVS_UNUSED; | |
eb391b76 | 478 | int prev_priority = INT_MAX; |
fe7cfa5c | 479 | |
da9cfca6 | 480 | PVECTOR_FOR_EACH (ptr, pvec) { |
eb391b76 | 481 | int priority = cursor__.vector[cursor__.entry_idx].priority; |
fe7cfa5c | 482 | if (priority > prev_priority) { |
38c449e0 JR |
483 | ovs_abort(0, "Priority vector is out of order (%u > %u)", |
484 | priority, prev_priority); | |
fe7cfa5c JR |
485 | } |
486 | prev_priority = priority; | |
487 | } | |
488 | } | |
489 | ||
f358a2cb JR |
490 | static unsigned int |
491 | trie_verify(const rcu_trie_ptr *trie, unsigned int ofs, unsigned int n_bits) | |
492 | { | |
493 | const struct trie_node *node = ovsrcu_get(struct trie_node *, trie); | |
494 | ||
495 | if (node) { | |
496 | assert(node->n_rules == 0 || node->n_bits > 0); | |
497 | ofs += node->n_bits; | |
498 | assert((ofs > 0 || (ofs == 0 && node->n_bits == 0)) && ofs <= n_bits); | |
499 | ||
500 | return node->n_rules | |
501 | + trie_verify(&node->edges[0], ofs, n_bits) | |
502 | + trie_verify(&node->edges[1], ofs, n_bits); | |
503 | } | |
504 | return 0; | |
505 | } | |
506 | ||
507 | static void | |
e48eccd1 | 508 | verify_tries(struct classifier *cls) |
fccd7c09 | 509 | OVS_NO_THREAD_SAFETY_ANALYSIS |
f358a2cb | 510 | { |
f358a2cb JR |
511 | unsigned int n_rules = 0; |
512 | int i; | |
513 | ||
514 | for (i = 0; i < cls->n_tries; i++) { | |
515 | n_rules += trie_verify(&cls->tries[i].root, 0, | |
516 | cls->tries[i].field->n_bits); | |
517 | } | |
f358a2cb | 518 | assert(n_rules <= cls->n_rules); |
f358a2cb JR |
519 | } |
520 | ||
064af421 | 521 | static void |
0b4f2078 | 522 | check_tables(const struct classifier *cls, int n_tables, int n_rules, |
44e0c35d | 523 | int n_dups, int n_invisible, ovs_version_t version) |
fccd7c09 | 524 | OVS_NO_THREAD_SAFETY_ANALYSIS |
064af421 | 525 | { |
03868246 | 526 | const struct cls_subtable *table; |
955f579d | 527 | struct test_rule *test_rule; |
064af421 | 528 | int found_tables = 0; |
3bbe9a1f | 529 | int found_tables_with_visible_rules = 0; |
064af421 | 530 | int found_rules = 0; |
b5d97350 | 531 | int found_dups = 0; |
3bbe9a1f JR |
532 | int found_invisible = 0; |
533 | int found_visible_but_removable = 0; | |
955f579d | 534 | int found_rules2 = 0; |
064af421 | 535 | |
da9cfca6 | 536 | pvector_verify(&cls->subtables); |
e48eccd1 | 537 | CMAP_FOR_EACH (table, cmap_node, &cls->subtables_map) { |
627fb667 | 538 | const struct cls_match *head; |
eb391b76 | 539 | int max_priority = INT_MIN; |
4d935a6b | 540 | unsigned int max_count = 0; |
fe7cfa5c | 541 | bool found = false; |
3bbe9a1f | 542 | bool found_visible_rules = false; |
fe7cfa5c JR |
543 | const struct cls_subtable *iter; |
544 | ||
545 | /* Locate the subtable from 'subtables'. */ | |
da9cfca6 | 546 | PVECTOR_FOR_EACH (iter, &cls->subtables) { |
fe7cfa5c JR |
547 | if (iter == table) { |
548 | if (found) { | |
38c449e0 JR |
549 | ovs_abort(0, "Subtable %p duplicated in 'subtables'.", |
550 | table); | |
fe7cfa5c JR |
551 | } |
552 | found = true; | |
553 | } | |
554 | } | |
555 | if (!found) { | |
38c449e0 | 556 | ovs_abort(0, "Subtable %p not found from 'subtables'.", table); |
fe7cfa5c | 557 | } |
b5d97350 | 558 | |
f2c21402 | 559 | assert(!cmap_is_empty(&table->rules)); |
f358a2cb | 560 | assert(trie_verify(&table->ports_trie, 0, table->ports_mask_len) |
f47eef15 | 561 | == (table->ports_mask_len ? cmap_count(&table->rules) : 0)); |
f358a2cb | 562 | |
064af421 | 563 | found_tables++; |
3bbe9a1f | 564 | |
f2c21402 | 565 | CMAP_FOR_EACH (head, cmap_node, &table->rules) { |
eb391b76 | 566 | int prev_priority = INT_MAX; |
44e0c35d | 567 | ovs_version_t prev_version = 0; |
3bbe9a1f JR |
568 | const struct cls_match *rule, *prev; |
569 | bool found_visible_rules_in_list = false; | |
570 | ||
571 | assert(head->priority <= table->max_priority); | |
b5d97350 | 572 | |
4d935a6b JR |
573 | if (head->priority > max_priority) { |
574 | max_priority = head->priority; | |
3bbe9a1f | 575 | max_count = 0; |
4d935a6b JR |
576 | } |
577 | ||
3bbe9a1f | 578 | FOR_EACH_RULE_IN_LIST_PROTECTED(rule, prev, head) { |
44e0c35d | 579 | ovs_version_t rule_version; |
3bbe9a1f JR |
580 | const struct cls_rule *found_rule; |
581 | ||
582 | /* Priority may not increase. */ | |
583 | assert(rule->priority <= prev_priority); | |
584 | ||
585 | if (rule->priority == max_priority) { | |
586 | ++max_count; | |
587 | } | |
588 | ||
589 | /* Count invisible rules and visible duplicates. */ | |
590 | if (!cls_match_visible_in_version(rule, version)) { | |
591 | found_invisible++; | |
592 | } else { | |
593 | if (cls_match_is_eventually_invisible(rule)) { | |
594 | found_visible_but_removable++; | |
595 | } | |
596 | if (found_visible_rules_in_list) { | |
597 | found_dups++; | |
598 | } | |
599 | found_visible_rules_in_list = true; | |
600 | found_visible_rules = true; | |
601 | } | |
602 | ||
603 | /* Rule must be visible in the version it was inserted. */ | |
44e0c35d | 604 | rule_version = rule->versions.add_version; |
3bbe9a1f JR |
605 | assert(cls_match_visible_in_version(rule, rule_version)); |
606 | ||
607 | /* We should always find the latest version of the rule, | |
608 | * unless all rules have been marked for removal. | |
609 | * Later versions must always be later in the list. */ | |
bd53aa17 JR |
610 | found_rule = classifier_find_rule_exactly(cls, rule->cls_rule, |
611 | rule_version); | |
3bbe9a1f | 612 | if (found_rule && found_rule != rule->cls_rule) { |
5e27fe97 JR |
613 | struct cls_match *cls_match; |
614 | cls_match = get_cls_match_protected(found_rule); | |
3bbe9a1f JR |
615 | |
616 | assert(found_rule->priority == rule->priority); | |
617 | ||
618 | /* Found rule may not have a lower version. */ | |
44e0c35d | 619 | assert(cls_match->versions.add_version >= rule_version); |
3bbe9a1f JR |
620 | |
621 | /* This rule must not be visible in the found rule's | |
622 | * version. */ | |
bd53aa17 | 623 | assert(!cls_match_visible_in_version( |
44e0c35d | 624 | rule, cls_match->versions.add_version)); |
3bbe9a1f JR |
625 | } |
626 | ||
627 | if (rule->priority == prev_priority) { | |
628 | /* Exact duplicate rule may not have a lower version. */ | |
629 | assert(rule_version >= prev_version); | |
630 | ||
631 | /* Previous rule must not be visible in rule's version. */ | |
632 | assert(!cls_match_visible_in_version(prev, rule_version)); | |
633 | } | |
4d935a6b | 634 | |
b5d97350 | 635 | prev_priority = rule->priority; |
3bbe9a1f | 636 | prev_version = rule_version; |
b5d97350 | 637 | found_rules++; |
b5d97350 BP |
638 | } |
639 | } | |
3bbe9a1f JR |
640 | |
641 | if (found_visible_rules) { | |
642 | found_tables_with_visible_rules++; | |
643 | } | |
644 | ||
4d935a6b JR |
645 | assert(table->max_priority == max_priority); |
646 | assert(table->max_count == max_count); | |
064af421 BP |
647 | } |
648 | ||
e48eccd1 | 649 | assert(found_tables == cmap_count(&cls->subtables_map)); |
da9cfca6 | 650 | assert(found_tables == pvector_count(&cls->subtables)); |
3bbe9a1f JR |
651 | assert(n_tables == -1 || n_tables == found_tables_with_visible_rules); |
652 | assert(n_rules == -1 || found_rules == n_rules + found_invisible); | |
b5d97350 | 653 | assert(n_dups == -1 || found_dups == n_dups); |
3bbe9a1f | 654 | assert(found_invisible == n_invisible); |
955f579d | 655 | |
5f0476ce | 656 | CLS_FOR_EACH (test_rule, cls_rule, cls) { |
955f579d BP |
657 | found_rules2++; |
658 | } | |
3bbe9a1f JR |
659 | /* Iteration does not see removable rules. */ |
660 | assert(found_rules | |
661 | == found_rules2 + found_visible_but_removable + found_invisible); | |
064af421 BP |
662 | } |
663 | ||
664 | static struct test_rule * | |
bd53aa17 | 665 | make_rule(int wc_fields, int priority, int value_pat) |
064af421 BP |
666 | { |
667 | const struct cls_field *f; | |
668 | struct test_rule *rule; | |
81a76618 | 669 | struct match match; |
064af421 | 670 | |
81a76618 | 671 | match_init_catchall(&match); |
064af421 BP |
672 | for (f = &cls_fields[0]; f < &cls_fields[CLS_N_FIELDS]; f++) { |
673 | int f_idx = f - cls_fields; | |
d8ae4d67 | 674 | int value_idx = (value_pat & (1u << f_idx)) != 0; |
81a76618 | 675 | memcpy((char *) &match.flow + f->ofs, |
d8ae4d67 BP |
676 | values[f_idx][value_idx], f->len); |
677 | ||
0bdc4bec | 678 | if (f_idx == CLS_F_IDX_NW_SRC) { |
b8266395 | 679 | match.wc.masks.nw_src = OVS_BE32_MAX; |
d8ae4d67 | 680 | } else if (f_idx == CLS_F_IDX_NW_DST) { |
b8266395 | 681 | match.wc.masks.nw_dst = OVS_BE32_MAX; |
73f33563 | 682 | } else if (f_idx == CLS_F_IDX_TP_SRC) { |
b8266395 | 683 | match.wc.masks.tp_src = OVS_BE16_MAX; |
73f33563 | 684 | } else if (f_idx == CLS_F_IDX_TP_DST) { |
b8266395 | 685 | match.wc.masks.tp_dst = OVS_BE16_MAX; |
73c0ce34 | 686 | } else if (f_idx == CLS_F_IDX_DL_SRC) { |
74ff3298 | 687 | WC_MASK_FIELD(&match.wc, dl_src); |
73c0ce34 | 688 | } else if (f_idx == CLS_F_IDX_DL_DST) { |
74ff3298 | 689 | WC_MASK_FIELD(&match.wc, dl_dst); |
66642cb4 | 690 | } else if (f_idx == CLS_F_IDX_VLAN_TCI) { |
b8266395 | 691 | match.wc.masks.vlan_tci = OVS_BE16_MAX; |
8368c090 | 692 | } else if (f_idx == CLS_F_IDX_TUN_ID) { |
b8266395 | 693 | match.wc.masks.tunnel.tun_id = OVS_BE64_MAX; |
7525e578 | 694 | } else if (f_idx == CLS_F_IDX_METADATA) { |
b8266395 | 695 | match.wc.masks.metadata = OVS_BE64_MAX; |
5d9499c4 | 696 | } else if (f_idx == CLS_F_IDX_NW_DSCP) { |
81a76618 | 697 | match.wc.masks.nw_tos |= IP_DSCP_MASK; |
851d3105 | 698 | } else if (f_idx == CLS_F_IDX_NW_PROTO) { |
81a76618 | 699 | match.wc.masks.nw_proto = UINT8_MAX; |
e2170cff | 700 | } else if (f_idx == CLS_F_IDX_DL_TYPE) { |
b8266395 | 701 | match.wc.masks.dl_type = OVS_BE16_MAX; |
0bdc4bec | 702 | } else if (f_idx == CLS_F_IDX_IN_PORT) { |
e2711da9 | 703 | match.wc.masks.in_port.ofp_port = u16_to_ofp(UINT16_MAX); |
064af421 | 704 | } else { |
428b2edd | 705 | OVS_NOT_REACHED(); |
064af421 BP |
706 | } |
707 | } | |
81a76618 BP |
708 | |
709 | rule = xzalloc(sizeof *rule); | |
712b4d24 | 710 | cls_rule_init(&rule->cls_rule, &match, wc_fields |
3bbe9a1f JR |
711 | ? (priority == INT_MIN ? priority + 1 : |
712 | priority == INT_MAX ? priority - 1 : priority) | |
bd53aa17 | 713 | : 0); |
064af421 BP |
714 | return rule; |
715 | } | |
716 | ||
48d28ac1 BP |
717 | static struct test_rule * |
718 | clone_rule(const struct test_rule *src) | |
719 | { | |
720 | struct test_rule *dst; | |
721 | ||
722 | dst = xmalloc(sizeof *dst); | |
723 | dst->aux = src->aux; | |
724 | cls_rule_clone(&dst->cls_rule, &src->cls_rule); | |
725 | return dst; | |
726 | } | |
727 | ||
728 | static void | |
729 | free_rule(struct test_rule *rule) | |
730 | { | |
731 | cls_rule_destroy(&rule->cls_rule); | |
732 | free(rule); | |
733 | } | |
734 | ||
064af421 | 735 | static void |
eb391b76 | 736 | shuffle(int *p, size_t n) |
064af421 BP |
737 | { |
738 | for (; n > 1; n--, p++) { | |
eb391b76 BP |
739 | int *q = &p[random_range(n)]; |
740 | int tmp = *p; | |
064af421 BP |
741 | *p = *q; |
742 | *q = tmp; | |
743 | } | |
744 | } | |
5cb7a798 BP |
745 | |
746 | static void | |
747 | shuffle_u32s(uint32_t *p, size_t n) | |
748 | { | |
749 | for (; n > 1; n--, p++) { | |
b028db44 | 750 | uint32_t *q = &p[random_range(n)]; |
5cb7a798 BP |
751 | uint32_t tmp = *p; |
752 | *p = *q; | |
753 | *q = tmp; | |
754 | } | |
755 | } | |
064af421 | 756 | \f |
5cb7a798 BP |
757 | /* Classifier tests. */ |
758 | ||
13751fd8 JR |
759 | static enum mf_field_id trie_fields[2] = { |
760 | MFF_IPV4_DST, MFF_IPV4_SRC | |
761 | }; | |
762 | ||
f358a2cb JR |
763 | static void |
764 | set_prefix_fields(struct classifier *cls) | |
f358a2cb JR |
765 | { |
766 | verify_tries(cls); | |
767 | classifier_set_prefix_fields(cls, trie_fields, ARRAY_SIZE(trie_fields)); | |
768 | verify_tries(cls); | |
769 | } | |
770 | ||
064af421 BP |
771 | /* Tests an empty classifier. */ |
772 | static void | |
1636c761 | 773 | test_empty(struct ovs_cmdl_context *ctx OVS_UNUSED) |
064af421 BP |
774 | { |
775 | struct classifier cls; | |
776 | struct tcls tcls; | |
777 | ||
d70e8c28 | 778 | classifier_init(&cls, flow_segment_u64s); |
f358a2cb | 779 | set_prefix_fields(&cls); |
064af421 BP |
780 | tcls_init(&tcls); |
781 | assert(classifier_is_empty(&cls)); | |
782 | assert(tcls_is_empty(&tcls)); | |
44e0c35d | 783 | compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls); |
064af421 BP |
784 | classifier_destroy(&cls); |
785 | tcls_destroy(&tcls); | |
786 | } | |
787 | ||
788 | /* Destroys a null classifier. */ | |
789 | static void | |
1636c761 | 790 | test_destroy_null(struct ovs_cmdl_context *ctx OVS_UNUSED) |
064af421 BP |
791 | { |
792 | classifier_destroy(NULL); | |
793 | } | |
794 | ||
795 | /* Tests classification with one rule at a time. */ | |
796 | static void | |
1636c761 | 797 | test_single_rule(struct ovs_cmdl_context *ctx OVS_UNUSED) |
064af421 BP |
798 | { |
799 | unsigned int wc_fields; /* Hilarious. */ | |
800 | ||
801 | for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) { | |
802 | struct classifier cls; | |
803 | struct test_rule *rule, *tcls_rule; | |
804 | struct tcls tcls; | |
805 | ||
806 | rule = make_rule(wc_fields, | |
bd53aa17 | 807 | hash_bytes(&wc_fields, sizeof wc_fields, 0), 0); |
d70e8c28 | 808 | classifier_init(&cls, flow_segment_u64s); |
f358a2cb | 809 | set_prefix_fields(&cls); |
064af421 | 810 | tcls_init(&tcls); |
064af421 | 811 | tcls_rule = tcls_insert(&tcls, rule); |
3bbe9a1f | 812 | |
44e0c35d JR |
813 | classifier_insert(&cls, &rule->cls_rule, OVS_VERSION_MIN, NULL, 0); |
814 | compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls); | |
815 | check_tables(&cls, 1, 1, 0, 0, OVS_VERSION_MIN); | |
064af421 BP |
816 | |
817 | classifier_remove(&cls, &rule->cls_rule); | |
818 | tcls_remove(&tcls, tcls_rule); | |
819 | assert(classifier_is_empty(&cls)); | |
820 | assert(tcls_is_empty(&tcls)); | |
44e0c35d | 821 | compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls); |
064af421 | 822 | |
42767cce | 823 | ovsrcu_postpone(free_rule, rule); |
064af421 BP |
824 | classifier_destroy(&cls); |
825 | tcls_destroy(&tcls); | |
826 | } | |
827 | } | |
828 | ||
829 | /* Tests replacing one rule by another. */ | |
830 | static void | |
1636c761 | 831 | test_rule_replacement(struct ovs_cmdl_context *ctx OVS_UNUSED) |
064af421 BP |
832 | { |
833 | unsigned int wc_fields; | |
834 | ||
835 | for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) { | |
836 | struct classifier cls; | |
f0f4410a BP |
837 | struct test_rule *rule1; |
838 | struct test_rule *rule2; | |
064af421 BP |
839 | struct tcls tcls; |
840 | ||
bd53aa17 JR |
841 | rule1 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX); |
842 | rule2 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX); | |
064af421 BP |
843 | rule2->aux += 5; |
844 | rule2->aux += 5; | |
845 | ||
d70e8c28 | 846 | classifier_init(&cls, flow_segment_u64s); |
f358a2cb | 847 | set_prefix_fields(&cls); |
064af421 | 848 | tcls_init(&tcls); |
f0f4410a | 849 | tcls_insert(&tcls, rule1); |
44e0c35d JR |
850 | classifier_insert(&cls, &rule1->cls_rule, OVS_VERSION_MIN, NULL, 0); |
851 | compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls); | |
852 | check_tables(&cls, 1, 1, 0, 0, OVS_VERSION_MIN); | |
064af421 BP |
853 | tcls_destroy(&tcls); |
854 | ||
855 | tcls_init(&tcls); | |
f0f4410a | 856 | tcls_insert(&tcls, rule2); |
5f0476ce | 857 | |
064af421 | 858 | assert(test_rule_from_cls_rule( |
44e0c35d | 859 | classifier_replace(&cls, &rule2->cls_rule, OVS_VERSION_MIN, |
18080541 | 860 | NULL, 0)) == rule1); |
42767cce | 861 | ovsrcu_postpone(free_rule, rule1); |
44e0c35d JR |
862 | compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls); |
863 | check_tables(&cls, 1, 1, 0, 0, OVS_VERSION_MIN); | |
802f84ff | 864 | classifier_defer(&cls); |
42767cce | 865 | classifier_remove(&cls, &rule2->cls_rule); |
5f0476ce JR |
866 | |
867 | tcls_destroy(&tcls); | |
064af421 BP |
868 | destroy_classifier(&cls); |
869 | } | |
870 | } | |
871 | ||
872 | static int | |
b5d97350 | 873 | factorial(int n_items) |
064af421 | 874 | { |
b5d97350 BP |
875 | int n, i; |
876 | ||
877 | n = 1; | |
878 | for (i = 2; i <= n_items; i++) { | |
879 | n *= i; | |
880 | } | |
881 | return n; | |
064af421 BP |
882 | } |
883 | ||
b5d97350 BP |
884 | static void |
885 | swap(int *a, int *b) | |
064af421 | 886 | { |
b5d97350 BP |
887 | int tmp = *a; |
888 | *a = *b; | |
889 | *b = tmp; | |
064af421 BP |
890 | } |
891 | ||
064af421 | 892 | static void |
b5d97350 | 893 | reverse(int *a, int n) |
064af421 | 894 | { |
b5d97350 | 895 | int i; |
064af421 | 896 | |
b5d97350 BP |
897 | for (i = 0; i < n / 2; i++) { |
898 | int j = n - (i + 1); | |
899 | swap(&a[i], &a[j]); | |
900 | } | |
901 | } | |
064af421 | 902 | |
b5d97350 BP |
903 | static bool |
904 | next_permutation(int *a, int n) | |
905 | { | |
906 | int k; | |
064af421 | 907 | |
b5d97350 BP |
908 | for (k = n - 2; k >= 0; k--) { |
909 | if (a[k] < a[k + 1]) { | |
910 | int l; | |
064af421 | 911 | |
b5d97350 BP |
912 | for (l = n - 1; ; l--) { |
913 | if (a[l] > a[k]) { | |
914 | swap(&a[k], &a[l]); | |
915 | reverse(a + (k + 1), n - (k + 1)); | |
916 | return true; | |
064af421 BP |
917 | } |
918 | } | |
919 | } | |
920 | } | |
b5d97350 | 921 | return false; |
064af421 BP |
922 | } |
923 | ||
b5d97350 | 924 | /* Tests classification with rules that have the same matching criteria. */ |
064af421 | 925 | static void |
1636c761 | 926 | test_many_rules_in_one_list (struct ovs_cmdl_context *ctx OVS_UNUSED) |
b5d97350 BP |
927 | { |
928 | enum { N_RULES = 3 }; | |
929 | int n_pris; | |
064af421 | 930 | |
b5d97350 BP |
931 | for (n_pris = N_RULES; n_pris >= 1; n_pris--) { |
932 | int ops[N_RULES * 2]; | |
933 | int pris[N_RULES]; | |
934 | int n_permutations; | |
935 | int i; | |
064af421 | 936 | |
b5d97350 BP |
937 | pris[0] = 0; |
938 | for (i = 1; i < N_RULES; i++) { | |
939 | pris[i] = pris[i - 1] + (n_pris > i); | |
940 | } | |
064af421 | 941 | |
b5d97350 BP |
942 | for (i = 0; i < N_RULES * 2; i++) { |
943 | ops[i] = i / 2; | |
064af421 | 944 | } |
064af421 | 945 | |
b5d97350 BP |
946 | n_permutations = 0; |
947 | do { | |
948 | struct test_rule *rules[N_RULES]; | |
949 | struct test_rule *tcls_rules[N_RULES]; | |
950 | int pri_rules[N_RULES]; | |
951 | struct classifier cls; | |
952 | struct tcls tcls; | |
44e0c35d | 953 | ovs_version_t version = OVS_VERSION_MIN; |
3bbe9a1f | 954 | size_t n_invisible_rules = 0; |
064af421 | 955 | |
b5d97350 | 956 | n_permutations++; |
064af421 | 957 | |
b5d97350 | 958 | for (i = 0; i < N_RULES; i++) { |
bd53aa17 | 959 | rules[i] = make_rule(456, pris[i], 0); |
b5d97350 BP |
960 | tcls_rules[i] = NULL; |
961 | pri_rules[i] = -1; | |
962 | } | |
064af421 | 963 | |
d70e8c28 | 964 | classifier_init(&cls, flow_segment_u64s); |
f358a2cb | 965 | set_prefix_fields(&cls); |
b5d97350 | 966 | tcls_init(&tcls); |
064af421 | 967 | |
b5d97350 | 968 | for (i = 0; i < ARRAY_SIZE(ops); i++) { |
3bbe9a1f JR |
969 | struct test_rule *displaced_rule = NULL; |
970 | struct cls_rule *removable_rule = NULL; | |
b5d97350 BP |
971 | int j = ops[i]; |
972 | int m, n; | |
064af421 | 973 | |
b5d97350 | 974 | if (!tcls_rules[j]) { |
b5d97350 | 975 | tcls_rules[j] = tcls_insert(&tcls, rules[j]); |
3bbe9a1f JR |
976 | if (versioned) { |
977 | /* Insert the new rule in the next version. */ | |
bd53aa17 | 978 | ++version; |
3bbe9a1f JR |
979 | |
980 | displaced_rule = test_rule_from_cls_rule( | |
981 | classifier_find_rule_exactly(&cls, | |
bd53aa17 JR |
982 | &rules[j]->cls_rule, |
983 | version)); | |
3bbe9a1f JR |
984 | if (displaced_rule) { |
985 | /* Mark the old rule for removal after the current | |
986 | * version. */ | |
987 | cls_rule_make_invisible_in_version( | |
18721c4a | 988 | &displaced_rule->cls_rule, version); |
3bbe9a1f JR |
989 | n_invisible_rules++; |
990 | removable_rule = &displaced_rule->cls_rule; | |
991 | } | |
bd53aa17 JR |
992 | classifier_insert(&cls, &rules[j]->cls_rule, version, |
993 | NULL, 0); | |
3bbe9a1f JR |
994 | } else { |
995 | displaced_rule = test_rule_from_cls_rule( | |
996 | classifier_replace(&cls, &rules[j]->cls_rule, | |
bd53aa17 | 997 | version, NULL, 0)); |
3bbe9a1f | 998 | } |
b5d97350 BP |
999 | if (pri_rules[pris[j]] >= 0) { |
1000 | int k = pri_rules[pris[j]]; | |
1001 | assert(displaced_rule != NULL); | |
1002 | assert(displaced_rule != rules[j]); | |
1003 | assert(pris[j] == displaced_rule->cls_rule.priority); | |
1004 | tcls_rules[k] = NULL; | |
1005 | } else { | |
1006 | assert(displaced_rule == NULL); | |
1007 | } | |
1008 | pri_rules[pris[j]] = j; | |
1009 | } else { | |
3bbe9a1f JR |
1010 | if (versioned) { |
1011 | /* Mark the rule for removal after the current | |
1012 | * version. */ | |
3bbe9a1f | 1013 | ++version; |
bd53aa17 JR |
1014 | cls_rule_make_invisible_in_version( |
1015 | &rules[j]->cls_rule, version); | |
3bbe9a1f JR |
1016 | n_invisible_rules++; |
1017 | removable_rule = &rules[j]->cls_rule; | |
1018 | } else { | |
1019 | classifier_remove(&cls, &rules[j]->cls_rule); | |
1020 | } | |
b5d97350 BP |
1021 | tcls_remove(&tcls, tcls_rules[j]); |
1022 | tcls_rules[j] = NULL; | |
1023 | pri_rules[pris[j]] = -1; | |
1024 | } | |
3bbe9a1f | 1025 | compare_classifiers(&cls, n_invisible_rules, version, &tcls); |
b5d97350 BP |
1026 | n = 0; |
1027 | for (m = 0; m < N_RULES; m++) { | |
1028 | n += tcls_rules[m] != NULL; | |
064af421 | 1029 | } |
3bbe9a1f JR |
1030 | check_tables(&cls, n > 0, n, n - 1, n_invisible_rules, |
1031 | version); | |
1032 | ||
1033 | if (versioned && removable_rule) { | |
5e27fe97 JR |
1034 | struct cls_match *cls_match = |
1035 | get_cls_match_protected(removable_rule); | |
1036 | ||
3bbe9a1f | 1037 | /* Removable rule is no longer visible. */ |
5e27fe97 JR |
1038 | assert(cls_match); |
1039 | assert(!cls_match_visible_in_version(cls_match, version)); | |
3bbe9a1f JR |
1040 | classifier_remove(&cls, removable_rule); |
1041 | n_invisible_rules--; | |
1042 | } | |
064af421 | 1043 | } |
b5d97350 | 1044 | |
802f84ff | 1045 | classifier_defer(&cls); |
b5d97350 | 1046 | for (i = 0; i < N_RULES; i++) { |
42767cce JR |
1047 | if (classifier_remove(&cls, &rules[i]->cls_rule)) { |
1048 | ovsrcu_postpone(free_rule, rules[i]); | |
627fb667 | 1049 | } |
b5d97350 | 1050 | } |
627fb667 JR |
1051 | classifier_destroy(&cls); |
1052 | tcls_destroy(&tcls); | |
b5d97350 BP |
1053 | } while (next_permutation(ops, ARRAY_SIZE(ops))); |
1054 | assert(n_permutations == (factorial(N_RULES * 2) >> N_RULES)); | |
064af421 BP |
1055 | } |
1056 | } | |
1057 | ||
b5d97350 BP |
1058 | static int |
1059 | count_ones(unsigned long int x) | |
064af421 | 1060 | { |
b5d97350 | 1061 | int n = 0; |
064af421 | 1062 | |
b5d97350 | 1063 | while (x) { |
8472a3ce | 1064 | x = zero_rightmost_1bit(x); |
b5d97350 BP |
1065 | n++; |
1066 | } | |
064af421 | 1067 | |
b5d97350 BP |
1068 | return n; |
1069 | } | |
064af421 | 1070 | |
b5d97350 BP |
1071 | static bool |
1072 | array_contains(int *array, int n, int value) | |
1073 | { | |
1074 | int i; | |
064af421 | 1075 | |
b5d97350 BP |
1076 | for (i = 0; i < n; i++) { |
1077 | if (array[i] == value) { | |
1078 | return true; | |
064af421 BP |
1079 | } |
1080 | } | |
b5d97350 BP |
1081 | |
1082 | return false; | |
064af421 BP |
1083 | } |
1084 | ||
b5d97350 BP |
1085 | /* Tests classification with two rules at a time that fall into the same |
1086 | * table but different lists. */ | |
064af421 | 1087 | static void |
1636c761 | 1088 | test_many_rules_in_one_table(struct ovs_cmdl_context *ctx OVS_UNUSED) |
064af421 | 1089 | { |
b5d97350 | 1090 | int iteration; |
064af421 | 1091 | |
b5d97350 BP |
1092 | for (iteration = 0; iteration < 50; iteration++) { |
1093 | enum { N_RULES = 20 }; | |
1094 | struct test_rule *rules[N_RULES]; | |
1095 | struct test_rule *tcls_rules[N_RULES]; | |
1096 | struct classifier cls; | |
1097 | struct tcls tcls; | |
44e0c35d | 1098 | ovs_version_t version = OVS_VERSION_MIN; |
3bbe9a1f | 1099 | size_t n_invisible_rules = 0; |
b5d97350 BP |
1100 | int value_pats[N_RULES]; |
1101 | int value_mask; | |
1102 | int wcf; | |
1103 | int i; | |
064af421 | 1104 | |
b5d97350 | 1105 | do { |
b028db44 | 1106 | wcf = random_uint32() & ((1u << CLS_N_FIELDS) - 1); |
b5d97350 BP |
1107 | value_mask = ~wcf & ((1u << CLS_N_FIELDS) - 1); |
1108 | } while ((1 << count_ones(value_mask)) < N_RULES); | |
064af421 | 1109 | |
d70e8c28 | 1110 | classifier_init(&cls, flow_segment_u64s); |
f358a2cb | 1111 | set_prefix_fields(&cls); |
b5d97350 | 1112 | tcls_init(&tcls); |
064af421 | 1113 | |
b5d97350 | 1114 | for (i = 0; i < N_RULES; i++) { |
eb391b76 | 1115 | int priority = random_range(INT_MAX); |
064af421 | 1116 | |
b5d97350 | 1117 | do { |
b028db44 | 1118 | value_pats[i] = random_uint32() & value_mask; |
b5d97350 | 1119 | } while (array_contains(value_pats, i, value_pats[i])); |
064af421 | 1120 | |
3bbe9a1f | 1121 | ++version; |
bd53aa17 | 1122 | rules[i] = make_rule(wcf, priority, value_pats[i]); |
b5d97350 | 1123 | tcls_rules[i] = tcls_insert(&tcls, rules[i]); |
5f0476ce | 1124 | |
bd53aa17 | 1125 | classifier_insert(&cls, &rules[i]->cls_rule, version, NULL, 0); |
3bbe9a1f | 1126 | compare_classifiers(&cls, n_invisible_rules, version, &tcls); |
b5d97350 | 1127 | |
3bbe9a1f | 1128 | check_tables(&cls, 1, i + 1, 0, n_invisible_rules, version); |
b5d97350 BP |
1129 | } |
1130 | ||
1131 | for (i = 0; i < N_RULES; i++) { | |
1132 | tcls_remove(&tcls, tcls_rules[i]); | |
3bbe9a1f JR |
1133 | if (versioned) { |
1134 | /* Mark the rule for removal after the current version. */ | |
3bbe9a1f | 1135 | ++version; |
bd53aa17 JR |
1136 | cls_rule_make_invisible_in_version(&rules[i]->cls_rule, |
1137 | version); | |
3bbe9a1f JR |
1138 | n_invisible_rules++; |
1139 | } else { | |
1140 | classifier_remove(&cls, &rules[i]->cls_rule); | |
1141 | } | |
1142 | compare_classifiers(&cls, n_invisible_rules, version, &tcls); | |
1143 | check_tables(&cls, i < N_RULES - 1, N_RULES - (i + 1), 0, | |
1144 | n_invisible_rules, version); | |
1145 | if (!versioned) { | |
1146 | ovsrcu_postpone(free_rule, rules[i]); | |
1147 | } | |
1148 | } | |
b5d97350 | 1149 | |
3bbe9a1f JR |
1150 | if (versioned) { |
1151 | for (i = 0; i < N_RULES; i++) { | |
1152 | classifier_remove(&cls, &rules[i]->cls_rule); | |
1153 | n_invisible_rules--; | |
1154 | ||
1155 | compare_classifiers(&cls, n_invisible_rules, version, &tcls); | |
1156 | check_tables(&cls, 0, 0, 0, n_invisible_rules, version); | |
1157 | ovsrcu_postpone(free_rule, rules[i]); | |
1158 | } | |
064af421 | 1159 | } |
b5d97350 BP |
1160 | |
1161 | classifier_destroy(&cls); | |
1162 | tcls_destroy(&tcls); | |
064af421 BP |
1163 | } |
1164 | } | |
1165 | ||
b5d97350 BP |
1166 | /* Tests classification with many rules at a time that fall into random lists |
1167 | * in 'n' tables. */ | |
064af421 | 1168 | static void |
b5d97350 | 1169 | test_many_rules_in_n_tables(int n_tables) |
064af421 BP |
1170 | { |
1171 | enum { MAX_RULES = 50 }; | |
b5d97350 | 1172 | int wcfs[10]; |
064af421 | 1173 | int iteration; |
b5d97350 BP |
1174 | int i; |
1175 | ||
1176 | assert(n_tables < 10); | |
1177 | for (i = 0; i < n_tables; i++) { | |
1178 | do { | |
b028db44 | 1179 | wcfs[i] = random_uint32() & ((1u << CLS_N_FIELDS) - 1); |
b5d97350 BP |
1180 | } while (array_contains(wcfs, i, wcfs[i])); |
1181 | } | |
064af421 BP |
1182 | |
1183 | for (iteration = 0; iteration < 30; iteration++) { | |
eb391b76 | 1184 | int priorities[MAX_RULES]; |
064af421 BP |
1185 | struct classifier cls; |
1186 | struct tcls tcls; | |
44e0c35d | 1187 | ovs_version_t version = OVS_VERSION_MIN; |
3bbe9a1f JR |
1188 | size_t n_invisible_rules = 0; |
1189 | struct ovs_list list = OVS_LIST_INITIALIZER(&list); | |
064af421 | 1190 | |
b028db44 | 1191 | random_set_seed(iteration + 1); |
064af421 | 1192 | for (i = 0; i < MAX_RULES; i++) { |
eb391b76 | 1193 | priorities[i] = (i * 129) & INT_MAX; |
064af421 BP |
1194 | } |
1195 | shuffle(priorities, ARRAY_SIZE(priorities)); | |
1196 | ||
d70e8c28 | 1197 | classifier_init(&cls, flow_segment_u64s); |
f358a2cb | 1198 | set_prefix_fields(&cls); |
064af421 BP |
1199 | tcls_init(&tcls); |
1200 | ||
1201 | for (i = 0; i < MAX_RULES; i++) { | |
1202 | struct test_rule *rule; | |
eb391b76 | 1203 | int priority = priorities[i]; |
b028db44 BP |
1204 | int wcf = wcfs[random_range(n_tables)]; |
1205 | int value_pat = random_uint32() & ((1u << CLS_N_FIELDS) - 1); | |
bd53aa17 | 1206 | rule = make_rule(wcf, priority, value_pat); |
064af421 | 1207 | tcls_insert(&tcls, rule); |
bd53aa17 | 1208 | classifier_insert(&cls, &rule->cls_rule, version, NULL, 0); |
3bbe9a1f JR |
1209 | compare_classifiers(&cls, n_invisible_rules, version, &tcls); |
1210 | check_tables(&cls, -1, i + 1, -1, n_invisible_rules, version); | |
064af421 BP |
1211 | } |
1212 | ||
3bbe9a1f | 1213 | while (classifier_count(&cls) - n_invisible_rules > 0) { |
5ecc9d81 | 1214 | struct test_rule *target; |
78c8df12 | 1215 | struct test_rule *rule; |
3bbe9a1f | 1216 | size_t n_removable_rules = 0; |
5ecc9d81 | 1217 | |
b028db44 | 1218 | target = clone_rule(tcls.rules[random_range(tcls.n_rules)]); |
5ecc9d81 | 1219 | |
bd53aa17 JR |
1220 | CLS_FOR_EACH_TARGET (rule, cls_rule, &cls, &target->cls_rule, |
1221 | version) { | |
3bbe9a1f JR |
1222 | if (versioned) { |
1223 | /* Mark the rule for removal after the current version. */ | |
1224 | cls_rule_make_invisible_in_version(&rule->cls_rule, | |
18721c4a | 1225 | version + 1); |
3bbe9a1f JR |
1226 | n_removable_rules++; |
1227 | compare_classifiers(&cls, n_invisible_rules, version, | |
1228 | &tcls); | |
1229 | check_tables(&cls, -1, -1, -1, n_invisible_rules, version); | |
1230 | ||
417e7e66 | 1231 | ovs_list_push_back(&list, &rule->list_node); |
3bbe9a1f | 1232 | } else if (classifier_remove(&cls, &rule->cls_rule)) { |
42767cce JR |
1233 | ovsrcu_postpone(free_rule, rule); |
1234 | } | |
5ecc9d81 | 1235 | } |
5f0476ce | 1236 | |
3bbe9a1f JR |
1237 | ++version; |
1238 | n_invisible_rules += n_removable_rules; | |
1239 | ||
5ecc9d81 | 1240 | tcls_delete_matches(&tcls, &target->cls_rule); |
48d28ac1 | 1241 | free_rule(target); |
3bbe9a1f JR |
1242 | |
1243 | compare_classifiers(&cls, n_invisible_rules, version, &tcls); | |
1244 | check_tables(&cls, -1, -1, -1, n_invisible_rules, version); | |
1245 | } | |
1246 | if (versioned) { | |
1247 | struct test_rule *rule; | |
1248 | ||
1249 | /* Remove rules that are no longer visible. */ | |
1250 | LIST_FOR_EACH_POP (rule, list_node, &list) { | |
1251 | classifier_remove(&cls, &rule->cls_rule); | |
1252 | n_invisible_rules--; | |
1253 | ||
1254 | compare_classifiers(&cls, n_invisible_rules, version, | |
1255 | &tcls); | |
1256 | check_tables(&cls, -1, -1, -1, n_invisible_rules, version); | |
1257 | } | |
064af421 | 1258 | } |
064af421 BP |
1259 | |
1260 | destroy_classifier(&cls); | |
1261 | tcls_destroy(&tcls); | |
1262 | } | |
1263 | } | |
b5d97350 BP |
1264 | |
1265 | static void | |
1636c761 | 1266 | test_many_rules_in_two_tables(struct ovs_cmdl_context *ctx OVS_UNUSED) |
b5d97350 BP |
1267 | { |
1268 | test_many_rules_in_n_tables(2); | |
1269 | } | |
1270 | ||
1271 | static void | |
1636c761 | 1272 | test_many_rules_in_five_tables(struct ovs_cmdl_context *ctx OVS_UNUSED) |
b5d97350 BP |
1273 | { |
1274 | test_many_rules_in_n_tables(5); | |
1275 | } | |
064af421 | 1276 | \f |
1add079e JR |
1277 | /* Classifier benchmarks. */ |
1278 | ||
1279 | static int n_rules; /* Number of rules to insert. */ | |
1280 | static int n_priorities; /* Number of priorities to use. */ | |
1281 | static int n_tables; /* Number of subtables. */ | |
1282 | static int n_threads; /* Number of threads to search and mutate. */ | |
1283 | static int n_lookups; /* Number of lookups each thread performs. */ | |
1284 | ||
1285 | static void benchmark(bool use_wc); | |
1286 | ||
1287 | static int | |
1288 | elapsed(const struct timeval *start) | |
1289 | { | |
1290 | struct timeval end; | |
1291 | ||
1292 | xgettimeofday(&end); | |
1293 | return timeval_to_msec(&end) - timeval_to_msec(start); | |
1294 | } | |
1295 | ||
1296 | static void | |
1297 | run_benchmarks(struct ovs_cmdl_context *ctx) | |
1298 | { | |
1299 | if (ctx->argc < 5 | |
1300 | || (ctx->argc > 1 && !strcmp(ctx->argv[1], "--help"))) { | |
1301 | printf( | |
1302 | "usage: ovstest %s benchmark <n_rules> <n_priorities> <n_subtables> <n_threads> <n_lookups>\n" | |
1303 | "\n" | |
1304 | "where:\n" | |
1305 | "\n" | |
1306 | "<n_rules> - The number of rules to install for lookups. More rules\n" | |
1307 | " makes misses less likely.\n" | |
1308 | "<n_priorities> - How many different priorities to use. Using only 1\n" | |
1309 | " priority will force lookups to continue through all\n" | |
1310 | " subtables.\n" | |
1311 | "<n_subtables> - Number of subtables to use. Normally a classifier has\n" | |
1312 | " rules with different kinds of masks, resulting in\n" | |
1313 | " multiple subtables (one per mask). However, in some\n" | |
1314 | " special cases a table may consist of only one kind of\n" | |
1315 | " rules, so there will be only one subtable.\n" | |
1316 | "<n_threads> - How many lookup threads to use. Using one thread should\n" | |
1317 | " give less variance accross runs, but classifier\n" | |
1318 | " scaling can be tested with multiple threads.\n" | |
1319 | "<n_lookups> - How many lookups each thread should perform.\n" | |
1320 | "\n", program_name); | |
1321 | return; | |
1322 | } | |
1323 | ||
1324 | n_rules = strtol(ctx->argv[1], NULL, 10); | |
1325 | n_priorities = strtol(ctx->argv[2], NULL, 10); | |
1326 | n_tables = strtol(ctx->argv[3], NULL, 10); | |
1327 | n_threads = strtol(ctx->argv[4], NULL, 10); | |
1328 | n_lookups = strtol(ctx->argv[5], NULL, 10); | |
1329 | ||
1330 | printf("\nBenchmarking with:\n" | |
1331 | "%d rules with %d priorities in %d tables, " | |
1332 | "%d threads doing %d lookups each\n", | |
1333 | n_rules, n_priorities, n_tables, n_threads, n_lookups); | |
1334 | ||
1335 | puts("\nWithout wildcards: \n"); | |
1336 | benchmark(false); | |
1337 | puts("\nWith wildcards: \n"); | |
1338 | benchmark(true); | |
1339 | } | |
1340 | ||
1341 | struct cls_aux { | |
1342 | const struct classifier *cls; | |
1343 | size_t n_lookup_flows; | |
1344 | struct flow *lookup_flows; | |
1345 | bool use_wc; | |
1346 | atomic_int hits; | |
1347 | atomic_int misses; | |
1348 | }; | |
1349 | ||
1350 | static void * | |
1351 | lookup_classifier(void *aux_) | |
1352 | { | |
1353 | struct cls_aux *aux = aux_; | |
44e0c35d | 1354 | ovs_version_t version = OVS_VERSION_MIN; |
1add079e JR |
1355 | int hits = 0, old_hits; |
1356 | int misses = 0, old_misses; | |
1357 | size_t i; | |
1358 | ||
1359 | random_set_seed(1); | |
1360 | ||
1361 | for (i = 0; i < n_lookups; i++) { | |
1362 | const struct cls_rule *cr; | |
1363 | struct flow_wildcards wc; | |
1364 | unsigned int x; | |
1365 | ||
1366 | x = random_range(aux->n_lookup_flows); | |
1367 | ||
1368 | if (aux->use_wc) { | |
1369 | flow_wildcards_init_catchall(&wc); | |
1370 | cr = classifier_lookup(aux->cls, version, &aux->lookup_flows[x], | |
1371 | &wc); | |
1372 | } else { | |
1373 | cr = classifier_lookup(aux->cls, version, &aux->lookup_flows[x], | |
1374 | NULL); | |
1375 | } | |
1376 | if (cr) { | |
1377 | hits++; | |
1378 | } else { | |
1379 | misses++; | |
1380 | } | |
1381 | } | |
1382 | atomic_add(&aux->hits, hits, &old_hits); | |
1383 | atomic_add(&aux->misses, misses, &old_misses); | |
1384 | return NULL; | |
1385 | } | |
1386 | ||
1387 | /* Benchmark classification. */ | |
1388 | static void | |
1389 | benchmark(bool use_wc) | |
1390 | { | |
1391 | struct classifier cls; | |
44e0c35d | 1392 | ovs_version_t version = OVS_VERSION_MIN; |
1add079e JR |
1393 | struct cls_aux aux; |
1394 | int *wcfs = xmalloc(n_tables * sizeof *wcfs); | |
1395 | int *priorities = xmalloc(n_priorities * sizeof *priorities); | |
1396 | struct timeval start; | |
1397 | pthread_t *threads; | |
1398 | int i; | |
1399 | ||
1400 | fatal_signal_init(); | |
1401 | ||
1402 | random_set_seed(1); | |
1403 | ||
1404 | for (i = 0; i < n_tables; i++) { | |
1405 | do { | |
1406 | wcfs[i] = random_uint32() & ((1u << CLS_N_FIELDS) - 1); | |
1407 | } while (array_contains(wcfs, i, wcfs[i])); | |
1408 | } | |
1409 | ||
1410 | for (i = 0; i < n_priorities; i++) { | |
1411 | priorities[i] = (i * 129) & INT_MAX; | |
1412 | } | |
1413 | shuffle(priorities, n_priorities); | |
1414 | ||
1415 | classifier_init(&cls, flow_segment_u64s); | |
1416 | set_prefix_fields(&cls); | |
1417 | ||
1418 | /* Create lookup flows. */ | |
1419 | aux.use_wc = use_wc; | |
1420 | aux.cls = &cls; | |
1421 | aux.n_lookup_flows = 2 * N_FLOW_VALUES; | |
1422 | aux.lookup_flows = xzalloc(aux.n_lookup_flows * sizeof *aux.lookup_flows); | |
1423 | for (i = 0; i < aux.n_lookup_flows; i++) { | |
1424 | struct flow *flow = &aux.lookup_flows[i]; | |
1425 | unsigned int x; | |
1426 | ||
1427 | x = random_range(N_FLOW_VALUES); | |
1428 | flow->nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)]; | |
1429 | flow->nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)]; | |
1430 | flow->tunnel.tun_id = tun_id_values[get_value(&x, N_TUN_ID_VALUES)]; | |
1431 | flow->metadata = metadata_values[get_value(&x, N_METADATA_VALUES)]; | |
1432 | flow->in_port.ofp_port = in_port_values[get_value(&x, | |
1433 | N_IN_PORT_VALUES)]; | |
1434 | flow->vlan_tci = vlan_tci_values[get_value(&x, N_VLAN_TCI_VALUES)]; | |
1435 | flow->dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)]; | |
1436 | flow->tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)]; | |
1437 | flow->tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)]; | |
74ff3298 JR |
1438 | flow->dl_src = dl_src_values[get_value(&x, N_DL_SRC_VALUES)]; |
1439 | flow->dl_dst = dl_dst_values[get_value(&x, N_DL_DST_VALUES)]; | |
1add079e JR |
1440 | flow->nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)]; |
1441 | flow->nw_tos = nw_dscp_values[get_value(&x, N_NW_DSCP_VALUES)]; | |
1442 | } | |
1443 | atomic_init(&aux.hits, 0); | |
1444 | atomic_init(&aux.misses, 0); | |
1445 | ||
1446 | /* Rule insertion. */ | |
1447 | for (i = 0; i < n_rules; i++) { | |
1448 | struct test_rule *rule; | |
1449 | const struct cls_rule *old_cr; | |
1450 | ||
1451 | int priority = priorities[random_range(n_priorities)]; | |
1452 | int wcf = wcfs[random_range(n_tables)]; | |
1453 | int value_pat = random_uint32() & ((1u << CLS_N_FIELDS) - 1); | |
1454 | ||
1455 | rule = make_rule(wcf, priority, value_pat); | |
1456 | old_cr = classifier_find_rule_exactly(&cls, &rule->cls_rule, version); | |
1457 | if (!old_cr) { | |
1458 | classifier_insert(&cls, &rule->cls_rule, version, NULL, 0); | |
1459 | } else { | |
1460 | free_rule(rule); | |
1461 | } | |
1462 | } | |
1463 | ||
1464 | /* Lookup. */ | |
1465 | xgettimeofday(&start); | |
1466 | threads = xmalloc(n_threads * sizeof *threads); | |
1467 | for (i = 0; i < n_threads; i++) { | |
1468 | threads[i] = ovs_thread_create("lookups", lookup_classifier, &aux); | |
1469 | } | |
1470 | for (i = 0; i < n_threads; i++) { | |
1471 | xpthread_join(threads[i], NULL); | |
1472 | } | |
1473 | ||
1474 | int elapsed_msec = elapsed(&start); | |
1475 | ||
1476 | free(threads); | |
1477 | ||
1478 | int hits, misses; | |
1479 | atomic_read(&aux.hits, &hits); | |
1480 | atomic_read(&aux.misses, &misses); | |
1481 | printf("hits: %d, misses: %d\n", hits, misses); | |
1482 | ||
1483 | printf("classifier lookups: %5d ms, %"PRId64" lookups/sec\n", | |
1484 | elapsed_msec, | |
1485 | (((uint64_t)hits + misses) * 1000) / elapsed_msec); | |
1486 | ||
1487 | destroy_classifier(&cls); | |
1488 | free(aux.lookup_flows); | |
1489 | free(priorities); | |
1490 | free(wcfs); | |
1491 | } | |
1492 | \f | |
5cb7a798 BP |
1493 | /* Miniflow tests. */ |
1494 | ||
1495 | static uint32_t | |
1496 | random_value(void) | |
1497 | { | |
1498 | static const uint32_t values[] = | |
1499 | { 0xffffffff, 0xaaaaaaaa, 0x55555555, 0x80000000, | |
1500 | 0x00000001, 0xface0000, 0x00d00d1e, 0xdeadbeef }; | |
1501 | ||
b028db44 | 1502 | return values[random_range(ARRAY_SIZE(values))]; |
5cb7a798 BP |
1503 | } |
1504 | ||
1505 | static bool | |
1506 | choose(unsigned int n, unsigned int *idxp) | |
1507 | { | |
1508 | if (*idxp < n) { | |
1509 | return true; | |
1510 | } else { | |
1511 | *idxp -= n; | |
1512 | return false; | |
1513 | } | |
1514 | } | |
1515 | ||
d70e8c28 JR |
1516 | #define FLOW_U32S (FLOW_U64S * 2) |
1517 | ||
5cb7a798 BP |
1518 | static bool |
1519 | init_consecutive_values(int n_consecutive, struct flow *flow, | |
1520 | unsigned int *idxp) | |
1521 | { | |
1522 | uint32_t *flow_u32 = (uint32_t *) flow; | |
1523 | ||
1524 | if (choose(FLOW_U32S - n_consecutive + 1, idxp)) { | |
1525 | int i; | |
1526 | ||
1527 | for (i = 0; i < n_consecutive; i++) { | |
1528 | flow_u32[*idxp + i] = random_value(); | |
1529 | } | |
1530 | return true; | |
1531 | } else { | |
1532 | return false; | |
1533 | } | |
1534 | } | |
1535 | ||
1536 | static bool | |
1537 | next_random_flow(struct flow *flow, unsigned int idx) | |
1538 | { | |
1539 | uint32_t *flow_u32 = (uint32_t *) flow; | |
1540 | int i; | |
1541 | ||
1542 | memset(flow, 0, sizeof *flow); | |
1543 | ||
1544 | /* Empty flow. */ | |
1545 | if (choose(1, &idx)) { | |
1546 | return true; | |
1547 | } | |
1548 | ||
1549 | /* All flows with a small number of consecutive nonzero values. */ | |
1550 | for (i = 1; i <= 4; i++) { | |
1551 | if (init_consecutive_values(i, flow, &idx)) { | |
1552 | return true; | |
1553 | } | |
1554 | } | |
1555 | ||
1556 | /* All flows with a large number of consecutive nonzero values. */ | |
1557 | for (i = FLOW_U32S - 4; i <= FLOW_U32S; i++) { | |
1558 | if (init_consecutive_values(i, flow, &idx)) { | |
1559 | return true; | |
1560 | } | |
1561 | } | |
1562 | ||
1563 | /* All flows with exactly two nonconsecutive nonzero values. */ | |
1564 | if (choose((FLOW_U32S - 1) * (FLOW_U32S - 2) / 2, &idx)) { | |
1565 | int ofs1; | |
1566 | ||
1567 | for (ofs1 = 0; ofs1 < FLOW_U32S - 2; ofs1++) { | |
1568 | int ofs2; | |
1569 | ||
1570 | for (ofs2 = ofs1 + 2; ofs2 < FLOW_U32S; ofs2++) { | |
1571 | if (choose(1, &idx)) { | |
1572 | flow_u32[ofs1] = random_value(); | |
1573 | flow_u32[ofs2] = random_value(); | |
1574 | return true; | |
1575 | } | |
1576 | } | |
1577 | } | |
428b2edd | 1578 | OVS_NOT_REACHED(); |
5cb7a798 BP |
1579 | } |
1580 | ||
1581 | /* 16 randomly chosen flows with N >= 3 nonzero values. */ | |
1582 | if (choose(16 * (FLOW_U32S - 4), &idx)) { | |
1583 | int n = idx / 16 + 3; | |
1584 | int i; | |
1585 | ||
1586 | for (i = 0; i < n; i++) { | |
1587 | flow_u32[i] = random_value(); | |
1588 | } | |
1589 | shuffle_u32s(flow_u32, FLOW_U32S); | |
1590 | ||
1591 | return true; | |
1592 | } | |
1593 | ||
1594 | return false; | |
1595 | } | |
1596 | ||
1597 | static void | |
1598 | any_random_flow(struct flow *flow) | |
1599 | { | |
1600 | static unsigned int max; | |
1601 | if (!max) { | |
1602 | while (next_random_flow(flow, max)) { | |
1603 | max++; | |
1604 | } | |
1605 | } | |
1606 | ||
1607 | next_random_flow(flow, random_range(max)); | |
1608 | } | |
1609 | ||
1610 | static void | |
1611 | toggle_masked_flow_bits(struct flow *flow, const struct flow_wildcards *mask) | |
1612 | { | |
1613 | const uint32_t *mask_u32 = (const uint32_t *) &mask->masks; | |
1614 | uint32_t *flow_u32 = (uint32_t *) flow; | |
1615 | int i; | |
1616 | ||
1617 | for (i = 0; i < FLOW_U32S; i++) { | |
1618 | if (mask_u32[i] != 0) { | |
1619 | uint32_t bit; | |
1620 | ||
1621 | do { | |
1622 | bit = 1u << random_range(32); | |
1623 | } while (!(bit & mask_u32[i])); | |
1624 | flow_u32[i] ^= bit; | |
1625 | } | |
1626 | } | |
1627 | } | |
1628 | ||
1629 | static void | |
1630 | wildcard_extra_bits(struct flow_wildcards *mask) | |
1631 | { | |
1632 | uint32_t *mask_u32 = (uint32_t *) &mask->masks; | |
1633 | int i; | |
1634 | ||
1635 | for (i = 0; i < FLOW_U32S; i++) { | |
1636 | if (mask_u32[i] != 0) { | |
1637 | uint32_t bit; | |
1638 | ||
1639 | do { | |
1640 | bit = 1u << random_range(32); | |
1641 | } while (!(bit & mask_u32[i])); | |
1642 | mask_u32[i] &= ~bit; | |
1643 | } | |
1644 | } | |
1645 | } | |
1646 | ||
a851eb94 JR |
1647 | /* Returns a copy of 'src'. The caller must eventually free the returned |
1648 | * miniflow with free(). */ | |
1649 | static struct miniflow * | |
1650 | miniflow_clone__(const struct miniflow *src) | |
1651 | { | |
1652 | struct miniflow *dst; | |
1653 | size_t data_size; | |
1654 | ||
1655 | data_size = miniflow_alloc(&dst, 1, src); | |
1656 | miniflow_clone(dst, src, data_size / sizeof(uint64_t)); | |
1657 | return dst; | |
1658 | } | |
1659 | ||
b30001c7 JR |
1660 | /* Returns a hash value for 'flow', given 'basis'. */ |
1661 | static inline uint32_t | |
1662 | miniflow_hash__(const struct miniflow *flow, uint32_t basis) | |
1663 | { | |
5fcff47b JR |
1664 | const uint64_t *p = miniflow_get_values(flow); |
1665 | size_t n_values = miniflow_n_values(flow); | |
1666 | struct flowmap hash_map = FLOWMAP_EMPTY_INITIALIZER; | |
b30001c7 | 1667 | uint32_t hash = basis; |
5fcff47b | 1668 | size_t idx; |
b30001c7 | 1669 | |
5fcff47b JR |
1670 | FLOWMAP_FOR_EACH_INDEX(idx, flow->map) { |
1671 | uint64_t value = *p++; | |
1672 | ||
1673 | if (value) { | |
1674 | hash = hash_add64(hash, value); | |
1675 | flowmap_set(&hash_map, idx, 1); | |
b30001c7 | 1676 | } |
b30001c7 | 1677 | } |
5fcff47b JR |
1678 | map_t map; |
1679 | FLOWMAP_FOR_EACH_MAP (map, hash_map) { | |
1680 | hash = hash_add64(hash, map); | |
b30001c7 | 1681 | } |
b30001c7 | 1682 | |
5fcff47b | 1683 | return hash_finish(hash, n_values); |
b30001c7 JR |
1684 | } |
1685 | ||
5cb7a798 | 1686 | static void |
1636c761 | 1687 | test_miniflow(struct ovs_cmdl_context *ctx OVS_UNUSED) |
5cb7a798 BP |
1688 | { |
1689 | struct flow flow; | |
1690 | unsigned int idx; | |
1691 | ||
1692 | random_set_seed(0xb3faca38); | |
1693 | for (idx = 0; next_random_flow(&flow, idx); idx++) { | |
d70e8c28 | 1694 | const uint64_t *flow_u64 = (const uint64_t *) &flow; |
8fd47924 | 1695 | struct miniflow *miniflow, *miniflow2, *miniflow3; |
5cb7a798 BP |
1696 | struct flow flow2, flow3; |
1697 | struct flow_wildcards mask; | |
8fd47924 | 1698 | struct minimask *minimask; |
5cb7a798 BP |
1699 | int i; |
1700 | ||
1701 | /* Convert flow to miniflow. */ | |
8fd47924 | 1702 | miniflow = miniflow_create(&flow); |
5cb7a798 BP |
1703 | |
1704 | /* Check that the flow equals its miniflow. */ | |
8fd47924 | 1705 | assert(miniflow_get_vid(miniflow) == vlan_tci_to_vid(flow.vlan_tci)); |
d70e8c28 | 1706 | for (i = 0; i < FLOW_U64S; i++) { |
8fd47924 | 1707 | assert(miniflow_get(miniflow, i) == flow_u64[i]); |
5cb7a798 BP |
1708 | } |
1709 | ||
1710 | /* Check that the miniflow equals itself. */ | |
8fd47924 | 1711 | assert(miniflow_equal(miniflow, miniflow)); |
5cb7a798 BP |
1712 | |
1713 | /* Convert miniflow back to flow and verify that it's the same. */ | |
8fd47924 | 1714 | miniflow_expand(miniflow, &flow2); |
5cb7a798 BP |
1715 | assert(flow_equal(&flow, &flow2)); |
1716 | ||
1717 | /* Check that copying a miniflow works properly. */ | |
a851eb94 | 1718 | miniflow2 = miniflow_clone__(miniflow); |
8fd47924 | 1719 | assert(miniflow_equal(miniflow, miniflow2)); |
b30001c7 | 1720 | assert(miniflow_hash__(miniflow, 0) == miniflow_hash__(miniflow2, 0)); |
8fd47924 | 1721 | miniflow_expand(miniflow2, &flow3); |
5cb7a798 BP |
1722 | assert(flow_equal(&flow, &flow3)); |
1723 | ||
1724 | /* Check that masked matches work as expected for identical flows and | |
1725 | * miniflows. */ | |
1726 | do { | |
1727 | next_random_flow(&mask.masks, 1); | |
1728 | } while (flow_wildcards_is_catchall(&mask)); | |
8fd47924 JR |
1729 | minimask = minimask_create(&mask); |
1730 | assert(minimask_is_catchall(minimask) | |
5cb7a798 | 1731 | == flow_wildcards_is_catchall(&mask)); |
8fd47924 JR |
1732 | assert(miniflow_equal_in_minimask(miniflow, miniflow2, minimask)); |
1733 | assert(miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask)); | |
1734 | assert(miniflow_hash_in_minimask(miniflow, minimask, 0x12345678) == | |
1735 | flow_hash_in_minimask(&flow, minimask, 0x12345678)); | |
b30001c7 JR |
1736 | assert(minimask_hash(minimask, 0) == |
1737 | miniflow_hash__(&minimask->masks, 0)); | |
5cb7a798 BP |
1738 | |
1739 | /* Check that masked matches work as expected for differing flows and | |
1740 | * miniflows. */ | |
1741 | toggle_masked_flow_bits(&flow2, &mask); | |
8fd47924 JR |
1742 | assert(!miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask)); |
1743 | miniflow3 = miniflow_create(&flow2); | |
1744 | assert(!miniflow_equal_in_minimask(miniflow, miniflow3, minimask)); | |
5cb7a798 BP |
1745 | |
1746 | /* Clean up. */ | |
8fd47924 JR |
1747 | free(miniflow); |
1748 | free(miniflow2); | |
1749 | free(miniflow3); | |
1750 | free(minimask); | |
5cb7a798 BP |
1751 | } |
1752 | } | |
1753 | ||
1754 | static void | |
1636c761 | 1755 | test_minimask_has_extra(struct ovs_cmdl_context *ctx OVS_UNUSED) |
5cb7a798 BP |
1756 | { |
1757 | struct flow_wildcards catchall; | |
8fd47924 | 1758 | struct minimask *minicatchall; |
5cb7a798 BP |
1759 | struct flow flow; |
1760 | unsigned int idx; | |
1761 | ||
1762 | flow_wildcards_init_catchall(&catchall); | |
8fd47924 JR |
1763 | minicatchall = minimask_create(&catchall); |
1764 | assert(minimask_is_catchall(minicatchall)); | |
5cb7a798 BP |
1765 | |
1766 | random_set_seed(0x2ec7905b); | |
1767 | for (idx = 0; next_random_flow(&flow, idx); idx++) { | |
1768 | struct flow_wildcards mask; | |
8fd47924 | 1769 | struct minimask *minimask; |
5cb7a798 BP |
1770 | |
1771 | mask.masks = flow; | |
8fd47924 JR |
1772 | minimask = minimask_create(&mask); |
1773 | assert(!minimask_has_extra(minimask, minimask)); | |
1774 | assert(minimask_has_extra(minicatchall, minimask) | |
1775 | == !minimask_is_catchall(minimask)); | |
1776 | if (!minimask_is_catchall(minimask)) { | |
1777 | struct minimask *minimask2; | |
5cb7a798 BP |
1778 | |
1779 | wildcard_extra_bits(&mask); | |
8fd47924 JR |
1780 | minimask2 = minimask_create(&mask); |
1781 | assert(minimask_has_extra(minimask2, minimask)); | |
1782 | assert(!minimask_has_extra(minimask, minimask2)); | |
1783 | free(minimask2); | |
5cb7a798 BP |
1784 | } |
1785 | ||
8fd47924 | 1786 | free(minimask); |
5cb7a798 | 1787 | } |
f2f3f5cb | 1788 | |
8fd47924 | 1789 | free(minicatchall); |
5cb7a798 BP |
1790 | } |
1791 | ||
1792 | static void | |
1636c761 | 1793 | test_minimask_combine(struct ovs_cmdl_context *ctx OVS_UNUSED) |
5cb7a798 BP |
1794 | { |
1795 | struct flow_wildcards catchall; | |
8fd47924 | 1796 | struct minimask *minicatchall; |
5cb7a798 BP |
1797 | struct flow flow; |
1798 | unsigned int idx; | |
1799 | ||
1800 | flow_wildcards_init_catchall(&catchall); | |
8fd47924 JR |
1801 | minicatchall = minimask_create(&catchall); |
1802 | assert(minimask_is_catchall(minicatchall)); | |
5cb7a798 BP |
1803 | |
1804 | random_set_seed(0x181bf0cd); | |
1805 | for (idx = 0; next_random_flow(&flow, idx); idx++) { | |
8fd47924 | 1806 | struct minimask *minimask, *minimask2; |
5cb7a798 | 1807 | struct flow_wildcards mask, mask2, combined, combined2; |
8fd47924 JR |
1808 | struct { |
1809 | struct minimask minicombined; | |
1810 | uint64_t storage[FLOW_U64S]; | |
1811 | } m; | |
5cb7a798 BP |
1812 | struct flow flow2; |
1813 | ||
1814 | mask.masks = flow; | |
8fd47924 | 1815 | minimask = minimask_create(&mask); |
5cb7a798 | 1816 | |
8fd47924 JR |
1817 | minimask_combine(&m.minicombined, minimask, minicatchall, m.storage); |
1818 | assert(minimask_is_catchall(&m.minicombined)); | |
5cb7a798 BP |
1819 | |
1820 | any_random_flow(&flow2); | |
1821 | mask2.masks = flow2; | |
8fd47924 | 1822 | minimask2 = minimask_create(&mask2); |
5cb7a798 | 1823 | |
8fd47924 | 1824 | minimask_combine(&m.minicombined, minimask, minimask2, m.storage); |
368eefac | 1825 | flow_wildcards_and(&combined, &mask, &mask2); |
8fd47924 | 1826 | minimask_expand(&m.minicombined, &combined2); |
5cb7a798 BP |
1827 | assert(flow_wildcards_equal(&combined, &combined2)); |
1828 | ||
8fd47924 JR |
1829 | free(minimask); |
1830 | free(minimask2); | |
5cb7a798 | 1831 | } |
f2f3f5cb | 1832 | |
8fd47924 | 1833 | free(minicatchall); |
5cb7a798 BP |
1834 | } |
1835 | \f | |
1add079e JR |
1836 | |
1837 | static void help(struct ovs_cmdl_context *ctx); | |
1838 | ||
5f383751 | 1839 | static const struct ovs_cmdl_command commands[] = { |
5cb7a798 | 1840 | /* Classifier tests. */ |
1f4a7252 RM |
1841 | {"empty", NULL, 0, 0, test_empty, OVS_RO }, |
1842 | {"destroy-null", NULL, 0, 0, test_destroy_null, OVS_RO }, | |
1843 | {"single-rule", NULL, 0, 0, test_single_rule, OVS_RO }, | |
1844 | {"rule-replacement", NULL, 0, 0, test_rule_replacement, OVS_RO }, | |
1845 | {"many-rules-in-one-list", NULL, 0, 1, test_many_rules_in_one_list, OVS_RO }, | |
1846 | {"many-rules-in-one-table", NULL, 0, 1, test_many_rules_in_one_table, OVS_RO }, | |
1847 | {"many-rules-in-two-tables", NULL, 0, 0, test_many_rules_in_two_tables, OVS_RO }, | |
1848 | {"many-rules-in-five-tables", NULL, 0, 0, test_many_rules_in_five_tables, OVS_RO }, | |
1849 | {"benchmark", NULL, 0, 5, run_benchmarks, OVS_RO }, | |
5cb7a798 BP |
1850 | |
1851 | /* Miniflow and minimask tests. */ | |
1f4a7252 RM |
1852 | {"miniflow", NULL, 0, 0, test_miniflow, OVS_RO }, |
1853 | {"minimask_has_extra", NULL, 0, 0, test_minimask_has_extra, OVS_RO }, | |
1854 | {"minimask_combine", NULL, 0, 0, test_minimask_combine, OVS_RO }, | |
5cb7a798 | 1855 | |
1f4a7252 RM |
1856 | {"--help", NULL, 0, 0, help, OVS_RO }, |
1857 | {NULL, NULL, 0, 0, NULL, OVS_RO }, | |
3223e977 | 1858 | }; |
064af421 | 1859 | |
1add079e JR |
1860 | static void |
1861 | help(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
1862 | { | |
1863 | const struct ovs_cmdl_command *p; | |
1864 | struct ds test_names = DS_EMPTY_INITIALIZER; | |
1865 | const int linesize = 80; | |
1866 | ||
1867 | printf("usage: ovstest %s TEST [TESTARGS]\n" | |
1868 | "where TEST is one of the following:\n\n", | |
1869 | program_name); | |
1870 | ||
1871 | for (p = commands; p->name != NULL; p++) { | |
1872 | if (*p->name != '-') { /* Skip internal commands */ | |
1873 | if (test_names.length > 1 | |
1874 | && test_names.length + strlen(p->name) + 1 >= linesize) { | |
1875 | test_names.length -= 1; | |
1876 | printf ("%s\n", ds_cstr(&test_names)); | |
1877 | ds_clear(&test_names); | |
1878 | } | |
1879 | ds_put_format(&test_names, "%s, ", p->name); | |
1880 | } | |
1881 | } | |
1882 | if (test_names.length > 2) { | |
1883 | test_names.length -= 2; | |
1884 | printf("%s\n", ds_cstr(&test_names)); | |
1885 | } | |
1886 | ds_destroy(&test_names); | |
1887 | } | |
1888 | ||
eadd1644 AZ |
1889 | static void |
1890 | test_classifier_main(int argc, char *argv[]) | |
064af421 | 1891 | { |
1636c761 RB |
1892 | struct ovs_cmdl_context ctx = { |
1893 | .argc = argc - 1, | |
1894 | .argv = argv + 1, | |
1895 | }; | |
b5d97350 | 1896 | set_program_name(argv[0]); |
3bbe9a1f JR |
1897 | |
1898 | if (argc > 1 && !strcmp(argv[1], "--versioned")) { | |
1899 | versioned = true; | |
1900 | ctx.argc--; | |
1901 | ctx.argv++; | |
1902 | } | |
1903 | ||
064af421 | 1904 | init_values(); |
1636c761 | 1905 | ovs_cmdl_run_command(&ctx, commands); |
064af421 | 1906 | } |
eadd1644 AZ |
1907 | |
1908 | OVSTEST_REGISTER("test-classifier", test_classifier_main); |