]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
f0f4410a | 2 | * Copyright (c) 2009, 2010 Nicira Networks. |
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 "classifier.h" |
30 | #include <errno.h> | |
31 | #include <limits.h> | |
10a24935 | 32 | #include "byte-order.h" |
3223e977 | 33 | #include "command-line.h" |
064af421 | 34 | #include "flow.h" |
064af421 BP |
35 | #include "packets.h" |
36 | ||
37 | #undef NDEBUG | |
38 | #include <assert.h> | |
39 | ||
40 | struct test_rule { | |
41 | int aux; /* Auxiliary data. */ | |
42 | struct cls_rule cls_rule; /* Classifier rule data. */ | |
43 | }; | |
44 | ||
45 | static struct test_rule * | |
46 | test_rule_from_cls_rule(const struct cls_rule *rule) | |
47 | { | |
48 | return rule ? CONTAINER_OF(rule, struct test_rule, cls_rule) : NULL; | |
49 | } | |
50 | ||
51 | /* Trivial (linear) classifier. */ | |
52 | struct tcls { | |
53 | size_t n_rules; | |
54 | size_t allocated_rules; | |
55 | struct test_rule **rules; | |
56 | }; | |
57 | ||
58 | static void | |
59 | tcls_init(struct tcls *tcls) | |
60 | { | |
61 | tcls->n_rules = 0; | |
62 | tcls->allocated_rules = 0; | |
63 | tcls->rules = NULL; | |
64 | } | |
65 | ||
66 | static void | |
67 | tcls_destroy(struct tcls *tcls) | |
68 | { | |
69 | if (tcls) { | |
70 | size_t i; | |
71 | ||
72 | for (i = 0; i < tcls->n_rules; i++) { | |
73 | free(tcls->rules[i]); | |
74 | } | |
75 | free(tcls->rules); | |
76 | } | |
77 | } | |
78 | ||
79 | static int | |
80 | tcls_count_exact(const struct tcls *tcls) | |
81 | { | |
82 | int n_exact; | |
83 | size_t i; | |
84 | ||
85 | n_exact = 0; | |
86 | for (i = 0; i < tcls->n_rules; i++) { | |
87 | n_exact += tcls->rules[i]->cls_rule.wc.wildcards == 0; | |
88 | } | |
89 | return n_exact; | |
90 | } | |
91 | ||
92 | static bool | |
93 | tcls_is_empty(const struct tcls *tcls) | |
94 | { | |
95 | return tcls->n_rules == 0; | |
96 | } | |
97 | ||
98 | static struct test_rule * | |
99 | tcls_insert(struct tcls *tcls, const struct test_rule *rule) | |
100 | { | |
101 | size_t i; | |
102 | ||
103 | assert(rule->cls_rule.wc.wildcards || rule->cls_rule.priority == UINT_MAX); | |
104 | for (i = 0; i < tcls->n_rules; i++) { | |
105 | const struct cls_rule *pos = &tcls->rules[i]->cls_rule; | |
106 | if (pos->priority == rule->cls_rule.priority | |
107 | && pos->wc.wildcards == rule->cls_rule.wc.wildcards | |
108 | && flow_equal(&pos->flow, &rule->cls_rule.flow)) { | |
109 | /* Exact match. | |
110 | * XXX flow_equal should ignore wildcarded fields */ | |
111 | free(tcls->rules[i]); | |
112 | tcls->rules[i] = xmemdup(rule, sizeof *rule); | |
113 | return tcls->rules[i]; | |
af7b73f4 | 114 | } else if (pos->priority < rule->cls_rule.priority) { |
064af421 BP |
115 | break; |
116 | } | |
117 | } | |
118 | ||
119 | if (tcls->n_rules >= tcls->allocated_rules) { | |
120 | tcls->rules = x2nrealloc(tcls->rules, &tcls->allocated_rules, | |
121 | sizeof *tcls->rules); | |
122 | } | |
123 | if (i != tcls->n_rules) { | |
124 | memmove(&tcls->rules[i + 1], &tcls->rules[i], | |
125 | sizeof *tcls->rules * (tcls->n_rules - i)); | |
126 | } | |
127 | tcls->rules[i] = xmemdup(rule, sizeof *rule); | |
128 | tcls->n_rules++; | |
129 | return tcls->rules[i]; | |
130 | } | |
131 | ||
132 | static void | |
133 | tcls_remove(struct tcls *cls, const struct test_rule *rule) | |
134 | { | |
135 | size_t i; | |
136 | ||
137 | for (i = 0; i < cls->n_rules; i++) { | |
138 | struct test_rule *pos = cls->rules[i]; | |
139 | if (pos == rule) { | |
140 | free(pos); | |
141 | memmove(&cls->rules[i], &cls->rules[i + 1], | |
142 | sizeof *cls->rules * (cls->n_rules - i - 1)); | |
143 | cls->n_rules--; | |
144 | return; | |
145 | } | |
146 | } | |
147 | NOT_REACHED(); | |
148 | } | |
149 | ||
150 | static uint32_t | |
151 | read_uint32(const void *p) | |
152 | { | |
153 | uint32_t x; | |
154 | memcpy(&x, p, sizeof x); | |
155 | return x; | |
156 | } | |
157 | ||
158 | static bool | |
ae412e7d | 159 | match(const struct cls_rule *wild, const struct flow *fixed) |
064af421 BP |
160 | { |
161 | int f_idx; | |
162 | ||
163 | for (f_idx = 0; f_idx < CLS_N_FIELDS; f_idx++) { | |
164 | const struct cls_field *f = &cls_fields[f_idx]; | |
165 | void *wild_field = (char *) &wild->flow + f->ofs; | |
166 | void *fixed_field = (char *) fixed + f->ofs; | |
167 | ||
168 | if ((wild->wc.wildcards & f->wildcards) == f->wildcards || | |
169 | !memcmp(wild_field, fixed_field, f->len)) { | |
170 | /* Definite match. */ | |
171 | continue; | |
172 | } | |
173 | ||
174 | if (wild->wc.wildcards & f->wildcards) { | |
175 | uint32_t test = read_uint32(wild_field); | |
176 | uint32_t ip = read_uint32(fixed_field); | |
177 | int shift = (f_idx == CLS_F_IDX_NW_SRC | |
178 | ? OFPFW_NW_SRC_SHIFT : OFPFW_NW_DST_SHIFT); | |
179 | uint32_t mask = flow_nw_bits_to_mask(wild->wc.wildcards, shift); | |
180 | if (!((test ^ ip) & mask)) { | |
181 | continue; | |
182 | } | |
183 | } | |
184 | ||
185 | return false; | |
186 | } | |
187 | return true; | |
188 | } | |
189 | ||
190 | static struct cls_rule * | |
ae412e7d | 191 | tcls_lookup(const struct tcls *cls, const struct flow *flow, int include) |
064af421 BP |
192 | { |
193 | size_t i; | |
194 | ||
195 | for (i = 0; i < cls->n_rules; i++) { | |
196 | struct test_rule *pos = cls->rules[i]; | |
197 | uint32_t wildcards = pos->cls_rule.wc.wildcards; | |
198 | if (include & (wildcards ? CLS_INC_WILD : CLS_INC_EXACT) | |
199 | && match(&pos->cls_rule, flow)) { | |
200 | return &pos->cls_rule; | |
201 | } | |
202 | } | |
203 | return NULL; | |
204 | } | |
205 | ||
206 | static void | |
207 | tcls_delete_matches(struct tcls *cls, | |
208 | const struct cls_rule *target, | |
209 | int include) | |
210 | { | |
211 | size_t i; | |
212 | ||
213 | for (i = 0; i < cls->n_rules; ) { | |
214 | struct test_rule *pos = cls->rules[i]; | |
215 | uint32_t wildcards = pos->cls_rule.wc.wildcards; | |
216 | if (include & (wildcards ? CLS_INC_WILD : CLS_INC_EXACT) | |
217 | && match(target, &pos->cls_rule.flow)) { | |
218 | tcls_remove(cls, pos); | |
219 | } else { | |
220 | i++; | |
221 | } | |
222 | } | |
223 | } | |
224 | \f | |
965f03d8 BP |
225 | static uint32_t nw_src_values[] = { CONSTANT_HTONL(0xc0a80001), |
226 | CONSTANT_HTONL(0xc0a04455) }; | |
227 | static uint32_t nw_dst_values[] = { CONSTANT_HTONL(0xc0a80002), | |
228 | CONSTANT_HTONL(0xc0a04455) }; | |
659586ef | 229 | static uint32_t tun_id_values[] = { 0, 0xffff0000 }; |
965f03d8 BP |
230 | static uint16_t in_port_values[] = { CONSTANT_HTONS(1), |
231 | CONSTANT_HTONS(OFPP_LOCAL) }; | |
232 | static uint16_t dl_vlan_values[] = { CONSTANT_HTONS(101), CONSTANT_HTONS(0) }; | |
959a2ecd | 233 | static uint8_t dl_vlan_pcp_values[] = { 7, 0 }; |
d87961bf | 234 | static uint16_t dl_type_values[] |
965f03d8 BP |
235 | = { CONSTANT_HTONS(ETH_TYPE_IP), CONSTANT_HTONS(ETH_TYPE_ARP) }; |
236 | static uint16_t tp_src_values[] = { CONSTANT_HTONS(49362), | |
237 | CONSTANT_HTONS(80) }; | |
238 | static uint16_t tp_dst_values[] = { CONSTANT_HTONS(6667), CONSTANT_HTONS(22) }; | |
064af421 BP |
239 | static uint8_t dl_src_values[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 }, |
240 | { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } }; | |
241 | static uint8_t dl_dst_values[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 }, | |
242 | { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } }; | |
243 | static uint8_t nw_proto_values[] = { IP_TYPE_TCP, IP_TYPE_ICMP }; | |
834377ea | 244 | static uint8_t nw_tos_values[] = { 49, 0 }; |
064af421 BP |
245 | |
246 | static void *values[CLS_N_FIELDS][2]; | |
247 | ||
248 | static void | |
249 | init_values(void) | |
250 | { | |
659586ef JG |
251 | values[CLS_F_IDX_TUN_ID][0] = &tun_id_values[0]; |
252 | values[CLS_F_IDX_TUN_ID][1] = &tun_id_values[1]; | |
253 | ||
064af421 BP |
254 | values[CLS_F_IDX_IN_PORT][0] = &in_port_values[0]; |
255 | values[CLS_F_IDX_IN_PORT][1] = &in_port_values[1]; | |
256 | ||
257 | values[CLS_F_IDX_DL_VLAN][0] = &dl_vlan_values[0]; | |
258 | values[CLS_F_IDX_DL_VLAN][1] = &dl_vlan_values[1]; | |
259 | ||
959a2ecd JP |
260 | values[CLS_F_IDX_DL_VLAN_PCP][0] = &dl_vlan_pcp_values[0]; |
261 | values[CLS_F_IDX_DL_VLAN_PCP][1] = &dl_vlan_pcp_values[1]; | |
262 | ||
064af421 BP |
263 | values[CLS_F_IDX_DL_SRC][0] = dl_src_values[0]; |
264 | values[CLS_F_IDX_DL_SRC][1] = dl_src_values[1]; | |
265 | ||
266 | values[CLS_F_IDX_DL_DST][0] = dl_dst_values[0]; | |
267 | values[CLS_F_IDX_DL_DST][1] = dl_dst_values[1]; | |
268 | ||
269 | values[CLS_F_IDX_DL_TYPE][0] = &dl_type_values[0]; | |
270 | values[CLS_F_IDX_DL_TYPE][1] = &dl_type_values[1]; | |
271 | ||
272 | values[CLS_F_IDX_NW_SRC][0] = &nw_src_values[0]; | |
273 | values[CLS_F_IDX_NW_SRC][1] = &nw_src_values[1]; | |
274 | ||
275 | values[CLS_F_IDX_NW_DST][0] = &nw_dst_values[0]; | |
276 | values[CLS_F_IDX_NW_DST][1] = &nw_dst_values[1]; | |
277 | ||
278 | values[CLS_F_IDX_NW_PROTO][0] = &nw_proto_values[0]; | |
279 | values[CLS_F_IDX_NW_PROTO][1] = &nw_proto_values[1]; | |
280 | ||
834377ea JP |
281 | values[CLS_F_IDX_NW_TOS][0] = &nw_tos_values[0]; |
282 | values[CLS_F_IDX_NW_TOS][1] = &nw_tos_values[1]; | |
283 | ||
064af421 BP |
284 | values[CLS_F_IDX_TP_SRC][0] = &tp_src_values[0]; |
285 | values[CLS_F_IDX_TP_SRC][1] = &tp_src_values[1]; | |
286 | ||
287 | values[CLS_F_IDX_TP_DST][0] = &tp_dst_values[0]; | |
288 | values[CLS_F_IDX_TP_DST][1] = &tp_dst_values[1]; | |
289 | } | |
290 | ||
291 | #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values) | |
292 | #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values) | |
659586ef | 293 | #define N_TUN_ID_VALUES ARRAY_SIZE(tun_id_values) |
064af421 BP |
294 | #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values) |
295 | #define N_DL_VLAN_VALUES ARRAY_SIZE(dl_vlan_values) | |
959a2ecd | 296 | #define N_DL_VLAN_PCP_VALUES ARRAY_SIZE(dl_vlan_pcp_values) |
064af421 BP |
297 | #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values) |
298 | #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values) | |
299 | #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values) | |
300 | #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values) | |
301 | #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values) | |
302 | #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values) | |
834377ea | 303 | #define N_NW_TOS_VALUES ARRAY_SIZE(nw_tos_values) |
064af421 BP |
304 | |
305 | #define N_FLOW_VALUES (N_NW_SRC_VALUES * \ | |
306 | N_NW_DST_VALUES * \ | |
659586ef | 307 | N_TUN_ID_VALUES * \ |
064af421 BP |
308 | N_IN_PORT_VALUES * \ |
309 | N_DL_VLAN_VALUES * \ | |
959a2ecd | 310 | N_DL_VLAN_PCP_VALUES * \ |
064af421 BP |
311 | N_DL_TYPE_VALUES * \ |
312 | N_TP_SRC_VALUES * \ | |
313 | N_TP_DST_VALUES * \ | |
314 | N_DL_SRC_VALUES * \ | |
315 | N_DL_DST_VALUES * \ | |
834377ea JP |
316 | N_NW_PROTO_VALUES * \ |
317 | N_NW_TOS_VALUES) | |
064af421 BP |
318 | |
319 | static unsigned int | |
320 | get_value(unsigned int *x, unsigned n_values) | |
321 | { | |
322 | unsigned int rem = *x % n_values; | |
323 | *x /= n_values; | |
324 | return rem; | |
325 | } | |
326 | ||
327 | static struct cls_rule * | |
328 | lookup_with_include_bits(const struct classifier *cls, | |
ae412e7d | 329 | const struct flow *flow, int include) |
064af421 BP |
330 | { |
331 | switch (include) { | |
332 | case CLS_INC_WILD: | |
333 | return classifier_lookup_wild(cls, flow); | |
334 | case CLS_INC_EXACT: | |
335 | return classifier_lookup_exact(cls, flow); | |
336 | case CLS_INC_WILD | CLS_INC_EXACT: | |
337 | return classifier_lookup(cls, flow); | |
338 | default: | |
339 | abort(); | |
340 | } | |
341 | } | |
342 | ||
343 | static void | |
344 | compare_classifiers(struct classifier *cls, struct tcls *tcls) | |
345 | { | |
70d3fbe7 | 346 | static const int confidence = 500; |
064af421 BP |
347 | unsigned int i; |
348 | ||
349 | assert(classifier_count(cls) == tcls->n_rules); | |
350 | assert(classifier_count_exact(cls) == tcls_count_exact(tcls)); | |
70d3fbe7 | 351 | for (i = 0; i < confidence; i++) { |
064af421 | 352 | struct cls_rule *cr0, *cr1; |
ae412e7d | 353 | struct flow flow; |
064af421 BP |
354 | unsigned int x; |
355 | int include; | |
356 | ||
70d3fbe7 | 357 | x = rand () % N_FLOW_VALUES; |
064af421 BP |
358 | flow.nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)]; |
359 | flow.nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)]; | |
659586ef | 360 | flow.tun_id = tun_id_values[get_value(&x, N_TUN_ID_VALUES)]; |
064af421 BP |
361 | flow.in_port = in_port_values[get_value(&x, N_IN_PORT_VALUES)]; |
362 | flow.dl_vlan = dl_vlan_values[get_value(&x, N_DL_VLAN_VALUES)]; | |
959a2ecd JP |
363 | flow.dl_vlan_pcp = dl_vlan_pcp_values[get_value(&x, |
364 | N_DL_VLAN_PCP_VALUES)]; | |
064af421 BP |
365 | flow.dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)]; |
366 | flow.tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)]; | |
367 | flow.tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)]; | |
368 | memcpy(flow.dl_src, dl_src_values[get_value(&x, N_DL_SRC_VALUES)], | |
369 | ETH_ADDR_LEN); | |
370 | memcpy(flow.dl_dst, dl_dst_values[get_value(&x, N_DL_DST_VALUES)], | |
371 | ETH_ADDR_LEN); | |
372 | flow.nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)]; | |
834377ea | 373 | flow.nw_tos = nw_tos_values[get_value(&x, N_NW_TOS_VALUES)]; |
064af421 BP |
374 | |
375 | for (include = 1; include <= 3; include++) { | |
376 | cr0 = lookup_with_include_bits(cls, &flow, include); | |
377 | cr1 = tcls_lookup(tcls, &flow, include); | |
378 | assert((cr0 == NULL) == (cr1 == NULL)); | |
379 | if (cr0 != NULL) { | |
380 | const struct test_rule *tr0 = test_rule_from_cls_rule(cr0); | |
381 | const struct test_rule *tr1 = test_rule_from_cls_rule(cr1); | |
382 | ||
383 | assert(flow_equal(&cr0->flow, &cr1->flow)); | |
384 | assert(cr0->wc.wildcards == cr1->wc.wildcards); | |
385 | assert(cr0->priority == cr1->priority); | |
386 | /* Skip nw_src_mask and nw_dst_mask, because they are derived | |
387 | * members whose values are used only for optimization. */ | |
388 | assert(tr0->aux == tr1->aux); | |
389 | } | |
390 | } | |
391 | } | |
392 | } | |
393 | ||
394 | static void | |
395 | free_rule(struct cls_rule *cls_rule, void *cls) | |
396 | { | |
397 | classifier_remove(cls, cls_rule); | |
398 | free(test_rule_from_cls_rule(cls_rule)); | |
399 | } | |
400 | ||
401 | static void | |
402 | destroy_classifier(struct classifier *cls) | |
403 | { | |
404 | classifier_for_each(cls, CLS_INC_ALL, free_rule, cls); | |
405 | classifier_destroy(cls); | |
406 | } | |
407 | ||
408 | static void | |
409 | check_tables(const struct classifier *cls, | |
410 | int n_tables, int n_buckets, int n_rules) | |
411 | { | |
412 | int found_tables = 0; | |
413 | int found_buckets = 0; | |
414 | int found_rules = 0; | |
415 | int i; | |
416 | ||
417 | BUILD_ASSERT(CLS_N_FIELDS == ARRAY_SIZE(cls->tables)); | |
418 | for (i = 0; i < CLS_N_FIELDS; i++) { | |
419 | const struct cls_bucket *bucket; | |
420 | if (!hmap_is_empty(&cls->tables[i])) { | |
421 | found_tables++; | |
422 | } | |
4e8e4213 | 423 | HMAP_FOR_EACH (bucket, hmap_node, &cls->tables[i]) { |
064af421 BP |
424 | found_buckets++; |
425 | assert(!list_is_empty(&bucket->rules)); | |
426 | found_rules += list_size(&bucket->rules); | |
427 | } | |
428 | } | |
429 | ||
430 | if (!hmap_is_empty(&cls->exact_table)) { | |
431 | found_tables++; | |
432 | found_buckets++; | |
433 | found_rules += hmap_count(&cls->exact_table); | |
434 | } | |
435 | ||
436 | assert(n_tables == -1 || found_tables == n_tables); | |
437 | assert(n_rules == -1 || found_rules == n_rules); | |
438 | assert(n_buckets == -1 || found_buckets == n_buckets); | |
439 | } | |
440 | ||
441 | static struct test_rule * | |
442 | make_rule(int wc_fields, unsigned int priority, int value_pat) | |
443 | { | |
444 | const struct cls_field *f; | |
445 | struct test_rule *rule; | |
446 | uint32_t wildcards; | |
ae412e7d | 447 | struct flow flow; |
064af421 BP |
448 | |
449 | wildcards = 0; | |
450 | memset(&flow, 0, sizeof flow); | |
451 | for (f = &cls_fields[0]; f < &cls_fields[CLS_N_FIELDS]; f++) { | |
452 | int f_idx = f - cls_fields; | |
453 | if (wc_fields & (1u << f_idx)) { | |
454 | wildcards |= f->wildcards; | |
455 | } else { | |
456 | int value_idx = (value_pat & (1u << f_idx)) != 0; | |
457 | memcpy((char *) &flow + f->ofs, values[f_idx][value_idx], f->len); | |
458 | } | |
459 | } | |
460 | ||
ec6fde61 | 461 | rule = xzalloc(sizeof *rule); |
659586ef JG |
462 | cls_rule_from_flow(&flow, wildcards, !wildcards ? UINT_MAX : priority, |
463 | &rule->cls_rule); | |
064af421 BP |
464 | return rule; |
465 | } | |
466 | ||
467 | static void | |
468 | shuffle(unsigned int *p, size_t n) | |
469 | { | |
470 | for (; n > 1; n--, p++) { | |
471 | unsigned int *q = &p[rand() % n]; | |
472 | unsigned int tmp = *p; | |
473 | *p = *q; | |
474 | *q = tmp; | |
475 | } | |
476 | } | |
477 | \f | |
478 | /* Tests an empty classifier. */ | |
479 | static void | |
3223e977 | 480 | test_empty(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
481 | { |
482 | struct classifier cls; | |
483 | struct tcls tcls; | |
484 | ||
485 | classifier_init(&cls); | |
486 | tcls_init(&tcls); | |
487 | assert(classifier_is_empty(&cls)); | |
488 | assert(tcls_is_empty(&tcls)); | |
489 | compare_classifiers(&cls, &tcls); | |
490 | classifier_destroy(&cls); | |
491 | tcls_destroy(&tcls); | |
492 | } | |
493 | ||
494 | /* Destroys a null classifier. */ | |
495 | static void | |
3223e977 | 496 | test_destroy_null(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
497 | { |
498 | classifier_destroy(NULL); | |
499 | } | |
500 | ||
501 | /* Tests classification with one rule at a time. */ | |
502 | static void | |
3223e977 | 503 | test_single_rule(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
504 | { |
505 | unsigned int wc_fields; /* Hilarious. */ | |
506 | ||
507 | for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) { | |
508 | struct classifier cls; | |
509 | struct test_rule *rule, *tcls_rule; | |
510 | struct tcls tcls; | |
511 | ||
512 | rule = make_rule(wc_fields, | |
513 | hash_bytes(&wc_fields, sizeof wc_fields, 0), 0); | |
514 | ||
515 | classifier_init(&cls); | |
516 | tcls_init(&tcls); | |
517 | ||
518 | tcls_rule = tcls_insert(&tcls, rule); | |
519 | if (wc_fields) { | |
520 | assert(!classifier_insert(&cls, &rule->cls_rule)); | |
521 | } else { | |
522 | classifier_insert_exact(&cls, &rule->cls_rule); | |
523 | } | |
524 | check_tables(&cls, 1, 1, 1); | |
525 | compare_classifiers(&cls, &tcls); | |
526 | ||
527 | classifier_remove(&cls, &rule->cls_rule); | |
528 | tcls_remove(&tcls, tcls_rule); | |
529 | assert(classifier_is_empty(&cls)); | |
530 | assert(tcls_is_empty(&tcls)); | |
531 | compare_classifiers(&cls, &tcls); | |
532 | ||
533 | free(rule); | |
534 | classifier_destroy(&cls); | |
535 | tcls_destroy(&tcls); | |
536 | } | |
537 | } | |
538 | ||
539 | /* Tests replacing one rule by another. */ | |
540 | static void | |
3223e977 | 541 | test_rule_replacement(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
542 | { |
543 | unsigned int wc_fields; | |
544 | ||
545 | for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) { | |
546 | struct classifier cls; | |
f0f4410a BP |
547 | struct test_rule *rule1; |
548 | struct test_rule *rule2; | |
064af421 BP |
549 | struct tcls tcls; |
550 | ||
551 | rule1 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX); | |
552 | rule2 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX); | |
553 | rule2->aux += 5; | |
554 | rule2->aux += 5; | |
555 | ||
556 | classifier_init(&cls); | |
557 | tcls_init(&tcls); | |
f0f4410a | 558 | tcls_insert(&tcls, rule1); |
064af421 BP |
559 | assert(!classifier_insert(&cls, &rule1->cls_rule)); |
560 | check_tables(&cls, 1, 1, 1); | |
561 | compare_classifiers(&cls, &tcls); | |
562 | tcls_destroy(&tcls); | |
563 | ||
564 | tcls_init(&tcls); | |
f0f4410a | 565 | tcls_insert(&tcls, rule2); |
064af421 BP |
566 | assert(test_rule_from_cls_rule( |
567 | classifier_insert(&cls, &rule2->cls_rule)) == rule1); | |
568 | free(rule1); | |
569 | check_tables(&cls, 1, 1, 1); | |
570 | compare_classifiers(&cls, &tcls); | |
571 | tcls_destroy(&tcls); | |
572 | destroy_classifier(&cls); | |
573 | } | |
574 | } | |
575 | ||
576 | static int | |
577 | table_mask(int table) | |
578 | { | |
579 | return ((1u << CLS_N_FIELDS) - 1) & ~((1u << table) - 1); | |
580 | } | |
581 | ||
582 | static int | |
583 | random_wcf_in_table(int table, int seed) | |
584 | { | |
585 | int wc_fields = (1u << table) | hash_int(seed, 0); | |
586 | return wc_fields & table_mask(table); | |
587 | } | |
588 | ||
589 | /* Tests classification with two rules at a time that fall into the same | |
590 | * bucket. */ | |
591 | static void | |
3223e977 | 592 | test_two_rules_in_one_bucket(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
593 | { |
594 | int table, rel_pri, wcf_pat, value_pat; | |
595 | ||
596 | for (table = 0; table <= CLS_N_FIELDS; table++) { | |
597 | for (rel_pri = -1; rel_pri <= +1; rel_pri++) { | |
598 | for (wcf_pat = 0; wcf_pat < 4; wcf_pat++) { | |
599 | int n_value_pats = table == CLS_N_FIELDS - 1 ? 1 : 2; | |
600 | for (value_pat = 0; value_pat < n_value_pats; value_pat++) { | |
601 | struct test_rule *rule1, *tcls_rule1; | |
602 | struct test_rule *rule2, *tcls_rule2; | |
603 | struct test_rule *displaced_rule; | |
604 | struct classifier cls; | |
605 | struct tcls tcls; | |
606 | unsigned int pri1, pri2; | |
607 | int wcf1, wcf2; | |
608 | ||
609 | if (table != CLS_F_IDX_EXACT) { | |
610 | /* We can use identical priorities in this test because | |
611 | * the classifier always chooses the rule added later | |
612 | * for equal-priority rules that fall into the same | |
613 | * bucket. */ | |
614 | pri1 = table * 257 + 50; | |
615 | pri2 = pri1 + rel_pri; | |
616 | ||
617 | wcf1 = (wcf_pat & 1 | |
618 | ? random_wcf_in_table(table, pri1) | |
619 | : 1u << table); | |
620 | wcf2 = (wcf_pat & 2 | |
621 | ? random_wcf_in_table(table, pri2) | |
622 | : 1u << table); | |
623 | if (value_pat) { | |
624 | wcf1 &= ~(1u << (CLS_N_FIELDS - 1)); | |
625 | wcf2 &= ~(1u << (CLS_N_FIELDS - 1)); | |
626 | } | |
627 | } else { | |
628 | /* This classifier always puts exact-match rules at | |
629 | * maximum priority. */ | |
630 | pri1 = pri2 = UINT_MAX; | |
631 | ||
632 | /* No wildcard fields. */ | |
633 | wcf1 = wcf2 = 0; | |
634 | } | |
635 | ||
636 | rule1 = make_rule(wcf1, pri1, 0); | |
637 | rule2 = make_rule(wcf2, pri2, | |
638 | value_pat << (CLS_N_FIELDS - 1)); | |
639 | ||
640 | classifier_init(&cls); | |
641 | tcls_init(&tcls); | |
642 | ||
643 | tcls_rule1 = tcls_insert(&tcls, rule1); | |
644 | tcls_rule2 = tcls_insert(&tcls, rule2); | |
645 | assert(!classifier_insert(&cls, &rule1->cls_rule)); | |
646 | displaced_rule = test_rule_from_cls_rule( | |
647 | classifier_insert(&cls, &rule2->cls_rule)); | |
648 | if (wcf1 != wcf2 || pri1 != pri2 || value_pat) { | |
649 | assert(!displaced_rule); | |
650 | ||
651 | check_tables(&cls, 1, 1, 2); | |
652 | compare_classifiers(&cls, &tcls); | |
653 | ||
654 | classifier_remove(&cls, &rule1->cls_rule); | |
655 | tcls_remove(&tcls, tcls_rule1); | |
656 | check_tables(&cls, 1, 1, 1); | |
657 | compare_classifiers(&cls, &tcls); | |
658 | } else { | |
659 | assert(displaced_rule == rule1); | |
660 | check_tables(&cls, 1, 1, 1); | |
661 | compare_classifiers(&cls, &tcls); | |
662 | } | |
663 | free(rule1); | |
664 | ||
665 | classifier_remove(&cls, &rule2->cls_rule); | |
666 | tcls_remove(&tcls, tcls_rule2); | |
667 | compare_classifiers(&cls, &tcls); | |
668 | free(rule2); | |
669 | ||
670 | destroy_classifier(&cls); | |
671 | tcls_destroy(&tcls); | |
672 | } | |
673 | } | |
674 | } | |
675 | } | |
676 | } | |
677 | ||
678 | /* Tests classification with two rules at a time that fall into the same | |
679 | * table but different buckets. */ | |
680 | static void | |
3223e977 | 681 | test_two_rules_in_one_table(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
682 | { |
683 | int table, rel_pri, wcf_pat; | |
684 | ||
685 | /* Skip tables 0 and CLS_F_IDX_EXACT because they have one bucket. */ | |
686 | for (table = 1; table < CLS_N_FIELDS; table++) { | |
687 | for (rel_pri = -1; rel_pri <= +1; rel_pri++) { | |
688 | for (wcf_pat = 0; wcf_pat < 5; wcf_pat++) { | |
689 | struct test_rule *rule1, *tcls_rule1; | |
690 | struct test_rule *rule2, *tcls_rule2; | |
691 | struct classifier cls; | |
692 | struct tcls tcls; | |
693 | unsigned int pri1, pri2; | |
694 | int wcf1, wcf2; | |
695 | int value_mask, value_pat1, value_pat2; | |
696 | int i; | |
697 | ||
698 | /* We can use identical priorities in this test because the | |
699 | * classifier always chooses the rule added later for | |
700 | * equal-priority rules that fall into the same table. */ | |
701 | pri1 = table * 257 + 50; | |
702 | pri2 = pri1 + rel_pri; | |
703 | ||
704 | if (wcf_pat & 4) { | |
705 | wcf1 = wcf2 = random_wcf_in_table(table, pri1); | |
706 | } else { | |
707 | wcf1 = (wcf_pat & 1 | |
708 | ? random_wcf_in_table(table, pri1) | |
709 | : 1u << table); | |
710 | wcf2 = (wcf_pat & 2 | |
711 | ? random_wcf_in_table(table, pri2) | |
712 | : 1u << table); | |
713 | } | |
714 | ||
715 | /* Generate value patterns that will put the two rules into | |
716 | * different buckets. */ | |
717 | value_mask = ((1u << table) - 1); | |
718 | value_pat1 = hash_int(pri1, 1) & value_mask; | |
719 | i = 0; | |
720 | do { | |
721 | value_pat2 = (hash_int(pri2, i++) & value_mask); | |
722 | } while (value_pat1 == value_pat2); | |
723 | rule1 = make_rule(wcf1, pri1, value_pat1); | |
724 | rule2 = make_rule(wcf2, pri2, value_pat2); | |
725 | ||
726 | classifier_init(&cls); | |
727 | tcls_init(&tcls); | |
728 | ||
729 | tcls_rule1 = tcls_insert(&tcls, rule1); | |
730 | tcls_rule2 = tcls_insert(&tcls, rule2); | |
731 | assert(!classifier_insert(&cls, &rule1->cls_rule)); | |
732 | assert(!classifier_insert(&cls, &rule2->cls_rule)); | |
733 | check_tables(&cls, 1, 2, 2); | |
734 | compare_classifiers(&cls, &tcls); | |
735 | ||
736 | classifier_remove(&cls, &rule1->cls_rule); | |
737 | tcls_remove(&tcls, tcls_rule1); | |
738 | check_tables(&cls, 1, 1, 1); | |
739 | compare_classifiers(&cls, &tcls); | |
740 | free(rule1); | |
741 | ||
742 | classifier_remove(&cls, &rule2->cls_rule); | |
743 | tcls_remove(&tcls, tcls_rule2); | |
744 | compare_classifiers(&cls, &tcls); | |
745 | free(rule2); | |
746 | ||
747 | classifier_destroy(&cls); | |
748 | tcls_destroy(&tcls); | |
749 | } | |
750 | } | |
751 | } | |
752 | } | |
753 | ||
754 | /* Tests classification with two rules at a time that fall into different | |
755 | * tables. */ | |
756 | static void | |
3223e977 BP |
757 | test_two_rules_in_different_tables(int argc OVS_UNUSED, |
758 | char *argv[] OVS_UNUSED) | |
064af421 BP |
759 | { |
760 | int table1, table2, rel_pri, wcf_pat; | |
761 | ||
762 | for (table1 = 0; table1 < CLS_N_FIELDS; table1++) { | |
763 | for (table2 = table1 + 1; table2 <= CLS_N_FIELDS; table2++) { | |
764 | for (rel_pri = 0; rel_pri < 2; rel_pri++) { | |
765 | for (wcf_pat = 0; wcf_pat < 4; wcf_pat++) { | |
766 | struct test_rule *rule1, *tcls_rule1; | |
767 | struct test_rule *rule2, *tcls_rule2; | |
768 | struct classifier cls; | |
769 | struct tcls tcls; | |
770 | unsigned int pri1, pri2; | |
771 | int wcf1, wcf2; | |
772 | ||
773 | /* We must use unique priorities in this test because the | |
774 | * classifier makes the rule choice undefined for rules of | |
775 | * equal priority that fall into different tables. (In | |
776 | * practice, lower-numbered tables win.) */ | |
777 | pri1 = table1 * 257 + 50; | |
778 | pri2 = rel_pri ? pri1 - 1 : pri1 + 1; | |
779 | ||
780 | wcf1 = (wcf_pat & 1 | |
781 | ? random_wcf_in_table(table1, pri1) | |
782 | : 1u << table1); | |
783 | wcf2 = (wcf_pat & 2 | |
784 | ? random_wcf_in_table(table2, pri2) | |
785 | : 1u << table2); | |
786 | ||
787 | if (table2 == CLS_F_IDX_EXACT) { | |
788 | pri2 = UINT16_MAX; | |
789 | wcf2 = 0; | |
790 | } | |
791 | ||
792 | rule1 = make_rule(wcf1, pri1, 0); | |
793 | rule2 = make_rule(wcf2, pri2, 0); | |
794 | ||
795 | classifier_init(&cls); | |
796 | tcls_init(&tcls); | |
797 | ||
798 | tcls_rule1 = tcls_insert(&tcls, rule1); | |
799 | tcls_rule2 = tcls_insert(&tcls, rule2); | |
800 | assert(!classifier_insert(&cls, &rule1->cls_rule)); | |
801 | assert(!classifier_insert(&cls, &rule2->cls_rule)); | |
802 | check_tables(&cls, 2, 2, 2); | |
803 | compare_classifiers(&cls, &tcls); | |
804 | ||
805 | classifier_remove(&cls, &rule1->cls_rule); | |
806 | tcls_remove(&tcls, tcls_rule1); | |
807 | check_tables(&cls, 1, 1, 1); | |
808 | compare_classifiers(&cls, &tcls); | |
809 | free(rule1); | |
810 | ||
811 | classifier_remove(&cls, &rule2->cls_rule); | |
812 | tcls_remove(&tcls, tcls_rule2); | |
813 | compare_classifiers(&cls, &tcls); | |
814 | free(rule2); | |
815 | ||
816 | classifier_destroy(&cls); | |
817 | tcls_destroy(&tcls); | |
818 | } | |
819 | } | |
820 | } | |
821 | } | |
822 | } | |
823 | ||
824 | /* Tests classification with many rules at a time that fall into the same | |
825 | * bucket but have unique priorities (and various wildcards). */ | |
826 | static void | |
3223e977 | 827 | test_many_rules_in_one_bucket(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
828 | { |
829 | enum { MAX_RULES = 50 }; | |
830 | int iteration, table; | |
831 | ||
832 | for (iteration = 0; iteration < 3; iteration++) { | |
833 | for (table = 0; table <= CLS_N_FIELDS; table++) { | |
834 | unsigned int priorities[MAX_RULES]; | |
835 | struct classifier cls; | |
836 | struct tcls tcls; | |
837 | int i; | |
838 | ||
839 | srand(hash_int(table, iteration)); | |
840 | for (i = 0; i < MAX_RULES; i++) { | |
841 | priorities[i] = i * 129; | |
842 | } | |
843 | shuffle(priorities, ARRAY_SIZE(priorities)); | |
844 | ||
845 | classifier_init(&cls); | |
846 | tcls_init(&tcls); | |
847 | ||
848 | for (i = 0; i < MAX_RULES; i++) { | |
849 | struct test_rule *rule; | |
850 | unsigned int priority = priorities[i]; | |
851 | int wcf; | |
852 | ||
853 | wcf = random_wcf_in_table(table, priority); | |
854 | rule = make_rule(wcf, priority, | |
855 | table == CLS_F_IDX_EXACT ? i : 1234); | |
856 | tcls_insert(&tcls, rule); | |
857 | assert(!classifier_insert(&cls, &rule->cls_rule)); | |
858 | check_tables(&cls, 1, 1, i + 1); | |
859 | compare_classifiers(&cls, &tcls); | |
860 | } | |
861 | ||
862 | destroy_classifier(&cls); | |
863 | tcls_destroy(&tcls); | |
864 | } | |
865 | } | |
866 | } | |
867 | ||
868 | /* Tests classification with many rules at a time that fall into the same | |
869 | * table but random buckets. */ | |
870 | static void | |
3223e977 | 871 | test_many_rules_in_one_table(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) |
064af421 BP |
872 | { |
873 | enum { MAX_RULES = 50 }; | |
874 | int iteration, table; | |
875 | ||
876 | for (iteration = 0; iteration < 3; iteration++) { | |
877 | for (table = 0; table < CLS_N_FIELDS; table++) { | |
878 | unsigned int priorities[MAX_RULES]; | |
879 | struct classifier cls; | |
880 | struct tcls tcls; | |
881 | int i; | |
882 | ||
883 | srand(hash_int(table, iteration)); | |
884 | for (i = 0; i < MAX_RULES; i++) { | |
885 | priorities[i] = i * 129; | |
886 | } | |
887 | shuffle(priorities, ARRAY_SIZE(priorities)); | |
888 | ||
889 | classifier_init(&cls); | |
890 | tcls_init(&tcls); | |
891 | ||
892 | for (i = 0; i < MAX_RULES; i++) { | |
893 | struct test_rule *rule; | |
894 | unsigned int priority = priorities[i]; | |
895 | int wcf; | |
896 | ||
897 | wcf = random_wcf_in_table(table, priority); | |
898 | rule = make_rule(wcf, priority, hash_int(priority, 1)); | |
899 | tcls_insert(&tcls, rule); | |
900 | assert(!classifier_insert(&cls, &rule->cls_rule)); | |
901 | check_tables(&cls, 1, -1, i + 1); | |
902 | compare_classifiers(&cls, &tcls); | |
903 | } | |
904 | ||
905 | destroy_classifier(&cls); | |
906 | tcls_destroy(&tcls); | |
907 | } | |
908 | } | |
909 | } | |
910 | ||
911 | /* Tests classification with many rules at a time that fall into random buckets | |
912 | * in random tables. */ | |
913 | static void | |
3223e977 BP |
914 | test_many_rules_in_different_tables(int argc OVS_UNUSED, |
915 | char *argv[] OVS_UNUSED) | |
064af421 BP |
916 | { |
917 | enum { MAX_RULES = 50 }; | |
918 | int iteration; | |
919 | ||
920 | for (iteration = 0; iteration < 30; iteration++) { | |
921 | unsigned int priorities[MAX_RULES]; | |
922 | struct classifier cls; | |
923 | struct tcls tcls; | |
924 | int i; | |
925 | ||
926 | srand(iteration); | |
927 | for (i = 0; i < MAX_RULES; i++) { | |
928 | priorities[i] = i * 129; | |
929 | } | |
930 | shuffle(priorities, ARRAY_SIZE(priorities)); | |
931 | ||
932 | classifier_init(&cls); | |
933 | tcls_init(&tcls); | |
934 | ||
935 | for (i = 0; i < MAX_RULES; i++) { | |
936 | struct test_rule *rule; | |
937 | unsigned int priority = priorities[i]; | |
938 | int table = rand() % (CLS_N_FIELDS + 1); | |
939 | int wcf = random_wcf_in_table(table, rand()); | |
940 | int value_pat = rand() & ((1u << CLS_N_FIELDS) - 1); | |
941 | rule = make_rule(wcf, priority, value_pat); | |
942 | tcls_insert(&tcls, rule); | |
943 | assert(!classifier_insert(&cls, &rule->cls_rule)); | |
944 | check_tables(&cls, -1, -1, i + 1); | |
945 | compare_classifiers(&cls, &tcls); | |
946 | } | |
947 | ||
948 | while (!classifier_is_empty(&cls)) { | |
949 | struct test_rule *rule = xmemdup(tcls.rules[rand() % tcls.n_rules], | |
950 | sizeof(struct test_rule)); | |
951 | int include = rand() % 2 ? CLS_INC_WILD : CLS_INC_EXACT; | |
952 | include |= (rule->cls_rule.wc.wildcards | |
953 | ? CLS_INC_WILD : CLS_INC_EXACT); | |
954 | classifier_for_each_match(&cls, &rule->cls_rule, include, | |
955 | free_rule, &cls); | |
956 | tcls_delete_matches(&tcls, &rule->cls_rule, include); | |
957 | compare_classifiers(&cls, &tcls); | |
958 | free(rule); | |
959 | } | |
064af421 BP |
960 | |
961 | destroy_classifier(&cls); | |
962 | tcls_destroy(&tcls); | |
963 | } | |
964 | } | |
965 | \f | |
3223e977 BP |
966 | static const struct command commands[] = { |
967 | {"empty", 0, 0, test_empty}, | |
968 | {"destroy-null", 0, 0, test_destroy_null}, | |
969 | {"single-rule", 0, 0, test_single_rule}, | |
970 | {"rule-replacement", 0, 0, test_rule_replacement}, | |
971 | {"two-rules-in-one-bucket", 0, 0, test_two_rules_in_one_bucket}, | |
972 | {"two-rules-in-one-table", 0, 0, test_two_rules_in_one_table}, | |
973 | {"two-rules-in-different-tables", 0, 0, | |
974 | test_two_rules_in_different_tables}, | |
975 | {"many-rules-in-one-bucket", 0, 0, test_many_rules_in_one_bucket}, | |
976 | {"many-rules-in-one-table", 0, 0, test_many_rules_in_one_table}, | |
977 | {"many-rules-in-different-tables", 0, 0, | |
978 | test_many_rules_in_different_tables}, | |
979 | {NULL, 0, 0, NULL}, | |
980 | }; | |
064af421 BP |
981 | |
982 | int | |
3223e977 | 983 | main(int argc, char *argv[]) |
064af421 BP |
984 | { |
985 | init_values(); | |
3223e977 | 986 | run_command(argc - 1, argv + 1, commands); |
064af421 BP |
987 | return 0; |
988 | } |