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 T_HTONL(VALUE) ((uint32_t) (VALUE))
227 #define T_HTONS(VALUE) ((uint32_t) (VALUE))
229 #define T_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 T_HTONS(VALUE) (((((uint16_t) (VALUE)) & 0xff00) >> 8) | \
234 ((((uint16_t) (VALUE)) & 0x00ff) << 8))
237 static uint32_t nw_src_values
[] = { T_HTONL(0xc0a80001),
238 T_HTONL(0xc0a04455) };
239 static uint32_t nw_dst_values
[] = { T_HTONL(0xc0a80002),
240 T_HTONL(0xc0a04455) };
241 static uint16_t in_port_values
[] = { T_HTONS(1), T_HTONS(OFPP_LOCAL
) };
242 static uint16_t dl_vlan_values
[] = { T_HTONS(101), T_HTONS(0) };
243 static uint16_t dl_type_values
[]
244 = { T_HTONS(ETH_TYPE_IP
), T_HTONS(ETH_TYPE_ARP
) };
245 static uint16_t tp_src_values
[] = { T_HTONS(49362), T_HTONS(80) };
246 static uint16_t tp_dst_values
[] = { T_HTONS(6667), T_HTONS(22) };
247 static uint8_t dl_src_values
[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 },
248 { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } };
249 static uint8_t dl_dst_values
[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 },
250 { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } };
251 static uint8_t nw_proto_values
[] = { IP_TYPE_TCP
, IP_TYPE_ICMP
};
253 static void *values
[CLS_N_FIELDS
][2];
258 values
[CLS_F_IDX_IN_PORT
][0] = &in_port_values
[0];
259 values
[CLS_F_IDX_IN_PORT
][1] = &in_port_values
[1];
261 values
[CLS_F_IDX_DL_VLAN
][0] = &dl_vlan_values
[0];
262 values
[CLS_F_IDX_DL_VLAN
][1] = &dl_vlan_values
[1];
264 values
[CLS_F_IDX_DL_SRC
][0] = dl_src_values
[0];
265 values
[CLS_F_IDX_DL_SRC
][1] = dl_src_values
[1];
267 values
[CLS_F_IDX_DL_DST
][0] = dl_dst_values
[0];
268 values
[CLS_F_IDX_DL_DST
][1] = dl_dst_values
[1];
270 values
[CLS_F_IDX_DL_TYPE
][0] = &dl_type_values
[0];
271 values
[CLS_F_IDX_DL_TYPE
][1] = &dl_type_values
[1];
273 values
[CLS_F_IDX_NW_SRC
][0] = &nw_src_values
[0];
274 values
[CLS_F_IDX_NW_SRC
][1] = &nw_src_values
[1];
276 values
[CLS_F_IDX_NW_DST
][0] = &nw_dst_values
[0];
277 values
[CLS_F_IDX_NW_DST
][1] = &nw_dst_values
[1];
279 values
[CLS_F_IDX_NW_PROTO
][0] = &nw_proto_values
[0];
280 values
[CLS_F_IDX_NW_PROTO
][1] = &nw_proto_values
[1];
282 values
[CLS_F_IDX_TP_SRC
][0] = &tp_src_values
[0];
283 values
[CLS_F_IDX_TP_SRC
][1] = &tp_src_values
[1];
285 values
[CLS_F_IDX_TP_DST
][0] = &tp_dst_values
[0];
286 values
[CLS_F_IDX_TP_DST
][1] = &tp_dst_values
[1];
289 #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values)
290 #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values)
291 #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values)
292 #define N_DL_VLAN_VALUES ARRAY_SIZE(dl_vlan_values)
293 #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values)
294 #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values)
295 #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values)
296 #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values)
297 #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values)
298 #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values)
300 #define N_FLOW_VALUES (N_NW_SRC_VALUES * \
312 get_value(unsigned int *x
, unsigned n_values
)
314 unsigned int rem
= *x
% n_values
;
319 static struct cls_rule
*
320 lookup_with_include_bits(const struct classifier
*cls
,
321 const flow_t
*flow
, int include
)
325 return classifier_lookup_wild(cls
, flow
);
327 return classifier_lookup_exact(cls
, flow
);
328 case CLS_INC_WILD
| CLS_INC_EXACT
:
329 return classifier_lookup(cls
, flow
);
336 compare_classifiers(struct classifier
*cls
, struct tcls
*tcls
)
340 assert(classifier_count(cls
) == tcls
->n_rules
);
341 assert(classifier_count_exact(cls
) == tcls_count_exact(tcls
));
342 for (i
= 0; i
< N_FLOW_VALUES
; i
++) {
343 struct cls_rule
*cr0
, *cr1
;
349 flow
.nw_src
= nw_src_values
[get_value(&x
, N_NW_SRC_VALUES
)];
350 flow
.nw_dst
= nw_dst_values
[get_value(&x
, N_NW_DST_VALUES
)];
351 flow
.in_port
= in_port_values
[get_value(&x
, N_IN_PORT_VALUES
)];
352 flow
.dl_vlan
= dl_vlan_values
[get_value(&x
, N_DL_VLAN_VALUES
)];
353 flow
.dl_type
= dl_type_values
[get_value(&x
, N_DL_TYPE_VALUES
)];
354 flow
.tp_src
= tp_src_values
[get_value(&x
, N_TP_SRC_VALUES
)];
355 flow
.tp_dst
= tp_dst_values
[get_value(&x
, N_TP_DST_VALUES
)];
356 memcpy(flow
.dl_src
, dl_src_values
[get_value(&x
, N_DL_SRC_VALUES
)],
358 memcpy(flow
.dl_dst
, dl_dst_values
[get_value(&x
, N_DL_DST_VALUES
)],
360 flow
.nw_proto
= nw_proto_values
[get_value(&x
, N_NW_PROTO_VALUES
)];
363 for (include
= 1; include
<= 3; include
++) {
364 cr0
= lookup_with_include_bits(cls
, &flow
, include
);
365 cr1
= tcls_lookup(tcls
, &flow
, include
);
366 assert((cr0
== NULL
) == (cr1
== NULL
));
368 const struct test_rule
*tr0
= test_rule_from_cls_rule(cr0
);
369 const struct test_rule
*tr1
= test_rule_from_cls_rule(cr1
);
371 assert(flow_equal(&cr0
->flow
, &cr1
->flow
));
372 assert(cr0
->wc
.wildcards
== cr1
->wc
.wildcards
);
373 assert(cr0
->priority
== cr1
->priority
);
374 /* Skip nw_src_mask and nw_dst_mask, because they are derived
375 * members whose values are used only for optimization. */
376 assert(tr0
->aux
== tr1
->aux
);
383 free_rule(struct cls_rule
*cls_rule
, void *cls
)
385 classifier_remove(cls
, cls_rule
);
386 free(test_rule_from_cls_rule(cls_rule
));
390 destroy_classifier(struct classifier
*cls
)
392 classifier_for_each(cls
, CLS_INC_ALL
, free_rule
, cls
);
393 classifier_destroy(cls
);
397 check_tables(const struct classifier
*cls
,
398 int n_tables
, int n_buckets
, int n_rules
)
400 int found_tables
= 0;
401 int found_buckets
= 0;
405 BUILD_ASSERT(CLS_N_FIELDS
== ARRAY_SIZE(cls
->tables
));
406 for (i
= 0; i
< CLS_N_FIELDS
; i
++) {
407 const struct cls_bucket
*bucket
;
408 if (!hmap_is_empty(&cls
->tables
[i
])) {
411 HMAP_FOR_EACH (bucket
, struct cls_bucket
, hmap_node
, &cls
->tables
[i
]) {
413 assert(!list_is_empty(&bucket
->rules
));
414 found_rules
+= list_size(&bucket
->rules
);
418 if (!hmap_is_empty(&cls
->exact_table
)) {
421 found_rules
+= hmap_count(&cls
->exact_table
);
424 assert(n_tables
== -1 || found_tables
== n_tables
);
425 assert(n_rules
== -1 || found_rules
== n_rules
);
426 assert(n_buckets
== -1 || found_buckets
== n_buckets
);
429 static struct test_rule
*
430 make_rule(int wc_fields
, unsigned int priority
, int value_pat
)
432 const struct cls_field
*f
;
433 struct test_rule
*rule
;
438 memset(&flow
, 0, sizeof flow
);
439 for (f
= &cls_fields
[0]; f
< &cls_fields
[CLS_N_FIELDS
]; f
++) {
440 int f_idx
= f
- cls_fields
;
441 if (wc_fields
& (1u << f_idx
)) {
442 wildcards
|= f
->wildcards
;
444 int value_idx
= (value_pat
& (1u << f_idx
)) != 0;
445 memcpy((char *) &flow
+ f
->ofs
, values
[f_idx
][value_idx
], f
->len
);
449 rule
= xcalloc(1, sizeof *rule
);
450 cls_rule_from_flow(&rule
->cls_rule
, &flow
, wildcards
,
451 !wildcards
? UINT_MAX
: priority
);
456 shuffle(unsigned int *p
, size_t n
)
458 for (; n
> 1; n
--, p
++) {
459 unsigned int *q
= &p
[rand() % n
];
460 unsigned int tmp
= *p
;
466 /* Tests an empty classifier. */
470 struct classifier cls
;
473 classifier_init(&cls
);
475 assert(classifier_is_empty(&cls
));
476 assert(tcls_is_empty(&tcls
));
477 compare_classifiers(&cls
, &tcls
);
478 classifier_destroy(&cls
);
482 /* Destroys a null classifier. */
484 test_destroy_null(void)
486 classifier_destroy(NULL
);
489 /* Tests classification with one rule at a time. */
491 test_single_rule(void)
493 unsigned int wc_fields
; /* Hilarious. */
495 for (wc_fields
= 0; wc_fields
< (1u << CLS_N_FIELDS
); wc_fields
++) {
496 struct classifier cls
;
497 struct test_rule
*rule
, *tcls_rule
;
500 rule
= make_rule(wc_fields
,
501 hash_bytes(&wc_fields
, sizeof wc_fields
, 0), 0);
503 classifier_init(&cls
);
506 tcls_rule
= tcls_insert(&tcls
, rule
);
508 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
510 classifier_insert_exact(&cls
, &rule
->cls_rule
);
512 check_tables(&cls
, 1, 1, 1);
513 compare_classifiers(&cls
, &tcls
);
515 classifier_remove(&cls
, &rule
->cls_rule
);
516 tcls_remove(&tcls
, tcls_rule
);
517 assert(classifier_is_empty(&cls
));
518 assert(tcls_is_empty(&tcls
));
519 compare_classifiers(&cls
, &tcls
);
522 classifier_destroy(&cls
);
527 /* Tests replacing one rule by another. */
529 test_rule_replacement(void)
531 unsigned int wc_fields
;
533 for (wc_fields
= 0; wc_fields
< (1u << CLS_N_FIELDS
); wc_fields
++) {
534 struct classifier cls
;
535 struct test_rule
*rule1
, *tcls_rule1
;
536 struct test_rule
*rule2
, *tcls_rule2
;
539 rule1
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
540 rule2
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
544 classifier_init(&cls
);
546 tcls_rule1
= tcls_insert(&tcls
, rule1
);
547 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
548 check_tables(&cls
, 1, 1, 1);
549 compare_classifiers(&cls
, &tcls
);
553 tcls_rule2
= tcls_insert(&tcls
, rule2
);
554 assert(test_rule_from_cls_rule(
555 classifier_insert(&cls
, &rule2
->cls_rule
)) == rule1
);
557 check_tables(&cls
, 1, 1, 1);
558 compare_classifiers(&cls
, &tcls
);
560 destroy_classifier(&cls
);
565 table_mask(int table
)
567 return ((1u << CLS_N_FIELDS
) - 1) & ~((1u << table
) - 1);
571 random_wcf_in_table(int table
, int seed
)
573 int wc_fields
= (1u << table
) | hash_int(seed
, 0);
574 return wc_fields
& table_mask(table
);
577 /* Tests classification with two rules at a time that fall into the same
580 test_two_rules_in_one_bucket(void)
582 int table
, rel_pri
, wcf_pat
, value_pat
;
584 for (table
= 0; table
<= CLS_N_FIELDS
; table
++) {
585 for (rel_pri
= -1; rel_pri
<= +1; rel_pri
++) {
586 for (wcf_pat
= 0; wcf_pat
< 4; wcf_pat
++) {
587 int n_value_pats
= table
== CLS_N_FIELDS
- 1 ? 1 : 2;
588 for (value_pat
= 0; value_pat
< n_value_pats
; value_pat
++) {
589 struct test_rule
*rule1
, *tcls_rule1
;
590 struct test_rule
*rule2
, *tcls_rule2
;
591 struct test_rule
*displaced_rule
;
592 struct classifier cls
;
594 unsigned int pri1
, pri2
;
597 if (table
!= CLS_F_IDX_EXACT
) {
598 /* We can use identical priorities in this test because
599 * the classifier always chooses the rule added later
600 * for equal-priority rules that fall into the same
602 pri1
= table
* 257 + 50;
603 pri2
= pri1
+ rel_pri
;
606 ? random_wcf_in_table(table
, pri1
)
609 ? random_wcf_in_table(table
, pri2
)
612 wcf1
&= ~(1u << (CLS_N_FIELDS
- 1));
613 wcf2
&= ~(1u << (CLS_N_FIELDS
- 1));
616 /* This classifier always puts exact-match rules at
617 * maximum priority. */
618 pri1
= pri2
= UINT_MAX
;
620 /* No wildcard fields. */
624 rule1
= make_rule(wcf1
, pri1
, 0);
625 rule2
= make_rule(wcf2
, pri2
,
626 value_pat
<< (CLS_N_FIELDS
- 1));
628 classifier_init(&cls
);
631 tcls_rule1
= tcls_insert(&tcls
, rule1
);
632 tcls_rule2
= tcls_insert(&tcls
, rule2
);
633 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
634 displaced_rule
= test_rule_from_cls_rule(
635 classifier_insert(&cls
, &rule2
->cls_rule
));
636 if (wcf1
!= wcf2
|| pri1
!= pri2
|| value_pat
) {
637 assert(!displaced_rule
);
639 check_tables(&cls
, 1, 1, 2);
640 compare_classifiers(&cls
, &tcls
);
642 classifier_remove(&cls
, &rule1
->cls_rule
);
643 tcls_remove(&tcls
, tcls_rule1
);
644 check_tables(&cls
, 1, 1, 1);
645 compare_classifiers(&cls
, &tcls
);
647 assert(displaced_rule
== rule1
);
648 check_tables(&cls
, 1, 1, 1);
649 compare_classifiers(&cls
, &tcls
);
653 classifier_remove(&cls
, &rule2
->cls_rule
);
654 tcls_remove(&tcls
, tcls_rule2
);
655 compare_classifiers(&cls
, &tcls
);
658 destroy_classifier(&cls
);
666 /* Tests classification with two rules at a time that fall into the same
667 * table but different buckets. */
669 test_two_rules_in_one_table(void)
671 int table
, rel_pri
, wcf_pat
;
673 /* Skip tables 0 and CLS_F_IDX_EXACT because they have one bucket. */
674 for (table
= 1; table
< CLS_N_FIELDS
; table
++) {
675 for (rel_pri
= -1; rel_pri
<= +1; rel_pri
++) {
676 for (wcf_pat
= 0; wcf_pat
< 5; wcf_pat
++) {
677 struct test_rule
*rule1
, *tcls_rule1
;
678 struct test_rule
*rule2
, *tcls_rule2
;
679 struct classifier cls
;
681 unsigned int pri1
, pri2
;
683 int value_mask
, value_pat1
, value_pat2
;
686 /* We can use identical priorities in this test because the
687 * classifier always chooses the rule added later for
688 * equal-priority rules that fall into the same table. */
689 pri1
= table
* 257 + 50;
690 pri2
= pri1
+ rel_pri
;
693 wcf1
= wcf2
= random_wcf_in_table(table
, pri1
);
696 ? random_wcf_in_table(table
, pri1
)
699 ? random_wcf_in_table(table
, pri2
)
703 /* Generate value patterns that will put the two rules into
704 * different buckets. */
705 value_mask
= ((1u << table
) - 1);
706 value_pat1
= hash_int(pri1
, 1) & value_mask
;
709 value_pat2
= (hash_int(pri2
, i
++) & value_mask
);
710 } while (value_pat1
== value_pat2
);
711 rule1
= make_rule(wcf1
, pri1
, value_pat1
);
712 rule2
= make_rule(wcf2
, pri2
, value_pat2
);
714 classifier_init(&cls
);
717 tcls_rule1
= tcls_insert(&tcls
, rule1
);
718 tcls_rule2
= tcls_insert(&tcls
, rule2
);
719 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
720 assert(!classifier_insert(&cls
, &rule2
->cls_rule
));
721 check_tables(&cls
, 1, 2, 2);
722 compare_classifiers(&cls
, &tcls
);
724 classifier_remove(&cls
, &rule1
->cls_rule
);
725 tcls_remove(&tcls
, tcls_rule1
);
726 check_tables(&cls
, 1, 1, 1);
727 compare_classifiers(&cls
, &tcls
);
730 classifier_remove(&cls
, &rule2
->cls_rule
);
731 tcls_remove(&tcls
, tcls_rule2
);
732 compare_classifiers(&cls
, &tcls
);
735 classifier_destroy(&cls
);
742 /* Tests classification with two rules at a time that fall into different
745 test_two_rules_in_different_tables(void)
747 int table1
, table2
, rel_pri
, wcf_pat
;
749 for (table1
= 0; table1
< CLS_N_FIELDS
; table1
++) {
750 for (table2
= table1
+ 1; table2
<= CLS_N_FIELDS
; table2
++) {
751 for (rel_pri
= 0; rel_pri
< 2; rel_pri
++) {
752 for (wcf_pat
= 0; wcf_pat
< 4; wcf_pat
++) {
753 struct test_rule
*rule1
, *tcls_rule1
;
754 struct test_rule
*rule2
, *tcls_rule2
;
755 struct classifier cls
;
757 unsigned int pri1
, pri2
;
760 /* We must use unique priorities in this test because the
761 * classifier makes the rule choice undefined for rules of
762 * equal priority that fall into different tables. (In
763 * practice, lower-numbered tables win.) */
764 pri1
= table1
* 257 + 50;
765 pri2
= rel_pri
? pri1
- 1 : pri1
+ 1;
768 ? random_wcf_in_table(table1
, pri1
)
771 ? random_wcf_in_table(table2
, pri2
)
774 if (table2
== CLS_F_IDX_EXACT
) {
779 rule1
= make_rule(wcf1
, pri1
, 0);
780 rule2
= make_rule(wcf2
, pri2
, 0);
782 classifier_init(&cls
);
785 tcls_rule1
= tcls_insert(&tcls
, rule1
);
786 tcls_rule2
= tcls_insert(&tcls
, rule2
);
787 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
788 assert(!classifier_insert(&cls
, &rule2
->cls_rule
));
789 check_tables(&cls
, 2, 2, 2);
790 compare_classifiers(&cls
, &tcls
);
792 classifier_remove(&cls
, &rule1
->cls_rule
);
793 tcls_remove(&tcls
, tcls_rule1
);
794 check_tables(&cls
, 1, 1, 1);
795 compare_classifiers(&cls
, &tcls
);
798 classifier_remove(&cls
, &rule2
->cls_rule
);
799 tcls_remove(&tcls
, tcls_rule2
);
800 compare_classifiers(&cls
, &tcls
);
803 classifier_destroy(&cls
);
811 /* Tests classification with many rules at a time that fall into the same
812 * bucket but have unique priorities (and various wildcards). */
814 test_many_rules_in_one_bucket(void)
816 enum { MAX_RULES
= 50 };
817 int iteration
, table
;
819 for (iteration
= 0; iteration
< 3; iteration
++) {
820 for (table
= 0; table
<= CLS_N_FIELDS
; table
++) {
821 unsigned int priorities
[MAX_RULES
];
822 struct classifier cls
;
826 srand(hash_int(table
, iteration
));
827 for (i
= 0; i
< MAX_RULES
; i
++) {
828 priorities
[i
] = i
* 129;
830 shuffle(priorities
, ARRAY_SIZE(priorities
));
832 classifier_init(&cls
);
835 for (i
= 0; i
< MAX_RULES
; i
++) {
836 struct test_rule
*rule
;
837 unsigned int priority
= priorities
[i
];
840 wcf
= random_wcf_in_table(table
, priority
);
841 rule
= make_rule(wcf
, priority
,
842 table
== CLS_F_IDX_EXACT
? i
: 1234);
843 tcls_insert(&tcls
, rule
);
844 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
845 check_tables(&cls
, 1, 1, i
+ 1);
846 compare_classifiers(&cls
, &tcls
);
849 destroy_classifier(&cls
);
855 /* Tests classification with many rules at a time that fall into the same
856 * table but random buckets. */
858 test_many_rules_in_one_table(void)
860 enum { MAX_RULES
= 50 };
861 int iteration
, table
;
863 for (iteration
= 0; iteration
< 3; iteration
++) {
864 for (table
= 0; table
< CLS_N_FIELDS
; table
++) {
865 unsigned int priorities
[MAX_RULES
];
866 struct classifier cls
;
870 srand(hash_int(table
, iteration
));
871 for (i
= 0; i
< MAX_RULES
; i
++) {
872 priorities
[i
] = i
* 129;
874 shuffle(priorities
, ARRAY_SIZE(priorities
));
876 classifier_init(&cls
);
879 for (i
= 0; i
< MAX_RULES
; i
++) {
880 struct test_rule
*rule
;
881 unsigned int priority
= priorities
[i
];
884 wcf
= random_wcf_in_table(table
, priority
);
885 rule
= make_rule(wcf
, priority
, hash_int(priority
, 1));
886 tcls_insert(&tcls
, rule
);
887 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
888 check_tables(&cls
, 1, -1, i
+ 1);
889 compare_classifiers(&cls
, &tcls
);
892 destroy_classifier(&cls
);
898 /* Tests classification with many rules at a time that fall into random buckets
899 * in random tables. */
901 test_many_rules_in_different_tables(void)
903 enum { MAX_RULES
= 50 };
906 for (iteration
= 0; iteration
< 30; iteration
++) {
907 unsigned int priorities
[MAX_RULES
];
908 struct classifier cls
;
913 for (i
= 0; i
< MAX_RULES
; i
++) {
914 priorities
[i
] = i
* 129;
916 shuffle(priorities
, ARRAY_SIZE(priorities
));
918 classifier_init(&cls
);
921 for (i
= 0; i
< MAX_RULES
; i
++) {
922 struct test_rule
*rule
;
923 unsigned int priority
= priorities
[i
];
924 int table
= rand() % (CLS_N_FIELDS
+ 1);
925 int wcf
= random_wcf_in_table(table
, rand());
926 int value_pat
= rand() & ((1u << CLS_N_FIELDS
) - 1);
927 rule
= make_rule(wcf
, priority
, value_pat
);
928 tcls_insert(&tcls
, rule
);
929 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
930 check_tables(&cls
, -1, -1, i
+ 1);
931 compare_classifiers(&cls
, &tcls
);
934 while (!classifier_is_empty(&cls
)) {
935 struct test_rule
*rule
= xmemdup(tcls
.rules
[rand() % tcls
.n_rules
],
936 sizeof(struct test_rule
));
937 int include
= rand() % 2 ? CLS_INC_WILD
: CLS_INC_EXACT
;
938 include
|= (rule
->cls_rule
.wc
.wildcards
939 ? CLS_INC_WILD
: CLS_INC_EXACT
);
940 classifier_for_each_match(&cls
, &rule
->cls_rule
, include
,
942 tcls_delete_matches(&tcls
, &rule
->cls_rule
, include
);
943 compare_classifiers(&cls
, &tcls
);
949 destroy_classifier(&cls
);
955 run_test(void (*function
)(void))
966 run_test(test_empty
);
967 run_test(test_destroy_null
);
968 run_test(test_single_rule
);
969 run_test(test_rule_replacement
);
970 run_test(test_two_rules_in_one_bucket
);
971 run_test(test_two_rules_in_one_table
);
972 run_test(test_two_rules_in_different_tables
);
973 run_test(test_many_rules_in_one_bucket
);
974 run_test(test_many_rules_in_one_table
);
975 run_test(test_many_rules_in_different_tables
);