2 * Copyright (c) 2009, 2010 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 uint8_t dl_vlan_pcp_values
[] = { 7, 0 };
244 static uint16_t dl_type_values
[]
245 = { T_HTONS(ETH_TYPE_IP
), T_HTONS(ETH_TYPE_ARP
) };
246 static uint16_t tp_src_values
[] = { T_HTONS(49362), T_HTONS(80) };
247 static uint16_t tp_dst_values
[] = { T_HTONS(6667), T_HTONS(22) };
248 static uint8_t dl_src_values
[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 },
249 { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } };
250 static uint8_t dl_dst_values
[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 },
251 { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } };
252 static uint8_t nw_proto_values
[] = { IP_TYPE_TCP
, IP_TYPE_ICMP
};
254 static void *values
[CLS_N_FIELDS
][2];
259 values
[CLS_F_IDX_IN_PORT
][0] = &in_port_values
[0];
260 values
[CLS_F_IDX_IN_PORT
][1] = &in_port_values
[1];
262 values
[CLS_F_IDX_DL_VLAN
][0] = &dl_vlan_values
[0];
263 values
[CLS_F_IDX_DL_VLAN
][1] = &dl_vlan_values
[1];
265 values
[CLS_F_IDX_DL_VLAN_PCP
][0] = &dl_vlan_pcp_values
[0];
266 values
[CLS_F_IDX_DL_VLAN_PCP
][1] = &dl_vlan_pcp_values
[1];
268 values
[CLS_F_IDX_DL_SRC
][0] = dl_src_values
[0];
269 values
[CLS_F_IDX_DL_SRC
][1] = dl_src_values
[1];
271 values
[CLS_F_IDX_DL_DST
][0] = dl_dst_values
[0];
272 values
[CLS_F_IDX_DL_DST
][1] = dl_dst_values
[1];
274 values
[CLS_F_IDX_DL_TYPE
][0] = &dl_type_values
[0];
275 values
[CLS_F_IDX_DL_TYPE
][1] = &dl_type_values
[1];
277 values
[CLS_F_IDX_NW_SRC
][0] = &nw_src_values
[0];
278 values
[CLS_F_IDX_NW_SRC
][1] = &nw_src_values
[1];
280 values
[CLS_F_IDX_NW_DST
][0] = &nw_dst_values
[0];
281 values
[CLS_F_IDX_NW_DST
][1] = &nw_dst_values
[1];
283 values
[CLS_F_IDX_NW_PROTO
][0] = &nw_proto_values
[0];
284 values
[CLS_F_IDX_NW_PROTO
][1] = &nw_proto_values
[1];
286 values
[CLS_F_IDX_TP_SRC
][0] = &tp_src_values
[0];
287 values
[CLS_F_IDX_TP_SRC
][1] = &tp_src_values
[1];
289 values
[CLS_F_IDX_TP_DST
][0] = &tp_dst_values
[0];
290 values
[CLS_F_IDX_TP_DST
][1] = &tp_dst_values
[1];
293 #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values)
294 #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values)
295 #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values)
296 #define N_DL_VLAN_VALUES ARRAY_SIZE(dl_vlan_values)
297 #define N_DL_VLAN_PCP_VALUES ARRAY_SIZE(dl_vlan_pcp_values)
298 #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values)
299 #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values)
300 #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values)
301 #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values)
302 #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values)
303 #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values)
305 #define N_FLOW_VALUES (N_NW_SRC_VALUES * \
309 N_DL_VLAN_PCP_VALUES * \
318 get_value(unsigned int *x
, unsigned n_values
)
320 unsigned int rem
= *x
% n_values
;
325 static struct cls_rule
*
326 lookup_with_include_bits(const struct classifier
*cls
,
327 const flow_t
*flow
, int include
)
331 return classifier_lookup_wild(cls
, flow
);
333 return classifier_lookup_exact(cls
, flow
);
334 case CLS_INC_WILD
| CLS_INC_EXACT
:
335 return classifier_lookup(cls
, flow
);
342 compare_classifiers(struct classifier
*cls
, struct tcls
*tcls
)
346 assert(classifier_count(cls
) == tcls
->n_rules
);
347 assert(classifier_count_exact(cls
) == tcls_count_exact(tcls
));
348 for (i
= 0; i
< N_FLOW_VALUES
; i
++) {
349 struct cls_rule
*cr0
, *cr1
;
355 flow
.nw_src
= nw_src_values
[get_value(&x
, N_NW_SRC_VALUES
)];
356 flow
.nw_dst
= nw_dst_values
[get_value(&x
, N_NW_DST_VALUES
)];
357 flow
.in_port
= in_port_values
[get_value(&x
, N_IN_PORT_VALUES
)];
358 flow
.dl_vlan
= dl_vlan_values
[get_value(&x
, N_DL_VLAN_VALUES
)];
359 flow
.dl_vlan_pcp
= dl_vlan_pcp_values
[get_value(&x
,
360 N_DL_VLAN_PCP_VALUES
)];
361 flow
.dl_type
= dl_type_values
[get_value(&x
, N_DL_TYPE_VALUES
)];
362 flow
.tp_src
= tp_src_values
[get_value(&x
, N_TP_SRC_VALUES
)];
363 flow
.tp_dst
= tp_dst_values
[get_value(&x
, N_TP_DST_VALUES
)];
364 memcpy(flow
.dl_src
, dl_src_values
[get_value(&x
, N_DL_SRC_VALUES
)],
366 memcpy(flow
.dl_dst
, dl_dst_values
[get_value(&x
, N_DL_DST_VALUES
)],
368 flow
.nw_proto
= nw_proto_values
[get_value(&x
, N_NW_PROTO_VALUES
)];
370 for (include
= 1; include
<= 3; include
++) {
371 cr0
= lookup_with_include_bits(cls
, &flow
, include
);
372 cr1
= tcls_lookup(tcls
, &flow
, include
);
373 assert((cr0
== NULL
) == (cr1
== NULL
));
375 const struct test_rule
*tr0
= test_rule_from_cls_rule(cr0
);
376 const struct test_rule
*tr1
= test_rule_from_cls_rule(cr1
);
378 assert(flow_equal(&cr0
->flow
, &cr1
->flow
));
379 assert(cr0
->wc
.wildcards
== cr1
->wc
.wildcards
);
380 assert(cr0
->priority
== cr1
->priority
);
381 /* Skip nw_src_mask and nw_dst_mask, because they are derived
382 * members whose values are used only for optimization. */
383 assert(tr0
->aux
== tr1
->aux
);
390 free_rule(struct cls_rule
*cls_rule
, void *cls
)
392 classifier_remove(cls
, cls_rule
);
393 free(test_rule_from_cls_rule(cls_rule
));
397 destroy_classifier(struct classifier
*cls
)
399 classifier_for_each(cls
, CLS_INC_ALL
, free_rule
, cls
);
400 classifier_destroy(cls
);
404 check_tables(const struct classifier
*cls
,
405 int n_tables
, int n_buckets
, int n_rules
)
407 int found_tables
= 0;
408 int found_buckets
= 0;
412 BUILD_ASSERT(CLS_N_FIELDS
== ARRAY_SIZE(cls
->tables
));
413 for (i
= 0; i
< CLS_N_FIELDS
; i
++) {
414 const struct cls_bucket
*bucket
;
415 if (!hmap_is_empty(&cls
->tables
[i
])) {
418 HMAP_FOR_EACH (bucket
, struct cls_bucket
, hmap_node
, &cls
->tables
[i
]) {
420 assert(!list_is_empty(&bucket
->rules
));
421 found_rules
+= list_size(&bucket
->rules
);
425 if (!hmap_is_empty(&cls
->exact_table
)) {
428 found_rules
+= hmap_count(&cls
->exact_table
);
431 assert(n_tables
== -1 || found_tables
== n_tables
);
432 assert(n_rules
== -1 || found_rules
== n_rules
);
433 assert(n_buckets
== -1 || found_buckets
== n_buckets
);
436 static struct test_rule
*
437 make_rule(int wc_fields
, unsigned int priority
, int value_pat
)
439 const struct cls_field
*f
;
440 struct test_rule
*rule
;
445 memset(&flow
, 0, sizeof flow
);
446 for (f
= &cls_fields
[0]; f
< &cls_fields
[CLS_N_FIELDS
]; f
++) {
447 int f_idx
= f
- cls_fields
;
448 if (wc_fields
& (1u << f_idx
)) {
449 wildcards
|= f
->wildcards
;
451 int value_idx
= (value_pat
& (1u << f_idx
)) != 0;
452 memcpy((char *) &flow
+ f
->ofs
, values
[f_idx
][value_idx
], f
->len
);
456 rule
= xzalloc(sizeof *rule
);
457 cls_rule_from_flow(&rule
->cls_rule
, &flow
, wildcards
,
458 !wildcards
? UINT_MAX
: priority
);
463 shuffle(unsigned int *p
, size_t n
)
465 for (; n
> 1; n
--, p
++) {
466 unsigned int *q
= &p
[rand() % n
];
467 unsigned int tmp
= *p
;
473 /* Tests an empty classifier. */
477 struct classifier cls
;
480 classifier_init(&cls
);
482 assert(classifier_is_empty(&cls
));
483 assert(tcls_is_empty(&tcls
));
484 compare_classifiers(&cls
, &tcls
);
485 classifier_destroy(&cls
);
489 /* Destroys a null classifier. */
491 test_destroy_null(void)
493 classifier_destroy(NULL
);
496 /* Tests classification with one rule at a time. */
498 test_single_rule(void)
500 unsigned int wc_fields
; /* Hilarious. */
502 for (wc_fields
= 0; wc_fields
< (1u << CLS_N_FIELDS
); wc_fields
++) {
503 struct classifier cls
;
504 struct test_rule
*rule
, *tcls_rule
;
507 rule
= make_rule(wc_fields
,
508 hash_bytes(&wc_fields
, sizeof wc_fields
, 0), 0);
510 classifier_init(&cls
);
513 tcls_rule
= tcls_insert(&tcls
, rule
);
515 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
517 classifier_insert_exact(&cls
, &rule
->cls_rule
);
519 check_tables(&cls
, 1, 1, 1);
520 compare_classifiers(&cls
, &tcls
);
522 classifier_remove(&cls
, &rule
->cls_rule
);
523 tcls_remove(&tcls
, tcls_rule
);
524 assert(classifier_is_empty(&cls
));
525 assert(tcls_is_empty(&tcls
));
526 compare_classifiers(&cls
, &tcls
);
529 classifier_destroy(&cls
);
534 /* Tests replacing one rule by another. */
536 test_rule_replacement(void)
538 unsigned int wc_fields
;
540 for (wc_fields
= 0; wc_fields
< (1u << CLS_N_FIELDS
); wc_fields
++) {
541 struct classifier cls
;
542 struct test_rule
*rule1
;
543 struct test_rule
*rule2
;
546 rule1
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
547 rule2
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
551 classifier_init(&cls
);
553 tcls_insert(&tcls
, rule1
);
554 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
555 check_tables(&cls
, 1, 1, 1);
556 compare_classifiers(&cls
, &tcls
);
560 tcls_insert(&tcls
, rule2
);
561 assert(test_rule_from_cls_rule(
562 classifier_insert(&cls
, &rule2
->cls_rule
)) == rule1
);
564 check_tables(&cls
, 1, 1, 1);
565 compare_classifiers(&cls
, &tcls
);
567 destroy_classifier(&cls
);
572 table_mask(int table
)
574 return ((1u << CLS_N_FIELDS
) - 1) & ~((1u << table
) - 1);
578 random_wcf_in_table(int table
, int seed
)
580 int wc_fields
= (1u << table
) | hash_int(seed
, 0);
581 return wc_fields
& table_mask(table
);
584 /* Tests classification with two rules at a time that fall into the same
587 test_two_rules_in_one_bucket(void)
589 int table
, rel_pri
, wcf_pat
, value_pat
;
591 for (table
= 0; table
<= CLS_N_FIELDS
; table
++) {
592 for (rel_pri
= -1; rel_pri
<= +1; rel_pri
++) {
593 for (wcf_pat
= 0; wcf_pat
< 4; wcf_pat
++) {
594 int n_value_pats
= table
== CLS_N_FIELDS
- 1 ? 1 : 2;
595 for (value_pat
= 0; value_pat
< n_value_pats
; value_pat
++) {
596 struct test_rule
*rule1
, *tcls_rule1
;
597 struct test_rule
*rule2
, *tcls_rule2
;
598 struct test_rule
*displaced_rule
;
599 struct classifier cls
;
601 unsigned int pri1
, pri2
;
604 if (table
!= CLS_F_IDX_EXACT
) {
605 /* We can use identical priorities in this test because
606 * the classifier always chooses the rule added later
607 * for equal-priority rules that fall into the same
609 pri1
= table
* 257 + 50;
610 pri2
= pri1
+ rel_pri
;
613 ? random_wcf_in_table(table
, pri1
)
616 ? random_wcf_in_table(table
, pri2
)
619 wcf1
&= ~(1u << (CLS_N_FIELDS
- 1));
620 wcf2
&= ~(1u << (CLS_N_FIELDS
- 1));
623 /* This classifier always puts exact-match rules at
624 * maximum priority. */
625 pri1
= pri2
= UINT_MAX
;
627 /* No wildcard fields. */
631 rule1
= make_rule(wcf1
, pri1
, 0);
632 rule2
= make_rule(wcf2
, pri2
,
633 value_pat
<< (CLS_N_FIELDS
- 1));
635 classifier_init(&cls
);
638 tcls_rule1
= tcls_insert(&tcls
, rule1
);
639 tcls_rule2
= tcls_insert(&tcls
, rule2
);
640 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
641 displaced_rule
= test_rule_from_cls_rule(
642 classifier_insert(&cls
, &rule2
->cls_rule
));
643 if (wcf1
!= wcf2
|| pri1
!= pri2
|| value_pat
) {
644 assert(!displaced_rule
);
646 check_tables(&cls
, 1, 1, 2);
647 compare_classifiers(&cls
, &tcls
);
649 classifier_remove(&cls
, &rule1
->cls_rule
);
650 tcls_remove(&tcls
, tcls_rule1
);
651 check_tables(&cls
, 1, 1, 1);
652 compare_classifiers(&cls
, &tcls
);
654 assert(displaced_rule
== rule1
);
655 check_tables(&cls
, 1, 1, 1);
656 compare_classifiers(&cls
, &tcls
);
660 classifier_remove(&cls
, &rule2
->cls_rule
);
661 tcls_remove(&tcls
, tcls_rule2
);
662 compare_classifiers(&cls
, &tcls
);
665 destroy_classifier(&cls
);
673 /* Tests classification with two rules at a time that fall into the same
674 * table but different buckets. */
676 test_two_rules_in_one_table(void)
678 int table
, rel_pri
, wcf_pat
;
680 /* Skip tables 0 and CLS_F_IDX_EXACT because they have one bucket. */
681 for (table
= 1; table
< CLS_N_FIELDS
; table
++) {
682 for (rel_pri
= -1; rel_pri
<= +1; rel_pri
++) {
683 for (wcf_pat
= 0; wcf_pat
< 5; wcf_pat
++) {
684 struct test_rule
*rule1
, *tcls_rule1
;
685 struct test_rule
*rule2
, *tcls_rule2
;
686 struct classifier cls
;
688 unsigned int pri1
, pri2
;
690 int value_mask
, value_pat1
, value_pat2
;
693 /* We can use identical priorities in this test because the
694 * classifier always chooses the rule added later for
695 * equal-priority rules that fall into the same table. */
696 pri1
= table
* 257 + 50;
697 pri2
= pri1
+ rel_pri
;
700 wcf1
= wcf2
= random_wcf_in_table(table
, pri1
);
703 ? random_wcf_in_table(table
, pri1
)
706 ? random_wcf_in_table(table
, pri2
)
710 /* Generate value patterns that will put the two rules into
711 * different buckets. */
712 value_mask
= ((1u << table
) - 1);
713 value_pat1
= hash_int(pri1
, 1) & value_mask
;
716 value_pat2
= (hash_int(pri2
, i
++) & value_mask
);
717 } while (value_pat1
== value_pat2
);
718 rule1
= make_rule(wcf1
, pri1
, value_pat1
);
719 rule2
= make_rule(wcf2
, pri2
, value_pat2
);
721 classifier_init(&cls
);
724 tcls_rule1
= tcls_insert(&tcls
, rule1
);
725 tcls_rule2
= tcls_insert(&tcls
, rule2
);
726 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
727 assert(!classifier_insert(&cls
, &rule2
->cls_rule
));
728 check_tables(&cls
, 1, 2, 2);
729 compare_classifiers(&cls
, &tcls
);
731 classifier_remove(&cls
, &rule1
->cls_rule
);
732 tcls_remove(&tcls
, tcls_rule1
);
733 check_tables(&cls
, 1, 1, 1);
734 compare_classifiers(&cls
, &tcls
);
737 classifier_remove(&cls
, &rule2
->cls_rule
);
738 tcls_remove(&tcls
, tcls_rule2
);
739 compare_classifiers(&cls
, &tcls
);
742 classifier_destroy(&cls
);
749 /* Tests classification with two rules at a time that fall into different
752 test_two_rules_in_different_tables(void)
754 int table1
, table2
, rel_pri
, wcf_pat
;
756 for (table1
= 0; table1
< CLS_N_FIELDS
; table1
++) {
757 for (table2
= table1
+ 1; table2
<= CLS_N_FIELDS
; table2
++) {
758 for (rel_pri
= 0; rel_pri
< 2; rel_pri
++) {
759 for (wcf_pat
= 0; wcf_pat
< 4; wcf_pat
++) {
760 struct test_rule
*rule1
, *tcls_rule1
;
761 struct test_rule
*rule2
, *tcls_rule2
;
762 struct classifier cls
;
764 unsigned int pri1
, pri2
;
767 /* We must use unique priorities in this test because the
768 * classifier makes the rule choice undefined for rules of
769 * equal priority that fall into different tables. (In
770 * practice, lower-numbered tables win.) */
771 pri1
= table1
* 257 + 50;
772 pri2
= rel_pri
? pri1
- 1 : pri1
+ 1;
775 ? random_wcf_in_table(table1
, pri1
)
778 ? random_wcf_in_table(table2
, pri2
)
781 if (table2
== CLS_F_IDX_EXACT
) {
786 rule1
= make_rule(wcf1
, pri1
, 0);
787 rule2
= make_rule(wcf2
, pri2
, 0);
789 classifier_init(&cls
);
792 tcls_rule1
= tcls_insert(&tcls
, rule1
);
793 tcls_rule2
= tcls_insert(&tcls
, rule2
);
794 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
795 assert(!classifier_insert(&cls
, &rule2
->cls_rule
));
796 check_tables(&cls
, 2, 2, 2);
797 compare_classifiers(&cls
, &tcls
);
799 classifier_remove(&cls
, &rule1
->cls_rule
);
800 tcls_remove(&tcls
, tcls_rule1
);
801 check_tables(&cls
, 1, 1, 1);
802 compare_classifiers(&cls
, &tcls
);
805 classifier_remove(&cls
, &rule2
->cls_rule
);
806 tcls_remove(&tcls
, tcls_rule2
);
807 compare_classifiers(&cls
, &tcls
);
810 classifier_destroy(&cls
);
818 /* Tests classification with many rules at a time that fall into the same
819 * bucket but have unique priorities (and various wildcards). */
821 test_many_rules_in_one_bucket(void)
823 enum { MAX_RULES
= 50 };
824 int iteration
, table
;
826 for (iteration
= 0; iteration
< 3; iteration
++) {
827 for (table
= 0; table
<= CLS_N_FIELDS
; table
++) {
828 unsigned int priorities
[MAX_RULES
];
829 struct classifier cls
;
833 srand(hash_int(table
, iteration
));
834 for (i
= 0; i
< MAX_RULES
; i
++) {
835 priorities
[i
] = i
* 129;
837 shuffle(priorities
, ARRAY_SIZE(priorities
));
839 classifier_init(&cls
);
842 for (i
= 0; i
< MAX_RULES
; i
++) {
843 struct test_rule
*rule
;
844 unsigned int priority
= priorities
[i
];
847 wcf
= random_wcf_in_table(table
, priority
);
848 rule
= make_rule(wcf
, priority
,
849 table
== CLS_F_IDX_EXACT
? i
: 1234);
850 tcls_insert(&tcls
, rule
);
851 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
852 check_tables(&cls
, 1, 1, i
+ 1);
853 compare_classifiers(&cls
, &tcls
);
856 destroy_classifier(&cls
);
862 /* Tests classification with many rules at a time that fall into the same
863 * table but random buckets. */
865 test_many_rules_in_one_table(void)
867 enum { MAX_RULES
= 50 };
868 int iteration
, table
;
870 for (iteration
= 0; iteration
< 3; iteration
++) {
871 for (table
= 0; table
< CLS_N_FIELDS
; table
++) {
872 unsigned int priorities
[MAX_RULES
];
873 struct classifier cls
;
877 srand(hash_int(table
, iteration
));
878 for (i
= 0; i
< MAX_RULES
; i
++) {
879 priorities
[i
] = i
* 129;
881 shuffle(priorities
, ARRAY_SIZE(priorities
));
883 classifier_init(&cls
);
886 for (i
= 0; i
< MAX_RULES
; i
++) {
887 struct test_rule
*rule
;
888 unsigned int priority
= priorities
[i
];
891 wcf
= random_wcf_in_table(table
, priority
);
892 rule
= make_rule(wcf
, priority
, hash_int(priority
, 1));
893 tcls_insert(&tcls
, rule
);
894 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
895 check_tables(&cls
, 1, -1, i
+ 1);
896 compare_classifiers(&cls
, &tcls
);
899 destroy_classifier(&cls
);
905 /* Tests classification with many rules at a time that fall into random buckets
906 * in random tables. */
908 test_many_rules_in_different_tables(void)
910 enum { MAX_RULES
= 50 };
913 for (iteration
= 0; iteration
< 30; iteration
++) {
914 unsigned int priorities
[MAX_RULES
];
915 struct classifier cls
;
920 for (i
= 0; i
< MAX_RULES
; i
++) {
921 priorities
[i
] = i
* 129;
923 shuffle(priorities
, ARRAY_SIZE(priorities
));
925 classifier_init(&cls
);
928 for (i
= 0; i
< MAX_RULES
; i
++) {
929 struct test_rule
*rule
;
930 unsigned int priority
= priorities
[i
];
931 int table
= rand() % (CLS_N_FIELDS
+ 1);
932 int wcf
= random_wcf_in_table(table
, rand());
933 int value_pat
= rand() & ((1u << CLS_N_FIELDS
) - 1);
934 rule
= make_rule(wcf
, priority
, value_pat
);
935 tcls_insert(&tcls
, rule
);
936 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
937 check_tables(&cls
, -1, -1, i
+ 1);
938 compare_classifiers(&cls
, &tcls
);
941 while (!classifier_is_empty(&cls
)) {
942 struct test_rule
*rule
= xmemdup(tcls
.rules
[rand() % tcls
.n_rules
],
943 sizeof(struct test_rule
));
944 int include
= rand() % 2 ? CLS_INC_WILD
: CLS_INC_EXACT
;
945 include
|= (rule
->cls_rule
.wc
.wildcards
946 ? CLS_INC_WILD
: CLS_INC_EXACT
);
947 classifier_for_each_match(&cls
, &rule
->cls_rule
, include
,
949 tcls_delete_matches(&tcls
, &rule
->cls_rule
, include
);
950 compare_classifiers(&cls
, &tcls
);
956 destroy_classifier(&cls
);
962 run_test(void (*function
)(void))
973 run_test(test_empty
);
974 run_test(test_destroy_null
);
975 run_test(test_single_rule
);
976 run_test(test_rule_replacement
);
977 run_test(test_two_rules_in_one_bucket
);
978 run_test(test_two_rules_in_one_table
);
979 run_test(test_two_rules_in_different_tables
);
980 run_test(test_many_rules_in_one_bucket
);
981 run_test(test_many_rules_in_one_table
);
982 run_test(test_many_rules_in_different_tables
);