2 * Copyright (c) 2009 Nicira Networks.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 /* "White box" tests for classifier.
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.)
24 * This test should receive a clean report from "valgrind --leak-check=full":
25 * it frees every heap block that it allocates.
30 #include "classifier.h"
41 int aux
; /* Auxiliary data. */
42 struct cls_rule cls_rule
; /* Classifier rule data. */
45 static struct test_rule
*
46 test_rule_from_cls_rule(const struct cls_rule
*rule
)
48 return rule
? CONTAINER_OF(rule
, struct test_rule
, cls_rule
) : NULL
;
51 /* Trivial (linear) classifier. */
54 size_t allocated_rules
;
55 struct test_rule
**rules
;
59 tcls_init(struct tcls
*tcls
)
62 tcls
->allocated_rules
= 0;
67 tcls_destroy(struct tcls
*tcls
)
72 for (i
= 0; i
< tcls
->n_rules
; i
++) {
80 tcls_count_exact(const struct tcls
*tcls
)
86 for (i
= 0; i
< tcls
->n_rules
; i
++) {
87 n_exact
+= tcls
->rules
[i
]->cls_rule
.wc
.wildcards
== 0;
93 tcls_is_empty(const struct tcls
*tcls
)
95 return tcls
->n_rules
== 0;
98 static struct test_rule
*
99 tcls_insert(struct tcls
*tcls
, const struct test_rule
*rule
)
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
)) {
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
];
114 } else if (pos
->priority
<= rule
->cls_rule
.priority
) {
119 if (tcls
->n_rules
>= tcls
->allocated_rules
) {
120 tcls
->rules
= x2nrealloc(tcls
->rules
, &tcls
->allocated_rules
,
121 sizeof *tcls
->rules
);
123 if (i
!= tcls
->n_rules
) {
124 memmove(&tcls
->rules
[i
+ 1], &tcls
->rules
[i
],
125 sizeof *tcls
->rules
* (tcls
->n_rules
- i
));
127 tcls
->rules
[i
] = xmemdup(rule
, sizeof *rule
);
129 return tcls
->rules
[i
];
133 tcls_remove(struct tcls
*cls
, const struct test_rule
*rule
)
137 for (i
= 0; i
< cls
->n_rules
; i
++) {
138 struct test_rule
*pos
= cls
->rules
[i
];
141 memmove(&cls
->rules
[i
], &cls
->rules
[i
+ 1],
142 sizeof *cls
->rules
* (cls
->n_rules
- i
- 1));
151 read_uint32(const void *p
)
154 memcpy(&x
, p
, sizeof x
);
159 match(const struct cls_rule
*wild
, const flow_t
*fixed
)
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
;
168 if ((wild
->wc
.wildcards
& f
->wildcards
) == f
->wildcards
||
169 !memcmp(wild_field
, fixed_field
, f
->len
)) {
170 /* Definite match. */
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
)) {
190 static struct cls_rule
*
191 tcls_lookup(const struct tcls
*cls
, const flow_t
*flow
, int include
)
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
;
207 tcls_delete_matches(struct tcls
*cls
,
208 const struct cls_rule
*target
,
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
);
225 #ifdef WORDS_BIGENDIAN
226 #define HTONL(VALUE) ((uint32_t) (VALUE))
227 #define HTONS(VALUE) ((uint32_t) (VALUE))
229 #define HTONL(VALUE) (((((uint32_t) (VALUE)) & 0x000000ff) << 24) | \
230 ((((uint32_t) (VALUE)) & 0x0000ff00) << 8) | \
231 ((((uint32_t) (VALUE)) & 0x00ff0000) >> 8) | \
232 ((((uint32_t) (VALUE)) & 0xff000000) >> 24))
233 #define HTONS(VALUE) (((((uint16_t) (VALUE)) & 0xff00) >> 8) | \
234 ((((uint16_t) (VALUE)) & 0x00ff) << 8))
237 static uint32_t nw_src_values
[] = { HTONL(0xc0a80001),
239 static uint32_t nw_dst_values
[] = { HTONL(0xc0a80002),
241 static uint16_t in_port_values
[] = { HTONS(1), HTONS(OFPP_LOCAL
) };
242 static uint16_t dl_vlan_values
[] = { HTONS(101), HTONS(0) };
243 static uint16_t dl_type_values
[] = { HTONS(ETH_TYPE_IP
), HTONS(ETH_TYPE_ARP
) };
244 static uint16_t tp_src_values
[] = { HTONS(49362), HTONS(80) };
245 static uint16_t tp_dst_values
[] = { HTONS(6667), HTONS(22) };
246 static uint8_t dl_src_values
[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 },
247 { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } };
248 static uint8_t dl_dst_values
[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 },
249 { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } };
250 static uint8_t nw_proto_values
[] = { IP_TYPE_TCP
, IP_TYPE_ICMP
};
252 static void *values
[CLS_N_FIELDS
][2];
257 values
[CLS_F_IDX_IN_PORT
][0] = &in_port_values
[0];
258 values
[CLS_F_IDX_IN_PORT
][1] = &in_port_values
[1];
260 values
[CLS_F_IDX_DL_VLAN
][0] = &dl_vlan_values
[0];
261 values
[CLS_F_IDX_DL_VLAN
][1] = &dl_vlan_values
[1];
263 values
[CLS_F_IDX_DL_SRC
][0] = dl_src_values
[0];
264 values
[CLS_F_IDX_DL_SRC
][1] = dl_src_values
[1];
266 values
[CLS_F_IDX_DL_DST
][0] = dl_dst_values
[0];
267 values
[CLS_F_IDX_DL_DST
][1] = dl_dst_values
[1];
269 values
[CLS_F_IDX_DL_TYPE
][0] = &dl_type_values
[0];
270 values
[CLS_F_IDX_DL_TYPE
][1] = &dl_type_values
[1];
272 values
[CLS_F_IDX_NW_SRC
][0] = &nw_src_values
[0];
273 values
[CLS_F_IDX_NW_SRC
][1] = &nw_src_values
[1];
275 values
[CLS_F_IDX_NW_DST
][0] = &nw_dst_values
[0];
276 values
[CLS_F_IDX_NW_DST
][1] = &nw_dst_values
[1];
278 values
[CLS_F_IDX_NW_PROTO
][0] = &nw_proto_values
[0];
279 values
[CLS_F_IDX_NW_PROTO
][1] = &nw_proto_values
[1];
281 values
[CLS_F_IDX_TP_SRC
][0] = &tp_src_values
[0];
282 values
[CLS_F_IDX_TP_SRC
][1] = &tp_src_values
[1];
284 values
[CLS_F_IDX_TP_DST
][0] = &tp_dst_values
[0];
285 values
[CLS_F_IDX_TP_DST
][1] = &tp_dst_values
[1];
288 #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values)
289 #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values)
290 #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values)
291 #define N_DL_VLAN_VALUES ARRAY_SIZE(dl_vlan_values)
292 #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values)
293 #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values)
294 #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values)
295 #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values)
296 #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values)
297 #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values)
299 #define N_FLOW_VALUES (N_NW_SRC_VALUES * \
311 get_value(unsigned int *x
, unsigned n_values
)
313 unsigned int rem
= *x
% n_values
;
318 static struct cls_rule
*
319 lookup_with_include_bits(const struct classifier
*cls
,
320 const flow_t
*flow
, int include
)
324 return classifier_lookup_wild(cls
, flow
);
326 return classifier_lookup_exact(cls
, flow
);
327 case CLS_INC_WILD
| CLS_INC_EXACT
:
328 return classifier_lookup(cls
, flow
);
335 compare_classifiers(struct classifier
*cls
, struct tcls
*tcls
)
339 assert(classifier_count(cls
) == tcls
->n_rules
);
340 assert(classifier_count_exact(cls
) == tcls_count_exact(tcls
));
341 for (i
= 0; i
< N_FLOW_VALUES
; i
++) {
342 struct cls_rule
*cr0
, *cr1
;
348 flow
.nw_src
= nw_src_values
[get_value(&x
, N_NW_SRC_VALUES
)];
349 flow
.nw_dst
= nw_dst_values
[get_value(&x
, N_NW_DST_VALUES
)];
350 flow
.in_port
= in_port_values
[get_value(&x
, N_IN_PORT_VALUES
)];
351 flow
.dl_vlan
= dl_vlan_values
[get_value(&x
, N_DL_VLAN_VALUES
)];
352 flow
.dl_type
= dl_type_values
[get_value(&x
, N_DL_TYPE_VALUES
)];
353 flow
.tp_src
= tp_src_values
[get_value(&x
, N_TP_SRC_VALUES
)];
354 flow
.tp_dst
= tp_dst_values
[get_value(&x
, N_TP_DST_VALUES
)];
355 memcpy(flow
.dl_src
, dl_src_values
[get_value(&x
, N_DL_SRC_VALUES
)],
357 memcpy(flow
.dl_dst
, dl_dst_values
[get_value(&x
, N_DL_DST_VALUES
)],
359 flow
.nw_proto
= nw_proto_values
[get_value(&x
, N_NW_PROTO_VALUES
)];
362 for (include
= 1; include
<= 3; include
++) {
363 cr0
= lookup_with_include_bits(cls
, &flow
, include
);
364 cr1
= tcls_lookup(tcls
, &flow
, include
);
365 assert((cr0
== NULL
) == (cr1
== NULL
));
367 const struct test_rule
*tr0
= test_rule_from_cls_rule(cr0
);
368 const struct test_rule
*tr1
= test_rule_from_cls_rule(cr1
);
370 assert(flow_equal(&cr0
->flow
, &cr1
->flow
));
371 assert(cr0
->wc
.wildcards
== cr1
->wc
.wildcards
);
372 assert(cr0
->priority
== cr1
->priority
);
373 /* Skip nw_src_mask and nw_dst_mask, because they are derived
374 * members whose values are used only for optimization. */
375 assert(tr0
->aux
== tr1
->aux
);
382 free_rule(struct cls_rule
*cls_rule
, void *cls
)
384 classifier_remove(cls
, cls_rule
);
385 free(test_rule_from_cls_rule(cls_rule
));
389 destroy_classifier(struct classifier
*cls
)
391 classifier_for_each(cls
, CLS_INC_ALL
, free_rule
, cls
);
392 classifier_destroy(cls
);
396 check_tables(const struct classifier
*cls
,
397 int n_tables
, int n_buckets
, int n_rules
)
399 int found_tables
= 0;
400 int found_buckets
= 0;
404 BUILD_ASSERT(CLS_N_FIELDS
== ARRAY_SIZE(cls
->tables
));
405 for (i
= 0; i
< CLS_N_FIELDS
; i
++) {
406 const struct cls_bucket
*bucket
;
407 if (!hmap_is_empty(&cls
->tables
[i
])) {
410 HMAP_FOR_EACH (bucket
, struct cls_bucket
, hmap_node
, &cls
->tables
[i
]) {
412 assert(!list_is_empty(&bucket
->rules
));
413 found_rules
+= list_size(&bucket
->rules
);
417 if (!hmap_is_empty(&cls
->exact_table
)) {
420 found_rules
+= hmap_count(&cls
->exact_table
);
423 assert(n_tables
== -1 || found_tables
== n_tables
);
424 assert(n_rules
== -1 || found_rules
== n_rules
);
425 assert(n_buckets
== -1 || found_buckets
== n_buckets
);
428 static struct test_rule
*
429 make_rule(int wc_fields
, unsigned int priority
, int value_pat
)
431 const struct cls_field
*f
;
432 struct test_rule
*rule
;
437 memset(&flow
, 0, sizeof flow
);
438 for (f
= &cls_fields
[0]; f
< &cls_fields
[CLS_N_FIELDS
]; f
++) {
439 int f_idx
= f
- cls_fields
;
440 if (wc_fields
& (1u << f_idx
)) {
441 wildcards
|= f
->wildcards
;
443 int value_idx
= (value_pat
& (1u << f_idx
)) != 0;
444 memcpy((char *) &flow
+ f
->ofs
, values
[f_idx
][value_idx
], f
->len
);
448 rule
= xcalloc(1, sizeof *rule
);
449 cls_rule_from_flow(&rule
->cls_rule
, &flow
, wildcards
,
450 !wildcards
? UINT_MAX
: priority
);
455 shuffle(unsigned int *p
, size_t n
)
457 for (; n
> 1; n
--, p
++) {
458 unsigned int *q
= &p
[rand() % n
];
459 unsigned int tmp
= *p
;
465 /* Tests an empty classifier. */
469 struct classifier cls
;
472 classifier_init(&cls
);
474 assert(classifier_is_empty(&cls
));
475 assert(tcls_is_empty(&tcls
));
476 compare_classifiers(&cls
, &tcls
);
477 classifier_destroy(&cls
);
481 /* Destroys a null classifier. */
483 test_destroy_null(void)
485 classifier_destroy(NULL
);
488 /* Tests classification with one rule at a time. */
490 test_single_rule(void)
492 unsigned int wc_fields
; /* Hilarious. */
494 for (wc_fields
= 0; wc_fields
< (1u << CLS_N_FIELDS
); wc_fields
++) {
495 struct classifier cls
;
496 struct test_rule
*rule
, *tcls_rule
;
499 rule
= make_rule(wc_fields
,
500 hash_bytes(&wc_fields
, sizeof wc_fields
, 0), 0);
502 classifier_init(&cls
);
505 tcls_rule
= tcls_insert(&tcls
, rule
);
507 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
509 classifier_insert_exact(&cls
, &rule
->cls_rule
);
511 check_tables(&cls
, 1, 1, 1);
512 compare_classifiers(&cls
, &tcls
);
514 classifier_remove(&cls
, &rule
->cls_rule
);
515 tcls_remove(&tcls
, tcls_rule
);
516 assert(classifier_is_empty(&cls
));
517 assert(tcls_is_empty(&tcls
));
518 compare_classifiers(&cls
, &tcls
);
521 classifier_destroy(&cls
);
526 /* Tests replacing one rule by another. */
528 test_rule_replacement(void)
530 unsigned int wc_fields
;
532 for (wc_fields
= 0; wc_fields
< (1u << CLS_N_FIELDS
); wc_fields
++) {
533 struct classifier cls
;
534 struct test_rule
*rule1
, *tcls_rule1
;
535 struct test_rule
*rule2
, *tcls_rule2
;
538 rule1
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
539 rule2
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
543 classifier_init(&cls
);
545 tcls_rule1
= tcls_insert(&tcls
, rule1
);
546 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
547 check_tables(&cls
, 1, 1, 1);
548 compare_classifiers(&cls
, &tcls
);
552 tcls_rule2
= tcls_insert(&tcls
, rule2
);
553 assert(test_rule_from_cls_rule(
554 classifier_insert(&cls
, &rule2
->cls_rule
)) == rule1
);
556 check_tables(&cls
, 1, 1, 1);
557 compare_classifiers(&cls
, &tcls
);
559 destroy_classifier(&cls
);
564 table_mask(int table
)
566 return ((1u << CLS_N_FIELDS
) - 1) & ~((1u << table
) - 1);
570 random_wcf_in_table(int table
, int seed
)
572 int wc_fields
= (1u << table
) | hash_int(seed
, 0);
573 return wc_fields
& table_mask(table
);
576 /* Tests classification with two rules at a time that fall into the same
579 test_two_rules_in_one_bucket(void)
581 int table
, rel_pri
, wcf_pat
, value_pat
;
583 for (table
= 0; table
<= CLS_N_FIELDS
; table
++) {
584 for (rel_pri
= -1; rel_pri
<= +1; rel_pri
++) {
585 for (wcf_pat
= 0; wcf_pat
< 4; wcf_pat
++) {
586 int n_value_pats
= table
== CLS_N_FIELDS
- 1 ? 1 : 2;
587 for (value_pat
= 0; value_pat
< n_value_pats
; value_pat
++) {
588 struct test_rule
*rule1
, *tcls_rule1
;
589 struct test_rule
*rule2
, *tcls_rule2
;
590 struct test_rule
*displaced_rule
;
591 struct classifier cls
;
593 unsigned int pri1
, pri2
;
596 if (table
!= CLS_F_IDX_EXACT
) {
597 /* We can use identical priorities in this test because
598 * the classifier always chooses the rule added later
599 * for equal-priority rules that fall into the same
601 pri1
= table
* 257 + 50;
602 pri2
= pri1
+ rel_pri
;
605 ? random_wcf_in_table(table
, pri1
)
608 ? random_wcf_in_table(table
, pri2
)
611 wcf1
&= ~(1u << (CLS_N_FIELDS
- 1));
612 wcf2
&= ~(1u << (CLS_N_FIELDS
- 1));
615 /* This classifier always puts exact-match rules at
616 * maximum priority. */
617 pri1
= pri2
= UINT_MAX
;
619 /* No wildcard fields. */
623 rule1
= make_rule(wcf1
, pri1
, 0);
624 rule2
= make_rule(wcf2
, pri2
,
625 value_pat
<< (CLS_N_FIELDS
- 1));
627 classifier_init(&cls
);
630 tcls_rule1
= tcls_insert(&tcls
, rule1
);
631 tcls_rule2
= tcls_insert(&tcls
, rule2
);
632 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
633 displaced_rule
= test_rule_from_cls_rule(
634 classifier_insert(&cls
, &rule2
->cls_rule
));
635 if (wcf1
!= wcf2
|| pri1
!= pri2
|| value_pat
) {
636 assert(!displaced_rule
);
638 check_tables(&cls
, 1, 1, 2);
639 compare_classifiers(&cls
, &tcls
);
641 classifier_remove(&cls
, &rule1
->cls_rule
);
642 tcls_remove(&tcls
, tcls_rule1
);
643 check_tables(&cls
, 1, 1, 1);
644 compare_classifiers(&cls
, &tcls
);
646 assert(displaced_rule
== rule1
);
647 check_tables(&cls
, 1, 1, 1);
648 compare_classifiers(&cls
, &tcls
);
652 classifier_remove(&cls
, &rule2
->cls_rule
);
653 tcls_remove(&tcls
, tcls_rule2
);
654 compare_classifiers(&cls
, &tcls
);
657 destroy_classifier(&cls
);
665 /* Tests classification with two rules at a time that fall into the same
666 * table but different buckets. */
668 test_two_rules_in_one_table(void)
670 int table
, rel_pri
, wcf_pat
;
672 /* Skip tables 0 and CLS_F_IDX_EXACT because they have one bucket. */
673 for (table
= 1; table
< CLS_N_FIELDS
; table
++) {
674 for (rel_pri
= -1; rel_pri
<= +1; rel_pri
++) {
675 for (wcf_pat
= 0; wcf_pat
< 5; wcf_pat
++) {
676 struct test_rule
*rule1
, *tcls_rule1
;
677 struct test_rule
*rule2
, *tcls_rule2
;
678 struct classifier cls
;
680 unsigned int pri1
, pri2
;
682 int value_mask
, value_pat1
, value_pat2
;
685 /* We can use identical priorities in this test because the
686 * classifier always chooses the rule added later for
687 * equal-priority rules that fall into the same table. */
688 pri1
= table
* 257 + 50;
689 pri2
= pri1
+ rel_pri
;
692 wcf1
= wcf2
= random_wcf_in_table(table
, pri1
);
695 ? random_wcf_in_table(table
, pri1
)
698 ? random_wcf_in_table(table
, pri2
)
702 /* Generate value patterns that will put the two rules into
703 * different buckets. */
704 value_mask
= ((1u << table
) - 1);
705 value_pat1
= hash_int(pri1
, 1) & value_mask
;
708 value_pat2
= (hash_int(pri2
, i
++) & value_mask
);
709 } while (value_pat1
== value_pat2
);
710 rule1
= make_rule(wcf1
, pri1
, value_pat1
);
711 rule2
= make_rule(wcf2
, pri2
, value_pat2
);
713 classifier_init(&cls
);
716 tcls_rule1
= tcls_insert(&tcls
, rule1
);
717 tcls_rule2
= tcls_insert(&tcls
, rule2
);
718 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
719 assert(!classifier_insert(&cls
, &rule2
->cls_rule
));
720 check_tables(&cls
, 1, 2, 2);
721 compare_classifiers(&cls
, &tcls
);
723 classifier_remove(&cls
, &rule1
->cls_rule
);
724 tcls_remove(&tcls
, tcls_rule1
);
725 check_tables(&cls
, 1, 1, 1);
726 compare_classifiers(&cls
, &tcls
);
729 classifier_remove(&cls
, &rule2
->cls_rule
);
730 tcls_remove(&tcls
, tcls_rule2
);
731 compare_classifiers(&cls
, &tcls
);
734 classifier_destroy(&cls
);
741 /* Tests classification with two rules at a time that fall into different
744 test_two_rules_in_different_tables(void)
746 int table1
, table2
, rel_pri
, wcf_pat
;
748 for (table1
= 0; table1
< CLS_N_FIELDS
; table1
++) {
749 for (table2
= table1
+ 1; table2
<= CLS_N_FIELDS
; table2
++) {
750 for (rel_pri
= 0; rel_pri
< 2; rel_pri
++) {
751 for (wcf_pat
= 0; wcf_pat
< 4; wcf_pat
++) {
752 struct test_rule
*rule1
, *tcls_rule1
;
753 struct test_rule
*rule2
, *tcls_rule2
;
754 struct classifier cls
;
756 unsigned int pri1
, pri2
;
759 /* We must use unique priorities in this test because the
760 * classifier makes the rule choice undefined for rules of
761 * equal priority that fall into different tables. (In
762 * practice, lower-numbered tables win.) */
763 pri1
= table1
* 257 + 50;
764 pri2
= rel_pri
? pri1
- 1 : pri1
+ 1;
767 ? random_wcf_in_table(table1
, pri1
)
770 ? random_wcf_in_table(table2
, pri2
)
773 if (table2
== CLS_F_IDX_EXACT
) {
778 rule1
= make_rule(wcf1
, pri1
, 0);
779 rule2
= make_rule(wcf2
, pri2
, 0);
781 classifier_init(&cls
);
784 tcls_rule1
= tcls_insert(&tcls
, rule1
);
785 tcls_rule2
= tcls_insert(&tcls
, rule2
);
786 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
787 assert(!classifier_insert(&cls
, &rule2
->cls_rule
));
788 check_tables(&cls
, 2, 2, 2);
789 compare_classifiers(&cls
, &tcls
);
791 classifier_remove(&cls
, &rule1
->cls_rule
);
792 tcls_remove(&tcls
, tcls_rule1
);
793 check_tables(&cls
, 1, 1, 1);
794 compare_classifiers(&cls
, &tcls
);
797 classifier_remove(&cls
, &rule2
->cls_rule
);
798 tcls_remove(&tcls
, tcls_rule2
);
799 compare_classifiers(&cls
, &tcls
);
802 classifier_destroy(&cls
);
810 /* Tests classification with many rules at a time that fall into the same
811 * bucket but have unique priorities (and various wildcards). */
813 test_many_rules_in_one_bucket(void)
815 enum { MAX_RULES
= 50 };
816 int iteration
, table
;
818 for (iteration
= 0; iteration
< 3; iteration
++) {
819 for (table
= 0; table
<= CLS_N_FIELDS
; table
++) {
820 unsigned int priorities
[MAX_RULES
];
821 struct classifier cls
;
825 srand(hash_int(table
, iteration
));
826 for (i
= 0; i
< MAX_RULES
; i
++) {
827 priorities
[i
] = i
* 129;
829 shuffle(priorities
, ARRAY_SIZE(priorities
));
831 classifier_init(&cls
);
834 for (i
= 0; i
< MAX_RULES
; i
++) {
835 struct test_rule
*rule
;
836 unsigned int priority
= priorities
[i
];
839 wcf
= random_wcf_in_table(table
, priority
);
840 rule
= make_rule(wcf
, priority
,
841 table
== CLS_F_IDX_EXACT
? i
: 1234);
842 tcls_insert(&tcls
, rule
);
843 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
844 check_tables(&cls
, 1, 1, i
+ 1);
845 compare_classifiers(&cls
, &tcls
);
848 destroy_classifier(&cls
);
854 /* Tests classification with many rules at a time that fall into the same
855 * table but random buckets. */
857 test_many_rules_in_one_table(void)
859 enum { MAX_RULES
= 50 };
860 int iteration
, table
;
862 for (iteration
= 0; iteration
< 3; iteration
++) {
863 for (table
= 0; table
< CLS_N_FIELDS
; table
++) {
864 unsigned int priorities
[MAX_RULES
];
865 struct classifier cls
;
869 srand(hash_int(table
, iteration
));
870 for (i
= 0; i
< MAX_RULES
; i
++) {
871 priorities
[i
] = i
* 129;
873 shuffle(priorities
, ARRAY_SIZE(priorities
));
875 classifier_init(&cls
);
878 for (i
= 0; i
< MAX_RULES
; i
++) {
879 struct test_rule
*rule
;
880 unsigned int priority
= priorities
[i
];
883 wcf
= random_wcf_in_table(table
, priority
);
884 rule
= make_rule(wcf
, priority
, hash_int(priority
, 1));
885 tcls_insert(&tcls
, rule
);
886 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
887 check_tables(&cls
, 1, -1, i
+ 1);
888 compare_classifiers(&cls
, &tcls
);
891 destroy_classifier(&cls
);
897 /* Tests classification with many rules at a time that fall into random buckets
898 * in random tables. */
900 test_many_rules_in_different_tables(void)
902 enum { MAX_RULES
= 50 };
905 for (iteration
= 0; iteration
< 30; iteration
++) {
906 unsigned int priorities
[MAX_RULES
];
907 struct classifier cls
;
912 for (i
= 0; i
< MAX_RULES
; i
++) {
913 priorities
[i
] = i
* 129;
915 shuffle(priorities
, ARRAY_SIZE(priorities
));
917 classifier_init(&cls
);
920 for (i
= 0; i
< MAX_RULES
; i
++) {
921 struct test_rule
*rule
;
922 unsigned int priority
= priorities
[i
];
923 int table
= rand() % (CLS_N_FIELDS
+ 1);
924 int wcf
= random_wcf_in_table(table
, rand());
925 int value_pat
= rand() & ((1u << CLS_N_FIELDS
) - 1);
926 rule
= make_rule(wcf
, priority
, value_pat
);
927 tcls_insert(&tcls
, rule
);
928 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
929 check_tables(&cls
, -1, -1, i
+ 1);
930 compare_classifiers(&cls
, &tcls
);
933 while (!classifier_is_empty(&cls
)) {
934 struct test_rule
*rule
= xmemdup(tcls
.rules
[rand() % tcls
.n_rules
],
935 sizeof(struct test_rule
));
936 int include
= rand() % 2 ? CLS_INC_WILD
: CLS_INC_EXACT
;
937 include
|= (rule
->cls_rule
.wc
.wildcards
938 ? CLS_INC_WILD
: CLS_INC_EXACT
);
939 classifier_for_each_match(&cls
, &rule
->cls_rule
, include
,
941 tcls_delete_matches(&tcls
, &rule
->cls_rule
, include
);
942 compare_classifiers(&cls
, &tcls
);
948 destroy_classifier(&cls
);
954 run_test(void (*function
)(void))
965 run_test(test_empty
);
966 run_test(test_destroy_null
);
967 run_test(test_single_rule
);
968 run_test(test_rule_replacement
);
969 run_test(test_two_rules_in_one_bucket
);
970 run_test(test_two_rules_in_one_table
);
971 run_test(test_two_rules_in_different_tables
);
972 run_test(test_many_rules_in_one_bucket
);
973 run_test(test_many_rules_in_one_table
);
974 run_test(test_many_rules_in_different_tables
);