]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
eadd1644 | 2 | * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014 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> | |
064af421 BP |
29 | #include <errno.h> |
30 | #include <limits.h> | |
10a24935 | 31 | #include "byte-order.h" |
3223e977 | 32 | #include "command-line.h" |
064af421 | 33 | #include "flow.h" |
0596e897 | 34 | #include "ofp-util.h" |
064af421 | 35 | #include "packets.h" |
b028db44 | 36 | #include "random.h" |
c0a56d9f | 37 | #include "unaligned.h" |
eadd1644 | 38 | #include "ovstest.h" |
064af421 BP |
39 | #undef NDEBUG |
40 | #include <assert.h> | |
41 | ||
3d91d909 JR |
42 | /* We need access to classifier internal definitions to be able to fully |
43 | * test them. The alternative would be to expose them all in the classifier | |
44 | * API. */ | |
45 | #include "classifier.c" | |
46 | ||
b5d97350 | 47 | /* Fields in a rule. */ |
d8ae4d67 | 48 | #define CLS_FIELDS \ |
296e07ac JG |
49 | /* struct flow all-caps */ \ |
50 | /* member name name */ \ | |
51 | /* ----------- -------- */ \ | |
52 | CLS_FIELD(tunnel.tun_id, TUN_ID) \ | |
53 | CLS_FIELD(metadata, METADATA) \ | |
54 | CLS_FIELD(nw_src, NW_SRC) \ | |
55 | CLS_FIELD(nw_dst, NW_DST) \ | |
56 | CLS_FIELD(in_port, IN_PORT) \ | |
57 | CLS_FIELD(vlan_tci, VLAN_TCI) \ | |
58 | CLS_FIELD(dl_type, DL_TYPE) \ | |
59 | CLS_FIELD(tp_src, TP_SRC) \ | |
60 | CLS_FIELD(tp_dst, TP_DST) \ | |
61 | CLS_FIELD(dl_src, DL_SRC) \ | |
62 | CLS_FIELD(dl_dst, DL_DST) \ | |
63 | CLS_FIELD(nw_proto, NW_PROTO) \ | |
64 | CLS_FIELD(nw_tos, NW_DSCP) | |
b5d97350 BP |
65 | |
66 | /* Field indexes. | |
67 | * | |
68 | * (These are also indexed into struct classifier's 'tables' array.) */ | |
69 | enum { | |
0bdc4bec | 70 | #define CLS_FIELD(MEMBER, NAME) CLS_F_IDX_##NAME, |
b5d97350 BP |
71 | CLS_FIELDS |
72 | #undef CLS_FIELD | |
73 | CLS_N_FIELDS | |
74 | }; | |
75 | ||
76 | /* Field information. */ | |
77 | struct cls_field { | |
78 | int ofs; /* Offset in struct flow. */ | |
79 | int len; /* Length in bytes. */ | |
b5d97350 BP |
80 | const char *name; /* Name (for debugging). */ |
81 | }; | |
82 | ||
83 | static const struct cls_field cls_fields[CLS_N_FIELDS] = { | |
0bdc4bec | 84 | #define CLS_FIELD(MEMBER, NAME) \ |
b5d97350 BP |
85 | { offsetof(struct flow, MEMBER), \ |
86 | sizeof ((struct flow *)0)->MEMBER, \ | |
b5d97350 BP |
87 | #NAME }, |
88 | CLS_FIELDS | |
89 | #undef CLS_FIELD | |
90 | }; | |
91 | ||
064af421 BP |
92 | struct test_rule { |
93 | int aux; /* Auxiliary data. */ | |
94 | struct cls_rule cls_rule; /* Classifier rule data. */ | |
95 | }; | |
96 | ||
97 | static struct test_rule * | |
98 | test_rule_from_cls_rule(const struct cls_rule *rule) | |
99 | { | |
100 | return rule ? CONTAINER_OF(rule, struct test_rule, cls_rule) : NULL; | |
101 | } | |
102 | ||
f2f3f5cb BP |
103 | static void |
104 | test_rule_destroy(struct test_rule *rule) | |
105 | { | |
106 | if (rule) { | |
107 | cls_rule_destroy(&rule->cls_rule); | |
108 | free(rule); | |
109 | } | |
110 | } | |
111 | ||
48d28ac1 BP |
112 | static struct test_rule *make_rule(int wc_fields, unsigned int priority, |
113 | int value_pat); | |
114 | static void free_rule(struct test_rule *); | |
115 | static struct test_rule *clone_rule(const struct test_rule *); | |
116 | ||
064af421 BP |
117 | /* Trivial (linear) classifier. */ |
118 | struct tcls { | |
119 | size_t n_rules; | |
120 | size_t allocated_rules; | |
121 | struct test_rule **rules; | |
122 | }; | |
123 | ||
124 | static void | |
125 | tcls_init(struct tcls *tcls) | |
126 | { | |
127 | tcls->n_rules = 0; | |
128 | tcls->allocated_rules = 0; | |
129 | tcls->rules = NULL; | |
130 | } | |
131 | ||
132 | static void | |
133 | tcls_destroy(struct tcls *tcls) | |
134 | { | |
135 | if (tcls) { | |
136 | size_t i; | |
137 | ||
138 | for (i = 0; i < tcls->n_rules; i++) { | |
f2f3f5cb | 139 | test_rule_destroy(tcls->rules[i]); |
064af421 BP |
140 | } |
141 | free(tcls->rules); | |
142 | } | |
143 | } | |
144 | ||
064af421 BP |
145 | static bool |
146 | tcls_is_empty(const struct tcls *tcls) | |
147 | { | |
148 | return tcls->n_rules == 0; | |
149 | } | |
150 | ||
151 | static struct test_rule * | |
152 | tcls_insert(struct tcls *tcls, const struct test_rule *rule) | |
153 | { | |
154 | size_t i; | |
155 | ||
064af421 BP |
156 | for (i = 0; i < tcls->n_rules; i++) { |
157 | const struct cls_rule *pos = &tcls->rules[i]->cls_rule; | |
193eb874 BP |
158 | if (cls_rule_equal(pos, &rule->cls_rule)) { |
159 | /* Exact match. */ | |
48d28ac1 BP |
160 | free_rule(tcls->rules[i]); |
161 | tcls->rules[i] = clone_rule(rule); | |
064af421 | 162 | return tcls->rules[i]; |
af7b73f4 | 163 | } else if (pos->priority < rule->cls_rule.priority) { |
064af421 BP |
164 | break; |
165 | } | |
166 | } | |
167 | ||
168 | if (tcls->n_rules >= tcls->allocated_rules) { | |
169 | tcls->rules = x2nrealloc(tcls->rules, &tcls->allocated_rules, | |
170 | sizeof *tcls->rules); | |
171 | } | |
172 | if (i != tcls->n_rules) { | |
173 | memmove(&tcls->rules[i + 1], &tcls->rules[i], | |
174 | sizeof *tcls->rules * (tcls->n_rules - i)); | |
175 | } | |
48d28ac1 | 176 | tcls->rules[i] = clone_rule(rule); |
064af421 BP |
177 | tcls->n_rules++; |
178 | return tcls->rules[i]; | |
179 | } | |
180 | ||
181 | static void | |
182 | tcls_remove(struct tcls *cls, const struct test_rule *rule) | |
183 | { | |
184 | size_t i; | |
185 | ||
186 | for (i = 0; i < cls->n_rules; i++) { | |
187 | struct test_rule *pos = cls->rules[i]; | |
188 | if (pos == rule) { | |
f2f3f5cb BP |
189 | test_rule_destroy(pos); |
190 | ||
064af421 BP |
191 | memmove(&cls->rules[i], &cls->rules[i + 1], |
192 | sizeof *cls->rules * (cls->n_rules - i - 1)); | |
f2f3f5cb | 193 | |
064af421 BP |
194 | cls->n_rules--; |
195 | return; | |
196 | } | |
197 | } | |
428b2edd | 198 | OVS_NOT_REACHED(); |
064af421 BP |
199 | } |
200 | ||
064af421 | 201 | static bool |
5cb7a798 | 202 | match(const struct cls_rule *wild_, const struct flow *fixed) |
064af421 | 203 | { |
5cb7a798 | 204 | struct match wild; |
064af421 BP |
205 | int f_idx; |
206 | ||
5cb7a798 | 207 | minimatch_expand(&wild_->match, &wild); |
064af421 | 208 | for (f_idx = 0; f_idx < CLS_N_FIELDS; f_idx++) { |
d8ae4d67 BP |
209 | bool eq; |
210 | ||
0bdc4bec | 211 | if (f_idx == CLS_F_IDX_NW_SRC) { |
5cb7a798 BP |
212 | eq = !((fixed->nw_src ^ wild.flow.nw_src) |
213 | & wild.wc.masks.nw_src); | |
d8ae4d67 | 214 | } else if (f_idx == CLS_F_IDX_NW_DST) { |
5cb7a798 BP |
215 | eq = !((fixed->nw_dst ^ wild.flow.nw_dst) |
216 | & wild.wc.masks.nw_dst); | |
73f33563 | 217 | } else if (f_idx == CLS_F_IDX_TP_SRC) { |
5cb7a798 BP |
218 | eq = !((fixed->tp_src ^ wild.flow.tp_src) |
219 | & wild.wc.masks.tp_src); | |
73f33563 | 220 | } else if (f_idx == CLS_F_IDX_TP_DST) { |
5cb7a798 BP |
221 | eq = !((fixed->tp_dst ^ wild.flow.tp_dst) |
222 | & wild.wc.masks.tp_dst); | |
73c0ce34 | 223 | } else if (f_idx == CLS_F_IDX_DL_SRC) { |
5cb7a798 BP |
224 | eq = eth_addr_equal_except(fixed->dl_src, wild.flow.dl_src, |
225 | wild.wc.masks.dl_src); | |
73c0ce34 | 226 | } else if (f_idx == CLS_F_IDX_DL_DST) { |
5cb7a798 BP |
227 | eq = eth_addr_equal_except(fixed->dl_dst, wild.flow.dl_dst, |
228 | wild.wc.masks.dl_dst); | |
66642cb4 | 229 | } else if (f_idx == CLS_F_IDX_VLAN_TCI) { |
5cb7a798 BP |
230 | eq = !((fixed->vlan_tci ^ wild.flow.vlan_tci) |
231 | & wild.wc.masks.vlan_tci); | |
8368c090 | 232 | } else if (f_idx == CLS_F_IDX_TUN_ID) { |
296e07ac JG |
233 | eq = !((fixed->tunnel.tun_id ^ wild.flow.tunnel.tun_id) |
234 | & wild.wc.masks.tunnel.tun_id); | |
7525e578 | 235 | } else if (f_idx == CLS_F_IDX_METADATA) { |
5cb7a798 BP |
236 | eq = !((fixed->metadata ^ wild.flow.metadata) |
237 | & wild.wc.masks.metadata); | |
2486e66a | 238 | } else if (f_idx == CLS_F_IDX_NW_DSCP) { |
5cb7a798 BP |
239 | eq = !((fixed->nw_tos ^ wild.flow.nw_tos) & |
240 | (wild.wc.masks.nw_tos & IP_DSCP_MASK)); | |
851d3105 | 241 | } else if (f_idx == CLS_F_IDX_NW_PROTO) { |
5cb7a798 BP |
242 | eq = !((fixed->nw_proto ^ wild.flow.nw_proto) |
243 | & wild.wc.masks.nw_proto); | |
e2170cff | 244 | } else if (f_idx == CLS_F_IDX_DL_TYPE) { |
5cb7a798 BP |
245 | eq = !((fixed->dl_type ^ wild.flow.dl_type) |
246 | & wild.wc.masks.dl_type); | |
0bdc4bec | 247 | } else if (f_idx == CLS_F_IDX_IN_PORT) { |
4e022ec0 AW |
248 | eq = !((fixed->in_port.ofp_port |
249 | ^ wild.flow.in_port.ofp_port) | |
250 | & wild.wc.masks.in_port.ofp_port); | |
d8ae4d67 | 251 | } else { |
428b2edd | 252 | OVS_NOT_REACHED(); |
064af421 BP |
253 | } |
254 | ||
d8ae4d67 BP |
255 | if (!eq) { |
256 | return false; | |
064af421 | 257 | } |
064af421 BP |
258 | } |
259 | return true; | |
260 | } | |
261 | ||
262 | static struct cls_rule * | |
3c4486a5 | 263 | tcls_lookup(const struct tcls *cls, const struct flow *flow) |
064af421 BP |
264 | { |
265 | size_t i; | |
266 | ||
267 | for (i = 0; i < cls->n_rules; i++) { | |
268 | struct test_rule *pos = cls->rules[i]; | |
3c4486a5 | 269 | if (match(&pos->cls_rule, flow)) { |
064af421 BP |
270 | return &pos->cls_rule; |
271 | } | |
272 | } | |
273 | return NULL; | |
274 | } | |
275 | ||
276 | static void | |
3c4486a5 | 277 | tcls_delete_matches(struct tcls *cls, const struct cls_rule *target) |
064af421 BP |
278 | { |
279 | size_t i; | |
280 | ||
281 | for (i = 0; i < cls->n_rules; ) { | |
282 | struct test_rule *pos = cls->rules[i]; | |
5cb7a798 BP |
283 | if (!minimask_has_extra(&pos->cls_rule.match.mask, |
284 | &target->match.mask)) { | |
285 | struct flow flow; | |
286 | ||
287 | miniflow_expand(&pos->cls_rule.match.flow, &flow); | |
288 | if (match(target, &flow)) { | |
289 | tcls_remove(cls, pos); | |
290 | continue; | |
291 | } | |
064af421 | 292 | } |
5cb7a798 | 293 | i++; |
064af421 BP |
294 | } |
295 | } | |
296 | \f | |
3c4486a5 | 297 | static ovs_be32 nw_src_values[] = { CONSTANT_HTONL(0xc0a80001), |
965f03d8 | 298 | CONSTANT_HTONL(0xc0a04455) }; |
3c4486a5 | 299 | static ovs_be32 nw_dst_values[] = { CONSTANT_HTONL(0xc0a80002), |
965f03d8 | 300 | CONSTANT_HTONL(0xc0a04455) }; |
b9298d3f BP |
301 | static ovs_be64 tun_id_values[] = { |
302 | 0, | |
303 | CONSTANT_HTONLL(UINT64_C(0xfedcba9876543210)) }; | |
7525e578 JS |
304 | static ovs_be64 metadata_values[] = { |
305 | 0, | |
306 | CONSTANT_HTONLL(UINT64_C(0xfedcba9876543210)) }; | |
4e022ec0 | 307 | static ofp_port_t in_port_values[] = { OFP_PORT_C(1), OFPP_LOCAL }; |
66642cb4 | 308 | static ovs_be16 vlan_tci_values[] = { CONSTANT_HTONS(101), CONSTANT_HTONS(0) }; |
3c4486a5 | 309 | static ovs_be16 dl_type_values[] |
965f03d8 | 310 | = { CONSTANT_HTONS(ETH_TYPE_IP), CONSTANT_HTONS(ETH_TYPE_ARP) }; |
3c4486a5 | 311 | static ovs_be16 tp_src_values[] = { CONSTANT_HTONS(49362), |
965f03d8 | 312 | CONSTANT_HTONS(80) }; |
3c4486a5 | 313 | static ovs_be16 tp_dst_values[] = { CONSTANT_HTONS(6667), CONSTANT_HTONS(22) }; |
064af421 BP |
314 | static uint8_t dl_src_values[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 }, |
315 | { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } }; | |
316 | static uint8_t dl_dst_values[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 }, | |
317 | { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } }; | |
6767a2cc | 318 | static uint8_t nw_proto_values[] = { IPPROTO_TCP, IPPROTO_ICMP }; |
2486e66a | 319 | static uint8_t nw_dscp_values[] = { 48, 0 }; |
064af421 BP |
320 | |
321 | static void *values[CLS_N_FIELDS][2]; | |
322 | ||
323 | static void | |
324 | init_values(void) | |
325 | { | |
659586ef JG |
326 | values[CLS_F_IDX_TUN_ID][0] = &tun_id_values[0]; |
327 | values[CLS_F_IDX_TUN_ID][1] = &tun_id_values[1]; | |
328 | ||
7525e578 JS |
329 | values[CLS_F_IDX_METADATA][0] = &metadata_values[0]; |
330 | values[CLS_F_IDX_METADATA][1] = &metadata_values[1]; | |
331 | ||
064af421 BP |
332 | values[CLS_F_IDX_IN_PORT][0] = &in_port_values[0]; |
333 | values[CLS_F_IDX_IN_PORT][1] = &in_port_values[1]; | |
334 | ||
66642cb4 BP |
335 | values[CLS_F_IDX_VLAN_TCI][0] = &vlan_tci_values[0]; |
336 | values[CLS_F_IDX_VLAN_TCI][1] = &vlan_tci_values[1]; | |
959a2ecd | 337 | |
064af421 BP |
338 | values[CLS_F_IDX_DL_SRC][0] = dl_src_values[0]; |
339 | values[CLS_F_IDX_DL_SRC][1] = dl_src_values[1]; | |
340 | ||
341 | values[CLS_F_IDX_DL_DST][0] = dl_dst_values[0]; | |
342 | values[CLS_F_IDX_DL_DST][1] = dl_dst_values[1]; | |
343 | ||
344 | values[CLS_F_IDX_DL_TYPE][0] = &dl_type_values[0]; | |
345 | values[CLS_F_IDX_DL_TYPE][1] = &dl_type_values[1]; | |
346 | ||
347 | values[CLS_F_IDX_NW_SRC][0] = &nw_src_values[0]; | |
348 | values[CLS_F_IDX_NW_SRC][1] = &nw_src_values[1]; | |
349 | ||
350 | values[CLS_F_IDX_NW_DST][0] = &nw_dst_values[0]; | |
351 | values[CLS_F_IDX_NW_DST][1] = &nw_dst_values[1]; | |
352 | ||
353 | values[CLS_F_IDX_NW_PROTO][0] = &nw_proto_values[0]; | |
354 | values[CLS_F_IDX_NW_PROTO][1] = &nw_proto_values[1]; | |
355 | ||
2486e66a JP |
356 | values[CLS_F_IDX_NW_DSCP][0] = &nw_dscp_values[0]; |
357 | values[CLS_F_IDX_NW_DSCP][1] = &nw_dscp_values[1]; | |
834377ea | 358 | |
064af421 BP |
359 | values[CLS_F_IDX_TP_SRC][0] = &tp_src_values[0]; |
360 | values[CLS_F_IDX_TP_SRC][1] = &tp_src_values[1]; | |
361 | ||
362 | values[CLS_F_IDX_TP_DST][0] = &tp_dst_values[0]; | |
363 | values[CLS_F_IDX_TP_DST][1] = &tp_dst_values[1]; | |
364 | } | |
365 | ||
366 | #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values) | |
367 | #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values) | |
659586ef | 368 | #define N_TUN_ID_VALUES ARRAY_SIZE(tun_id_values) |
7525e578 | 369 | #define N_METADATA_VALUES ARRAY_SIZE(metadata_values) |
064af421 | 370 | #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values) |
66642cb4 | 371 | #define N_VLAN_TCI_VALUES ARRAY_SIZE(vlan_tci_values) |
064af421 BP |
372 | #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values) |
373 | #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values) | |
374 | #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values) | |
375 | #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values) | |
376 | #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values) | |
377 | #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values) | |
2486e66a | 378 | #define N_NW_DSCP_VALUES ARRAY_SIZE(nw_dscp_values) |
064af421 BP |
379 | |
380 | #define N_FLOW_VALUES (N_NW_SRC_VALUES * \ | |
381 | N_NW_DST_VALUES * \ | |
659586ef | 382 | N_TUN_ID_VALUES * \ |
064af421 | 383 | N_IN_PORT_VALUES * \ |
66642cb4 | 384 | N_VLAN_TCI_VALUES * \ |
064af421 BP |
385 | N_DL_TYPE_VALUES * \ |
386 | N_TP_SRC_VALUES * \ | |
387 | N_TP_DST_VALUES * \ | |
388 | N_DL_SRC_VALUES * \ | |
389 | N_DL_DST_VALUES * \ | |
834377ea | 390 | N_NW_PROTO_VALUES * \ |
2486e66a | 391 | N_NW_DSCP_VALUES) |
064af421 BP |
392 | |
393 | static unsigned int | |
394 | get_value(unsigned int *x, unsigned n_values) | |
395 | { | |
396 | unsigned int rem = *x % n_values; | |
397 | *x /= n_values; | |
398 | return rem; | |
399 | } | |
400 | ||
064af421 BP |
401 | static void |
402 | compare_classifiers(struct classifier *cls, struct tcls *tcls) | |
0b4f2078 | 403 | OVS_REQ_RDLOCK(cls->rwlock) |
064af421 | 404 | { |
70d3fbe7 | 405 | static const int confidence = 500; |
064af421 BP |
406 | unsigned int i; |
407 | ||
408 | assert(classifier_count(cls) == tcls->n_rules); | |
70d3fbe7 | 409 | for (i = 0; i < confidence; i++) { |
476f36e8 | 410 | struct cls_rule *cr0, *cr1, *cr2; |
ae412e7d | 411 | struct flow flow; |
476f36e8 | 412 | struct flow_wildcards wc; |
064af421 | 413 | unsigned int x; |
064af421 | 414 | |
476f36e8 | 415 | flow_wildcards_init_catchall(&wc); |
b028db44 | 416 | x = random_range(N_FLOW_VALUES); |
51c14ddd | 417 | memset(&flow, 0, sizeof flow); |
064af421 BP |
418 | flow.nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)]; |
419 | flow.nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)]; | |
296e07ac | 420 | flow.tunnel.tun_id = tun_id_values[get_value(&x, N_TUN_ID_VALUES)]; |
7525e578 | 421 | flow.metadata = metadata_values[get_value(&x, N_METADATA_VALUES)]; |
4e022ec0 AW |
422 | flow.in_port.ofp_port = in_port_values[get_value(&x, |
423 | N_IN_PORT_VALUES)]; | |
66642cb4 | 424 | flow.vlan_tci = vlan_tci_values[get_value(&x, N_VLAN_TCI_VALUES)]; |
064af421 BP |
425 | flow.dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)]; |
426 | flow.tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)]; | |
427 | flow.tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)]; | |
428 | memcpy(flow.dl_src, dl_src_values[get_value(&x, N_DL_SRC_VALUES)], | |
429 | ETH_ADDR_LEN); | |
430 | memcpy(flow.dl_dst, dl_dst_values[get_value(&x, N_DL_DST_VALUES)], | |
431 | ETH_ADDR_LEN); | |
432 | flow.nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)]; | |
2486e66a | 433 | flow.nw_tos = nw_dscp_values[get_value(&x, N_NW_DSCP_VALUES)]; |
064af421 | 434 | |
c424c2f7 DDP |
435 | /* This assertion is here to suppress a GCC 4.9 array-bounds warning */ |
436 | ovs_assert(cls->cls->n_tries <= CLS_MAX_TRIES); | |
437 | ||
476f36e8 | 438 | cr0 = classifier_lookup(cls, &flow, &wc); |
3c4486a5 BP |
439 | cr1 = tcls_lookup(tcls, &flow); |
440 | assert((cr0 == NULL) == (cr1 == NULL)); | |
441 | if (cr0 != NULL) { | |
442 | const struct test_rule *tr0 = test_rule_from_cls_rule(cr0); | |
443 | const struct test_rule *tr1 = test_rule_from_cls_rule(cr1); | |
444 | ||
193eb874 | 445 | assert(cls_rule_equal(cr0, cr1)); |
3c4486a5 | 446 | assert(tr0->aux == tr1->aux); |
064af421 | 447 | } |
476f36e8 JR |
448 | cr2 = classifier_lookup(cls, &flow, NULL); |
449 | assert(cr2 == cr0); | |
064af421 BP |
450 | } |
451 | } | |
452 | ||
064af421 BP |
453 | static void |
454 | destroy_classifier(struct classifier *cls) | |
455 | { | |
5ecc9d81 BP |
456 | struct test_rule *rule, *next_rule; |
457 | struct cls_cursor cursor; | |
458 | ||
06f81620 | 459 | fat_rwlock_wrlock(&cls->rwlock); |
5ecc9d81 BP |
460 | cls_cursor_init(&cursor, cls, NULL); |
461 | CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cls_rule, &cursor) { | |
462 | classifier_remove(cls, &rule->cls_rule); | |
48d28ac1 | 463 | free_rule(rule); |
5ecc9d81 | 464 | } |
06f81620 | 465 | fat_rwlock_unlock(&cls->rwlock); |
064af421 BP |
466 | classifier_destroy(cls); |
467 | } | |
468 | ||
fe7cfa5c JR |
469 | static void |
470 | pvector_verify(struct pvector *pvec) | |
471 | { | |
472 | void *ptr OVS_UNUSED; | |
473 | unsigned int priority, prev_priority = UINT_MAX; | |
474 | ||
475 | PVECTOR_FOR_EACH (ptr, pvec) { | |
476 | priority = cursor__.vector[cursor__.entry_idx].priority; | |
477 | if (priority > prev_priority) { | |
478 | VLOG_ABORT("Priority vector is out of order (%u > %u)", | |
479 | priority, prev_priority); | |
480 | } | |
481 | prev_priority = priority; | |
482 | } | |
483 | } | |
484 | ||
064af421 | 485 | static void |
0b4f2078 EJ |
486 | check_tables(const struct classifier *cls, int n_tables, int n_rules, |
487 | int n_dups) OVS_REQ_RDLOCK(cls->rwlock) | |
064af421 | 488 | { |
03868246 | 489 | const struct cls_subtable *table; |
955f579d BP |
490 | struct test_rule *test_rule; |
491 | struct cls_cursor cursor; | |
064af421 | 492 | int found_tables = 0; |
064af421 | 493 | int found_rules = 0; |
b5d97350 | 494 | int found_dups = 0; |
955f579d | 495 | int found_rules2 = 0; |
064af421 | 496 | |
fe7cfa5c JR |
497 | pvector_verify(&cls->cls->subtables); |
498 | ||
f2c21402 | 499 | CMAP_FOR_EACH (table, cmap_node, &cls->cls->subtables_map) { |
627fb667 | 500 | const struct cls_match *head; |
4d935a6b JR |
501 | unsigned int max_priority = 0; |
502 | unsigned int max_count = 0; | |
fe7cfa5c JR |
503 | bool found = false; |
504 | const struct cls_subtable *iter; | |
505 | ||
506 | /* Locate the subtable from 'subtables'. */ | |
507 | PVECTOR_FOR_EACH (iter, &cls->cls->subtables) { | |
508 | if (iter == table) { | |
509 | if (found) { | |
510 | VLOG_ABORT("Subtable %p duplicated in 'subtables'.", | |
511 | table); | |
512 | } | |
513 | found = true; | |
514 | } | |
515 | } | |
516 | if (!found) { | |
517 | VLOG_ABORT("Subtable %p not found from 'subtables'.", table); | |
518 | } | |
b5d97350 | 519 | |
f2c21402 | 520 | assert(!cmap_is_empty(&table->rules)); |
064af421 | 521 | |
064af421 | 522 | found_tables++; |
f2c21402 | 523 | CMAP_FOR_EACH (head, cmap_node, &table->rules) { |
b5d97350 | 524 | unsigned int prev_priority = UINT_MAX; |
627fb667 | 525 | const struct cls_match *rule; |
b5d97350 | 526 | |
4d935a6b JR |
527 | if (head->priority > max_priority) { |
528 | max_priority = head->priority; | |
529 | max_count = 1; | |
530 | } else if (head->priority == max_priority) { | |
531 | ++max_count; | |
532 | } | |
533 | ||
b5d97350 BP |
534 | found_rules++; |
535 | LIST_FOR_EACH (rule, list, &head->list) { | |
536 | assert(rule->priority < prev_priority); | |
4d935a6b JR |
537 | assert(rule->priority <= table->max_priority); |
538 | ||
b5d97350 BP |
539 | prev_priority = rule->priority; |
540 | found_rules++; | |
541 | found_dups++; | |
627fb667 JR |
542 | assert(classifier_find_rule_exactly(cls, rule->cls_rule) |
543 | == rule->cls_rule); | |
b5d97350 BP |
544 | } |
545 | } | |
4d935a6b JR |
546 | assert(table->max_priority == max_priority); |
547 | assert(table->max_count == max_count); | |
064af421 BP |
548 | } |
549 | ||
f2c21402 | 550 | assert(found_tables == cmap_count(&cls->cls->subtables_map)); |
fe7cfa5c | 551 | assert(found_tables == pvector_count(&cls->cls->subtables)); |
f2c21402 | 552 | assert(n_tables == -1 || n_tables == cmap_count(&cls->cls->subtables_map)); |
064af421 | 553 | assert(n_rules == -1 || found_rules == n_rules); |
b5d97350 | 554 | assert(n_dups == -1 || found_dups == n_dups); |
955f579d BP |
555 | |
556 | cls_cursor_init(&cursor, cls, NULL); | |
557 | CLS_CURSOR_FOR_EACH (test_rule, cls_rule, &cursor) { | |
558 | found_rules2++; | |
559 | } | |
560 | assert(found_rules == found_rules2); | |
064af421 BP |
561 | } |
562 | ||
563 | static struct test_rule * | |
564 | make_rule(int wc_fields, unsigned int priority, int value_pat) | |
565 | { | |
566 | const struct cls_field *f; | |
567 | struct test_rule *rule; | |
81a76618 | 568 | struct match match; |
064af421 | 569 | |
81a76618 | 570 | match_init_catchall(&match); |
064af421 BP |
571 | for (f = &cls_fields[0]; f < &cls_fields[CLS_N_FIELDS]; f++) { |
572 | int f_idx = f - cls_fields; | |
d8ae4d67 | 573 | int value_idx = (value_pat & (1u << f_idx)) != 0; |
81a76618 | 574 | memcpy((char *) &match.flow + f->ofs, |
d8ae4d67 BP |
575 | values[f_idx][value_idx], f->len); |
576 | ||
0bdc4bec | 577 | if (f_idx == CLS_F_IDX_NW_SRC) { |
b8266395 | 578 | match.wc.masks.nw_src = OVS_BE32_MAX; |
d8ae4d67 | 579 | } else if (f_idx == CLS_F_IDX_NW_DST) { |
b8266395 | 580 | match.wc.masks.nw_dst = OVS_BE32_MAX; |
73f33563 | 581 | } else if (f_idx == CLS_F_IDX_TP_SRC) { |
b8266395 | 582 | match.wc.masks.tp_src = OVS_BE16_MAX; |
73f33563 | 583 | } else if (f_idx == CLS_F_IDX_TP_DST) { |
b8266395 | 584 | match.wc.masks.tp_dst = OVS_BE16_MAX; |
73c0ce34 | 585 | } else if (f_idx == CLS_F_IDX_DL_SRC) { |
81a76618 | 586 | memset(match.wc.masks.dl_src, 0xff, ETH_ADDR_LEN); |
73c0ce34 | 587 | } else if (f_idx == CLS_F_IDX_DL_DST) { |
81a76618 | 588 | memset(match.wc.masks.dl_dst, 0xff, ETH_ADDR_LEN); |
66642cb4 | 589 | } else if (f_idx == CLS_F_IDX_VLAN_TCI) { |
b8266395 | 590 | match.wc.masks.vlan_tci = OVS_BE16_MAX; |
8368c090 | 591 | } else if (f_idx == CLS_F_IDX_TUN_ID) { |
b8266395 | 592 | match.wc.masks.tunnel.tun_id = OVS_BE64_MAX; |
7525e578 | 593 | } else if (f_idx == CLS_F_IDX_METADATA) { |
b8266395 | 594 | match.wc.masks.metadata = OVS_BE64_MAX; |
5d9499c4 | 595 | } else if (f_idx == CLS_F_IDX_NW_DSCP) { |
81a76618 | 596 | match.wc.masks.nw_tos |= IP_DSCP_MASK; |
851d3105 | 597 | } else if (f_idx == CLS_F_IDX_NW_PROTO) { |
81a76618 | 598 | match.wc.masks.nw_proto = UINT8_MAX; |
e2170cff | 599 | } else if (f_idx == CLS_F_IDX_DL_TYPE) { |
b8266395 | 600 | match.wc.masks.dl_type = OVS_BE16_MAX; |
0bdc4bec | 601 | } else if (f_idx == CLS_F_IDX_IN_PORT) { |
e2711da9 | 602 | match.wc.masks.in_port.ofp_port = u16_to_ofp(UINT16_MAX); |
064af421 | 603 | } else { |
428b2edd | 604 | OVS_NOT_REACHED(); |
064af421 BP |
605 | } |
606 | } | |
81a76618 BP |
607 | |
608 | rule = xzalloc(sizeof *rule); | |
609 | cls_rule_init(&rule->cls_rule, &match, wc_fields ? priority : UINT_MAX); | |
064af421 BP |
610 | return rule; |
611 | } | |
612 | ||
48d28ac1 BP |
613 | static struct test_rule * |
614 | clone_rule(const struct test_rule *src) | |
615 | { | |
616 | struct test_rule *dst; | |
617 | ||
618 | dst = xmalloc(sizeof *dst); | |
619 | dst->aux = src->aux; | |
620 | cls_rule_clone(&dst->cls_rule, &src->cls_rule); | |
621 | return dst; | |
622 | } | |
623 | ||
624 | static void | |
625 | free_rule(struct test_rule *rule) | |
626 | { | |
627 | cls_rule_destroy(&rule->cls_rule); | |
628 | free(rule); | |
629 | } | |
630 | ||
064af421 BP |
631 | static void |
632 | shuffle(unsigned int *p, size_t n) | |
633 | { | |
634 | for (; n > 1; n--, p++) { | |
b028db44 | 635 | unsigned int *q = &p[random_range(n)]; |
064af421 BP |
636 | unsigned int tmp = *p; |
637 | *p = *q; | |
638 | *q = tmp; | |
639 | } | |
640 | } | |
5cb7a798 BP |
641 | |
642 | static void | |
643 | shuffle_u32s(uint32_t *p, size_t n) | |
644 | { | |
645 | for (; n > 1; n--, p++) { | |
b028db44 | 646 | uint32_t *q = &p[random_range(n)]; |
5cb7a798 BP |
647 | uint32_t tmp = *p; |
648 | *p = *q; | |
649 | *q = tmp; | |
650 | } | |
651 | } | |
064af421 | 652 | \f |
5cb7a798 BP |
653 | /* Classifier tests. */ |
654 | ||
13751fd8 JR |
655 | static enum mf_field_id trie_fields[2] = { |
656 | MFF_IPV4_DST, MFF_IPV4_SRC | |
657 | }; | |
658 | ||
064af421 BP |
659 | /* Tests an empty classifier. */ |
660 | static void | |
3223e977 | 661 | test_empty(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
662 | { |
663 | struct classifier cls; | |
664 | struct tcls tcls; | |
665 | ||
476f36e8 | 666 | classifier_init(&cls, flow_segment_u32s); |
06f81620 | 667 | fat_rwlock_wrlock(&cls.rwlock); |
13751fd8 | 668 | classifier_set_prefix_fields(&cls, trie_fields, ARRAY_SIZE(trie_fields)); |
064af421 BP |
669 | tcls_init(&tcls); |
670 | assert(classifier_is_empty(&cls)); | |
671 | assert(tcls_is_empty(&tcls)); | |
672 | compare_classifiers(&cls, &tcls); | |
06f81620 | 673 | fat_rwlock_unlock(&cls.rwlock); |
064af421 BP |
674 | classifier_destroy(&cls); |
675 | tcls_destroy(&tcls); | |
676 | } | |
677 | ||
678 | /* Destroys a null classifier. */ | |
679 | static void | |
3223e977 | 680 | test_destroy_null(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
681 | { |
682 | classifier_destroy(NULL); | |
683 | } | |
684 | ||
685 | /* Tests classification with one rule at a time. */ | |
686 | static void | |
3223e977 | 687 | test_single_rule(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
688 | { |
689 | unsigned int wc_fields; /* Hilarious. */ | |
690 | ||
691 | for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) { | |
692 | struct classifier cls; | |
693 | struct test_rule *rule, *tcls_rule; | |
694 | struct tcls tcls; | |
695 | ||
696 | rule = make_rule(wc_fields, | |
697 | hash_bytes(&wc_fields, sizeof wc_fields, 0), 0); | |
698 | ||
476f36e8 | 699 | classifier_init(&cls, flow_segment_u32s); |
06f81620 | 700 | fat_rwlock_wrlock(&cls.rwlock); |
13751fd8 JR |
701 | classifier_set_prefix_fields(&cls, trie_fields, |
702 | ARRAY_SIZE(trie_fields)); | |
064af421 BP |
703 | tcls_init(&tcls); |
704 | ||
705 | tcls_rule = tcls_insert(&tcls, rule); | |
08944c1d | 706 | classifier_insert(&cls, &rule->cls_rule); |
b5d97350 | 707 | check_tables(&cls, 1, 1, 0); |
064af421 BP |
708 | compare_classifiers(&cls, &tcls); |
709 | ||
710 | classifier_remove(&cls, &rule->cls_rule); | |
711 | tcls_remove(&tcls, tcls_rule); | |
712 | assert(classifier_is_empty(&cls)); | |
713 | assert(tcls_is_empty(&tcls)); | |
714 | compare_classifiers(&cls, &tcls); | |
715 | ||
48d28ac1 | 716 | free_rule(rule); |
06f81620 | 717 | fat_rwlock_unlock(&cls.rwlock); |
064af421 BP |
718 | classifier_destroy(&cls); |
719 | tcls_destroy(&tcls); | |
720 | } | |
721 | } | |
722 | ||
723 | /* Tests replacing one rule by another. */ | |
724 | static void | |
3223e977 | 725 | test_rule_replacement(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
726 | { |
727 | unsigned int wc_fields; | |
728 | ||
729 | for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) { | |
730 | struct classifier cls; | |
f0f4410a BP |
731 | struct test_rule *rule1; |
732 | struct test_rule *rule2; | |
064af421 BP |
733 | struct tcls tcls; |
734 | ||
735 | rule1 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX); | |
736 | rule2 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX); | |
737 | rule2->aux += 5; | |
738 | rule2->aux += 5; | |
739 | ||
476f36e8 | 740 | classifier_init(&cls, flow_segment_u32s); |
06f81620 | 741 | fat_rwlock_wrlock(&cls.rwlock); |
13751fd8 JR |
742 | classifier_set_prefix_fields(&cls, trie_fields, |
743 | ARRAY_SIZE(trie_fields)); | |
064af421 | 744 | tcls_init(&tcls); |
f0f4410a | 745 | tcls_insert(&tcls, rule1); |
08944c1d | 746 | classifier_insert(&cls, &rule1->cls_rule); |
b5d97350 | 747 | check_tables(&cls, 1, 1, 0); |
064af421 BP |
748 | compare_classifiers(&cls, &tcls); |
749 | tcls_destroy(&tcls); | |
750 | ||
751 | tcls_init(&tcls); | |
f0f4410a | 752 | tcls_insert(&tcls, rule2); |
064af421 | 753 | assert(test_rule_from_cls_rule( |
08944c1d | 754 | classifier_replace(&cls, &rule2->cls_rule)) == rule1); |
48d28ac1 | 755 | free_rule(rule1); |
b5d97350 | 756 | check_tables(&cls, 1, 1, 0); |
064af421 BP |
757 | compare_classifiers(&cls, &tcls); |
758 | tcls_destroy(&tcls); | |
06f81620 | 759 | fat_rwlock_unlock(&cls.rwlock); |
064af421 BP |
760 | destroy_classifier(&cls); |
761 | } | |
762 | } | |
763 | ||
764 | static int | |
b5d97350 | 765 | factorial(int n_items) |
064af421 | 766 | { |
b5d97350 BP |
767 | int n, i; |
768 | ||
769 | n = 1; | |
770 | for (i = 2; i <= n_items; i++) { | |
771 | n *= i; | |
772 | } | |
773 | return n; | |
064af421 BP |
774 | } |
775 | ||
b5d97350 BP |
776 | static void |
777 | swap(int *a, int *b) | |
064af421 | 778 | { |
b5d97350 BP |
779 | int tmp = *a; |
780 | *a = *b; | |
781 | *b = tmp; | |
064af421 BP |
782 | } |
783 | ||
064af421 | 784 | static void |
b5d97350 | 785 | reverse(int *a, int n) |
064af421 | 786 | { |
b5d97350 | 787 | int i; |
064af421 | 788 | |
b5d97350 BP |
789 | for (i = 0; i < n / 2; i++) { |
790 | int j = n - (i + 1); | |
791 | swap(&a[i], &a[j]); | |
792 | } | |
793 | } | |
064af421 | 794 | |
b5d97350 BP |
795 | static bool |
796 | next_permutation(int *a, int n) | |
797 | { | |
798 | int k; | |
064af421 | 799 | |
b5d97350 BP |
800 | for (k = n - 2; k >= 0; k--) { |
801 | if (a[k] < a[k + 1]) { | |
802 | int l; | |
064af421 | 803 | |
b5d97350 BP |
804 | for (l = n - 1; ; l--) { |
805 | if (a[l] > a[k]) { | |
806 | swap(&a[k], &a[l]); | |
807 | reverse(a + (k + 1), n - (k + 1)); | |
808 | return true; | |
064af421 BP |
809 | } |
810 | } | |
811 | } | |
812 | } | |
b5d97350 | 813 | return false; |
064af421 BP |
814 | } |
815 | ||
b5d97350 | 816 | /* Tests classification with rules that have the same matching criteria. */ |
064af421 | 817 | static void |
b5d97350 BP |
818 | test_many_rules_in_one_list (int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
819 | { | |
820 | enum { N_RULES = 3 }; | |
821 | int n_pris; | |
064af421 | 822 | |
b5d97350 BP |
823 | for (n_pris = N_RULES; n_pris >= 1; n_pris--) { |
824 | int ops[N_RULES * 2]; | |
825 | int pris[N_RULES]; | |
826 | int n_permutations; | |
827 | int i; | |
064af421 | 828 | |
b5d97350 BP |
829 | pris[0] = 0; |
830 | for (i = 1; i < N_RULES; i++) { | |
831 | pris[i] = pris[i - 1] + (n_pris > i); | |
832 | } | |
064af421 | 833 | |
b5d97350 BP |
834 | for (i = 0; i < N_RULES * 2; i++) { |
835 | ops[i] = i / 2; | |
064af421 | 836 | } |
064af421 | 837 | |
b5d97350 BP |
838 | n_permutations = 0; |
839 | do { | |
840 | struct test_rule *rules[N_RULES]; | |
841 | struct test_rule *tcls_rules[N_RULES]; | |
842 | int pri_rules[N_RULES]; | |
843 | struct classifier cls; | |
844 | struct tcls tcls; | |
064af421 | 845 | |
b5d97350 | 846 | n_permutations++; |
064af421 | 847 | |
b5d97350 BP |
848 | for (i = 0; i < N_RULES; i++) { |
849 | rules[i] = make_rule(456, pris[i], 0); | |
850 | tcls_rules[i] = NULL; | |
851 | pri_rules[i] = -1; | |
852 | } | |
064af421 | 853 | |
476f36e8 | 854 | classifier_init(&cls, flow_segment_u32s); |
06f81620 | 855 | fat_rwlock_wrlock(&cls.rwlock); |
13751fd8 JR |
856 | classifier_set_prefix_fields(&cls, trie_fields, |
857 | ARRAY_SIZE(trie_fields)); | |
b5d97350 | 858 | tcls_init(&tcls); |
064af421 | 859 | |
b5d97350 BP |
860 | for (i = 0; i < ARRAY_SIZE(ops); i++) { |
861 | int j = ops[i]; | |
862 | int m, n; | |
064af421 | 863 | |
b5d97350 BP |
864 | if (!tcls_rules[j]) { |
865 | struct test_rule *displaced_rule; | |
866 | ||
867 | tcls_rules[j] = tcls_insert(&tcls, rules[j]); | |
868 | displaced_rule = test_rule_from_cls_rule( | |
08944c1d | 869 | classifier_replace(&cls, &rules[j]->cls_rule)); |
b5d97350 BP |
870 | if (pri_rules[pris[j]] >= 0) { |
871 | int k = pri_rules[pris[j]]; | |
872 | assert(displaced_rule != NULL); | |
873 | assert(displaced_rule != rules[j]); | |
874 | assert(pris[j] == displaced_rule->cls_rule.priority); | |
875 | tcls_rules[k] = NULL; | |
876 | } else { | |
877 | assert(displaced_rule == NULL); | |
878 | } | |
879 | pri_rules[pris[j]] = j; | |
880 | } else { | |
881 | classifier_remove(&cls, &rules[j]->cls_rule); | |
882 | tcls_remove(&tcls, tcls_rules[j]); | |
883 | tcls_rules[j] = NULL; | |
884 | pri_rules[pris[j]] = -1; | |
885 | } | |
064af421 | 886 | |
b5d97350 BP |
887 | n = 0; |
888 | for (m = 0; m < N_RULES; m++) { | |
889 | n += tcls_rules[m] != NULL; | |
064af421 | 890 | } |
b5d97350 BP |
891 | check_tables(&cls, n > 0, n, n - 1); |
892 | ||
893 | compare_classifiers(&cls, &tcls); | |
064af421 | 894 | } |
b5d97350 | 895 | |
b5d97350 | 896 | for (i = 0; i < N_RULES; i++) { |
627fb667 JR |
897 | if (rules[i]->cls_rule.cls_match) { |
898 | classifier_remove(&cls, &rules[i]->cls_rule); | |
899 | } | |
48d28ac1 | 900 | free_rule(rules[i]); |
b5d97350 | 901 | } |
627fb667 JR |
902 | |
903 | fat_rwlock_unlock(&cls.rwlock); | |
904 | classifier_destroy(&cls); | |
905 | tcls_destroy(&tcls); | |
b5d97350 BP |
906 | } while (next_permutation(ops, ARRAY_SIZE(ops))); |
907 | assert(n_permutations == (factorial(N_RULES * 2) >> N_RULES)); | |
064af421 BP |
908 | } |
909 | } | |
910 | ||
b5d97350 BP |
911 | static int |
912 | count_ones(unsigned long int x) | |
064af421 | 913 | { |
b5d97350 | 914 | int n = 0; |
064af421 | 915 | |
b5d97350 | 916 | while (x) { |
8472a3ce | 917 | x = zero_rightmost_1bit(x); |
b5d97350 BP |
918 | n++; |
919 | } | |
064af421 | 920 | |
b5d97350 BP |
921 | return n; |
922 | } | |
064af421 | 923 | |
b5d97350 BP |
924 | static bool |
925 | array_contains(int *array, int n, int value) | |
926 | { | |
927 | int i; | |
064af421 | 928 | |
b5d97350 BP |
929 | for (i = 0; i < n; i++) { |
930 | if (array[i] == value) { | |
931 | return true; | |
064af421 BP |
932 | } |
933 | } | |
b5d97350 BP |
934 | |
935 | return false; | |
064af421 BP |
936 | } |
937 | ||
b5d97350 BP |
938 | /* Tests classification with two rules at a time that fall into the same |
939 | * table but different lists. */ | |
064af421 | 940 | static void |
3223e977 | 941 | test_many_rules_in_one_table(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 | 942 | { |
b5d97350 | 943 | int iteration; |
064af421 | 944 | |
b5d97350 BP |
945 | for (iteration = 0; iteration < 50; iteration++) { |
946 | enum { N_RULES = 20 }; | |
947 | struct test_rule *rules[N_RULES]; | |
948 | struct test_rule *tcls_rules[N_RULES]; | |
949 | struct classifier cls; | |
950 | struct tcls tcls; | |
951 | int value_pats[N_RULES]; | |
952 | int value_mask; | |
953 | int wcf; | |
954 | int i; | |
064af421 | 955 | |
b5d97350 | 956 | do { |
b028db44 | 957 | wcf = random_uint32() & ((1u << CLS_N_FIELDS) - 1); |
b5d97350 BP |
958 | value_mask = ~wcf & ((1u << CLS_N_FIELDS) - 1); |
959 | } while ((1 << count_ones(value_mask)) < N_RULES); | |
064af421 | 960 | |
476f36e8 | 961 | classifier_init(&cls, flow_segment_u32s); |
06f81620 | 962 | fat_rwlock_wrlock(&cls.rwlock); |
13751fd8 JR |
963 | classifier_set_prefix_fields(&cls, trie_fields, |
964 | ARRAY_SIZE(trie_fields)); | |
b5d97350 | 965 | tcls_init(&tcls); |
064af421 | 966 | |
b5d97350 | 967 | for (i = 0; i < N_RULES; i++) { |
b028db44 | 968 | unsigned int priority = random_uint32(); |
064af421 | 969 | |
b5d97350 | 970 | do { |
b028db44 | 971 | value_pats[i] = random_uint32() & value_mask; |
b5d97350 | 972 | } while (array_contains(value_pats, i, value_pats[i])); |
064af421 | 973 | |
b5d97350 BP |
974 | rules[i] = make_rule(wcf, priority, value_pats[i]); |
975 | tcls_rules[i] = tcls_insert(&tcls, rules[i]); | |
08944c1d | 976 | classifier_insert(&cls, &rules[i]->cls_rule); |
b5d97350 BP |
977 | |
978 | check_tables(&cls, 1, i + 1, 0); | |
979 | compare_classifiers(&cls, &tcls); | |
980 | } | |
981 | ||
982 | for (i = 0; i < N_RULES; i++) { | |
983 | tcls_remove(&tcls, tcls_rules[i]); | |
984 | classifier_remove(&cls, &rules[i]->cls_rule); | |
48d28ac1 | 985 | free_rule(rules[i]); |
b5d97350 BP |
986 | |
987 | check_tables(&cls, i < N_RULES - 1, N_RULES - (i + 1), 0); | |
988 | compare_classifiers(&cls, &tcls); | |
064af421 | 989 | } |
b5d97350 | 990 | |
06f81620 | 991 | fat_rwlock_unlock(&cls.rwlock); |
b5d97350 BP |
992 | classifier_destroy(&cls); |
993 | tcls_destroy(&tcls); | |
064af421 BP |
994 | } |
995 | } | |
996 | ||
b5d97350 BP |
997 | /* Tests classification with many rules at a time that fall into random lists |
998 | * in 'n' tables. */ | |
064af421 | 999 | static void |
b5d97350 | 1000 | test_many_rules_in_n_tables(int n_tables) |
064af421 BP |
1001 | { |
1002 | enum { MAX_RULES = 50 }; | |
b5d97350 | 1003 | int wcfs[10]; |
064af421 | 1004 | int iteration; |
b5d97350 BP |
1005 | int i; |
1006 | ||
1007 | assert(n_tables < 10); | |
1008 | for (i = 0; i < n_tables; i++) { | |
1009 | do { | |
b028db44 | 1010 | wcfs[i] = random_uint32() & ((1u << CLS_N_FIELDS) - 1); |
b5d97350 BP |
1011 | } while (array_contains(wcfs, i, wcfs[i])); |
1012 | } | |
064af421 BP |
1013 | |
1014 | for (iteration = 0; iteration < 30; iteration++) { | |
1015 | unsigned int priorities[MAX_RULES]; | |
1016 | struct classifier cls; | |
1017 | struct tcls tcls; | |
064af421 | 1018 | |
b028db44 | 1019 | random_set_seed(iteration + 1); |
064af421 BP |
1020 | for (i = 0; i < MAX_RULES; i++) { |
1021 | priorities[i] = i * 129; | |
1022 | } | |
1023 | shuffle(priorities, ARRAY_SIZE(priorities)); | |
1024 | ||
476f36e8 | 1025 | classifier_init(&cls, flow_segment_u32s); |
06f81620 | 1026 | fat_rwlock_wrlock(&cls.rwlock); |
13751fd8 JR |
1027 | classifier_set_prefix_fields(&cls, trie_fields, |
1028 | ARRAY_SIZE(trie_fields)); | |
064af421 BP |
1029 | tcls_init(&tcls); |
1030 | ||
1031 | for (i = 0; i < MAX_RULES; i++) { | |
1032 | struct test_rule *rule; | |
1033 | unsigned int priority = priorities[i]; | |
b028db44 BP |
1034 | int wcf = wcfs[random_range(n_tables)]; |
1035 | int value_pat = random_uint32() & ((1u << CLS_N_FIELDS) - 1); | |
064af421 BP |
1036 | rule = make_rule(wcf, priority, value_pat); |
1037 | tcls_insert(&tcls, rule); | |
08944c1d | 1038 | classifier_insert(&cls, &rule->cls_rule); |
b5d97350 | 1039 | check_tables(&cls, -1, i + 1, -1); |
064af421 BP |
1040 | compare_classifiers(&cls, &tcls); |
1041 | } | |
1042 | ||
1043 | while (!classifier_is_empty(&cls)) { | |
5ecc9d81 BP |
1044 | struct test_rule *rule, *next_rule; |
1045 | struct test_rule *target; | |
1046 | struct cls_cursor cursor; | |
1047 | ||
b028db44 | 1048 | target = clone_rule(tcls.rules[random_range(tcls.n_rules)]); |
5ecc9d81 BP |
1049 | |
1050 | cls_cursor_init(&cursor, &cls, &target->cls_rule); | |
1051 | CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cls_rule, &cursor) { | |
1052 | classifier_remove(&cls, &rule->cls_rule); | |
48d28ac1 | 1053 | free_rule(rule); |
5ecc9d81 BP |
1054 | } |
1055 | tcls_delete_matches(&tcls, &target->cls_rule); | |
064af421 | 1056 | compare_classifiers(&cls, &tcls); |
b5d97350 | 1057 | check_tables(&cls, -1, -1, -1); |
48d28ac1 | 1058 | free_rule(target); |
064af421 | 1059 | } |
064af421 | 1060 | |
06f81620 | 1061 | fat_rwlock_unlock(&cls.rwlock); |
064af421 BP |
1062 | destroy_classifier(&cls); |
1063 | tcls_destroy(&tcls); | |
1064 | } | |
1065 | } | |
b5d97350 BP |
1066 | |
1067 | static void | |
1068 | test_many_rules_in_two_tables(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
1069 | { | |
1070 | test_many_rules_in_n_tables(2); | |
1071 | } | |
1072 | ||
1073 | static void | |
1074 | test_many_rules_in_five_tables(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
1075 | { | |
1076 | test_many_rules_in_n_tables(5); | |
1077 | } | |
064af421 | 1078 | \f |
5cb7a798 BP |
1079 | /* Miniflow tests. */ |
1080 | ||
1081 | static uint32_t | |
1082 | random_value(void) | |
1083 | { | |
1084 | static const uint32_t values[] = | |
1085 | { 0xffffffff, 0xaaaaaaaa, 0x55555555, 0x80000000, | |
1086 | 0x00000001, 0xface0000, 0x00d00d1e, 0xdeadbeef }; | |
1087 | ||
b028db44 | 1088 | return values[random_range(ARRAY_SIZE(values))]; |
5cb7a798 BP |
1089 | } |
1090 | ||
1091 | static bool | |
1092 | choose(unsigned int n, unsigned int *idxp) | |
1093 | { | |
1094 | if (*idxp < n) { | |
1095 | return true; | |
1096 | } else { | |
1097 | *idxp -= n; | |
1098 | return false; | |
1099 | } | |
1100 | } | |
1101 | ||
1102 | static bool | |
1103 | init_consecutive_values(int n_consecutive, struct flow *flow, | |
1104 | unsigned int *idxp) | |
1105 | { | |
1106 | uint32_t *flow_u32 = (uint32_t *) flow; | |
1107 | ||
1108 | if (choose(FLOW_U32S - n_consecutive + 1, idxp)) { | |
1109 | int i; | |
1110 | ||
1111 | for (i = 0; i < n_consecutive; i++) { | |
1112 | flow_u32[*idxp + i] = random_value(); | |
1113 | } | |
1114 | return true; | |
1115 | } else { | |
1116 | return false; | |
1117 | } | |
1118 | } | |
1119 | ||
1120 | static bool | |
1121 | next_random_flow(struct flow *flow, unsigned int idx) | |
1122 | { | |
1123 | uint32_t *flow_u32 = (uint32_t *) flow; | |
1124 | int i; | |
1125 | ||
1126 | memset(flow, 0, sizeof *flow); | |
1127 | ||
1128 | /* Empty flow. */ | |
1129 | if (choose(1, &idx)) { | |
1130 | return true; | |
1131 | } | |
1132 | ||
1133 | /* All flows with a small number of consecutive nonzero values. */ | |
1134 | for (i = 1; i <= 4; i++) { | |
1135 | if (init_consecutive_values(i, flow, &idx)) { | |
1136 | return true; | |
1137 | } | |
1138 | } | |
1139 | ||
1140 | /* All flows with a large number of consecutive nonzero values. */ | |
1141 | for (i = FLOW_U32S - 4; i <= FLOW_U32S; i++) { | |
1142 | if (init_consecutive_values(i, flow, &idx)) { | |
1143 | return true; | |
1144 | } | |
1145 | } | |
1146 | ||
1147 | /* All flows with exactly two nonconsecutive nonzero values. */ | |
1148 | if (choose((FLOW_U32S - 1) * (FLOW_U32S - 2) / 2, &idx)) { | |
1149 | int ofs1; | |
1150 | ||
1151 | for (ofs1 = 0; ofs1 < FLOW_U32S - 2; ofs1++) { | |
1152 | int ofs2; | |
1153 | ||
1154 | for (ofs2 = ofs1 + 2; ofs2 < FLOW_U32S; ofs2++) { | |
1155 | if (choose(1, &idx)) { | |
1156 | flow_u32[ofs1] = random_value(); | |
1157 | flow_u32[ofs2] = random_value(); | |
1158 | return true; | |
1159 | } | |
1160 | } | |
1161 | } | |
428b2edd | 1162 | OVS_NOT_REACHED(); |
5cb7a798 BP |
1163 | } |
1164 | ||
1165 | /* 16 randomly chosen flows with N >= 3 nonzero values. */ | |
1166 | if (choose(16 * (FLOW_U32S - 4), &idx)) { | |
1167 | int n = idx / 16 + 3; | |
1168 | int i; | |
1169 | ||
1170 | for (i = 0; i < n; i++) { | |
1171 | flow_u32[i] = random_value(); | |
1172 | } | |
1173 | shuffle_u32s(flow_u32, FLOW_U32S); | |
1174 | ||
1175 | return true; | |
1176 | } | |
1177 | ||
1178 | return false; | |
1179 | } | |
1180 | ||
1181 | static void | |
1182 | any_random_flow(struct flow *flow) | |
1183 | { | |
1184 | static unsigned int max; | |
1185 | if (!max) { | |
1186 | while (next_random_flow(flow, max)) { | |
1187 | max++; | |
1188 | } | |
1189 | } | |
1190 | ||
1191 | next_random_flow(flow, random_range(max)); | |
1192 | } | |
1193 | ||
1194 | static void | |
1195 | toggle_masked_flow_bits(struct flow *flow, const struct flow_wildcards *mask) | |
1196 | { | |
1197 | const uint32_t *mask_u32 = (const uint32_t *) &mask->masks; | |
1198 | uint32_t *flow_u32 = (uint32_t *) flow; | |
1199 | int i; | |
1200 | ||
1201 | for (i = 0; i < FLOW_U32S; i++) { | |
1202 | if (mask_u32[i] != 0) { | |
1203 | uint32_t bit; | |
1204 | ||
1205 | do { | |
1206 | bit = 1u << random_range(32); | |
1207 | } while (!(bit & mask_u32[i])); | |
1208 | flow_u32[i] ^= bit; | |
1209 | } | |
1210 | } | |
1211 | } | |
1212 | ||
1213 | static void | |
1214 | wildcard_extra_bits(struct flow_wildcards *mask) | |
1215 | { | |
1216 | uint32_t *mask_u32 = (uint32_t *) &mask->masks; | |
1217 | int i; | |
1218 | ||
1219 | for (i = 0; i < FLOW_U32S; i++) { | |
1220 | if (mask_u32[i] != 0) { | |
1221 | uint32_t bit; | |
1222 | ||
1223 | do { | |
1224 | bit = 1u << random_range(32); | |
1225 | } while (!(bit & mask_u32[i])); | |
1226 | mask_u32[i] &= ~bit; | |
1227 | } | |
1228 | } | |
1229 | } | |
1230 | ||
1231 | static void | |
1232 | test_miniflow(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
1233 | { | |
1234 | struct flow flow; | |
1235 | unsigned int idx; | |
1236 | ||
1237 | random_set_seed(0xb3faca38); | |
1238 | for (idx = 0; next_random_flow(&flow, idx); idx++) { | |
1239 | const uint32_t *flow_u32 = (const uint32_t *) &flow; | |
1240 | struct miniflow miniflow, miniflow2, miniflow3; | |
1241 | struct flow flow2, flow3; | |
1242 | struct flow_wildcards mask; | |
1243 | struct minimask minimask; | |
1244 | int i; | |
1245 | ||
1246 | /* Convert flow to miniflow. */ | |
1247 | miniflow_init(&miniflow, &flow); | |
1248 | ||
1249 | /* Check that the flow equals its miniflow. */ | |
1250 | assert(miniflow_get_vid(&miniflow) == vlan_tci_to_vid(flow.vlan_tci)); | |
1251 | for (i = 0; i < FLOW_U32S; i++) { | |
28a560d9 JR |
1252 | assert(MINIFLOW_GET_TYPE(&miniflow, uint32_t, i * 4) |
1253 | == flow_u32[i]); | |
5cb7a798 BP |
1254 | } |
1255 | ||
1256 | /* Check that the miniflow equals itself. */ | |
1257 | assert(miniflow_equal(&miniflow, &miniflow)); | |
1258 | ||
1259 | /* Convert miniflow back to flow and verify that it's the same. */ | |
1260 | miniflow_expand(&miniflow, &flow2); | |
1261 | assert(flow_equal(&flow, &flow2)); | |
1262 | ||
1263 | /* Check that copying a miniflow works properly. */ | |
1264 | miniflow_clone(&miniflow2, &miniflow); | |
1265 | assert(miniflow_equal(&miniflow, &miniflow2)); | |
1266 | assert(miniflow_hash(&miniflow, 0) == miniflow_hash(&miniflow2, 0)); | |
1267 | miniflow_expand(&miniflow2, &flow3); | |
1268 | assert(flow_equal(&flow, &flow3)); | |
1269 | ||
1270 | /* Check that masked matches work as expected for identical flows and | |
1271 | * miniflows. */ | |
1272 | do { | |
1273 | next_random_flow(&mask.masks, 1); | |
1274 | } while (flow_wildcards_is_catchall(&mask)); | |
1275 | minimask_init(&minimask, &mask); | |
1276 | assert(minimask_is_catchall(&minimask) | |
1277 | == flow_wildcards_is_catchall(&mask)); | |
1278 | assert(miniflow_equal_in_minimask(&miniflow, &miniflow2, &minimask)); | |
1279 | assert(miniflow_equal_flow_in_minimask(&miniflow, &flow2, &minimask)); | |
1280 | assert(miniflow_hash_in_minimask(&miniflow, &minimask, 0x12345678) == | |
1281 | flow_hash_in_minimask(&flow, &minimask, 0x12345678)); | |
1282 | ||
1283 | /* Check that masked matches work as expected for differing flows and | |
1284 | * miniflows. */ | |
1285 | toggle_masked_flow_bits(&flow2, &mask); | |
1286 | assert(!miniflow_equal_flow_in_minimask(&miniflow, &flow2, &minimask)); | |
1287 | miniflow_init(&miniflow3, &flow2); | |
1288 | assert(!miniflow_equal_in_minimask(&miniflow, &miniflow3, &minimask)); | |
1289 | ||
1290 | /* Clean up. */ | |
1291 | miniflow_destroy(&miniflow); | |
1292 | miniflow_destroy(&miniflow2); | |
1293 | miniflow_destroy(&miniflow3); | |
1294 | minimask_destroy(&minimask); | |
1295 | } | |
1296 | } | |
1297 | ||
1298 | static void | |
1299 | test_minimask_has_extra(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
1300 | { | |
1301 | struct flow_wildcards catchall; | |
1302 | struct minimask minicatchall; | |
1303 | struct flow flow; | |
1304 | unsigned int idx; | |
1305 | ||
1306 | flow_wildcards_init_catchall(&catchall); | |
1307 | minimask_init(&minicatchall, &catchall); | |
1308 | assert(minimask_is_catchall(&minicatchall)); | |
1309 | ||
1310 | random_set_seed(0x2ec7905b); | |
1311 | for (idx = 0; next_random_flow(&flow, idx); idx++) { | |
1312 | struct flow_wildcards mask; | |
1313 | struct minimask minimask; | |
1314 | ||
1315 | mask.masks = flow; | |
1316 | minimask_init(&minimask, &mask); | |
1317 | assert(!minimask_has_extra(&minimask, &minimask)); | |
1318 | assert(minimask_has_extra(&minicatchall, &minimask) | |
1319 | == !minimask_is_catchall(&minimask)); | |
1320 | if (!minimask_is_catchall(&minimask)) { | |
1321 | struct minimask minimask2; | |
1322 | ||
1323 | wildcard_extra_bits(&mask); | |
1324 | minimask_init(&minimask2, &mask); | |
1325 | assert(minimask_has_extra(&minimask2, &minimask)); | |
1326 | assert(!minimask_has_extra(&minimask, &minimask2)); | |
1327 | minimask_destroy(&minimask2); | |
1328 | } | |
1329 | ||
1330 | minimask_destroy(&minimask); | |
1331 | } | |
f2f3f5cb BP |
1332 | |
1333 | minimask_destroy(&minicatchall); | |
5cb7a798 BP |
1334 | } |
1335 | ||
1336 | static void | |
1337 | test_minimask_combine(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
1338 | { | |
1339 | struct flow_wildcards catchall; | |
1340 | struct minimask minicatchall; | |
1341 | struct flow flow; | |
1342 | unsigned int idx; | |
1343 | ||
1344 | flow_wildcards_init_catchall(&catchall); | |
1345 | minimask_init(&minicatchall, &catchall); | |
1346 | assert(minimask_is_catchall(&minicatchall)); | |
1347 | ||
1348 | random_set_seed(0x181bf0cd); | |
1349 | for (idx = 0; next_random_flow(&flow, idx); idx++) { | |
1350 | struct minimask minimask, minimask2, minicombined; | |
1351 | struct flow_wildcards mask, mask2, combined, combined2; | |
1352 | uint32_t storage[FLOW_U32S]; | |
1353 | struct flow flow2; | |
1354 | ||
1355 | mask.masks = flow; | |
1356 | minimask_init(&minimask, &mask); | |
1357 | ||
1358 | minimask_combine(&minicombined, &minimask, &minicatchall, storage); | |
1359 | assert(minimask_is_catchall(&minicombined)); | |
1360 | ||
1361 | any_random_flow(&flow2); | |
1362 | mask2.masks = flow2; | |
1363 | minimask_init(&minimask2, &mask2); | |
1364 | ||
1365 | minimask_combine(&minicombined, &minimask, &minimask2, storage); | |
368eefac | 1366 | flow_wildcards_and(&combined, &mask, &mask2); |
5cb7a798 BP |
1367 | minimask_expand(&minicombined, &combined2); |
1368 | assert(flow_wildcards_equal(&combined, &combined2)); | |
1369 | ||
1370 | minimask_destroy(&minimask); | |
1371 | minimask_destroy(&minimask2); | |
1372 | } | |
f2f3f5cb BP |
1373 | |
1374 | minimask_destroy(&minicatchall); | |
5cb7a798 BP |
1375 | } |
1376 | \f | |
3223e977 | 1377 | static const struct command commands[] = { |
5cb7a798 | 1378 | /* Classifier tests. */ |
3223e977 BP |
1379 | {"empty", 0, 0, test_empty}, |
1380 | {"destroy-null", 0, 0, test_destroy_null}, | |
1381 | {"single-rule", 0, 0, test_single_rule}, | |
1382 | {"rule-replacement", 0, 0, test_rule_replacement}, | |
b5d97350 | 1383 | {"many-rules-in-one-list", 0, 0, test_many_rules_in_one_list}, |
3223e977 | 1384 | {"many-rules-in-one-table", 0, 0, test_many_rules_in_one_table}, |
b5d97350 BP |
1385 | {"many-rules-in-two-tables", 0, 0, test_many_rules_in_two_tables}, |
1386 | {"many-rules-in-five-tables", 0, 0, test_many_rules_in_five_tables}, | |
5cb7a798 BP |
1387 | |
1388 | /* Miniflow and minimask tests. */ | |
1389 | {"miniflow", 0, 0, test_miniflow}, | |
eadd1644 AZ |
1390 | {"minimask_has_extra", 0, 0, test_minimask_has_extra}, |
1391 | {"minimask_combine", 0, 0, test_minimask_combine}, | |
5cb7a798 | 1392 | |
3223e977 BP |
1393 | {NULL, 0, 0, NULL}, |
1394 | }; | |
064af421 | 1395 | |
eadd1644 AZ |
1396 | static void |
1397 | test_classifier_main(int argc, char *argv[]) | |
064af421 | 1398 | { |
b5d97350 | 1399 | set_program_name(argv[0]); |
064af421 | 1400 | init_values(); |
3223e977 | 1401 | run_command(argc - 1, argv + 1, commands); |
064af421 | 1402 | } |
eadd1644 AZ |
1403 | |
1404 | OVSTEST_REGISTER("test-classifier", test_classifier_main); |